1，隨機選取兩個質數p和q

2，計算n=pq

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

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

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

詳細解析如下：

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

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

然后，開始計算n:

n=pq

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

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

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

這里d和e是模乘法逆元的關系。

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

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

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

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

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

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

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

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

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

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

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

另一個有趣的性質是對于任意小于n且與n互素的正整數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。

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

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

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

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

d=e-1modφ(n)

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

RSA算法的安全性保障來自一個重要的事實，那就是歐拉函數是乘法性質的。這意味著如果p和q是互素的，那么有φ(pq)=φ(p)φ(q)。因此，如果有兩個素數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的值足夠大，這就是一個相當耗費時間的過程。

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