數(shù)論與組合數(shù)學(xué)第五章數(shù)論的應(yīng)用

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

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

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

4、對(duì)應(yīng)的數(shù)字就是2214240014110008。在實(shí)際應(yīng)用中，一個(gè)文件所對(duì)應(yīng)的整數(shù)是一個(gè)很大的數(shù)字，所以，人們往往要對(duì)大的正整數(shù)進(jìn)行處理，使它們可以與較小的正整數(shù)列對(duì)應(yīng)，從而容易進(jìn)行加密運(yùn)算。我們知道，對(duì)于給定的正整數(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建立了一一對(duì)應(yīng)的關(guān)系，對(duì)大整數(shù)P的加密就轉(zhuǎn)化為對(duì)不超過(guò)k的整數(shù)pi（0 £ i £ n）的加密。以下

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

6、密：對(duì)于密文E，計(jì)算P0 º a ¢(E - b) (mod M)，0 £ P0 < M， (3)P0就是與E對(duì)應(yīng)的明文P?，F(xiàn)在，我們說(shuō)明式(3)中確定的P0就是明文P。事實(shí)上，由式(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 設(shè)符號(hào)a，b，L，y，z分別與整數(shù)0，1，L，24，25

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

8、，“a ® 00”，“d ® 03”，等等。又用“Þ”表示明文和密文的對(duì)應(yīng)關(guān)系，例如，“s Þ a”“men Þ phq”，等等。例2 已知明文所使用的符號(hào)只是26個(gè)英文字母a，b，L，y，z，它們分別與整數(shù)00，01，L，24，25對(duì)應(yīng)，又知道使用公式E º P + b (mod 26)，0 £ E < 26 (4)對(duì)每個(gè)符號(hào)加密。已經(jīng)知道明文字母e與密文字母u對(duì)應(yīng)，試求出解密方法。解 將已知的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，這就是解密方法，也可以用下表說(shuō)明：表 3EabcdefghijklmPklmnopqrstuvwEnopqrstuvwxyzPxyzabcdefghij一般地，對(duì)于由式(2)定義的仿射加密方法，只要知道兩對(duì)（不同的）相對(duì)應(yīng)的明文和密文P1，E1與P2，E2，就可以求出解密方法。事實(shí)上，由式(2)及已知的對(duì)應(yīng)關(guān)系，得到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。當(dāng)(P2 - P1, M) = 1時(shí)，這樣的ai與bi只有一組，當(dāng)(P2 - P1, M) > 1時(shí)，為了確

11、定出正確的a與b，首先，利用(a，M) = 1刪去某些ai與bi，其次，用它們驗(yàn)證式（4）是否成立，并用它們?cè)囎g部分密文，就可以確定正確的a與b。將確定的a，b代入式(3)，就得到解密公式。習(xí) 題 一1. 利用例1中的加密方法，將“ICOMETODAY”加密。2. 已知字母a，b，L，y，z，它們分別與整數(shù)00，01，L，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)容

12、不被某一部分人（以后，我們稱(chēng)他們?yōu)椤皵撤健保┝私?；同時(shí)，這個(gè)信息的內(nèi)容應(yīng)該能夠被另一部分人（以后，我們稱(chēng)他們?yōu)椤坝逊健保┖苋菀椎亓私?。上一?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è)

13、足夠長(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è)滿(mǎn)足下述條件的函數(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)

14、與之對(duì)應(yīng)，同時(shí)，計(jì)算g(E)是困難的；() 如果掌握了關(guān)于函數(shù)g(E)的某種條件（信息），計(jì)算g(E)是容易的。在這一節(jié)，我們要介紹滿(mǎn)足上述三個(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，j(n) = (p - 1)(q - 1)，再隨機(jī)地取正整數(shù)e，(e, j(n) = 1，并計(jì)算d，使得ed º 1 (m

15、od j(n)。 (1)公開(kāi)n，e，供加密使用（稱(chēng)它們?yōu)镽SA加密鑰）；將p，q，j(n)和d保密（稱(chēng)它們?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 = p1p2Lpk是k個(gè)不同的素?cái)?shù)之積，e與d是正整數(shù)，(e, j(n) = 1，并且式(1)

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

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

18、n - j(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ū)別。 通常，稱(chēng)具有這種特點(diǎn)的加密方法為公鑰加密方法。公鑰加密方法使得信息的加密傳送更為方便。例如，每個(gè)單位或個(gè)人可以像公布電話(huà)號(hào)碼一樣公布自己的RSA加密鑰。于是，凡是要向它或他發(fā)送加密信息的單位或個(gè)人都可以使用這些參數(shù)發(fā)送加密信息。

19、此外，RSA加密方法還有更廣泛的用途。下面介紹的數(shù)字簽名的方法就是一個(gè)例子。數(shù)字簽名在社會(huì)生活中，在處理具體事件時(shí)，常需要當(dāng)事人進(jìn)行簽證（簽名），以保證他做出的許諾或送出的信息的可靠性與合法性。例如，在簽署文件時(shí)，由當(dāng)事人簽名，蓋章，簽署日期以及重要的特殊記號(hào)，常是不可少的環(huán)節(jié)。這樣的簽證，應(yīng)該滿(mǎn)足一定的要求。假設(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)，只

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

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

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

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

24、L, mn滿(mǎn)足條件mi > Fi（1 £ i £ n），(mi, mj) = 1（i ¹ j，1 £ i，j £ n），記M = m1m2Lmn，Mi =（1 £ i £ n）。 (1)又設(shè)Mi¢（1 £ i £ n）由下面的同余式確定：MiM i¢ º 1 (mod mi)，1 £ Mi¢ £ m 。 (2) MiM i¢ (mod M)，0 £ £M-1。將集合A按下面的方式進(jìn)行加密：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，也可以對(duì)它進(jìn)行修改。例如，修改成Fi¢，并且，在修改之后，還可以重新對(duì)由F1, L, Fi -1, Fi¢, Fi + 1, L, Fn 組成的新集合A¢

26、;進(jìn)行加密；() 無(wú)論求出Fi或者對(duì)Fi進(jìn)行修改，都對(duì)其他文件Fj（j ¹ i）沒(méi)有影響。例1 設(shè)某數(shù)據(jù)庫(kù)含四段文字：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。對(duì)集合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ù)庫(kù)加密，則使用上面的方法，對(duì)7, 10, 12, 15加密，得到E¢ º 4199×7×7 + 3553×10×10 + 2717×11×12 + 2431×18×15º 5639 (mod 46189)即E¢ = 5639。二、秘密共享假定有一個(gè)文件M與r個(gè)人有關(guān)。為了共同的利益，他們約定，只有當(dāng)他們中的至少s（s £ r）個(gè)人同意時(shí)，才可以把M公開(kāi)。這樣，就需要一種滿(mǎn)足下述條件的加

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

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

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

32、0 << mrmr - 1Lmr - s + 2得到- 1。由式(8)我們見(jiàn)到，M + tp的取值范圍是從1到m1m2Lms ，因此，利用式(5)可知，的取值范圍是從1到p - 1，于是，由式(12)，l的取值范圍是從0到p - 1，當(dāng)p很大的時(shí)候，確定l的數(shù)值顯然是困難的，例2 設(shè)由三方共同管理的一份文件是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中的任意兩個(gè)都可以確定出M。例如，假設(shè)已知E1 = 4和E2 = 7，則利用孫子定理，得到方程組x º 4 (mod 11)，x º 7 (mod 12)的解x0 º 103 (mod 11×13)，于是M = x0 - tp = 103 - 14×7 = 5 。習(xí) 題 三1. 設(shè)某數(shù)據(jù)庫(kù)由四個(gè)文件組成：F1 = 4，F(xiàn)2 = 6，F(xiàn)3

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

35、 £ i £ n）？這就是“背包問(wèn)題”。一般地，求解背包問(wèn)題是計(jì)算上困難的。但是，對(duì)于某些特殊的a1, a2, L, an，背包問(wèn)題是容易解決的。例如，若a1, a2, L, an滿(mǎn)足條件ai >a1 + a2 + L + ai - 1 ，2 £ i £ n ， (2)則解方程(1)可以按以下步驟進(jìn)行：() 比較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。() 重復(fù)步驟()與()，直到求出所有的xi（1 £ i £ n）：或者，斷定方程(1)沒(méi)有0-1解。定義1 若a1, a2, L, an都是正整數(shù)，則稱(chēng)向量(a1, a2, L, an)是背包向量。稱(chēng)滿(mǎn)足條件(2)的背包向量為超增背包向量，或超增向量。如上所述，一般地，求解背包問(wèn)題是計(jì)算上困難的。但是，對(duì)于某些特殊的背包向量（例如，超增背包向量），求解背包問(wèn)題并不困難。求解一般的背包問(wèn)題與特殊的背包問(wèn)題在計(jì)算困難程度上的差別，是設(shè)計(jì)背包型加密方法的基礎(chǔ)。1978年，R. C. Merkel與M. E. Hellman提出了一個(gè)加密方法，是以求解背包

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

38、2，則與P對(duì)應(yīng)的密文是E = b1p1 + b2p2 + L + bnpn。 (6) 解密() 計(jì)算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：我們來(lái)說(shuō)明由式(8)所確定的(p1p2Lpn)2就是明文P。事實(shí)上，由式(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的二進(jìn)制表示的位數(shù)碼。例1 利用超增背包向量(2, 3, 6, 12, 24, 48)設(shè)計(jì)一個(gè)背包型加密方法，將明文P = 47加密。解 取M = 99，k = 5，k -1 = 20，計(jì)算b1 º 5

40、5;2 = 10 (mod 99)，取b1 = 10。同樣的，計(jì)算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。對(duì)外公開(kāi)的加密向量是(10, 15, 30, 60, 21, 42)。由于P = 47 = (101111)2，所以與P對(duì)應(yīng)的密文是E = 10×1 + 15×0 + 30×1 + 60×1 + 21×1 + 42×1 = 163。若要從密文16