數(shù)論與組合數(shù)學第五章數(shù)論的應用

1、第五章 數(shù)論的應用在一個很長的時期里，數(shù)論被認為是很難有應用價值的。但是，二十世紀中后期，數(shù)論的應用，特別是在密碼學等學科中的應用，改變了人們的看法，數(shù)論的研究也增加了新的內容。本章以下幾節(jié)將要介紹數(shù)論在信息保密技術中的幾個應用。第一節(jié) 仿射加密現(xiàn)實社會中，充滿了各種各樣的信息，例如，軍事情報，商業(yè)秘密，金融消息，計算機文件，私人通信等等。在很多情況下，人們希望在秘密的情況下保存或傳送信息，這就導致了對信息加密的研究。對于那些一目了然的信息，我們稱為“明文”。當我們要把某個信息傳送給某些人（稱之為“合法接收人”）時，是先把明文進行“加密”處理，這種經(jīng)過加密處理的明文，我們稱為“密文”。密文不是

2、隨便甚麼人都可以看懂的。只有合法接收人，他們掌握了一定的方法，才能把它“翻譯”成加密處理之前的明文?？偟膩碚f，關于信息加密的研究主要是兩個方面：第一，研究把明文翻譯成密文的方法，這個方法要盡可能的簡單易行；第二，研究這種加密方法的保密性（安全性），即，除合法接收人外，其他人從密文了解到明文內容（全部或部分）的可能性。把明文翻譯成密文的過程，稱為加密過程，或加密；所用的方法（或公式），稱為加密方法（或加密公式）。把密文翻譯成明文的過程，稱為解密過程，或解密；所用的方法（或公式），稱為解密方法（或解密公式）。為了能將數(shù)論用于明文的加密，首先需要建立明文與正整數(shù)的對應關系。一個文件總是由文字和其他符

3、號（標點符號，數(shù)字，特殊記號，等等）組成的。如果用漢語拼音書寫漢字，那么，文件就可以用26個拉丁字母和一些符號來表達。假設所使用的字母和符號共有N個，如果把這些符號和N個正整數(shù)0，1，2，L，N - 1建立一一對應的關系，那么，文字、符號、句子和文件就都和正整數(shù)建立了一一對應的關系。例如，假設使26個拉丁字母a，b，c，L，y，z與數(shù)字00，01，02，L，24，25建立了下表所示的一一對應關系：表 1abcdefghijklm00010203040506070809101112nopqrstuvwxyz13141516171819202122232425那么，與“woyaolai”（我要來）

4、對應的數(shù)字就是2214240014110008。在實際應用中，一個文件所對應的整數(shù)是一個很大的數(shù)字，所以，人們往往要對大的正整數(shù)進行處理，使它們可以與較小的正整數(shù)列對應，從而容易進行加密運算。我們知道，對于給定的正整數(shù)k，任何正整數(shù)P都可以唯一地表示成P = pnkn + pn - 1kn - 1 + L + p1k + p0，0 £ pi £ k - 1，0 £ i £ n。這樣，任何整數(shù)P就與整數(shù)列pn, pn - 1, L, p0建立了一一對應的關系，對大整數(shù)P的加密就轉化為對不超過k的整數(shù)pi（0 £ i £ n）的加密。以下

5、幾節(jié)中，我們總用P表示明文，用E(P)或E表示與P相應的密文。在這一節(jié)，我們主要介紹歷史較長久的一類加密方法，即仿射加密方法。用W表示需要加密的所有明文P的集合，并且假定集合W的上界是A。用仿射加密方法對明文P加密的過程是這樣的：() 取大正整數(shù)M > A，以及正整數(shù)a，b，a ¢，使得(a, M) = 1，aa ¢ º 1 (mod M)。 (1)（注意：因此，明文P滿足0 £ P < M。）() 加密：對于明文P，計算E º aP + b (mod M)，0 £ E < M。 (2)E就是與P對應的密文。() 解

6、密：對于密文E，計算P0 º a ¢(E - b) (mod M)，0 £ P0 < M， (3)P0就是與E對應的明文P?，F(xiàn)在，我們說明式(3)中確定的P0就是明文P。事實上，由式(3)，式(2)和式(1)，我們得到P0 º a ¢(E - b) º a¢(aP + b) - b) º aa¢P º P (mod M)，由于0 £ P < M，0 £ P0 < M，所以，由上式得到P0 = P。例1 設符號a，b，L，y，z分別與整數(shù)0，1，L，24，25

7、對應，使用仿射加密方法，取M = 26，a = 1，b = 3，a ¢ = 1，對明文P中的每一個符號用這一方法加密：E º P + 3 (mod 26)。這就是所謂的“愷撒密碼”。在古羅馬時代，愷撒大帝在傳送軍事命令時，把每個英文字母用它后面的第三個字母代替，即按表2的替換方式：表 2PabcdefghijklmEdefghijklmnopPnopqrstuvwxyzEqrstuvwxyzabc例如，使用例1中的加密方法，明文“jiudianzhong”（九點鐘）被加密成“mlxgldqckrqj”。以下，為了敘述方便，我們用“®”表示數(shù)字與符號的對應關系，例如

8、，“a ® 00”，“d ® 03”，等等。又用“Þ”表示明文和密文的對應關系，例如，“s Þ a”“men Þ phq”，等等。例2 已知明文所使用的符號只是26個英文字母a，b，L，y，z，它們分別與整數(shù)00，01，L，24，25對應，又知道使用公式E º P + b (mod 26)，0 £ E < 26 (4)對每個符號加密。已經(jīng)知道明文字母e與密文字母u對應，試求出解密方法。解 將已知的e Þ u以及e ® 04，u ® 20代入式(4)，得到20 º 4 + b (m

9、od 26)，所以b º 16 (mod 26)，再由式(4)得到P º E - 16 º E + 10 (mod 26)，0 £ P < 26，這就是解密方法，也可以用下表說明：表 3EabcdefghijklmPklmnopqrstuvwEnopqrstuvwxyzPxyzabcdefghij一般地，對于由式(2)定義的仿射加密方法，只要知道兩對（不同的）相對應的明文和密文P1，E1與P2，E2，就可以求出解密方法。事實上，由式(2)及已知的對應關系，得到E1 º aP1 + b (mod M)， E2 º aP2 + b

10、(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。當(P2 - P1, M) = 1時，這樣的ai與bi只有一組，當(P2 - P1, M) > 1時，為了確

11、定出正確的a與b，首先，利用(a，M) = 1刪去某些ai與bi，其次，用它們驗證式（4）是否成立，并用它們試譯部分密文，就可以確定正確的a與b。將確定的a，b代入式(3)，就得到解密公式。習 題 一1. 利用例1中的加密方法，將“ICOMETODAY”加密。2. 已知字母a，b，L，y，z，它們分別與整數(shù)00，01，L，24，25對應，又已知明文h與p分別與密文e與g對應，試求出密解公式：P º a ¢E + b ¢ (mod 26)，并破譯下面的密文：“IRQXREFRXLGXEPQVEP”。第二節(jié) RSA密碼體制對信息進行加密的目的，當然是希望這個信息的內容

12、不被某一部分人（以后，我們稱他們?yōu)椤皵撤健保┝私?；同時，這個信息的內容應該能夠被另一部分人（以后，我們稱他們?yōu)椤坝逊健保┖苋菀椎亓私狻Ｉ弦还?jié)所介紹的仿射加密方法具有計算方便的優(yōu)點，其中，參數(shù)a和b是兩個關鍵的數(shù)據(jù)。我們已經(jīng)看到，利用統(tǒng)計的方法，能夠很容易地確定這兩個數(shù)據(jù)，此外，為了提高保密性，即增加敵方從密文得到密文的困難程度，需要經(jīng)常更換a和b的數(shù)值，于是，就要隨時把這些數(shù)值及時通知友方，這就增加了敵方獲取 a和b的數(shù)值的可能性。因此，仿射加密方法的保密性（安全性）是不好的。在這一節(jié)，我們介紹一種加密方法，在很大程度上克服了上述缺點。從實用的觀點來看，保密是有時間性的。如果加密后的文件在一個

13、足夠長的時間內不被敵方了解，就可以認為這個加密是安全的。當我們談論“把某一份文件加密，使它不被敵方了解”的時候，其實是包含著一個時間界限的。就是說，這里指的是，在某一個時期內，加密后的文件不被敵方了解。例如，一個發(fā)動某次戰(zhàn)役的具體時間，在戰(zhàn)役開始之前是絕對要保密的，但是，戰(zhàn)役結束之后，就不存在保密的必要了。用P和E分別表示明文和密文，從數(shù)學的觀點來看文件加密的問題，加密方法和解密方法其實就是兩個滿足下述條件的函數(shù)f(P)和g(E)：() 對于某個整數(shù)集合中的數(shù) P，有確定的函數(shù)值E = f(P)與之對應，同時，計算f(P)是容易的：() 對于某個整數(shù)集合中的數(shù)E，有確定的函數(shù)值P = g(E)

14、與之對應，同時，計算g(E)是困難的；() 如果掌握了關于函數(shù)g(E)的某種條件（信息），計算g(E)是容易的。在這一節(jié)，我們要介紹滿足上述三個條件的一個加密方法，它以下面的命題為基礎。命題 已知兩個素數(shù)，計算它們的的乘積是容易的；但是，已知兩個大素數(shù)的乘積，求這兩個素數(shù)卻是非常困難的。從這一個命題出發(fā)，R. L. Rivest與A. Shamir，L. M. Adleman提出了下面的加密方法。RSA加密方法 參數(shù)的選取隨機地選取大素數(shù)p，q，計算n = pq，j(n) = (p - 1)(q - 1)，再隨機地取正整數(shù)e，(e, j(n) = 1，并計算d，使得ed º 1 (m

15、od j(n)。 (1)公開n，e，供加密使用（稱它們?yōu)镽SA加密鑰）；將p，q，j(n)和d保密（稱它們?yōu)楸Ｃ荑€）。 加密設明文是P，0 £ P < n，則與之相應的密文是E º P e (mod n)， 0 £ E < n。 (2) 解密已知密文E時，明文P由下式確定：P º E d (mod n)， 0 £ P < n。 (3)我們將以上設計的RSA加密方法簡記為RSA(n, e)。下面的定理給出了解密方法的依據(jù)。定理1 設n = p1p2Lpk是k個不同的素數(shù)之積，e與d是正整數(shù)，(e, j(n) = 1，并且式(1)

16、成立，則對于任意的aÎN，有a ed º a (mod n)。證明 對于任意的pi（1 £ i £ k）， 若(a, pi) = 1，則由Euler定理可知º 1 (mod pi )。由式(1)，ed = rj(n) + 1 = r (p1 - 1) L (pk - 1) + 1，其中r是非負整數(shù)，所以，a ed º a (mod pi )，i = 1, 2, L, k。 (4)當(a, pi) > 1時，這個同余式當然也成立。由于p1, p2, L, pk是互不相同的素數(shù)，由式(4)及同余式的性質即可證得定理。證畢。一般來說，

17、從密文求明文，有許多可能的方法，例如：() 將n分解因數(shù)，求出p和q， 使得n = pq，然后計算j(n) = (p - 1)(q - 1)，利用輾轉相除法求出d，使得式(1)成立。再利用式(3)從密文E計算明文P。容易看出，用這種方法從密文求出明文的難度，就是將大整數(shù)分解因數(shù)的難度。() 如果能用某種方法（不是先將n分解因數(shù)）求出j(n)，則也可以從密文E求出明文P。因為，利用輾轉相除法，由e可以求出d使得式(1)成立，于是，由式(3)可以從密文E計算明文P。但是，如果j(n) = (p - 1)(q - 1)是已知的，那么，有pq = n以及p + q = pq - j(n) + 1 =

18、n - j(n) + 1。由此，可以利用一元二次方程的求解公式求出p和q。這說明，這種方法的難度不會低于將大整數(shù)分解因數(shù)的難度。除此之外，還有一些別的方法。對于這些方法的分析，有興趣的讀者可以查閱關于密碼學的文獻?？偟膩碚f，RSA加密方法被認為有較好的安全性。RSA加密方法的特點，在于加密方法是公開的，而且加密時所使用的參數(shù)也是公開的。這是它與仿射加密方法的重要區(qū)別。 通常，稱具有這種特點的加密方法為公鑰加密方法。公鑰加密方法使得信息的加密傳送更為方便。例如，每個單位或個人可以像公布電話號碼一樣公布自己的RSA加密鑰。于是，凡是要向它或他發(fā)送加密信息的單位或個人都可以使用這些參數(shù)發(fā)送加密信息。

19、此外，RSA加密方法還有更廣泛的用途。下面介紹的數(shù)字簽名的方法就是一個例子。數(shù)字簽名在社會生活中，在處理具體事件時，常需要當事人進行簽證（簽名），以保證他做出的許諾或送出的信息的可靠性與合法性。例如，在簽署文件時，由當事人簽名，蓋章，簽署日期以及重要的特殊記號，常是不可少的環(huán)節(jié)。這樣的簽證，應該滿足一定的要求。假設A簽證一個文件給B，那么，() B應該能夠確定這是否A的簽證；() 任何其他人，無法偽造A的簽證，即A有其獨特的簽證方式；() 有一個仲裁簽證是否由A發(fā)出的方法，例如，當A否認這個簽證時，這樣的方法可以鑒定簽證的真?zhèn)巍Ｏ旅嫖覀冋f明，RSA加密方法可以用來進行簽證，不需要當事人到場，只

20、需傳送必要的信息。假設要簽證的信息是M（例如，它是簽證人的姓名，簽證日期，特定的標志，等等），并且，已經(jīng)根據(jù)信息M所使用的符號將它與一個正整數(shù)對應。為方便計，我們就同時用M表示簽證以及它所對應的正整數(shù)。設A要將簽證信息M傳送給B。又設向 A和B傳送信息時使用的RSA加密方法分別是RSA(nA, eA)和RSA(nB, eB)，設A和B的保密鑰分別是dA，pA，qA，和dB，pB，qB 。在第一節(jié)中我們已經(jīng)談到，不妨假定M < nA 。A要將簽證信息M傳送給B時，首先計算E1 º(mod nA)，0 £ E1 < nA 。 (5)同樣地，不妨假定E1 < n

21、B 。再計算E º(mod nB)，0 £ E < nB 。 (6)然后，A將E傳送給B。nB和eB是公開的，而dA卻只有A知道，所以，其他人是無法依照上述步驟進行偽造的。B收到信息E后，計算M1 º(mod nB)，0 £ M1 < nB ， (7)M0 º(mod nA)，0 £ M0 < nA ， (8)并且進行驗證是否M0 = M。事實上，由定理1以及式(5)，式(6)，式(7)和式(8)，應該有M1 º(mod nB)， M1 = E1，M0 º(mod nA)，M0 = M。對B來說，

22、上述驗證過程是容易的，因為他知道dB 。顯然，任何第三者都可以按照式(7)和式(8)鑒定收到的信息是否A的簽證。這樣，此處所提供的數(shù)字簽名方法是滿足上面的三個要求的。做為本節(jié)的結尾，我們指出，RSA加密方法的基礎是命題“將大整數(shù)分解成素因數(shù)乘積在計算上是困難的”。此處所謂“計算上困難”與素因數(shù)的大小以及人們的計算能力是有關的。如果限定素因數(shù)的大小，那么，當人們的計算能力達到一定水平的時候，這個命題就不成立了，那時，RSA加密方法也就不再是安全的了。習 題 二 1. 設一RSA的公開加密鑰為n = 943，e = 9，試將明文P = 100加密成密文E。 2. 設RSA(nA, eA) = RS

23、A(33, 3)，RSA(nB, eB) = RSA(35, 5)，A的簽證信息為M = 3，試說明A向B發(fā)送簽證M的傳送和認證過程。第三節(jié) 孫子定理的應用本節(jié)要介紹孫子定理在信息加密中的兩個應用。一、文件集合的加密假設A是由n個文件F1, F2, L, Fn 組成的集合，它們分別屬于n個單位（例如，n個個人，公司，工廠，等等）。又設按某種方法使這n個文件與n個整數(shù)對應。為簡便計，我們仍用F1, F2, L, Fn表示每個文件所對應的整數(shù)。下面敘述一種對集合A的加密方法，滿足這樣的要求：每個單位可以很方便地查閱集合A中屬于自己的文件，卻很難查閱集合A中不屬于自己的文件。設正整數(shù)m1, m2,

24、L, mn滿足條件mi > Fi（1 £ i £ n），(mi, mj) = 1（i ¹ j，1 £ i，j £ n），記M = m1m2Lmn，Mi =（1 £ i £ n）。 (1)又設Mi¢（1 £ i £ n）由下面的同余式確定：MiM i¢ º 1 (mod mi)，1 £ Mi¢ £ m 。 (2) MiM i¢ (mod M)，0 £ £M-1。將集合A按下面的方式進行加密：E = E(A) &#

25、186;(mod M)，1 £ E £ M。 (3)若要從密文E求出Fi，可利用同余式Fi º E º (mod mi)，0 £ Fi < mi。 (4)在上面所用的加密方法中，數(shù)據(jù)mi，Mi以及Mi¢（1 £ i £ n）都是保密的。顯然，() 只有掌握mi，才能利用式(4)由E得到Fi；() 在掌握mi的情況下，可以求出Fi，也可以對它進行修改。例如，修改成Fi¢，并且，在修改之后，還可以重新對由F1, L, Fi -1, Fi¢, Fi + 1, L, Fn 組成的新集合A¢

26、;進行加密；() 無論求出Fi或者對Fi進行修改，都對其他文件Fj（j ¹ i）沒有影響。例1 設某數(shù)據(jù)庫含四段文字：F1 = 7，F(xiàn)2 = 9，F(xiàn)3 = 12，F(xiàn)4 = 15，取m1 = 11，m2 = 13，m3 = 17，m4 = 19，則M = 11×13×17×19 = 46189，M1 = 13×17×19 = 4199，M2 = 11×17×19 = 3553，M3 = 11×13×19 = 2717，M4 = 11×13×17 = 2431，M1¢

27、= 7，M2¢ = 10，M3¢ = 11，M4¢ = 18,e1=4199×7, e2=3553×10, e3=2717×11, e4=2431×18。對集合7, 9, 12, 15加密，得到E = E(A) º = 4199×7×7 + 3553×10×9 +2717×11×12 + 2431×18×15 º 16298 (mod 46189)，即E = 16298。若要求出F2，則由F2 º 16298

28、86; 9 (mod 13)得到F2 = 9。若要將F2改變成10，并且將新的數(shù)據(jù)庫加密，則使用上面的方法，對7, 10, 12, 15加密，得到E¢ º 4199×7×7 + 3553×10×10 + 2717×11×12 + 2431×18×15º 5639 (mod 46189)即E¢ = 5639。二、秘密共享假定有一個文件M與r個人有關。為了共同的利益，他們約定，只有當他們中的至少s（s £ r）個人同意時，才可以把M公開。這樣，就需要一種滿足下述條件的加

29、密方法：() r個人各掌握一個與這個加密方法有關的數(shù)據(jù)；() 利用s個不同的數(shù)據(jù)可以很容易地求出M；() 如果知道的數(shù)據(jù)少于s個，那么求出M是很難的?，F(xiàn)在，我們來提出一個滿足這些條件的加密方法。選取素數(shù)p > M，又選取兩兩互素的正整數(shù)m1, m2, L, mr，使得m1 < m2 < L < mr ，pm1m2Lmr ，m1m2Lms ³ pmrmr - 1Lmr - s + 2。 (5)又隨機地選取正整數(shù)t，使得t £-1。 (6)我們這樣來計算第i（i = 1, 2, L, r）個人所要掌握的數(shù)據(jù)：Ei º M + tp (mod m

30、i)，0Ei<mi, i = 1, 2, L, r。下面，我們說明E1, E2, L, Er是滿足上述要求()，()，()的數(shù)據(jù)。顯然，只需證明條件()和()是滿足的。條件()：由s個不同的數(shù)據(jù)可以容易地求出M。設這s個數(shù)據(jù)。由孫子定理我們知道，存在唯一的x0，0 £ x0<，滿足方程組x º，1 £ k £ s 。 (7)顯然M + tp滿足方程組(7)，而且，由于p > M以及式(6)，有M + tp < (t + 1)p £ m1m2Lms £， (8)因此，必是x0 = M + tp，即M = x0 -

31、 tp。條件()：如果僅僅知道，l £ s - 1，則確定M是很困難的。事實上，由孫子定理，方程組x º，1 £ k £ l (9)對模有唯一解x0，0 £ x0 < 。因為是兩兩互素的，由Ei的定義，顯然x0 º M + tp (mod )。 (10)即M + tp - x0 = l， (11)其中l(wèi)是整數(shù)。要確定M的值，必須確定l的數(shù)值。我們要說明，確定l的數(shù)值是困難的。事實上，由式(11)，得到0 £ l £。 (12)另一方面，由式(5)式(6)和l £ s - 1，以及0 £ x

32、0 << mrmr - 1Lmr - s + 2得到- 1。由式(8)我們見到，M + tp的取值范圍是從1到m1m2Lms ，因此，利用式(5)可知，的取值范圍是從1到p - 1，于是，由式(12)，l的取值范圍是從0到p - 1，當p很大的時候，確定l的數(shù)值顯然是困難的，例2 設由三方共同管理的一份文件是M = 5。取p = 7，m1 = 11，m2 = 12，m3 = 17，則11×12 > 7×17。取t = 14 <，分配給三方的數(shù)據(jù)分別是E1 º 5 + 14×7 º 4 (mod 11)，E1 = 4；E2

33、 º 5 + 14×7 º 7 (mod 12)，E2 = 7；E3 º 5 + 14×7 º 1 (mod 17)，E3 = 1。由E1，E2與E3中的任意兩個都可以確定出M。例如，假設已知E1 = 4和E2 = 7，則利用孫子定理，得到方程組x º 4 (mod 11)，x º 7 (mod 12)的解x0 º 103 (mod 11×13)，于是M = x0 - tp = 103 - 14×7 = 5 。習 題 三1. 設某數(shù)據(jù)庫由四個文件組成：F1 = 4，F(xiàn)2 = 6，F(xiàn)3

34、= 10，F(xiàn)4 = 13。試設計一個對該數(shù)據(jù)庫加密的方法，但要能取出個別的Fi（1 £ i £ 4），同時不影響其他文件的保密。2. 利用本節(jié)中的秘密共享方案，設計一個由三方共管文件M = 3的方法，要求：只要有兩方提供他們所掌握的數(shù)據(jù)，就可以求出文件M，但是，僅由任何一方的數(shù)據(jù)，不能求出文件M。（提示：取p = 5，m1 = 8，m2 = 9，m3 = 11）第四節(jié) 背包型加密體制假設a1, a2, L, an是正整數(shù)，對于給定的整數(shù)b，方程a1x1 + a2x2 + L + anxn = b (1)是否有0-1解，即解(x1, x2, L, xn)，xi = 0或1（1

35、 £ i £ n）？這就是“背包問題”。一般地，求解背包問題是計算上困難的。但是，對于某些特殊的a1, a2, L, an，背包問題是容易解決的。例如，若a1, a2, L, an滿足條件ai >a1 + a2 + L + ai - 1 ，2 £ i £ n ， (2)則解方程(1)可以按以下步驟進行：() 比較b與an，若an > b，則xn = 0；否則，xn = 1；() 若xn, xn - 1, L, xk + 1已經(jīng)確定，則由方程a1x1 + a2x2 + L + akxk = b - (anxn + L + ak + 1xk +

36、1)及步驟()確定xk。() 重復步驟()與()，直到求出所有的xi（1 £ i £ n）：或者，斷定方程(1)沒有0-1解。定義1 若a1, a2, L, an都是正整數(shù)，則稱向量(a1, a2, L, an)是背包向量。稱滿足條件(2)的背包向量為超增背包向量，或超增向量。如上所述，一般地，求解背包問題是計算上困難的。但是，對于某些特殊的背包向量（例如，超增背包向量），求解背包問題并不困難。求解一般的背包問題與特殊的背包問題在計算困難程度上的差別，是設計背包型加密方法的基礎。1978年，R. C. Merkel與M. E. Hellman提出了一個加密方法，是以求解背包

37、問題的計算困難性為基礎的，這個方法，稱為MH加密方法。MH加密方法的設計 參數(shù)的選取隨機地選取正整數(shù)M，k，(M, k) = 1，以及超增背包向量(a1, a2, L, an)，使得a1 + a2 + L + an < M; (3) 計算bi º kai (mod M)，1 £ bi < M，1 £ i £ n (4)以及正整數(shù)k -1，使得kk -1 º 1 (mod M )。 (5)將背包向量(b1, b2, L, bn)公開, 稱為加密鑰。正整數(shù)M，k，k -1則保密。 明文的加密設明文的二進制表示是P = (p1p2Lpn)

38、2，則與P對應的密文是E = b1p1 + b2p2 + L + bnpn。 (6) 解密() 計算E0 º k -1E (mod M)，0 £ E0 < M。 (7)() 由E0 = a1p1 + a2p2 + L + anpn (8)求出p1, p2, L, pn 。注1：一般地，用MH(b1, b2, L, bn)表示上面所定義的加密方法。注2：我們來說明由式(8)所確定的(p1p2Lpn)2就是明文P。事實上，由式(6)和式(5)，有 k -1E = k -1(b1p1 + b2p2 + L + bnpn) º kk -1(a1p1 + a2p2 +

39、 L + anpn)º a1p1 + a2p2 + L + anpn (mod M)。由式(3)，得到0 £ a1p1 + a2p2 + L + anpn £ a1 + a2 + L + an < M。所以，由上式和式(7)，可知E0 = a1p1 + a2p2 + L + anpn。因此，由式(8)得到的p1, p2, L, pn就是明文P的二進制表示的位數(shù)碼。例1 利用超增背包向量(2, 3, 6, 12, 24, 48)設計一個背包型加密方法，將明文P = 47加密。解 取M = 99，k = 5，k -1 = 20，計算b1 º 5

40、5;2 = 10 (mod 99)，取b1 = 10。同樣的，計算b2 º 5×3 = 15 (mod 99)，取b2 = 15，b3 º 5×6 = 30 (mod 99)，取b3 = 30，b4 º 5×12 = 60 (mod 99)，取b4 = 60，b5 º 5×24 º 21 (mod 99)，取b5 = 21，b6 º 5×48 º 42 (mod 99)，取b6 = 42。對外公開的加密向量是(10, 15, 30, 60, 21, 42)。由于P = 47 = (101111)2，所以與P對應的密文是E = 10×1 + 15×0 + 30×1 + 60×1 + 21×1 + 42×1 = 163。若要從密文16