如何進行RSA算法分析和實現

如何進行RSA算法分析和實現，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

密碼學領域中，加密算法主要分為對稱加密和非對稱加密，隨著信息時代安全性要求越來越高，對稱加密因為其易被破解的原因逐漸被舍棄。而RSA算法是目前密碼學世界中比較流行的非對稱加密算法，命名是根據其發明者Rives，Shamir，Adleman三人的名字縮寫而來。講到RSA就不得不提到最近"黎曼猜想被正面后RSA算法不在安全"的傳言。帶著這個問題，講述完RSA的原理以后會順帶講一下即便"黎曼猜想"被證實是否對目前一些基于RSA算法的區塊鏈項目有影響。

## **什么是非對稱加密？**

加密就是對一段明文信息進行特殊操作產生讓人無法理解的密文，而解密就是反向前一步的操作。非對稱加密就是整個加密過程中需要兩個秘鑰：公鑰和私鑰。公鑰和私鑰是一對，對一段明文進行公鑰加密以后只有對應的私鑰能解密。大致過程如下：


## **RSA加密**

RSA加密的過程定義的公式如下：

明文=密文*D**m**o**d**N*

簡單說，明文的E次方對N取模的結果就是密文。相信到這里讀者的疑問都是E和N到底是什么？其實這里的E和N 就是RSA加密的公鑰，它們的用法我已經介紹過了，通常暴露給其他使用者的是E和N的組合。

## **RSA解密**

RSA解密的過程定義如下：

明文=密文*D**m**o**d**N*

對密文取D次方，在對N取模得到的結果就是明文。這里的D和N的組合就是RSA算法的秘鑰，這一步的N和加密用到的N是同一個數。

## **RSA 生產密鑰對**

通過上面的兩個公式可以看到，只要知道E,D,N的值就很容易實現一次RSA加解密的過程。下面介紹一下這三個數生成的過程：

\1. 首先準備兩個很大的質數p，q。這兩個數的選擇依據：如果p,q很大，算法的安全性會很高，但是相對應的計算時間會增長。一般編程語言都有對應的庫用來生成這樣的數據。計算p和q的乘積就得到了值N。

\2. 根據歐拉函數，不大于N且與N互質的整數個數有(p-1)(q-1)個。φ(n) =(q-1)*(p-1);隨機選擇一個整數e，要求是φ(n)>e>1，并且e與φ(n)互質，一般選擇65537（如果范圍允許的話）。

\3. 前兩步生成了公鑰，下面生成私鑰需要的D：

D需要滿足條件：

1<*D*<*φ*(*n*);(*E*×*D*)*m**o**d**φ*(*n*)=1

D的值就是 （ φ(n)的倍數+1）/E；

到這一步就簡單的實現RSA算法的加解密過程。

## **RSA算法安全性**

相信通過上面的過程讀者應該能發現，RSA運用了大量的質數運算，這也正是RSA算法的核心：當p和q是一個大素數的時候，從它們的積pq去分解因子p和q，這是一個公認的數學難題。所以當p,q的值足夠大的時候，是很難根據p和q的乘積計算出p和q的值的。注意這里用的是”很難“，這也是RSA算法的缺陷，沒有任何理論或概率方面的算法證明RSA算法的破解難度，所以其安全性保障也僅僅在于此，并沒有如之前講SHA256時類比宇宙中原子數量來證明碰撞的難度。RSA的安全性問題還在于這些因式分解算法隨著被因式分解的數字變得越大而變得越有效率。也就是說RSA算法的安全性在一定程度上依賴于私鑰的長短，而不是其本身的算法。

## **RSA算法和“黎曼猜想”**

在文章的開頭講述了黎曼猜想，今年9月24號，英國著名數學家邁克爾·阿提亞提出了他驗證黎曼猜想的思路。我們這里不打算花費大量的篇幅介紹”黎曼猜想“和證明過程。只是希望從本質上告訴讀者，”黎曼猜想“的證實和RSA算法的破解是兩碼事。總結起來一句話就是：”黎曼猜想“被證實的結果是證明了素數的分布是有規律的，它能夠幫助我們快速的定位素數的位置。然而想要破解RSA算法的本質是對兩個大質數的乘積進行因式分解，這個本質上跟”黎曼猜想“的被證實沒有關系。

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。