RSA加密算法是一種非對稱加密算法，由Ron Rivest、Adi Shamir和Leonard Adleman在1977年共同提出。下文先簡要介紹RSA加密的原理，再介紹如何使用Python進行解密。

RSA算法的加密

生成公鑰和私鑰

第一步：任取不相等的兩質數$p,q$。（此處$p,q$的大小決定了破譯難度）

第二步：$n=pq$。（$n$的二進位制的長度即為密鑰長度)

第三步：計算$n$的Euler函數$φ(n) = (p-1)(q-1)$。

第四步：任取整數$e$滿足$1<e<φ(n)$，且$e$與$φ(n)$互質。

第五步：計算出$e$對於$φ(n)$的模反元素$d$。

第六步：公鑰為$(n,e)$，私鑰為$(n,d)$。

加密

第一步：取需要加密的整數$m$。（此處$m<n$）（若要加密字串等，可用ASCII編碼先轉化為整數）

第二步：密文$c\equiv m^e({\rm mod}\ n)$。

$n,e,c$是公開的，$p,q,φ(n),d,m$是私密的。

RSA算法的解密

首先，我們需要了解以下兩個算法：

擴展Euclidean算法 (EEA)

對於兩正整數$a,b$，我們有Euclidean算法（即輾轉相除法）來計算$gcd(a,b)$：

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

由Bézout定理可知，存在整數$x,y$使得$ax+by=gcd(a,b)$成立。

相較於Euclidean算法，擴展Euclidean算法除了計算$gcd(a,b)$，還會得到$x,y$的值。

代碼如下：

（非遞歸）

def eea(a,b): 
    x,x1=1,0
    y,y1=0,1
    r,r1=a,b 
    if b==0: 
        return a,1,0  
    while r1!=0:
        q=r//r1
        r,r1=r1,r-q*r1
        x,x1=x1,x-q*x1
        y,y1=y1,y-q*y1
    # r is gcd(a,b)
    # ax+by=r
    return r,x,y

（遞歸）

def eea(a,b):
    if b==0:
        return a,1,0
    r,x,y=eea(b,a%b)
    # ax+by=r
    # return r,x,y successively
    return r,y,x-a//b*y

Square-and-Multiply算法 (SAMA)

對於三正整數$a,e,n$，我們有Square-and-Multiply算法來計算$a^e({\rm mod}\ n)$，其原理是：

取$e$的二進位制$e=(e_{k-1}…e_0)_2$（其中$k$為$e$的二進位制的長度），則有$e=\sum^{k-1}_{i=0}{e_i\cdot 2^i}$。

$x_0=a$

$x_1=(x_0^2\ {\rm mod}\ n)=(a^2\ {\rm mod}\ n)$

$…$

$x_i=(x_{i-1}^2\ {\rm mod}\ n)=(a^{2^i}\ {\rm mod}\ n)$

$…$

$x_{k-1}=(x_{k-2}^2\ {\rm mod}\ n)=(a^{2^{k-1} }\ {\rm mod}\ n)$

由此可得$a^e\equiv \prod^{k-1}_{i=0}{x_i^{e_i}} ({\rm mod}\ n)$。

代碼如下：

def sam(a,e,n):
    k=len(bin(e))-2
    remainder=1
    x=a 
    for i in range(k): 
        if bin(e)[-i-1]=="1": 
            remainder*=x 
        x=x**2%n 
    return remainder%n

解密

由$c\equiv m^e({\rm mod}\ n)$可證$c^d\equiv m({\rm mod}\ n)$，下給出證明過程：

知$ed\equiv1({\rm mod}\ φ(n))$，因此有$ed-1=lφ(n),(l\in\mathbb N_+)$；

由Euler定理，有$c^d\equiv m^{ed}\equiv m^{lφ(n)+1}\equiv m\cdot (m^{φ(n)})^l\equiv m\cdot 1^l\equiv m({\rm mod}\ n)$，得證。

因此，如果已知$(n,d,c)$，結合Square-and-Multiply算法即可得到原文$m$，代碼如下：

1 2	def rsa_1(n,d,c): return sam(c,d,n)

同理，如果已知$(p,q,e,c)$，結合擴展Euclidean算法和Square-and-Multiply算法也可得到原文$m$，代碼如下：

def rsa_2(p,q,e,c):
    φ=(p-1)*(q-1)
    d=eea(e,φ)[1]%φ #Ensure d>0
    n=p*q
    return sam(c,d,n)

這是因為由$φ(n) = (p-1)(q-1)$和$ed\equiv1({\rm mod}\ φ(n))$可知$de+kφ(n) =1(k\in\mathbb Z) $，對$(e,φ(n))$使用擴展Euclidean算法即可得$d$，又由$c^d\equiv m({\rm mod}\ n)$可知對$(c,d,n)$使用Square-and-Multiply算法即可得$m$（此處也說明$d$必須是正數）。

例題

對密文$c$在RSA中進行解密，已知

p=92848022024833655041372304737256052921065477715975001419347548380734496823522565044177931242947122534563813415992433917108481569319894167972639736788613656007853719476736625612543893748136536594494005487213485785676333621181690463942417781763743640447405597892807333854156631166426238815716390011586838580891
q=149600854933825512159828331527177109689118555212385170831387365804008437367913613643959968668965614270559113472851544758183282789643129469226548555150464780229538086590498853718102052468519876788192865092229749643546710793464305243815836267024770081889047200172952438000587807986096107675012284269101785114471
e=4099852173630681822722339660229701793484497077549023050739406744299194740794285841565894857183257305962091658478256403457898496259755474199072635097327398971990092224918103250375455707498928712201945370461644425637423044616348028546654820134532012544433519158531485300462390097592776352017667386632661678681500542766835469056490039928380877979712159080905348869475217939844173751698241442662611990406492300411900572847532884748092860563495914734527293634873292356463076178294881900968373918292064527855306925898818421646057616238873254251939953144948550922456255743607156013509822605943382352582252129366170771186337
c=1965004133006974659995314560167723896560162823992014763466676295156568780181324759118466356116827422439409513865820570400810380977333397895810023254515182242123244875173658899005048988942666876614798046351776061310094809679938914368938218289806790724992660151078718864505196754907261135221257146114289875149015431301569207527108638684989789729747097766650481983822742788958528594215002940645806662061041825912562593269329369550470854629711422167160350497882132054038403027493105855840606846063029571758386220434189610971724518330438082401592895354255430599515214166039595157639322144199213475742435020500518884278854

使用代碼

1	print(tsa_2(p,q,e,c))

可得

m=6307076265101868022401168220914091002094923647543913608078494521549403802210173444891094505706734673093765283572976861935581726849816923593651509857540611964713018709162664925976240947063856932023113689107118569968804329173281583483592095382533613111762918421362278333322916021933519728291798749842494918068962745956079827474452589542646246101220774107235973703726237733253085312380677531524226610656535104841419537111452876626825419473934925741346089252331195249707094812401729770078951956524070871949864300367817846976007250758036392548367298788322489841149673899984125317729640492807125318100997973696848942216291