數(shù)論在密碼學(xué)中的應(yīng)用new

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

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

3、語15主要參考資料：16致謝17數(shù)論在密碼學(xué)中的應(yīng)用摘要論文介紹了一些數(shù)論的基本知識(shí)和密碼學(xué)的主要思想。并著重從RSA算法與背包原理算法兩個(gè)方面介紹了數(shù)論在密碼學(xué)中的應(yīng)用。而且構(gòu)造了一個(gè)簡單的數(shù)學(xué)語言體系對(duì)背包原理和RSA的實(shí)例講解。本文把數(shù)論蘊(yùn)含在整個(gè)密碼學(xué)的兩種算法的闡述之中，其重點(diǎn)是現(xiàn)行的公鑰體制RSA，全面的介紹了其產(chǎn)生，運(yùn)用，安全性，發(fā)展，未來前景及局限性。關(guān)鍵詞： RSA算法，背包原理，數(shù)論，密碼學(xué)，公鑰體制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ù)學(xué)中最古老、最純粹的一個(gè)重要數(shù)學(xué)分支。素有“數(shù)學(xué)王子”之稱的19世紀(jì)德國數(shù)學(xué)大師高斯就曾說過，數(shù)學(xué)是科學(xué)的皇后，數(shù)論是數(shù)學(xué)的皇后。數(shù)論，顧名思義，是一門研究數(shù)字性質(zhì)的學(xué)問。一般所謂的數(shù)論，特指正整數(shù)(即自然數(shù))的許多性質(zhì)，例如同余、質(zhì)數(shù)、數(shù)論函數(shù)、有限域、背包原理等。密碼學(xué)是研究編制密碼和破譯密碼的技術(shù)科學(xué)。研究密碼變化的客觀規(guī)律，應(yīng)用于編制密碼以保守通信秘密的，稱為編碼學(xué)；應(yīng)用于破譯密碼以獲取通信情報(bào)的，稱為破譯學(xué)?？偡Q密碼學(xué)。密碼學(xué)，起初是應(yīng)用于軍事信息的保密上，但是隨著當(dāng)今社會(huì)計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展，尤其是電子商務(wù)的普及與深入，密碼

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

8、和數(shù)學(xué)語言的簡單對(duì)應(yīng)如表1。表1字母二進(jìn)制數(shù)十進(jìn)制數(shù)字母二進(jìn)制數(shù)十進(jìn)制數(shù)a000011o0111115b000102p1000016c000113q1000117d001004r1001018e001015s1001119f001106t1010020g001117u1010121h010008v1011022i010019w1011123j0101010x1100024k0101111y1100125l0110012z1101026m0110113空格000000n01110142數(shù)論數(shù)論就是指研究整數(shù)性質(zhì)的一門理論。整數(shù)的基本元素是素?cái)?shù)，所以數(shù)論的本質(zhì)是對(duì)素?cái)?shù)性質(zhì)的研究。2000年前，歐幾

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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