?關(guān)于使用python實(shí)現(xiàn)RSA加密解密

一寇甸、非對(duì)稱(chēng)加密算法

1、乙方生成兩把密鑰（公鑰和私鑰）疗涉。公鑰是公開(kāi)的拿霉，任何人都可以獲得，私鑰則是保密的咱扣。

2绽淘、甲方獲取乙方的公鑰，然后用它對(duì)信息加密闹伪。

3沪铭、乙方得到加密后的信息壮池，用私鑰解密。

二杀怠、RSA算法

1977年椰憋，三位數(shù)學(xué)家Rivest、Shamir 和 Adleman 設(shè)計(jì)了一種算法赔退，可以實(shí)現(xiàn)非對(duì)稱(chēng)加密橙依。這種算法用他們?nèi)齻€(gè)人的名字命名，叫做RSA算法离钝。從那時(shí)直到現(xiàn)在票编，RSA算法一直是最廣為使用的"非對(duì)稱(chēng)加密算法"褪储。毫不夸張地說(shuō)卵渴，只要有計(jì)算機(jī)網(wǎng)絡(luò)的地方，就有RSA算法鲤竹。

這種算法非忱硕粒可靠，密鑰越長(zhǎng)辛藻，它就越難破解碘橘。根據(jù)已經(jīng)披露的文獻(xiàn)，目前被破解的最長(zhǎng)RSA密鑰是768個(gè)二進(jìn)制位吱肌。也就是說(shuō)痘拆，長(zhǎng)度超過(guò)768位的密鑰，還無(wú)法破解（至少?zèng)]人公開(kāi)宣布）氮墨。因此可以認(rèn)為纺蛆，1024位的RSA密鑰基本安全，2048位的密鑰極其安全规揪。

三桥氏、數(shù)學(xué)基礎(chǔ)

1、互質(zhì)關(guān)系

如果兩個(gè)正整數(shù)猛铅，除了1以外字支，沒(méi)有其他公因子，我們就稱(chēng)這兩個(gè)數(shù)是互質(zhì)關(guān)系（coprime）奸忽。比如堕伪，15和32沒(méi)有公因子，所以它們是互質(zhì)關(guān)系栗菜。這說(shuō)明刃跛，不是質(zhì)數(shù)也可以構(gòu)成互質(zhì)關(guān)系。

關(guān)于互質(zhì)關(guān)系苛萎，不難得到以下結(jié)論：

1.任意兩個(gè)質(zhì)數(shù)構(gòu)成互質(zhì)關(guān)系桨昙，比如13和61检号。

2.一個(gè)數(shù)是質(zhì)數(shù)，另一個(gè)數(shù)只要不是前者的倍數(shù)蛙酪，兩者就構(gòu)成互質(zhì)關(guān)系齐苛，比如3和10。

3.如果兩個(gè)數(shù)之中桂塞，較大的那個(gè)數(shù)是質(zhì)數(shù)凹蜂，則兩者構(gòu)成互質(zhì)關(guān)系，比如97和57阁危。

4. 1和任意一個(gè)自然數(shù)是都是互質(zhì)關(guān)系玛痊，比如1和99。

5. p是大于1的整數(shù)狂打，則p和p-1構(gòu)成互質(zhì)關(guān)系擂煞，比如57和56。

6. p是大于1的奇數(shù)趴乡，則p和p-2構(gòu)成互質(zhì)關(guān)系对省，比如17和15。

2晾捏、歐拉函數(shù)

請(qǐng)思考以下問(wèn)題：

任意給定正整數(shù)n蒿涎，請(qǐng)問(wèn)在小于等于n的正整數(shù)之中，有多少個(gè)與n構(gòu)成互質(zhì)關(guān)系惦辛？（比如劳秋，在1到8之中，有多少個(gè)數(shù)與8構(gòu)成互質(zhì)關(guān)系胖齐？）

計(jì)算這個(gè)值的方法就叫做歐拉函數(shù)玻淑，以φ(n)表示。在1到8之中市怎，與8形成互質(zhì)關(guān)系的是1岁忘、3、5区匠、7干像，所以 φ(n) = 4。

φ(n) 的計(jì)算方法并不復(fù)雜驰弄，但是為了得到最后那個(gè)公式麻汰，需要一步步討論。

[if !supportLists]四戚篙、[endif]密鑰生成

我們通過(guò)一個(gè)例子五鲫，來(lái)理解RSA算法。假設(shè)愛(ài)麗絲要與鮑勃進(jìn)行加密通信岔擂，她該怎么生成公鑰和私鑰呢位喂？

第一步浪耘，隨機(jī)選擇兩個(gè)不相等的質(zhì)數(shù)p和q。

愛(ài)麗絲選擇了61和53塑崖。（實(shí)際應(yīng)用中七冲，這兩個(gè)質(zhì)數(shù)越大，就越難破解规婆。）

第二步澜躺，計(jì)算p和q的乘積n。

愛(ài)麗絲就把61和53相乘抒蚜。

n = 61×53 = 3233

n的長(zhǎng)度就是密鑰長(zhǎng)度掘鄙。3233寫(xiě)成二進(jìn)制是110010100001，一共有12位嗡髓，所以這個(gè)密鑰就是12位操漠。實(shí)際應(yīng)用中，RSA密鑰一般是1024位器贩，重要場(chǎng)合則為2048位颅夺。

[if !supportLists]l?[endif]第三步朋截，計(jì)算n的歐拉函數(shù)φ(n)蛹稍。

根據(jù)公式：

φ(n) = (p-1)(q-1)

愛(ài)麗絲算出φ(3233)等于60×52，即3120部服。

第四步唆姐，隨機(jī)選擇一個(gè)整數(shù)e，條件是1< e < φ(n)廓八，且e與φ(n) 互質(zhì)奉芦。

愛(ài)麗絲就在1到3120之間，隨機(jī)選擇了17剧蹂。（實(shí)際應(yīng)用中声功，常常選擇65537。）

第五步宠叼，計(jì)算e對(duì)于φ(n)的模反元素d先巴。

所謂"模反元素"就是指有一個(gè)整數(shù)d，可以使得ed被φ(n)除的余數(shù)為1冒冬。

ed≡ 1 (mod φ(n))

這個(gè)式子等價(jià)于

ed - 1 = kφ(n) ?(k∈Z)

于是伸蚯，找到模反元素d，實(shí)質(zhì)上就是對(duì)下面這個(gè)二元一次方程求解简烤。

ex +φ(n)y = 1

已知e=17,φ(n)=3120剂邮，

17x + 3120y = 1

這個(gè)方程可以用"擴(kuò)展歐幾里得算法"求解，此處省略具體過(guò)程横侦』用龋總之绰姻，愛(ài)麗絲算出一組整數(shù)解為 (x,y)=(2753,-15)，即 d=2753引瀑。

至此所有計(jì)算完成龙宏。

第六步，將n和e封裝成公鑰伤疙，n和d封裝成私鑰银酗。

在愛(ài)麗絲的例子中，n=3233徒像，e=17黍特，d=2753，所以公鑰就是 (3233,17)锯蛀，私鑰就是（3233, 2753）灭衷。

總結(jié)，實(shí)際上就是計(jì)算n,e,d的過(guò)程

pq的作用用于求n==pq旁涤，再用 (p-1)(q-1)求φ(n)翔曲，在φ(n)范圍內(nèi)隨機(jī)選擇即為e，d==e對(duì)于φ(n)的模反元素

五劈愚、驗(yàn)證RSA算法的可靠性

公鑰公開(kāi)瞳遍，私鑰不公開(kāi)，故d被破解即RSA算法被破解菌羽。

回顧上面的密鑰生成步驟掠械，一共出現(xiàn)六個(gè)數(shù)字：

p,q,n,φ(n),e,d

這六個(gè)數(shù)字之中，公鑰用到了兩個(gè)（n和e）注祖，其余四個(gè)數(shù)字都是不公開(kāi)的猾蒂。其中最關(guān)鍵的是d，因?yàn)閚和d組成了私鑰是晨，一旦d泄漏肚菠，就等于私鑰泄漏。

那么罩缴，有無(wú)可能在已知n和e的情況下蚊逢，推導(dǎo)出d？

ed=1 (modφ(n))靴庆。只有知道e和φ(n)时捌，才能算出d。

φ(n)=(p-1)(q-1)炉抒。只有知道p和q奢讨，才能算出φ(n)。

n=pq。只有將n因數(shù)分解拿诸，才能算出p和q扒袖。

結(jié)論：如果n可以被因數(shù)分解，d就可以算出亩码，也就意味著私鑰被破解季率。

可是，大整數(shù)的因數(shù)分解描沟，是一件非常困難的事情飒泻。目前，除了暴力破解吏廉，還沒(méi)有發(fā)現(xiàn)別的有效方法泞遗。維基百科這樣寫(xiě)道："對(duì)極大整數(shù)做因數(shù)分解的難度決定了RSA算法的可靠性。換言之席覆，對(duì)一極大整數(shù)做因數(shù)分解愈困難史辙，RSA算法愈可靠。

假如有人找到一種快速因數(shù)分解的算法佩伤，那么RSA的可靠性就會(huì)極度下降聊倔。但找到這樣的算法的可能性是非常小的。今天只有短的RSA密鑰才可能被暴力破解生巡。到2008年為止耙蔑，世界上還沒(méi)有任何可靠的攻擊RSA算法的方式。

只要密鑰長(zhǎng)度足夠長(zhǎng)障斋，用RSA加密的信息實(shí)際上是不能被解破的纵潦。"

舉例來(lái)說(shuō)徐鹤，你可以對(duì)3233進(jìn)行因數(shù)分解（61×53）垃环，但是你沒(méi)法對(duì)下面這個(gè)整數(shù)進(jìn)行因數(shù)分解。

1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

它等于這樣兩個(gè)質(zhì)數(shù)的乘積：

3347807169895689878604416984821269081770479498371376856892431388982883793878002287614711652531743087737814467999489

　　　　×

36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

事實(shí)上返敬，這大概是人類(lèi)已經(jīng)分解的最大整數(shù)（232個(gè)十進(jìn)制位遂庄，768個(gè)二進(jìn)制位）。比它更大的因數(shù)分解劲赠，還沒(méi)有被報(bào)道過(guò)涛目，因此目前被破解的最長(zhǎng)RSA密鑰就是768位。

[if !supportLists]六凛澎、[endif]加密與解密

有了公鑰和密鑰霹肝，就能進(jìn)行加密和解密了。

1塑煎、加密要用公鑰 (n,e)

假設(shè)鮑勃要向愛(ài)麗絲發(fā)送加密信息m沫换，他就要用愛(ài)麗絲的公鑰 (n,e) 對(duì)m進(jìn)行加密。這里需要注意最铁，m必須是整數(shù)（字符串可以取ascii值或unicode值）讯赏，且m必須小于n垮兑。

所謂"加密"，就是算出下式的c：

m^e≡ c (mod n)

愛(ài)麗絲的公鑰是(3233, 17)漱挎，鮑勃的m假設(shè)是65系枪，那么可以算出下面的等式：

65^17≡ 2790 (mod 3233)

于是，c等于2790磕谅，鮑勃就把2790發(fā)給了愛(ài)麗絲私爷。

2、解密要用私鑰(n,d)

愛(ài)麗絲拿到鮑勃發(fā)來(lái)的2790以后膊夹，就用自己的私鑰(3233, 2753) 進(jìn)行解密当犯。可以證明割疾，下面的等式一定成立：

c^d≡ m (mod n)

也就是說(shuō)嚎卫，c的d次方除以n的余數(shù)為m。現(xiàn)在宏榕，c等于2790拓诸，私鑰是(3233, 2753)，那么麻昼，愛(ài)麗絲算出

2790^2753≡ 65 (mod 3233)

因此奠支，愛(ài)麗絲知道了鮑勃加密前的原文就是65。

至此抚芦，"加密--解密"的整個(gè)過(guò)程全部完成倍谜。

我們可以看到，如果不知道d叉抡，就沒(méi)有辦法從c求出m尔崔。而前面已經(jīng)說(shuō)過(guò)，要知道d就必須分解n褥民，這是極難做到的季春，所以RSA算法保證了通信安全。

你可能會(huì)問(wèn)消返，公鑰(n,e)只能加密小于n的整數(shù)m载弄，那么如果要加密大于n的整數(shù)，該怎么辦撵颊？有兩種解決方法：一種是把長(zhǎng)信息分割成若干段短消息宇攻，每段分別加密；另一種是先選擇一種"對(duì)稱(chēng)性加密算法"（比如DES）倡勇，用這種算法的密鑰加密信息逞刷，再用RSA公鑰加密DES密鑰。

七、私鑰解密的證明

a=b(mod c)等價(jià)于a/c的余數(shù)是b,a mod c ==b

最后亲桥，我們來(lái)證明洛心，為什么用私鑰解密，一定可以正確地得到m题篷。也就是證明下面這個(gè)式子：

c^d≡ m (mod n)

因?yàn)榇噬恚鶕?jù)加密規(guī)則

ｍ^e ≡ c (mod n)

于是，c可以寫(xiě)成下面的形式：

c = m^e - kn(h∈Z)

將c代入要我們要證明的那個(gè)解密規(guī)則：

由于(a-b)^n=a^n-C1n a^(n-1)b+C2n a^(n-2)b^2+...+(-b)^n

它等同于求證

m^(ed) ≡ m (mod n)

由于

ed ≡ 1 (mod φ(n))

所以

ed = hφ(n)+1

將ed代入：

m^(hφ(n)+1) ≡ m (mod n)

接下來(lái)番枚，分成兩種情況證明上面這個(gè)式子法严。

當(dāng)m與n互質(zhì)。

根據(jù)歐拉定理葫笼，此時(shí)

　　=====> m^φ(n)=kn+1 (k∈Z)

得到

證明(kn+1)^h*m=m(mod n)展開(kāi)即可

原式得到證明深啤。

當(dāng)m與n不是互質(zhì)關(guān)系。

此時(shí)路星，由于n等于質(zhì)數(shù)p和q的乘積溯街，所以m必然等于kp或kq。

以m = kp為例洋丐，考慮到這時(shí)k與q必然互質(zhì)呈昔，則根據(jù)歐拉定理，下面的式子成立：

(kp)^q-1 ≡ 1 (mod q)

進(jìn)一步得到

即

將它改寫(xiě)成下面的等式

這時(shí)t必然能被p整除友绝，即 t=t'p

因?yàn)閙=kp堤尾，n=pq，所以

原式得到證明迁客。

[if !supportLists]八郭宝、[endif]快速冪模算法

在講解快速冪取模算法之前，我們先將幾個(gè)必備的知識(shí)

1.對(duì)于取模運(yùn)算：

(a*b)%c=(a%c)*(b%c)%c ?

這個(gè)是成立的：也是我們實(shí)現(xiàn)快速冪的基礎(chǔ)

核心思想在于：

將大數(shù)的冪運(yùn)算拆解成了相對(duì)應(yīng)的乘法運(yùn)算掷漱，利用上面的式子粘室，始終將我們的運(yùn)算的數(shù)據(jù)量控制在c的范圍以下，這樣我們可以客服樸素的算法的缺點(diǎn)二切威，我們將計(jì)算的數(shù)據(jù)量壓縮了很大一部分育特，當(dāng)指數(shù)非常大的時(shí)候這個(gè)優(yōu)化是更加顯著的，我們用Python來(lái)做一個(gè)實(shí)驗(yàn)來(lái)看看就知道我們優(yōu)化的效率有多高了

算法實(shí)現(xiàn)：

#快速冪模運(yùn)算先朦，把b拆分為二進(jìn)制，遍歷b的二進(jìn)制犬缨，當(dāng)二進(jìn)制位為0時(shí)不計(jì)入計(jì)算

def quick_pow_mod(a, b, c):

????a = a % c

????ans = 1

#這里我們不需要考慮b<0喳魏，因?yàn)榉謹(jǐn)?shù)沒(méi)有取模運(yùn)算

????while b != 0:

#判斷b的二進(jìn)制最后一位數(shù)是不是1，是則參與計(jì)算

????????if b & 1:

????????????ans = (ans * a) % c

# ans = (ans * a) % c,理論上等價(jià)于 ans = (ans % c) * (a % c)但是不知道為什么這樣寫(xiě)會(huì)出錯(cuò)怀薛。已解決刺彩，因?yàn)榭赡茏詈笠淮蜗喑说臅r(shí)候返回一個(gè)未除盡的數(shù)

#相當(dāng)于遍歷二進(jìn)制的b

????????b >>= 1

# A(n) == A(n-1)^2，% c可以提高效率

????????a = (a % c) * (a % c)

????return ans

我們現(xiàn)在來(lái)看核心原理：

對(duì)于任何一個(gè)整數(shù)的模冪運(yùn)算

a^b%c

對(duì)于b我們可以拆成二進(jìn)制的形式 ?

b=b0+b1*2+b2*2^2+...+bn*2^n ?

這里我們的b0對(duì)應(yīng)的是b二進(jìn)制的第一位（倒數(shù)第一位），那么我們的a^b運(yùn)算就可以拆解成

a^b0*a^b1*2*...*a^(bn*2^n) ?

對(duì)于b來(lái)說(shuō)创倔，二進(jìn)制位不是0就是1嗡害，那么對(duì)于bx為0的項(xiàng)我們的計(jì)算結(jié)果是1就不用考慮了，我們真正想要的其實(shí)是b的非0二進(jìn)制位畦攘，那么假設(shè)除去了b的0的二進(jìn)制位之后我們得到的式子是

a^(bx*2^x)*...*a(bn*2^n) ?

這里我們?cè)賾?yīng)用我們一開(kāi)始提到的公式霸妹，那么我們的a^b%c運(yùn)算就可以轉(zhuǎn)化為

(a^(bx*2^x)%c）*...*(a^(bn*2^n)%c)

這樣的話(huà)，我們就很接近快速冪的本質(zhì)了知押。

(a^(bx*2^x)%c)*...*(a^(bn*2^n)%c)

我們會(huì)發(fā)現(xiàn)令

A1=(a^(bx*2^x)%c) ?

... ?

An=(a^(bn*2^n)%c) ?

這樣的話(huà)叹螟，假設(shè)bx都=1，An始終等于A(n-1)的平方台盯，依次遞推罢绽。

首先，我們會(huì)觀察到静盅，我們每次都是將b的規(guī)牧技郏縮小了2倍。

那么很顯然蒿叠，原本的樸素的時(shí)間復(fù)雜度是O(n)棚壁。快速冪的時(shí)間復(fù)雜度就是O(logn)栈虚。在數(shù)據(jù)量越大的時(shí)候袖外，者中優(yōu)化效果越明顯。

[if !supportLists]九魂务、[endif]Miller-Rabin素性測(cè)試算法

素性測(cè)試(即測(cè)試給定的數(shù)是否為素?cái)?shù))是近代密碼學(xué)中的一個(gè)非常重要的課題曼验。雖然Wilson定理(對(duì)于給定的正整數(shù)n，n是素?cái)?shù)的充要條件為)給出了一個(gè)數(shù)是素?cái)?shù)的充要條件粘姜，但根據(jù)它來(lái)素性測(cè)試所需的計(jì)算量太大鬓照，無(wú)法實(shí)現(xiàn)對(duì)較大整數(shù)的測(cè)試。目前孤紧，盡管高效的確定性的素性算法尚未找到豺裆，但已有一些隨機(jī)算法可用于素性測(cè)試及大整數(shù)的因數(shù)分解。下面描述的Miller-Rabin素性測(cè)試算法就是一個(gè)這樣的算法号显。

算法：

首先要知道費(fèi)馬定理只是n是素?cái)?shù)的必要條件臭猜。即費(fèi)馬定理不成立挠进，n一定是合數(shù)斤儿；費(fèi)馬定理成立尊浓，n可能是素?cái)?shù)橙数。接下來(lái)請(qǐng)看Miller-Rabin算法的分析過(guò)程局蚀。

x^2 = 1(mod p),p為質(zhì)數(shù)蝉娜，x小于p

x = 1或 p -1

x的偶數(shù)次方對(duì)p取余數(shù)馏予，結(jié)果可能是1^x * (p-1)^y對(duì)p取余數(shù)乐尊，即結(jié)果有可能是1，p-1劫灶，或(p-1)^k對(duì)p取模裸违，當(dāng)k為偶數(shù)時(shí)=1，當(dāng)k為奇數(shù)時(shí)=p-1

若有解本昏，3/4概率是質(zhì)數(shù)

算法實(shí)現(xiàn)：

# n為要檢驗(yàn)的大質(zhì)數(shù)供汛，a < n,k = n - 1

def miller_rabin_witness(a, n):

????if n == 1:

????????return False

????if n == 2:

????????return True

# n - 1 = m * 2^q求解 m, q,因?yàn)閚為偶數(shù)，所以必有解

????k = n - 1

# 2為 底數(shù)凛俱，n為N

????q = int(math.floor(math.log(k, 2)))

????while q > 0:

????????m = k / 2 ** q

#必須同時(shí)滿(mǎn)足兩個(gè)條件紊馏，因?yàn)閙有可能是未除盡的數(shù)

????????if k % 2 ** q == 0 and m % 2 == 1:

????????????break

????????q = q - 1

#先計(jì)算 a ^ (n-1) == 1 mod(n) 是否成立，不成立必定為合數(shù)

????if quick_pow_mod(a, n - 1, n) != 1:

????????return False

#計(jì)算第一項(xiàng)

????b1 = quick_pow_mod(a, m, n)

????for i in range(1, q + 1):

????????if b1 == n - 1 or b1 == 1:

????????????return True

#后一項(xiàng)等于前一項(xiàng)的平方mod n

????????b2 = b1 ** 2 % n

????????b1 = b2

????if b1 == 1:

????????return True

????return False

# Miller-Rabin素性檢驗(yàn)算法,檢驗(yàn)8次

def prime_test_miller_rabin(p, k):

????while k > 0:

????????a = random.randint(1, p - 1)

????????if not miller_rabin_witness(a, p):

????????????return False

????????k = k - 1

????return True

十蒲犬、[endif]擴(kuò)展歐幾里德算法

擴(kuò)展歐幾里德算法是用來(lái)在已知a, b求解一組x朱监，y，使它們滿(mǎn)足貝祖等式： ax+by = gcd(a, b) =d（解一定存在原叮，根據(jù)數(shù)論中的相關(guān)定理）赫编。

e取65537，故list[0] * s + list[1] * e = 1奋隶，list[1]為(e)mod(s)的乘法逆元擂送，也就是e對(duì)于φ(n)的模反元素d，此方程必有解唯欣。

歐幾里德算法停止的狀態(tài)是：a= gcd嘹吨， b = 0 ，那么境氢，這是否能給我們求解 x y 提供一種思路呢蟀拷？因?yàn)椋@時(shí)候萍聊，只要 a = gcd 的系數(shù)是 1 问芬，那么只要 b 的系數(shù)是 0 或者其他值（無(wú)所謂是多少，反正任何數(shù)乘以 0 都等于 0 但是a 的系數(shù)一定要是 1）寿桨，這時(shí)此衅，我們就會(huì)有： a*1 + b*0 = gcd

當(dāng)然這是最終狀態(tài)，但是我們是否可以從最終狀態(tài)反推到最初的狀態(tài)呢亭螟？

假設(shè)當(dāng)前我們要處理的是求出a和 b的最大公約數(shù)挡鞍，并求出 x 和 y 使得 a*x + b*y= gcd ，而我們已經(jīng)求出了下一個(gè)狀態(tài)：b 和 a%b 的最大公約數(shù)媒佣，并且求出了一組x1 和y1 使得： b*x1 + (a%b)*y1 = gcd 匕累， 那么這兩個(gè)相鄰的狀態(tài)之間是否存在一種關(guān)系呢？

我們知道：a%b = a - (a/b)*b（這里的 “/” 指的是整除默伍，例如 5/2=2 , 1/3=0）欢嘿， 代入b*x1 + (a%b)*y1 = gcd 那么，我們可以進(jìn)一步得到：

gcd = b*x1 + (a-(a/b)*b)*y1

= b*x1 + a*y1– (a/b)*b*y1

= a*y1 + b*(x1– a/b*y1)

對(duì)比之前我們的狀態(tài)：求一組x和 y 使得：a*x + b*y = gcd 也糊，是否發(fā)現(xiàn)了什么炼蹦？

這里：

x = y1

y = x1– a/b*y1

算法實(shí)現(xiàn)：

#這里的邏輯很復(fù)雜

#擴(kuò)展歐幾里得算法，得到結(jié)果list[0]是a的系數(shù)狸剃，list[1]是b的系數(shù) list[0] * a + list[1] * b = 1,但是有可能得到的list[1]是負(fù)數(shù)

def ex_euclid(a, b, list):

# b==0時(shí) a 為先求出最大公約數(shù)

????if b == 0:

????????list[0] = 1L

????????list[1] = 0L

????????list[2] = a

????else:

#把b作為a傳入函數(shù)掐隐，會(huì)形成一個(gè)交替的過(guò)程以 8,3為例，以次為[8,3],[3,2],[2,1],[1,0],即函數(shù)入棧時(shí)钞馁，第二個(gè)參數(shù)的值為入棧后第一個(gè)參數(shù)的值

#對(duì)應(yīng)著出棧時(shí)虑省，函數(shù)的第一個(gè)參數(shù)的值等于出棧后第二個(gè)參數(shù)

# [8, 3], [3, 2], [2, 1], [1, 0]對(duì)應(yīng)的list取值為[-1,3,1][1,-1,1][0,1,1][1,0,1]

????????ex_euclid(b, a % b, list)

????????temp = list[0]

????????# a%b = a - (a/b)*b ,b*x1 + (a%b)*y1 = gcd

# gcd = b*x1 + (a-(a/b)*b)*y1 = b*x1 + a*y1–(a/b)*b*y1 = a*y1 + b*(x1 – a/b*y1)

#故出棧時(shí)，函數(shù)的第二個(gè)參數(shù)的系數(shù)等于出棧后第一個(gè)參數(shù)的系數(shù)僧凰，出棧后第二個(gè)參數(shù)b的系數(shù)=x1 – a/b*y1

????????list[0] = list[1]

#算法 1

????????list[1] = temp - a / b * list[1]

# 3 * x1 + 2 * y1 = 1,x1已知= 1,y1 = (1 - 3 * x1 )/2

#算法2探颈，結(jié)果一致，使用時(shí)注釋temp = list[0]

????????# list[1] = (list[2] - a * list[0]) / b

#求模反元素

def mod_inverse(a, b):

????# x = list[0],y = list[1],q = list[2]

????list = [0L, 0L, 0L]

????if a < b:

????????temp = a;a = b;b = temp;

????ex_euclid(a, b, list)

#改進(jìn)训措，將負(fù)的模反元素變?yōu)檎哪７丛匚苯冢鶕?jù)公式 ed ≡ 1 (mod (s)),ed + s * k ≡ 1 (mod (s)),k為任意整數(shù)，令 k = m * e,即e的整數(shù)倍

# e(d + s * m)≡ 1 (mod (s)), abs(b) < s绩鸣，所以只加一次即可

#此處只對(duì)list[1]進(jìn)行修改

????if list[1] < 0:

????????list[1] = a + list[1]

????return list[1]

RSA實(shí)現(xiàn)流程

1.先創(chuàng)建一個(gè)包含有接近一萬(wàn)小質(zhì)數(shù)的數(shù)組怀大，隨機(jī)獲得一個(gè)30-31位數(shù)的十進(jìn)制數(shù)字num，判斷是否與數(shù)組元素都互質(zhì)呀闻，若不互質(zhì)則+2化借，直到獲得一個(gè)都互質(zhì)的整數(shù)

2.對(duì)num進(jìn)行Miller-Rabin素性檢驗(yàn)8次或者更多次。如果num沒(méi)有通過(guò)檢驗(yàn)捡多，重新隨機(jī)生成大整數(shù)重復(fù)之前步驟蓖康，否則認(rèn)為num是素?cái)?shù)。Miller-Rabin素性檢驗(yàn)有一定概率會(huì)失敗局服。