【正文】 成立。由于 p1, p2, ? , pk 是互不相同的素數(shù)，由式 (4)及同余式的性質(zhì)即可證得定理。 由式 (1)， ed = r?(n) ? 1 = r (p1 ? 1) ? (pk ? 1) ? 1，其中 r是非負整數(shù)，所以， a ed ? a (mod pi )， i = 1, 2, ? , k。 定理 1 設(shè) n = p1p2? pk 是 k 個不同的素數(shù)之積， e 與 d是正整數(shù)，(e, ?(n)) = 1， 并且式 (1)成立 ， 則對于任意的 a?N，有 a ed ? a (mod n)。 (3) 我們將以上設(shè)計的 RSA加密方法簡記為 RSA(n, e)。 Ⅱ 加密 設(shè)明文是 P， 0 ? P n， 則與之相應(yīng)的密文是 E ? P e (mod n)， 0 ? E n。 RSA 加密方法 Ⅰ 參數(shù)的選取 隨機地選取大素數(shù) p， q，計算 n = pq， ?(n) = (p ? 1)(q ? 1)， 191 再隨機地取正整數(shù) e， (e, ?(n)) = 1， 并計算 d， 使得 ed ? 1 (mod ?(n))。 命題 已知兩個素數(shù)，計算它們的的乘積是容易的；但 是，已知兩個大素數(shù)的乘積，求這兩個素數(shù)卻是非常困難的。 用 P 和 E 分別表示明文和密文，從數(shù)學(xué)的觀 點來看文件加密的問題，加密方法和解密方法其實就是兩個滿足下述條件的函數(shù) f(P)和g(E)： (ⅰ ) 對于某個整數(shù)集合中的數(shù) P，有確定的函數(shù)值 E = f(P)與之對應(yīng)，同時，計算 f(P)是容易的： (ⅱ ) 對于某個整數(shù)集合中的數(shù) E，有確定的函數(shù)值 P = g(E)與之對應(yīng)，同時，計算 g(E)是困難的； (ⅲ ) 如果掌握了關(guān)于函數(shù) g(E)的某種條件（信息），計算 g(E)是容易的。就是說，這里指的是，在某一個時期內(nèi)，加密后的文件不被敵方了解。如果加密后的文件在一個足夠長的時間內(nèi)不被敵方了解，就可以認為這個加密是安全的。在這一節(jié)，我們介紹一種加密方法，在很大程度上克服了上述缺點。我們已經(jīng)看到，利用統(tǒng)計的方法，能夠很容易地確定這兩個數(shù)據(jù)，此外，為了提高保密性，即增加敵方從密文得到密文的困難程度，需要經(jīng)常更換 a 和 b 的數(shù)值，于是，就要隨時把這些數(shù)值及時通知友方，這就增加了敵方獲取 a 和 b 的數(shù)值的可能性。 第四節(jié) RSA 加密方法 對信息進行加密的目的，當(dāng)然是希望這個信息的內(nèi)容不被某一部分人（以后，我們稱他們?yōu)椤皵撤健保┝私?；同時，這個信息的內(nèi)容應(yīng)該能夠被另一部分人（以后，我們稱他們?yōu)椤坝逊健保┖苋菀椎亓私狻? 習(xí) 題 三 1. 利用例 1 中的加密方法，將“ ICOMETODAY”加密。 這樣，得到了兩個可能的解密方法： (ⅰ ) P ? 11E ? 15 (mod 28)， 0 ? P 28， (ⅱ ) P ? 25E ? 1 (mod 28)， 0 ? P 28。 解 設(shè)解密公式為 P ? a ?E ? b ? (mod 28)， 0 ? P 28， 則由已知的符號與數(shù)字的對應(yīng)關(guān)系，比較出現(xiàn)頻率的高低，可以假定“ !”與“ e”分別對應(yīng) 著“ b”與“ ?”，于是 26 ? a ??1 ? b ? (mod 28)， 4 ? a ??27 ? b ? (mod 28)， 將兩式相減，得到 26a ?? ?22 (mod 28)。 例 3 已知明文由 26個英文字母 a， b， ? ， y， z（分別與 00， 01，? ， 24， 25對應(yīng)）及符號“！”和“？”（分別與 26 和 27 對應(yīng)）組成，用這 28 個符號寫成的正常英文中，出現(xiàn)頻率最高的依次是！， e 與 t。例如，有統(tǒng)計數(shù)字表明，在報刊文章中，英語的 26 個字母中，出現(xiàn)頻率較高的，依次是 e， t， a， o等；較低的，依次是 z， q， j， x等。將確定的 a， b代入式 (3)，就得到解密公式。 以 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。 解 將已知的 e ? u 以及 e ? 04， u ? 20 代入式 (4)，得到 20 ? 4 ? b (mod 26)， 所以 b ? 16 (mod 26)， 再由式 (4)得到 P ? E ? 16 ? E ? 10 (mod 26)， 0 ? P 26， 這就是解密方法，也可以用下表說明： 表 3 188 E a b c d e f g h i j k l m P k l m n o p q r s t u v w E n o p q r s t u v w x y z P x y z a b c d e f g h i j 一般地，對于由式 (2)定義的仿射加密方法，只要知道兩對（不同的）相對應(yīng)的明文和密文 P1， E1與 P2， E2，就可以求出解密方法。 例 2 已知明文所使用的符號只是 26 個英文字母 a， b， ? ， y， z，它們分 別與整數(shù) 00， 01， ? ， 24， 25 對應(yīng)，又知道使用公式 E ? P ? b (mod 26)， 0 ? E 26 (4) 對每個符號加密。 以下，為了敘述方便，我們用“ ?”表示數(shù)字與符號的對應(yīng)關(guān)系，例如，“ a ? 00” ， “ d ? 03” ， 等等。 這就是所謂的“愷撒密碼” 。事實上，由式 (3)，式 (2)和式 (1)，我們得到 187 P0 ? a ?(E ? b) ? a?((aP ? b) ? b) ? aa?P ? P (mod M)， 由于 0 ? P M， 0 ? P0 M，所以，由上式得到 P0 = P。 (ⅲ ) 解密：對于密文 E，計算 P0 ? a ?(E ? b) (mod M)， 0 ? P0 M， (3) P0就是與 E 對應(yīng)的明文 P。） (ⅱ ) 加密：對于明文 P，計算 E ? aP ? b (mod M)， 0 ? E M。 用仿射加密方法對明文 P 加密的過程是這樣的： (ⅰ ) 取大正整數(shù) M A， 以及正整數(shù) a， b， a ?，使得 (a, M) = 1， aa ? ? 1 (mod M)。 在這一節(jié)，我們主要介紹歷史較長久的一類加密方法，即仿射加密方法。 這樣，任何整數(shù) P 就與整數(shù)列 {pn, pn ? 1, ? , p0}建立了一一對應(yīng)的關(guān)系，對大整數(shù) P 的加密就轉(zhuǎn)化為對不超過 k 的整數(shù) pi（ 0 ? i ? n）的加密。 在實際應(yīng)用中，一個文件所對應(yīng)的整數(shù)是一個很大的數(shù)字，所以，人們往往要對大的正整數(shù)進行處理，使它們可以與較小的正整數(shù)列對應(yīng)，從而容易進行加密運算。假設(shè)所使用的字母和符號共有 N個，如果把這些符號和 N 個正整數(shù) 0， 1， 2， ? ， N ? 1 建立一一對應(yīng)的關(guān)系，那么，文 字、符號、句子和文件就都和正整數(shù)建立了一一對應(yīng)的 186 關(guān)系。一個文件總是由文字和其他符號（標(biāo)點符號，數(shù)字，特殊記號，等等）組成的。把密文翻譯成明文的過程，稱為解密過程，或解密；所用的方法（或公式），稱為解密方法（或解密公式）?？偟膩碚f，關(guān)于信息加密的研究主要是兩個方面：第一，研究把明文翻譯成密文的方法，這個方法要盡可能的簡單易行；第二，研究這種加密方法的保密性（安全性），即，除合法接收人外，其他人從密文了解到明文內(nèi)容（全部或部分）的可能性。密文不是隨便甚麼人都可以看懂的。 對于那些一目了然的信息，我們稱為“明文”。 現(xiàn)實社會中，充滿了各種各樣的信息，例如，軍事情報，商業(yè)秘密，金融消息，計算機文件，私人通信等等。事實并非如此。 2. 編一個有九個球隊進行循環(huán)賽的程序表。如果在 這個位置上沒有數(shù)字，就表示球隊 m在第 k 輪比賽中沒有賽事。 下面，我們舉了兩個例子說明具體的按排方法。如果21 ii xx ?? N，那么，由式 (3)得到 i1 ?21 ii xxxx ???? i2 (mod N ? 1)， 因此 i1 = i2 。 (ⅱ ) 再看球隊 x， x N。如果 21 ii NN ?(1 ? i1, i2 ? N ? 1)。 最后，我們指 出，對于每一個確定的隊 x，它在每一輪比賽中的對手是不同的，即 21 ii xx ?， i1 ? i2， (1 ? i1, i2 ? N ? 1)。當(dāng) x = N時，由式 (1)可知 N ? Ni。 (6) 但是，由于對 x? 的假定 ， 式 (5)或式 (6)都不能成立。 (ⅱ ) 若 x = N， x? = Ni， 則 xi = Ni， xi? = N， 顯然 xi ? xi?。 我們分三種情況進行討論。 (3) 183 下面，我們要證明，這樣的按排滿足要求。當(dāng)，是偶數(shù)；當(dāng)，iNiiiNi212 (1) 顯然 N ? Ni。 下面 ，我們給出一個按排比賽的方法，它說明，用 N ? 1 輪比賽就可以完成循環(huán)賽。這樣， N 是奇數(shù)的情形就可以化為 N是偶數(shù)的情形，因此，下面我們總假定 N是偶數(shù)。這時，我們把一個“假想的”球隊 A 加到這 N 個球隊中，就有了 N ? 1 個球隊。其次，用 r表示在每一輪比賽中所進行 的比賽場數(shù)，則 ??????? 是奇數(shù)。我們希望知道：最少需要按排幾輪比 182 賽，才能完成循環(huán)賽？ 我們先來做一些分析。 注意，由例 2 我們看到，一月和二月分別是作為上一年的十一月和十二月。 例 1 問： 1976 年 8 月 6 日是星期幾？ 解 將 N = 1976， c = 19， y = 76， m = 6， k = 6 代入式 (6)，得到