Crypto学习笔记（持续更新）

数学是个看天赋的学科，而我恰好没有这个天赋，别人很容易理解的内容，我需要学习很久。

本篇博客将记录我探索Crypto世界的点滴旅程，初衷是为了方便自己查阅，也便于自我成长与回顾，倘若笔者浅薄之见，能有幸为诸位师傅学问之海添一滴水，实乃蓬荜生辉，甚为喜悦。在此过程中，各位师傅如有任何观察到的疏漏或偏差，欢迎随时指正，先谢过各位师傅了。

二零二四年四月三十日记

2024第九届中国海洋大学信息安全竞赛-NeXT RSA（费马分解法，p、q相近）

题目描述：聪明的小军觉得既然都选择了随机的 p，那根据 p 选择 q，q 也是随机的辣！

import sympy
import libnum

flag="flag{" + "???" + "}"
m = libnum.s2n(flag)

p = sympy.randprime(1<<1024, 1<<1025)# 生成1024位到1025位之间的随机素数p
q = sympy.nextprime(p)# 找到大于p的下一个素数q

n = p*q
r = (p-1)*(q-1)
e = 65537

c = pow(m, e, n)

print(n, e, c)
# output:
#80044118049755180996754407858488943779355738585718372337839486032339412481191013051614126608584578841408197524632831442032118319629160505851518198448787590483634506563248531254421862061651099856312546562506221294620627871718678484548245902274972044599314097339549053518589561289734819710218838311181044519738709148493164321955860982700783886286661558574861608455547990794798848491695189544811325833194530596317989718866319530140199263278168146224240677087191093183415595617994125075880280632369616506148501757653260154487000183157405531772172082897743929126980157956142627803176227942226654177011633301413616266656761
#65537
#23280133104463252598665779150831148192014617461904564929071121215373331248942762386170411274023248423328388793808975632652896384007449549469345318875514363621903138122407682293848670093433946555776164835208375667498606187869211466397624286383057425296636315379314349307816391315242971306898487494604324473266965665471735612154916305882443496151118031672777088597821127499085632141307413890900246444539517971766135909771880642211582699957211983212981047822362311969553832913399476190919026666192056319334425636757404603336130688707109219644178606626422717046059209499394056295682594928581470210114322505904198054215544

其中 q 是 p 的下一个素数，这题可以使用费马分解法。

由于p，q直接相邻，则必有p < sqrt(n) < q 且p，q都是紧挨着sqrt(n) 的素数，用题目里的nextprime(sqrt(n)) 即可得q，进而解出密文。

解题脚本：

import gmpy2
import sympy
from Crypto.Util.number import *
 
n = 80044118049755180996754407858488943779355738585718372337839486032339412481191013051614126608584578841408197524632831442032118319629160505851518198448787590483634506563248531254421862061651099856312546562506221294620627871718678484548245902274972044599314097339549053518589561289734819710218838311181044519738709148493164321955860982700783886286661558574861608455547990794798848491695189544811325833194530596317989718866319530140199263278168146224240677087191093183415595617994125075880280632369616506148501757653260154487000183157405531772172082897743929126980157956142627803176227942226654177011633301413616266656761
c = 23280133104463252598665779150831148192014617461904564929071121215373331248942762386170411274023248423328388793808975632652896384007449549469345318875514363621903138122407682293848670093433946555776164835208375667498606187869211466397624286383057425296636315379314349307816391315242971306898487494604324473266965665471735612154916305882443496151118031672777088597821127499085632141307413890900246444539517971766135909771880642211582699957211983212981047822362311969553832913399476190919026666192056319334425636757404603336130688707109219644178606626422717046059209499394056295682594928581470210114322505904198054215544
e = 65537
n2=gmpy2.iroot(n,2)[0]
p=sympy.nextprime(n2)
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

这段代码使用了几个Python库（gmpy2, sympy, Crypto.Util.number）来执行一个RSA加密信息的解密过程。

1. 导入所需库:

   import gmpy2
   import sympy
   from Crypto.Util.number import *
   

   • gmpy2库用于高效的数学运算，特别是大数运算。
   • sympy库用于符号数学计算，这里主要用到了寻找下一个素数的功能。
   • Crypto.Util.number模块包含了处理大整数的工具。

2. 定义密文、模数和公钥指数:

   n = ...  # 很长的整数，模数
   c = ...  # 密文
   e = 65537  # 公钥指数，常见的RSA公钥指数
   

3. 计算n的平方根:

   n2=gmpy2.iroot(n,2)[0]
   

   这里尝试计算n的平方根，并取整数部分，用于后续步骤中的近似估计p或q的大小。

4. 寻找p和q:

   p=sympy.nextprime(n2)
   q=n//p
   

   首先，使用sympy.nextprime(n2)找到大于n的平方根的下一个素数作为p的一个估计值。然后，通过n除以p得到q的近似值。这里的方法假设n是两个相近的素数的乘积，且通过近似方法找到这两个素数。

5. 计算欧拉函数φ(n):

   phi=(p-1)*(q-1)
   

   计算模数n对应的欧拉函数φ(n)，用于计算解密指数d。

6. 计算解密指数d:

   d=gmpy2.invert(e,phi)
   

   利用扩展欧几里得算法计算d，使得(ed \equiv 1 \mod \phi(n))。

7. 解密密文:

   m=pow(c,d,n)
   

   使用快速幂算法计算(c^d \mod n)，得到原始明文的数值表示。

8. 转换并打印解密结果:

   print(long_to_bytes(m))
   

   将解密得到的数值转换为字节串并打印出来，通常用于展示解密后的文本信息。