【文章內(nèi)容簡(jiǎn)介】 由式 (2)定義的仿射加密方法，只要知道兩對(duì)（不同的）相對(duì)應(yīng)的明文和密文 P1， E1與 P2， E2，就可以求出解密方法。事實(shí)上，由式 (2)及已知的對(duì)應(yīng)關(guān)系，得到 E1 ? aP1 ? b (mod M)， E2 ? aP2 ? b (mod M)， （ 4） 所以 E2 ? E1 ? a(P2 ? P1) (mod M)。 以 x ? ai (mod M)， 0 ? ai M， 1 ? i ? r 表示同余方程 x(P2 ? P1) ? E2 ? E1 (mod M) 的全部解，并且記 bi ? E1 – aiP1 (mod M)， 0 ? bi M， 則 ai與 bi（ 1 ? i ? r）就可能是式 (2)中所使用的 a 和 b。 當(dāng) (P2 ? P1, M) = 1 時(shí)，這樣的 ai與 bi只有一組，當(dāng) (P2 ? P1, M) 1時(shí)，為了確定出正確的 a 與 b，首先，利用 (a， M) = 1 刪去某些 ai與bi，其次，用它們驗(yàn)證式（ 4）是否成立，并用它們?cè)囎g部分密文，就可以確定正確的 a 與 b。將確定的 a， b代入式 (3)，就得到解密公式。 在現(xiàn)實(shí)生活中，無(wú)論使用什么語(yǔ)言符號(hào)傳送信息，各個(gè)符號(hào)的出現(xiàn)頻率總是有差別的。例如，有統(tǒng)計(jì)數(shù)字表明，在報(bào)刊文章中，英語(yǔ)的 26 個(gè)字母中，出現(xiàn)頻率較高的，依次是 e， t， a， o等；較低的，依次是 z， q， j， x等。這樣，在對(duì)密文中的每個(gè)字母的出現(xiàn)頻率進(jìn)行統(tǒng)計(jì)之后，可以對(duì)于明文字母和密文字母之 間的對(duì)應(yīng)關(guān)系作出猜測(cè)，然后試行解密。 例 3 已知明文由 26個(gè)英文字母 a， b， ? ， y， z（分別與 00， 01，? ， 24， 25對(duì)應(yīng)）及符號(hào)“！”和“？”（分別與 26 和 27 對(duì)應(yīng)）組成，用這 28 個(gè)符號(hào)寫成的正常英文中，出現(xiàn)頻率最高的依次是！， e 與 t。在對(duì)一組密文做了統(tǒng)計(jì)分析之后，發(fā)現(xiàn)密文中出現(xiàn)頻率最高的三個(gè)符 189 號(hào)依次是 b， ?與 i， 試求解密公式。 解 設(shè)解密公式為 P ? a ?E ? b ? (mod 28)， 0 ? P 28， 則由已知的符號(hào)與數(shù)字的對(duì)應(yīng)關(guān)系，比較出現(xiàn)頻率的高低，可以假定“ !”與“ e”分別對(duì)應(yīng) 著“ b”與“ ?”，于是 26 ? a ??1 ? b ? (mod 28)， 4 ? a ??27 ? b ? (mod 28)， 將兩式相減，得到 26a ?? ?22 (mod 28)。 這個(gè)同余方程有兩個(gè)解： a1? ? 11 (mod 28)， a2? ? 25 (mod 28)， 相應(yīng)的，b1? ? 15 (mod 28)， b2? ? 1 (mod 28)。 這樣，得到了兩個(gè)可能的解密方法： (ⅰ ) P ? 11E ? 15 (mod 28)， 0 ? P 28， (ⅱ ) P ? 25E ? 1 (mod 28)， 0 ? P 28。 再通過(guò)比較出現(xiàn)頻率，又可假定 i與 t 對(duì)應(yīng)（它們對(duì)應(yīng)的數(shù)字分別是 8 與 19），將這兩個(gè)數(shù)字分別代入 (ⅰ )與 (ⅱ )進(jìn)行驗(yàn)證，可知解密方法 (ⅰ )是正確的。 習(xí) 題 三 1. 利用例 1 中的加密方法，將“ ICOMETODAY”加密。 2. 已知字母 a， b， ? ， y， z，它們分別與整數(shù) 00， 01， ? ， 24，25 對(duì)應(yīng)，又已知明文 h 與 p分別與密文 e 與 g對(duì)應(yīng)，試求出密解公式： P ? a ?E ? b ? (mod 26)， 并破譯下面的密文：“ IRQXREFRXLGXEPQVEP”。 第四節(jié) RSA 加密方法 對(duì)信息進(jìn)行加密的目的，當(dāng)然是希望這個(gè)信息的內(nèi)容不被某一部分人（以后，我們稱他們?yōu)椤皵撤健保┝私猓煌瑫r(shí)，這個(gè)信息的內(nèi)容應(yīng)該能夠被另一部分人（以后，我們稱他們?yōu)椤坝逊健保┖苋菀椎亓私狻?190 上一節(jié)所介紹的仿射加密方法具有計(jì)算方便的優(yōu)點(diǎn)，其中，參數(shù) a 和b 是兩個(gè)關(guān)鍵的數(shù)據(jù)。我們已經(jīng)看到，利用統(tǒng)計(jì)的方法，能夠很容易地確定這兩個(gè)數(shù)據(jù)，此外，為了提高保密性，即增加敵方從密文得到密文的困難程度，需要經(jīng)常更換 a 和 b 的數(shù)值，于是，就要隨時(shí)把這些數(shù)值及時(shí)通知友方，這就增加了敵方獲取 a 和 b 的數(shù)值的可能性。因 此，仿射加密方法的保密性（安全性）是不好的。在這一節(jié)，我們介紹一種加密方法，在很大程度上克服了上述缺點(diǎn)。 從實(shí)用的觀點(diǎn)來(lái)看，保密是有時(shí)間性的。如果加密后的文件在一個(gè)足夠長(zhǎng)的時(shí)間內(nèi)不被敵方了解，就可以認(rèn)為這個(gè)加密是安全的。當(dāng)我們談?wù)摗鞍涯骋环菸募用?，使它不被敵方了解”的時(shí)候，其實(shí)是包含著一個(gè)時(shí)間界限的。就是說(shuō)，這里指的是，在某一個(gè)時(shí)期內(nèi)，加密后的文件不被敵方了解。例如，一個(gè)發(fā)動(dòng)某次戰(zhàn)役的具體時(shí)間，在戰(zhàn)役開(kāi)始之前是絕對(duì)要保密的，但是，戰(zhàn)役結(jié)束之后，就不存在保密的必要了。 用 P 和 E 分別表示明文和密文，從數(shù)學(xué)的觀 點(diǎn)來(lái)看文件加密的問(wèn)題，加密方法和解密方法其實(shí)就是兩個(gè)滿足下述條件的函數(shù) f(P)和g(E)： (ⅰ ) 對(duì)于某個(gè)整數(shù)集合中的數(shù) P，有確定的函數(shù)值 E = f(P)與之對(duì)應(yīng)，同時(shí)，計(jì)算 f(P)是容易的： (ⅱ ) 對(duì)于某個(gè)整數(shù)集合中的數(shù) E，有確定的函數(shù)值 P = g(E)與之對(duì)應(yīng)，同時(shí)，計(jì)算 g(E)是困難的； (ⅲ ) 如果掌握了關(guān)于函數(shù) g(E)的某種條件（信息），計(jì)算 g(E)是容易的。 在這一節(jié)，我們要介紹滿足上述三個(gè)條件的一個(gè)加密方法，它以下面的命題為基礎(chǔ)。 命題 已知兩個(gè)素?cái)?shù)，計(jì)算它們的的乘積是容易的；但 是，已知兩個(gè)大素?cái)?shù)的乘積，求這兩個(gè)素?cái)?shù)卻是非常困難的。 從這一個(gè)命題出發(fā)， R. L. Rivest 與 A. Shamir， L. M. Adleman 提出了下面的加密方法。 RSA 加密方法 Ⅰ 參數(shù)的選取 隨機(jī)地選取大素?cái)?shù) p， q，計(jì)算 n = pq， ?(n) = (p ? 1)(q ? 1)， 191 再隨機(jī)地取正整數(shù) e， (e, ?(n)) = 1， 并計(jì)算 d， 使得 ed ? 1 (mod ?(n))。 (1) 公開(kāi) n， e，供加密使用（稱它們?yōu)?RSA加密鑰）；將 p， q， ?(n)和 d 保密（稱它們?yōu)楸Ｃ荑€）。 Ⅱ 加密 設(shè)明文是 P， 0 ? P n， 則與之相應(yīng)的密文是 E ? P e (mod n)， 0 ? E n。 (2) Ⅲ 解密 已知密文 E 時(shí)，明文 P 由下式確定： P ? E d (mod n)， 0 ? P n。 (3) 我們將以上設(shè)計(jì)的 RSA加密方法簡(jiǎn)記為 RSA(n, e)。 下面的定理給出了解密方法的依據(jù)。 定理 1 設(shè) n = p1p2? pk 是 k 個(gè)不同的素?cái)?shù)之積， e 與 d是正整數(shù)，(e, ?(n)) = 1， 并且式 (1)成立 ， 則對(duì)于任意的 a?N，有 a ed ? a (mod n)。 證明 對(duì)于任意的 pi（ 1 ? i ? k） ， 若 (a, pi) = 1， 則由 Euler 定理可知 1?ipa ? 1 (mod pi )。 由式 (1)， ed = r?(n) ? 1 = r (p1 ? 1) ? (pk ? 1) ? 1，其中 r是非負(fù)整數(shù)，所以， a ed ? a (mod pi )， i = 1, 2, ? , k。 (4) 當(dāng) (a, pi) 1 時(shí)，這個(gè) 同余式當(dāng)然也成立。由于 p1, p2, ? , pk 是互不相同的素?cái)?shù)，由式 (4)及同余式的性質(zhì)即可證得定理。證畢。 一般來(lái)說(shuō)，從密文求明文，有許多可能的方法，例如： (ⅰ ) 將 n分解因數(shù)，求出 p 和 q， 使得 n = pq， 然后計(jì)算 ?(n) = (p ? 1)(q ? 1)， 利用輾轉(zhuǎn)相除法求出 d，使得式 (1)成立。再利用式 (3)從密文 E計(jì)算明文 P。容易看出，用這種方法從密文求出明文的難度，就是將大整數(shù)分解因數(shù)的難度。 (ⅱ ) 如果能用某種方法（不是先將 n分解因數(shù)）求出 ?(n)，則也可以從密文 E 求出明文 P。 因?yàn)椋?利用輾轉(zhuǎn)相除法，由 e 可以求出 d使得式 (1)成立，于是，由式 (3)可以從密文 E 計(jì)算明文 P。但是，如果?(n) = (p ? 1)(q ? 1)是已知的，那么，有 pq = n 以及 192 p ? q = pq ? ?(n) ? 1 = n ? ?(n) ? 1。 由此，可以利用一元二次方程的求解公式求出 p 和 q。這說(shuō)明，這種方法的難度不會(huì)低于將大整數(shù)分解因數(shù)的難度。 除此之外，還有一些別的方法。對(duì)于這些方法的分析，有興趣的讀者可以查閱關(guān)于密碼學(xué)的文獻(xiàn)?？偟膩?lái)說(shuō)， RSA加密方法被認(rèn)為有較好的安全性。 RSA加密方法的特點(diǎn)， 在于加密方法是公開(kāi)的，而且加密時(shí)所使用的參數(shù)也是公開(kāi)的。這是它與仿射加密方法的重要區(qū)別。 通常，稱具有這種特點(diǎn)的加密方法為公鑰加密方法。公鑰加密方法使得信息的加密傳送更為方便。例如，每個(gè)單位或個(gè)人可以像公布電話號(hào)碼一樣公布自己的 RSA加密鑰。于是，凡是要向它或他發(fā)送加密信息的單位或個(gè)人都可以使用這些參數(shù)發(fā)送加密信息。此外， RSA加密方法還有更廣泛的用途。下面介紹的數(shù)字簽名的方法就是一個(gè)例子。 數(shù)字簽名 在社會(huì)生活中，在處理具體事件時(shí)，常需要當(dāng)事人進(jìn)行簽證（簽名），以保證他做出的許諾或送出的信息的可靠性與合法 性。例如，在簽署文件時(shí)，由當(dāng)事人簽名，蓋章，簽署日期以及重要的特殊記號(hào)，常是不可少的環(huán)節(jié)。這樣的簽證，應(yīng)該滿足一定的要求。 假設(shè) A 簽證一個(gè)文件給 B，那么， (ⅰ ) B 應(yīng)該能夠確定這是否 A 的簽證 ； (ⅱ ) 任何其他人，無(wú)法偽造 A 的簽證，即 A 有其獨(dú)特的簽證方式 ； (ⅲ ) 有一個(gè)仲裁簽證是否由 A 發(fā)出的方法，例如，當(dāng) A 否認(rèn)這個(gè)簽證時(shí)，這樣的方法可以鑒定簽證的真?zhèn)巍? 下面我們說(shuō)明， RSA加密方法可以用來(lái)進(jìn)行簽證，不需要當(dāng)事人到場(chǎng)