數(shù)論在密碼學中的應用new

1、 本科學生畢業(yè)論文（設計） 題目（中文）： 數(shù)論在密碼學中的應用 （英文）： The Application of Number Theory in Cryptography 姓 名 龍 瑞 學 號 200805001104 院 （系） 湖南科技學院數(shù)學與計算科學系 專業(yè)、年級 數(shù)學與應用數(shù)學 0801班 指導教師 王啟春（博士） 2012年 5 月 1日湖南科技學院本科畢業(yè)論文（設計）誠信聲明本人鄭重聲明：所呈交的本科畢業(yè)論文（設計），是本人在指導老師的指導下，獨立進行研究工作所取得的成果，成果不存在知識產(chǎn)權爭議，除文中已經(jīng)注明引用的內(nèi)容外，本論文不含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的作品

2、成果。對本文的研究做出重要貢獻的個人和集體均已在文中以明確方式標明。本人完全意識到本聲明的法律結果由本人承擔。 本科畢業(yè)論文（設計）作者簽名： 二一二年五月一日 目錄1緒論11.1引言11.2數(shù)學語言12數(shù)論22.1同余32.2質數(shù)與互質32.3因數(shù)分解42.4幾個定理的證明53密碼學64 RSA算法74.1公開密鑰74.2現(xiàn)行公鑰RSA加密算法的基本思想74.3公鑰與密鑰的產(chǎn)生94.4加密消息94.5解密消息94.6實例說明RSA算法的全過程104.7簽名消息104.8安全性114.9 RSA前景115背包原理125.1背包原理125.2超遞增序列135.3背包系統(tǒng)的加密和解密方法146結束

3、語15主要參考資料：16致謝17數(shù)論在密碼學中的應用摘要論文介紹了一些數(shù)論的基本知識和密碼學的主要思想。并著重從RSA算法與背包原理算法兩個方面介紹了數(shù)論在密碼學中的應用。而且構造了一個簡單的數(shù)學語言體系對背包原理和RSA的實例講解。本文把數(shù)論蘊含在整個密碼學的兩種算法的闡述之中，其重點是現(xiàn)行的公鑰體制RSA，全面的介紹了其產(chǎn)生，運用，安全性，發(fā)展，未來前景及局限性。關鍵詞： RSA算法，背包原理，數(shù)論，密碼學，公鑰體制The Application of Number Theory in CryptographyAbstractThis paper introduces some basic

4、 knowledge of number theory and cryptography, Emphasize from RSA algorithm and knapsack algorithm, it will introduce the two aspects of the application of number theory in cryptography. And constructed a simple mathematical language system on the backpack principle and RSA examples to explain.In thi

5、s paper, the number theory is described in all the two algorithms in cryptography, the focus is on current public key system RSA, a comprehensive introduction to the use of safety, development, future prospects and limitations.Key words: RSA algorithm, knapsack theory, number theory, cryptography, p

6、ublic key systemIII1緒論1.1引言數(shù)論是數(shù)學中最古老、最純粹的一個重要數(shù)學分支。素有“數(shù)學王子”之稱的19世紀德國數(shù)學大師高斯就曾說過，數(shù)學是科學的皇后，數(shù)論是數(shù)學的皇后。數(shù)論，顧名思義，是一門研究數(shù)字性質的學問。一般所謂的數(shù)論，特指正整數(shù)(即自然數(shù))的許多性質，例如同余、質數(shù)、數(shù)論函數(shù)、有限域、背包原理等。密碼學是研究編制密碼和破譯密碼的技術科學。研究密碼變化的客觀規(guī)律，應用于編制密碼以保守通信秘密的，稱為編碼學；應用于破譯密碼以獲取通信情報的，稱為破譯學?？偡Q密碼學。密碼學，起初是應用于軍事信息的保密上，但是隨著當今社會計算機網(wǎng)絡的發(fā)展，尤其是電子商務的普及與深入，密碼

7、設計在非軍事領域也大有用武之地,密碼已經(jīng)與我們每一位息息相關。而密碼學的發(fā)展到現(xiàn)在與數(shù)學，特別數(shù)學的基礎數(shù)論已經(jīng)密不可分，可以說密碼學是數(shù)論從理論到現(xiàn)實的一個應用，而數(shù)論是密碼學走向更高的基石。1.2數(shù)學語言為了本文的討論方便，現(xiàn)就本文涉及到的自然語言與數(shù)學語言做如下規(guī)定；1.本文將一個字母代替整個傳輸過程中的數(shù)據(jù)，也就是一個字母成立則對于由字母構成的所有整體也成立。2.由于文字母只有26個，本文計算過程中，為了簡化，不考慮語言中問號、驚嘆號、逗號與句號等的區(qū)別，只考慮語言的停頓間隙，并一律用空格表示，那么，組成數(shù)字語言的基本單位就有了共27個（），將不使用ASCII值，只使用如下表所示的字母

8、和數(shù)學語言的簡單對應如表1。表1字母二進制數(shù)十進制數(shù)字母二進制數(shù)十進制數(shù)a000011o0111115b000102p1000016c000113q1000117d001004r1001018e001015s1001119f001106t1010020g001117u1010121h010008v1011022i010019w1011123j0101010x1100024k0101111y1100125l0110012z1101026m0110113空格000000n01110142數(shù)論數(shù)論就是指研究整數(shù)性質的一門理論。整數(shù)的基本元素是素數(shù)，所以數(shù)論的本質是對素數(shù)性質的研究。2000年前，歐幾

9、里得證明了有無窮個素數(shù)。尋找一個表示所有素數(shù)的素數(shù)通項公式，或者叫素數(shù)普遍公式，是古典數(shù)論最主要的問題之一。它是和平面幾何學同樣歷史悠久的學科。高斯譽之為“數(shù)學中的皇冠” 按照研究方法的難易程度來看，數(shù)論大致上可以分為初等數(shù)論（古典數(shù)論）和高等數(shù)論（近代數(shù)論）。 初等數(shù)論主要包括整除理論、同余理論、連分數(shù)理論。它的研究方法本質上說，就是利用整數(shù)環(huán)的整除性質。初等數(shù)論也可以理解為用初等數(shù)學方法研究的數(shù)論。其中最高的成就包括高斯的“二次互反律”等。高等數(shù)論則包括了更為深刻的數(shù)學研究工具。它大致包括代數(shù)數(shù)論、解析數(shù)論、算術代數(shù)幾何等等。下面粗略的介紹一些在本文中需要應用的數(shù)論中的知識。2.1同余設m

10、是大于1的正整數(shù)，a,b是整數(shù)，如果ma-b,則稱a，b關于模m同余，記作ab(mod m),讀作a同余b模m。通俗的講就是m除a,b余數(shù)相同則a,b關于m同余。例如5和7除以2，余數(shù)都是1，則5和7關于2同余。同余有如下性質:(1) ；(2)若，則；(3)如果， ，那么；(4)如果， 那么，；(5)若，則； (6)如果那么 ；(7)若， 則；(8)若，則，其中表示的最小公倍數(shù)；(9)歐拉定理：設 ，指模m的簡系個數(shù)，；2.2質數(shù)與互質如果一個整數(shù)（1除外）只有1和它本身兩個約數(shù)，則這個數(shù)是質數(shù)（即素數(shù)）。若兩正整數(shù)p,q的最大公因子(約數(shù))是1，則我們稱p,q互質，以(p,q)=1表示之。如

11、13是質數(shù)，13與28互質。素性檢測是數(shù)論中一個經(jīng)典的問題 ，近代密碼學的興起給它注入了新的活力 ，其中最重要的是素數(shù)的判定 ，特別是在素數(shù)的生成和分解。強素數(shù)的提出源自RSA對p,q兩素數(shù)的要求。橢圓曲線公鑰密碼中所涉及到大特征基域的尺寸和安全橢圓曲線的基點 的階也需要是確定意義下的素數(shù) ，而不是概率素數(shù) 。 目前，學術界關于素性證明的算法有兩種 ：一種是橢圓曲線素性證明，現(xiàn)已列入IEEE標準P1363中；另一種是現(xiàn)行公開密鑰碼系統(tǒng)最常用的 Miller-Rabin素數(shù)測試 。 1)素數(shù)分布定理：設為小于或等于的全部素數(shù)個數(shù) ，則 。2)威爾遜定理：n是素數(shù)的充要條件下有： 。威爾遜定理給出

12、判定素數(shù)充要條件 ，有很高的理論價值 。但用來尋找素數(shù)不適當 。 3)Fermat 定理（費馬小定理）：關于素數(shù)還有一個 Fermat 定理。此定理給出素數(shù)的必要條件 p ，若不滿足 ，則可斷定它為素數(shù) 定理內(nèi)容為，若p是素數(shù) ，則對于任意的整數(shù)a ，應有 。2.3因數(shù)分解整數(shù)分解（質因子分解）問題是指：給出一個正整數(shù)，將其寫成幾個質數(shù)的乘積。例如，給出45這個數(shù)，它可以分解成32 ×5。本文接下來要著重介紹的RSA算法就是一個基于大數(shù)分解的算法。而RSA用到都是128bit及以上的大數(shù)，用計算機和人腦都是很難分解的。下面給大家介紹一種大數(shù)分解的方法讓大家體驗一下大數(shù)分解的難度：幾率

13、演算法：首先選定一個簡單的整數(shù)多項式,如，再任選并且依序計算。然后計算，且，若q可以整除n，則q是n的一個因數(shù)。例如： 所以我們得到了91的一個質因數(shù)7，另外一個13也可以用類似方法求出。但是這還只是兩位的，要是對于更大的數(shù)，我們要處理的次數(shù)就越多，它的質因數(shù)每增加一個，計算量就成指數(shù)增加，所以即使你懂得了分解方法，要用計算機去分解一個大數(shù)（128bit及以上）要需要幾十年年的時間。2.4幾個定理的證明1)若兩正整數(shù)互質，則可以找到二整數(shù)(不一定正) 使得證明：令A為含所有為整數(shù)之集合，此集合顯然不是空集合，因可取。令d為此集合中之最小者，若，則本定理得證，若，令，則任取此集中之另一數(shù)。，則我

14、們?nèi)粢詃除，則得代入則得此r必為0，否則r為A集中一小于d之數(shù)，與假設d為最小數(shù)相矛盾，因r=0故d為A集中任何一數(shù)之因子。因故d為之公因子。但之最大公因子為1，故d=1，定理證畢。2)若w與m為二互質的正整數(shù)且，則可找到一正整數(shù)使得證明：由定理知，有二整數(shù)使得，因為之倍數(shù)，故令則得且因不可能為0，故得證。3)若為質數(shù)，為任一與互質之整數(shù)，則證明：先把w寫成w個1的和，則由多項式定理知之展開式中除w個1之外，都含有之因子，(為質數(shù)中之不可能消去)，故兩邊乘以2)中之a(chǎn)，即得本定理證畢。3密碼學密碼學是研究編制密碼和破譯密碼的技術科學。研究密碼變化的客觀規(guī)律，應用于編制密碼以保守通信秘密的，稱為

15、編碼學；應用于破譯密碼以獲取通信情報的，稱為破譯學?？偡Q密碼學。 密碼學是研究如何隱密地傳遞信息的學科。在現(xiàn)代特別指對信息以及其傳輸?shù)臄?shù)學性研究，常被認為是數(shù)學和計算機的分支，密碼學的首要目的是隱藏信息的涵義，并不是隱藏信息的存在。密碼學也促進了計算機科學，特別是在于電腦與網(wǎng)絡安全所使用的技術，如訪問控制與信息的機密性。密碼學已被應用在日常生活：包括銀行卡的優(yōu)盾、電腦使用者存取密碼、qq等網(wǎng)絡應用密碼等等。 密碼是通信雙方按約定的法則進行信息特殊變換的一種重要保密手段。依照這些法則，變明文為密文，稱為加密變換；變密文為明文，稱為脫密變換。密碼在早期僅對文字或數(shù)碼進行加、脫密變換，隨著通信技術的

16、發(fā)展，對語音、圖像、數(shù)據(jù)等都可實施加、脫密變換。 密碼學是在編碼與破譯的斗爭實踐中逐步發(fā)展起來的，并隨著先進科學技術的應用，已成為一門綜合性的尖端技術科學。它與語言學、數(shù)學、電子學、聲學、信息論、計算機科學等有著廣泛而密切的聯(lián)系。它的現(xiàn)實研究成果，特別是各國政府現(xiàn)用的密碼編制及破譯手段都具有高度的機密性。 4 RSA算法4.1公開密鑰進行明密變換的法則，稱為密碼的體制。指示這種變換的參數(shù)，稱。為密鑰。它們是密碼編制的重要組成部分。密碼體制的基本類型可以分為四種：錯亂即按照規(guī)定的圖形和線路，改變明文字母或數(shù)碼等的位置成為密文；代替即用一個或多個代替表將明文字母或數(shù)碼等代替為密文；密本即用預先編定

17、的字母或數(shù)字密碼組，代替一定的詞組單詞等變明文為密文；加亂即用有限元素組成的一串序列作為亂數(shù)，按規(guī)定的算法，同明文序列相結合變成密文。以上四種密碼體制，既可單獨使用，也可混合使用 ，以編制出各種復雜度很高的實用密碼。公開密鑰算法是在1976年由當時在美國斯坦福大學的迪菲（Diffie）和赫爾曼(Hellman)兩人首先發(fā)明的（論文”New Direction in Cryptography”）。但目前最流行的RSA是1977年由MIT教授Ronald L.Rivest,Adi Shamir和Leonard M.Adleman共同開發(fā)的,分別取自三名數(shù)學家的名字的第一個字母來構成的。4.2現(xiàn)行公

18、鑰RSA加密算法的基本思想公鑰加密算法中使用最廣的是RSA。RSA使用兩個密鑰，一個公共密鑰，一個專用密鑰。因為公鑰是公開對外發(fā)布的，所以想給私鑰持有者發(fā)送信息的人都可以取得公鑰，用公鑰加密后，發(fā)送給私鑰持有者，即使被攔截或竊取，沒有私鑰的攻擊者也無法獲得加密后的信息，可以保證信息的安全傳輸 另外，先用私鑰加密，再用公鑰解密，可以完成對私鑰持有者的身份認證，因為公鑰只能解開有私鑰加密后的信息。 雖然公鑰和私鑰是一對互相關聯(lián)的密鑰，但是并不能從兩者中的任何一把，推斷出另一把。如用其中一個加密，則可用另一個解密，密鑰長度從40到2048bit可變，加密時也把明文分成塊，塊的大小可變，但不能超過密鑰

19、的長度，RSA算法把每一塊明文轉化為與密鑰長度相同的密文塊。密鑰越長，加密效果越好，但加密解密的開銷也大，所以要在安全與性能之間折衷考慮，一般64位是較合適的。RSA的一個比較知名的應用是SSL，在美國和加拿大SSL用128位RSA算法，由于出口限制，在其它地區(qū)（包括中國）通用的則是40位版本。下面用一個簡單的示意圖，幫助大家理解基于RSA算法的數(shù)據(jù)傳輸（加密與解密）過程。基于RSA算法的數(shù)據(jù)傳輸過程圖3.1數(shù)據(jù)傳送方的數(shù)據(jù)加密后的數(shù)據(jù)加密RSA算法數(shù)據(jù)接收方的公鑰解密RSA算法數(shù)據(jù)接收方的私鑰數(shù)據(jù)接收方獲得原始數(shù)據(jù)從圖3.1中我們可以看出所謂的公開密鑰密碼體制（下文通常默認指RSA）就是使用

20、不同的加密密鑰與解密密鑰(兩者都由數(shù)據(jù)接收者持有，公鑰是公開的，而私鑰是接收者所獨有的)。RSA算法是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在的三十多年里，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰方案之一。在公開密鑰密碼體制中，加密密鑰（即公開密鑰）PK是公開信息，而解密密鑰（即秘密密鑰）SK是需要保密的。加密算法E和解密算法D也都是公開的。雖然秘密密鑰SK是由公開密鑰PK決定的，但卻不能根據(jù)PK計算出SK。4.3公鑰與密鑰的產(chǎn)生假設A給B傳送一個消息，A可以用以下的方式來產(chǎn)生一個公鑰和一個私鑰：1. 根據(jù)歐

21、拉函數(shù)，不大于且與互質的整數(shù)個數(shù)為.選擇一個整數(shù)與互質，并且小于.用以下這個公式計算.將和的記錄銷毀。是公鑰，是私鑰。是秘密的。A將她的公鑰傳給B，而將她的私鑰藏起來。4.4加密消息因為B知道產(chǎn)生的和。他使用起先與A約好的格式將轉換為一個小于N的整數(shù)n，比如他可以將每一個字轉換為這個字的Unicode碼，然后將這些數(shù)字連在一起組成一個數(shù)字。假如他的信息非常長的話，他可以將這個信息分為幾段，然后將每一段轉換為n。用下面這個公式他可以將n加密為c：。計算c并不復雜。B算出c后就可以將它傳遞給A。4.5解密消息A得到B的消息c后就可以利用她的密鑰d來解碼。他可以用以下這個公式來將c轉換為n：。得到n

22、后，他可以將原來的信息m重新復原。解碼的原理是以及和。由費馬小定理可證明（因為p和q是質數(shù)）和。這說明（因為p和q是不同的質數(shù)，所以p和q互質）。4.6實例說明RSA算法的全過程下文將通過一個數(shù)據(jù)傳輸假設（此假設省略了加密過程中的數(shù)據(jù)轉換過程）為大家講解RSA加密算法的實現(xiàn)?，F(xiàn)在假設數(shù)據(jù)發(fā)送方（A）要給數(shù)據(jù)接受方（B）發(fā)送一個私人數(shù)據(jù)sa,按照表1不煩把sa對應成數(shù)學語言1901（十進制對應）。比如傳輸1901的時候我們選取p=47,q=59則n=2773。不妨選擇d=157,則根據(jù)4.3中可以算出e=17。把明文1901自乘e（=17）次，并模n（=2773）得到余數(shù)1281，就是密文。這就

23、是加密的全過程了，而解密的時候我們接收方已經(jīng)知道了密文1281，密鑰d=157以及公鑰n=2773利用4.5中的公式，也就是說我們只要把模去若干個n即可得到明文1901，再把1901根據(jù)表1翻譯成自然語言就是sa。這里牽涉到兩個很大的數(shù)的同余問題，可以參考一下高等教育出版社的競賽數(shù)學教程第二版。以第一個計算除以2773的余數(shù)為例，很容易看出，進而進而可以算得，從而，這樣我們就得到密文了。4.7簽名消息RSA也可以用來為一個消息署名。假如甲想給乙傳遞一個署名的消息的話，那么她可以為她的消息計算一個散列值(Message digest)，然后用她的密鑰(private key)加密這個散列值并將這

24、個“署名”加在消息的后面。這個消息只有用她的公鑰才能被解密。乙獲得這個消息后可以用甲的公鑰解密這個散列值，然后將這個數(shù)據(jù)與他自己為這個消息計算的散列值相比較。假如兩者相符的話，那么他就可以知道發(fā)信人持有甲的密鑰，以及這個消息在傳播路徑上沒有被篡改過。4.8安全性假設偷聽者乙獲得了甲的公鑰N和e以及丙的加密消息c，但她無法直接獲得甲的密鑰d。要獲得d，最簡單的方法是將N分解為p和q，這樣她可以得到同余方程并解出d，然后代入解密公式導出n（破密）。但至今為止還沒有人找到一個多項式時間的算法來分解一個大的整數(shù)的因子，同時也還沒有人能夠證明這種算法不存在。至今為止也沒有人能夠證明對N進行因數(shù)分解是唯一

25、的從c導出n的方法，但今天還沒有找到比它更簡單的方法。（至少沒有公開的方法。）因此今天一般認為只要N足夠大，那么黑客就沒有辦法了。假如N的長度小于或等于256位，那么用一臺個人電腦在幾個小時內(nèi)就可以分解它的因子了。1999年，數(shù)百臺電腦合作分解了一個512位長的N。今天對N的要求是它至少要1024位長。1994年彼得·秀爾（Peter Shor）證明一臺量子計算機可以在多項式時間內(nèi)進行因數(shù)分解。假如量子計算機有朝一日可以成為一種可行的技術的話，那么秀爾的算法可以淘汰RSA和相關的衍生算法。（即依賴于分解大整數(shù)困難性的加密算法）假如有人能夠找到一種有效的分解大整數(shù)的算法的話，或者假如量

26、子計算機可行的話，那么在解密和制造更長的鑰匙之間就會展開一場競爭。但從原理上來說RSA在這種情況下是不可靠的。4.9 RSA前景針對RSA最流行的攻擊一般是基于大數(shù)因數(shù)分解。1999年，RSA-155（512 bits）被成功分解，花了五個月時間（約8000 MIPS年）和224 CPU hours在一臺有3.2G中央內(nèi)存的Cray C916計算機上完成 。2002年，RSA-158也被成功因數(shù)分解。RSA-158表示如下：39505874583265144526419767800614481996020776460304936454139376051579355626529450683609

27、727842468219535093544305870490251995655335710209799226484977949442955603= 3388495837466721394368393204672181522815830368604993048084925840555281177×116588234066712599031483765583832708181310122581463926004395209941313443341629245361392009年12月12日，編號為RSA-768 （768 bits, 232 digits）數(shù)也被成功分解1。這一事件威脅了

28、現(xiàn)通行的1024-bit密鑰的安全性，普遍認為用戶應盡快升級到2048-bit或以上。RSA-768表示如下：1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413= 33478071698

29、956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489×6032283815739666511279233373417143396810270092798736308917盡管這樣RSA加密在相當一段時間內(nèi)還是很有市場的，除非量子計算機真正的問世，還有就是RSA由于需求的位數(shù)越來越高，計算的速度也會越來越慢，對計算機的要求也會越高，個人認為終有被取代的一天，而且其中新加密方法也要必不可少的運用到數(shù)學的思想！5背包原理5.1背包原理

30、設想有一個長方體形狀的背包，里面恰好裝滿一組大小不等、形狀各 異的積木塊。又，旁邊還有一堆積木塊。如果把背包里的積木塊倒在這一堆積木塊里攪勻，那么再從中挑出一組積術塊使它們恰好裝滿背包是十分困難的。類似的數(shù)學問題可表述為 ：背包問題： 設，n是正整數(shù)，也是正整數(shù)。問是否存在使 A稱為背包矢量或背包序列。 這里A就像那一大堆積木塊，a是背包，能不能從A中挑出 恰好裝滿n是很難判斷的。用專業(yè)語言來說，這是一個NP完全問題(見本節(jié)后注1)。 不過對于某些背包矢量A，上述問題是容易解決的，這就是矢量A構成超遞增數(shù)列的情形。 5.2超遞增序列 定義1正整數(shù)序列 叫超遞增序列，如果 這一定義對有限序列也適

31、用。通俗地說，每一項都大于它前面各項之和的正整數(shù)序列叫超遞增序列。下面就是兩個超 遞增序列： ，。對于超遞增序列A而言，如果給定了一個正整數(shù)a是很容易判斷a是否能表示為A中的若 干個項之和的。比如序列A ，a=52。因為n>41，41必須被選中，否則其它各項全選也不 夠41，從而更達不到52。然后算出5241：11。因為11恰大于A中的9，9必須被選中， 否則前面各項加起來也不到9，更達不到11。同理，算出119=2正好是A中的項，這樣就 得到52=41+9+2。再如序列B，a=10000。如果a能表示為B中的若干項之和，那么 從a恰大于6907知6907是一個加項，然后算出100006

32、907=3093。3093恰大于B中的 1718，30391718=1375，1375863=512，512430=82。因為82不是B中的項，所以 a=10000不能表示為B中的若干項之和。 背包系統(tǒng)就是將超遞增序列用于秘密地傳遞數(shù)字語言的一種密碼系統(tǒng)。事實上，只要會 秘密地傳送一個字母，也就會傳送整個語言了。而由表1知一個字母可以看成一個5位的二進制數(shù)，比如i可看成01001。選取一個超遞增序列把i也想成一個矢量 并作A與 的內(nèi)積?；诔f增序列A就可以把i以數(shù)字22的形式發(fā)送給對方，對方收到數(shù)字22后，如果他 也知道這個超遞增序列A，就很容易算出(0，1，0，0，1)這個序列從而可以恢復

33、出文字來。如果敵方截獲了數(shù)字22，因為他不知道A，也就恢復不出i來。但以上所述不是真正的背包系統(tǒng)。在實用的背包系統(tǒng)中，序列A的長度 遠遠大于5，可以達到 100。同時序列A經(jīng)過用數(shù)論方法進行變換后可將所得的非超遞增序列B公諸與眾，但控制一些秘鑰僅為友方所知。5.3背包系統(tǒng)的加密和解密方法 用機器語言作加密對象，以傳送兩個英文字母為例進行說明。為了方便，不妨取i 。（字母i和空格） 加密方法 選取一個超遞增序列比如A為前文中所給出的。以 記A中各項之和，則 =55205。取整數(shù)m使，比如取m =55207。再取整 數(shù) t使且 與m互素，即1,比如取t=25236。用t乘A的各項后再 用m去除所得

34、各項，以C記所得余數(shù)依次構成的序列，即， 這里的等于t除以m所得的余數(shù)。經(jīng)計算得 這個C可以公之于眾，友方敵方都知道，但請注意C已經(jīng)不是超遞增序列了。 設為待傳送的i (i和空格)，由表1知（二進制對應）。將 與C作內(nèi)積得。這個77426就是密文，敵方截獲了也很難從B和口算出，因為C已經(jīng)不是超遞增的了，正像想從一大堆積木塊中找出恰好裝滿背包的那些積木塊一樣。當n=100時，如果不借助其它數(shù)學理論 ，用計算機去試探性地破譯背包系統(tǒng)得花上30年的時間 ! 解密方法 友方在收到信息 后是容易基于C而恢復出來的，因為t與m這兩個密鑰是 通知了友方的。利用t和m，根據(jù)公式，可以很快算出u=1061。有了

35、u “就可以從C中恢復出超遞增序列A來，用u去乘C的各項再摸去若干個m記得A。下面以C的第一項4579為例，因為所以A的第一項是103。同理可以求得A的其他各項?，F(xiàn)在我們知道了A還有t與m就可以算出非遞增序列C，然后進而求出，這些只要對加密方法進行逆運算就可以很快得到。再把機器語言，翻譯出來即可。 注1：NP完全問題，是世界七大數(shù)學難題之一。 NP的英文全稱是Non-deterministic Polynomial的問題，即多項式復雜程度的非確定性問題。簡單的寫法是 NP=P？，問題就在這個問號上，到底是NP等于P，還是NP不等于P。NP就是Non-deterministic Polynomi

36、al的問題，也即是多項式復雜程度的非確定性問題。 有些計算問題是確定性的，比如加減乘除之類，你只要按照公式推導，按部就班一步步來，就可以得到結果。但是，有些問題是無法按部就班直接地計算出來。比如，找大質數(shù)的問題。有沒有一個公式，你一套公式，就可以一步步推算出來，下一個質數(shù)應該是多少呢？這樣的公式是沒有的。再比如，大的合數(shù)分解質因數(shù)的問題，有沒有一個公式，把合數(shù)代進去，就直接可以算出，它的因子各自是多少？也沒有這樣的公式。這種問題的答案，是無法直接計算得到的，只能通過間接的“猜算”來得到結果。這就是非確定性問題。而這些問題的通常有個算法，它不能直接告訴你答案是什么，但可以告訴你，某個可能的結果是正確的答案還是錯誤的。這個可以告訴你“猜算”的答案正確與否的算法，假如可以在多項式時間內(nèi)算出來，就叫做多項式非確定性問題。而如果這個問題的所有可能答案，都是可以在多項式時間背包問題實際上是一個NP完全問題內(nèi)進行正確與否的驗算的話，就叫完全多項式非確定問題完全多項式非確定性問題可以用窮舉法得到答案，一個個檢驗下去，最終便能得到結果。但是這樣算法的復雜程度，是指數(shù)關系，因此計算的時間隨問題的復雜程度成指數(shù)的增長，很快便變得不可計算了。6結束語在著手這篇論文的時候作者一直都是力求用最簡單的文字向大家展示數(shù)論在密碼學中的兩方面應用。其中RSA算法是先擺理論后舉事