RSA 題常見的情況
$$c = m^e \ mod\ N$$
如果 N 的其中一個質數是 K-smooth 數 (k不大) :
像是 N 後面很多零 (ex : ...00000000000000001) 這種數字的 phi : (p-1)*(q-1) 通常很好分解 可以試試看 Pollard p-1 把他炸開 只要 $x^{a}$ 不斷疊加中的 $a$ 涉及到所有 $p-1$ 的因式，那麼這個數字就會被分解出來- Pollard rho 分解
- Pollard’s p-1
- William’s p+1
如果 N 是由兩個相近的質數相乘
- Fermat Factorization
N 結尾是 $0$、$2$ 或是 $5$：
- 可能是由小質數組合而成的，可以試著用小質數來分解(<1000000)看看
e 爆幹大
- Wiener Attack，可以直接由 e,n 來分解 n
- 如果 $(d < n^{0.29})$，可以用 Boneh Durfee，直接由 e,n 來找出 d (容忍度比 Wiener 大，但是跑比較久)
e 不大，且已知高位 ($\frac{2}{3}$) 的 m
f = (m + x)**e - c2 (in Zmod(n))- Coppersmith 攻擊：如果說 e 階多項式有一個根小於 $n^{\frac{1}{e}}$，給定 m, e, c, n 就能夠算出 x，這個演算法可以慢慢的將 RSA 的明文復原。
1
2
3
4
5def coppersmith(N,e,known_m,c,epsilon=1/50):
P.<x> = PolynomialRing(Zmod(N), implementation='NTL')
pol = (known_m + x)^e - c
roots = pol.small_roots(epsilon=epsilon)
return roots
有兩組密文，使用的 e 不一樣 (彼此互質) 且 N 相同
使用 “擴展歐幾里得算法(Extended Euclidean algorithm)”
假設 $e1 = 5, e2 = 65537$
$$xgcd(e1,e2) : (26215, -2, 1)$$
也就是說 $e126215 + e2(-2) = 1$
把次方項消掉就好囉$$c_1 = m^{e1}\ mod\ N$$
$$c_2 = m^{e2}\ mod\ N$$$$c_1^{26215} + c_2^{-2} \ mod\ N \ \ \ : use\ \ invmod((c_2)^{2},N)$$
$$\rightarrow c = m^1\ mod\ N$$
e 不大，兩段密文，且已知明文 m 之間有微小的差距
g1 = m ** e - c1 g2 = (m + x)**e - c2- Coppersmith Shortpad：給定 (n, e, c1, c2) 能夠算出他們倆之間的差 x
e 不大，兩段密文中，明文具有線性關係
g1 = m ** e - c1 g2 = (a*m + x)**e - c2- Franklin Reiter’s Attack：給 (n, e, c1, c2) 幫你找最大公因式，把 x 噴出來
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16def franklin_reiter_related_message(n,e,c1,c2,r,a) :
R.<X> = Zmod(n)[]
f1 = X^e - c1
f2 = (a*X + r)^e - c2
def fun_gcd(a, b):
if a == 0: return b
if b == 0: return a
print("Dimensionality reduction : ")
while b:
print(str(a.degree()))
a, b = b, a % b
return a.monic()
return str(fun_gcd(f1, f2).coefficients()[0])
如果遇到 N 不相同：
e 一樣但是不大：
這個情況下或許會用到 “中國餘式定理CRT(Chinese Remainder Theorem)”
關於這個 $e$ 大不大，需要自己估一下 $m^e$ 會不會大於全部的 $N$ 相乘。
如果 $m^e < N$ ，直接開 e 次方就是答案了e 一樣：
這個時候可能 N1, N2, N3 之中會有同樣的 p,q，做最大公因數(gcd)，有時候就會分解出什麼來。
$$N_1 = a * b$$
$$N_2 = p * q$$
$$N_3 = p * r$$e 一樣，且 d 不大 ：
- LLL 解 d