1，隨機(jī)選取兩個(gè)質(zhì)數(shù)p和q

2，計(jì)算n=pq

3，選取一個(gè)與?(n)互質(zhì)的小奇數(shù)e，?(n)=(p-1)(q-1)

4，對(duì)模?(n)，計(jì)算e的乘法逆元d，即滿足(e*d)mod?(n)=1

5，公鑰(e,n)，私鑰(d,n)

詳細(xì)解析如下：

RSA中的公鑰和私鑰需要結(jié)合在一起工作。公鑰用來(lái)對(duì)數(shù)據(jù)塊加密，之后，只有對(duì)應(yīng)的私鑰才能用來(lái)解密。生成密鑰時(shí)，需要遵循幾個(gè)步驟以確保公鑰和私鑰的這種關(guān)系能夠正常工作。這些步驟也確保沒(méi)有實(shí)際方法能夠從一個(gè)密鑰推出另一個(gè)。

開(kāi)始前，首先要選擇兩個(gè)大的素?cái)?shù)，記為p和q。根據(jù)當(dāng)今求解大數(shù)因子的技術(shù)水平，這兩個(gè)數(shù)應(yīng)該至少有200位，這們?cè)趯?shí)踐中才可以認(rèn)為是安全的。

然后，開(kāi)始計(jì)算n:

n=pq

接下來(lái)，選擇一個(gè)小的奇數(shù)e，它將成為公鑰的一部分。選擇e最需要考慮的重點(diǎn)是它與(p-1)(q-1)不能有相同的因子。換句話說(shuō)，e與(p-1)(q-1)是互為素?cái)?shù)關(guān)系的。比如，如果p=11而q=19，那么n=11X19=209。這里選擇e=17，因?yàn)?p-1)(q-1)=10X18=180，而17和180沒(méi)有相同的因子。通常選擇3、17、65、537作為e的值。使用這些值不會(huì)對(duì)RSA的安全性造成影響，因?yàn)榻饷軘?shù)據(jù)還需要用到私鑰。

一旦為e選擇了一個(gè)值，接下來(lái)開(kāi)始計(jì)算相對(duì)應(yīng)的值d，d將成為私鑰的一部分。d的值就是計(jì)算e的倒數(shù)對(duì)(p-1)(q-1)的取模結(jié)果，公式如下：

d=e-1mod(p-1)(q-1)

這里d和e是模乘法逆元的關(guān)系。

思考一下這個(gè)問(wèn)題：當(dāng)d為多少時(shí)可以滿足edmod(p-1)(q-1)=1?比如在等式17dmod180=1中，d的一個(gè)可能值是53。其他的可能值是233、413、593等。在實(shí)踐中，可以利用歐幾里德算法來(lái)計(jì)算模乘法逆元。這里就不再展開(kāi)。

現(xiàn)在有了e和d的值，將(e,n)作為公鑰P，將(d,n)作為私鑰S并保持其不可見(jiàn)。表示為：

P=(e,n),S=(d,n)

加密方使用P來(lái)加密數(shù)據(jù)，解密方使用S來(lái)解密。為了防止就算有人知道了P也無(wú)法推算出S，必須保證p和q的值絕對(duì)不能暴露。

P和S結(jié)合在一起提供的安全性來(lái)自于一個(gè)事實(shí)，那就是乘法是一種很好的單向函數(shù)。

單向函數(shù)是加密技術(shù)的基礎(chǔ)。簡(jiǎn)單的說(shuō)，單向函數(shù)就是在一個(gè)方向上能夠很容易算出結(jié)果，但反向推導(dǎo)則是不切實(shí)際的。比如，在RSA算法中，計(jì)算p和q的成績(jī)是一種單向函數(shù)，因?yàn)楸M管計(jì)算p和q的成績(jī)很容易，但將n反向因子分解為p和q則是極其耗時(shí)的。這里，選擇的p和q的值要足夠大才可以。

計(jì)算P和S的步驟起源于歐拉函數(shù)中的一些有趣性質(zhì)。特別是，這些性質(zhì)允許對(duì)模冪運(yùn)算做一些有用的操作。

歐拉函數(shù)記為φ(n)，定義所有小于n的正整數(shù)里和n互素的整數(shù)的個(gè)數(shù)。

只有當(dāng)兩個(gè)整數(shù)的唯一公因子為1時(shí)，才說(shuō)這兩個(gè)整數(shù)是互素的。例如，φ(8)=4，因?yàn)橐还仓挥?個(gè)比8小的整數(shù)是互素的，它們是1，3，5，7。

歐拉方程有兩個(gè)性質(zhì)對(duì)RSA算法來(lái)說(shuō)是特別重要的。

第一，當(dāng)n是素?cái)?shù)時(shí)，φ(n)=n-1。這是由于n的唯一因子是1和n，因此，n與之前的所有n-1個(gè)正整數(shù)都是互素的。

另一個(gè)有趣的性質(zhì)是對(duì)于任意小于n且與n互素的正整數(shù)a，都有aφ(n)modn=1。例如，14mod8=1,34mod8=1,54mod8=1,74mod8=1。對(duì)上述方程兩邊都乘以a，得到：

(a)(aφ(n)modn)=a，或者aφ(n)+1modn=a

因此，可以得到15mod8=1,35mod8=3,55mod8=5,75mod8=7。

調(diào)整之后得到的等式非常強(qiáng)大。因?yàn)閷?duì)于某些等式c=memodn，該等于可以讓我們找出一個(gè)d的值，使得cdmodn=m。

這就是RSA算法中允許加密數(shù)據(jù)，之后再解密回原文的恒等式。可以按照如下方式表示：

cdmodn=(me)dmodn=medmodn=mφ(n)+1modn=mmodn

歐拉函數(shù)和指數(shù)間的關(guān)系保證了加密的任意數(shù)據(jù)都能夠唯一地解密回來(lái)。為了找出d的值，解方程d=e-1φ(n)+1。不巧的是，對(duì)于方程d=e-1φ(n)+1不一定總是有整數(shù)解。為了解決這種問(wèn)題，轉(zhuǎn)而計(jì)算dmodφ(n)的值。換句話說(shuō)，d=(e-1φ(n)+1)modφ(n)，可以簡(jiǎn)化為：

d=e-1modφ(n)

我們可以得到這樣的簡(jiǎn)化形式，因?yàn)?φ(n)+1)modφ(n)=(φ(n)+1)-φ(n)=1。可以用任意的正整數(shù)替代φ(n)來(lái)證明等式成立。注意這個(gè)方程式同之前計(jì)算密鑰的過(guò)程中得出d的推導(dǎo)式之間的相似之處。這提供了一種通過(guò)e和n來(lái)計(jì)算d的方法。當(dāng)然了，e和n是公開(kāi)的，對(duì)于攻擊者來(lái)說(shuō)是事先可知的，因此就有人問(wèn)，這難道不是給了攻擊者相同的機(jī)會(huì)來(lái)計(jì)算出私鑰嗎?討論到這里，是時(shí)候來(lái)探討一下RSA算法安全性保障的由來(lái)了。

RSA算法的安全性保障來(lái)自一個(gè)重要的事實(shí)，那就是歐拉函數(shù)是乘法性質(zhì)的。這意味著如果p和q是互素的，那么有φ(pq)=φ(p)φ(q)。因此，如果有兩個(gè)素?cái)?shù)p和q，且n=p*q，則φ(n)=(p-1)(q-1)，而且最重要的是：

d=e-1mod(p-1)(q-1)

因此，盡管攻擊者可能知道了e和n的值，為了計(jì)算出d必須知道φ(n)，而這又必須同時(shí)得到p和q的值才能辦到。由于p和q是不可知的，因此攻擊者只能計(jì)算n的因子，只要給出的p和q的值足夠大，這就是一個(gè)相當(dāng)耗費(fèi)時(shí)間的過(guò)程。

以上內(nèi)容為大家介紹了pythonRSA加密算法過(guò)程，希望對(duì)大家有所幫助，如果想要了解更多Python相關(guān)知識(shí)，請(qǐng)關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。