NewStarCTF 2023 公开赛道 WEEK4|CRYPTO 部分WP

RSA Variation II

1、题目信息
提示："Schmidt Samoa"
附件信息

1. from secret import flag
2. from Crypto.Util.number import *
4. p = getPrime(1024)
5. q = getPrime(1024)
7. N = p*p*q
9. d= inverse(N, (p-1)*(q-1)//GCD(p-1, q-1))
11. m = bytes_to_long(flag)
13. c = pow(m, N, N)
15. print('c =', c)
16. print('N =', N)
17. print('d =', d)
19. # c = 1653396627113549535760516503668455111392369905404419847336187180051939350514408518095369852411718553340156505246372037811032919080426885042549723125598742783778413642221563616358386699697645814225855089454045984443096447166740882693228043505960011332616740785976743150624114653594631779427044055729185392854961786323215146318588164139423925400772680226861699990332420246447180631417523181196631188540323779487858453719444807515638025771586275969579201806909799448813112034867089866513864971414742370516244653259347267231436131850871346106316007958256749016599758599549180907260093080500469394473142003147643172770078092713912200110043214435078277125844112816260967490086038358669788006182833272351526796228536135638071670829206746835346784997437044707950580087067666459222916040902038574157577881880027391425763503693184264104932693985833980182986816664377018507487697769866530103927375926578569947076633923873193100147751463
20. # N = 1768427447158131856514034889456397424027937796617829756303525705316152314769129050888899742667986532346611229157207778487065194513722005516611969754197481310330149721054855689646133721600838194741123290410384315980339516947257172981002480414254023253269098539962527834174781356657779988761754582343096332391763560921491414520707112852896782970123018263505426447126195645371941116395659369152654368118569516482251442513192892626222576419747048343942947570016045016127917578272819812760632788343321742583353340158009324794626006731057267603803701663256706597904789047060978427573361035171008822467120148227698893238773305320215769410594974360573727150122036666987718934166622785421464647946084162895084248352643721808444370307254417501852264572985908550839933862563001186477021313236113690793843893640190378131373214104044465633483953616402680853776480712599669132572907096151664916118185486737463253559093537311036517461749439
21. # d = 20650646933118544225095544552373007455928574480175801658168105227037950105642248948645762488881219576174131624593293487325329703919313156659700002234392400636474610143032745113473842675857323774566945229148664969659797779146488402588937762391470971617163496433008501858907585683428652637958844902909796849080799141999490231877378863244093900363251415972834146031490928923962271054053278056347181254936750536280638321211545167520935870220829786490686826062142415755063724639110568511969041175019898031990455911525941036727091961083201123910761290998968240338217895275414072475701909497518616112236380389851984377079

复制代码

2、解题方法
学了一个新技巧，哈哈哈。
简介：
Schmidt-Samoa密码系统，像rabin加密一样，其安全性基于整数因式分解的难度。但 Rabin 解密时会得到四个解，而 Schmidt-Samor 得到的是唯一解。
密钥生成
1.选取两个大的质数p和q并进行计算 N = p **2*q
2. 计算 d = i n v e r t ( N , φ ( p q ) )
加密
对消息m，计算密文 C = m **N  m o d  N
解密
计算明文 m=C**d   m o d   p*q
举例：

验证：

关于获取pq的问题

所以：

所以：

例题：

1. from Crypto.Util.number import *
3. def generkey(k):
4.         p, q = getPrime(k), getPrime(k)
5.         pubkey = p**2 * q
6.         n = pubkey
7.         l = (p-1)*(q-1) / gcd(p-1, q-1)
8.         privkey = inverse(n, l)
9.         return pubkey, privkey
11. def encrypt(m, pubkey):
12.         return pow(bytes_to_long(m), pubkey, pubkey)
15. # pubkey =  2188967977749378274223515689363599801320698247938997135947965550196681836543275429767581633044354412195352229175764784503562989045268075431206876726265968368605210824232207290410773979606662689866265612797103853982014198455433380266671856355564273196151136025319624636805659505233975208570409914054916955097594873702395812044506205943671404203774360656553350987491558491176962018842708476009578127303566834534914605109859995649555122751891647040448980718882755855420324482466559223748065037520788159654436293431470164057490350841209872489538460060216015196875136927502162027562546316560342464968237957692873588796640619530455268367136243313422579857823529592167101260779382665832380054690727358197646512896661216090677033395209196007249594394515130315041760988292009930675192749010228592156047159029095406021812884258810889225617544404799863903982758961208187042972047819358256866346758337277473016068375206319837317222523597
16. # privkey = 1430375790065574721602196196929651174572674429040725535698217207301881161695296519567051246290199551982286327831985649037584885137134580625982555634409225551121712376849579015320947279716204424716566222721338735256648873164510429206991141648646869378141312253135997851908862030990576004173514556541317395106924370019574216894560447817319669690140544728277302043783163888037836675290468320723215759693903569878293475447370766682477726453262771004872749335257953507469109966448126634101604029506006038527612917418016783711729800719387298398848370079742790126047329182349899824258355003200173612567191747851669220766603
17. # enc = 1491421391364871767357931639710394622399451019824572362288458431186299231664459957755422474433520889084351841298056066100216440853409346006657723086501921816381226292526490195810903459483318275931326433052468863850690793659405367902593999395060606972100169925074005992478583035226026829214443008941631771292291305226470216430735050944285543542354459162474346521327649934512511202470099020668235115245819634762067338432916012664452035696422865651002305445711778476072004708256200872226475346448360491248823843688268126341094612981308791499434770936360676087490303951728563482686307164877000300082742316368597958297217061375140696272398140310043942637287763946305961019518639745426370821124559939597559475362769382796386720030343305889701616194279058139516811941262747298761646317383112470923295543635754747288259324745583689440061956478083777663996487389553238481759103908588004219390662578446313004404784835263543083088327198

复制代码

解题EXP：

1. from gmpy2 import*
2. from libnum import*
4. N =  2188967977749378274223515689363599801320698247938997135947965550196681836543275429767581633044354412195352229175764784503562989045268075431206876726265968368605210824232207290410773979606662689866265612797103853982014198455433380266671856355564273196151136025319624636805659505233975208570409914054916955097594873702395812044506205943671404203774360656553350987491558491176962018842708476009578127303566834534914605109859995649555122751891647040448980718882755855420324482466559223748065037520788159654436293431470164057490350841209872489538460060216015196875136927502162027562546316560342464968237957692873588796640619530455268367136243313422579857823529592167101260779382665832380054690727358197646512896661216090677033395209196007249594394515130315041760988292009930675192749010228592156047159029095406021812884258810889225617544404799863903982758961208187042972047819358256866346758337277473016068375206319837317222523597
5. #N = p^2*q
6. d = 1430375790065574721602196196929651174572674429040725535698217207301881161695296519567051246290199551982286327831985649037584885137134580625982555634409225551121712376849579015320947279716204424716566222721338735256648873164510429206991141648646869378141312253135997851908862030990576004173514556541317395106924370019574216894560447817319669690140544728277302043783163888037836675290468320723215759693903569878293475447370766682477726453262771004872749335257953507469109966448126634101604029506006038527612917418016783711729800719387298398848370079742790126047329182349899824258355003200173612567191747851669220766603
7. c = 1491421391364871767357931639710394622399451019824572362288458431186299231664459957755422474433520889084351841298056066100216440853409346006657723086501921816381226292526490195810903459483318275931326433052468863850690793659405367902593999395060606972100169925074005992478583035226026829214443008941631771292291305226470216430735050944285543542354459162474346521327649934512511202470099020668235115245819634762067338432916012664452035696422865651002305445711778476072004708256200872226475346448360491248823843688268126341094612981308791499434770936360676087490303951728563482686307164877000300082742316368597958297217061375140696272398140310043942637287763946305961019518639745426370821124559939597559475362769382796386720030343305889701616194279058139516811941262747298761646317383112470923295543635754747288259324745583689440061956478083777663996487389553238481759103908588004219390662578446313004404784835263543083088327198
9. pq = gcd(pow(2,d*N,N)-2,N)
11. m = pow(c,d,pq)
12. print(n2s(m))
13. #flag{61e19444-7afb-11e9-b704-4ccc6adfc6f0}

复制代码

因此，话说回来，本题exp也就有了。哈哈哈.....嗝！！

1. from gmpy2 import*
2. from libnum import*
4. N = 1768427447158131856514034889456397424027937796617829756303525705316152314769129050888899742667986532346611229157207778487065194513722005516611969754197481310330149721054855689646133721600838194741123290410384315980339516947257172981002480414254023253269098539962527834174781356657779988761754582343096332391763560921491414520707112852896782970123018263505426447126195645371941116395659369152654368118569516482251442513192892626222576419747048343942947570016045016127917578272819812760632788343321742583353340158009324794626006731057267603803701663256706597904789047060978427573361035171008822467120148227698893238773305320215769410594974360573727150122036666987718934166622785421464647946084162895084248352643721808444370307254417501852264572985908550839933862563001186477021313236113690793843893640190378131373214104044465633483953616402680853776480712599669132572907096151664916118185486737463253559093537311036517461749439
5. #N = p^2*q
6. c = 1653396627113549535760516503668455111392369905404419847336187180051939350514408518095369852411718553340156505246372037811032919080426885042549723125598742783778413642221563616358386699697645814225855089454045984443096447166740882693228043505960011332616740785976743150624114653594631779427044055729185392854961786323215146318588164139423925400772680226861699990332420246447180631417523181196631188540323779487858453719444807515638025771586275969579201806909799448813112034867089866513864971414742370516244653259347267231436131850871346106316007958256749016599758599549180907260093080500469394473142003147643172770078092713912200110043214435078277125844112816260967490086038358669788006182833272351526796228536135638071670829206746835346784997437044707950580087067666459222916040902038574157577881880027391425763503693184264104932693985833980182986816664377018507487697769866530103927375926578569947076633923873193100147751463
7. d = 20650646933118544225095544552373007455928574480175801658168105227037950105642248948645762488881219576174131624593293487325329703919313156659700002234392400636474610143032745113473842675857323774566945229148664969659797779146488402588937762391470971617163496433008501858907585683428652637958844902909796849080799141999490231877378863244093900363251415972834146031490928923962271054053278056347181254936750536280638321211545167520935870220829786490686826062142415755063724639110568511969041175019898031990455911525941036727091961083201123910761290998968240338217895275414072475701909497518616112236380389851984377079
9. pq = gcd(pow(2,d*N,N)-2,N)
11. m = pow(c,d,pq)
12. print(n2s(m))
13. #flag{l3arn_s0m3_e1ement4ry_numb3r_the0ry}

复制代码

Smart

1、题目信息
提示：一个解决ECDLP的好方法

1. from Crypto.Util.number import *
2. from sage.all import *
3. from secret import flag
5. p = 75206427479775622966537995406541077245842499523456803092204668034148875719001
6. a = 40399280641537685263236367744605671534251002649301968428998107181223348036480
7. b = 34830673418515139976377184302022321848201537906033092355749226925568830384464
9. E = EllipticCurve(GF(p), [a, b])
11. d = bytes_to_long(flag)
13. G = E.random_element()
15. P = d * G
17. print(G)
18. print(P)
20. # (63199291976729017585116731422181573663076311513240158412108878460234764025898 : 11977959928854309700611217102917186587242105343137383979364679606977824228558 : 1)
21. # (75017275378438543246214954287362349176908042127439117734318700769768512624429 : 39521483276009738115474714281626894361123804837783117725653243818498259351984 : 1)

复制代码

2、解题方法
Smart’s attack
适用情况：E.order() = p。
参考：https://lazzzaro.github.io/2020/11/07/crypto-ECC/
exp:

1. #sage
2. p = 75206427479775622966537995406541077245842499523456803092204668034148875719001
3. A = 40399280641537685263236367744605671534251002649301968428998107181223348036480
4. B = 34830673418515139976377184302022321848201537906033092355749226925568830384464
5. E = EllipticCurve(GF(p),[A,B])
6. Q = E(75017275378438543246214954287362349176908042127439117734318700769768512624429,39521483276009738115474714281626894361123804837783117725653243818498259351984)
7. P = E(63199291976729017585116731422181573663076311513240158412108878460234764025898,11977959928854309700611217102917186587242105343137383979364679606977824228558)
8. def SmartAttack(P,Q,p):
9.     E = P.curve()
10.     Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])
12.     P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
13.     for P_Qp in P_Qps:
14.         if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
15.             break
17.     Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
18.     for Q_Qp in Q_Qps:
19.         if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
20.             break
22.     p_times_P = p*P_Qp
23.     p_times_Q = p*Q_Qp
25.     x_P,y_P = p_times_P.xy()
26.     x_Q,y_Q = p_times_Q.xy()
28.     phi_P = -(x_P/y_P)
29.     phi_Q = -(x_Q/y_Q)
30.     k = phi_Q/phi_P
31.     return ZZ(k)
33. r = SmartAttack(P, Q, p)
34. print(r)
35. #706900059475062772067312229965334421909675651947459433421022963709731965

复制代码

[code]from Crypto.Util.number import long_to_bytesm = 706900059475062772067312229965334421909675651947459433421022963709731965print('
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！