[[357279]]

微信公眾號：計算機(jī)與網(wǎng)絡(luò)安全

ID：Computer-network

傳統(tǒng)的加密方法是加密、解密使用同樣的密鑰，由發(fā)送者和接收者分別保存，在加密和解密時使用。采用這種方法的主要問題是密鑰的生成、注入、存儲、管理、分發(fā)等很復(fù)雜，特別是隨著用戶數(shù)量的增加，密鑰的需求量成倍增加。在網(wǎng)絡(luò)通信中，大量密鑰的分配是一個難以解決的問題。

為了解決常規(guī)密鑰密碼體制的密鑰分配問題，滿足用戶對數(shù)字簽名的需求，1976年，美國學(xué)者Diffie和Hellman發(fā)表了著名論文《密碼學(xué)的新方向》，提出了建立“公開密鑰密碼體制”：若用戶A有加密密鑰ka(公開)，不同于解密密鑰ka′(保密)，要求ka的公開不影響ka′的安全;若用戶B要向用戶A保密傳送明文m，則可查用戶A的公開密鑰ka，若用ka加密得到密文c，則用戶A收到c后，用只有用戶A自己才掌握的解密密鑰ka′對c進(jìn)行解密以得到m。

1978年，美國麻省理工學(xué)院的研究小組成員李維斯特(Rivest)、沙米爾(Shamir)和艾德曼(Adleman)(如圖1所示)提出了一種基于公鑰密碼體制的優(yōu)秀加密算法——RSA算法。RSA算法是第一個比較完善的公開密鑰算法，它既能用于加密，也能用于數(shù)字簽名。RSA算法以它的三個發(fā)明者Rivest，Shamir，Adleman的名字首字母命名，這個算法經(jīng)受住了多年深入的密碼分析。密碼分析者既不能證明也不能否定RSA算法的安全性，但這恰恰說明該算法有一定的可信性。目前，RSA算法已經(jīng)成為最流行的公開密鑰算法。

[[357280]]

圖1 RSA公開密鑰算法的發(fā)明人

注：從左到右依次為李維斯特、沙米爾和艾德曼，照片拍攝于1978年

1、RSA算法原理

RSA是最著名且應(yīng)用最廣泛的公開密鑰算法，可以同時用于加密和數(shù)字簽名。國際標(biāo)準(zhǔn)化組織(International Organization for Standardization，ISO)在1992年頒布的國際標(biāo)準(zhǔn)X.509中，將RSA算法正式納入國際標(biāo)準(zhǔn)。1999年，美國參議院通過立法，規(guī)定了數(shù)字簽名與手寫簽名的文件、郵件在美國具有同等的法律效力。

RSA算法是一種分組密碼體制算法，它的保密強(qiáng)度是建立在具有大素數(shù)因子的合數(shù)上的，其因子分解較困難。RSA算法的公鑰和私鑰選擇一對大素數(shù)(100到200位十進(jìn)制數(shù)或更大的數(shù))的函數(shù)。而從一個公鑰和密文恢復(fù)出明文的難度，等價于分解兩個大素數(shù)之積(這是公認(rèn)的數(shù)學(xué)難題)，但是否為NP問題尚不確定。表1給出了大數(shù)分解難度的例子。

表1 大數(shù)分解難度舉例

RSA算法體制包括：一個公開密鑰KU={e，n}，一個私有密鑰KR={d，n}。其公鑰、私鑰的組成以及加密、解密的公式如表2所示。

表2 RSA算法

① 有可能找到e、d、n的值，使得對所有的M

② 對于所有的M

③ 在給定e和n時，計算出d是不可行的。

(1)RSA算法的數(shù)論基礎(chǔ)

下面介紹RSA算法中需要使用的幾個術(shù)語。

1)素數(shù)

素數(shù)又稱為質(zhì)數(shù)，是指在大于1的自然數(shù)中，除了1和此數(shù)自身外，不能被其他自然數(shù)整除的數(shù)。例如，15=3×5，所以15不是素數(shù);又如，12=6×2=4×3，所以12也不是素數(shù)。而13除了等于13×1以外，不能再表示為其他任何兩個整數(shù)的乘積，所以13是一個素數(shù)。

2)互為素數(shù)

公約數(shù)只有1的兩個自然數(shù)，叫作互質(zhì)數(shù)，即互素數(shù)。兩個自然數(shù)是否互為素數(shù)的判別方法主要有以下8種(不限于此)。

① 兩個質(zhì)數(shù)一定是互質(zhì)數(shù)，例如，2與7，13與19。

② 一個質(zhì)數(shù)如果不能整除另一個合數(shù)，那么這兩個數(shù)為互質(zhì)數(shù)，例如，3與10，5與26。

③ 1不是質(zhì)數(shù)也不是合數(shù)，它和任何一個自然數(shù)都是互質(zhì)數(shù)，例如，1和9908。

④ 相鄰的兩個自然數(shù)是互質(zhì)數(shù)，例如，15與16。

⑤ 相鄰的兩個奇數(shù)是互質(zhì)數(shù)，例如，49與51。

⑥ 大數(shù)是質(zhì)數(shù)的兩個數(shù)是互質(zhì)數(shù)，例如，97與88。

⑦ 小數(shù)是質(zhì)數(shù)，大數(shù)不是小數(shù)的倍數(shù)的兩個數(shù)是互質(zhì)數(shù)，例如，7與16。

⑧ 兩個數(shù)都是合數(shù)(兩數(shù)之差又較大)，小數(shù)所有的質(zhì)因數(shù)都不是大數(shù)的約數(shù)，這兩個數(shù)是互質(zhì)數(shù)。例如，357與715，357=3×7×17，而3、7和17都不是715的約數(shù)，所以這兩個數(shù)為互質(zhì)數(shù)。

3)模運(yùn)算

模運(yùn)算是整數(shù)運(yùn)算，有一個整數(shù)m，以n為模做模運(yùn)算，即mmod n。令m被n整除，只取所得的余數(shù)作為結(jié)果，就叫作模運(yùn)算。例如，10 mod 3=1，26 mod 6=2，28 mod 2=0等。

模運(yùn)算有以下性質(zhì)。

① 同余性：若amod n=bmod n，則正整數(shù)a與b同余。

② 對稱性：若a=b mod n，則b=amod n。

③ 傳遞性：若a=b mod n，b=cmod n，則a=cmod n。

4)Euler函數(shù)

任意給定正整數(shù)n，計算在小于或等于n的正整數(shù)之中有多少個與n能構(gòu)成互質(zhì)關(guān)系的方法叫作歐拉函數(shù)，以φ(n)表示。例如，φ(8)=4，這是因為在1~8之中與8能形成互質(zhì)關(guān)系的數(shù)有4個：1，3，5，7。

φ(n)的計算方法并不復(fù)雜，下面分情況對其進(jìn)行討論。

第一種情況：如果n=1，則φ(1)=1，因為1與任何數(shù)(包括其自身)都能構(gòu)成互質(zhì)關(guān)系。

第二種情況：如果n是素數(shù)，則φ(n)=n-1，因為質(zhì)數(shù)與每個小于它的數(shù)都能構(gòu)成互質(zhì)關(guān)系。

第三種情況：如果n是素數(shù)的某一個次方，如n=pk，p為素數(shù)，k≥1，則

φ(pk)=pk-pk-1

例如，φ(8)=φ(23)=23-22=4。這是因為只有當(dāng)一個數(shù)不包含素數(shù)p時，才能與n互質(zhì)。而包含素數(shù)p的數(shù)一共有pk-1個，即1×p、2×p、…、pk-1×p。

第四種情況：如果n可以分解成兩個互質(zhì)的整數(shù)之積，例如，n=p1×p2，則φ(n)=φ(p1p2)=φ(p1)φ(p2)，即積的歐拉函數(shù)等于各個因子的歐拉函數(shù)之積。例如，φ(56)=φ(7×8)=φ(7)×φ(8)=6×4=24。

第五種情況：對于任意大于1的整數(shù)，若其可以寫成一系列素數(shù)的積，如

，則有

。

5)歐拉定理

如果兩個正整數(shù)a和n互質(zhì)，則n的歐拉函數(shù)φ(n)滿足：

aφ(n)≡1(mod n)

即a的φ(n)次方減去1，被n整除。例如，3和7互質(zhì)，φ(7)=6，(36-1)/7=104。

如果正整數(shù)a與質(zhì)數(shù)p互質(zhì)，則因為φ(p)=p-1，所以歐拉函數(shù)可寫成：

ap−1≡1(mod p)

這就是著名的費(fèi)馬小定理(Fermat Theory)。

6)費(fèi)馬小定理

若m是素數(shù)，且a不是m的倍數(shù)，則am-1 mod m=1。或者，若m是素數(shù)，則ammod m=a。例如，46mod 7=4096 mod 7=1，47mod 7=16384 mod 7=4。

推論：對于互素的a和n，有aφ(n)mod n=1。

(2)素數(shù)的產(chǎn)生與檢驗

首先來介紹素數(shù)的簡單判定算法。在C程序設(shè)計中，素數(shù)的判定算法為：給定一個正整數(shù)n，用2到sqrt(n)之間的所有整數(shù)去除n，如果可以整除，則n不是素數(shù)，如果不可以整除，則n是素數(shù)。這個算法的時間復(fù)雜度為O(sqrt(n))，算法描述簡單，實(shí)現(xiàn)也不困難。但是，這個算法對于位數(shù)較大的素數(shù)判定就顯得力不從心了。

目前，適用于RSA算法的最實(shí)用的素數(shù)產(chǎn)生辦法是概率測試法。該法的思想是隨機(jī)產(chǎn)生一個大奇數(shù)，然后測試其是否滿足條件，若滿足，則該大奇數(shù)可能是素數(shù)，否則，其是合數(shù)。

由于素數(shù)有無窮多個，因此判定一個整數(shù)是不是素數(shù)一直是一個大難題，威爾遜定理(Wilson's Theorem)就是其中的一種判定方法。

威爾遜定理：若正整數(shù)n>1，則n是一個素數(shù)當(dāng)且僅當(dāng)(n-1)! ≡ -1(mod n)。

雖然說威爾遜定理給出了素數(shù)的等價命題，但是由于階乘的增長速度太快(如13!為60多億)，因此其實(shí)際操作價值不高。由此提出了概率檢驗方法。

米勒-拉賓素性檢驗(Miller-Rabin Prime Test)是一種典型的概率檢驗方法。可以證明單次Miller-Rabin的正確概率大于3/4，我們重復(fù)若干次就可以增大這個概率。Miller-Rabin雖然有一定的概率出錯，但實(shí)踐證明，在重復(fù)20次的情況下，107以內(nèi)的質(zhì)數(shù)不會判斷出錯。

2、RSA加解密算法過程

(1)RSA加密算法過程

RSA加密算法的過程如下：

① 取兩個隨機(jī)大素數(shù)p和q(保密);

② 計算公開的模數(shù)n=p×q(公開);

③ 計算秘密的歐拉函數(shù)φ(n)=(p-1)×(q-1)(保密)，丟棄p和q，不要讓任何人知道;

④ 隨機(jī)選取整數(shù)e，使其滿足gcd(e,φ(n))=1(公開e加密密鑰);

⑤ 計算d，使其滿足de≡1(mod φ(n))(保密d解密密鑰);

⑥ 將明文X按模為r自乘e次冪以完成加密操作，從而產(chǎn)生密文Y(X、Y值在0到n-1范圍內(nèi))，即Y=Xemod n;

⑦ 解密，將密文Y按模為n自乘d次冪，得X=Ydmod n。

在RSA加(解)密算法實(shí)現(xiàn)過程中，主要的運(yùn)算量是計算模的逆元以及模指數(shù)，通常情況下，計算模的逆元時會采用擴(kuò)展的歐幾里德算法。

(2)RSA解密算法過程

由于指數(shù)較大，因此RSA解密過程比較耗時，但利用孫子定理(Chinese Remainder Theorem，CRT)可提高解密算法效率。CRT對RSA解密算法生成兩個解密方程(利用M=Cdmod pq)，即：M1=Mmod p=(Cmod p)d mod (p-1)mod p，M2=Mmod q=(Cmod q)d mod (q-1)mod q。

解方程M=M1mod p和M=M2mod q，可求得其具有唯一解。

3、RSA算法應(yīng)用

(1)RSA用于數(shù)字簽名

① 簽名：對任意消息m∈M，用戶使用自己的私鑰簽名如下：S≡md(mod n)，進(jìn)而可以得到簽名的消息(m, S)。

② 驗證簽名：由該用戶的公開密鑰(e, n)，驗證m≡Se(mod n)是否成立。

(2)RSA加密算法實(shí)例

可以通過一個簡單的例子來理解RSA的工作原理。為了便于計算，在以下實(shí)例中只選取小數(shù)值的素數(shù)p, q以及e，假設(shè)用戶A需要將明文“key”通過RSA加密后傳遞給用戶B，過程如下。

1)設(shè)計公私密鑰(e,n)和(d,n)

令p=3，q=11，得出n=p×q=3×11=33;f(n)=(p-1)(q-1)=2×10=20;取e=3(3與20互質(zhì))，則e×d≡1 mod f(n)，即3×d≡1 mod 20。d的取值可以用試算的辦法來確定。試算結(jié)果如表3所示。

表3 d的取值試算結(jié)果

通過試算得出，當(dāng)d=7時，e×d≡1 mod f(n)同余等式成立。因此，可令d=7，從而可以設(shè)計出一對公私密鑰，加密密鑰(公鑰)為：KU=(e,n)=(3,33)，解密密鑰(私鑰)為：KR=(d,n)=(7,33)。

2)英文數(shù)字化

將明文信息數(shù)字化，并將其以每塊兩個數(shù)字進(jìn)行分組。假定明文英文字母編碼表為按字母順序排列的數(shù)值，如表4所示。

表4 明文英文字母編碼表

則可得到分組后的key的明文信息為：11，05，25。

3)明文加密

用戶加密密鑰(3,33)將數(shù)字化明文分組信息加密成密文。由C≡Me(mod n)得：

C1=(M1)d(modn)=113(mod33)=11

C2=(M2)d(modn)=053(mod33)=26

C3=(M3)d(modn)=253(mod33)=16

因此，得到相應(yīng)的密文信息為：11，26，16。

4)密文解密

用戶B收到密文后，若要將其解密，則只需要計算M≡Cd(mod n)，即：

M1=(C1)d(modn)=117(mod33)=11

M2=(C2)d(modn)=317(mod33)=05

M3=(C3)d(modn)=167(mod33)=25

用戶B得到的明文信息為：11，05，25。根據(jù)上面的編碼表將其轉(zhuǎn)換為英文，即可得到恢復(fù)后的原文“key”。

當(dāng)然，實(shí)際運(yùn)用要比這復(fù)雜得多。由于RSA算法的公鑰私鑰的長度(模長度)須達(dá)到1024位甚至2048位才能保證安全，因此，p、q、e的選取、公鑰私鑰的生成、加密解密模指數(shù)的運(yùn)算都有一定的計算程序，需要依賴計算機(jī)的高速計算能力來完成。

4、RSA加解密算法的安全性

在RSA密碼應(yīng)用中，公鑰KU是被公開的，即e和n的數(shù)值可以被第三方竊聽者得到。破解RSA密碼的關(guān)鍵在于從已知的e和n的數(shù)值(n等于pq)中求出d的數(shù)值，從而得到私鑰以破解密文。從上文中的公式：d≡e-1(mod((p-1)(q-1)))或de≡1(mod((p-1)(q-1)))可以看出，密碼破解的實(shí)質(zhì)問題是：從pq這一數(shù)值求出(p-1)和(q-1)。換句話說，只要求出p和q的值，就能求出d的值進(jìn)而得到私鑰。

若p和q是大素數(shù)，則從它們的積pq去分解因子p和q，就是一個公認(rèn)的數(shù)學(xué)難題。例如，當(dāng)pq大到1024位時，迄今為止還沒有人能夠利用任何計算工具完成其分解因子這一任務(wù)。因此，RSA從被提出到現(xiàn)在40余年，經(jīng)歷了各種攻擊的考驗，逐漸為人們所接受，被普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。

然而，雖然RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解的難度等價，即RSA的重大缺陷是無法從理論上把握它的保密性能。

此外，RSA的缺點(diǎn)還有：

① 產(chǎn)生密鑰很麻煩，會受到素數(shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密;

② 分組長度太大，為保證安全性，n至少需要600 bits 以上，運(yùn)算代價高，速度慢，較對稱密碼算法慢幾個數(shù)量級，且隨著大數(shù)分解技術(shù)的發(fā)展，這個長度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。

因此，使用RSA只能加密少量數(shù)據(jù)，大量的數(shù)據(jù)加密還要依靠對稱密碼算法。