RSA簡介:

取一個大數 n=p*q,p,q為大素數.

設n的歐拉函數為 f(n) = (p-1)(q-1);

?

則取一個公鑰為e,相應密鑰為d.

ed?+ x * f(n) = 1

要求: e*d = 1 (mod f(n))

原文為m:

密文為c =?m^e (mod n)

因為: m ^ f(n) = 1 (mod n)

解密:?c^d =?m^(e*d)? = m*( (m^f(n)) ^(-x)) (mod n)

?

破密:

1,因子分解法:

破解意向:若知道?p-1 , q-1 ,就知道了 f(n),?則就很容易破解了.

?

由于 p*q = n, p+q = n - f(n) +1

p,q 是 x^2 + (f(n)-n-1)x + n = 0 的根.

?

進而只要試出n的因子分解,就可以破解,因此n的分子分解決定了安全性.

如:

當p 和 q 很接近時,

因為 n = p*q =? ((p + q)/2)^2 -? ((p - q)/2)^2

當 (p - q)/2 接近于 0 時 ,? t = (p + q)/2 接近于 n^(1/2)

只要枚舉大于 n^(1/2) 的 t 很快就可以找出滿足

t^2 - n 為平方數的 t

使得?t^2 - n = s^2

則 n = (t+s) * (t-s)

至此就求出了 p 和? q.

?

2,階乘法

意向:

黑客可能會利用階乘法不斷地遞增 t 來求出 m 如:

?

因為 c^(e^t) = c? (mod n), 就有 c^(e^(t-1)) = m (mod n)

而 c^(e^(t-1)) = m? (mod n) 就是 m^(e^t) = m (mod n)

即 n |? (?m^(e^t -1) - 1 )

若 m mod n 的階為k,則

e^t = 1 (mod k)

取 t 的最小值就是 e mod k 的階,

而 e mod k 的階,是 f(k) 在因子,又 k 是 m mod n 階,

即 k 是 f(n) 的因子,求出 k 就容易破解了.

所以 最好使 f(n) ?中的兩個因子 p-1 , q-1 ,它們的因子中出現的素因子都要為大素數因子,

才能不容易被破解.

總結

以上是生活随笔為你收集整理的破解RSA的一些技术的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。