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

2，計算n=pq

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

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

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

詳細解析如下：

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

開始前，首先要選擇兩個大的素數(shù)，記為p和q。根據(jù)當今求解大數(shù)因子的技術(shù)水平，這兩個數(shù)應(yīng)該至少有200位，這們在實踐中才可以認為是安全的。

然后，開始計算n:

n=pq

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

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

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

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

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

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

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

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

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

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

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

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

只有當兩個整數(shù)的唯一公因子為1時，才說這兩個整數(shù)是互素的。例如，φ(8)=4，因為一共只用4個比8小的整數(shù)是互素的，它們是1，3，5，7。

歐拉方程有兩個性質(zhì)對RSA算法來說是特別重要的。

第一，當n是素數(shù)時，φ(n)=n-1。這是由于n的唯一因子是1和n，因此，n與之前的所有n-1個正整數(shù)都是互素的。

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

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

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

調(diào)整之后得到的等式非常強大。因為對于某些等式c=memodn，該等于可以讓我們找出一個d的值，使得cdmodn=m。

這就是RSA算法中允許加密數(shù)據(jù)，之后再解密回原文的恒等式?？梢园凑杖缦路绞奖硎荆?/p>

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

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

d=e-1modφ(n)

我們可以得到這樣的簡化形式，因為(φ(n)+1)modφ(n)=(φ(n)+1)-φ(n)=1?？梢杂萌我獾恼麛?shù)替代φ(n)來證明等式成立。注意這個方程式同之前計算密鑰的過程中得出d的推導(dǎo)式之間的相似之處。這提供了一種通過e和n來計算d的方法。當然了，e和n是公開的，對于攻擊者來說是事先可知的，因此就有人問，這難道不是給了攻擊者相同的機會來計算出私鑰嗎?討論到這里，是時候來探討一下RSA算法安全性保障的由來了。

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

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

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

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