原理
随机生成两个素数,p , q
令n = p*q
由欧拉公式计算出φ(n) = (p-1)(q-1)
规定e,使得e满足1<e<φ(n),且gcd(e,φ(n)) = 1,一般e=65537或0x10001
此时就有了公钥=(e,n)
计算私钥
计算d,使得d满足ed≡1mod φ(n),即称d是e在模φ(n)下的逆元
得到私钥=(d,n)
有关欧拉公式
- $n=p^{e_1}_1p^{e_2}_2\dots p^{e_k}_k$
- $\varphi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots (1-\frac{1}{p_k})$
- $\varphi(n)=p^{e_1-1}_1p^{e_2-1}_2\dots p^{e_k-1}_k(p_1-1)(p_2-1)\dots (p_k-1)$
- 当$gcd(n,x)=1$时,满足$x^{\varphi(n)}\equiv 1\ mod\ n$
RSA加密和解密
规定m表示明文,c表示密文
加密:c≡me mod n
解密:m≡cd mod n
解密方式
正常解密
- 此方法适用于已知$p,q,e,c$的情况下
可以使用RSA Tool 2工具解密或者编写如下脚本
from Crypto.Util.number import *
p = ?
q = ?
e = ?
c = ?
n = p*q
d = inverse(e,(p-1) * (q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
dp,dq泄露
- 此方法使用于已知$p,q,d_{p},d_{q},c$的情况下
- 然而使用此方法前可以先尝试常用e值,在发现无法确定e值的情况下再使用
理论推导
- dp,dq泄露
- 理论推导 红色字 为重要结论
$$\because m \equiv c^d(mod\ n)$$
$$\therefore m = c^d+kn = c^d+k\cdot pq$$
$$m_{1} \equiv c^d(mod\ p)\ ①\ ,\ m_{2} \equiv c^d(mod\ q)\ ②$$
$$①\Rightarrow c^d=m_{1}+tp$$
$$代入②\Rightarrow m_{2}\equiv m_{1}+tp(mod\ q)$$
$$\therefore m_{2}=m_{1}+t\cdot p+r\cdot q\ \Rightarrow m_{2}-m_{1}=t\cdot p+r\cdot q$$
$$\therefore m_{2}-m_{1}=t\cdot p(mod\ q)$$
$$\therefore (m_{2}-m_{1})\cdot p^{-1}\equiv t(mod\ q)$$
$$\Rightarrow t=(m_{2}-m_{1})\cdot p^{-1}(mod\ q)$$
$$\therefore c^d=[(m_{2}-m_{1})\cdot p^{-1}(mod\ q)]p+m_{1}$$
$$\because m\equiv c^d(mod\ n)$$
$$\therefore {\color{Red} m\equiv [[(m_{2}-m_{1})\cdot p^{-1}(mod\ q)]p+m_{1}]mod\ n}$$
$$d\equiv d_{p}mod(p-1)\ , \ d\equiv d_{q}mod(q-1)$$
$$m_{1} \equiv c^dmod\ p\ ,\ m_{2} \equiv c^dmod\ q$$
$$\Rightarrow m_{1} \equiv c^\left .d_{p}\ +k_{1}\cdot (p-1)\right.\ mod\ p\ ,\ m_{2} \equiv c^\left .d_{q}\ +k_{2}\cdot (q-1)\right.\ mod\ p$$
$$\because c^\left.p-1\right.\equiv 1\ mod\ p$$
$$\Rightarrow {\color{Red} m_{1}\equiv c^\left .d_{p}\right . mod\ p\ ,\ m_{2}\equiv c^\left .d_{q}\right . mod \ q}$$
使用脚本解密
from Crypto.Util.number import *
p = ?
q = ?
dp = ?
dq = ?
c = ?
mp = pow(c,dp,p)
mq = pow(c,dq,q)
pi = inverse(p,q)
m = ((((mq-mp)pi)%q)p+mp)%(p*q)
print(long_to_bytes(m))
dp泄露
- 此方法使用于已知$e,n,d_{p},c$的情况下
理论推导
- dp泄露
- 理论推导 红色字 为重要结论
$$d_{p} \equiv d mod (p-1)$$
$$\Rightarrow d\cdot e = k_{1}(p-1)+d_{p}\cdot e$$
$$\because d\cdot e = 1mod(p-1)(q-1) \Rightarrow d\cdot e=k_{2}(p-1)(q-1)+1$$
$$\therefore {\color{Red} (p-1)(k_{2}(q-1)-k_{1})+1 = d_{p}e}$$
$$\because d_{p}<d$$
$$\therefore (k_{2}(q-1)-k_{1})=x\in (1,e)$$
from Crypto.Util.number import *
e = 65537
n = ?
dp = ?
c = ?
a = dp*e-1
for x in range(2,e):
if a%x == 0:
p = a//x+1
if n%p == 0:
q = n//p
break
d = inverse(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
共模攻击
- 此方法使用于已知$n,e_{1},e_{2},c_{1},c_{2}$的情况下
- 且$gcd(e_{1},e_{2})=1$
理论推导
- 共模攻击
- 理论推导 红色字 为重要结论
- 存在两种密钥对同一明文进行加密
- 下述为针对此题特殊情况下的特殊推导,需满足$gcd(e_{1},e_{2})=1$
$$c_{1}=m^\left. e_{1}\right. mod\ n\ \&\ m=c_{1}^\left.d_{1}\right.mod\ n$$
$$c_{2}=m^\left. e_{2}\right. mod\ n\ \&\ m=c_{2}^\left.d_{2}\right.mod\ n$$
$$构造一对(s_{1},s_{2})满足e_{1}s_{1}+e_{2}s_{2}=1其中s_{1},s_{2}\in Z,s_{1}>0,s_{2}<0$$
$$c_{1}=m^\left. e_{1}\right. mod\ n \Rightarrow c_{1}^\left. s_{1}\right. =m^\left. e_{1}s_{1}\right. mod\ n ①$$
$$c_{2}=m^\left. e_{2}\right. mod\ n \Rightarrow c_{2}^\left. s_{2}\right. =m^\left. e_{2}s_{2}\right. mod\ n ②$$
$$①\times ②\Rightarrow c_{1}^\left. s_{1}\right. c_{2}^\left. s_{2}\right. mod\ n = m^\left. e_{1}s_{1}+e_{2}s_{2}\right. mod\ n$$
$$\Rightarrow c_{1}^\left. s_{1}\right. c_{2}^\left. s_{2}\right. mod\ n=m\ mod\ n$$
$$\because m=c^d mod\ n \therefore m<n$$
$$\therefore {\color{red}m=c_{1}^\left. s_{1}\right. c_{2}^\left. s_{2}\right. mod\ n}$$
$$需要注意的是推论到上面就结束了,但是实际计算中上述式子计算过于复杂,所以应当使用下述式子$$
$${\color{red}m=(c_{1}^\left. s_{1}\right. mod\ n\cdot c_{2}^\left. s_{2}\right. mod\ n)mod\ n}$$
$$以及在计算s_{1},s_{2}过程中可以采用逆元的方式$$
$$(e_{1}-e{2})s_{1}+e{2}(s_{1}+s_{2})=1$$
$$(e_{1}-e{2})s_{1}\equiv 1\ mod\ e_{2}$$
$$s_{1}=(e_{1}-e{2})^\left. -1\right. $$
- 由此计算出一对$(s_{1},s_{2})$,进而算出明文m
- 编写脚本
from Crypto.Util.number import *
n = ?
c1 = ?
c2 = ?
e1 = ?
e2 = ?
e1_e2 = e1-e2
s1 = inverse(e1_e2,e2)
s2 = (1-e1*s1)//e2
m = pow(c1,s1,n)*pow(c2,s2,n)%n
print(long_to_bytes(m))
维纳攻击
- 此方法使用于$e$过大或过小的情况下
- 本质:满足$d < \frac{1}{3} N^{\frac{1}{4} }$则一定可以分解$N$
- 大致解密过程是用RSAwienerHacker库来攻击得到d
- 原理太复杂了要翻论文了-链接
- 板子
from RSAwienerHacker import *
n = ?
e = ?
d = hack_RSA(e,n)
扩展维纳攻击
两个低解密指数
from Crypto.Util.number import *
e1 = ...
e2 = ...
N = ...
a = 5/14
D = diagonal_matrix(ZZ, [N, int(N^(1/2)), int(N^(1+a)), 1])
M = matrix(ZZ, [[1, -N, 0, N^2], [0, e1, -e1, -e1*N], [0, 0, e2, -e2*N], [0, 0, 0, e1*e2]])*D
L = M.LLL()
t = vector(ZZ, L[0])
x = t * M^(-1)
phi = int(x[1]/x[0]*e1)
d = inverse(e,phi)
二次剩余+CRT
- 此方法适用于$e$非质,即$gcd(e,\varphi )=2$
- 要求解任意模数二次剩余先要求解奇素数模数二次剩余–具体理论查看此链
- 据此推导过程编写脚本
实例[0xGame 2024] Number-Theory-CRT
from Crypto.Util.number import *
import sympy
from sympy.ntheory.modular import crt
c = ?
e = ?
n = ?
p = ?
q = ?
phi = (p-1) * (q-1)
print(GCD(e,phi)) # 发现公约数2,分析得到二次剩余
def find_quadratic_residues(a, p):
# 首先检查 a 是否是模 p 下的二次剩余
if not sympy.is_quad_residue(a, p):
return None # 如果 a 不是二次剩余,返回 None
# 使用 sympy 的 nthroot_mod 找到一个解
x = sympy.nthroot_mod(a, 2, p, all_roots=False)
# 计算另一个解
second_solution = p - x
return (x, second_solution)
x1 = find_quadratic_residues(c,p) # 求解模p下的二次剩余
x2 = find_quadratic_residues(c,q) # 求解模q下的二次剩余
for i in x1:
for j in x2:
remainders = [i,j]
mods = [p,q]
m_ = crt(mods, remainders)[0] # CRT合并得到模n的二次剩余解
c_ = m_%n
e_ = e//2
d = inverse(e_,phi)
m = pow(c_,d,n)
print(long_to_bytes(m))
Rabin加密
- 可以看作是RSA中$e=2$的特殊情况,且$p\equiv q\equiv 3\ mod\ 4$
- 解法原理同上二次剩余+CRT
*论文题
关键字:RSA、相同私钥、格基规约、格、同一明文多次加密
太强了哥|´・ω・)ノ