RSA密碼算法的研究與改進(jìn)

周偉

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

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

中圖分類號(hào) TP3 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào) 2095-6363（2017）14-0089-02

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

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

2 RSA算法的分析與改進(jìn)

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)

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