周偉

摘 要 隨著計算機(jī)在全世界普及，網(wǎng)絡(luò)技術(shù)已經(jīng)進(jìn)一步融入日常生產(chǎn)工作，成為了信息化時代交流和反饋的重要渠道。所以，網(wǎng)絡(luò)技術(shù)的不斷發(fā)展帶來了人們生活的便利化，但是計算機(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)算

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

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

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

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

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

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

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

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

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

下面舉個例子：取兩個自然數(shù)42和12，用大一點(diǎn)的數(shù)減去小一點(diǎn)的數(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ù)，這樣就不利于算法的運(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ìn)后的歐幾里德法通過C語言編程計算五組數(shù)123456和987456、125478和369854、125478和325874、1254789和36541、235478和124785最大公約數(shù)所需時間為24.348秒，而傳統(tǒng)歐幾里德法計算五組最大公約數(shù)所需要的時間為63.795秒。由實(shí)驗結(jié)果顯然可以得到以下結(jié)論，本文改進(jìn)后的歐幾里德算法確實(shí)優(yōu)化了大整數(shù)除法耗時長的缺點(diǎn)。從而提高了RSA密碼算法的速度。

參考文獻(xiàn)

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