ToB企服应用市场:ToB评测及商务社交产业平台

标题: 2024SHCTF--Crypto--Week1&Week2--WP [打印本页]
作者: 魏晓东    时间: 2024-11-4 09:41
标题: 2024SHCTF--Crypto--Week1&Week2--WP
2024SHCTF

注：针对2024SHCTF赛事，写下自己的解题思绪以及个别赛题赛后复现对于标题而产生的理解。
Week1

d_known

task:
  1. from Crypto.Util.number import *
  2. from gmpy2 import*
  3. from flag import flag
  5. m = bytes_to_long(flag)
  6. p = getPrime(1024)
  7. q = next_prime(p)
  8. n = p * q
  9. e = 0x10001
  10. d = inverse(e, (p-1) * (q-1))
  11. c = pow(m, e, n)
  12. print(c)
  13. print(d)
  15. '''
  16. c = 2023280206852799756188533543726445899210461674882103741449846207085209158128274530066961712554168490693338804965645257201915901430270289914927031884869765066207700835767543832965446328994297771171239554854439801951855734405930228978819264617926307331498279823792404896708489491845814993901912406921233209174052585982422702902921150509799525025006961668679058706680338445147732742087594370544143929344692878849762859325278353499113047627166145064375388330723568647380571912097704007649949039872655521965438358883046062395057460962164069910080794938688401346483471199715397419486956888803799635787660289917216321436075
  17. d = 5325557477974651131933634251521791991925782269036709550928544143247135213750451805876289560548176503358408907072006083232605644148148348426759760165848721826856045819883560475601424759644170039021289236399016340754732526066778542800516887549418899285710399950124543460448926261999153088331976259647327700619342183115011084680629309966651674276478502656272680143227400879298842573111724783827297704483713490258469730037991356794901334012297158591206594636469676973210545148034611453362521846968132369356368152162040634155912080095620977164991291750678677808423018575966921693161165571968455135962605729487885568490033
  18. '''
复制代码
analysis:
已知d,

\[ed≡1(mod\ \ phi)=>ed-1≡0(mod\ \ phi)=>ed-1 = k*phi\]
e.bit_length = 17;d.bit_length = 2046;phi.bit_length≈2048，所以可以大致推出k的位数,爆破求出phi
然后求出p,q，q = next_prime(p)，p,q接近，直接对phi开方然后用next_prime,prevprime即可求解p,q
tqdm: tqdm是一个快速、扩展性很强的Python库，用于在长循环中添加一个进度提示信息，能够给用户一个直接的反馈。range-->trange
exp:
  1. from Crypto.Util.number import *
  2. from sympy import *
  3. from gmpy2 import *
  4. from tqdm import *
  5. c = 2023280206852799756188533543726445899210461674882103741449846207085209158128274530066961712554168490693338804965645257201915901430270289914927031884869765066207700835767543832965446328994297771171239554854439801951855734405930228978819264617926307331498279823792404896708489491845814993901912406921233209174052585982422702902921150509799525025006961668679058706680338445147732742087594370544143929344692878849762859325278353499113047627166145064375388330723568647380571912097704007649949039872655521965438358883046062395057460962164069910080794938688401346483471199715397419486956888803799635787660289917216321436075
  6. d = 5325557477974651131933634251521791991925782269036709550928544143247135213750451805876289560548176503358408907072006083232605644148148348426759760165848721826856045819883560475601424759644170039021289236399016340754732526066778542800516887549418899285710399950124543460448926261999153088331976259647327700619342183115011084680629309966651674276478502656272680143227400879298842573111724783827297704483713490258469730037991356794901334012297158591206594636469676973210545148034611453362521846968132369356368152162040634155912080095620977164991291750678677808423018575966921693161165571968455135962605729487885568490033
  7. e = 65537
  8. kphi = e*d - 1
  9. for k in trange(2**13,2**17):
  10.     if kphi % k == 0:
  11.         phi = kphi // k
  12.         p = next_prime(iroot(phi,2)[0])
  13.         q = prevprime(iroot(phi,2)[0])
  14.         if d == inverse(e,(p-1)*(q-1)):
  15.             m = pow(c,d,p*q)
  16.             print(long_to_bytes(m))
  17. # SHCTF{53398660-8e40-460d-9f28-2b25b687fbe9}
复制代码
baby_mod

task:
  1. from Crypto.Util.number import *
  2. from enc import flag
  4. m = bytes_to_long(flag)
  5. p = getPrime(512)
  6. q = getPrime(512)
  7. r = getPrime(777)
  8. t = getPrime(777)
  9. tmp = getPrime(15)
  10. e = 65537
  11. n = p*q
  12. print(f"c = {pow(m,e,n)}")
  13. print(f"leak = {p*r-q*t-tmp}")
  14. print(f"r = {r}")
  15. print(f"t = {t}")
  16. '''
  17. c = 17937472553998606504669747140789726307439582196963451030969242254157949062129324494114590658920012871180079814675678946453897865233224992985089451278231663618857965418389487647355253063941790618808955858162224234190981820557457655720791346278352310012094147015720264246236621546172323951815149898363856098823
  18. leak = -1587213174398707503036319512989790705844433773053364648490744871188009448006267321887626866013134130998268382756317172409049882250682995546076129821312371197174231288418315516151931068209717088211878340641266286735555866264605212381502721300165430517113230358235888004114974340620550567298211707561178407907225299235498063377164047589836058708230195966901891786125922264824283899806368097
  19. r = 466415729162296733529092458774194130369566652709805609481844599849536821250812719015532685709318199315612306114406654748660375049578603355246845205423401652241172615507957208288364106021726317326899229799053280291178121413651628535023
  20. t = 635316670184189895492730019113841833333699743242997516619486647136468690062607793643684031305893867906907074562340028701514502349937069085426784869269608878466785830130266100418807129895963018317044053909910919832387196116916663544813
  21. '''
复制代码
analysis:

\[leak = pr-qt-tmp\\leak+tmp=pr-qt\\leak+tmp≡pr(mod\ \ t)\]
此时有r,t,leak也就是说tmp确定时我们即可使用(leak+tmp)*inverse(r,t)%t求解p。
exp:
  1. from Crypto.Util.number import *
  3. # Given values
  4. e = 65537
  5. c = 17937472553998606504669747140789726307439582196963451030969242254157949062129324494114590658920012871180079814675678946453897865233224992985089451278231663618857965418389487647355253063941790618808955858162224234190981820557457655720791346278352310012094147015720264246236621546172323951815149898363856098823
  6. leak = -1587213174398707503036319512989790705844433773053364648490744871188009448006267321887626866013134130998268382756317172409049882250682995546076129821312371197174231288418315516151931068209717088211878340641266286735555866264605212381502721300165430517113230358235888004114974340620550567298211707561178407907225299235498063377164047589836058708230195966901891786125922264824283899806368097
  7. r = 466415729162296733529092458774194130369566652709805609481844599849536821250812719015532685709318199315612306114406654748660375049578603355246845205423401652241172615507957208288364106021726317326899229799053280291178121413651628535023
  8. t = 635316670184189895492730019113841833333699743242997516619486647136468690062607793643684031305893867906907074562340028701514502349937069085426784869269608878466785830130266100418807129895963018317044053909910919832387196116916663544813
  9. for temp in range(2**14,2**15):
  10.     if isPrime(temp):
  11.         p = (leak + temp) * inverse(r, t) % t
  12.         if isPrime(p):
  13.             q = (p * r - leak - temp) // t
  14.             if isPrime(q):
  15.                 phi = (p - 1) * (q - 1)
  16.                 d = inverse(e, phi)
  17.                 m = pow(c, d, p * q)
  18.                 flag = long_to_bytes(m)
  19.                 print(flag)
  20.                 break
  21. # SHCTF{0055b9ad-d96a-4d43-a9a9-28ecb08d557e}
复制代码
Week2

worde很大

task:
  1. import gmpy2
  2. from Crypto.Util.number import *
  3. from enc import flag
  5. m = bytes_to_long(flag)
  6. p = getPrime(512)
  7. q = getPrime(512)
  8. n = p*q
  9. e = getPrime(200)
  10. d = gmpy2.invert(e,(p-1)*(q-1))
  11. dp = d % (p-1)
  12. c = pow(m,e,n)
  14. print(f"n = {n}")
  15. print(f"c = {c}")
  16. print(f"e = {e}")
  17. print(f"dp = {dp}")
  18. '''
  19. n = 107032957087630288996268413289950221007178661091952415803799204807322719946773789072727097283876411371451855146945178785099365053975022744275499071412639566826876925607457076160736517239727314406122177641305989161650710675377046111659861132320470194374212535258339049977749925125713806268856103059658246838823
  20. c = 13426059268971299890058502967962382039319233826881681062400371816555313938352978412770129453032021159626652883952418968332266876616888219630681123569091893928354304104629165208088101777538952907693381585125393549212184411084081938892612243511190758716729464349148805390375073663394447190303250531328411306179
  21. e = 940179304603814149880259136688231799983345424885109815443153
  22. dp = 1389519949170420652498985591042020010547189625918115450421402099250611740108790835840554944891132491698692658805867305372374541674726218271082297905819817
  23. '''
复制代码
analysis:
dp泄露，但是e很大，使用费马小定理可以求出p

\[d_p≡d(mod\quad(p-1))\\ed≡1(mod(\ \ (p-1)(q-1)))\\由性质戊：\\若a_1≡b_1(mod\ \  m),a_2≡b_2(mod\ \  m),则\\a_1a_2≡b_1b_2(mod \ \ m)\\特别地,若a≡b(mod\ \ m),则ak≡bk(mod\ \ m)\\ed_p≡ed(mod\ \ (p-1))\\\forall mm,p) = 1;m^{ed_p}(mod\ \ n)≡m^{ed(mod\ \ (p-1))}(mod\ \ p)\\m^{ed_p}(mod\ \ n)≡m^{1+k(p-1)}(mod\ \ p)\\由费马小定理:a^{p-1}≡1(mod\ \ p)=>a^p≡a(mod\ \ p)\\m^{1+k(p-1)}≡m(mod\ \ p)\\m^{ed_p}(mod\ \ n)≡m(mod\ \ p)=>m^{ed_p}(mod\ \ n)-m≡0(mod\ \ p)\\又∵n = p*q.则m^{ed_p}(mod \ \ n) - m与n存在最大公因数p.\\\forall mm,p)=1,满意p=gcd(m^{ed_p}(mod\ \ n)-m,n),m∈(1,p)\]
exp:
  1. from Crypto.Util.number import *
  2. n = 107032957087630288996268413289950221007178661091952415803799204807322719946773789072727097283876411371451855146945178785099365053975022744275499071412639566826876925607457076160736517239727314406122177641305989161650710675377046111659861132320470194374212535258339049977749925125713806268856103059658246838823
  3. c = 13426059268971299890058502967962382039319233826881681062400371816555313938352978412770129453032021159626652883952418968332266876616888219630681123569091893928354304104629165208088101777538952907693381585125393549212184411084081938892612243511190758716729464349148805390375073663394447190303250531328411306179
  4. e = 940179304603814149880259136688231799983345424885109815443153
  5. dp = 1389519949170420652498985591042020010547189625918115450421402099250611740108790835840554944891132491698692658805867305372374541674726218271082297905819817
  6. p = GCD(pow(5,e*dp,n)-5,n)
  7. q = n // p
  8. phi_n = (p-1) * (q-1)
  9. d = inverse(e,phi_n)
  10. m = pow(c,d,n)
  11. flag = long_to_bytes(m)
  12. print(flag)
  13. #SHCTF{worD_E_YOU_d1aN_DA_EA7zaA}
复制代码
pading

task:
  1. from Crypto.Util.number import *
  2. import gmpy2
  3. flag = b'SHCTF{********}'
  4. assert len(flag) == 39
  5. p = getPrime(512)
  6. q = getPrime(512)
  7. n = p * q
  8. e = 0x3
  9. pad = b'a_easy_problem'
  10. c = pow(bytes_to_long(flag + pad),e,n)
  11. print(f'n = {n}')
  12. print(f'c = {c}')
  13. '''
  14. n = 75098630616111482769180659620329958045667354926061075208260621193990567410087157843957397740063249813712091785246064471170031967563730722416238514564741845799209165882736179507743810974327683565208643579519017836211681069084365442156637269419638211790587926949896791807497864162801395061736248644788921667789
  15. c = 3638646373008661843144668651345881752890064263891078270562520797735374345440840522319031089914051142881157757879267055752918804376422359639737717683576378097238618841707519724197204326012840131370755503486240820145945437287578597232976614322766435861623599998349726858207129492804638826767780589762299083258
  16. '''
复制代码
analysis:
此题对于flag+pad进行加密，小e，并且已知pad，隶属于高位攻击，使用coppersmith算法求解。
flag的二进制位时39*8=312，e次方之后是312*3=936而n的位数是1024，312的flag相对于1024的n来说是小值，可用coppersmith的方法求解。
beta的值依据912/1024=0.89取整0.8，epslilon逐步放小。对于多项式的方程而言
现有一个e阶的多项式f，那么可以：f =

\[b≥n^β,(0≤β≤)\]
2.在模n意义下，快速求出

\[n^{β^2 \over e}\]
coppersmith: 在RSA中，高位攻击，已知部门二进制位，通过coppersmith定理（里面应用了LLL算法）求剩余二进制位。p,q位数一致时，unkown_bits/p_bits≤0.44.sagemath中的small_roots(X=  ,beta=  ),beta选在0.4.
small_roots: 使用small_roots时，多设一个参数epsilon，让里面构造的格大一点，就可以不用爆破直接出结果了,epsilon越小，造出来的格越大。在不设置的情况下默以为beta/8，这里就是0.4*8=0.05，这样跑不出来结果，就可以实验缩小epsilon的值，可以通过逐步减小的值来求解答案epsilon=0.026就可以出结果。当epslion过小时，格过大，LLL算法会非常耗时，这里测试epsilon=0.01就需要一点时间了。所以一般取0.01左右出不来，就得思量方法问题了。
exp:
  1. from Crypto.Util.number import *
  3. n = 75098630616111482769180659620329958045667354926061075208260621193990567410087157843957397740063249813712091785246064471170031967563730722416238514564741845799209165882736179507743810974327683565208643579519017836211681069084365442156637269419638211790587926949896791807497864162801395061736248644788921667789
  4. c = 3638646373008661843144668651345881752890064263891078270562520797735374345440840522319031089914051142881157757879267055752918804376422359639737717683576378097238618841707519724197204326012840131370755503486240820145945437287578597232976614322766435861623599998349726858207129492804638826767780589762299083258
  5. e=3
  7. pre=b'SHCTF{'
  8. suf=b'}a_easy_problem'
  10. flag_length=39
  11. # 去除高位，即SHCTF{
  12. pre_bits=(flag_length+len(suf)-1-len(pre))*8
  13. # 计算后面已知明文的bits
  14. suf_bits=len(suf)*8
  15. # 计算未知的bits
  16. unknown_bits=(flag_length-len(pre)-1)*8
  18. PR.<x> = PolynomialRing(Zmod(n))
  19. # f = m^e-c
  20. # x即unknown的部分
  21. # bytes_to_long(a+b)≠bytes_to_long(a)+bytes_to_long(b);bytes_to_long(a+b)=bytes_to_long(a)*2^(len(a)*8)
  22. f=(bytes_to_long(pre)*2^pre_bits+x*2^suf_bits+bytes_to_long(suf))^e-c
  23. f=f.monic()
  24. m=f.small_roots(X=2^unknown_bits,beta=0.4,epsilon=0.026)
  25. if m:
  26.     x=m[0]
  27.     flag=pre+long_to_bytes(int(x))+suf
  28.     print(flag)
  29. #b'SHCTF{4RE_yOu_PaDddln9_mE_8oY_EIz66G45}a_easy_problem'
复制代码
ezECC
  1. from Crypto.Util.number import *
  2. from flag import flag
  4. assert flag.startswith(b'SHCTF{')
  6. m = next_prime(bytes_to_long(flag))
  7. p = getPrime(512)
  8. a,b = getPrime(128),getPrime(128)
  9. E = EllipticCurve(Zmod(p),[a,b])
  10. k = getPrime(256)
  11. A1 = E.random_point()
  12. A2 = A1*k
  13. M = E.lift_x(m)
  14. C = M+A2
  16. print('p = ',p)
  17. print('k = ',k)
  18. print('A1 = ',A1)
  19. print('C = ',C)
复制代码
data:
  1. p =  9799485259524549113003780400336995829253375211044694607315372450399356814285244762186468904824132005209991983177601498069896166228214442123763065076327679
  2. k =  73771953838487511457389800773038323262861649769228176071578897500004883270121
  3. A1 =  (5945412329827707694132352090606154232045921322662767755331097180167148601629747751274580872108985870208681845078153424348847330421799769770041805208089791 : 4113102573821904570542216004200810877456931033522276527318388416329888348077285857968081007666714313806776668203284797556825595791189566621228705928598709 : 1)
  4. C = (2336301464307188733995312208152021176388718095735565422234047912672553316288080052957448196669174030921526180747767251838308335308474037066343018337141276 : 6868888273736103386336636953449998615833854869329393895956720058438723636197866928342387693671211918574357564701700555086194574821628053750572619551290025 : 1)
复制代码
analysis:
已知A1和C两个在曲线上地点和曲线地p值，根据曲线

\[y^2=x^3+ax+b(mod\ \ p)\]
两个式子相减求得a和b.构造曲线，由于C=M+A2，且A2=kA1,A1和k的值都已知。M=C-kA1求得M的值，由于M的x坐标是明文m的下一个素数，爆破即可。
点的处理: 对于标题给出数据的点，我们要进行修改，因为sagemath中的点要求(x,y)而非(x:y:1)
遗留问题: sympy中的prevprime函数的使用方法。
exp:
  1. from Crypto.Util.number import *
  3. p =  9799485259524549113003780400336995829253375211044694607315372450399356814285244762186468904824132005209991983177601498069896166228214442123763065076327679
  4. k =  73771953838487511457389800773038323262861649769228176071578897500004883270121
  5. A1 =  (5945412329827707694132352090606154232045921322662767755331097180167148601629747751274580872108985870208681845078153424348847330421799769770041805208089791 , 4113102573821904570542216004200810877456931033522276527318388416329888348077285857968081007666714313806776668203284797556825595791189566621228705928598709 )
  6. C = (2336301464307188733995312208152021176388718095735565422234047912672553316288080052957448196669174030921526180747767251838308335308474037066343018337141276 , 6868888273736103386336636953449998615833854869329393895956720058438723636197866928342387693671211918574357564701700555086194574821628053750572619551290025 )
  8. a = inverse(A1[0]-C[0],p)*((A1[1]**2-A1[0]**3)-(C[1]**2-C[0]**3))% p
  9. b = (C[1]**2-C[0]**3-a*C[0])%p
  11. E = EllipticCurve(Zmod(p),[a,b])
  12. A1 = E(A1)
  13. C = E(C)
  14. M = C-k*A1
  16. mm = (M.xy())[0]
  17. for i in range(292):
  18.     m = long_to_bytes(int(mm-i))
  19.     if m.endswith(b'}'):
  20.         print(m)
复制代码
魔鬼的步伐

task:
  1.       
  2. from Crypto.Util.number import *
  3. from random import choice
  4. from enc import flag
  6. m = bytes_to_long(flag)
  7. def get_primes(limit):
  8.     primes = []
  9.     is_prime = [True] * (limit + 1)
  10.     for num in range(2, limit + 1):
  11.         if is_prime[num]:
  12.             primes.append(num)
  13.             for multiple in range(num * num, limit + 1, num):
  14.                 is_prime[multiple] = False
  15.     return primes
  17. def get_Prime(bits):
  18.     while True:
  19.         n = 2
  20.         while n.bit_length() < bits:
  21.             n *= choice(primes)
  22.         if isPrime(n + 1):
  23.             return n + 1
  25. e = 65537
  26. primes = get_primes(e)
  27. p = get_Prime(512)
  28. q = get_Prime(512)
  29. n = p*q
  30. c = pow(m,e,n)
  31. print(f"n = {n}")
  32. print(f"e = {e}")
  33. print(f"c = {c}")
  34. '''
  35. n = 779579301738188606639541475585479048662338414978423162511086618350581959037809676355175033940672838358216296034989613684765924879020007985463372880378958453235938149726732804842653385407460552866449233717559756619739481517089434393605029261842182116054349584175198599481092380973944251651872382058614325364639417
  36. e = 65537
  37. c = 547032040563518540116157223879027303340872416038133089003193905244978422560735616179910978730578423924420033057963791332760379132346877909806353927165538096867865399527460216074519919572776729647581400118345644864260152466704275743378828075020134070702051989890847762735538767329450466068109132805742740564390842
  38. '''
复制代码
analysis:
欧拉函数φ(n): 给定一个正整数 n，欧拉函数就是求在 [1,n) 区间上，与 n互质的整数的个数。举例来说，设m = 8，则与8互质的正整数聚集A={1, 3, 5, 7}，此聚集共有4个元素，所以 φ ( 8 ) = 4。

\[\forall n\in \mathbb{N^+},φ(n)=∣A∣,whereA=\{m|1≤m≤n,(m,n)=1\}\\|S|表示聚集S中的元素个数\]
欧拉定理: 对恣意两个正整数 a , n ，若两者互素，则：对比费马小定理，实际上就是欧拉定理的特殊情况。

\[a^{φ(n)}≡1(mod\ \ n)=>a^{kφ(n)}=(a^{φ(n)})^k≡1^k≡1(mod\ \ n)\]
所以只要指数是模数n的欧拉函数的倍数，在模n下就等于1.
对于本题中的情况：

\[p = p_1p_2\cdots p_s+1;q=q_1q_2\cdots q_t+1\\φ(p)=p_1p_2\cdots p_s;φ(q)=q_1q_2\cdots q_t\\n = pq;φ(n)=p_1p_2\cdots p_sq_1q_2\cdots q_t\\所以只需要遍历get\_primes()得到的素数表就可以得到数a的计算指数.\\得，a^{k*φ(n)}≡1(mod\ \ n)\\a^{k*φ(n)}-1≡0(mod\ \ p)=>gcd(a^{k*φ(n)}-1,n)=p\]
求解φ(n)即可。
exp:
  1. from Crypto.Util.number import *
  2. # Given values
  3. n = 779579301738188606639541475585479048662338414978423162511086618350581959037809676355175033940672838358216296034989613684765924879020007985463372880378958453235938149726732804842653385407460552866449233717559756619739481517089434393605029261842182116054349584175198599481092380973944251651872382058614325364639417
  4. e = 65537
  5. c = 547032040563518540116157223879027303340872416038133089003193905244978422560735616179910978730578423924420033057963791332760379132346877909806353927165538096867865399527460216074519919572776729647581400118345644864260152466704275743378828075020134070702051989890847762735538767329450466068109132805742740564390842
  7. # 初始化生成光滑数的列表get_primes(e)
  8. def get_primes(limit):
  9.     primes = []
  10.     is_prime = [True] * (limit + 1)
  11.     for num in range(2, limit + 1):
  12.         if is_prime[num]:
  13.             primes.append(num)
  14.             for multiple in range(num * num, limit + 1, num):
  15.                 is_prime[multiple] = False
  16.     return primes
  17. # 由于n = p * q ,而p,q分别由一个get_primes生成，所以最终n的列表应该是2*get_primes(e)
  18. primes_value = get_primes(e) + get_primes(e)
  20. # 求解φ(n)
  21. def Solve(n):
  22.     counter = 0
  23.     for p in primes_value:
  24.         if n % p == 0:
  25.             counter += 1
  26.     return n - counter - 2  # 减去1和n的两种情况
  27. # 取素数2当作最初的a，在φ(n)的范围内不断增大指数寻找GCD(a^{k*φ(n)}-1,n) != 0和 != n
  28. a = 2
  29. for _ in range(2,Solve(n)):
  30.     a = pow(a,_,n)
  31.     p = GCD(a-1,n)
  32.     if p !=1 and p != n:
  33.         q = n // p
  34.         break
  35. phi_n = (p-1)*(q-1)
  36. d = inverse(e,phi_n)
  37. flag = long_to_bytes(pow(c,d,n))
  38. print(flag)
  39. #SHCTF{1rlCTioN_is_ThE_d3vils_st3P_4s}
复制代码
E&R

task:
  1. #sage
  2. from Crypto.Util.number import *
  3. from secret import flag
  5. flag = flag[6:-1]
  6. l = len(flag)
  7. m1 = bytes_to_long(flag[:l//2])
  8. m2 = bytes_to_long(flag[l//2:])
  9. #RSA
  10. p = getPrime(256)
  11. q = getPrime(256)
  12. n = p * q
  13. e = 65537
  14. r_q = int(bin(q)[2:][::-1] , 2)
  15. leak = p ^ r_q
  16. c = pow(m2,e,n)
  18. #ECC
  19. E = EllipticCurve(Zmod(n),[114514,1919810])
  20. G = E.lift_x(Integer(m1))
  21. P = G * e
  22. print(f'leak = {leak}')
  23. print(f'n = {n}')
  24. print(f'c = {c}')
  25. print(f'P = {P}')
  26. # leak = 5599968251197363876087002284371721787318931284225671549507477934076746561842
  27. # n = 7120275986401660066259983193598830554385933355254283093021239164350142898387660104515624591378875067038235085428170557400012848874756868985306042421950909
  28. # c = 6803450117490196163076010186755045681029929816618361161925865477601994608941714788803007124967390157378525581080320415602012078322064392991884070073083436
  29. # P = (4143131125485719352848137000299706175276016714942734255688381872061184989156686585992844083387698688432978380177564346382756951426943827434190895490233627 : 3879946878859691332371384275396678851932267609535096278038417524609690721322205780110680003522999409696718745532857001461869452116434787256032366267905519 : 1)
复制代码
analysis:
Crypto趣题-剪枝
剪枝: 剪枝是对于树算法类的标题而言的，通过减去已经计算后的树的枝点来缩短算法的时间复杂度。而在这里则是同时找到p和q高位或低位，要是只找p高位和q低位，爆破条件无法判断，这就是为什么这题需要同时用到pxorq的两端.
剪枝已知条件: p 与 q 的反方向二进制的异或值，共256bit，记为p_xor_q
剪枝搜索方式: 1.从两端向中心搜索                                                                                                                                                                                        2. 每一次搜索，需使用当前 pxorq 两端的bit位。这是因为，pxorq 的当前最高位对应p的最高位及q的最低位，pxorq 的当前最低位对应p的最低位及q的最高位 (其中最高、最低均是对于当前搜索而言)                                                                                                                                                                                             3.如果当前需搜索的最高位为”1”，则对应两种大概：p该位为1，q对应低位为0；p该位为0，q对应低位为1。剩下依此类推
剪枝条件: 将p、q未搜索到的位全填0，乘积应小于n                                                                                                                                                                     将p、q未搜索到的位全填1，乘积应大于n                                                                                                                                                                                               p、q 低 k 位乘积再取低 k 位，应与 n 的低 k 位类似
exp:
第一部门参考鸡块大神的文章。
  1. from Crypto.Util.number import *
  2. import sys
  3. e = 65537
  4. leak = 5599968251197363876087002284371721787318931284225671549507477934076746561842
  5. n = 7120275986401660066259983193598830554385933355254283093021239164350142898387660104515624591378875067038235085428170557400012848874756868985306042421950909
  6. c = 6803450117490196163076010186755045681029929816618361161925865477601994608941714788803007124967390157378525581080320415602012078322064392991884070073083436
  7. P = (4143131125485719352848137000299706175276016714942734255688381872061184989156686585992844083387698688432978380177564346382756951426943827434190895490233627 , 3879946878859691332371384275396678851932267609535096278038417524609690721322205780110680003522999409696718745532857001461869452116434787256032366267905519)
  9. p_xor_q = str(bin(leak)[2:]).zfill(256)
  11. def find(ph, qh, pl, ql):
  12.     l = len(ph)
  13.     tmp0 = ph + (256 - 2 * l) * "0" + pl
  14.     tmp1 = ph + (256 - 2 * l) * "1" + pl
  15.     tmq0 = qh + (256 - 2 * l) * "0" + ql
  16.     tmq1 = qh + (256 - 2 * l) * "1" + ql
  17.     if (int(tmp0, 2) * int(tmq0, 2) > n):
  18.         return
  19.     if (int(tmp1, 2) * int(tmq1, 2) < n):
  20.         return
  21.     if (int(pl, 2) * int(ql, 2) % (2 ** (l - 1)) != n % (2 ** (l - 1))):
  22.         return
  24.     if (l == 128):
  25.         pp0 = int(tmp0, 2)
  26.         if (n % pp0 == 0):
  27.             pf = pp0
  28.             qf = n // pp0
  29.             print(pf)
  30.             print(qf)
  31.             phi = (pf - 1) * (qf - 1)
  32.             d = inverse(e, phi)
  33.             m1 = pow(c, d, n)
  34.             print(long_to_bytes(m1))
  35.             exit()
  37.     else:
  38.         if (p_xor_q[l] == "1" and p_xor_q[255 - l] == "1"):
  39.             find(ph + "1", qh + "0", "1" + pl, "0" + ql)
  40.             find(ph + "0", qh + "0", "1" + pl, "1" + ql)
  41.             find(ph + "1", qh + "1", "0" + pl, "0" + ql)
  42.             find(ph + "0", qh + "1", "0" + pl, "1" + ql)
  43.         elif (p_xor_q[l] == "1" and p_xor_q[255 - l] == "0"):
  44.             find(ph + "1", qh + "0", "0" + pl, "0" + ql)
  45.             find(ph + "0", qh + "0", "0" + pl, "1" + ql)
  46.             find(ph + "1", qh + "1", "1" + pl, "0" + ql)
  47.             find(ph + "0", qh + "1", "1" + pl, "1" + ql)
  48.         elif (p_xor_q[l] == "0" and p_xor_q[255 - l] == "1"):
  49.             find(ph + "0", qh + "0", "1" + pl, "0" + ql)
  50.             find(ph + "0", qh + "1", "0" + pl, "0" + ql)
  51.             find(ph + "1", qh + "0", "1" + pl, "1" + ql)
  52.             find(ph + "1", qh + "1", "0" + pl, "1" + ql)
  53.         elif (p_xor_q[l] == "0" and p_xor_q[255 - l] == "0"):
  54.             find(ph + "0", qh + "0", "0" + pl, "0" + ql)
  55.             find(ph + "1", qh + "0", "0" + pl, "1" + ql)
  56.             find(ph + "0", qh + "1", "1" + pl, "0" + ql)
  57.             find(ph + "1", qh + "1", "1" + pl, "1" + ql)
  59. find("1", "1", "1", "1")
  60. # p = 64760524083545528318139240449356269097871629401328435356643510319660757701117
  61. # q = 109947782034870726628911928816041880655659770652764045401662566933641952899777
  62. # -908f-7c002c687387
复制代码
第二部门ECC，在这里已知n,a,b,P,而m2是就是M的x坐标，那么主要任务就是求出e，对于曲线的逆元。而n的位数较大，这里试过，无法直接求取模n的曲线的阶，而n = p * q，所以可以转为求模p,模q的阶，之后求取e对于n的逆元。
  1. # sage
  2. from  Crypto.Util.number import *
  3. p = 64760524083545528318139240449356269097871629401328435356643510319660757701117
  4. q = 109947782034870726628911928816041880655659770652764045401662566933641952899777
  5. e = 65537
  6. n = 7120275986401660066259983193598830554385933355254283093021239164350142898387660104515624591378875067038235085428170557400012848874756868985306042421950909
  7. P = E(4143131125485719352848137000299706175276016714942734255688381872061184989156686585992844083387698688432978380177564346382756951426943827434190895490233627 , 3879946878859691332371384275396678851932267609535096278038417524609690721322205780110680003522999409696718745532857001461869452116434787256032366267905519)
  8. E = EllipticCurve(Zmod(n),[114514,1919810])
  9. Ep = EllipticCurve(Zmod(p),[114514,1919810])
  10. Eq = EllipticCurve(Zmod(q),[114514,1919810])
  11. phi_n = Ep.order()*Eq.order()
  12. d = inverse(e,phi_n)
  13. G = P * d
  14. m = G[0]
  15. flag = long_to_bytes(int(m))
  16. print(flag)
  17. # a67b2a9b-0542-4646
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4