糖醋小鸡块的blog
0%

2024-SICTF-#Round3-wp-crypto

发表于 更新于 分类于 Valine：

简单做一下比赛记录。

[签到]Vigenere

题目描述：

1
19世纪末，无法破译的密码被应用于一场大规模内战，它在20世纪初期更是被认为是无法被转化的密码。后来，人们走到了21世纪，有着更高的算力，这种无法破译的密码也被高算力轻松攻破，你的任务便是使用你的高算力，跨越历史的长河，攻破这份密文！

题目：

1
2
3
4
5
6
7
Gn taj xirly gf Fxgjuakd, oe igywnd mt tegbs mnrxxlrivywd sngearbsw wakksre. Bs kpimj gf tank, it bx gur bslenmngn th jfdetagur mt ceei yze Ugnled Lystel tx Amxwaca gjmtrtq.

An taj wvegy gf tank nom xmccxjvinz, bw prhugse ts sllbffce hs lhe ytdlopnfg btxas wbyz Meqnuo: Tafl we lmsll ffce wtw logxyzer tsv madj heavj logxyzer. Pj khaeq yivLNUTF{4695vft9-fd68-4684-uj81-u6c1avg6uaft}j yenxwgus ynfanvnsl snuhorm, ffd ag zfdekxlanwnfg og tmr ptwl thty Eexbhg is mt jechsiuek yze lhxl tekwatokd an Nxb Eexbhg, Teqfk, anw Fjizhss. Thx iwtabqk of ljltlxrwnt tww leyy lo yhz.

Qou tww inlyjucmjv to bsxorf yze Pkjkidxsl [of Fjpich] tx thx ftovx nf thx ljeamjkt chsxidxsue al xgon tx at il hwrttnf thty lhekj oile gw an hzlbrxfc of pfj wimm lhe Nsatew Xlatxx snd lzygely lham yze Pkjkidxsl, on ank owg nfitbflivx, nfvimj Bapts lo ifrwdityw adajjenvj oita yzis iqsn; am yze strw tifj, gffxw lo mxiaatx gwtwxjf Jaiff anw tmrsxqnes.

Iqwasx hsll mt lhe tylenmngn oy yze Pkjkidxsl thty lhe kzlhlxxk emiqgymxsl of hzj suursrigjk nop txfekx lhe iwgspxhl of vtepeeqang Xsylagi lo mtpw pethw in t kww mhslhs.

直接用维吉尼亚爆破网站就可以得到明文：

Vigenere Solver | guballa.de

1
2
3
4
5
6
7
On the first of February, we intend to begin unrestricted submarine warfare. In spite of this, it is our intention to endeavour to keep the United States of America neutral.

In the event of this not succeeding, we propose an alliance on the following basis with Mexico: That we shall make war together and make peace together. We shall givSICTF{4695cab9-fd68-4684-be81-c6c1acb6cafa}e generous financial support, and an understanding on our part that Mexico is to reconquer the lost territory in New Mexico, Texas, and Arizona. The details of settlement are left to you.

You are instructed to inform the President [of Mexico] of the above in the greatest confidence as soon as it is certain that there will be an outbreak of war with the United States and suggest that the President, on his own initiative, invite Japan to immediate adherence with this plan; at the same time, offer to mediate between Japan and ourselves.

Please call to the attention of the President that the ruthless employment of our submarines now offers the prospect of compelling England to make peace in a few months.



签到，确信！

题目描述：

1
都坤叭是兄弟，我怎么会骗你呢!

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)
def gen_keys(bits):
    while 1:
        p = getPrime(bits)
        q = sum([p**i for i in range(7)])
        if isPrime(q):
            r = getPrime(1024)
            n = p*q*r
            return p,n
p,n = gen_keys(512)
e = 65537
c = pow(m,e,n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
'''
n = 8361361624563191168612863710516449028280757632934603412143152925186847721821552879338608951120157631182699762833743097837368740526055736516080136520584848113137087581886426335191207688807063024096128001406698217998816782335655663803544853496060418931569545571397849643826584234431049002394772877263603049736723071392989824939202362631409164434715938662038795641314189628730614978217987868150651491343161526447894569241770090377633602058561239329450046036247193745885174295365633411482121644408648089046016960479100220850953009927778950304754339013541019536413880264074456433907671670049288317945540495496615531150916647050158936010095037412334662561046016163777575736952349827380039938526168715655649566952708788485104126900723003264019513888897942175890007711026288941687256962012799264387545892832762304320287592575602683673845399984039272350929803217492617502601005613778976109701842829008365226259492848134417818535629827769342262020775115695472218876430557026471282526042545195944063078523279341459199475911203966762751381334277716236740637021416311325243028569997303341317394525345879188523948991698489667794912052436245063998637376874151553809424581376068719814532246179297851206862505952437301253313660876231136285877214949094995458997630235764635059528016149006613720287102941868517244509854875672887445099733909912598895743707420454623997740143407206090319567531144126090072331
e = 65537
c = 990174418341944658163682355081485155265287928299806085314916265580657672513493698560580484907432207730887132062242640756706695937403268682912083148568866147011247510439837340945334451110125182595397920602074775022416454918954623612449584637584716343806255917090525904201284852578834232447821716829253065610989317909188784426328951520866152936279891872183954439348449359491526360671152193735260099077198986264364568046834399064514350538329990985131052947670063605611113730246128926850242471820709957158609175376867993700411738314237400038584470826914946434498322430741797570259936266226325667814521838420733061335969071245580657187544161772619889518845348639672820212709030227999963744593715194928502606910452777687735614033404646237092067644786266390652682476817862879933305687452549301456541574678459748029511685529779653056108795644495442515066731075232130730326258404497646551885443146629498236191794065050199535063169471112533284663197357635908054343683637354352034115772227442563180462771041527246803861110504563589660801224223152060573760388045791699221007556911597792387829416892037414283131499832672222157450742460666013331962249415807439258417736128976044272555922344342725850924271905056434303543500959556998454661274520986141613977331669376614647269667276594163516040422089616099849315644424644920145900066426839607058422686565517159251903275091124418838917480242517812783383
'''

改编自ImaginaryCTF的sus一题，增加了多项式的度，但是原理上没有任何差异，具体解释之前有写过：

Crypto趣题-RSA(一) | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *

n = 8361361624563191168612863710516449028280757632934603412143152925186847721821552879338608951120157631182699762833743097837368740526055736516080136520584848113137087581886426335191207688807063024096128001406698217998816782335655663803544853496060418931569545571397849643826584234431049002394772877263603049736723071392989824939202362631409164434715938662038795641314189628730614978217987868150651491343161526447894569241770090377633602058561239329450046036247193745885174295365633411482121644408648089046016960479100220850953009927778950304754339013541019536413880264074456433907671670049288317945540495496615531150916647050158936010095037412334662561046016163777575736952349827380039938526168715655649566952708788485104126900723003264019513888897942175890007711026288941687256962012799264387545892832762304320287592575602683673845399984039272350929803217492617502601005613778976109701842829008365226259492848134417818535629827769342262020775115695472218876430557026471282526042545195944063078523279341459199475911203966762751381334277716236740637021416311325243028569997303341317394525345879188523948991698489667794912052436245063998637376874151553809424581376068719814532246179297851206862505952437301253313660876231136285877214949094995458997630235764635059528016149006613720287102941868517244509854875672887445099733909912598895743707420454623997740143407206090319567531144126090072331
e = 65537
c = 990174418341944658163682355081485155265287928299806085314916265580657672513493698560580484907432207730887132062242640756706695937403268682912083148568866147011247510439837340945334451110125182595397920602074775022416454918954623612449584637584716343806255917090525904201284852578834232447821716829253065610989317909188784426328951520866152936279891872183954439348449359491526360671152193735260099077198986264364568046834399064514350538329990985131052947670063605611113730246128926850242471820709957158609175376867993700411738314237400038584470826914946434498322430741797570259936266226325667814521838420733061335969071245580657187544161772619889518845348639672820212709030227999963744593715194928502606910452777687735614033404646237092067644786266390652682476817862879933305687452549301456541574678459748029511685529779653056108795644495442515066731075232130730326258404497646551885443146629498236191794065050199535063169471112533284663197357635908054343683637354352034115772227442563180462771041527246803861110504563589660801224223152060573760388045791699221007556911597792387829416892037414283131499832672222157450742460666013331962249415807439258417736128976044272555922344342725850924271905056434303543500959556998454661274520986141613977331669376614647269667276594163516040422089616099849315644424644920145900066426839607058422686565517159251903275091124418838917480242517812783383
k = 7

R = Zmod(n)["x"]
while True:
    Q = R.quo(R.random_element(k))
    pp = gcd(ZZ(list(Q.random_element() ^ n)[1]), n)
    if pp != 1:
        qq = sum([pp**i for i in range(k)])
        rr = n // (pp * qq)
        assert n == pp * qq * rr
        break
phi = (pp - 1) * (qq - 1) * (rr - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))

#SICTF{d9428fc7-fa3a-4096-8ec9-191c0a4562ff}



easyLattice

题目描述：

1
这是真签到

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
from secret import flag
import gmpy2

assert len(flag) == 47

f = bytes_to_long(flag)
p = getPrime(512)
g = getPrime(128)
h = gmpy2.invert(f, p) * g % p

print('h =', h)
print('p =', p)

"""
h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947     
"""

题目基于NTRU，给出如下关系式：

以及h和p的值，要求解出作为flag的f值。同时知道f是47字节，g是128字节。

可以看出，f和g在模p下依然算小量，所以用格规约的思路是不会变的，依然是移项构造出等式：

然后造出如下格：

这个格具有的线性关系是：

可以看出目标向量中g远小于f，所以需要配平一下，为了能更精确的使两者数量级相等，可以利用flag是”S”开头的这一特点，其最高位是0而第七位是1，从而更精确确定要配的系数。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *

h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947     

T = 2^(47*8-1-128)
L = Matrix(ZZ, [[1, T*h],
                [0, T*p]])

res = L.LLL()[0]
print(long_to_bytes(int(abs(res[0]))))

#SICTF{e3fea01c-18f3-4638-9544-9201393940a9}



铜匠

题目描述：

1
三年二班的皮郜伟同学，他的理想是做一名铜匠，为此他决定深入学习关于铜匠的知识

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from Crypto.Util.number import *
from enc import flag



def Decimal_conversion(num):
    if num == 0:
        return '0'
    digits = []
    while num:
        digits.append(str(num % 5))
        num //= 5
    return ''.join(reversed(digits))

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
e = 65537
n = p*q
c = pow(m,e,n)
print(f"leak = {Decimal_conversion(p)[:112]}")
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
'''
leak = 2011133132443111302000224204142244403203442000141102312242343143241244243020003333022112141220422134444214010012
n = 85988668134257353631742597258304937106964673395852009846703777410474172989069717247424903079500594820235304351355706519069516847244761609583338251489134035212061654870087550317540291994559481862615812258493738064606592165529948648774081655902831715928483206013332330998262897765489820121129058926463847702821
e = 65537
c = 64708526479058278743788046708923650158905888858865427385501446781738669889375403360886995849554813207230509920789341593771929287415439407977283018525484281064769128358863513387658744063469874845446480637925790150835186431234289848506337341595817156444941964510251032210939739594241869190746437858135599624562
'''

题目基于p高位泄露，不同的是泄露的是p的112个五进制高位，实测一下可以知道512bit的p一定是221个五进制位，所以其实未知的只有109个五进制位，结合以前做过的题目知道，就算只知道256bit都是可以爆破出来的，所以这题有了更多的信息，就肯定也可以爆破。

然后由于不确定p和q的大小关系，所以beta稳妥一些取0.49，同时考虑到速度问题和上界问题，epsilon取0.01依然最合适，然后按如下方式算界：

可以大概算出大概会差两个五进制位，所以就爆破两个五进制低位就能copper出来。事实上爆破一位也可以。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from Crypto.Util.number import *
from tqdm import *

leak = "2011133132443111302000224204142244403203442000141102312242343143241244243020003333022112141220422134444214010012"
n = 85988668134257353631742597258304937106964673395852009846703777410474172989069717247424903079500594820235304351355706519069516847244761609583338251489134035212061654870087550317540291994559481862615812258493738064606592165529948648774081655902831715928483206013332330998262897765489820121129058926463847702821
e = 65537
c = 64708526479058278743788046708923650158905888858865427385501446781738669889375403360886995849554813207230509920789341593771929287415439407977283018525484281064769128358863513387658744063469874845446480637925790150835186431234289848506337341595817156444941964510251032210939739594241869190746437858135599624562

ph = int(leak+(221-112)*"0",5)
if(0):
    for i in trange(5^2):
        PR.<x> = PolynomialRing(Zmod(n))
        f = ph + 5^2*x + i
        f = f.monic()
        res = f.small_roots(beta = 0.49,X = 5^(109-2),epsilon = 0.01)
        if(res != []):
            print(i,res)

pl = 583068978003981313997513183180671820624155651436585878218014495402013030123
p = ph + 5^2*pl + 3
q = n // p
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(int(pow(c,d,n))))


#SICTF{1d213ffc-d5dc-42d0-b206-e9a0c1a3cb69}



SuperbRSA

题目描述：

1
CRYPTO真的很难吗？Ö_O不会吧不会吧！，一定要相信自己咩~

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#user:mumu666
from Crypto.Util.number import *
p=getPrime(1024)
q=getPrime(1024)
n=p*q
e1=55
e2=200
m=bytes_to_long("flag")
assert(pow(m,5) < n)
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)
print("n=",n)
print("c1=",c1)
print("c2=",c2)

n= 19006830358118902392432453595802675566730850352890246995920642811967821259388009049803513102750594524106471709641202019832682438027312468849299985832675191795417160553379580813410722359089872519372049229233732405993062464286888889084640878784209014165871696882564834896322508054231777967011195636564463806270998326936161449009988434249178477100127347406759932149010712091376183710135615375272671888541233275415737155953323133439644529709898791881795186775830217884663044495979067807418758455237701315019683802437323177125493076113419739827430282311018083976114158159925450746712064639569301925672742186294237113199023
c1= 276245243658976720066605903875366763552720328374098965164676247771817997950424168480909517684516498439306387133611184795758628248588201187138612090081389226321683486308199743311842513053259894661221013008371261704678716150646764446208833447643781574516045641493770778735363586857160147826684394417412837449465273160781074676966630398315417741542529612480836572205781076576325382832502694868883931680720558621770570349864399879523171995953720198118660355479626037129047327185224203109006251809257919143284157354935005710902589809259500117996982503679601132486140677013625335552533104471327456798955341220640782369529
c2= 11734019659226247713821792108026989060106712358397514827024912309860741729438494689480531875833287268454669859568719053896346471360750027952226633173559594064466850413737504267807599435679616522026241111887294138123201104718849744300769676961585732810579953221056338076885840743126397063074940281522137794340822594577352361616598702143477379145284687427705913831885493512616944504612474278405909277188118896882441812469679494459216431405139478548192152811441169176134750079073317011232934250365454908280676079801770043968006983848495835089055956722848080915898151352242215210071011331098761828031786300276771001839021

题目给出了两组密文：

e1和e2的gcd是5，所以可以共模攻击得到m^5模n下的值，而由于题目保证了m^5小于n所以可以开五次方得到m。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from gmpy2 import *

e1=55
e2=200

n= 19006830358118902392432453595802675566730850352890246995920642811967821259388009049803513102750594524106471709641202019832682438027312468849299985832675191795417160553379580813410722359089872519372049229233732405993062464286888889084640878784209014165871696882564834896322508054231777967011195636564463806270998326936161449009988434249178477100127347406759932149010712091376183710135615375272671888541233275415737155953323133439644529709898791881795186775830217884663044495979067807418758455237701315019683802437323177125493076113419739827430282311018083976114158159925450746712064639569301925672742186294237113199023
c1= 276245243658976720066605903875366763552720328374098965164676247771817997950424168480909517684516498439306387133611184795758628248588201187138612090081389226321683486308199743311842513053259894661221013008371261704678716150646764446208833447643781574516045641493770778735363586857160147826684394417412837449465273160781074676966630398315417741542529612480836572205781076576325382832502694868883931680720558621770570349864399879523171995953720198118660355479626037129047327185224203109006251809257919143284157354935005710902589809259500117996982503679601132486140677013625335552533104471327456798955341220640782369529
c2= 11734019659226247713821792108026989060106712358397514827024912309860741729438494689480531875833287268454669859568719053896346471360750027952226633173559594064466850413737504267807599435679616522026241111887294138123201104718849744300769676961585732810579953221056338076885840743126397063074940281522137794340822594577352361616598702143477379145284687427705913831885493512616944504612474278405909277188118896882441812469679494459216431405139478548192152811441169176134750079073317011232934250365454908280676079801770043968006983848495835089055956722848080915898151352242215210071011331098761828031786300276771001839021

d,s,t = gcdext(e1,e2)
m5 = pow(c1,s,n)*pow(c2,t,n) % n

print(long_to_bytes(iroot(m5,5)[0]))

#SICTF{S0_Great_RSA_Have_Y0u_Learned?}



[进阶]2024_New_Setback

题目描述：

1
新的一年，我们总要有一个新的起点🕛，你们说对吧🎉！

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#user:mumu666

from Crypto.Util.number import *
from secret import flag, Curve

def happy(C, P):
    c, d, p = C
    u, v = P
    return (u**2 + v**2 - c**2 * (1 + d * u**2*v**2)) % p == 0

def new(C, P, Q):
    c, d, p = C
    u1, v1 = P
    u2, v2 = Q
    assert happy(C, P) and happy(C, Q)
    u3 = (u1 * v2 + v1 * u2) * inverse(c * (1 + d * u1 * u2 * v1 * v2), p) % p
    v3 = (v1 * v2 - u1 * u2) * inverse(c * (1 - d * u1 * u2 * v1 * v2), p) % p
    return (int(u3), int(v3))

def year(C, P, m):
    assert happy(C, P)
    c, d, p = C
    B = bin(m)[2:]
    l = len(B)
    u, v = P
    PP = (-u, v)
    O = new(C, P, PP)
    Q = O
    if m == 0:
        return O
    elif m == 1:
        return P
    else:
        for _ in range(l-1):
            P = new(C, P, P)
        m = m - 2**(l-1)
        Q, P = P, (u, v)
        return new(C, Q, year(C, P, m))

c, d, p = Curve

flag = flag.lstrip(b'SICTF{').rstrip(b'}')
l = len(flag)
l_flag, r_flag = flag[:l // 2], flag[l // 2:]

m1, m2 = bytes_to_long(l_flag), bytes_to_long(r_flag)
assert m1 < p and m2 < p

P = (398011447251267732058427934569710020713094, 548950454294712661054528329798266699762662)
Q = (139255151342889674616838168412769112246165, 649791718379009629228240558980851356197207)

print(f'happy(C, P) = {happy(Curve, P)}')
print(f'happy(C, Q) = {happy(Curve, Q)}')

print(f'P = {P}')
print(f'Q = {Q}')

print(f'm1 * P = {year(Curve, P, m1)}')
print(f'm2 * Q = {year(Curve, Q, m2)}')



"""
happy(C, P) = True
happy(C, Q) = True
P = (398011447251267732058427934569710020713094, 548950454294712661054528329798266699762662)
Q = (139255151342889674616838168412769112246165, 649791718379009629228240558980851356197207)
m1 * P = (730393937659426993430595540476247076383331, 461597565155009635099537158476419433012710)
m2 * Q = (500532897653416664117493978883484252869079, 620853965501593867437705135137758828401933) 
"""

题目给了一条曲线：

然后给了曲线上的两点P、Q的坐标，以及两个倍点坐标：

要求出作为flag两部分的m1、m2。

这是扭曲爱德华兹曲线在a=1时的方程，而这种曲线向Weierstrass曲线的映射之前也出现过：

Crypto趣题-曲线 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

所以，如果可以求出曲线方程的所有参数，就可以映射到ECC上去求DLP，而观察到坐标都不是特别大，说明p也不大，DLP应该挺容易求。又因为题目提供了四个点，所以可以用四个点的坐标去造四个多项式，然后groebner求出c、d和p。

然而求出来会发现有点小问题，就是映射回去时发现有些值模p下的逆元并不存在，分解发现p还含有3和7两个因子，但可以验证，给出的四个点其实也在模(p/3/7)的曲线上，所以可以直接取去除了小因子的p当模数，然后映射到ECC上求DLP。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from Crypto.Util.number import *

#part1 get c2、d
P = (398011447251267732058427934569710020713094, 548950454294712661054528329798266699762662)
Q = (139255151342889674616838168412769112246165, 649791718379009629228240558980851356197207)
C1 = (730393937659426993430595540476247076383331, 461597565155009635099537158476419433012710)
C2 = (500532897653416664117493978883484252869079, 620853965501593867437705135137758828401933) 
if(0):
    PR.<c,d> = PolynomialRing(ZZ)
    f1 = P[0]**2 + P[1]**2 - c**2 * (1 + d * P[0]**2*P[1]**2)
    f2 = Q[0]**2 + Q[1]**2 - c**2 * (1 + d * Q[0]**2*Q[1]**2)
    f3 = C1[0]**2 + C1[1]**2 - c**2 * (1 + d * C1[0]**2*C1[1]**2)
    f4 = C2[0]**2 + C2[1]**2 - c**2 * (1 + d * C2[0]**2*C2[1]**2)
    res = ideal([f1,f2,f3,f4]).groebner_basis()
    print(res)
p = 18983346087633426019400112058348303476269889
d = p-1267506405851766513801807982398420823635884
c2 = p-11256226422403535024125759760236595858726933
a = 1
p = p//3//7
#get c
PR.<c> = PolynomialRing(Zmod(p))
f = c^2 - c2
#print(f.roots())

c = 662698094423288904843781932253259903384619
#c = 241270766892588524651461499096659309771090



#part2 map to ECC
F = GF(p)
dd = F(d*c^4)
A = F(2) * F(a+dd) / F(a-dd)
B = F(4) / F(a-dd)
a = F(3-A^2) / F(3*B^2)
b = F(2*A^3-9*A) / F(27*B^3)

def edwards_to_ECC(x,y):
    x1 = F(x) / F(c)
    y1 = F(y) / F(c)
    #now curve is a*x^2+y^2 = 1+dd*x^2*y^2

    x2 = F(1+y1) / F(1-y1)
    y2 = F(x2) / F(x1)
    #now curve is By^2 = x^3 + Ax^2 + x

    x3 = (F(3*x2) + F(A)) / F(3*B)
    y3 = F(y2) / F(B)
    #now curve is y^2 = x^3 + ax + b

    return (x3,y3)
 
def ECC_to_edwards(x,y):
    x2 = (F(x) * F(3*B) - F(A)) / F(3)
    y2 = F(y) * F(B)
    #now curve is By^2 = x^3 + Ax^2 + x

    x1 = F(x2) / F(y2)
    y1 = F(1) - (F(2) / F(x2+1))
    #now curve is a*x^2+y^2 = 1+dd*x^2*y^2

    x_ = F(x1) * F(c)
    y_ = F(y1) * F(c)
    #now curve is a*x^2+y^2 = c^2(1+d*x^2*y^2)
    
    return (x_,y_)
 
E = EllipticCurve(GF(p), [a, b])
P = E(edwards_to_ECC(P[0],P[1]))
Q = E(edwards_to_ECC(Q[0],Q[1]))
C1 = E(edwards_to_ECC(C1[0],C1[1]))
C2 = E(edwards_to_ECC(C2[0],C2[1]))


#part3 Dlog
m1 = int(P.discrete_log(C1))
m2 = int(Q.discrete_log(C2))

print(long_to_bytes(m1))
print(long_to_bytes(m2))

#SICTF{nOt_50_3a5Y_Edw4rDs_3LlipT!c_CURv3}



[进阶]easy_or_baby_RSA?

题目描述：

1
众所周知，easy是真易贼，baby是真卑鄙

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from Crypto.Util.number import *
import gmpy2
from enc import flag


m = bytes_to_long(flag)
p = getPrime(256)
q = getPrime(256)
n = (p**5)*(q**3)
phi = (p-1)*(q-1)*p**4 * q**2
d = getPrime(1380)
e = gmpy2.invert(d,phi)
p1 = gmpy2.next_prime(p)
q1 = gmpy2.next_prime(q)
c = pow(m,65537,p1*q1)

print(f"c = {c}")
print(f"n = {n}")
print(f"e = {e}")

'''
c = 6027704939934795526809476320408984749353451163184148193613218899917989403800738729505135647560822568147775955030636790796412038749080589962404088890138
n = 2345049742327685796181532105032554795628696111708534285951012187089560814230641663133312117797131139088986342455315166062482479446527815702735474197358418746066993291802284464812612727625991647573889402281825863578807474887341632160586307943897790827019291411639756252138594856687013363652094621849674259604512491449809337670874218320926522274379234396955495643125680407916326561528774056618181536326260093822819468635513422755218190798616168156924793527386350080400722536575372660262573683231490166520738579903818495107264328324326819989553511070207494208500239603511665056894947107356065440333537271115434438827753
e = 1560967245790387854530279132085915310737094193704812456970549221459036227794862560384548159924112528879771688534015861357630951162558357151823378870345945435342412220708167081427844035498174919749839232806280901968067512188264340755833308035745702731211924571583963089915893479992177245815565483658484702813753029786985027579475059989141119719224961817402605977566829967197490932672021566512826377376988752959467389833419735737545201988916590880487156074463948048461415870071893002222885078350961871888123567241990517365430474025391208925638731208820904957752596249597885523540692851123131898267246576902438472358221

'''

题目的RSA有两个地方不太一样：

  • $n = p^5q^3$
  • d是1380bit的小素数(相对于2048bit的n来说)

可以想见直接利用ed=1在模p^4q^2下copper界完全不够，所以思路应该是根据p^rq^s去找论文。找到论文过后发现其实是一个很标准的论文题，要做的事情是：

  • 根据论文里的copper写出要求small_roots的多项式
  • 对着论文改造格的多项式

但是实际上这题是根据一道原题dasfactor改的，而且原题正好前段时间才有师傅问过我，所以直接拿板子打就结束了。由于d是1380bit，所以m要取40，sage10.2大概会跑50min左右。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
from Crypto.Util.number import *
import gmpy2

def small_roots(f, bound,r,s,N,m):
    '''
    small private d RSA with moduli N=p^r*q^s,that d < 1-(3*r+s)/(r+s)^2 - eps
    the eps is 
    ((15*s+1)*r^4-(2*s^2-10*s)*r^3-(s^3-6*s^2+8*s)*r^2+(2*s^3-12*s^2+6*s)*r+s^4-4*s^3+s^2)
    /(4*m*(r-s)*(r+s)^3) in theory,by this we can choose the proper m which is lower than theory.
    return : one factor of N.you can factor N by this
    for example:
    p,q : 256
    r,s : 5,3
    d : 1300,m = 9
    d : 1350,m = 14
    d : 1360,m = 20
    d : 1370,m = 30
    d > 1370,m = 40 # spend long time to do this(2800s)
    you can choose the larger m to approach the theory solution
    '''
    t1 = int((r*(r+s-2))/((r-1)*(r+s))*m)
    t2 = m
    bounds = [bound ,1]
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    x = f.variables()[0]
    for k in range(t2+1):
        for i in range(t2+1-k):
            d=max([0,ceil((r-1)*(t1-k)/r),ceil((s-1)*(t2-k)/s)])
            base=N ^ d * f ^ k * x ^ i
            G.append(base)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
#     B = flatter(B)
    '''
    another question is can't use flatter because flatter not support 
    the matrix that its row far greater than its cols
    '''
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        for i in h.coefficients():
            if gcd(i,N)!=1 and gcd(i,N)!=N:
                return gcd(h.coefficients()[0],N)
    return 0

c = 6027704939934795526809476320408984749353451163184148193613218899917989403800738729505135647560822568147775955030636790796412038749080589962404088890138
N = 2345049742327685796181532105032554795628696111708534285951012187089560814230641663133312117797131139088986342455315166062482479446527815702735474197358418746066993291802284464812612727625991647573889402281825863578807474887341632160586307943897790827019291411639756252138594856687013363652094621849674259604512491449809337670874218320926522274379234396955495643125680407916326561528774056618181536326260093822819468635513422755218190798616168156924793527386350080400722536575372660262573683231490166520738579903818495107264328324326819989553511070207494208500239603511665056894947107356065440333537271115434438827753
e = 1560967245790387854530279132085915310737094193704812456970549221459036227794862560384548159924112528879771688534015861357630951162558357151823378870345945435342412220708167081427844035498174919749839232806280901968067512188264340755833308035745702731211924571583963089915893479992177245815565483658484702813753029786985027579475059989141119719224961817402605977566829967197490932672021566512826377376988752959467389833419735737545201988916590880487156074463948048461415870071893002222885078350961871888123567241990517365430474025391208925638731208820904957752596249597885523540692851123131898267246576902438472358221
r,s= 5,3
edge = 1380

if(0):
    a= -int(inverse(e,N)) %N
    PR.<x,y> = PolynomialRing(Zmod(N))
    f=a-x
    m=40
    res=small_roots(f, 2^edge,r,s,N,m)
    print(res) #3880841886154333953773650424963616396441043690868788265611642694520916610789745536631157643368280831495777902173955747450998897753151868119085453880516169

q= 62296403476880862016690545256535671712771160075146460730605631039440772133987
print(isPrime(q))
p=int(gmpy2.iroot(N//q^3,5)[0])
assert N==p^5*q^3

p1 = gmpy2.next_prime(p)
q1 = gmpy2.next_prime(q)
d=inverse(65537,(p1-1)*(q1-1))
print(long_to_bytes(ZZ(pow(c,d,p1*q1))))


#SICTF{4d41abf4-c48a-4b82-aefe-0e05d59933a0}



gggcccddd

题目描述：

1
灯灯灯，signin兽进化！gggcccddd兽！ 进化中（50%），进化失败

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
c1 = pow(m,e,n)
c2 = pow(233*m+9527,e,n)
print(f'n = {n}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'e = {e}')
"""
n = 71451784354488078832557440841067139887532820867160946146462765529262021756492415597759437645000198746438846066445835108438656317936511838198860210224738728502558420706947533544863428802654736970469313030584334133519644746498781461927762736769115933249195917207059297145965502955615599481575507738939188415191
c1 = 60237305053182363686066000860755970543119549460585763366760183023969060529797821398451174145816154329258405143693872729068255155086734217883658806494371105889752598709446068159151166250635558774937924668506271624373871952982906459509904548833567117402267826477728367928385137857800256270428537882088110496684
c2 = 20563562448902136824882636468952895180253983449339226954738399163341332272571882209784996486250189912121870946577915881638415484043534161071782387358993712918678787398065688999810734189213904693514519594955522460151769479515323049821940285408228055771349670919587560952548876796252634104926367078177733076253
e = 65537
"""

题目给了两组数据：

可以看出是线性明文攻击，求两个多项式的GCD可以求出公共根m，由于e是65537，度比较大，所以用HGCD效果会好很多，大概30s以内就能跑出来。

不过直接硬求gcd，一两个小时应该也能搞定，还可以接受。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from Crypto.Util.number import *

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)


n = 71451784354488078832557440841067139887532820867160946146462765529262021756492415597759437645000198746438846066445835108438656317936511838198860210224738728502558420706947533544863428802654736970469313030584334133519644746498781461927762736769115933249195917207059297145965502955615599481575507738939188415191
c1 = 60237305053182363686066000860755970543119549460585763366760183023969060529797821398451174145816154329258405143693872729068255155086734217883658806494371105889752598709446068159151166250635558774937924668506271624373871952982906459509904548833567117402267826477728367928385137857800256270428537882088110496684
c2 = 20563562448902136824882636468952895180253983449339226954738399163341332272571882209784996486250189912121870946577915881638415484043534161071782387358993712918678787398065688999810734189213904693514519594955522460151769479515323049821940285408228055771349670919587560952548876796252634104926367078177733076253
e = 65537

PR.<x> = PolynomialRing(Zmod(n))
f1 = x^e - c1
f2 = (233*x+9527)^e - c2

res = GCD(f1,f2)

m = -res.monic().coefficients()[0]
flag = long_to_bytes(int(m))
print(flag)

#SICTF{45115fb2-84d6-4369-88c2-c8c3d72b4c55}



babyRSA

题目描述：

1
树木想要一个baby题目，不说了。。那就来个吧！

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
p = random_prime(1<<512)

with open("ffllaagg.txt", "rb") as f:
    flag = int.from_bytes(f.read().strip(), "big")
assert flag < p

a = randint(2, p-1)
b = randint(2, p-1)
x = randint(2, p-1)

def h():
    global a, b, x
    x = (a*x + b) % p
    return x

PR.<X> = PolynomialRing(GF(p))
f = h() + h()*X + h()*X**2 + h()*X**3 + h()*X**4 + h()*X**5
v_me_50 = [(i, f(i)) for i in range(1, 5)]

print(p)
print(v_me_50)
print(f(flag))


p = 8432316544210923620966806031040552674652729976238765323782536889706914762471638598119051165931563126522925761119650997703305509546949570434637437942542827
v_me_50 = [(1, 5237331460408741346823741966490617418367283531029963248255318507187035341590236835730694472064897540292182231844047116067936691956970631907605500080014355), (2, 5798977431976767515500795413771120575460553181185728489626756434911307088093739452469315524092208822863785429164219547384598943937099787390543171055679780), (3, 5030862375386942201139427367618716490378481408210696947331523552250206476805124204780313138835912303941204343248384742875319182761611109448446270069831113), (4, 4705360705603328842229554954026497175574981026785287316439514185860486128679614980330307863925942038530792583274904352630757089631411920876914529907563209)]
f_flag = 7251453750672416392395590357197330390627853878488142305852099080761477796591562813165554150640801022882531891827653530623183405183605476913024545431842867

题目给了四组已知数据，分别是1、2、3、4代入如下多项式的值：

同时还给了flag代入多项式的值，要求解出flag来。其中，多项式系数满足LCG的递推关系，只是LCG的a、b、初始x都未知，所以也需要求。

由于多项式系数都满足LCG，所以实际上方程涉及的变量只有a、b、x三个，因此四个方程来做groebner或者resultant完全足够。求出a、b、x后就可以直接对代入flag值的多项式求根得到flag。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from Crypto.Util.number import *

p = 8432316544210923620966806031040552674652729976238765323782536889706914762471638598119051165931563126522925761119650997703305509546949570434637437942542827
v_me_50 = [(1, 5237331460408741346823741966490617418367283531029963248255318507187035341590236835730694472064897540292182231844047116067936691956970631907605500080014355), (2, 5798977431976767515500795413771120575460553181185728489626756434911307088093739452469315524092208822863785429164219547384598943937099787390543171055679780), (3, 5030862375386942201139427367618716490378481408210696947331523552250206476805124204780313138835912303941204343248384742875319182761611109448446270069831113), (4, 4705360705603328842229554954026497175574981026785287316439514185860486128679614980330307863925942038530792583274904352630757089631411920876914529907563209)]
f_flag = 7251453750672416392395590357197330390627853878488142305852099080761477796591562813165554150640801022882531891827653530623183405183605476913024545431842867

#part1 groebner to get a,b,x
#h() + h()*X + h()*X**2 + h()*X**3 + h()*X**4 + h()*X**5
PR.<a,b,x> = PolynomialRing(GF(p))

X = 1
f1 = (a*x+b) + (a*(a*x+b)+b)*X + (a*(a*(a*x+b)+b)+b)*X^2 + (a*(a*(a*(a*x+b)+b)+b)+b)*X^3 + (a*(a*(a*(a*(a*x+b)+b)+b)+b)+b)*X^4 + (a*(a*(a*(a*(a*(a*x+b)+b)+b)+b)+b)+b)*X^5 - v_me_50[0][1]

X = 2
f2 = (a*x+b) + (a*(a*x+b)+b)*X + (a*(a*(a*x+b)+b)+b)*X^2 + (a*(a*(a*(a*x+b)+b)+b)+b)*X^3 + (a*(a*(a*(a*(a*x+b)+b)+b)+b)+b)*X^4 + (a*(a*(a*(a*(a*(a*x+b)+b)+b)+b)+b)+b)*X^5 - v_me_50[1][1]

X = 3
f3 = (a*x+b) + (a*(a*x+b)+b)*X + (a*(a*(a*x+b)+b)+b)*X^2 + (a*(a*(a*(a*x+b)+b)+b)+b)*X^3 + (a*(a*(a*(a*(a*x+b)+b)+b)+b)+b)*X^4 + (a*(a*(a*(a*(a*(a*x+b)+b)+b)+b)+b)+b)*X^5 - v_me_50[2][1]

X = 4
f4 = (a*x+b) + (a*(a*x+b)+b)*X + (a*(a*(a*x+b)+b)+b)*X^2 + (a*(a*(a*(a*x+b)+b)+b)+b)*X^3 + (a*(a*(a*(a*(a*x+b)+b)+b)+b)+b)*X^4 + (a*(a*(a*(a*(a*(a*x+b)+b)+b)+b)+b)+b)*X^5 - v_me_50[3][1]

res = Ideal([f1,f2,f3,f4]).groebner_basis()
a = -res[0].coefficients()[1]
b = -res[1].coefficients()[1]
x = -res[2].coefficients()[1]


#part2 get flag
PR.<m> = PolynomialRing(GF(p))
final = (a*x+b) + (a*(a*x+b)+b)*m + (a*(a*(a*x+b)+b)+b)*m^2 + (a*(a*(a*(a*x+b)+b)+b)+b)*m^3 + (a*(a*(a*(a*(a*x+b)+b)+b)+b)+b)*m^4 + (a*(a*(a*(a*(a*(a*x+b)+b)+b)+b)+b)+b)*m^5 - f_flag
flag = long_to_bytes(int(final.roots()[0][0]))
print(flag)


#SICTF{Th3s_1s_a_high_l3vel_p0lyn0mial}

做这题的时候闹了点乌龙，以为每调一次f(i)，h()都会继续递推6次，所以groebner了半天都是[1]。但其实f并不是一个函数，而只是个多项式名称，所以对于1、2、3、4各自的f，系数都完全一样。