版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第1章
緒論第2章
基礎(chǔ)知識(shí)第3章
古典密碼第4章
分組密碼第5章
中外文網(wǎng)絡(luò)數(shù)據(jù)庫(kù)檢索第6章Hash函數(shù)第7章
公鑰密碼第8章
數(shù)字簽名與身份認(rèn)證第9章
密鑰管理《新編密碼學(xué)》全套可編輯PPT課件
本課件是可編輯的正常PPT課件1.1概述
1.2保密通信的基本模型
1.3密碼學(xué)的基本概念全套可編輯PPT課件
本課件是可編輯的正常PPT課件1.1概述本課件是可編輯的正常PPT課件密碼學(xué)有著悠久而神秘的歷史,人們很難準(zhǔn)確給出密碼學(xué)的起始時(shí)間。一般認(rèn)為人類對(duì)密碼學(xué)的研究與應(yīng)用已經(jīng)有幾千年的歷史,它最早應(yīng)用在軍事和外交領(lǐng)域,隨著科技的發(fā)展逐漸進(jìn)入人們的生活中。密碼學(xué)研究的是密碼編碼和破譯的技術(shù)方法。其中,通過(guò)研究密碼變化的客觀規(guī)律,并將其應(yīng)用于編制密碼,實(shí)現(xiàn)保密通信的技術(shù)稱為編碼學(xué);通過(guò)研究密碼變化的客觀規(guī)律,并將其應(yīng)用于破譯密碼,獲取通信信息的技術(shù)稱為破譯學(xué)。DavidKahn在他的被稱為“密碼學(xué)圣經(jīng)”的著作KahnonCodes:SecretsoftheNewCryptology中這樣定義密碼學(xué):Cryptology,thescienceofcommunicationsecrecy。密碼學(xué)是研究編碼密碼技術(shù)和破譯密碼技術(shù)的科學(xué),它是在編碼與破譯的斗爭(zhēng)實(shí)踐中逐步發(fā)展起來(lái)的。隨著先進(jìn)科學(xué)技術(shù)的應(yīng)用,密碼學(xué)已成為一門綜合性的尖端技術(shù)科學(xué),發(fā)展至今已有幾千年的歷史,大致可以分為古典密碼學(xué)和現(xiàn)代密碼學(xué)兩個(gè)時(shí)期。本課件是可編輯的正常PPT課件密碼學(xué)是研究編碼密碼技術(shù)和破譯密碼技術(shù)的科學(xué),它是在編碼與破譯的斗爭(zhēng)實(shí)踐中逐步發(fā)展起來(lái)的。隨著先進(jìn)科學(xué)技術(shù)的應(yīng)用,密碼學(xué)已成為一門綜合性的尖端技術(shù)科學(xué),發(fā)展至今已有幾千年的歷史,大致可以分為古典密碼學(xué)和現(xiàn)代密碼學(xué)兩個(gè)時(shí)期。1.古典密碼學(xué)時(shí)期(1949年之前)這一時(shí)期的密碼學(xué)更像一門藝術(shù),密碼工作者常常憑借直覺(jué)和信念進(jìn)行密碼設(shè)計(jì)和分析,而不是靠推理證明。密碼算法的核心實(shí)現(xiàn)方式是代換和置換,密鑰空間較小,信息的安全性主要依賴加密算法和解密算法的保密性。從這個(gè)意義上說(shuō),古典密碼學(xué)更具有藝術(shù)性、技巧性,而非科學(xué)性。本課件是可編輯的正常PPT課件古典密碼學(xué)時(shí)期的加密技術(shù)根據(jù)實(shí)現(xiàn)方式分為手工密碼階段和機(jī)器時(shí)代密碼階段。在手工密碼階段,人們通過(guò)紙和筆對(duì)字符進(jìn)行加密。Phaistos圓盤(pán)和凱撒密碼是這一階段比較有代表性的加密技術(shù)。圖11所示的Phaistos圓盤(pán)是一種直徑約為160mm的黏土圓盤(pán),表面的字母間有明顯的間隙。該圓盤(pán)于1930年在克里特島被人們發(fā)現(xiàn),但人們無(wú)法破譯圓盤(pán)上的那些象形文字。近年有研究學(xué)者認(rèn)為它記錄著某種古代天文歷法,其真相仍是個(gè)謎,研究學(xué)者只能大致推論出它的產(chǎn)生時(shí)間(大約在公元前1700—公元前1600年之間)。本課件是可編輯的正常PPT課件這一階段還出現(xiàn)了另一種著名的加密方式———?jiǎng)P撒密碼。為了避免重要信息落入敵軍手中而導(dǎo)致泄密,凱撒發(fā)明了一種單字替代密碼,即把明文中的每個(gè)字母用密文中的對(duì)應(yīng)字母替代,明文字符集與密文字符集是一一對(duì)應(yīng)的關(guān)系。通過(guò)替代操作,凱撒密碼實(shí)現(xiàn)了對(duì)字符信息的加密。隨著工業(yè)革命的興起,密碼學(xué)也進(jìn)入了機(jī)器時(shí)代、電子時(shí)代。與手工操作相比,電子密碼機(jī)使用了更優(yōu)秀復(fù)雜的加密手段,同時(shí)也擁有更高的加密解密效率。其中最具有代表性的就是圖12所示的ENIGMA密碼機(jī)。本課件是可編輯的正常PPT課件ENIGMA密碼機(jī)是德國(guó)科研人員在1919年發(fā)明的一種加密電子器,它表面看上去就像常用的打字機(jī),但功能與打印機(jī)有著天壤之別。ENIGMA密碼機(jī)的鍵盤(pán)與電流驅(qū)動(dòng)的轉(zhuǎn)子相連,可以多次改變每次敲擊的數(shù)字,相應(yīng)信息以摩斯密碼輸出,同時(shí)還需要密鑰,而密鑰每天都會(huì)修改。ENIGMA密碼機(jī)被證明是有史以來(lái)最可靠的加密系統(tǒng)之一,二戰(zhàn)期間它開(kāi)始被德軍大量用于鐵路、企業(yè)中,使德軍保密通信技術(shù)處于領(lǐng)先地位。在古典密碼學(xué)時(shí)期,雖然加密設(shè)備有了很大的進(jìn)步,但是密碼學(xué)的理論沒(méi)有很大的改變,加密的主要手段仍是代換和置換,而且實(shí)現(xiàn)信息加密的過(guò)程過(guò)于簡(jiǎn)單,安全性能很差。伴隨著高性能計(jì)算機(jī)的出現(xiàn),古典密碼體制逐漸退出了歷史舞臺(tái)。本課件是可編輯的正常PPT課件2.現(xiàn)代密碼學(xué)時(shí)期第一階段(1949—1975)隨著通信、電子和計(jì)算機(jī)等技術(shù)的發(fā)展,密碼學(xué)得到了前所未有的系統(tǒng)發(fā)展。1949年,Shannon發(fā)表了“CommunicationTheoryofSecrecySystems”一文,將密碼學(xué)置于堅(jiān)實(shí)的數(shù)學(xué)和計(jì)算機(jī)科學(xué)理論的基礎(chǔ)之上,標(biāo)志著密碼學(xué)成為一門嚴(yán)謹(jǐn)?shù)目茖W(xué)。這一階段的密碼學(xué)有別于古典密碼學(xué)的方面是:這一階段對(duì)密碼學(xué)的各個(gè)方面都有了科學(xué)的描述和刻畫(huà);密碼方案都以單向函數(shù)的存在為前提,許多方案的存在與單向函數(shù)的存在是等價(jià)的;在研究對(duì)象的安全性、方案構(gòu)造的基礎(chǔ)假設(shè)與研究對(duì)象安全性的證明等方面,都有著嚴(yán)格精準(zhǔn)的數(shù)學(xué)描述、刻畫(huà)和證明過(guò)程。本課件是可編輯的正常PPT課件3.現(xiàn)代密碼學(xué)時(shí)期第二階段(1976—1994)1976年,Diffie和Hellman在他們的開(kāi)創(chuàng)性論文“NewDirectionsinCryptography”中首次提出了公鑰密碼學(xué)的概念。他們突破了傳統(tǒng)密碼學(xué)中加密者與解密者必須共享相同密鑰的思想,首次表明在發(fā)送端和接收端無(wú)共享密鑰傳輸?shù)谋C芡ㄐ攀强赡艿?即加密密鑰和解密密鑰可以不同,加密密鑰可以公開(kāi),只需要保密解密密鑰,從公開(kāi)密鑰難以推導(dǎo)出相應(yīng)的密鑰,這就形成了公開(kāi)密鑰密碼學(xué),簡(jiǎn)稱公鑰密碼學(xué)。公鑰密碼學(xué)的提出開(kāi)創(chuàng)了密碼學(xué)的新紀(jì)元,使得密鑰協(xié)商、數(shù)字簽名等密碼問(wèn)題有了新的解決辦法,也為密碼學(xué)的廣泛應(yīng)用奠定了基礎(chǔ)。本課件是可編輯的正常PPT課件4.現(xiàn)代密碼學(xué)時(shí)期第三階段(1994年之后)1994年,Shor提出了量子計(jì)算機(jī)模型下分解大整數(shù)和求解離散對(duì)數(shù)的多項(xiàng)式時(shí)間算法。從這個(gè)意義上講,如果人們能夠在實(shí)際中實(shí)現(xiàn)“Shor大
數(shù)
因
子
化”的
量
子
算
法,則RSA、ElGamal等經(jīng)典的公鑰加密體制將不再安全。因此,量子計(jì)算會(huì)對(duì)由傳統(tǒng)密碼體系保護(hù)的信息安全產(chǎn)生致命的打擊,這對(duì)現(xiàn)有保密通信提出了嚴(yán)峻挑戰(zhàn)。為了抵御量子計(jì)算的攻擊,后量子密碼學(xué)應(yīng)運(yùn)而生。典型的后量子密碼算法主要包括基于格的公鑰密碼體制、基于編碼(線性糾錯(cuò)碼)的公鑰密碼體制、基于多變量多項(xiàng)式方程組的公鑰密碼體制、基于哈希函數(shù)的數(shù)字簽名等。直到現(xiàn)在,世界各國(guó)仍然高度重視對(duì)密碼的研究,密碼學(xué)已經(jīng)成為結(jié)合物理、量子力學(xué)、電子學(xué)、語(yǔ)言學(xué)等多個(gè)專業(yè)的綜合科學(xué),出現(xiàn)了量子密碼、混沌密碼等先進(jìn)理論。隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的發(fā)展、互聯(lián)網(wǎng)的普及和網(wǎng)上業(yè)務(wù)的大量開(kāi)展,人們更加關(guān)注密碼學(xué),也更加依賴密碼技術(shù)。密碼技術(shù)在信息安全中扮演著十分重要的角色。本課件是可編輯的正常PPT課件1.2保密通信的基本模型本課件是可編輯的正常PPT課件保密是密碼學(xué)的核心目的。密碼學(xué)的基本目的是面對(duì)攻擊者Oscar,在被稱為Alice和Bob的通信雙方之間應(yīng)用不安全信道進(jìn)行通信時(shí)保證通信安全。圖1-3給出了保密通信的基本模型。在保密通信過(guò)程中,Alice和Bob分別稱為信息的發(fā)送方和接收方,Alice要發(fā)送給Bob的信息稱為明文(Plaintext)。為了保證信息不被未經(jīng)授權(quán)的Oscar識(shí)別,Alice需要使用密鑰(Key)對(duì)明文進(jìn)行加密(Encryption),加密得到的結(jié)果稱為密文(Ciphertext)。密文一般是不可理解的。Alice將密文通過(guò)不安全的信道發(fā)送給Bob,同時(shí)通過(guò)安全的通信方式將密鑰發(fā)送給Bob。Bob在接收到密文和密鑰的基礎(chǔ)上,可以對(duì)密文進(jìn)行解密(Decryption),從而獲得明文。對(duì)于Oscar來(lái)說(shuō),他可能會(huì)竊聽(tīng)到信道中的密文,但由于得不到加密密鑰,所以無(wú)法知道相應(yīng)的明文。本課件是可編輯的正常PPT課件1.3密碼學(xué)的基本概念本課件是可編輯的正常PPT課件在圖1-3給出的保密通信的基本模型中,根據(jù)加密和解密過(guò)程所采用密鑰的特點(diǎn)可以將加密算法分為兩類:對(duì)稱加密算法,又稱單鑰密碼算法;非對(duì)稱密碼算法,又稱雙鑰密碼算法。對(duì)稱加密算法也稱為傳統(tǒng)加密算法,是指解密密鑰與加密密鑰相同或者能夠從加密密鑰中直接推算出解密密鑰的加密算法。通常在大多數(shù)對(duì)稱加密算法中解密密鑰與加密密鑰是相同的,所以這類加密算法要求Alice和Bob在進(jìn)行保密通信前,通過(guò)安全的方式商定一個(gè)密鑰。對(duì)稱加密算法的安全性依賴于密鑰的管理。非對(duì)稱密碼算法也稱為公鑰加密算法,是指用來(lái)解密的密鑰不同于進(jìn)行加密的密鑰,也不能夠通過(guò)加密密鑰直接推算出解密密鑰。一般情況下,加密密鑰是可以公開(kāi)的,任何人都可以應(yīng)用加密密鑰來(lái)對(duì)信息進(jìn)行加密,但只有擁有解密密鑰的人才可以解密出被加密的信息。在以上過(guò)程中,加密密鑰稱為公鑰,解密密鑰稱為私鑰。本課件是可編輯的正常PPT課件在圖1-3所示的保密通信的基本模型中,為了在接收端能夠有效地恢復(fù)出明文信息,要求加密過(guò)程必須是可逆的??梢?jiàn),加密方法、解密方法、密鑰和消息(明文、密文)是保密通信中的幾個(gè)關(guān)鍵要素,它們構(gòu)成了相應(yīng)的密碼體制(CipherSystem)。密碼體制包括以下要素:(1)M:明文消息空間,表示所有可能的明文組成的有限集。(2)C:密文消息空間,表示所有可能的密文組成的有限集。(3)K:密鑰空間,表示所有可能的密鑰組成的有限集。(4)E:加密算法集合。(5)D:解密算法集合。本課件是可編輯的正常PPT課件該密碼體制應(yīng)該滿足的基本條件是:對(duì)任意的key∈K,存在一個(gè)加密規(guī)則ekey∈E和相應(yīng)的解密規(guī)則dkey∈D,使得對(duì)任意的明文x∈M,ekey(x)∈C且dkey(ekey(x))=x。在以上密碼體制的定義中,最關(guān)鍵的條件是加密過(guò)程具有可逆性,即密碼體制不僅能夠?qū)γ魑南應(yīng)用ekey進(jìn)行加密,而且可以使用相應(yīng)的dkey對(duì)得到的密文進(jìn)行解密,從而恢復(fù)出明文。顯然,密碼體制中的加密函數(shù)必須是一一映射的。我們要避免在加密時(shí)x1≠x2,而對(duì)應(yīng)的密文ekey(x1)=ekey(x2)=y的情況,這時(shí)通過(guò)解密過(guò)程無(wú)法準(zhǔn)確地確定密文y對(duì)應(yīng)的明文x。自從有了加密算法,對(duì)加密信息的破解技術(shù)應(yīng)運(yùn)而生。加密的對(duì)立面稱作密碼分析,也就是研究密碼算法的破譯技術(shù)。加密和破譯構(gòu)成了一對(duì)矛盾體,密碼學(xué)的主要目的是保護(hù)通信消息的秘密以防止其被攻擊。密碼分析是指在不知道密鑰的情況下恢復(fù)出明文。根據(jù)密碼分析的Kerckhoffs原則(即攻擊者知道所用的加密算法的內(nèi)部機(jī)制,不知道的僅僅是加密算法所采用的加密密鑰),可將常用的密碼分析攻擊分為以下4類:本課件是可編輯的正常PPT課件(1)唯密文攻擊:攻擊者有一些消息的密文,這些密文都是用相同的加密算法進(jìn)行加密得到的,攻擊者的任務(wù)就是恢復(fù)出盡可能多的明文,或者能夠推算出加密算法采用的密鑰,以便采用相同的密鑰解密出其他被加密的消息。(2)已知明文攻擊:攻擊者不僅可以得到一些消息的密文,而且也知道對(duì)應(yīng)的明文,攻擊者的任務(wù)就是用加密信息來(lái)推算出加密算法采用的密鑰或者導(dǎo)出一個(gè)算法。此算法可以對(duì)用同一密鑰加密的任何新的消息進(jìn)行解密。(3)選擇明文攻擊:攻擊者不僅可以得到一些消息的密文和相應(yīng)的明文,還可以選擇被加密的明文,這比已知明文攻擊更為有效,因?yàn)楣粽吣軌蜻x擇特定的明文消息進(jìn)行加密,從而得到更多有關(guān)密鑰的信息,攻擊者的任務(wù)是推算出加密算法采用的密鑰或者導(dǎo)出一個(gè)算法。此算法可以對(duì)用同一密鑰加密的任何新的消息進(jìn)行解密。(4)選擇密文攻擊:攻擊者能夠選擇一些不同的被加密的密文,并得到與其對(duì)應(yīng)的明文信息,攻擊者的任務(wù)是推算出加密密鑰。本課件是可編輯的正常PPT課件對(duì)于以上任何一種攻擊,攻擊者的主要目標(biāo)都是確定加密算法采用的密鑰。顯然,這4種類型攻擊的攻擊強(qiáng)度依次增大,相應(yīng)的攻擊難度則依次降低。隨著信息技術(shù)的發(fā)展和普及,對(duì)信息保密的需求將日益廣泛和深入,密碼技術(shù)的應(yīng)用也將越來(lái)越多地融入人們的日常工作、學(xué)習(xí)和生活中。鑒于密碼學(xué)有著廣闊的應(yīng)用前景和完善的理論研究基礎(chǔ),可以相信,密碼學(xué)一定能夠不斷地發(fā)展和完善,為信息安全提供堅(jiān)實(shí)的理論基礎(chǔ)和支撐,為信息技術(shù)的發(fā)展提供安全服務(wù)和技術(shù)保障。本課件是可編輯的正常PPT課件2.1數(shù)論
2.2計(jì)算復(fù)雜性問(wèn)題2.1數(shù)論在數(shù)學(xué)中,研究整數(shù)性質(zhì)的分支稱為數(shù)論。數(shù)論中的許多概念是設(shè)計(jì)公鑰密碼算法的基礎(chǔ),數(shù)論領(lǐng)域中的大整數(shù)分解、素性檢測(cè)、開(kāi)方求根、求解不同模數(shù)的同余方程組等問(wèn)題在公鑰密碼學(xué)中經(jīng)常遇到,同時(shí)它們也是數(shù)論中非常重要的內(nèi)容。2.1.1素?cái)?shù)與互素1.整除與素?cái)?shù)如果整數(shù)a,b,c之間存在關(guān)系a=b·c且b≠0,則稱b整除a或者a能被b整除,且b是a的因子或除數(shù),a是b的倍數(shù),記為b|a。整除有如下性質(zhì):性質(zhì)1a|a。性質(zhì)2如果a|1,則有a=±1。性質(zhì)3對(duì)于任何a≠0,則有a|0。性質(zhì)4如果a|b且b|a,那么a=±b。性質(zhì)5如果a|b且b|c,則有a|c。性質(zhì)6如果a|b且b|c,那么對(duì)所有的x,y∈?,有a|(bx+cy)(這里?表示整數(shù)集,下同)。根據(jù)整除的定義,這些性質(zhì)都是顯而易見(jiàn)的,在此不再證明。另外,在本書(shū)中,如不做特別說(shuō)明,所有的量均取整數(shù)。如果p>1且只能被1和自身整除,則正整數(shù)p稱為素?cái)?shù)或質(zhì)數(shù)。非素?cái)?shù)的整數(shù)稱為合數(shù)。1既不是素?cái)?shù),也不是合數(shù)。素?cái)?shù)的一些基本結(jié)論如下:結(jié)論1素?cái)?shù)有無(wú)窮多個(gè)。結(jié)論2設(shè)p是素?cái)?shù),xi(i=1,2,…,n)是整數(shù),如果,則至少存在一個(gè)xi(i∈{1,2,…,n})能被p整除。結(jié)論3(素?cái)?shù)定理)設(shè)x∈?,則不超過(guò)x的素?cái)?shù)個(gè)數(shù)可近似地用
表示。結(jié)論4(算術(shù)基本定理)設(shè)2≤n∈?,則n可分解成素?cái)?shù)冪的乘積:其中,pi(i=1,2,…,n)是互不相同的素?cái)?shù),αi(i=1,2,…,n)是正整數(shù)。如果不計(jì)因子的順序,則上述因子分解式是唯一的。2.最大公因子與互素設(shè)a,b,c∈?,如果c|a且c|b,則稱c是a與b的公因子或公約數(shù)。如果d滿足下列條件,則稱正整數(shù)d是a與b的最大公因子或最大公約數(shù)。(1)d是a與b的公因子。(2)如果c也是a與b的公因子,則c必是d的因子??梢?jiàn),a與b的最大公因子就是a與b的公因子中最大的那一個(gè),記為d=gcd(a,b)=max{c|{c|a且c|b}}。注:如果a和b全為0,則它們的公因子和最大公因子均無(wú)意義。如果a與b的最大公因子為1,即gcd(a,b)=1,則稱整數(shù)a與b互素。最大公因子有以下性質(zhì):性質(zhì)1任何不全為0的兩個(gè)整數(shù)的最大公因子存在且唯一。性質(zhì)2設(shè)整數(shù)a與b不全為0,則存在整數(shù)x和y,使得ax+by=gcd(a,b)。特別地,如果a與b互素,則存在整數(shù)x和y,使得ax+by=1。性質(zhì)3如果gcd(a,b)=d,性質(zhì)4如果gcd(a,x)=gcd(b,x)=1,那么gcd(ab,x)=1。性質(zhì)5如果c|(ab),且gcd(b,c)=1,那么c|a。以上性質(zhì)可由因子和素?cái)?shù)的定義直接證明,并且上面關(guān)于因子和互素的概念與性質(zhì)都可以推廣到多個(gè)整數(shù)的情況。2.1.2同余與模運(yùn)算1.帶余除法對(duì)于任意兩個(gè)正整數(shù)a和b,一定可以找到唯一確定的兩個(gè)整數(shù)k和r,滿足a=kb+r(0≤r<b),則k和r分別被稱為a除以b(或者b除a)的商和余數(shù),并把滿足這種規(guī)則的運(yùn)算稱為帶余除法。顯然,在帶余除法中,,其中x表示不大于x的最大整數(shù),或者稱為x的下整數(shù)。若記a除以b的余數(shù)為amodb,則帶余除法可表示成:例如,若a=17,b=5,則a=3b+2,即
,r≡17mod5≡2。對(duì)于整數(shù)a<0,也可以類似地定義帶余除法和它的余數(shù),如-17mod5≡3。2.整數(shù)同余與模運(yùn)算設(shè)a,b,n∈?且n>0,如果a和b除以n的余數(shù)相等,即amodn≡bmodn,則稱a與b模n同余,并將這種關(guān)系記為a≡bmodn,n稱為模數(shù),相應(yīng)地,amodn也可以稱為a模n的余數(shù)。例如,17≡2mod5,73≡27mod23。顯然,如果a與b模n同余,則必然有n(a-b),也可以寫(xiě)成a-b=kn或a=kn+b,其中k∈?。由帶余除法的定義可知,任何整數(shù)a除以正整數(shù)n的余數(shù)一定在集合{0,1,2,…,n-1}中,結(jié)合整數(shù)同余的概念,所有整數(shù)根據(jù)模n同余關(guān)系可以分成n個(gè)集合,每個(gè)集合中的整數(shù)模n同余,將這樣的集合稱為模n同余類或剩余類,依次記為[0]n,[1]n,[2]n,…,[n-1]n,即[x]n={y|y∈?∧y≡xmodn},x∈{0,1,2,…,n-1}。如果從每個(gè)模n同余類中取一個(gè)數(shù)為代表,形成一個(gè)集合,則此集合稱為模n的完全剩余系,用?n表示。顯然,?n的最簡(jiǎn)單表示就是集合{0,1,2,…,n-1},即?n={0,1,2,…,n-1}。綜上可知,amodn將任一整數(shù)a映射到?n={0,1,2,…,n-1}中,并且是唯一的數(shù),這個(gè)數(shù)就是a模n的余數(shù),所以可將amodn視作一種運(yùn)算,并稱其為模運(yùn)算。模運(yùn)算有如下性質(zhì)(其中n>1):性質(zhì)1如果n(a-b),則a≡bmodn。性質(zhì)2模n同余關(guān)系是整數(shù)間的一種等價(jià)關(guān)系,它具有等價(jià)關(guān)系的3個(gè)基本性質(zhì):(1)自反性
對(duì)任意整數(shù)a,有a≡amodn。(2)對(duì)稱性
如果a≡bmodn,則b≡amodn。(3)傳遞性
如果a≡bmodn且b≡cmodn,則a≡cmodn。性質(zhì)3如果a≡bmodn且c≡dmodn,則a±c≡(b±d)modn,ac≡bdmodn。性質(zhì)4模運(yùn)算具有普通運(yùn)算的代數(shù)性質(zhì),即(amodn±bmodn)modn≡(a±b)modn(amodn×bmodn)modn≡(a×b)modn(a×b)modn±(a×c)modn≡[a×(b±c)]modn性質(zhì)5(加法消去律)如果(a+b)≡(a+c)modn,則b≡cmodn。性質(zhì)6(乘法消去律)如果ab≡acmodn且gcd(a,n)=1,則b≡cmodn。性質(zhì)7如果ac≡bdmodn,c≡dmodn且gcd(c,n)=1,則a≡bmodn。2.1.3歐拉定理1.歐拉函數(shù)設(shè)n∈?且n>1,將小于n且與n互素的正整數(shù)的個(gè)數(shù)稱為n的歐拉(Euler)函數(shù),記為φ(n)。例如,φ(5)=4,φ(6)=2。歐拉函數(shù)有如下性質(zhì):性質(zhì)1如果p為素?cái)?shù),則有φ(p)=p-1。性質(zhì)2如果gcd(m,n)=1,則φ(mn)=φ(m)φ(n)。性質(zhì)3如果(其中,pi
為素?cái)?shù),αi
為正整數(shù),i=1,2,…,k)。2.歐拉定理定理2.2(歐拉定理)設(shè)a,n∈?且n>1,如果gcd(a,n)=1,那么aφ(n)≡1modn。證明
記小于n且與n互素的全體正整數(shù)構(gòu)成的集合R={x1,x2,…,xφ(n)},這個(gè)集合也稱為模n的既約剩余系,那么對(duì)于集合中任一元素aximodn(i=1,2,…,φ(n)),由于所以gcd(axi,n)=1。加之a(chǎn)ximodn<n,故aximodn∈R,進(jìn)而aRmodn?R。又因?yàn)閷?duì)于任意的xi,xj∈R且xi≠xj,都有aximodn≠axjmodn。否則,若aximodn=axjmodn,那么由于gcd(a,n)=1,根據(jù)消去律可得ximodn=xjmodn,即xi=xj,所以集合aRmodn中沒(méi)有相同的元素,因此aRmodn=R。令兩個(gè)集合的全體元素相乘,則有所以再由gcd(xi,n)=1(i=1,2,…,φ(n))和消去律可得
由歐拉定理可得如下推論:推論1若p為素?cái)?shù)且gcd(a,p)=1,則有aφ(p)=ap-1≡1modp。這個(gè)結(jié)論又稱為費(fèi)爾馬(Fermat)定理。推論2若gcd(a,n)=1,顯然有aφ(n)-1≡a-1modn,aφ(n)+1≡amodn;對(duì)于n=p為素?cái)?shù)的情況,有ap≡amodp,ap-2≡a-1modn。推論3設(shè)n=pq且p和q為素?cái)?shù),a∈?,如果gcd(a,n)=p或q,則同樣有aφ(n)+1≡amodn。根據(jù)歐拉定理,如果gcd(a,n)=1,則至少存在一個(gè)整數(shù)m滿足方程am≡1modn,例如m=φ(n)。稱滿足方程am≡1modn的最小正整數(shù)m為a模n的階。例如,若a=5,n=11,則有51≡5mod11,52≡3mod11,53≡4mod11,54≡9mod11,55≡1mod11,則5模11的階為5。如果a模n的階m=φ(n),則稱a為n的本原根或者本原元。顯然,5不是11的本原根。由本原根的定義和模運(yùn)算的性質(zhì)可知,如果a是n的本原根,那么a,a2,…,aφ(n)在模n下互不相同且都與n互素;如果n=p為素?cái)?shù),則有a,a2,…,ap-1在模p下互不相同且都與p互素,即并非所有的正整數(shù)都有本原根,且有本原根的整數(shù),其本原根也不一定唯一。只有以下形式的正整數(shù)才有本原根:其中,p為奇素?cái)?shù),α為正整數(shù)。例如,7有兩個(gè)本原根,分別是3和52.1.4幾個(gè)有用的算法1.歐幾里得算法在2.1.2節(jié)中,我們給出了模運(yùn)算下的乘法逆元概念,求模運(yùn)算下的乘法逆元是數(shù)論中常用的一種技能。由歐拉定理,我們知道,若整數(shù)a與n互素,則1≡aφ(n)modn,那么a-1≡aφ(n)-1modn,但如果n不是素?cái)?shù),則不容易求出φ(n),所以這種方法在多數(shù)情況下不適用?,F(xiàn)在求乘法逆元最有效的方法是歐幾里得算法?;镜臍W幾里得算法可以方便地求出兩個(gè)整數(shù)的最大公因子,擴(kuò)展的歐幾里得算法不僅可以求兩個(gè)整數(shù)的最大公因子,在這兩個(gè)整數(shù)互素的情況下,還可以求出其中一個(gè)數(shù)模另一個(gè)數(shù)的乘法逆元。1)基本的歐幾里得算法歐幾里得(Euclid)算法基于一個(gè)基本事實(shí):對(duì)任意兩個(gè)整數(shù)a和b(設(shè)a>b>0),有g(shù)cd(a,b)=gcd(b,amodb)。注:若其中有負(fù)整數(shù),則可以通過(guò)其絕對(duì)值來(lái)求它們的最大公因子;若其中一個(gè)為0,則最大公因子為非0的那一個(gè);若兩個(gè)都為0,則最大公因子無(wú)意義。證明
對(duì)于任意兩個(gè)整數(shù)a和b,一定存在整數(shù)k,滿足a≡(kb+a)modb設(shè)d是a與b的任一公因子,故d|a且d|b,所以d|(a-kb),即d|(amodb)。因此,d是b與amodb的公因子。同理,若d是b與amodb的公因子,則d也是a與b的公因子。所以a與b的全部公因子和b與amodb的全部公因子完全相同,因此它們的最大公因子也相同,即gcd(a,b)=gcd(b,amodb)在計(jì)算兩個(gè)整數(shù)的最大公因子時(shí),可以重復(fù)使用上面的結(jié)論,直到余數(shù)變?yōu)?,這個(gè)過(guò)程稱為輾轉(zhuǎn)相除。通過(guò)輾轉(zhuǎn)相除求最大公因子的過(guò)程可表示如下:其中,r0≡amodb,r1≡bmodr0,ri≡ri-2modri-1(i=2,3,…,n)。由于r0>r1>r2>…≥0且它們皆為整數(shù),所以上面的帶余除法在經(jīng)過(guò)有限步后余數(shù)必為0。最后,當(dāng)余數(shù)為0時(shí),有g(shù)cd(rn,0)=rn。再倒推回來(lái),可得rn=gcd(rn,0)=gcd(rn-1,rn)=gcd(rn-2,rn-1)=…=gcd(r0,r1)=gcd(b,r0)=gcd(a,b),即輾轉(zhuǎn)相除到余數(shù)為0時(shí),其前一步的余數(shù)即為要求的最大公因子。歐
幾
里
得
算
法
就
是
使
用
輾
轉(zhuǎn)
相
除
法
求
兩
個(gè)
整
數(shù)
最
大
公
因
子
的
簡(jiǎn)
化
過(guò)
程
。例
如,gcd(30,12)=gcd(12,6)=gcd(6,0)=6。歐幾里得算法描述如下(假定輸入的兩個(gè)整數(shù)a>b>0):2)擴(kuò)展的歐幾里得算法基本的歐幾里得算法不僅可以求出兩個(gè)整數(shù)a和b的最大公因子gcd(a,b),而且還可以進(jìn)一步求出方程sa+tb=gcd(a,b)的一組整數(shù)解(注意s,t不唯一)。具體方法是將歐幾里算法倒推回去,由輾轉(zhuǎn)相除過(guò)程中的倒數(shù)第二行可得即gcd(a,b)可表示成rn-2和rn-1的整系數(shù)線性組合。再由輾轉(zhuǎn)相除過(guò)程中的倒數(shù)第三行可得代入式gcd(a,b)=rn=rn-2-rn-1kn,可得即gcd(a,b)可表示成rn-3和rn-2的整系數(shù)線性組合。如此下去,最終可將gcd(a,b)表示成a和b的整系數(shù)線性組合,即如
果a與b互
素,即gcd(a,b)=1,則
有1=sa+tb,所
以sa=1modb,因
此s=a-1modb。擴(kuò)展的歐幾里得算法不僅能夠求出gcd(a,b),而且當(dāng)gcd(a,b)=1時(shí),它還能求出a-1modb。擴(kuò)展的歐幾里得算法描述如下所示。算法中,Q即為X3
除以Y3
的商,故X3-QY3
就是X3
除以Y3
的余數(shù)X3modY3。與基本的歐幾里得算法一樣,這里的X3與Y3
通過(guò)中間變量T3
輾轉(zhuǎn)相除,最終產(chǎn)生a與b的最大公因子gcd(a,b)。算法中的變量之間有如下關(guān)系:如果gcd(a,b)=1,則在最后一輪循環(huán)中Y3=1。因此,bY1+aY2=1,進(jìn)而aY2≡1modb,Y2≡a-1modb,或者bY1≡1moda,Y1≡b-1moda。2.快速指數(shù)算法在RSA等公鑰密碼算法中,經(jīng)常遇到大量的底數(shù)和指數(shù)均為大整數(shù)的模冪運(yùn)算。如果按模冪運(yùn)算的含義直接計(jì)算,一方面可能由于中間結(jié)果過(guò)大而超過(guò)計(jì)算機(jī)允許的整數(shù)取值范圍,另一方面其運(yùn)算工作量也是讓人難以忍受的。要有效解決這個(gè)問(wèn)題,可以從以下兩個(gè)方面著手:(1)利用模運(yùn)算的性質(zhì),即其中,m=u+v。(2)提高指數(shù)運(yùn)算的有效性。例如,通過(guò)計(jì)算出x,x2,x4,x8,x16,可以方便地組合出指數(shù)在1~31之間的任何一個(gè)整數(shù)次冪,并且最多只需4次乘法運(yùn)算即得出答案。一般地,求am
可以通過(guò)如下快速指數(shù)算法完成,其中a和m是正整數(shù)。將m表示成二進(jìn)制的形式即因此,有所以因此,計(jì)算am
的快速指數(shù)算法如下:上面的算法中,變量c表示指數(shù)的變化情況,其終值是m;變量d表示相對(duì)于指數(shù)c的冪的變化情況,其終值就是所求的am
。其實(shí),變量c完全可以去掉,但也可以通過(guò)c的值來(lái)判斷d是否達(dá)到最終結(jié)果am。3.素性檢測(cè)算法判定一個(gè)給定的整數(shù)是否為素?cái)?shù)的問(wèn)題被稱為素性檢測(cè)。目前,對(duì)于大整數(shù)的素性檢測(cè)問(wèn)題還沒(méi)有簡(jiǎn)單直接的通用方法,在這里介紹一個(gè)概率檢測(cè)算法。先介紹一個(gè)引理。引理2.1如果p是大于2的素?cái)?shù),則方程x2≡1modp的解只有x≡±1modp。證明
由x2≡1modp得x2-1≡0modp所以(x+1)(x-1)≡0modp因此,有p(x+1),或p(x-1),或p(x+1)且p(x-1)。事實(shí)上,p(x+1)且p(x-1)是不可能的,如果p(x+1)與p(x-1)同時(shí)成立,則存在兩個(gè)整數(shù)s,t滿足x+1=spx-1=tp兩式相減,得到2=(s-t)p對(duì)大于2的素?cái)?shù)p和整數(shù)s,t,這是不可能的。因此,只能有p|(x+1)或者p|(x-1)。由p(x+1)可得,x+1=kp,故x≡-1modp。同理,由p(x-1)可得x≡1modp。所以,如果p是大于2的素?cái)?shù),則方程x2≡1modp的解只有x≡±1modp。此引理的逆否命題為:如果方程x2≡1modp存在非±1(模p)的解,則p不是大于2的素?cái)?shù)。例如,32mod8≡1,所以8不是素?cái)?shù)。上述引理的逆否命題就是著名的Miller-Rabin素性檢測(cè)算法的基本依據(jù)之一。下面給出Miller-Rabin素性檢測(cè)算法的基本描述。此算法的兩個(gè)輸入中,n是待檢測(cè)的數(shù),a是小于n的整數(shù)。如果算法的返回值為TRUE,則n肯定不是素?cái)?shù);如果返回值為FALSE,則n有可能是素?cái)?shù)。容易看出,在for循環(huán)結(jié)束時(shí),d≡an-1modn,那么由費(fèi)爾馬定理可知,如果n為素?cái)?shù),則d為1;反之,若d≠1,則n不是素?cái)?shù),返回TRUE。由于n-1≡-1modn,結(jié)合算法中變量x和d的聯(lián)系,可知for循環(huán)體內(nèi)的if條件(d=1)and(x≠1)and(x≠n-1)意味著方程x2≡1modn有非±1(模n)的解。因此,根據(jù)前述引理易知n不是素?cái)?shù),算法返回TRUE。前述引理并不是充分必要條件,所以Miller-Rabin算法只是一種概率算法,如果該算法返回FALSE,則只能說(shuō)n有可能是素?cái)?shù)。為了用足夠大的概率確定n是素?cái)?shù),通常對(duì)s個(gè)不同的整數(shù)a重復(fù)調(diào)用Miller-Rabin算法,只要其中有一次算法返回TRUE,則可以肯定n不是素?cái)?shù);如果算法每次都返回FALSE,則以1-2-s的概率確信n就是素?cái)?shù)。因此,當(dāng)s足夠大時(shí),可以確定n就是素?cái)?shù)。2.1.5中國(guó)剩余定理1.一次同余方程給定整數(shù)a,b,n,n>0,且n不能整除a,則ax≡bmodn稱為模n的一次同余方程,其中x為變量。顯然,如果一次同余方程ax≡bmodn有解x=x',則必然存在某個(gè)整數(shù)k,使得ax'=b+kn即ax'-kn=b因此,上面的一次同余方程有解的必要條件是d|b(其中d=gcd(a,n))另一方面,假如d=gcd(a,n)且d|b,那么由同余方程理論可知,滿足一次同余方程ax≡b(modn)的x與滿足同余方程
的x在取值上相同。因?yàn)?/p>
互素,存在,故方程有解,則所以方程ax≡bmodn也有解。這說(shuō)明gcd(a,n)|b是一次同余方程ax≡bmodn有解的充分必要條件。定理2.3設(shè)整數(shù)a,b,n,n>0,且n不能整除a,令d=gcd(a,n),那么(1)如果d不能整除b,則一次同余方程ax≡bmodn無(wú)解。(2)如果d|b,則ax≡bmodn恰好存在d個(gè)模n不同余的解。證明
因?yàn)閐|b是一次同余方程ax≡bmodn有解的充分必要條件,所以(1)是顯然的。下面證明(2)。當(dāng)d|b時(shí),方程ax≡bmodn有解,設(shè)解為x0,則一定存在整數(shù)k0,使得那么對(duì)于任意整數(shù)t,構(gòu)造
則有
即axt≡bmodn,所以xt也是方程ax≡bmodn的解。由于t是任意的整數(shù),當(dāng)d|b時(shí),一次同余方程ax≡bmodn有無(wú)窮個(gè)解。但由于
在模n下只有d個(gè)不相同的剩余類,且它們分別對(duì)應(yīng)t=0,1,…,d-1,所以一次同余方程ax≡bmodn只有d個(gè)模n不同余的解。此定理不僅告訴我們一次同余方程ax≡bmodn是否有解,而且還給出有解時(shí)的解數(shù)和求解方法。(1)利用歐幾里得算法求出d=gcd(a,n),若d不能整除b,則方程無(wú)解。(2)若d|b,則同余方程
有唯一解
只要利用擴(kuò)展的歐幾里得算法求出
就能計(jì)算出這個(gè)解,并記為x0。(3)上面算出的x0
同樣也是同余方程ax≡bmodn的一個(gè)解,再令xt=x0+modn,并算出對(duì)應(yīng)t=0,1,…,d-1的值,即可得到同余方程ax≡bmodn的全部d個(gè)模n不同余的解。2.中國(guó)剩余定理我們解決了一次同余方程的求解問(wèn)題,如果進(jìn)一步將若干個(gè)一次同余方程組成同余方程組,又該如何求解呢?這個(gè)問(wèn)題是數(shù)論中的基本問(wèn)題之一,我國(guó)古代數(shù)學(xué)家孫子給出了這個(gè)問(wèn)題的答案,現(xiàn)在國(guó)際上一般稱這個(gè)問(wèn)題為中國(guó)剩余定理,國(guó)內(nèi)稱為孫子定理。這個(gè)定理告訴我們,如果知道某個(gè)整數(shù)關(guān)于一些兩兩互素的模數(shù)的余數(shù),則可以重構(gòu)這個(gè)數(shù)。例如,如果已知x關(guān)于5和7的余數(shù)分別是2和3,即xmod5≡2且xmod7≡3,則在?35范圍內(nèi),x的唯一取值是17。同樣,?35中的每個(gè)數(shù)都可以用關(guān)于5和7的兩個(gè)余數(shù)來(lái)重構(gòu)。定理2.4(中國(guó)剩余定理)設(shè)n1,n2,…,nk是兩兩互素的正整數(shù),那么對(duì)任意的整數(shù)a1,a2,…,ak,一次同余方程組x≡aimodni(i=1,2,…,k)在同余意義下必有唯一解,且這個(gè)解是其中,即Ni-1
是Ni關(guān)于模數(shù)ni的逆(i=1,2,…,k)。證明
先證此同余方程組在同余意義下不會(huì)有多個(gè)解。若此同余方程組有兩個(gè)解c1
和c2,那么對(duì)所有ni(i=1,2,…,k)都有c1≡c2≡aimodni,故c1-c2≡0modni,ni|(c1-c2)。又因?yàn)樗械膎i(i=1,2,…,k)兩兩互素,所以N|(c1-c2),即c1≡c2modN。因此,此同余方程組在同余意義下不可能有多個(gè)解。再證
就是此同余方程組的解。由于n1,n2,…,nk
兩兩互素,所以ni
與Ni
必然互素,因此Ni
關(guān)于模數(shù)ni
的逆Ni-1
存在。另一方面,NjNj-1≡1modnj,且若j≠i,則nj|Ni。因此所以N是此同余方程組的解。綜上,滿足定理?xiàng)l件的同余方程組有唯一解現(xiàn)在來(lái)看我國(guó)古代《孫子算經(jīng)》上的一個(gè)問(wèn)題:“今有物,不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二,問(wèn)物幾何?”這個(gè)問(wèn)題實(shí)際上就是求同余方程組的正整數(shù)解。書(shū)中給出滿足這一問(wèn)題的最小正整數(shù)解是x=23,所用的解法就是中國(guó)剩余定理。因此,國(guó)際上所說(shuō)的中國(guó)剩余定理也稱為孫子剩余定理或?qū)O子定理。實(shí)際上,所有模N=3×5×7=105同余23的正整數(shù)都是上面問(wèn)題的解。2.1.6模為素?cái)?shù)的二次剩余二次剩余是數(shù)論中一個(gè)非常重要的概念,許多數(shù)論問(wèn)題都要用到二次剩余理論,這一小節(jié)我們來(lái)了解一下模為素?cái)?shù)的二次剩余。對(duì)于一般形式的二次同余方程ax2+bx+c≡0modp通過(guò)同解變形和變量代換,可化為這里y≡(2ax+b)modp,d≡(b2-4ac)modp,p為素?cái)?shù),a是與p互素的整數(shù)。當(dāng)p|d時(shí),二次同余方程(21)僅有解y≡0modp,所以下面一直假定p與d互素。另外,如果素?cái)?shù)p=2,則僅可取d≡1mod2,這時(shí)方程(21)僅有解y≡1modp,故以下定義恒假定p為大于2的素?cái)?shù),即奇素?cái)?shù)。設(shè)p是奇素?cái)?shù),d是與p互素的整數(shù),如果方程x2≡dmodp有解,則稱d是模p的二次剩余或平方剩余,否則稱d是模p的二次非剩余。定理2.5(Euler準(zhǔn)則)設(shè)p是奇素?cái)?shù),d是與p互素的整數(shù),那么d是模p二次剩余的充要條件是d(p-1)/2≡1modpd是模p非二次剩余的充要條件是d(p-1)/2≡-1modp證明
先證對(duì)于任何與p互素的d,d(p-1)/2≡1modp與d(p-1)/2≡-1modp有且僅有一式成立。由于d與p互素,由歐拉定理或費(fèi)爾馬定理可知d(p-1)≡1modp因此,有即由于p是奇素?cái)?shù),即p>2,且所以有且僅有一式成立,即
有且僅有一式成立,所以
有且僅有一式成立。下面證明d是模p的二次剩余的充要條件是同余式
成立。先證必要性。若d是模p的二次剩余,則必定存在x0,使得因而有由于d與p互素,所以x0
也與p互素,由歐拉定理可知所以必要性得證。
再證充分性。設(shè)成立,那么d與p必定互素??疾橐淮瓮喾匠塘頺取遍?n={1,2,…,p-1}中的每一個(gè)整數(shù),則有k與p互素,且對(duì)每一個(gè)k上面的同余方程存在唯一的解x∈?n。如果d不是模p的二次剩余,則每一個(gè)k與對(duì)應(yīng)的解x不相等。這樣,?n
中的p-1個(gè)數(shù)可以按k與x配對(duì),且兩兩配完,共(p-1)/2對(duì)。因此有
由數(shù)論中的結(jié)論
得這個(gè)結(jié)果與前提
條
件
矛
盾,所
以
假
設(shè)d不
是
模p的
二
次
剩
余
是
錯(cuò)
誤
的,即
如果那么d必是模p的二次剩余。充分性得證。由上面兩部分的證明,可以推出Euler準(zhǔn)則的剩余部分。由Euler準(zhǔn)則容易得出下面兩個(gè)推論。推論1-1是模p的二次剩余,當(dāng)且僅當(dāng)p≡1mod4,這里p是奇素?cái)?shù)。推論2設(shè)p是奇素?cái)?shù),d1,d2
均與p互素,那么(1)若d1,d2均為模p的二次剩余,則d1,d2也是模p的二次剩余。(2)若d1,d2均為模p的非二次剩余,則d1,d2
是模p的二次剩余。(3)若d1
是模p的二次剩余,d2
是模p的非二次剩余,則d1,d2
是模p的非二次剩余。Euler準(zhǔn)則告訴我們?nèi)绾闻卸ㄒ粋€(gè)整數(shù)d是否模p的二次剩余(p是奇素?cái)?shù)),但對(duì)于一個(gè)模p的二次剩余d,如何求出d的兩個(gè)平方根?求解這個(gè)問(wèn)題沒(méi)有簡(jiǎn)練的方法,這里我們給出一類特殊模數(shù)的平方根的求法。
定理2.6若p≡3mod4,d是模p的二次剩余,那么d模p的兩個(gè)平方根是證明
由于d是模p的二次剩余,由歐拉準(zhǔn)則可知所以,有因此
是d模p的兩個(gè)平方根。2.1.7?p
上的離散對(duì)數(shù)
設(shè)計(jì)公鑰密碼算法的關(guān)鍵是尋找一個(gè)符合密碼學(xué)要求的陷門單向函數(shù),構(gòu)造這樣的陷門單向函數(shù)的思路主要有兩種:一種思路是以RSA算法為代表的一類算法所使用的以大整數(shù)分解為基礎(chǔ)的構(gòu)造方法,另一種思路是利用離散對(duì)數(shù)來(lái)構(gòu)造陷門單向函數(shù)。那么什么是離散對(duì)數(shù)呢?這里我們介紹一種最簡(jiǎn)單的離散對(duì)數(shù),即建立在?p上的離散對(duì)數(shù)。認(rèn)識(shí)離散對(duì)數(shù)要從模指數(shù)運(yùn)算開(kāi)始,模指數(shù)函數(shù)為其中,a,x,y和p都是正整數(shù),且在密碼學(xué)里總是要求p為素?cái)?shù)。顯然,在模指數(shù)函數(shù)中,如果已知a,x和p,則很容易計(jì)算出函數(shù)值y?,F(xiàn)在反過(guò)來(lái)看問(wèn)題,如果已知y,a和p,能否求出x呢?或者說(shuō),能否找到x,使之滿足ax≡ymodp。這實(shí)際上就是模指數(shù)函數(shù)的反函數(shù),也就是我們所說(shuō)的離散對(duì)數(shù),并且可將其表示成
由于這里要求a,x,y和p都是正整數(shù),因此不是所有的離散對(duì)數(shù)都有解。例如,很容易驗(yàn)證方程3x≡7mod13無(wú)解。也就是說(shuō)離散對(duì)數(shù)y≡log73mod13是無(wú)解的(在整數(shù)范圍內(nèi))?,F(xiàn)在,在?p
上考查模指數(shù)函數(shù)y≡axmodp,令y=1,則可得一個(gè)模指數(shù)方程ax≡1modp由歐拉定理可知,如果a∈?p,則有a與p互素,那么上面的模指數(shù)方程至少有一個(gè)解(比如x=φ(p))。在數(shù)論中將滿足上述方程的最小正整數(shù)x稱為a模p的階。a模p的階一定是φ(p)的因子。這是因?yàn)?假如a模p的階(記為m)不是φ(p)的因子,則φ(p)可表示成φ(p)=km+r(其中0<r<m)那么即這與m是a模p的階矛盾。如果a模p的階等于φ(p),則稱a是p的本原根。由于φ(p)=p-1,所以當(dāng)a是p的本原根時(shí),有a1,a2,…,ap-1在同余意義下互不相同,且都與p互素。也就是說(shuō),當(dāng)x∈?p*={1,2,…,p-1}時(shí),模指數(shù)函數(shù)y≡axmodp是?p*
到?p*的一一映射。下面給出離散對(duì)數(shù)的嚴(yán)格定義。
設(shè)p是素?cái)?shù),正整數(shù)a是p的本原根,那么對(duì)?y∈{1,2,…,p-1},必定存在唯一的x∈{1,2,…,p-1},使得y=axmodp。此時(shí)稱x為模p下以a為底y的離散對(duì)數(shù),記為x≡logaymodp,但習(xí)慣上仍然寫(xiě)成y≡logaxmodp。離散對(duì)數(shù)有如下性質(zhì):性質(zhì)1loga1≡0modp。性質(zhì)2logaa≡1modp。性質(zhì)3logaxymodp≡(logaxmodp+logaymodp)modφ(p)。上述性質(zhì)1和性質(zhì)2可以由關(guān)系式a0≡1modp,a1≡amodp直接得出。性質(zhì)3的證明需要用到如下引理。引理2.2設(shè)a與p為互素的正整數(shù),如果am≡anmodp,則有m≡nmodφ(p)。因?yàn)閍與p互素,所以a存在模p的逆元a-1。同余
式am≡anmodp兩
邊
同
乘(a-1)n,得到又由歐拉定理知所以一定存在整數(shù)k,使得即現(xiàn)在證明性質(zhì)3。證明
由離散對(duì)數(shù)的定義可知:所以由模運(yùn)算的性質(zhì)可得根據(jù)前面的引理,有性質(zhì)3:前面已經(jīng)提到,如果已知a,x和p,那么使用快速指數(shù)算法可以很容易地計(jì)算出函數(shù)y≡axmodp,但如果已知a,y和p,能不能輕易地計(jì)算出離散對(duì)數(shù)x≡logaymodp呢?現(xiàn)
在
的
回
答
是
很
困
難,目
前
已
知
的
求
離
散
對(duì)
數(shù)
問(wèn)
題
的
最
好
算
法
的
時(shí)
間
復(fù)
雜
度
為
因此,當(dāng)p很大時(shí),計(jì)算離散對(duì)數(shù)在時(shí)間上是不可行的,也正是這個(gè)原因使離散對(duì)數(shù)可以用于設(shè)計(jì)單向陷門函數(shù)。2.2計(jì)算復(fù)雜性問(wèn)題OdedGoldreich在他的著作FoundationsofCryptography:BasicTools提到了定義“安全”的兩種途徑:基于信息論的經(jīng)典方法和基于計(jì)算復(fù)雜性的現(xiàn)代方法。利用信息論考查安全,主要手段是度量密文中包含明文的信息量;而采用計(jì)算復(fù)雜性討論安全,則是給出破解密文的難度,即是否能有效獲取明文的完整信息。某些問(wèn)題,如公鑰加密體制,是不能用傳統(tǒng)的信息論方法來(lái)研究的。隨著計(jì)算復(fù)雜性和密碼學(xué)研究的相互融合,計(jì)算復(fù)雜性方法成為研究密碼學(xué)所必須掌握的工具。本章簡(jiǎn)要介紹確定型圖靈機(jī)、非確定型圖靈機(jī)、概率圖靈機(jī)這3個(gè)基本計(jì)算模型,在此基礎(chǔ)上討論非確定性多項(xiàng)式時(shí)間完全問(wèn)題和加密體制是否安全之間的關(guān)系,以及多項(xiàng)式時(shí)間不可區(qū)分性。2.2.1確定性多項(xiàng)式時(shí)間1.算法效率分析
算法(Algorithm)就是在有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義明確的規(guī)則。前面已經(jīng)介紹了幾種算法,但未對(duì)其做詳細(xì)的效率分析。本節(jié)主要給出衡量算法效率的方法,它是后續(xù)幾節(jié)的基礎(chǔ)。一般而言,分析某算法的效率存在如下兩個(gè)指標(biāo):(1)時(shí)間復(fù)雜度(TimeComplexity):該算法完全運(yùn)行所需運(yùn)算時(shí)間的多少。(2)空間復(fù)雜度(SpaceComplexity):該算法完全運(yùn)行所需存儲(chǔ)空間的大小。
在理論和實(shí)際中,由于使用者更關(guān)心問(wèn)題解決的快慢,所以時(shí)間復(fù)雜度更為重要。隨著技術(shù)的發(fā)展,存儲(chǔ)設(shè)備的價(jià)格不斷下降,對(duì)空間復(fù)雜度的關(guān)注越來(lái)越少。衡量時(shí)間復(fù)雜度最精確也最原始的辦法是在某臺(tái)計(jì)算機(jī)上執(zhí)行算法,經(jīng)過(guò)測(cè)量后得到關(guān)于它的評(píng)價(jià)。但這種時(shí)間復(fù)雜度的測(cè)試與具體機(jī)器有關(guān),不同的計(jì)算機(jī)有不同的性能和結(jié)構(gòu),測(cè)量值自然不同。即便在同一臺(tái)計(jì)算機(jī)上,算法的每次執(zhí)行時(shí)間也會(huì)有一些偏差。為此,對(duì)時(shí)間復(fù)雜度的漸進(jìn)分析是必要的。插入排序效率分析如下://這段程序?qū)nt型數(shù)組a進(jìn)行插入排序,數(shù)組長(zhǎng)度為n
顯然,每一次循環(huán)的程序步數(shù)最少是4,最多是2i+4。整個(gè)程序在最好情況下需要執(zhí)行4n次,在最壞情況下需要執(zhí)行
次。計(jì)算出其上下界可了解該算法的執(zhí)行時(shí)間。
假定該算法執(zhí)行5次插入操作,并且假設(shè)這5次操作的實(shí)際程序步數(shù)分別為4,4,6,10,8,那么該操作序列的實(shí)際程序步數(shù)為4+4+6+10+8=32。該指標(biāo)和上下界有一定的差距,而復(fù)雜的算法,其時(shí)間復(fù)雜度變化可能相當(dāng)大。為描述由于輸入數(shù)據(jù)而導(dǎo)致的時(shí)間復(fù)雜度差異,可用平均時(shí)間復(fù)雜度描述,即設(shè)算法執(zhí)行i步出現(xiàn)的概率為pi,則平均時(shí)間復(fù)雜度為
與此對(duì)應(yīng),漸近時(shí)間復(fù)雜度存在最好情況、最壞情況和平均情況3種度量指標(biāo)。最壞情況下的時(shí)間復(fù)雜度漸進(jìn)分析由Hopcroft和Tarjan最先提出,其目的是給算法分析一個(gè)不依賴具體硬件的定量方法。假定f(n)、g(n)均為非負(fù)函數(shù),定義域均為?。問(wèn)題的輸入規(guī)模為n,為描述漸進(jìn)復(fù)雜度中的階,定義如下漸進(jìn)記號(hào)(AsymptoticNotation):O:當(dāng)且僅當(dāng)?c,n0,?n(n≥n0→f(n)≤c×g(n)),稱f(n)=O(g(n))。Ω:當(dāng)且僅當(dāng)?c,n0,?n(n≥n0→f(n)≥c×g(n)),稱f(n)=Ω(g(n))。Θ:當(dāng)且僅當(dāng)f(n)=O(g(n))與f(n)=Ω(g(n)),稱f(n)=Θ(g(n))。我們通常分析的是時(shí)間的漸進(jìn)復(fù)雜度,需要估計(jì)出t(n)=O(tasymptotic(n))。O記號(hào)經(jīng)常被采用(PaulBachmann于1894年引入),因?yàn)樗赋隽怂惴〞r(shí)間的上界,也較好估算。更為精確的Θ記號(hào)大多時(shí)候較難計(jì)算,較少采用。此外,O記號(hào)僅表示函數(shù)的上界,它不意味著最壞情況,各種情況下均有此記號(hào)。
一般而言,各種階的增長(zhǎng)速度不同,輸入規(guī)模增大時(shí),增長(zhǎng)速度慢的階可認(rèn)為是快速算法。常用的階按照增長(zhǎng)速度遞增排序?yàn)镺(c)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2n)<O(n!)<O(nn)
其中,O(c)一般寫(xiě)為O(1),它是理論上的最佳算法;O(n)稱為線性算法,它是實(shí)際中常見(jiàn)的最好算法;而O(nn)是最差算法,相當(dāng)于窮舉搜索。
多項(xiàng)式算法是有效算法,即時(shí)間復(fù)雜度為O(nk)(k∈?)的算法是有效算法。2.問(wèn)題的難度
對(duì)于某個(gè)問(wèn)題而言,需要對(duì)其難度進(jìn)行描述。一個(gè)自然的想法是:該問(wèn)題若存在有效算法,則認(rèn)為它是較簡(jiǎn)單的問(wèn)題,反之則認(rèn)為它是較困難的問(wèn)題。1)排序問(wèn)題的難度
元素的
排
序
問(wèn)
題
可
用
堆
排
序(HeapSort)解
決,最
壞
情
況
下
的
時(shí)
間
復(fù)
雜
度
為O(nlogn)。注意到O(nlogn)也是O(n2),可知堆排序算法是有效算法,進(jìn)而可認(rèn)為排序問(wèn)題是較簡(jiǎn)單的問(wèn)題。事實(shí)上,基于比較方法的排序算法時(shí)間下界是Ω(nlogn),堆排序也是解決排序問(wèn)題的最好算法之一。
為引入更一般的定義,下面介紹圖靈機(jī)(TuringMachine,TM)的概念,引入它的主要目的是形式化給出“計(jì)算”(Computation)的模型。當(dāng)然,計(jì)算模型不只TM一種,λ演算、遞歸函數(shù)等都是計(jì)算模型,它們相互等價(jià)。計(jì)算理論領(lǐng)域?qū)Υ擞幸粋€(gè)被普遍接受的論題,即著名的Church-Turing論題。TheChurch-TuringThesis(丘奇-圖靈論題)在直觀上可計(jì)算的函數(shù)類就是TM(以及任意與TM等價(jià)的計(jì)算模型)可計(jì)算的函數(shù)類。
討論計(jì)算模型時(shí),首先對(duì)計(jì)算進(jìn)行抽象。A.M.Turing仔細(xì)研究了人類計(jì)算的過(guò)程,他把人類的計(jì)算抽象成計(jì)算者、筆、紙3個(gè)基本要素。Turing認(rèn)為只要存在這3個(gè)要素,即可模擬計(jì)算的全過(guò)程。假定存在某個(gè)旁觀者,他不認(rèn)識(shí)計(jì)算者所采用的符號(hào),以他所看到的過(guò)程作為模擬,旁觀者認(rèn)為計(jì)算者一直在進(jìn)行兩種類型的操作:在紙上書(shū)寫(xiě)某些符號(hào)和把筆移動(dòng)到紙上某位置。計(jì)算者采用的符號(hào)類型是有限的,他每次書(shū)寫(xiě)的符號(hào)可由紙上現(xiàn)有符號(hào)和他自身的狀態(tài)決定。事實(shí)上,旁觀者觀察到的過(guò)程即是抽象化的計(jì)算過(guò)程。為方便以后的討論,Turing進(jìn)一步把紙簡(jiǎn)化成一條無(wú)限長(zhǎng)的紙帶,該紙帶由無(wú)限方格組成。計(jì)算者每次只能移動(dòng)紙帶或者改變某方格內(nèi)的符號(hào),并且他每一時(shí)刻只能處于某一特定狀態(tài),狀態(tài)的變化就是計(jì)算者行為的抽象。
上面給出的
這
種
簡(jiǎn)
單
的TM是
確
定
性
的,即
確
定
型
圖
靈
機(jī)(DeterministicTuringMachine,DTM)。DTM在給定輸入數(shù)據(jù)后,其后它每一步的動(dòng)作都可完全確定。每一時(shí)刻的DTM可用格局(Configuration)來(lái)描述,它包括紙帶的內(nèi)容、讀寫(xiě)頭的位置和控制器的狀態(tài)。一臺(tái)DTM由如下要素組成,如圖2-1所示。(1)符號(hào)表Σ:由有限個(gè)符號(hào)組成,包括標(biāo)識(shí)空白的特殊字符*。(2)可雙向移動(dòng)的無(wú)限長(zhǎng)紙帶:由無(wú)限個(gè)方格組成,方格上的符號(hào)均屬于Σ,除了有限個(gè)方格外,其他方格上的符號(hào)均為*。(3)讀寫(xiě)頭:可在任一時(shí)刻對(duì)某個(gè)確定的方格進(jìn)行操作。此讀寫(xiě)頭可向左(←)或向右(→)移動(dòng)。(4)控制器:攜帶狀態(tài)集Γ,包括特定的起始狀態(tài)γ0和停機(jī)狀態(tài)集?。DTM的計(jì)算可由轉(zhuǎn)移函數(shù)(TransitionFunction)決定:δ:?!力病!力病羬←,→}
若控制器當(dāng)前狀態(tài)為γn
且讀寫(xiě)頭指向方格內(nèi)容為σn,轉(zhuǎn)移函數(shù)δ(γn,σn)可完成如下工作:(1)若γn∈?,則計(jì)算停止(也稱停機(jī)),否則確定控制器的下一步狀態(tài)γn+1。(2)修改讀寫(xiě)頭指向方格內(nèi)容,將其改為σn+1。(3)確定讀寫(xiě)頭移動(dòng)的方向,要么向左(←),要么向右(→)。
確定型圖靈機(jī)模型易于理解:輸入固定的程序和數(shù)據(jù)(此處隱含了馮·諾依曼結(jié)構(gòu)中不區(qū)分程序和數(shù)據(jù)的思想),然后DTM按照輸入完全確定性地運(yùn)行。不過(guò)DTM的構(gòu)造相當(dāng)復(fù)雜,在實(shí)際
中
往
往
采
用
更
接
近
現(xiàn)
實(shí)
計(jì)
算
機(jī)
的
模
型,如RASP、RAM等,它
們
均
與DTM等效,此處不再贅述。
一般而言,DTM如果停機(jī),運(yùn)行結(jié)果只能是兩種:接受或不接受。于是停機(jī)狀態(tài)集?
可劃分為接受狀態(tài)集?Y={γT}與不接受狀態(tài)集?N={γF}。接受格局(AcceptingConfiguration)意味著DTM停機(jī)時(shí),控制器狀態(tài)屬于?Y,DTM不接受該輸入就是控制器狀態(tài)屬于?N。于是DTM可等價(jià)于一臺(tái)能回答問(wèn)題的機(jī)器,接受輸入數(shù)據(jù)計(jì)算后僅可回答Yes或No。至于DTM是否停機(jī)屬于可計(jì)算性(Computability)領(lǐng)域所研究的問(wèn)題,可參閱相關(guān)書(shū)籍。
表面上,DTM只能以停機(jī)來(lái)表示接受輸入的程序和數(shù)據(jù),它是如何和日常使用的計(jì)算機(jī)等價(jià)呢?這需要引入判定問(wèn)題(DecisionProblem)。判定問(wèn)題就是指問(wèn)題的答案僅有Yes或No。最優(yōu)化問(wèn)題均可轉(zhuǎn)化為對(duì)應(yīng)的判定問(wèn)題,若該問(wèn)題存在有效算法,當(dāng)且僅當(dāng)其對(duì)應(yīng)的判定問(wèn)題存在有效算法。2)最短路徑問(wèn)題的判定問(wèn)題
最短路徑問(wèn)題的判定問(wèn)題僅考慮路徑長(zhǎng)度均為非負(fù)整數(shù)的情況。定義判定問(wèn)題為“是否存在長(zhǎng)度小于等于L的路徑?”容易計(jì)算出路徑長(zhǎng)度的上界M,于是可對(duì)L從0開(kāi)始遞增到M,給出一系列判定問(wèn)題。解決每個(gè)判定問(wèn)題,直到找到某個(gè)回答為Yes的L,該值即為所求最短路徑。利用此判定問(wèn)題可解決最短路徑問(wèn)題。
對(duì)于一般的問(wèn)題,可先將該問(wèn)題轉(zhuǎn)換成判定問(wèn)題,然后利用DTM回答的答案解決。密碼學(xué)中大量涉及的是離散優(yōu)化問(wèn)題,它們均可以轉(zhuǎn)換成相應(yīng)的判定問(wèn)題,本章中的問(wèn)題大部分為判定問(wèn)題。一個(gè)粗略的結(jié)
論
是:DTM的
計(jì)
算
能
力
與
日
常
使
用
的
計(jì)
算
機(jī)
等
效。DTM的輸入成為語(yǔ)言,了解DTM的定義后,可給出較簡(jiǎn)單的問(wèn)題的定義,即P的確定型的圖靈機(jī)上的具有有效算法的判定的集合。
DTM是有效算法的模型表示,即任何確定性有效算法均可由DTM實(shí)現(xiàn),且可以在多項(xiàng)式時(shí)間內(nèi)運(yùn)行,這就是多項(xiàng)式時(shí)間Church-Turing論題(thePolynomial-TimeChurch-TuringThesis)。
通過(guò)對(duì)DTM的討論,可知DTM代表了計(jì)算的能力,于是問(wèn)題的難度即可定義為:某問(wèn)題存在有效算法則稱之為易解的(Tractable);如果不存在多項(xiàng)式算法則稱之為難解的(Intractable)。該定義等價(jià)于:L是易解的,當(dāng)且僅當(dāng)L∈P。這就是著名的Cook-Karp論題。2.2.2非確定性多項(xiàng)式時(shí)間
如果所有的問(wèn)題都存在有效算法,那么密碼就沒(méi)有存在的價(jià)值,因?yàn)槠谱g密碼可以通過(guò)有效算法輕易解決。事實(shí)上,大多數(shù)問(wèn)題目前還未發(fā)現(xiàn)有效算法。這些未解決的問(wèn)題中有一個(gè)巨大的問(wèn)題子集,它們擁有共同的特點(diǎn),即對(duì)于這些問(wèn)題的正確答案能在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證。一個(gè)最簡(jiǎn)單的例子就是判定某數(shù)是否合數(shù),如果有人聲稱找到了其約數(shù),就可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證。計(jì)算機(jī)科學(xué)和密碼學(xué)中可找到許多類似的問(wèn)題,它們的集合稱為NP。
當(dāng)然也有大量問(wèn)題是超出NP的。輸出全排列就是一個(gè)超出NP的典型例子,該問(wèn)題屬于P-Space(PolynomialSpace)。
容易驗(yàn)證P是NP的子集,但P是否NP的真子集呢?此問(wèn)題被稱為P=NP?問(wèn)題,它是計(jì)算復(fù)雜性領(lǐng)域,甚至整個(gè)計(jì)算機(jī)科學(xué)理論的焦點(diǎn)問(wèn)題。(注意:了解P的定義后,常有人認(rèn)
為NP是Non-Polynomial的
縮
寫(xiě)。事
實(shí)
上,這
里
的“N”是“非
確
定
性”(Non-Deteministic)的縮寫(xiě)。如果NP是Non-Polynomial,有關(guān)P=NP?的討論也將不復(fù)存在。)可滿足性問(wèn)題(BooleanSatisfiability)為:給定某布爾表達(dá)式,是否存在某一組對(duì)其變量的真假賦值,使得該布爾表達(dá)式為真。此問(wèn)題可在多項(xiàng)式內(nèi)驗(yàn)證,所以它是NP問(wèn)題。例如,S=((p1∨p2)∧p3),需判斷p1,p2,p3
在何種賦值下,可使S為真。當(dāng)p1,p2,p3
在1,0,1情況下,可知S為真
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 幼兒園園長(zhǎng)個(gè)人工作計(jì)劃
- 中學(xué)生自我評(píng)價(jià)15篇
- 愛(ài)崗敬業(yè)演講稿范文集錦6篇
- 大一新生自我鑒定15篇
- 學(xué)期班務(wù)工作計(jì)劃
- 初中生新學(xué)期開(kāi)學(xué)典禮演講稿合集6篇
- 大學(xué)課前三分鐘演講稿(合集15篇)
- 《廣告經(jīng)典案例》課件
- 幼兒園大班老師的綜合教育筆記合集6篇
- 金錢的詩(shī)句李白
- 漂亮的可編輯顏色魚(yú)骨圖PPT模板
- 氧、氬、二氧化碳?xì)怏w充裝企業(yè)風(fēng)險(xiǎn)點(diǎn)分級(jí)管控資料
- 噎食風(fēng)險(xiǎn)評(píng)估和預(yù)防措施
- 幼兒繪本故事:小福變成大漢堡
- 常寶精特能源概況
- 政治經(jīng)濟(jì)學(xué)結(jié)構(gòu)圖解
- 國(guó)家開(kāi)放大學(xué)電大專科《獸醫(yī)基礎(chǔ)》2023-2024期末試題及答案試卷編號(hào):2776
- 示教機(jī)械手控制系統(tǒng)設(shè)計(jì)
- 氧化鋁生產(chǎn)工藝教學(xué)(拜耳法)
- 選礦學(xué)基礎(chǔ)PPT課件
- 安利食品經(jīng)銷商合同協(xié)議范本模板
評(píng)論
0/150
提交評(píng)論