簡述rsa算法基本思想?1.公鑰與私鑰的生成：，我來為大家科普一下關于簡述rsa算法基本思想?以下内容希望對你有幫助!

簡述rsa算法基本思想

1.公鑰與私鑰的生成：

• (1) 随機挑選兩個大質數 p 和 q，構造n = p*q;
• (2)計算歐拉函數φ(n) = (p-1) * (q-1);
• (3)随機挑選e，使得gcd(e, φ(n)) = 1，即 e 與 φ(n) 互素,gcd指的是求最大公約數;
• (4)計算d，使得 e*d ≡ 1 (mod φ(n))，即d 是e 的乘法逆元。

2.加密過程：

• (1)待加密信息（明文）為 m，m < n；（因為要做模運算，若m大于n，則後面的運算不會成立，因此當信息比n要大時，應該分塊加密）;
• (2))密文 c 的生成是 $$ c = m^e mod (n) $$

3.解密

$$ c^d mod (n) = (m^e)^d mod (n) = m^(d*e) mod (n) ; $$

3.解密

$$ c^d mod (n) = (m^e)^d mod (n) = m^(d*e) mod (n) ; $$

為什麼能解密？

要用到歐拉定理（其實是費馬小定理的推廣）

a^φ(n) ≡ 1 (mod n)，

再推廣：a^(φ(n)k) ≡ 1 (mod n)，

得到 a^(φ(n)k 1) ≡ a (mod n)

注意到 ed ≡ 1 mod φ(N)，即：ed = 1 k*φ(N)。

因此，$$ M^(de) mod N = M^1 kφ(N) mod N = M $$

4.代碼如下

實例

#coding=utf-8

#__author__ = 'ralph'

import random

def extendedGCD(a, b):

#a*xi b*yi = ri

if b == 0:

return (1, 0, a)

#a*x1 b*y1 = a

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部