原理

随机生成两个素数，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)

RSA加密和解密

规定m表示明文，c表示密文

加密：c≡m^e mod n

解密：m≡c^d 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值的情况下再使用

实例BUUCTF-Crypto-21.RSA1

理论推导

• 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$的情况下

实例BUUCTF-Crypto-27.RSA2

理论推导

• 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$

实例BUUCTF-Crypto-28.RSA3

理论推导

• 共模攻击
• 理论推导 红色字 为重要结论
• 存在两种密钥对同一明文进行加密
• 下述为针对此题特殊情况下的特殊推导，需满足$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
• 原理太复杂了要翻论文了-链接
• 板子

实例BUUCTF-Crypto-40.rsa2

from RSAwienerHacker import *
n = ?
e = ?
d = hack_RSA(e,n)

扩展维纳攻击

参考 CTF wiki

两个低解密指数

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、相同私钥、格基规约、格、同一明文多次加密

论文链接

实例