W'Blog

Wbuildings的自勉小屋

0%

SICTF Round#3

发表于 分类于 Valine：
本文字数： 41k 阅读时长 ≈ 37 分钟

新年都未有芳华，二月初惊见草芽。

[签到]Vigenere

出题人：树木

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.

常见的维吉尼亚在线爆破密钥

https://www.guballa.de/vigenere-solver

1
2
3
4
5
6
7
8
9
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.

# SICTF{4695cab9-fd68-4684-be81-c6c1acb6cafa}

签到，确信！

出题人：3tefanie

附件：

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
'''

随机多项式中找到n的因子

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
from Crypto.Util.number import *
k = 7
n=8361361624563191168612863710516449028280757632934603412143152925186847721821552879338608951120157631182699762833743097837368740526055736516080136520584848113137087581886426335191207688807063024096128001406698217998816782335655663803544853496060418931569545571397849643826584234431049002394772877263603049736723071392989824939202362631409164434715938662038795641314189628730614978217987868150651491343161526447894569241770090377633602058561239329450046036247193745885174295365633411482121644408648089046016960479100220850953009927778950304754339013541019536413880264074456433907671670049288317945540495496615531150916647050158936010095037412334662561046016163777575736952349827380039938526168715655649566952708788485104126900723003264019513888897942175890007711026288941687256962012799264387545892832762304320287592575602683673845399984039272350929803217492617502601005613778976109701842829008365226259492848134417818535629827769342262020775115695472218876430557026471282526042545195944063078523279341459199475911203966762751381334277716236740637021416311325243028569997303341317394525345879188523948991698489667794912052436245063998637376874151553809424581376068719814532246179297851206862505952437301253313660876231136285877214949094995458997630235764635059528016149006613720287102941868517244509854875672887445099733909912598895743707420454623997740143407206090319567531144126090072331

e=65537
c=990174418341944658163682355081485155265287928299806085314916265580657672513493698560580484907432207730887132062242640756706695937403268682912083148568866147011247510439837340945334451110125182595397920602074775022416454918954623612449584637584716343806255917090525904201284852578834232447821716829253065610989317909188784426328951520866152936279891872183954439348449359491526360671152193735260099077198986264364568046834399064514350538329990985131052947670063605611113730246128926850242471820709957158609175376867993700411738314237400038584470826914946434498322430741797570259936266226325667814521838420733061335969071245580657187544161772619889518845348639672820212709030227999963744593715194928502606910452777687735614033404646237092067644786266390652682476817862879933305687452549301456541574678459748029511685529779653056108795644495442515066731075232130730326258404497646551885443146629498236191794065050199535063169471112533284663197357635908054343683637354352034115772227442563180462771041527246803861110504563589660801224223152060573760388045791699221007556911597792387829416892037414283131499832672222157450742460666013331962249415807439258417736128976044272555922344342725850924271905056434303543500959556998454661274520986141613977331669376614647269667276594163516040422089616099849315644424644920145900066426839607058422686565517159251903275091124418838917480242517812783383

R = Zmod(n)["x"]
while True:
    Q = R.quo(R.random_element(k))
    pp1 = gcd(ZZ(list(Q.random_element() ^ n)[1]), n)
    
    if pp1 != 1:
        print(pp1)
        qq = sum([pp1**i for i in range(k)])
        rr = n // (pp1 * qq)
        assert n == pp1 * qq * rr
        break

phi = (pp1 - 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}
  1. R = Zmod(n)["x"]：创建了一个环R，它是整数模n（即Z/nZ）上的多项式环，变量为x。这样我们可以进行多项式运算。
  2. Q = R.quo(R.random_element(k))：创建了一个多项式Q，R.random_element(k)生成一个随机多项式。 即

抽象代数，商环？推理具体看

Crypto趣题-RSA(一)

easyLattice

出题人：DexterJie

附件：

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     
"""

一道格的入门题

格（Lattice）

给定一组线性无关的基向量,那么这些基向量的所有整系数线性组合：

所形成的集合，就称作格（Lattice）

线性组合：

两个数乘向量的和，被称为这两个向量的线性组合

线性无关：

所有向量都给张成的空间增添了新的维度

张成的空间：

所有可以表示为给定向量线性组合的向量的集合

=>

我们尝试构造一个SVP问题，构造一个矩阵M（由两个线性无关的基构成），我们希望(f,g)

是M张成的格上的最短向量，这样我们或许可以求出未知的(f,g)

增加一个式子 ，即构造一个矩阵

可以发现

也就是说，(f,g)可以用两组向量基 M的某种整系数线性组合(f,−u)来表示，因此(f,g)确实在这个格上

  • SVP(最短向量问题，Shortest Vector Problem)：给定lattice和基向量，找到lattice中的一个长度最短的非零向量。低维可以利用LLL算法求解

最短向量, p为512位，可能 f 稍大了，没有直接求出flag来

因为 搞出来的f和g与原f和g存在倍数关系

f 376位，g 128 位，差距 248位

image-20240226033237586

1
2
3
4
5
6
7
8
9
10
11
12
13
import libnum

h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947     
T = 2^248

Ge = Matrix(ZZ,[[T*h,1],[T*p,0]])
print(Ge.LLL())
g,f = Ge.LLL()[0]
g,f = abs(g),abs(f)

print(libnum.n2s(int(f)))
# SICTF{e3fea01c-18f3-4638-9544-9201393940a9}

还需要注意一点的是 最短向量的上界： (应该是)

于是换了连分数来求解

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
q = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947     

# Construct lattice.

N = 20000
fra = (h/q).n(N).exact_rational().continued_fraction()

for i in range(len(fra)):
    k = fra.numerator(i)
    f = fra.denominator(i)
    m = libnum.n2s(int(abs(f)))
    if b'SICTF' in m:
        print(f)
        print(m)
# SICTF{e3fea01c-18f3-4638-9544-9201393940a9}

Wiener’s v.s Lattices —— Ax≡y(mod P)的方程解法笔记 | Tover’ Blog

NTRU格密码 - 上辰 - 博客园 (cnblogs.com)

格密码（Lattice）与NTRUEncrypt介绍_getrandomnbitinteger-CSDN博客

初识格 | DexterJie’Blog

SuperbRSA

出题人：Kicky_Mu

附件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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不互素

这里公约数为5，较小，直接开根

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
import libnum

n= 19006830358118902392432453595802675566730850352890246995920642811967821259388009049803513102750594524106471709641202019832682438027312468849299985832675191795417160553379580813410722359089872519372049229233732405993062464286888889084640878784209014165871696882564834896322508054231777967011195636564463806270998326936161449009988434249178477100127347406759932149010712091376183710135615375272671888541233275415737155953323133439644529709898791881795186775830217884663044495979067807418758455237701315019683802437323177125493076113419739827430282311018083976114158159925450746712064639569301925672742186294237113199023
c1= 276245243658976720066605903875366763552720328374098965164676247771817997950424168480909517684516498439306387133611184795758628248588201187138612090081389226321683486308199743311842513053259894661221013008371261704678716150646764446208833447643781574516045641493770778735363586857160147826684394417412837449465273160781074676966630398315417741542529612480836572205781076576325382832502694868883931680720558621770570349864399879523171995953720198118660355479626037129047327185224203109006251809257919143284157354935005710902589809259500117996982503679601132486140677013625335552533104471327456798955341220640782369529
c2= 11734019659226247713821792108026989060106712358397514827024912309860741729438494689480531875833287268454669859568719053896346471360750027952226633173559594064466850413737504267807599435679616522026241111887294138123201104718849744300769676961585732810579953221056338076885840743126397063074940281522137794340822594577352361616598702143477379145284687427705913831885493512616944504612474278405909277188118896882441812469679494459216431405139478548192152811441169176134750079073317011232934250365454908280676079801770043968006983848495835089055956722848080915898151352242215210071011331098761828031786300276771001839021
e1=55
e2=200
s,s1,s2 = gmpy2.gcdext(e1,e2)
print(s)
m = pow(c1,s1,n)*pow(c2,s2,n)%n
print(libnum.n2s(int(libnum.nroot(m,s))))
# SICTF{S0_Great_RSA_Have_Y0u_Learned?}

如果 e1,e2存在极大的公约数，且有e3

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2
import libnum

e1e2,s1,s2 = gmpy2.gcdext(e1,e2)
c12 = pow(c1,s1,n)*pow(c2,s2,n)%n

e2e3,s2,s3 = gmpy2.gcdext(e1,e2)
c23 = pow(c2,s2,n)*pow(c3,s3,n)%n

s12,s23,gcd = gmpy2.gcdext(e1e2,e2e3)
m = pow(c12,s12,n)*pow(c23,s23,n1)%n
print(libnum.n2s(m))

gggcccddd

出题人：3tefanie

附件：

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
"""

一眼 Franklin-Reiter（太慢了）

所以我用half gcd

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

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

P = Zmod(n)["x"]
x = P.gen()
f = x**e - c1
g = (233*x+9527) ** e - c2
h = fast_polynomial_gcd(f, g)
m = -h[0] // h[1]
print(long_to_bytes(int(m)))
# SICTF{45115fb2-84d6-4369-88c2-c8c3d72b4c55}

或者这个脚本：

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
from Crypto.Util.number import *
import sys

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)

sys.setrecursionlimit(500000)

n = 71451784354488078832557440841067139887532820867160946146462765529262021756492415597759437645000198746438846066445835108438656317936511838198860210224738728502558420706947533544863428802654736970469313030584334133519644746498781461927762736769115933249195917207059297145965502955615599481575507738939188415191
c1 = 60237305053182363686066000860755970543119549460585763366760183023969060529797821398451174145816154329258405143693872729068255155086734217883658806494371105889752598709446068159151166250635558774937924668506271624373871952982906459509904548833567117402267826477728367928385137857800256270428537882088110496684
c2 = 20563562448902136824882636468952895180253983449339226954738399163341332272571882209784996486250189912121870946577915881638415484043534161071782387358993712918678787398065688999810734189213904693514519594955522460151769479515323049821940285408228055771349670919587560952548876796252634104926367078177733076253
e = 65537
R.<x> = PolynomialRing(Zmod(n))
f = x^e - c1
g = (233*x+9527)^e - c2

res = GCD(f,g)

m = -res.monic().coefficients()[0]
print(m)
flag = long_to_bytes(int(m))
print(flag)
# SICTF{45115fb2-84d6-4369-88c2-c8c3d72b4c55}

*铜匠

出题人：3tefanie

附件：

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转5进制给出前112位，经过测试，可以补零得到高位

猜测进位差，舍弃三到四位，爆破八到九位就可解，实际没出来，

最后猜测可能要五进制的形式解这题，不会写脚本，g

以五进制的形式爆破：

求解未知bit的理论上界

$p_{未知位数}<n^{\frac{\beta^2}{d}-\epsilon}$

$epsilon = \epsilon $

d 是造的多项式的度，这个多项式x是变量，度为1

n就是大数 n

$beta=\beta$

beta是指copper理想的模数大于实际模数的多少次幂

如此题，理想模数是p，实际模数是 n， $p>n^{0.49}$ 

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

t = 0.5*getPrime(1024)**(0.49**2-0.01)

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

cc = Decimal_conversion(int(t))
print(len(cc))
# 102

可以看到未知位数的理论上界是102，而我们未知位数有109位，理论上要爆破7位

不过copper一般界会松散一点，从低位开始试试

这里爆破两位

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)

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:
        p = ph + 5^2*res[0] + i
        print(p)
p = 12170789707638469557363249767228204966074269830454332436369564884472290413677820876733675261757160662428920138919536054003455470370040518528641001253487453
q = n // p
d = inverse(e,(p-1)*(q-1))
m = long_to_bytes(int(pow(c,d,n)))

print(m)	
	
#SICTF{1d213ffc-d5dc-42d0-b206-e9a0c1a3cb69}

最开始以十进制的形式爆破没出可能是因为5进制转成十进制出了问题

5进制转成十进制：$temp =\sum_{i}^{n}x*5^i $

抹3位，也就是从109位开始 ，即 i=109

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 *
import gmpy2
from tqdm import *

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

def five_to_ten(num):
    temp = 0
    i = 109
    for j in reversed(num):
        temp += int(j) * 5**i
        i += 1
    return temp

leak = five_to_ten(leak)
gift = leak >> 256

for i in trange(2^8):
    ph = gift << 8
    phigh = ph + i
    phigh = phigh << 248
    R.<x> = PolynomialRing(Zmod(n))
    f = phigh + x
    res = f.small_roots(X=2^248, beta=0.4, epsilon=0.01)
    if res != []:
        p = phigh + int(res[0])
        q = n // p
        d = gmpy2.invert(e,(p-1)*(q-1))
        m = pow(c,d,n)
        print(f"i = {i}")
        print(long_to_bytes(int(m)))
        break
# SICTF{1d213ffc-d5dc-42d0-b206-e9a0c1a3cb69}

*BabyRSA

出题人：Kicky_Mu

附件：

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
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

给了四个lcg用来求a、b、x

image-20240226033053986

以为给了四个式子来求六个未知数，因为是lcg，实际每个$x_i$ 都可以用a、b、x代替，也即 四个式子解三个未知数（都在 模 p下），所以用sage的groebner_basis 来求
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
from Crypto.Util.number import *

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

PR.<a,b,x> = PolynomialRing(GF(p))

L = []
for i in range(6):
    x = a*x+b
    L.append(x)

f1 = L[0]+L[1]+L[2]+L[3]+L[4]+L[5]-c[0][1]
f2 = L[0]+L[1]*2+L[2]*2^2+L[3]*2^3+L[4]*2^4+L[5]*2^5-c[1][1]
f3 = L[0]+L[1]*3+L[2]*3^2+L[3]*3^3+L[4]*3^4+L[5]*3^5-c[2][1]
f4 = L[0]+L[1]*4+L[2]*4^2+L[3]*4^3+L[4]*4^4+L[5]*4^5-c[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]

L = []
for i in range(6):
    x = a*x+b
    L.append(x)
    
PR.<x> = PolynomialRing(GF(p))
f = L[0]+L[1]*x+L[2]*x^2+L[3]*x^3+L[4]*x^4+L[5]*x^5-enc_flag
roots = f.roots()
print(long_to_bytes(int(roots[0][0])))
# SICTF{Th3s_1s_a_high_l3vel_p0lyn0mial}

*[进阶]easy_or_baby_RSA

出题人：3tefanie

hint：论文地址：https://wwt.lanzout.com/i7lU01omy8uf

附件：

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

'''

paper题

特点是 $n=p^rq^s$ ，可以根据 注释里的调参

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
from Crypto.Util.number import *

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
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

这次求出的不是素数，拿去分解一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
from Crypto.Util.number import *
c = 6027704939934795526809476320408984749353451163184148193613218899917989403800738729505135647560822568147775955030636790796412038749080589962404088890138
n = 2345049742327685796181532105032554795628696111708534285951012187089560814230641663133312117797131139088986342455315166062482479446527815702735474197358418746066993291802284464812612727625991647573889402281825863578807474887341632160586307943897790827019291411639756252138594856687013363652094621849674259604512491449809337670874218320926522274379234396955495643125680407916326561528774056618181536326260093822819468635513422755218190798616168156924793527386350080400722536575372660262573683231490166520738579903818495107264328324326819989553511070207494208500239603511665056894947107356065440333537271115434438827753
e = 1560967245790387854530279132085915310737094193704812456970549221459036227794862560384548159924112528879771688534015861357630951162558357151823378870345945435342412220708167081427844035498174919749839232806280901968067512188264340755833308035745702731211924571583963089915893479992177245815565483658484702813753029786985027579475059989141119719224961817402605977566829967197490932672021566512826377376988752959467389833419735737545201988916590880487156074463948048461415870071893002222885078350961871888123567241990517365430474025391208925638731208820904957752596249597885523540692851123131898267246576902438472358221

q=62296403476880862016690545256535671712771160075146460730605631039440772133987

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(pow(c,d,p1*q1)))
# SICTF{4d41abf4-c48a-4b82-aefe-0e05d59933a0}

*[进阶]2024_New_Setback

出题人：Kicky_Mu

附件：

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) 
"""

这里先求曲线的参数c，d，p

同 BabyRSA ，四个点得到四个多项式方程，再次 groebner_basis

会出现问题，发现 p 有两个小因子，处理掉

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 *

P = (398011447251267732058427934569710020713094, 548950454294712661054528329798266699762662)
Q = (139255151342889674616838168412769112246165, 649791718379009629228240558980851356197207)
C1 = (730393937659426993430595540476247076383331, 461597565155009635099537158476419433012710)
C2 = (500532897653416664117493978883484252869079, 620853965501593867437705135137758828401933) 

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
p = p//3//7
PR.<cc> = PolynomialRing(Zmod(p))
f = cc^2 - c2
c = f.roots()[0][0]


朴实无华而又细致无比的出题人的wp：2024 SICTF Round#3出题 crypto misc osint - Kicky_Mu - 博客园

看着复杂实则条理清晰的推理过程

一切准备工作(结论)都已做好的 La佬 ，直接拿来用即可 :曲线

解题思路：

  • 将Edcurve通过换元映射，变换为常见的椭圆曲线的形式 (Edwards ——> Montgomery ——>Weierstrass )

  • 求Dlp discrete_log ，（在椭圆曲线中，Q = nP 存在两种意思，一种是标量积，一种是对数）

Edwards Curves(爱德华曲线)

一般方程：$x^2+y^2=c^2(1+dx^2y^2)$

变换：$(\frac{x}{c})^2+(\frac{y}{c})^2=1+(dc^4(\frac{x}{c})^2(\frac{y}{c})^2)=>X^2+Y^2=1+DX^2Y^2$

其中：$X=\frac{x}{c},Y=\frac{y}{c},D = dc^4$

加法：$(x_1,y_1)+(x_2,y_2)=(\frac{x_1y_2+y_1x_2}{c(1+dx_1x_2y_1y_2)},\frac{y_1y_2-x_1x_2}{c(1-dx_1x_2y_1y_2)})$

映射：$x^2+y^2=1+dx^2y^2\longmapsto Bv^2=u^3+Au^2+u$ (Edwards Curve ——> Montgomery Curve)

其中：

$u=\frac{1+y}{1-y},v=\frac{2(1+y)}{x(1-y)}=\frac{2u}{x}$

$A=\frac{4}{1-d}-2,B=\frac{1}{1-d}$

Montgomery Curves(蒙哥马利曲线)

映射：$By^2=x^3+Ax^2+x \longmapsto v^2=u^3+au+b$ （Montgomery ——-> Weierstrass)

其中：

$(x,y) \longmapsto (u,v)=(\frac{x}{B}+\frac{A}{3B},\frac{y}{B})$

$a=\frac{3-A^2}{3B^2},b=\frac{2A^3-9A}{27B^3}$

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
from Crypto.Util.number import *

P = (398011447251267732058427934569710020713094, 548950454294712661054528329798266699762662)
Q = (139255151342889674616838168412769112246165, 649791718379009629228240558980851356197207)
C1 = (730393937659426993430595540476247076383331, 461597565155009635099537158476419433012710)
C2 = (500532897653416664117493978883484252869079, 620853965501593867437705135137758828401933) 

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
p = p//3//7
PR.<cc> = PolynomialRing(Zmod(p))
f = cc^2 - c2
c = f.roots()[0][0]
a = 1

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]))


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

print(long_to_bytes(m1)+long_to_bytes(m2))
# #SICTF{nOt_50_3a5Y_Edw4rDs_3LlipT!c_CURv3}

常见形式的椭圆曲线(Weierstrass)求法：eG = e*G(gx,gy) (gx即为flag)

给出eG、e

步骤：

  • 用sage中的order()函数求解出该椭圆曲线的阶n
  • 求出e关于阶n的逆元，记为t
  • 求倍点G=t*(eG) ，横坐标即为所求

参考：

2024-SICTF-#Round3-wp-crypto

SICTFround3

-------------　　　　本文结束　　感谢阅读　　　　-------------