太简单的题就不往上发了，只发一些我觉得有些意思的题。

WEEK 1

[SWPU 2020]happy

1
2
3
4
('c=', '0x7a7e031f14f6b6c3292d11a41161d2491ce8bcdc67ef1baa9eL')
('e=', '0x872a335')
#q + q*p^3 =1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586
#qp + q *p^2 = 1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594

一道数学题。

提取两式公因式：

能看出存在公因子q，gcd求一下公因子放进yafu里分解一下，得到几个小因子：

1
2
3
4
5
6
P1 = 2
P1 = 3
P1 = 3
P1 = 3
P29 = 21450188030183929729657414367
P30 = 827089796345539312201480770649

里面应该就有一个为q，其他的因子应该是剩下的部分含有的公因子，先试一试哪一个反向代入能成立（2,3的肯定先排除了），这里我选取的是测试x1式所求p能否被开三次方：

1
2
3
4
q1=21450188030183929729657414367
q2=827089796345539312201480770649
print(gmpy2.iroot((x1//q1-1),3)[1])#False
print(gmpy2.iroot((x1//q2-1),3)[1])#True

得到因子，解出RSA：

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

c=int('0x7a7e031f14f6b6c3292d11a41161d2491ce8bcdc67ef1baa9e',16)
e=int('0x872a335',16)
x1=1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586
x2=1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594
print(gmpy2.gcd(x1,x2))
q1=21450188030183929729657414367
q2=827089796345539312201480770649
if gmpy2.iroot((x1//q2-1),3)[1]==1:
    q=q2
else:
    q=q1
p=gmpy2.iroot((x1//q2-1),3)[0]
n=p*q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[SWPUCTF 2021 新生赛]crypto1

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

flag  = '****************************'
flag = {"asfajgfbiagbwe"}
p = getPrime(2048)
q = getPrime(2048)
m1 = bytes_to_long(bytes(flag.encode()))

e1e2 = 3087
n = p*q
print()

flag1 = pow(m1,e1,n)
flag2 = pow(m1,e2,n)
print('flag1= '+str(flag1))
print('flag2= '+str(flag2))
print('n= '+str(n))

#flag1= 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
#flag2= 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
#n= 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437

这只是一道共模攻击题，但是里面包含了一个一直以来被我忽视的一个问题，导致我一直没解出来。

题目给了两个e的乘积，分解得到因子为3,3,7,7,7，我们可以把e1所有的可能用数组列出来，然后依次运算看看哪个存在flag：

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

c1= 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
c2= 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
n= 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437
e1=[3,7,3*3,3*7,7*7,7*7*3,7*7*7,7*7*7*3,7*7*3*3,3*3*7]
for i in e1:
    e2=3087//i
    s,s1,s2=gmpy2.gcdext(i,e2)
    m = pow(c1,s1,n) * pow(c2,s2,n) % n

但是，我这样将所有的结果转码出来后发现并没有得到flag。之前学习共模攻击时，有个前提条件为e1和e2应该是互素的，但在这里显然并不一定成立。

我们假设如果两个e有公因子s，知道$e_1s_1+e_2s_2=1$不成立了，应该为$e_1s_1+e_2s_2=s$

换算一下得到：

可见，我们用老方法求出的m其实是m的s次方，我们需要再进行开根得到flag：

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

c1= 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
c2= 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
n= 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437
e1=[3,7,3*3,3*7,7*7,7*7*3,7*7*7,7*7*7*3,7*7*3*3,3*3*7]
for i in e1:
    e2=3087//i
    s,s1,s2=gmpy2.gcdext(i,e2)
    ms = pow(c1,s1,n) * pow(c2,s2,n) % n
    m = gmpy2.iroot(ms,s)
    if m[1]:
        print(long_to_bytes(m[0]))

[RoarCTF 2019]RSA

1
2
3
4
5
6
A=(((y%x)**5)%(x%y))**2019+y**316+(y+1)/x
p=next_prime(z*x*y)
q=next_prime(z)
A =  2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
n =  117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
c =  41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128

题目给了一个A：

1
A=(((y%x)**5)%(x%y))**2019+y**316+(y+1)/x

观察可以发现x和y应该不会很大，因为需要有y的316次方，x还为y+1的因子，所以先尝试爆破出x和y：

1
2
3
4
5
6
7
8
9
10
A=2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
for x in range(2,100):
    for y in range(2,100):
        try:
            if A==(((y%x)**5)%(x%y))**2019+y**316+(y+1)//x:
                print('x=',x)#2
                print('y=',y)#83
                break
        except:
            pass

还有个z求不出来，不过x和y已知，先忽略next_prime，进行计算：

所以，计算$\sqrt\frac n {166}$，所得的值应该是要比z要大，理论上讲不会大太多。

我们从n的角度来看，可以将next_prime附加值设为未知数进行计算，我们已知了xy，上面的计算使值逼近其中的一个因子$z+\beta$：

同样的方法，有：

通过比较上式对应系数和简单的分析，实际的因子q值应该比$\sqrt\frac n {166}$的值要稍大一些，这样$\sqrt\frac n {166}$就夹在z和因子q之间，q一定是$\sqrt\frac n {166}$的下一个质数：

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

A=2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
for x in range(2,100):
    for y in range(2,100):
        try:
            if A==(((y%x)**5)%(x%y))**2019+y**316+(y+1)//x:
                print('x=',x)
                print('y=',y)
                break
        except:
            pass

n=117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
c=41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128
nn=n//166
q=gmpy2.iroot(nn,2)[0]
q=sympy.nextprime(q)
if n%q==0:
    p=n//q
e=65537
d=gmpy2.invert(e,(p-1)*(q-1))
m=pow(c,d,n)
print(long_to_bytes(m))

[CISCN 2021初赛]rsa

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
from flag import text,flag
import md5
from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime

assert md5.new(text).hexdigest() == flag[6:-1]

msg1 = text[:xx]
msg2 = text[xx:yy]
msg3 = text[yy:]

msg1 = bytes_to_long(msg1)#solved 
msg2 = bytes_to_long(msg2)
msg3 = bytes_to_long(msg3)#solved

p1 = getPrime(512)
q1 = getPrime(512)
N1 = p1*q1
e1 = 3
print pow(msg1,e1,N1)
print (e1,N1)

p2 = getPrime(512)
q2 = getPrime(512)
N2 = p2*q2
e2 = 17
e3 = 65537
print pow(msg2,e2,N2)
print pow(msg2,e3,N2)
print (e2,N2)
print (e3,N2)

p3 = getPrime(512)
q3 = getPrime(512)
N3 = p3*q3
print pow(msg3,e3,N3)
print (e3,N3)
print p3>>200

'''
19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
(3, 123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009L)

54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
(17, 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977L)
(65537, 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977L)

59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
(65537, 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147L)
7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
'''

加密分三部分，小明文攻击，共模攻击和p高位攻击，分别写脚本：

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

c1=19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
e1=3
n1=123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009
m1=long_to_bytes(gmpy2.iroot(c1,e1)[0])
#b' \nO wild West Wind, thou breath of Autum'

cc1=54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
cc2=91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
n2=111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977
ee1=17
ee2=65537
s,s1,s2=gmpy2.gcdext(ee1,ee2)
m2=long_to_bytes((pow(cc1,s1,n2)*pow(cc2,s2,n2))%n2)
#b"n's being,\nThou, from whose unseen presence the leaves dead\nAre driven, like ghosts from an enchanter fleeing,\nYellow, a"

e3=65537
c3=59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
p3=11437038763581010263116493983733546014403343859218003707512796706928880848035239990740428334091106443982769386517753703890002478698418549777553268906496423
n3=113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
q3=n3//p3
phi=(p3-1)*(q3-1)
d=gmpy2.invert(e3,phi)
m3=long_to_bytes(pow(c3,d,n3))
#nd black, and pale, and hectic red,\nPestilence-stricken multitudes: O thou,\nWho chariotest to their dark wintry bed\n
1
2
3
4
5
6
7
8
#sage
n3=113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
p3_=7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
p3_high=p3_<<200
P.<x>=PolynomialRing(Zmod(n3))
f=x+p3_high
x0=f.small_roots(X=2^200,beta=0.4)[0]
print("p=",p3_high+x0)

flag为md5加密的text文本，直接用hashlib库加密即可：

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

c1=19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
e1=3
n1=123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009
m1=long_to_bytes(gmpy2.iroot(c1,e1)[0])
#b' \nO wild West Wind, thou breath of Autum'

cc1=54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
cc2=91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
n2=111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977
ee1=17
ee2=65537
s,s1,s2=gmpy2.gcdext(ee1,ee2)
m2=long_to_bytes((pow(cc1,s1,n2)*pow(cc2,s2,n2))%n2)
#b"n's being,\nThou, from whose unseen presence the leaves dead\nAre driven, like ghosts from an enchanter fleeing,\nYellow, a"

e3=65537
c3=59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
p3=11437038763581010263116493983733546014403343859218003707512796706928880848035239990740428334091106443982769386517753703890002478698418549777553268906496423
n3=113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
q3=n3//p3
phi=(p3-1)*(q3-1)
d=gmpy2.invert(e3,phi)
m3=long_to_bytes(pow(c3,d,n3))
#nd black, and pale, and hectic red,\nPestilence-stricken multitudes: O thou,\nWho chariotest to their dark wintry bed\n

m=m1+m2+m3
print('NSSCTF{'+hashlib.md5(m).hexdigest()+'}')

[鹤城杯 2021]BabyRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724
hint2 = q % (2 ** 265)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)

学长说1024位的因子进行coppersmith需要至少已知约572位。

看题目就像是coppersmith题，知道了p的高位，q的低位，知道的位数太少，暂时不能直接用coppersmith，需要继续求某个因子的位数，在模$2^{265}$下：

可以求得p的低位：

这样，我们知道了p的高位和低位，中间位不知道，可以用coppersmith求，这里如果直接求解，会报错没结果，这里可以设一个for循环爆破几位出来，减少coppersmith计算的位数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
p_=1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q_=40812438243894343296354573724131194431453023461572200856406939246297219541329623
n=21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
p_h=p_<<724
p_l=n*gmpy2.invert(q_,2**265)%2**265
p1=p_h+p_l
t=2**265
P.<x>=PolynomialRing(Zmod(n))
for i in range(64):
    f=p1+x*t*64+i*t
    f=f.monic()
    x0=f.small_roots(X=2^453,beta=0.4)
    if x0:
        break
print(x0,i)

注意p的构成，既有高位低位，也有中间位，还要算上我们爆破的i位：

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

p_=1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q_=40812438243894343296354573724131194431453023461572200856406939246297219541329623
n=21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
c=19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
p_h=p_<<724
p_l=n*gmpy2.invert(q_,2**265)%2**265
i=19
x0=7914249681483699348105896117503653090559709096541336321100288778319519769467957659191305141838207370902177955576606946702942703171837148
p=p_h+p_l+(i<<265)+(x0<<271)
q=n//p
e = 65537
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[黑盾杯 2020]Factor

1
2
3
4
n = 3454083680130687060405946528826790951695785465926614724373
e = 3
c = 1347530713288996422676156069761604101177635382955634367208
gcd(m, n) = 1

yafu分解n得到三个因数，直接求逆元发现不存在，看wp发现可以根据flag长度较小，只取与e互质的因数，得到新的phi和n，然后求得m。以前没见过这种方法：

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

n = 3454083680130687060405946528826790951695785465926614724373
e = 3
c = 1347530713288996422676156069761604101177635382955634367208

p = [17100682436035561357,17172929050033177661,11761833764528579549]

n,phi=1,1
for i in p:
    if gmpy2.gcd(e,i-1)==1:
        phi*=(i-1)
        n*=i
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[湖湘杯 2021]signin

题目给了一个连分数的tag，那么肯定是跟连分数有关了：

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
#sage
from Crypto.Util.number import *
from secret import flag
import random

m1 = bytes_to_long(flag[:len(flag) // 2])
m2 = bytes_to_long(flag[len(flag) // 2:])

def gen(pbits, qbits):
    p1, q1 = getPrime(pbits), getPrime(qbits)
    n1 = p1**4*q1
    q2 = getPrime(qbits)
    bound = p1 // (8*q1*q2) + 1
    p2 = random.randrange(p1, p1 + bound)
    while not isPrime(p2):
        p2 = random.randrange(p1, p1 + bound)
    n2 = p2**4*q2
    return (n1, n2), (p1, q1), (p2, q2)

e = 0x10001
pbits = int(360)
qbits = int(128)
pk, sk1, sk2 = gen(pbits, qbits)
c1 = pow(m1, e, pk[0])
c2 = pow(m2, e, pk[1])
print(f'pk = {pk}')
print(f'c1, c2 = {c1, c2}')

"""
pk = (1150398070565459492080597718626032792435556703413923483458704675295997646493249759818468321328556510074044954676615760446708253531839417036997811506222349194302791943489195718713797322878586379546657275419261647635859989280700191441312691274285176619391539387875252135478424580680264554294179123254566796890998243909286508189826458854346825493157697201495100628216832191035903848391447704849808577310612723700318670466035077202673373956324725108350230357879374234418393233, 1242678737076048096780023147702514112272319497423818488193557934695583793070332178723043194823444815153743889740338870676093799728875725651036060313223096288606947708155579060628807516053981975820338028456770109640111153719903207363617099371353910243497871090334898522942934052035102902892149792570965804205461900841595290667647854346905445201396273291648968142608158533514391348407631818144116768794595226974831093526512117505486679153727123796834305088741279455621586989)
c1, c2 = (361624030197288323178211941746074961985876772079713896964822566468795093475887773853629454653096485450671233584616088768705417987527877166166213574572987732852155320225332020636386698169212072312758052524652761304795529199864805108000796457423822443871436659548626629448170698048984709740274043050729249408577243328282313593461300703078854044587993248807613713896590402657788194264718603549894361488507629356532718775278399264279359256975688280723740017979438505001819438, 33322989148902718763644384246610630825314206644879155585369541624158380990667828419255828083639294898100922608833810585530801931417726134558845725168047585271855248605561256531342703212030641555260907310067120102069499927711242804407691706542428236208695153618955781372741765233319988193384708525251620506966304554054884590718068210659709406626033891748214407992041364462525367373648910810036622684929049996166651416565651803952838857960054689875755131784246099270581394)
"""

读代码，bound为一个不到100位的数，p都为360位的大数，那么p2这个随机数生成也就比p1稍微大一点点。先寻找可以使用连分数攻击的目标：

p1和p2非常接近，那么$(\frac{p_1}{p_2})^4$接近1，那么n1和n2的比值与q1和q2的比值很接近，$\frac{q_1}{q_2}$大于$\frac{n_1}{n_2}$且小于1，可以进行连分数攻击找到q1和q2。

改改之前用过的维纳攻击脚本就好了：

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

def f2c(p,q):#分数转连分数
 a=[]
 while q:
  a.append(p//q)
  p,q=q,p%q
 return a

def c2f(a):#连分数转分数
  x,y=1,0#x为分子y为分母
  for a in a[::-1]:#逆序累加
    x,y=a*x+y,x
  return (x,y)

def sf(a):#求各项渐进分数
 f=[]
 for i in range(1,len(a)):
  f.append(c2f(a[:i]))
 return f

def wiener_attack(n1,n2):
 a=f2c(n1,n2)
 for (q1,q2) in sf(a):			
        if q1!=0 and q1!=1 and n1%q1==0:	
            return (q1,q2)

c1, c2 = 361624030197288323178211941746074961985876772079713896964822566468795093475887773853629454653096485450671233584616088768705417987527877166166213574572987732852155320225332020636386698169212072312758052524652761304795529199864805108000796457423822443871436659548626629448170698048984709740274043050729249408577243328282313593461300703078854044587993248807613713896590402657788194264718603549894361488507629356532718775278399264279359256975688280723740017979438505001819438, 33322989148902718763644384246610630825314206644879155585369541624158380990667828419255828083639294898100922608833810585530801931417726134558845725168047585271855248605561256531342703212030641555260907310067120102069499927711242804407691706542428236208695153618955781372741765233319988193384708525251620506966304554054884590718068210659709406626033891748214407992041364462525367373648910810036622684929049996166651416565651803952838857960054689875755131784246099270581394
n1,n2=1150398070565459492080597718626032792435556703413923483458704675295997646493249759818468321328556510074044954676615760446708253531839417036997811506222349194302791943489195718713797322878586379546657275419261647635859989280700191441312691274285176619391539387875252135478424580680264554294179123254566796890998243909286508189826458854346825493157697201495100628216832191035903848391447704849808577310612723700318670466035077202673373956324725108350230357879374234418393233, 1242678737076048096780023147702514112272319497423818488193557934695583793070332178723043194823444815153743889740338870676093799728875725651036060313223096288606947708155579060628807516053981975820338028456770109640111153719903207363617099371353910243497871090334898522942934052035102902892149792570965804205461900841595290667647854346905445201396273291648968142608158533514391348407631818144116768794595226974831093526512117505486679153727123796834305088741279455621586989
e=0x10001
q1,q2=wiener_attack(n1,n2)
p1=gmpy2.iroot(n1//q1,4)[0]
p2=gmpy2.iroot(n2//q2,4)[0]
phi1=p1**3*(p1-1)*(q1-1)
phi2=p2**3*(p2-1)*(q2-1)
d1=gmpy2.invert(e,phi1)
d2=gmpy2.invert(e,phi2)
m1=pow(c1,d1,n1)
m2=pow(c2,d2,n2)
print(long_to_bytes(m1)+long_to_bytes(m2))

[长安杯 2021]checkin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from secret import flag
p = getPrime(1024)
q = getPrime(16)
n = p*q
m = bytes_to_long(flag)
for i in range(1,p-q):
    m = m*i%n
e = 1049
print(pow(2,e,n))
print(pow(m,e,n))

#4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
#3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270

这道题由于q过小，可以直接爆破出q，进而爆破出p。

题目给了2的e次方后的结果，可以用2的e次方减去模n值得到kn，然后慢慢爆破pq即可：

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

c=3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270
c2=4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
e = 1049

kn=2**1049-c2
q=gmpy2.next_prime(2**15)
while 1:
    if kn%q==0:
        break
    q=gmpy2.next_prime(q)

k=2
kp=kn//q
while 1:
  if kp%k==0:
     kp=kp//k
     k=2
  if gmpy2.is_prime(kp):
     p=kp
     break
  k+=1

n=p*q

观察对m单独进行的加密，从1阶乘到p-q，单独算的话根本算不出来，需要考虑到威尔逊定理。

对于这题，有：

猜测M长度应该不会太长，既然满足在模n下相等，那么应该也在模p下相等，这样就把两个式子联系起来了：

要做的是化简掉这个阶乘，和威尔逊的公式相除得：

得到：

由于q不是很大，所以相乘的数不是很多，能计算了：

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

c=3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270
c2=4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
e = 1049

kn=2**1049-c2
q=gmpy2.next_prime(2**15)
while 1:
    if kn%q==0:
        break
    q=gmpy2.next_prime(q)

k=2
kp=kn//q
while 1:
  if kp%k==0:
     kp=kp//k
     k=2
  if gmpy2.is_prime(kp):
     p=kp
     break
  k+=1

n=p*q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m0=pow(c,d,n)
mm=1
for i in range(p-q,p):
   mm=mm*i%p
m=(-m0)*mm%p
print(long_to_bytes(m))

WEEK 2

[CISCN 2022 西南]rsa

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

flag = b'XXXXXXXX'
p1 = getPrime(700)
r1 = getPrime(700)
for i in range(10):
    q1 = 5*p1+i
n = p1*q1*r1
p3 = pow(p1,3,n)
q3 = pow(q1,3,n)

print(p3)
print(q3)
'''
p3 = 29914513810588158800677413177910972738704129106546850855032986405861482276089830788972187432277517348644647399654780884571794069905291936470934226328931651386658328163535027343107140438177837479649822914209171476632450951930287641742344330471734177295804718555774395704231261550376220154493373703096062950390869299905383682611063374747752091585836452902373843865043412096365874638466683035848817858586173172058756256354758712684819253211761289032789542371351760915771791997388241121078055468403109260493642435791152671979552597191217179672328555740595434990908530985477314228867209314472001848844089467987561661918366232980944933533
q3 = 66208618374366130551979192465001581263127328176551695213970812805980115496523825511250542987452691413485117902772315362811067501379171731387904074565035353566976164797769439898266222919741874340315356585585077141595328441423323822407738375537476582506440045835592730211502035261968878999959340204806442390319739977816872969200022096331677277225467021553564212725120939434924481787524609852608476848761521446441776154400518315701988027274150425936061679275540502720782853648148897480117033152064922234451671636288396704170234613549011854618414776342798740690128675106027908639984431432591397555541420243824539205614036979987830125678
'''
P = getPrime(1024)
Q = getPrime(1024)
N = P * Q
E = 65537
lcm = gmpy2.lcm(P-1, Q-1)
e1 = gmpy2.invert(p1, lcm)
e2 = gmpy2.invert(r1, lcm)
m = bytes_to_long(flag)
c = pow(m, E, N)

print(lcm)
print(c)
print(N)
'''
lcm = 4292158730589770192682795435047249488185453170529228019750042608688907718268448193363838203887391025871515871000364259326343790645215256385842265899206372365402431198699714374850409466996627163968391249416054093529090485677808301343590811445080871279796162536469847469761747058736980603093722710824453312207182881241846080117790728778291633761198069016865260030288832065807438020772711645648333908622890343009942617559434851450007195025869850769670769715654662127278293639938359741401336592219730356884542179574372134014927006215640945952229142436595334916765255426954857520777553915330597952622785359222832224632624
c = 4288727484183191191687364666620023549392656794153112764357730676861570386983002380982803054964588111708662498647767438881892355599604826306427809017097724346976778230464708540600157055782723189971534549543664668430013171469625043063261219462210251726207552819381767396148632877168530609902046293626355744288863460554297860696918890189350721960355460410677203131993419723440382095665713164422367291153108363066159712951217816814873413423853338021627653555202253351957999686659021298525147460016557904084617528199284448056532965033560516083489693334373695545423561715471204868795248569806148395196572046378679014697206
N  = 17168634922359080770731181740188997952741812682116912079000170434755630873073792773455352815549564103486063484001457037305375162580861025543369063596825489461609724794798857499401637867986508655873564997664216374116361942711233205374363245780323485119184650145879389879046988234947922412374890843297813248828996855478005656041814919367820336728271583686844991928889831691815821365423570311291064846736832327637944358854661523107817781673029406341843040857813841671405147146887291204140157388049394514390098066284975682117038362207142272098796924412602725857521665773622056312191400612944442008222587867782281556388669
'''

对flag的加密在后半部分，题目给出了p-1和q-1的最小公倍数，由于pq都为质数，一定是奇数，p-1和q-1肯定为偶数，所以它们的lcm就肯定不是相乘的phi，不过可以爆破一下最大公因子得到phi，反正位数差不多应该和phi很接近，爆破出来之后知道n和phi直接分解得到pq，flag就求出来了：

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

lcm = 4292158730589770192682795435047249488185453170529228019750042608688907718268448193363838203887391025871515871000364259326343790645215256385842265899206372365402431198699714374850409466996627163968391249416054093529090485677808301343590811445080871279796162536469847469761747058736980603093722710824453312207182881241846080117790728778291633761198069016865260030288832065807438020772711645648333908622890343009942617559434851450007195025869850769670769715654662127278293639938359741401336592219730356884542179574372134014927006215640945952229142436595334916765255426954857520777553915330597952622785359222832224632624
c = 4288727484183191191687364666620023549392656794153112764357730676861570386983002380982803054964588111708662498647767438881892355599604826306427809017097724346976778230464708540600157055782723189971534549543664668430013171469625043063261219462210251726207552819381767396148632877168530609902046293626355744288863460554297860696918890189350721960355460410677203131993419723440382095665713164422367291153108363066159712951217816814873413423853338021627653555202253351957999686659021298525147460016557904084617528199284448056532965033560516083489693334373695545423561715471204868795248569806148395196572046378679014697206
N  = 17168634922359080770731181740188997952741812682116912079000170434755630873073792773455352815549564103486063484001457037305375162580861025543369063596825489461609724794798857499401637867986508655873564997664216374116361942711233205374363245780323485119184650145879389879046988234947922412374890843297813248828996855478005656041814919367820336728271583686844991928889831691815821365423570311291064846736832327637944358854661523107817781673029406341843040857813841671405147146887291204140157388049394514390098066284975682117038362207142272098796924412602725857521665773622056312191400612944442008222587867782281556388669
E = 65537

def solve_p_q(n,phi):
  x=n-phi+1  #x=p+q=n-p*q+(p+q)-1+1
  y=x*x-4*n  #y=(p-q)^2=(p+q)^2-4n
  z=gmpy2.iroot(y,2)[0]  #z=q-p
  q=(x+z)//2
  p=(x-z)//2
  return p,q

for k in range(1,10000):
    p,q=solve_p_q(N,k*lcm)
    if p*q==N:
       break
phi=k*lcm
d=gmpy2.invert(E,phi)
print(long_to_bytes(pow(c,d,N)))

那么问题来了，这题前面这么多复杂操作是为了什么呢？

[HGAME 2022 week1]Easy RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from math import gcd
from random import randint
from gmpy2 import next_prime
from Crypto.Util.number import getPrime
from secret import flag

def encrypt(c):
    p = getPrime(8)
    q = getPrime(8)
    e = randint(0, p * q)
    while gcd(e, (p - 1) * (q - 1)) != 1:
        e = int(next_prime(e))
    return e, p, q, pow(ord(c), e, p * q)

if __name__ == '__main__':
    print(list(map(encrypt, flag)))
    # [(12433, 149, 197, 104), (8147, 131, 167, 6633), (10687, 211, 197, 35594), (19681, 131, 211, 15710), (33577, 251, 211, 38798), (30241, 157, 251, 35973), (293, 211, 157, 31548), (26459, 179, 149, 4778), (27479, 149, 223, 32728), (9029, 223, 137, 20696), (4649, 149, 151, 13418), (11783, 223, 251, 14239), (13537, 179, 137, 11702), (3835, 167, 139, 20051), (30983, 149, 227, 23928), (17581, 157, 131, 5855), (35381, 223, 179, 37774), (2357, 151, 223, 1849), (22649, 211, 229, 7348), (1151, 179, 223, 17982), (8431, 251, 163, 30226), (38501, 193, 211, 30559), (14549, 211, 151, 21143), (24781, 239, 241, 45604), (8051, 179, 131, 7994), (863, 181, 131, 11493), (1117, 239, 157, 12579), (7561, 149, 199, 8960), (19813, 239, 229, 53463), (4943, 131, 157, 14606), (29077, 191, 181, 33446), (18583, 211, 163, 31800), (30643, 173, 191, 27293), (11617, 223, 251, 13448), (19051, 191, 151, 21676), (18367, 179, 157, 14139), (18861, 149, 191, 5139), (9581, 211, 193, 25595)]

这题的map函数相当于对flag进行逐个字符加密了，写个循环挨个解即可，p和q都给了：

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

list=[(12433, 149, 197, 104), (8147, 131, 167, 6633), (10687, 211, 197, 35594), (19681, 131, 211, 15710), (33577, 251, 211, 38798), (30241, 157, 251, 35973), (293, 211, 157, 31548), (26459, 179, 149, 4778), (27479, 149, 223, 32728), (9029, 223, 137, 20696), (4649, 149, 151, 13418), (11783, 223, 251, 14239), (13537, 179, 137, 11702), (3835, 167, 139, 20051), (30983, 149, 227, 23928), (17581, 157, 131, 5855), (35381, 223, 179, 37774), (2357, 151, 223, 1849), (22649, 211, 229, 7348), (1151, 179, 223, 17982), (8431, 251, 163, 30226), (38501, 193, 211, 30559), (14549, 211, 151, 21143), (24781, 239, 241, 45604), (8051, 179, 131, 7994), (863, 181, 131, 11493), (1117, 239, 157, 12579), (7561, 149, 199, 8960), (19813, 239, 229, 53463), (4943, 131, 157, 14606), (29077, 191, 181, 33446), (18583, 211, 163, 31800), (30643, 173, 191, 27293), (11617, 223, 251, 13448), (19051, 191, 151, 21676), (18367, 179, 157, 14139), (18861, 149, 191, 5139), (9581, 211, 193, 25595)]
for i in list:
    e,p,q,c=i[0],i[1],i[2],i[3]
    n=p*q
    phi=(p-1)*(q-1)
    d=gmpy2.invert(e,phi)
    m=pow(c,d,n)
    print(long_to_bytes(m).decode('utf-8'),end='')

[羊城杯 2020]RRRRRRRSA

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

flag = 'GWHT{*********}'

flag1 = flag[:14]
flag2 = flag[14:]
assert(len(flag) == 27)

P1 = getPrime(1038)
P2 = sympy.nextprime(P1)
assert(P2 - P1 < 1000)

Q1 = getPrime(512)
Q2 = sympy.nextprime(Q1)

N1 = P1 * P1 * Q1
N2 = P2 * P2 * Q2

E1 = getPrime(1024)
E2 = sympy.nextprime(E1)

m1 = bytes_to_long(flag1)
m2 = bytes_to_long(flag2)

c1 = pow(m1, E1, N1)
c2 = pow(m2, E2, N2)


output = open('secret', 'w')
output.write('N1=' + str(N1) + '\n')
output.write('c1=' + str(c1) + '\n')
output.write('E1=' + str(E1) + '\n')
output.write('N2=' + str(N2) + '\n')
output.write('c2=' + str(c2) + '\n')
output.write('E2=' + str(E2) + '\n')
output.close()

p1p2和q1q2分别都是相邻素数，有：

和上周的signin差不多，依旧是维纳攻击：

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

N1=28539239760609998188190348006307254423529984523926011298354682217538318221201323233400895681944936240127760319591714405028970789289069319799896668405374649890651532747231344681669678805558659075027847592497103008180667401328194026698749233856463858487096300279373254961880228864461848969277992345170787143090948199697266462389362914238819698112687026213976658417210663710975098053456243238943838516217798558036642447022751111845270483110159293737669560262193958772015914816987850140197853369767380678566336063010710812528919482513791382363881826680659095433918156094107350594201368395060384315773118343026193511099009931177740948978534045707679969732723167077325752299598557383348276880809860413060977442176372544771414690543709674125255716088409107695219200275948083389811120343
c1=1432582014696304280729383293185554513436929310033823269133977593539672022744978340029313742941392672688363895524640351487464959860278576282854691764963077939567531721178912737755379413034164798305484717033762726637503348022397339246940965129765378824268519081645805470821347112369377592502109678876165836108257610182421452838639591697308432137885174692492190957254254995673010537260331832973067691597718100899475899017281060822990010249568584370589711942182283002241043038119931455622397903939297537776804134742442672001638774739818585840571993745726530468147630711418520486306194651956014117679528472239294239116641656014852458465706006398065574504399016286485027421474307531748266141136418468990741046806688381193860509615850629805172129297224123462801586090084637746562423808
E1=165789626975534012040420057284463500775834911397214992496515507176272849770841998477139944440126985014248815418211585858658342524799286016374109756516450870298232454995876047057825952563581619963387275065218691863272435560584657400761485940130783607258311246708485662913432455714363728035174035069036312370233
N2=28539239760609998188190348006307254423529984523926011298354682217538318221201323233400895681944936240127760319591714405028970789289069319799896668405377378062335966544017315329665365256524558696688888741558627244653037221467229159144343040629127843297021870442297090214085287305843208151069804261723045390513830069085816369993597001968164660390663983571269250460727348123970070188870297493687465127551913118724304293942732950040939150438510454614095673775735977217966562306548665616925803946575019193754095625773160561193234183507671760318885800972555685452762447998320093072265818485061557955267533908006243431570323359331106169234651310488306412479972526063665874847216797986275140105142694301359006633212114432527436809944525332728559649659936613255629968696993687582732203577
c2=15573518512630583133605706431375892476846434992703760807266881477212729790675502562405142453118932977842339803883111403869334521098950030048699583130857582338419182841819307757252097704148569218757559761264396801310961344678392000382263595912787825617009851110457692404940207973548999796553024456145274114257889573707649959860997335143214788897776951837248853483762434899857463503651914305981628033038172123120703537802061315610043298426738218704990852775023413248589434394708618489802771255075164976384643287270994751622452142844176084933641827641239534332334446368745588970480750957569438747829980771324981588625047320914720986351721280038816715323656526802000900688313558979941992015923305782197562859553039256619824373010017972420560224632828808074734952385591551175446599133
E2=165789626975534012040420057284463500775834911397214992496515507176272849770841998477139944440126985014248815418211585858658342524799286016374109756516450870298232454995876047057825952563581619963387275065218691863272435560584657400761485940130783607258311246708485662913432455714363728035174035069036312370859

def f2c(p,q):#分数转连分数
 a=[]
 while q:
  a.append(p//q)
  p,q=q,p%q
 return a

def c2f(a):#连分数转分数
  x,y=1,0#x为分子y为分母
  for a in a[::-1]:#逆序累加
    x,y=a*x+y,x
  return (x,y)

def sf(a):#求各项渐进分数
 f=[]
 for i in range(1,len(a)):
  f.append(c2f(a[:i]))
 return f

def wiener_attack(n1,n2):
 a=f2c(n1,n2)
 for (q1,q2) in sf(a):		
    if q1!=0 and q1!=1 and n1%q1==0:	
        return (q1,q2)

Q1,Q2=wiener_attack(N1,N2)
P1=gmpy2.iroot(N1//Q1,2)[0]
P2=gmpy2.iroot(N2//Q2,2)[0]
phi1=P1*(P1-1)*(Q1-1)
phi2=P2*(P2-1)*(Q2-1)
d1=gmpy2.invert(E1,phi1)
d2=gmpy2.invert(E2,phi2)
m1=pow(c1,d1,N1)
m2=pow(c2,d2,N2)
print(long_to_bytes(m1)+long_to_bytes(m2))

[SWPUCTF 2021 新生赛]crypto3

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

flag  = '******************'

p = getPrime(512)
q = getPrime(512)
m1 = bytes_to_long(bytes(flag.encode()))

n = p*q

flag1 = pow(m1,p,n)
flag2 = pow(m1,q,n)
print('flag1= '+str(flag1))
print('flag2= '+str(flag2))
print('n= '+str(n))

#flag1= 17893542812755845772427795161304049467610774531005620109503081344099161906017295486868699578946474114607624347167976713200068059018517606363517478396368430072890681401898145302336139240273132723451063402106360810413024642916851746118524166947301681245568333254648265529408446609050354235727237078987509705857
#flag2= 95580409405085606847879727622943874726633827220524165744517624606566789614499137069562997931972825651309707390763700301965277040876322904891716953565845966918293178547100704981251056401939781365264616997055296773593435626490578886752446381493929807909671245959154990639046333135728431707979143972145708806954
#n= 140457323583824160338989317689698102738341061967768153879646505422358544720607476140977064053629005764551339082120337223672330979298373653766782620973454095507484118565884885623328751648660379894592063436924903894986994746394508539721459355200184089470977772075720319482839923856979166319700474349042326898971

题目加密所用的指数为p和q，这让我想到了费马小定理：

此外，根据同余的性质可以对$c_1$做如下处理：

这样就有了$m\equiv c_1(\bmod p)$，在模p下：

可以构造多项式求解小值根了：

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

c1= 17893542812755845772427795161304049467610774531005620109503081344099161906017295486868699578946474114607624347167976713200068059018517606363517478396368430072890681401898145302336139240273132723451063402106360810413024642916851746118524166947301681245568333254648265529408446609050354235727237078987509705857
c2= 95580409405085606847879727622943874726633827220524165744517624606566789614499137069562997931972825651309707390763700301965277040876322904891716953565845966918293178547100704981251056401939781365264616997055296773593435626490578886752446381493929807909671245959154990639046333135728431707979143972145708806954
n= 140457323583824160338989317689698102738341061967768153879646505422358544720607476140977064053629005764551339082120337223672330979298373653766782620973454095507484118565884885623328751648660379894592063436924903894986994746394508539721459355200184089470977772075720319482839923856979166319700474349042326898971

p.<x>=PolynomialRing(Zmod(n))
f=x^2-(c1+c2)*x+c1*c2
x0=f.small_roots()[0]
print(long_to_bytes(int(x0)))

我们由于未知flag长度，猜测flag很小，不需要设置上界就能解出flag。

[TSGCTF 2021]Beginner’s Crypto 2021

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
from secret import e
from Crypto.Util.number import getStrongPrime, isPrime

p = getStrongPrime(1024)
q = getStrongPrime(1024)
N = p * q
phi = (p - 1) * (q - 1)

with open('flag.txt', 'rb') as f:
    flag = int.from_bytes(f.read(), 'big')

assert(isPrime(e))
assert(isPrime(e + 2))
assert(isPrime(e + 4))

e1 = pow(e, 0x10001, phi)
e2 = pow(e + 2, 0x10001, phi)
e3 = pow(e + 4, 0x10001, phi)

c1 = pow(flag, e1, N)
c2 = pow(flag, e2, N)
c3 = pow(flag, e3, N)

print(f'p = {p}')
print(f'q = {q}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')

这题用了共模攻击，但是未知e，首先想到的就是爆破一下e，观察一下代码，可以判断一下e，e+2，e+4来找到e，事实上，爆破了一会发现满足要求的e只有3：

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 libnum import *
import gmpy2
import hashlib

p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837
n=p*q
e=2
phi=(p-1)*(q-1)
while 1:
    print(e)
    if isPrime(e) and isPrime(e+2) and isPrime(e+4):
        e1 = pow(e, 0x10001, phi)
        e2 = pow(e + 2, 0x10001, phi)
        s,s1,s2=gmpy2.gcdext(e1,e2)
        m=(pow(c1,s1,n)*pow(c2,s2,n))%n
        flag=long_to_bytes(m)
        #print(flag)
        str='You are intuitively understanding the distribution of prime numbers! Bonus: You can solve this challenge w/ N instead of p and q!'
        print(hashlib.md5(str.encode('utf-8')).hexdigest())
        break
    e+=1

提交需要md5加密，注意只需要加密flag内部的内容即可。

[长城杯 2022 政企组]xor

看题目是一道异或题：

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
import os
from secret import flag

def cut(obj, sec):
    return [obj[i:i+sec] for i in range(0,len(obj),sec)]

x = 6
assert flag.startswith('flag{')
assert flag.endswith('}')
m = cut(flag, x)

pad = os.urandom(x)
res = []
for i in m:
    tmp = []

    tmp.append(i[0] ^ i[1] ^ i[2] ^ pad[0])
    tmp.append(i[3] ^ i[4] ^ pad[1] ^ pad[2])
    tmp.append(pad[5] ^ i[5] ^ pad[1] ^ pad[3])
    tmp.append(i[3] ^ pad[3] ^ pad[4] ^ pad[1])
    tmp.append(i[5] ^ pad[0] ^ i[4] ^ pad[1])
    tmp.append(i[2] ^ i[4] ^ pad[0] ^ pad[1])
    tmp.append(i[2] ^ i[0] ^ i[4] ^ pad[4])
    
    res.append(tmp)

print(res)
#[[150, 194, 49, 195, 23, 79, 66], [194, 136, 63, 147, 3, 2, 81], [132, 221, 57, 144, 83, 83, 93], [208, 223, 37, 193, 28, 0, 70], [154, 203, 108, 156, 28, 78, 68], [159, 221, 62, 146, 86, 82, 88], [197, 141, 117, 192, 31, 90, 85]]

这题用cut对flag进行了一种块加密的操作，实质就是异或。

这题最好的突破口就在题目提了一下assert flag.startswith('flag{')，这个异或有一个pad生成的随机字节我们需要去求，用这个flag头代入i数组去运算就能得到pad，也能得到flag第一个块的最后一位：

1
2
3
4
5
6
7
8
9
pad=[0,0,0,0,0,0]
pad[0]=150^ord('f')^ord('l')^ord('a')
pad[4]=66^ord('a')^ord('f')^ord('{')
pad[1]=79^ord('a')^ord('{')^pad[0]
pad[3]=195^ord('g')^pad[4]^pad[1]
pad[2]=194^ord('g')^ord('{')^pad[1]
i=23^pad[0]^ord('{')^pad[1]
pad[5]=49^i^pad[1]^pad[3]
print(pad)

有了pad之后，根据他的运算法则把得到的数组再异或回去即可，有点绕，但不多：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
list=[[150, 194, 49, 195, 23, 79, 66], [194, 136, 63, 147, 3, 2, 81], [132, 221, 57, 144, 83, 83, 93], [208, 223, 37, 193, 28, 0, 70], [154, 203, 108, 156, 28, 78, 68], [159, 221, 62, 146, 86, 82, 88], [197, 141, 117, 192, 31, 90, 85]]
pad=[0,0,0,0,0,0]
pad[0]=150^ord('f')^ord('l')^ord('a')
pad[4]=66^ord('a')^ord('f')^ord('{')
pad[1]=79^ord('a')^ord('{')^pad[0]
pad[3]=195^ord('g')^pad[4]^pad[1]
pad[2]=194^ord('g')^ord('{')^pad[1]
i=23^pad[0]^ord('{')^pad[1]
pad[5]=49^i^pad[1]^pad[3]
flag=''
flag+='flag{'+chr(i)
for j in range(1,len(list)):
    i=list[j]
    tmp=['','','','','','']
    tmp[5]=chr(i[2]^pad[5]^pad[1]^pad[3])
    tmp[3]=chr(i[3]^pad[3]^pad[4]^pad[1])
    tmp[4]=chr(i[4]^ord(tmp[5])^pad[0]^pad[1])
    tmp[2]=chr(i[5]^ord(tmp[4])^pad[0]^pad[1])
    tmp[0]=chr(i[6]^ord(tmp[2])^ord(tmp[4])^pad[4])
    tmp[1]=chr(i[0]^ord(tmp[0])^ord(tmp[2])^pad[0])
    for k in tmp:
        flag+=k
print(flag)

[红明谷CTF 2022]easy_ya

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

def gen():
    e = 3
    while True:
        try:
            p = getPrime(512)
            q = getPrime(512)
            n = p*q
            phi = (p-1)*(q-1)
            d = inverse(e,phi)
            return p,q,d,n,e
        except:
            continue
    return p,q,d,n,e

p,q,d,n,e = gen()
r = getPrime(512)
m = bytes_to_long(flag+os.urandom(32))
M = m%r
c = pow(m,e,n)
print("r = %d"%r)
print("M = %d"%M)
print("n = %d"%n)
print("e = %d"%e)
print("c = %d"%c)
'''
r = 7996728164495259362822258548434922741290100998149465194487628664864256950051236186227986990712837371289585870678059397413537714250530572338774305952904473
M = 4159518144549137412048572485195536187606187833861349516326031843059872501654790226936115271091120509781872925030241137272462161485445491493686121954785558
n = 131552964273731742744001439326470035414270864348139594004117959631286500198956302913377947920677525319260242121507196043323292374736595943942956194902814842206268870941485429339132421676367167621812260482624743821671183297023718573293452354284932348802548838847981916748951828826237112194142035380559020560287
e = 3
c = 46794664006708417132147941918719938365671485176293172014575392203162005813544444720181151046818648417346292288656741056411780813044749520725718927535262618317679844671500204720286218754536643881483749892207516758305694529993542296670281548111692443639662220578293714396224325591697834572209746048616144307282
'''

这题对m做了处理，有$m=M+k_1r$

因为$e=3$，所以有：

可以构造多项式$f=(M+k_1r)^3-c$

用coppersmith求解m得到flag：

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

r = 7996728164495259362822258548434922741290100998149465194487628664864256950051236186227986990712837371289585870678059397413537714250530572338774305952904473
M = 4159518144549137412048572485195536187606187833861349516326031843059872501654790226936115271091120509781872925030241137272462161485445491493686121954785558
n = 131552964273731742744001439326470035414270864348139594004117959631286500198956302913377947920677525319260242121507196043323292374736595943942956194902814842206268870941485429339132421676367167621812260482624743821671183297023718573293452354284932348802548838847981916748951828826237112194142035380559020560287
e = 3
c = 46794664006708417132147941918719938365671485176293172014575392203162005813544444720181151046818648417346292288656741056411780813044749520725718927535262618317679844671500204720286218754536643881483749892207516758305694529993542296670281548111692443639662220578293714396224325591697834572209746048616144307282
p.<x>=PolynomialRing(Zmod(n))
f=(M+x*r)^3-c
f=f.monic()
x0=f.small_roots()[0]
k=int(x0)
m=M+k*r
print(long_to_bytes(m))

WEEK 3

[zer0pts 2020]ROR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import random
from secret import flag

ror = lambda x, l, b: (x >> l) | ((x & ((1<<l)-1)) << (b-l))

N = 1
for base in [2, 3, 7]:
    N *= pow(base, random.randint(123, 456))
e = random.randint(271828, 314159)

m = int.from_bytes(flag, byteorder='big')
assert m.bit_length() < N.bit_length()

for i in range(m.bit_length()):
    print(pow(ror(m, i, m.bit_length()), e, N))
    
'''
共367个大数
1123279905753420854056949270002079681846506391469678488301569277287912082415123311220349271402019208029052224502080757137106573269187631637748684158368045600005655891722764459682451768985892383847582777401840658306512477897257240329468693759755275846566672333848486514916087101615422164522188501353017634498421719941291156644882844167419683097913336651801182760157321799921263689020310161398379427011654220488495216138997481624067312309716359256133688385745929373875911175705411323092025782228256765
60848463499016786897050297575193379856357320605752544731915960900662600736882534150881154375836797044831443206517611246422944245077214035778529831198642997131725966633365520266930784297332554358743269582513125982070736168184463231257501147666235039856936758619962287224127462217899181431380749110624483441043813791223675322207707555956618770587208981573720919846554234432849886071965346594511242517114924137967847829591750727942755115692172497988369795219622584033874069145907439553222939015905280
237348271212870069146218394147712821983756154361121125464843821356777343086464786262769510843094453963434423871359291400355493177339013648909538576312957298531245771260362473919076759706682735266855920298899200500046967238386252391851138198530671332478315828876262645843939174292712690021408705461921177334034837441241231182751353058298103009124765377211803579840406270396477937117875490192355651017855958671557749329097262800621575287211938761281102664405069806503929644344867737790185734896367903
...
'''

第一次看这个题一点头绪都没有，后来仔细研究了一下ror()之后发现好像不是很复杂：

1
ror = lambda x, l, b: (x >> l) | ((x & ((1<<l)-1)) << (b-l))

顺着分析了一下这个位运算，这个函数把x数后l位给移到了最前面，在题目代码中用了一个循环：

1
2
for i in range(m.bit_length()):
    print(pow(ror(m, i, m.bit_length()), e, N))

对于ror(m, i, m.bit_length())随着i的增大，被提到最前面的后位越来越多，所以可以根据每一轮的末位来复原原数，e次方并没有改变二进制的末位，由于n为偶数，含有因子2，n的二进制末位一定为0，模运算不会改变原数的末位值，所以直接把得到的这些数末位提取出来还原原数就能得到flag：

1
2
3
4
5
6
7
from Crypto.Util.number import *

with open('chall.txt','r') as f:
    f=f.readlines()
    num=[bin(int(i))[-1] for i in f]
    flag=''.join(num[len(num)-i-1] for i in range(len(num)))
    print(long_to_bytes(int(flag,2)))

[HUBUCTF 2022 新生赛]ezMath

题目：小学二年级数学，做对100道就给flag，简单吧。

这道题给了nc的ip和端口，没给代码，先连上看看要干啥：

1
2
3
4
5
6
7
8
9
from pwn import *

p = remote("43.143.7.97", 28018)
p.interactive()

'''
[+] sha256(XXXX+Vmadgdm6sxtjigB7) == 1aca8c61a88c891794e47ff8cbb6c3ded7bcb764df23c15d4a65ad591077a3e9
[+] Plz Tell Me XXXX :
'''

首先需要爆破一个sha256，然后发送爆破值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from pwn import *
import hashlib
import string

def sfsha(str1, str2):
    t = string.ascii_letters+string.digits
    for a in t:
        for b in t:
            for c in t:
                for d in t:
                    if hashlib.sha256((a+b+c+d+str1.decode()).encode()).hexdigest() == str2.decode():
                        return a+b+c+d

p = remote("43.143.7.97", 28018)
p.recvuntil(b'sha256(XXXX+')
str1 = p.recvuntil(b')', drop=True)
p.recvuntil(b'== ')
str2 = p.recvuntil(b'\n', drop=True)
p.sendline((sfsha(str1, str2)).encode())

这里需要利用到pwntools库的一些函数，在知道了返回的内容之后可以根据其特点来截取需要的部分：我们需要已知的爆破字段Vmadgdm6sxtjigB7和sha256值，p.recvuntil(b'xxxxx')这个函数可以接收返回内容截止到括号内的字符串停止，drop属性可以设置返回值是否包含括号内字符串。

发送爆破值之后继续监听：

1
2
3
4
p.interactive()

[+] Welcome to  Calc Service
[+] 44//53 = ?

这就是所谓的100道小学数学题，根据其特点写一个循环解100次就行：

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
from pwn import *
import hashlib
import string

def sfsha(str1, str2):
    t = string.ascii_letters+string.digits
    for a in t:
        for b in t:
            for c in t:
                for d in t:
                    if hashlib.sha256((a+b+c+d+str1.decode()).encode()).hexdigest() == str2.decode():
                        return a+b+c+d

p = remote("43.143.7.97", 28018)
p.recvuntil(b'sha256(XXXX+')
str1 = p.recvuntil(b')', drop=True)
p.recvuntil(b'== ')
str2 = p.recvuntil(b'\n', drop=True)
p.sendline((sfsha(str1, str2)).encode())
for i in range(100):
    l = p.recvline()
    l = p.recvline()
    c = eval(l.split(b' ')[1])
    print(l.split(b' ')[1].decode(), '=', c)
    p.sendline(str(c).encode())
print(p.recv().decode())

'''
28+17 = 45
54%93 = 54
86-94 = -8
57+82 = 139
34*76 = 2584
37%26 = 11
2*93 = 186
17+90 = 107
18-60 = -42
45-35 = 10
10*14 = 140
95+30 = 125
5+75 = 80
40*97 = 3880
58+35 = 93
79%85 = 79
17//38 = 0
80-78 = 2
55-40 = 15
71*7 = 497
60*83 = 4980
90*31 = 2790
40-78 = -38
15%51 = 15
60//40 = 1
44+99 = 143
58*68 = 3944
41*30 = 1230
87+38 = 125
50-84 = -34
12*33 = 396
1+80 = 81
63-23 = 40
76%32 = 12
73*20 = 1460
86*46 = 3956
1*73 = 73
87%50 = 37
6-80 = -74
16%24 = 16
93%41 = 11
93*63 = 5859
42%4 = 2
97*8 = 776
40%3 = 1
80*66 = 5280
41%43 = 41
93-68 = 25
75//42 = 1
22%43 = 22
51-71 = -20
26//91 = 0
40-99 = -59
38-20 = 18
29//50 = 0
78//77 = 1
50%34 = 16
76//92 = 0
52//8 = 6
65-26 = 39
78*31 = 2418
54//91 = 0
56//25 = 2
16+27 = 43
52+37 = 89
4//81 = 0
71-77 = -6
71//47 = 1
44-46 = -2
27-38 = -11
4*76 = 304
28+40 = 68
48+16 = 64
59*66 = 3894
99+62 = 161
51+49 = 100
47//62 = 0
62+79 = 141
84-22 = 62
76%31 = 14
40-7 = 33
48*31 = 1488
74-10 = 64
61-31 = 30
73%96 = 73
27+69 = 96
55-57 = -2
67//72 = 0
99*53 = 5247
13*39 = 507
3%42 = 3
88*66 = 5808
50+24 = 74
52%63 = 52
62*53 = 3286
66+5 = 71
16-14 = 2
55*35 = 1925
28*8 = 224
61+7 = 68
[+] Good Job!
You get flag: NSSCTF{dc9397ce-cb67-4557-8176-3dff71cb202b}
'''

python的eval函数可以寻找字符串中符合条件的运算式并计算返回值，但是它会识别到pwntools库返回的[+]导致报错，所以实际使用可以稍微处理一下返回值，方式并不唯一。

[广东强网杯 2021 团队组]RSA and BASE?

题目：

1
2
3
4
5
6
7
RSA:
n=56661243519426563299920058134092862370737397949947210394843021856477420959615132553610830104961645574615005956183703191006421508461009698780382360943562001485153455401650697532951591191737164547520951628336941289873198979641173541232117518791706826699650307105202062429672725308809988269372149027026719779368169
e=36269788044703267426177340992826172140174404390577736281478891381612294207666891529019937732720246602062358244751177942289155662197410594434293004130952671354973700999803850153697545606312859272554835232089533366743867361181786472126124169787094837977468259794816050397735724313560434944684790818009385459207329
c=137954301101369152742229874240507191901061563449586247819350394387527789763579249250710679911626270895090455502283455665178389917777053863730286065809459077858674885530015624798882224173066151402222862023045940035652321621761390317038440821354117827990307003831352154618952447402389360183594248381165728338233

BASE:
"GHI45FQRSCX****UVWJK67DELMNOPAB3"

就给了几个数，先看到enc，直接维纳攻击得到flag{TCMDIEOH2MJFBLKHT2J7BLYZ2WUE5NYR2HNG====}

里面的内容很明显是base32加密过，但是解密过后发现是乱码，题目还给了一行BASE，猜测是自定义base32加密，而且里面还有四位未知，可以爆破。

至于如何进行自定义base32解密，有个办法是通过下标对应来转为传统密文：

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

list = ['T', 'Y', 'Z', '2']
b32 = []
for i in list:
    for j in list:
        if i != j:
            for h in list:
                if h != i and h != j:
                    for g in list:
                        if h != g and g != i and g != j:
                            key = i+j+h+g
                            b32.append(key)

cipher = 'TCMDIEOH2MJFBLKHT2J7BLYZ2WUE5NYR2HNG===='
base32 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567"

for i in b32:
    dic = 'GHI45FQRSCX' + i + 'UVWJK67DELMNOPAB3'
    res = ''
    for i in cipher:
        if i in base32:
            res += base32[dic.index(i)]
        else:
            res += i
    print(base64.b32decode(res))

能在给出的几个结果里找到一个合适的作为flag。

[GKCTF 2021]RRRRsa

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

flag = b'xxxxxxxxxxxxx'
p = getPrime(512)
q = getPrime(512)
m = bytes_to_long(flag)
n = p*q
e = 65537
c = pow(m,e,n)
print('c={}'.format(c))

p1 = getPrime(512)
q1 = getPrime(512)
n1 = p1*q1
e1 = 65537
assert gcd(e1,(p1-1)*(q1-1)) == 1
c1 = pow(p,e1,n1)
print('n1={}'.format(n1))
print('c1={}'.format(c1))
hint1 = pow(2020 * p1 + q1, 202020, n1)
hint2 = pow(2021 * p1 + 212121, q1, n1)
print('hint1={}'.format(hint1))
print('hint2={}'.format(hint2))

p2 = getPrime(512)
q2 = getPrime(512)
n2 = p2*q2
e2 = 65537
assert gcd(e1,(p2-1)*(q2-1)) == 1
c2 = pow(q,e2,n2)
hint3 = pow(2020 * p2 + 2021 * q2, 202020, n2)
hint4 = pow(2021 * p2 + 2020 * q2, 212121, n2)
print('n2={}'.format(n2))
print('c2={}'.format(c2))
print('hint3={}'.format(hint3))
print('hint4={}'.format(hint4))

#c=13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
#n1=75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
#c1=68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
#hint1=23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
#hint2=52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
#n2=114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
#c2=67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
#hint3=25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
#hint4=104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513

先看hint1和hint2：

根据同余的性质和费马小定理，将上面两个式子拆分变形：

将两式放在一起配一下可以得到含有p的式子：

同理，hint3和hint4也可以用类似的方法：

将其化简，配方：

分别解两次RSA得到pq之后再解一轮得到flag：

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

c=13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
n1=75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
c1=68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
hint1=23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
hint2=52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
n2=114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
c2=67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
hint3=25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
hint4=104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513
e = 65537

q1 = gmpy2.gcd(pow(2021,202020)*hint1 - pow(2020*(hint2 - 212121), 202020, n1), n1)
p1=n1//q1
phi1=(p1-1)*(q1-1)
d1=gmpy2.invert(e,phi1)
p=pow(c1,d1,n1)
q2=gmpy2.gcd(pow(pow(2020,202020)*hint3,212121,n2)-pow(pow(2021,212121)*hint4,202020,n2),n2)
p2=n2//q2
phi2=(p2-1)*(q2-1)
d2=gmpy2.invert(e,phi2)
q=pow(c2,d2,n2)
n=p*q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

WEEK 4

[MTCTF 2021]hamburgerRSA

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 *

flag = open('flag.txt').read()
nbit = 64

while True:
    p, q = getPrime(nbit), getPrime(nbit)
    PP = int(str(p) + str(p) + str(q) + str(q))
    QQ = int(str(q) + str(q) + str(p) + str(p))
    if isPrime(PP) and isPrime(QQ):
        break

n = PP * QQ
m = bytes_to_long(flag.encode())
c = pow(m, 65537, n)
print('n =', n)
print('c =', c)

'''
n = 177269125756508652546242326065138402971542751112423326033880862868822164234452280738170245589798474033047460920552550018968571267978283756742722231922451193
c = 47718022601324543399078395957095083753201631332808949406927091589044837556469300807728484035581447960954603540348152501053100067139486887367207461593404096
'''

这题对pq生成用了一种特殊的方法，在得到因子之前，需要先了解一下位数和乘法之间的关系：

对于64bit的p和q，先试一下它们在十进制下的位数长度和乘积长度：

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

while True:
    p = getPrime(64)
    q = getPrime(64)
    res = p*q
    print(len(str(p)),end=" ")
    print(len(str(q)),end=" ")
    print(len(str(res)))

p和q大部分为20位，少数会生成19位。全为20位时乘积为39位，单个为19位时乘积有一定可能为38位，如果两个19位时乘积为38位。

我们需要大致判断出来本题的p和q大概为多少位，先设为x和y：

由上式可以观察到：决定n的位数的就是第一项，这题的n为156位，如果xy全为20，第一项的位数就为120+39=159位，不满足要求，如果其中一个为19位，位数为117+39(38)=156(155)，基本符合要求，所以p和q的位数关系应该为1个20位、1个19位，pq乘积为39位。

由于PPQQ位数太大构成式子复杂不好分解，pq只有39位比较好因式分解，需要得到pq，在给出n的多项式前三项里，包含实际数据的位数分别为118-156；98-136；99-137

所以，n的138-156位是已知的“纯净”的pq乘积，总共19位，同理，可以得到低位三项位数范围1-39；20-58；21-59；的19位，缺少中间的一位，可以爆破一下挨个因式分解一下看看哪个能分解成两个bit=64的因子：

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 *

n=177269125756508652546242326065138402971542751112423326033880862868822164234452280738170245589798474033047460920552550018968571267978283756742722231922451193
print(str(n)[:19],str(n)[-19:])
res1=1772691257565086525
res2=6742722231922451193
for i in range(0,10):
    pq=int(str(res1)+str(i)+str(res2))
    if not isPrime(pq):
        print(i,pq)
'''
0 177269125756508652506742722231922451193
1 177269125756508652516742722231922451193
2 177269125756508652526742722231922451193
3 177269125756508652536742722231922451193
4 177269125756508652546742722231922451193
5 177269125756508652556742722231922451193
6 177269125756508652566742722231922451193
7 177269125756508652576742722231922451193
8 177269125756508652586742722231922451193
'''

当中间位为2时，能分解出pq两个因子，破解RSA：

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

n = 177269125756508652546242326065138402971542751112423326033880862868822164234452280738170245589798474033047460920552550018968571267978283756742722231922451193
c = 47718022601324543399078395957095083753201631332808949406927091589044837556469300807728484035581447960954603540348152501053100067139486887367207461593404096
a = 18109858317913867117
b = 9788542938580474429
e=65537
p=int(str(a)+str(a)+str(b)+str(b))
q=int(str(b)+str(b)+str(a)+str(a))
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[鹏城杯 2022]babyrsa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from libnum import s2n
from secret import flag
p = getPrime(1024)
q = getPrime(16)
n = p*q
m = s2n(flag)
for i in range(1,p-q):
    m = m*i%n
e = 1049
print(pow(2,e,n))
print(pow(m,e,n))
#4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
#3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270

看到m想到了威尔逊定理，不过在此之前，可以先把n因式分解出来，尽管没给n，可以根据$2^{1049}$求出n：

用yafu爆一下，由于pq差距太大，能顺带求得n因式分解的结果，这就方便很多了：

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

e=1049
p=170229264879724117919007372149468684565431232721075153274808454126426741324966131188484635914814926870341378228417496808202497615585946352638507704855332363766887139815236730403246238633855524068161116748612090155595549964229654262432946553891601975628848891407847198187453488358420350203927771308228162321231
q=34211
n=170229264879724117919007372149468684565431232721075153274808454126426741324966131188484635914814926870341378228417496808202497615585946352638507704855332363766887139815236730403246238633855524068161116748612090155595549964229654262432946553891601975628848891407847198187453488358420350203927771308228162321231*34211
c=3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270
phi=int(sympy.totient(n))
d=gmpy2.invert(e,phi)
M=pow(c,d,n)

求出M之后用威尔逊定理求解m：

两式相除：

简化运算后可以求解：

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

e=1049
n=170229264879724117919007372149468684565431232721075153274808454126426741324966131188484635914814926870341378228417496808202497615585946352638507704855332363766887139815236730403246238633855524068161116748612090155595549964229654262432946553891601975628848891407847198187453488358420350203927771308228162321231*34211
c=3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270
phi=int(sympy.totient(n))
d=gmpy2.invert(e,phi)
M=pow(c,d,n)
m=1
for i in range(p-q,p):
    m = m*i%p
m=(-M)*m%p
print(long_to_bytes(m))

[羊城杯 2021]Easy_Rsa

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

def gen_prime(nbits, gamma):
    g = getPrime(int(nbits * gamma))
    alpha = 0.5 - gamma
    while True:
        a = getRandomNBitInteger(int(alpha * nbits))
        p = 2 * g * a + 1
        if isPrime(p):
            b = getRandomNBitInteger(int(alpha * nbits))
            q = 2 * g * b + 1
            h = 2 * g * a * b + a + b
            while not isPrime(q) or isPrime(h) or gmpy2.gcd(a, b) != 1:
                b = getRandomNBitInteger(int(alpha * nbits))
                q = 2 * g * b + 1
            return p, q

def encrypt(nbits, gamma):
    p, q = gen_prime(nbits, gamma)
    n = p * q
    e = getPrime(16)
    while gmpy2.gcd(e, gmpy2.lcm(p-1,q-1)) != 1:
        e = getPrime(16)
    m = bytes_to_long(flag)
    c = pow(m, e, n)
    return n, e, c

n, e, c = encrypt(1024, 0.48)
print 'n =', n
print 'e =', e
print 'c =', c

# n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
# e = 58337
# c = 13646200911032594651110040891135783560995665642049282201695300382255436792102048169200570930229947213493204600006876822744757042959653203573780257603577712302687497959686258542388622714078571068849217323703865310256200818493894194213812410547780002879351619924848073893321472704218227047519748394961963394668

这题用了pollardrho算法的变种，先记着脚本，没找到算法：

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

f = lambda x,n: (pow(x, n - 1, n) + 3) % n
def phllard_rho(n):
    i = 1
    while True:
        a = getRandomRange(2, n)
        b = f(a, n)
        j = 1
        while True:
            p = GCD(abs(a - b), n)
            if p == n:
                break
            elif p > 1:
                return (p, n // p)
            else:
                a = f(a, n)
                b = f(f(b, n), n)
            j += 1
        i += 1

n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
c = 13646200911032594651110040891135783560995665642049282201695300382255436792102048169200570930229947213493204600006876822744757042959653203573780257603577712302687497959686258542388622714078571068849217323703865310256200818493894194213812410547780002879351619924848073893321472704218227047519748394961963394668
e = 58337

p,q = phllard_rho(n)
d = invert(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

[强网杯 2022]ASR

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 getPrime
from secret import falg
pad = lambda s:s + bytes([(len(s)-1)%16+1]*((len(s)-1)%16+1))

n = getPrime(128)**2 * getPrime(128)**2 * getPrime(128)**2 * getPrime(128)**2
e = 3

flag = pad(flag)
print(flag)
assert(len(flag) >= 48)
m = int.from_bytes(flag,'big')
c = pow(m,e,n)

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

'''
n = 8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001
e = 3
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149
'''

对于n有：

pqrs都是128位小因子，或者网站或者yafu爆破可以得到四个因子，尝试直接求phi解RSA，发现phi和e有不互质，再看看是谁不互质：

1
2
print(gmpy2.gcd(e,p-1),gmpy2.gcd(e,q-1),gmpy2.gcd(e,r-1),gmpy2.gcd(e,s-1))
#3 1 3 1

有两个因子使得e和phi不互素，去掉这两个因子根据同余性质构造新RSA求解：

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

n=8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001
p=218566259296037866647273372633238739089
q=223213222467584072959434495118689164399
r=225933944608558304529179430753170813347
s=260594583349478633632570848336184053653
e=3
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149
print(gmpy2.gcd(e,p-1),gmpy2.gcd(e,q-1),gmpy2.gcd(e,r-1),gmpy2.gcd(e,s-1))
phi=q*s*(q-1)*(s-1)
n=q*s*q*s
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

注意到这里需要两个q和s，因为如果只用单个p和s的话原始m的长度不够，需要两组q和s。

这题看wp还有一种做法，用中国剩余定理分别在有限域开三次方根：

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

n = 8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001
e = 3
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149
p = 225933944608558304529179430753170813347
q = 260594583349478633632570848336184053653
r = 218566259296037866647273372633238739089
t = 223213222467584072959434495118689164399

R.<x> = Zmod(p)[]
f = x^e-c
f = f.monic()
results1 = f.roots()

R.<x> = Zmod(q)[]
f = x^e-c
f = f.monic()
results2 = f.roots()

R.<x> = Zmod(r)[]
f = x^e-c
f = f.monic()
results3 = f.roots()

R.<x> = Zmod(t)[]
f = x^e-c
f = f.monic()
results4 = f.roots()
for a in results1:
    for b in results2:
        for c in results3:
             for d in results4:
                list1=[int(a[0]),int(b[0]),int(c[0]),int(d[0])]
                list2=[p,q,r,t]
                m = CRT_list(list1,list2)
                flag = long_to_bytes(int(m))
                if b'flag' in flag:
                    print(flag)

[watevrCTF 2019]ECC-RSA

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
from fastecdsa.curve import P521 as Curve
from fastecdsa.point import Point
from Crypto.Util.number import bytes_to_long, isPrime
from os import urandom
from random import getrandbits

def gen_rsa_primes(G):
	urand = bytes_to_long(urandom(521//8))
	while True:
		s = getrandbits(521) ^ urand

		Q = s*G
		if isPrime(Q.x) and isPrime(Q.y):
			print("ECC Private key:", hex(s))
			print("RSA primes:", hex(Q.x), hex(Q.y))
			print("Modulo:", hex(Q.x * Q.y))
			return (Q.x, Q.y)


flag = int.from_bytes(input(), byteorder="big")

ecc_p = Curve.p
a = Curve.a
b = Curve.b

Gx = Curve.gx
Gy = Curve.gy
G = Point(Gx, Gy, curve=Curve)


e = 0x10001
p, q = gen_rsa_primes(G)
n = p*q


file_out = open("downloads/ecc-rsa.txt", "w")

file_out.write("ECC Curve Prime: " + hex(ecc_p) + "\n")
file_out.write("Curve a: " + hex(a) + "\n")
file_out.write("Curve b: " + hex(b) + "\n")
file_out.write("Gx: " + hex(Gx) + "\n")
file_out.write("Gy: " + hex(Gy) + "\n")

file_out.write("e: " + hex(e) + "\n")
file_out.write("p * q: " + hex(n) + "\n")

c = pow(flag, e, n)
file_out.write("ciphertext: " + hex(c) + "\n")

'''
ECC Curve Prime: 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Curve a: -0x3
Curve b: 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00
Gx: 0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66
Gy: 0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650
e: 0x10001
p * q: 0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f
ciphertext: 0x3862c872480bdd067c0c68cfee4527a063166620c97cca4c99baff6eb0cf5d42421b8f8d8300df5f8c7663adb5d21b47c8cb4ca5aab892006d7d44a1c5b5f5242d88c6e325064adf9b969c7dfc52a034495fe67b5424e1678ca4332d59225855b7a9cb42db2b1db95a90ab6834395397e305078c5baff78c4b7252d7966365afed9e
'''

这是一道RSA和ECC综合起来的一道题目，本质还是RSA，因子pq的生成是借助椭圆曲线来生成的，有：

当x,y=p,q时，代入：

构造多项式：

题目把P、a、b都给了，可以用sage进行求解p：

1
2
3
4
5
6
7
8
9
10
11
12
13
P=0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
a = -0x3
b = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00
e = 0x10001
n=0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f
c=0x3862c872480bdd067c0c68cfee4527a063166620c97cca4c99baff6eb0cf5d42421b8f8d8300df5f8c7663adb5d21b47c8cb4ca5aab892006d7d44a1c5b5f5242d88c6e325064adf9b969c7dfc52a034495fe67b5424e1678ca4332d59225855b7a9cb42db2b1db95a90ab6834395397e305078c5baff78c4b7252d7966365afed9e
R.<x>=Zmod(P)[]
f=x**5+a*x**3+b*x**2-n**2
list=f.roots()
for i in list:
    if isPrime(int(i[0])) and n%int(i[0])==0:
        print(i[0])
        break

解密RSA：

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

e = 0x10001
n=0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f
c=0x3862c872480bdd067c0c68cfee4527a063166620c97cca4c99baff6eb0cf5d42421b8f8d8300df5f8c7663adb5d21b47c8cb4ca5aab892006d7d44a1c5b5f5242d88c6e325064adf9b969c7dfc52a034495fe67b5424e1678ca4332d59225855b7a9cb42db2b1db95a90ab6834395397e305078c5baff78c4b7252d7966365afed9e
p=4573744216059593260686660411936793507327994800883645562370166075007970317346237399760397301505506131100113886281839847419425482918932436139080837246914736557 
q=2824062321531218201174796572016162635824475505413691713885561763408852922459097896008852396651320629671944905279844855869954833917289579518017582137554769067
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[强网拟态 2021]ONLYRSA

1
2
3
4
5
6
7
8
9
10
#!/usr/bin/env python
from Crypto.Util.number import *
from secret import flag

n = 264048827496427248021277383801027180195275776366915828865010362454006394906519399441496561006668252031429735502465174250525698696973129422193405161920872162928097673289330345041221985548078586423910246601720647996170161319016119241836415788315729493164331517547663558380515400720081995290120793014108439083514403659082115510258023834737471488528527557960636984676435543300074504679264476413252780514962473070445293528877641502742438571110744667739728450283295649865745629276142949963507003094791773183928894536793857609738113546410753895719242547720815692998871947957214118354127328586542848234994500987288641595105
e = 65537
m = bytes_to_long(flag)
c = pow(m,e,n)
print(c)
# 76196483810925191371357319946893762223027002702624516192769497540954799651198719100683206759706879828894501526423422596543748404479640715319801018211652987852179907519286760601944889601355220646374788026632971331786307898234821477134265724962397355614076896148563340833323366935479885600112872998594315513803419069126624158092821269145991266528158747750965226483644012365861166608598063649804899693010576080857540523307078138634628539419178875838147396170651777949577793359622498517581948006585916952705460782942977789615065947303447566918741750017127110484065354974088489869377128636357092420660532261674969708694

题目给了一句描述：RSA say : My birthday is in November instead of October

看完wp后才发现这是一个脑洞题，不过也为解RSA提供了一种新的思路：

描述的意思让我们把模数转为11进制，可以在sage里用digit函数进行转换：

1
2
3
4
5
n = 264048827496427248021277383801027180195275776366915828865010362454006394906519399441496561006668252031429735502465174250525698696973129422193405161920872162928097673289330345041221985548078586423910246601720647996170161319016119241836415788315729493164331517547663558380515400720081995290120793014108439083514403659082115510258023834737471488528527557960636984676435543300074504679264476413252780514962473070445293528877641502742438571110744667739728450283295649865745629276142949963507003094791773183928894536793857609738113546410753895719242547720815692998871947957214118354127328586542848234994500987288641595105
p = 11
a = n.digits(p)
print(a)
#[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

得到的是按照位数顺序整理的数组，可见有非常多的0，用11进制数的形式构造多项式的项数相对较少，对多项式进行分解比较容易，可以考虑到多项式分解求p：

这里用sage进行相关操作比较容易：

1
2
3
4
5
6
7
8
n = 264048827496427248021277383801027180195275776366915828865010362454006394906519399441496561006668252031429735502465174250525698696973129422193405161920872162928097673289330345041221985548078586423910246601720647996170161319016119241836415788315729493164331517547663558380515400720081995290120793014108439083514403659082115510258023834737471488528527557960636984676435543300074504679264476413252780514962473070445293528877641502742438571110744667739728450283295649865745629276142949963507003094791773183928894536793857609738113546410753895719242547720815692998871947957214118354127328586542848234994500987288641595105
p = 11
a = n.digits(p)
PR.<x> = PolynomialRing(ZZ)
f = PR(a)
fac = factor(f)
print(fac)
#(x^295 + 2*x^249 + x^196 + 1) * (x^295 + 2*x^281 + 2*x^192 + x^100 + 2*x^37 + 1)

注意到这里我们是在11进制下构造的10进制多项式，在x=11下才能得到原来的n。

所以，对于分解出的两个多项式因子，分别使x=11就能得到两个因子：

1
2
16249579302136589695295481114504339262045249125801939374419304404565893699789462299636475519992076209810443523832755415818528536943125532985768629325734679453205207122927745917471850395124342956866284689792620888965652429711989205344392333681297321070276796015579775171010928476523589349812683875326849195595
16249579302136675275737472669394168521026727339712083110552530420348131906271518040549529167354613121510156841352658645018277766962773342379074137176993546193979134201416444089373463960664685121485689105129185197998903479181913613273443541075619342246119648308939006396145123630152777688592984718084919469059

最坑的地方来了，检测一下这两个大数发现有一个不是素数，继续分解的话又比较困难，索性直接用p当n解RSA：

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

p=16249579302136675275737472669394168521026727339712083110552530420348131906271518040549529167354613121510156841352658645018277766962773342379074137176993546193979134201416444089373463960664685121485689105129185197998903479181913613273443541075619342246119648308939006396145123630152777688592984718084919469059
e=65537
c=76196483810925191371357319946893762223027002702624516192769497540954799651198719100683206759706879828894501526423422596543748404479640715319801018211652987852179907519286760601944889601355220646374788026632971331786307898234821477134265724962397355614076896148563340833323366935479885600112872998594315513803419069126624158092821269145991266528158747750965226483644012365861166608598063649804899693010576080857540523307078138634628539419178875838147396170651777949577793359622498517581948006585916952705460782942977789615065947303447566918741750017127110484065354974088489869377128636357092420660532261674969708694
phi=p-1
d=gmpy2.invert(e,phi)
m=pow(c,d,p)
print(long_to_bytes(m))

[NISACTF 2022]xor

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
import os
import base64
from Crypto.Util import number, strxor
#from flag import flag

flag='xxxxxxxxxxxxxxxxxx'


def gen_key():
    return [os.urandom(16) for _ in range(8)]

def rnd(b: bytes, k: bytes):
    l = b[:16]
    r = b[16:]
    _r = l
    _l = strxor.strxor(strxor.strxor(r, k), l)
    return _l + _r

def enc(b: bytes, ks):
    c = b
    for i in range(8):
        c = rnd(c, ks[i])
    return c

if __name__ == '__main__':
    a = os.urandom(32)
    ks = gen_key()
    enc_a = enc(a, ks)
    enc_flag = enc(flag.encode(), ks)
    print(base64.b64encode(a).decode())
    print(base64.b64encode(enc_a).decode())
    print(base64.b64encode(enc_flag).decode())

#i03yXzXWe4QTiwJHlUZo6iqEdDkwJVviSOQ7CM3vJmM=
#4EnYOhbivTMP5r4VYLA8cwJBFTXIeeKAoNf/3ctgLLA=
#+qyVMEei1eN3YbV/z2kjcaCKngWc2pW2/e7HwpXKaj0=

是一道块加密的程序题，用异或进行的加密：

1
2
def gen_key():
    return [os.urandom(16) for _ in range(8)]

这里生成了八轮16字节的轮密钥。

1
2
3
4
5
6
7
8
9
10
11
12
def rnd(b: bytes, k: bytes):
    l = b[:16]
    r = b[16:]
    _r = l
    _l = strxor.strxor(strxor.strxor(r, k), l)
    return _l + _r

def enc(b: bytes, ks):
    c = b
    for i in range(8):
        c = rnd(c, ks[i])
    return c

每轮加密，让右半和本轮密钥以及左半异或，交换前后位置，重复八轮。

这道题并没有给轮密钥，要说求的话也求不出来，由于无论加密什么消息，最终出来的结果无非是左右两半信息，并带有轮密钥一起跟着异或的特点，所以这里可以不考虑具体的轮密钥，而是把左右每一块异或过的密钥看做一个整体，加密的消息变了，但是密钥的转移在过程中不会改变。

先注意一下在过程中，消息的转移，每一轮的右半会与左半进行异或：

八轮转换 originalLeft（L） originalRight（R）
1-2 2.R 1.R^L
3-4 4.R^L 3.L
5-6 6.L 5.R
7-8 8.R 7.L^R

所以，最终得到的两块密文，左半带有原始密文右半的信息同时有密钥一起异或，右半带有右半和左半异或的结果还有密钥。所以可以让其与原来的密文异或得到剩下的秘钥块。

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.strxor import strxor as xor
from base64 import b64decode as b64

a='i03yXzXWe4QTiwJHlUZo6iqEdDkwJVviSOQ7CM3vJmM='
e_a='#4EnYOhbivTMP5r4VYLA8cwJBFTXIeeKAoNf/3ctgLLA='
e_flag='+qyVMEei1eN3YbV/z2kjcaCKngWc2pW2/e7HwpXKaj0='
a=b64(a)
enc_a=b64(e_a)
enc_flag=b64(e_flag)
l,r=a[:16],a[16:]
enc_r,enc_l=enc_a[16:],enc_a[:16]
key_r=xor(xor(enc_r,l),r)
key_l=xor(enc_l,r)

所以，flag的加密也满足上表，得到每组的key之后异或即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
from Crypto.Util.strxor import strxor as xor
from base64 import b64decode as b64

a='i03yXzXWe4QTiwJHlUZo6iqEdDkwJVviSOQ7CM3vJmM='
e_a='#4EnYOhbivTMP5r4VYLA8cwJBFTXIeeKAoNf/3ctgLLA='
e_flag='+qyVMEei1eN3YbV/z2kjcaCKngWc2pW2/e7HwpXKaj0='
a=b64(a)
enc_a=b64(e_a)
enc_flag=b64(e_flag)
l,r=a[:16],a[16:]
enc_r,enc_l=enc_a[16:],enc_a[:16]
key_r=xor(xor(enc_r,l),r)
key_l=xor(enc_l,r)
flag_r=xor(enc_flag[:16],key_l)
flag_l=xor(xor(enc_flag[16:],key_r),flag_r)
print('NSSCTF{'+flag_l.decode()+flag_r.decode()+'}')

NSSCTF Round#11 Basic

这比赛做了一个来小时，出了四个题，剩那两个题有点难就不坐牢了。

ez_enc

Baconic？No,not baconic

ABAABBBAABABAABBABABAABBABAAAABBABABABAAABAAABBAABBBBABBABBABBABABABAABBAABBABAAABBAABBBABABABAAAABBAAABABAABABBABBBABBAAABBBAABABAABBAAAABBBAAAABAABBBAABBABABAABABAAAAABBBBABAABBBBAAAABBBBBAB

试了一下培根，192位不能解，猜测是二进制，A为0B为1然后解码，得到flag：

1
2
3
str='ABAABBBAABABAABBABABAABBABAAAABBABABABAAABAAABBAABBBBABBABBABBABABABAABBAABBABAAABBAABBBABABABAAAABBAAABABAABABBABBBABBAAABBBAABABAABBAAAABBBAAAABAABBBAABBABABAABABAAAAABBBBABAABBBBAAAABBBBBAB'
str=str.replace('A','0').replace('B', '1')
print(''.join(chr(int(str[i:i+8],2)) for i in range(0,len(str),8)))

MyMessage

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 *
import os

flag = os.getenv('FLAG')

e = 127

def sign():
    msg = input("Input message：")
    p = getPrime(512)
    q = getPrime(512)
    n = p*q
    c = pow(bytes_to_long((msg + flag).encode()), e, n)
    print(f"n: {n}")
    print(f"Token: {hex(c)}")

def main():
    while True:
        sign()

main()

e=127，这让我想到了前几天做五道题的时候的那个低加密指数攻击，获取127组数直接CRT就能解，脚本改改就能用：

注意需要先输入我们自己的信息，后台会把flag和msg一起加密，这里直接用个不可见字符加密了就行，不影响flag：

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

e=127
ns,cs = [],[]
sh = remote('node2.anna.nssctf.cn',28972)
for i in range(127):
    print(f'{i+1}/{127}')
    sh.sendline(b'\x00')
    sh.recvuntil(b'n: ')
    ns.append(int(sh.recvline().decode()))
    sh.recvuntil(b'Token: ')
    cs.append(int(sh.recvline().decode(),16))
m_e=solve_crt(cs,ns)
m = int(gmpy2.iroot(m_e, e)[0])
print(long_to_bytes(m))

MyGame

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

flag = os.getenv('FLAG')

def menu():
    print('''=---menu---=
1. Guess
2. Encrypt
''')

p = getPrime(512)
q = getPrime(512)
n = p*q

def randommsg():
    return ''.join(random.choices(string.ascii_lowercase+string.digits, k=30))

mymsg = randommsg()
def guess():
    global mymsg
    msg = input()

    if msg == mymsg:
        print(flag)
    else:
        print(mymsg)
        mymsg = randommsg()

def encrypt():
    e = random.getrandbits(8)
    c = pow(bytes_to_long(mymsg.encode()), e, n)
    print(f'Cipher_{e}: {c}')

def main():
    print(f'n: {n}')
    while True:
        opt = int(input())

        if opt == 1:
            guess()
        elif opt == 2:
            encrypt()

main()

这题题目很长，不过得益于e = random.getrandbits(8)会有概率生成很小的数，直接开方就能得到mymsg然后验证得到flag：

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

p=remote('node1.anna.nssctf.cn',28512)
print(p.recvline())
while 1:
    p.sendline('2'.encode())
    t=p.recvline()
    print(t[:15])
    if b'Cipher_1:' in t :
        break
    if b'Cipher_2:' in t:
        break
    if b'Cipher_3:' in t:
        break
    if b'Cipher_4:' in t:
        break

msg=long_to_bytes(gmpy2.iroot(int(t[10:]),int(chr(t[7])))[0])
print(msg)
p.sendline('1'.encode())
p.sendline(msg)
print(p.recvline())

ez_signin

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 *
from secret import flag

p = getPrime(512)
q = getPrime(512)
assert p > q
n = p*q
e = 65536
m = bytes_to_long(flag)
num1 = (pow(p,e,n)-pow(q,e,n)) % n
num2 = pow(p-q,e,n)
c = pow(m,e,n)

print("num1=",num1)
print("num2=",num2)
print("n=",n)
print("c=",c)

c= 49140445537557319747370258521380832266628925480997870608481586932493417284728958741898158715141253481426256782862515069377084448131828373205132956168004394787405869498445767375566916390982148263164591421258539492316104936618465204360809734703249247155425048804311972229129144861794011029251351400008603964208
n= 91530815691867359702851809294843883210988261884502065659703236526417089749297194911652819322901902811672635037961607325344868895249369348890823963715451286330263722759397285433088118125072701539439159319690211982633007064884800262543109901388114825805923119356671940284021983884326245270988185032638715421361
a0= 9567173861275196858460021832302469701883011569848610630647973537343577185110893845356470627768583723955352277616717525865651072348955345569349493461591617
a1= 9567173861275196858460021793425744964971995864734881146246615079880405791684218529798175073376613011755369604379938176024666146578623561846054825791860481
b0= 62076258573599781640280492901494077016751499076309821274994840668372448434757031161585099060759223091642261784834895411252
b1= 86005590473247956807188326544447837958969250994225159304619548233594032409996812924660353546715287124965907562786740309700

根据题目构造含有公因子的表达式：

和n求公因子得到因式分解：

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

num1= 79619421894029884638677851880473974285442927382245165370739056040759373646371770788157736026274332831561856119631720623514629268579816753416034541909837307091058466817126597057548180129822317731594823465494792051287463339171717641625476673408882440284031658532401976615208858603868261548868074622540386126768
num2= 91822828674172883164716888996174839666678823411077041843096256035477780510442004096659467175147094362970318180834969767217981486835289275533118063566355171073579551817984258735625793623211106430202288294682209882571948851233885979012287314493151872159735325013038543729799578632525474654819432094595256453214
n= 92875831742832378748895662989067752055771801344046318768656580407112306063908453067740280899972677871728194311476114821242068010156585531144035681426722516684584563008407855784146796246241361495649307382425970272912587311106136648975801842846127380231678957556486109520422978004986278328890117201062166628193
c= 71447307417287313144879136829692601205166497818416632261484978008166993137789557661514683724831221759059527356240537593120676746613230611929654083120275104860948647608613639712999291243106945047993160233126018269241066399012656713740126017505002345546448511642658499265913182268607507729813704374651035412796
p=gmpy2.gcd(num1+num2,n)
q=n//p
e=65536

这题还有个比较坑的地方在e上，e为2的16次方，还好前两天做的题里有用Tonelli-Shanks算法求解e为2的次方问题，那道题的n为质数，这里不大好用，不过既然已经直接因式分解完了，那就直接用p做模数求解得了：

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

num1= 79619421894029884638677851880473974285442927382245165370739056040759373646371770788157736026274332831561856119631720623514629268579816753416034541909837307091058466817126597057548180129822317731594823465494792051287463339171717641625476673408882440284031658532401976615208858603868261548868074622540386126768
num2= 91822828674172883164716888996174839666678823411077041843096256035477780510442004096659467175147094362970318180834969767217981486835289275533118063566355171073579551817984258735625793623211106430202288294682209882571948851233885979012287314493151872159735325013038543729799578632525474654819432094595256453214
n= 92875831742832378748895662989067752055771801344046318768656580407112306063908453067740280899972677871728194311476114821242068010156585531144035681426722516684584563008407855784146796246241361495649307382425970272912587311106136648975801842846127380231678957556486109520422978004986278328890117201062166628193
c= 71447307417287313144879136829692601205166497818416632261484978008166993137789557661514683724831221759059527356240537593120676746613230611929654083120275104860948647608613639712999291243106945047993160233126018269241066399012656713740126017505002345546448511642658499265913182268607507729813704374651035412796
p=gmpy2.gcd(num1+num2,n)
e=65536

n=p

def legendre(a, p):#勒让德符号
    return pow(a, (p - 1) // 2, p)

def tonelli(n, p):#求n在模p下平方根
    assert legendre(n, p) == 1
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    if s == 1:
        return pow(n, (p + 1) // 4, p)
    for z in range(2, p):
        if p - 1 == legendre(z, p):
            break
    c = pow(z, q, p)
    r = pow(n, (q + 1) // 2, p)
    t = pow(n, q, p)
    m = s
    t2 = 0
    while (t - 1) % p != 0:
        t2 = (t * t) % p
        for i in range(1, m):
            if (t2 - 1) % p == 0:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        r = (r * b) % p
        c = (b * b) % p
        t = (t * c) % p
        m = i
    return r

count = 0
while e % 2 == 0:
    e = e // 2
    count += 1
d = gmpy2.invert(1,n-1)
m = pow(c, d, n)
for i in range(count):
    m = tonelli(m, n)
m = -m % n
print(bytes.fromhex(hex(m)[2:]).decode())

ez_fac

下面是剩下两道没出的题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
import random
from secret import flag,a0,a1,b0,b1

p = getPrime(512)
q = getPrime(512)
e = getPrime(128)
n = p*q
assert pow(a0,2) + e * pow(b0,2) == n
assert pow(a1,2) + e * pow(b1,2) == n
m = bytes_to_long(flag)
c = pow(m,e,n)

print("c=",c)
print("n=",n)
print("a0=",a0)
print("a1=",a1)
print("b0=",b0)
print("b1=",b1)

这题文献检索能找到这么个定理：

给了已知的数能求出e，也能对其进行因式分解：

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

c= 62194144015175943943855803977418397563269819928731209809196217501647944435916921321318208689570885053208681285165006338680066130685191282724431116319714224319810582802626632327166134936512407699703343679880875370820558819411160671694247759813313254748559859242895992131982108197054171637856584124517664717643
n= 99943274509913720142135216122189172155252982914602347927725454090959589551021883486383109456502386885984323593256577110633781683076806158798313301910944677156126217433591860014718178332010183335581498192962459730957969919416911334293034819918756657854875160945858491843863159358722797616289914287170788070113
a0= 9997163323158910968564455619055683563384377855734437604853384372535221152500103875749523067668673075458165333038276700710441246039726577724818647081592601
a1= 9997163323158910968564455201868948268399388529521602919595477259759197222629470595436905859514103739865816151018028333458856229441684399348916315665031001
b0= 19376653007294289996140050578995499724597175169840963112069668308300718878508042259593504819913431943552934079142053449356
b1= 207063812834149129185677532886004240022752343126800397828673085283869040653437389474190773570107170337460753519011212120156

e=(n-a0**2)//b0**2
p=gmpy2.gcd(a0*b1-a1*b0,n)
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

NTR

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

def init():
    p = getPrime(2048)
    while True:
        x = getRandomNBitInteger(1024)
        y = getPrime(768)
        z = gmpy2.invert(x, p) * y % p
        return (p, x, y, z)

def encrypt(cipher, p, z):
    message = bytes_to_long(cipher)
    r = getRandomNBitInteger(1024)
    c = (r * z + message) % p
    return c

p, x, y, z = init()
c = encrypt(flag, p, z)
with open("cipher.txt", "w") as f:
    f.write("binz = " + str(bin(z)) + "\n")
    f.write("binp = " + str(bin(p)) + "\n")
    f.write("binc = " + str(bin(c)) + "\n")

这题一时半会没找到wp，晚上看了会格密码之后恍然大悟又做了一遍就解出来了，我一想这不都是一样的吗……

化简：

又有：

构造$L=\begin{bmatrix}1 & z\\0 & p\end{bmatrix}$：

直接LLL求解，舍去负值：

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

z = int('1100111100010100101101000110111010110001111111010110111100111111000001001011011010001001010011010000110010100111110011010000011111011011000001101011011101011111111011111111000000001000110110111001111100000100101010101001011111001010110101111001110010010001100001101001001110010001011001011100110111101001011111001001010110100110101110011001001000111101000100000100011101110101101000000000000000010001110001101010111100010111010100110101100000101100110100000001111001101001101011110100000101101001001010100100101110011110100010001001111110011111110101010111111110011111110001000101111100010011111101001111000100111000110011110100010000001001000100110101110000101001001111111000010111101111001110011011011011111100100000011000000111001101000000111111111101001000110101100100011100001010010110001000001110010110100000100010110011010000011010110001101001101100010101001000110110111011100010000010110010000001110010101010101011011010011001011011011001111010101101001111001000101000100001101000110010100101101011100101000100110101010011101000011001111011110111000100111100010111000000011011100111000100001011110001101010001100100101001110000000011001110000010011110101100010000001011110011010011111001100010111010110101101111011001101001110000010010110001100010110011111001110111111001101100010011001111011010111011011001010011110101101110001101000101100111110100001011100100101110100011010110001100010000011110000001001111100000011000110000111101110101010111100101000110100001100101000011001001011111001100010011100111101100001110100101010100100111011011010110001010100101101010001101100110001011111001111111011011010111111101110000001011110001011001110111001011100100001000101101111101011100100010010011001001011010011011101111010101110101101010100101011000100101101100011010111001110001011001110001000101000011001001011000111101010111111000111100111111000110000000101011001011110101010010001111110000011100111011110001001100111011000010111001010011101011111001001011011011011110111010101110001000101000110101101010101100100110101101001011111011010000',2)
p = int('10010000100000001100010000110101101101001001001111010110100010000011010001101110011100101100111001111001100101100010010001101100001011011010111111101010010111110111101100011100110101101011111000000111001001010011101111001111010101010100001111110100111101110100101110110101111111001011100110110100111011001101100010001010100011101100100110110010111100101000111000110010101010000111101110111000011100101000101010010111110101011111100110000010101001001001111011110000010100101010000111101101101101001110001010110001101100101011101010001010010100110101110001010001000100101101011000110010100001111101100000111011010110100101111011011100010101111111000001100111111100101111011000000111100101111011100010100111111001110110111001101101110000011010011010010111000011101101001101001010111111000111110101011111110100010011010111101101100110011111010001011001000001100100101000001110111110111011011010011010000011101011001101001101100000110011101011101000000001101101110100000110101001010101010001000110101110001101110111011010101111101001111011110100000000101000001110100110001111101000010001001001000101110100100010101100000010111000010111100010011011011011101111110011100100010001011011010100111001101111100001110011110010110111010100011011101110010110101100111000011011001100110000001000101001111000111100000101110010000100000110000111001101010001011010001100001111010000101001100001010001011010011010110000000110110100011111110110011100010000101001001110111010001011010110001000110101011001111101110010100011101011101111011100110101110100110010111100010100001000110110100111100101011110010110100001011100100110101011100110011010110011011000011100011110101011001000111010101110111010101101101011001010101100100110110001010000001111001101100011101011000010100111011001010100100010110100110101111000000101000111110101010001100000101000101011110110011000111111101111100001110110011111110000101011001100000101011100000001010101100101101100001011010100100000011001010111001111111000111111100101011010011000101000001011010001101001011111101001101000111011001101',2)
c = int('111100101010010000001000000001110101001100100110110100010011100100000100001001001011111011001110110000000110110010100101101011100100001110101110101101000000101101111001011100110100101100111000110010100001001111111001110111111000101100100111001110000110101010011101010111101000100010100110110010100000011011001010011010001000010001101101010000101011000000001111001001000000111100011000001110001011111100111010011101010010101101111111110000100010001001010100100011100100000101111000101110100111101010100110010111011000111111111100001101100111000001000111001111010101011100101101111111110110110010011000000101011110100011101100010111111111111011100000000000100001010101111010011010111001010000100011001111110001111111110110100001000001001001010111111101101100111101000001111111100110100110111100101101110111001001001111101000111011011101111010101011000000001001010101110011000110110010110000010111000010000100111010001111110000100001111111000001111000101010100001000001101000101111101101111010101111111010001100001110000110000101100000011110010111000001001000001111101100010001100101001010010010011100001000110010110000001001110111111101100111101100100000011100110101001000110011100111110010111110001110110000101010111000011101001100010000100100000011001111010110100111111110110010011110011101010000010111001101101000011100001001010010011010000010110011001111000101010101100000100111010110110010011111101000001000000011010000100010011100010010001001101010011101000011010011110110011101010110111001000000110001000101011100011110010011000111011001000001100111101010010011100000100000010110000011010001010010101100110011110111101100101001001001011000001111110000111110100110110000111010100001110000110100110101111111101100011101100111100011101110001011011100010101010011000101010110011100100100000110011000011000011010110110011111011110101010111001000000110110111111011010100001100100000100011000000011011010111101010000110101111101110100000011001101101111011011101111110101001010001000111111001011101010010011110110111110011110011011101100101101000010',2)

L = matrix(ZZ, [[1, z],[0, p]])
v = L.LLL()[1]
x,y=v[0],v[1]
x_1=gmpy2.invert(x,y)
m=c*x%p*x_1%y
print(long_to_bytes(m))