攻防世界Crypto练习区：crypto_rsa1练习

0x1 题目来源

  1.攻防世界Crypto练习区：crypto_rsa1。

  2.题目没有描述，下载后是一个压缩包，解压后看到源码：

1. from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes
   
2. from gmpy2 import powmod,invert,gcd
   
3. from flag import flag
   
4. import sympy
   
5. 
   
6. q = getPrime(1024)
   
7. p = sympy.nextprime(q)
   
8. N = p * q
   
9. e = 0x10001
   
10. flag = flag.ljust(80)
    
11. m = bytes_to_long(flag)
    
12. c = pow(m,e,N)
    
13. 
    
14. print('N = ',N)
    
15. print('e = ',e)
    
16. print('c = ',c)
    
17. 
    
18. '''
    
19. N =  12194420073815392880989031611545296854145241675320130314821394843436947373331080911787176737202940676809674543138807024739454432089096794532016797246441325729856528664071322968428804098069997196490382286126389331179054971927655320978298979794245379000336635795490242027519669217784433367021578247340154647762800402140321022659272383087544476178802025951768015423972182045405466448431557625201012332239774962902750073900383993300146193300485117217319794356652729502100167668439007925004769118070105324664379141623816256895933959211381114172778535296409639317535751005960540737044457986793503218555306862743329296169569
    
20. e =  65537
    
21. c =  4504811333111877209539001665516391567038109992884271089537302226304395434343112574404626060854962818378560852067621253927330725244984869198505556722509058098660083054715146670767687120587049288861063202617507262871279819211231233198070574538845161629806932541832207041112786336441975087351873537350203469642198999219863581040927505152110051313011073115724502567261524181865883874517555848163026240201856207626237859665607255740790404039098444452158216907752375078054615802613066229766343714317550472079224694798552886759103668349270682843916307652213810947814618810706997339302734827571635179684652559512873381672063
    
22. '''

复制代码

  3. 看源码给出了N，e，c，这个sympy.nextprime(q)，表示p和q接近。

0x2 分析工具

  1.想办法分解大数N，已经p,q,e,c再使用rsa计算工具得到明文d，网上找到了一篇参考教程：https://www.bilibili.com/read/cv13392301/。

  2.在线查询分解网站：http://www.factordb.com/index.php

  3.使用yafu工具分解,下载地址：https://sourceforge.net/projects/yafu/

  4.费马定理分解

1. def isqrt(n):
   
2.   x = n
   
3.   y = (x + n // x) // 2
   
4.   while y < x:
   
5.     x = y
   
6.     y = (x + n // x) // 2
   
7.   return x
   
8. 
   
9. def fermat(n, verbose=True):
   
10.     a = isqrt(n) # int(ceil(n**0.5))
    
11.     b2 = a*a - n
    
12.     b = isqrt(n) # int(b2**0.5)
    
13.     count = 0
    
14.     while b*b != b2:
    
15.         # if verbose:
    
16.         #     print('Trying: a=%s b2=%s b=%s' % (a, b2, b))
    
17.         a = a + 1
    
18.         b2 = a*a - n
    
19.         b = isqrt(b2) # int(b2**0.5)
    
20.         count += 1
    
21.     p=a+b
    
22.     q=a-b
    
23.     assert n == p * q
    
24.     # print('a=',a)
    
25.     # print('b=',b)
    
26.     # print('p=',p)
    
27.     # print('q=',q)
    
28.     # print('pq=',p*q)
    
29.     return p, q
    
30. fermat(n)

复制代码

0x3 脚本解密

&#8195;&#8195;1.套用参考文章的脚本，替换N，e，c三个值，得到：

1. import  gmpy2
   
2. import libnum
   
3. 
   
4. def isqrt(n):
   
5.   x = n
   
6.   y = (x + n // x) // 2
   
7.   while y < x:
   
8.     x = y
   
9.     y = (x + n // x) // 2
   
10.   return x
    
11. 
    
12. def fermat(n, verbose=True):
    
13.     a = isqrt(n) # int(ceil(n**0.5))
    
14.     b2 = a*a - n
    
15.     b = isqrt(n) # int(b2**0.5)
    
16.     count = 0
    
17.     while b*b != b2:
    
18.         # if verbose:
    
19.         #     print('Trying: a=%s b2=%s b=%s' % (a, b2, b))
    
20.         a = a + 1
    
21.         b2 = a*a - n
    
22.         b = isqrt(b2) # int(b2**0.5)
    
23.         count += 1
    
24.     p=a+b
    
25.     q=a-b
    
26.     assert n == p * q
    
27.     # print('a=',a)
    
28.     # print('b=',b)
    
29.     print('p=',p)
    
30.     print('q=',q)
    
31.     # print('pq=',p*q)
    
32.     return p, q
    
33. n= 12194420073815392880989031611545296854145241675320130314821394843436947373331080911787176737202940676809674543138807024739454432089096794532016797246441325729856528664071322968428804098069997196490382286126389331179054971927655320978298979794245379000336635795490242027519669217784433367021578247340154647762800402140321022659272383087544476178802025951768015423972182045405466448431557625201012332239774962902750073900383993300146193300485117217319794356652729502100167668439007925004769118070105324664379141623816256895933959211381114172778535296409639317535751005960540737044457986793503218555306862743329296169569
    
34. e= 65537
    
35. c= 4504811333111877209539001665516391567038109992884271089537302226304395434343112574404626060854962818378560852067621253927330725244984869198505556722509058098660083054715146670767687120587049288861063202617507262871279819211231233198070574538845161629806932541832207041112786336441975087351873537350203469642198999219863581040927505152110051313011073115724502567261524181865883874517555848163026240201856207626237859665607255740790404039098444452158216907752375078054615802613066229766343714317550472079224694798552886759103668349270682843916307652213810947814618810706997339302734827571635179684652559512873381672063
    
36. pq=fermat(n)
    
37. p=pq[0]
    
38. q=pq[1]
    
39. phi_n=(p-1)*(q-1)
    
40. #求逆元
    
41. #d=libnum.invmod(e,phi_n)
    
42. d=gmpy2.invert(e,phi_n)
    
43. m=pow(c,d,n)
    
44. print(m)
    
45. print(libnum.n2s(int(m)).decode())

复制代码

&#8195;&#8195;2.执行py脚本报错，提示没有找到libnum模块，输入pip install libnum安装，运行再报错，重复同样的步骤安装对应模块即可。

1. C:\Users\LENOVO\Desktop>1.py
   
2. Traceback (most recent call last):
   
3.   File "C:\Users\LENOVO\Desktop\1.py", line 2, in <module>
   
4.     import libnum
   
5. ModuleNotFoundError: No module named 'libnum'

复制代码

&#8195;&#8195;3.打印出了p,q的值和flag。

1. C:\Users\LENOVO\Desktop>1.py
   
2. p= 11042834814401324223490700808335597483426691702722872474973038510408702524935
   
3. 23459461649803610821785323136697674852702543264047239481539129106881181406217129
   
4. 22649644396733499972695482991866293857864311557686710317462165131360819813493524
   
5. 457615383204504505224030129953230866877990529769205769592709254542472051
   
6. q= 11042834814401324223490700808335597483426691702722872474973038510408702524935
   
7. 23459461649803610821785323136697674852702543264047239481539129106881181406217129
   
8. 22649644396733499972695482991866293857864311557686710317462165131360819813493524
   
9. 457615383204504505224030129953230866877990529769205769592709254542470619
   
10. 18253925923982047205986424851121322554758057061858542412479835360825682848439282
    
11. 39211521652778447259428509799330489185958833814558444450696791918083165183860444
    
12. 150060968303497172121385611304992
    
13. flag{5c9c885c361541e0b261f58b61db8cec}

复制代码

&#8195;&#8195;4.提交flag，验证通过：

0x4总结

&#8195;&#8195;这种方法是在已知大数N，加密密钥e，密文c才可以使用，并且e很小，p和q接近，才会很快爆出。