[[357279]]

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

ID：Computer-network

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

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

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

[[357280]]

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

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

1、RSA算法原理

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

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

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

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

表2 RSA算法

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

② 對(duì)于所有的M

③ 在給定e和n時(shí)，計(jì)算出d是不可行的。

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

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

1)素?cái)?shù)

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

2)互為素?cái)?shù)

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

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

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

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

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

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

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

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

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

3)模運(yùn)算

模運(yùn)算是整數(shù)運(yùn)算，有一個(gè)整數(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同余。

② 對(duì)稱(chēng)性：若a=b mod n，則b=amod n。

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

4)Euler函數(shù)

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

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

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

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

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

φ(pk)=pk-pk-1

例如，φ(8)=φ(23)=23-22=4。這是因?yàn)橹挥挟?dāng)一個(gè)數(shù)不包含素?cái)?shù)p時(shí)，才能與n互質(zhì)。而包含素?cái)?shù)p的數(shù)一共有pk-1個(gè)，即1×p、2×p、…、pk-1×p。

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

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

，則有

。

5)歐拉定理

如果兩個(gè)正整數(shù)a和n互質(zhì)，則n的歐拉函數(shù)φ(n)滿(mǎ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ì)，則因?yàn)?phi;(p)=p-1，所以歐拉函數(shù)可寫(xiě)成：

ap−1≡1(mod p)

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

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

若m是素?cái)?shù)，且a不是m的倍數(shù)，則am-1 mod m=1?；蛘?，若m是素?cái)?shù)，則ammod m=a。例如，46mod 7=4096 mod 7=1，47mod 7=16384 mod 7=4。

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

(2)素?cái)?shù)的產(chǎn)生與檢驗(yàn)

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

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

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

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

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

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

2、RSA加解密算法過(guò)程

(1)RSA加密算法過(guò)程

RSA加密算法的過(guò)程如下：

① 取兩個(gè)隨機(jī)大素?cái)?shù)p和q(保密);

② 計(jì)算公開(kāi)的模數(shù)n=p×q(公開(kāi));

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

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

⑤ 計(jì)算d，使其滿(mǎn)足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)過(guò)程中，主要的運(yùn)算量是計(jì)算模的逆元以及模指數(shù)，通常情況下，計(jì)算模的逆元時(shí)會(huì)采用擴(kuò)展的歐幾里德算法。

(2)RSA解密算法過(guò)程

由于指數(shù)較大，因此RSA解密過(guò)程比較耗時(shí)，但利用孫子定理(Chinese Remainder Theorem，CRT)可提高解密算法效率。CRT對(duì)RSA解密算法生成兩個(gè)解密方程(利用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ù)字簽名

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

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

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

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

1)設(shè)計(jì)公私密鑰(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的取值可以用試算的辦法來(lái)確定。試算結(jié)果如表3所示。

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

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

2)英文數(shù)字化

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

表4 明文英文字母編碼表

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

3)明文加密

用戶(hù)加密密鑰(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)密文解密

用戶(hù)B收到密文后，若要將其解密，則只需要計(jì)算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

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

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

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

在RSA密碼應(yīng)用中，公鑰KU是被公開(kāi)的，即e和n的數(shù)值可以被第三方竊聽(tīng)者得到。破解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ì)問(wèn)題是：從pq這一數(shù)值求出(p-1)和(q-1)。換句話(huà)說(shuō)，只要求出p和q的值，就能求出d的值進(jìn)而得到私鑰。

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

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

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

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

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

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