1.隨機取大質數(shù) p、q

2.設 n = p x q, n 的二進制位數(shù)就是密鑰長度,一般為1024,2048.

3.計算n的歐拉函數(shù) φ(n) = (p - 1)(q - 1)

4.從 1 - φ(n) 之間選擇一個整數(shù),且 e 與 φ(n) 互質,計作 e

5.計算 e 對于 φ(n) 的模反元素d
ed ≡ 1 (mod φ(n))
意思就是 ed / φ(n) 余數(shù) 1
等價于 ed - 1 = k * φ(n), 由于d 和 k 未知,相當于二元一次方程求解

6. (n,e) 作為公鑰, (n,d) 作為私鑰

7.加密: me ≡ c (mod n) ,其中m (密文,整數(shù))二進制長度不可超過n m:明文 c:密文

8.解密: cd ≡ m (mod n) 歐拉定理可證

9.暴力破解:

• 因為解密需要私鑰(n,d).
• 根據(jù) ed ≡ 1 (mod φ(n))
• e 已經(jīng)是公鑰提供了,所以只要知道φ(n)就可以破解
• 問題轉化為求 φ(n):
• • 求 φ(n), 根據(jù) φ(n) = (p - 1)(q - 1)
• • 所以轉求 p - 1 和 q - 1, 根據(jù)n = p * q
• • 只要因數(shù)分解 n 得出p 和 q 就可以計算φ(n) = (p - 1)(q - 1)
• 但是,想要因數(shù)分解n為兩個大質數(shù)的乘積,只能從最小的質數(shù)一點點循環(huán)的試,目前貌似只有768位的二進制被質因數(shù)分解了.再長還未公布.