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

x1 = 1

y1 = 0

#a*x2 + b*y2 = b

x2 = 0

y2 = 1

while b != 0:

q = a / b

#ri = r(i-2) % r(i-1)

r = a % b

a = b

b = r

#xi = x(i-2) - q*x(i-1)

x = x1 - q*x2

x1 = x2

x2 = x

#yi = y(i-2) - q*y(i-1)

y = y1 - q*y2

y1 = y2

y2 = y

return(x1, y1, a)

def computeD(fn, e):

(x, y, r) = extendedGCD(fn, e)

#y maybe < 0, so convert it

if y < 0:

return fn + y

return y

def keyGeneration(p,q,e):

#generate public key and private key

n = p * q

fn = (p-1) * (q-1)

d = computeD(fn, e)

return (d,n)

p_v = int(raw_input("請輸入p的值(10進位)
"))

q_v = int(raw_input("請輸入q的值(10進位)
"))

e_v = int(raw_input("請輸入e的值(10進位)
"))

c_v = int(raw_input("請輸入密文c的值(10進位)
"))

(d,n) = keyGeneration(p_v,q_v,e_v) #生成 d和n

m = pow(c_v,d,n)

print ("得到的明文m是: "+str(m))

當輸入p值：18443，q值：49891，e值19，

密文c值：

70479679275221115227470416418414022368270835483295235263072905459788476483295235459788476663551792475206804459788476428313374475206804459788476425392137704796792458265677341524652483295235534149509425392137428313374425392137341524652458265677263072905483295235828509797341524652425392137475206804428313374483295235475206804459788476306220148

得到的結果就會顯示

得到的明文m是: 88455713

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！