RSA密碼算法的研究與改進

周偉

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

關(guān)鍵詞 RSA；歐幾里德算法；大整數(shù)運算

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

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

1 RSA傳統(tǒng)算法概述

2 RSA算法的分析與改進

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

歐幾里德算法是按照輾轉(zhuǎn)相除的思想計算兩個正整數(shù)最大公約數(shù)的算法。

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

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

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

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

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

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

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

第一步在數(shù)組i中，2是42和12的因子，故gcd（42，12）=2* gcd（21，6）；第二步在數(shù)組i中，3是21和6的因子，故gcd（42，12）=2* gcd（21，6）=2*3*gcd（7，2）；第三步在數(shù)組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。

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

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

參考文獻

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