RSA密碼算法的研究與改進

周偉

摘 要 隨著計算機在全世界普及，網絡技術已經進一步融入日常生產工作，成為了信息化時代交流和反饋的重要渠道。所以，網絡技術的不斷發展帶來了人們生活的便利化，但是計算機系統的安全保障在網絡技術的發展下受到了更大的威脅，因此需要不斷完善和發展信息保密技術。本文著重探析RSA密碼體制原理。RSA算法是一種安全可靠的密碼算法，一定程度上可以免疫絕大部分密碼攻擊手段。人們通過不斷改進和完善進一步提高了RSA密碼算法的安全性。但伴隨先進技術的層出不窮以及網絡科技的高速發展，RSA密碼體制也面臨著更多挑戰。

關鍵詞 RSA；歐幾里德算法；大整數運算

中圖分類號 TP3 文獻標識碼 A 文章編號 2095-6363（2017）14-0089-02

在信息技術高速發展的時代，海量的信息不再是確切存在的實物，而是由存在的實體通過計算機轉換成了數字代碼。如果沒有對這些數字代碼采取適當的保密手段，很容易發生數字代碼被人截獲被破譯者利用。在計算機網絡的發展過程中，人們在信息安全理論中引進了密碼學理論，通過各種形式的加密以保證信息的可靠傳輸。因此，計算機系統安全以及信息傳輸安全已經離不開密碼學理論。

1 RSA傳統算法概述

2 RSA算法的分析與改進

RSA算法的密鑰中的e加密密鑰是和互素的任何數字，由此我們可先行選取一個隨機的大數，然后檢驗這個數是否和互素，如果不是互素，則再次循環這兩個步驟，到與互素停止。這里檢驗兩個大數是否互素就需要考慮他們的最大公約數，自然而然就需要運用到求最大公約數的歐幾里德法[1]。

歐幾里德算法是按照輾轉相除的思想計算兩個正整數最大公約數的算法。

歐幾里德算法的優點：綜合上面的證明可知，求模運算計算得到余數r是最大公約數c的倍數，因為他們的倍數關系簡化了最大公約數冗長繁復的計算。與此同時，不需要進行試商這樣的運算，只需要對余數進行相應的計算就可以直接得到最大公約數，極大地提高了運算的效率。

歐幾里德算法的缺點：在大整數計算的時候歐幾里德算法會出現很大的缺陷。考慮到現行的運行系統和硬件平臺，操作過程中的整數一般較大的也就只有64位，對于這些整數，他們之間的求模運算是不算太難。但是對于位數更多的素數，像這樣的計算過程就只能落到用戶肩上，由用戶自己來設計。但是這個過程不僅復雜，而且會耗費很大一部分CPU時間。而對于現現今情況下的密碼算法，要求計算128位以上的素數的情況層出不窮，所以在這樣的程序設計急需要摒棄除法運算和取模運算。

輾轉相減的方法（尼考曼徹斯法）是按照輾轉相減的思想計算兩個整數最大公約數的算法。該算法描述為：1）將兩個正整數相減；2）輾轉相減（大一點的數就作被減數）；3）計算得到的差和減數的最大公約數就是原來要求的兩個數的最大公約數。

下面舉個例子：取兩個自然數42和12，用大一點的數減去小一點的數，（42，12）到（30，12）到（18，12） 到（6，12），此時，6小于12，就要做一次交換，把大數12作為被減數，即（12，6）到（6，6），再做一次相減，6—6的結果等于0，這樣也就求出了42和12的最大公約數6。

而這個方法在面對大素數的時候也會顯得過分的冗長，例如兩個128位的大數相減其結果可能還為128位的大數，這樣就不利于算法的運行。

考慮到輾轉相除法對于大整數除法運算的難度以及輾轉相減法對于大整數減法的繁復，本文考慮將兩種方法結合起來，對歐幾里德算法求最大公約數進行改進，希望達到簡化算法復雜程度的效果。

例：以gcd（42，12）為例：

第一步在數組i中，2是42和12的因子，故gcd（42，12）=2* gcd（21，6）；第二步在數組i中，3是21和6的因子，故gcd（42，12）=2* gcd（21，6）=2*3*gcd（7，2）；第三步在數組i中，2是2的因子但不是7的因子，7是7的因子但不是2的因子，故gcd（42，12）=2* gcd（21，6）=2*3*gcd（7，2）=2*3*gcd（1，1）=2*3*1=6。

這種方法簡化了大整數除法的復雜性，提取大整數的小因子發揮了除法的在運算中的跳躍性，如果沒有辦法從大數中提取因子，那就采用輾轉相減的方法進行處理，比之原來的歐幾里德算法直接大整數相除在計算上有了極大的簡化。

改進后的歐幾里德法通過C語言編程計算五組數123456和987456、125478和369854、125478和325874、1254789和36541、235478和124785最大公約數所需時間為24.348秒，而傳統歐幾里德法計算五組最大公約數所需要的時間為63.795秒。由實驗結果顯然可以得到以下結論，本文改進后的歐幾里德算法確實優化了大整數除法耗時長的缺點。從而提高了RSA密碼算法的速度。

參考文獻

[1]閔嗣鶴，嚴士健.初等數論[M].北京：高等教育出版社，1982.