新編密碼學(xué) 課件 第1章 緒論

1.1概述

1.2保密通信的基本模型

1.3密碼學(xué)的基本概念1.1概述密碼學(xué)有著悠久而神秘的歷史,人們很難準(zhǔn)確給出密碼學(xué)的起始時間。一般認(rèn)為人類對密碼學(xué)的研究與應(yīng)用已經(jīng)有幾千年的歷史,它最早應(yīng)用在軍事和外交領(lǐng)域,隨著科技的發(fā)展逐漸進入人們的生活中。密碼學(xué)研究的是密碼編碼和破譯的技術(shù)方法。其中,通過研究密碼變化的客觀規(guī)律,并將其應(yīng)用于編制密碼,實現(xiàn)保密通信的技術(shù)稱為編碼學(xué);通過研究密碼變化的客觀規(guī)律,并將其應(yīng)用于破譯密碼,獲取通信信息的技術(shù)稱為破譯學(xué)。DavidKahn在他的被稱為“密碼學(xué)圣經(jīng)”的著作KahnonCodes:SecretsoftheNewCryptology中這樣定義密碼學(xué):Cryptology,thescienceofcommunicationsecrecy。密碼學(xué)是研究編碼密碼技術(shù)和破譯密碼技術(shù)的科學(xué),它是在編碼與破譯的斗爭實踐中逐步發(fā)展起來的。隨著先進科學(xué)技術(shù)的應(yīng)用,密碼學(xué)已成為一門綜合性的尖端技術(shù)科學(xué),發(fā)展至今已有幾千年的歷史,大致可以分為古典密碼學(xué)和現(xiàn)代密碼學(xué)兩個時期。密碼學(xué)是研究編碼密碼技術(shù)和破譯密碼技術(shù)的科學(xué),它是在編碼與破譯的斗爭實踐中逐步發(fā)展起來的。隨著先進科學(xué)技術(shù)的應(yīng)用,密碼學(xué)已成為一門綜合性的尖端技術(shù)科學(xué),發(fā)展至今已有幾千年的歷史,大致可以分為古典密碼學(xué)和現(xiàn)代密碼學(xué)兩個時期。1.古典密碼學(xué)時期(1949年之前)這一時期的密碼學(xué)更像一門藝術(shù),密碼工作者常常憑借直覺和信念進行密碼設(shè)計和分析,而不是靠推理證明。密碼算法的核心實現(xiàn)方式是代換和置換,密鑰空間較小,信息的安全性主要依賴加密算法和解密算法的保密性。從這個意義上說,古典密碼學(xué)更具有藝術(shù)性、技巧性,而非科學(xué)性。古典密碼學(xué)時期的加密技術(shù)根據(jù)實現(xiàn)方式分為手工密碼階段和機器時代密碼階段。在手工密碼階段,人們通過紙和筆對字符進行加密。Phaistos圓盤和凱撒密碼是這一階段比較有代表性的加密技術(shù)。圖11所示的Phaistos圓盤是一種直徑約為160mm的黏土圓盤,表面的字母間有明顯的間隙。該圓盤于1930年在克里特島被人們發(fā)現(xiàn),但人們無法破譯圓盤上的那些象形文字。近年有研究學(xué)者認(rèn)為它記錄著某種古代天文歷法,其真相仍是個謎,研究學(xué)者只能大致推論出它的產(chǎn)生時間(大約在公元前1700—公元前1600年之間)。這一階段還出現(xiàn)了另一種著名的加密方式———凱撒密碼。為了避免重要信息落入敵軍手中而導(dǎo)致泄密,凱撒發(fā)明了一種單字替代密碼,即把明文中的每個字母用密文中的對應(yīng)字母替代,明文字符集與密文字符集是一一對應(yīng)的關(guān)系。通過替代操作,凱撒密碼實現(xiàn)了對字符信息的加密。隨著工業(yè)革命的興起,密碼學(xué)也進入了機器時代、電子時代。與手工操作相比,電子密碼機使用了更優(yōu)秀復(fù)雜的加密手段,同時也擁有更高的加密解密效率。其中最具有代表性的就是圖12所示的ENIGMA密碼機。ENIGMA密碼機是德國科研人員在1919年發(fā)明的一種加密電子器,它表面看上去就像常用的打字機,但功能與打印機有著天壤之別。ENIGMA密碼機的鍵盤與電流驅(qū)動的轉(zhuǎn)子相連,可以多次改變每次敲擊的數(shù)字,相應(yīng)信息以摩斯密碼輸出,同時還需要密鑰,而密鑰每天都會修改。ENIGMA密碼機被證明是有史以來最可靠的加密系統(tǒng)之一,二戰(zhàn)期間它開始被德軍大量用于鐵路、企業(yè)中,使德軍保密通信技術(shù)處于領(lǐng)先地位。在古典密碼學(xué)時期,雖然加密設(shè)備有了很大的進步,但是密碼學(xué)的理論沒有很大的改變,加密的主要手段仍是代換和置換,而且實現(xiàn)信息加密的過程過于簡單,安全性能很差。伴隨著高性能計算機的出現(xiàn),古典密碼體制逐漸退出了歷史舞臺。2.現(xiàn)代密碼學(xué)時期第一階段(1949—1975)隨著通信、電子和計算機等技術(shù)的發(fā)展,密碼學(xué)得到了前所未有的系統(tǒng)發(fā)展。1949年,Shannon發(fā)表了“CommunicationTheoryofSecrecySystems”一文,將密碼學(xué)置于堅實的數(shù)學(xué)和計算機科學(xué)理論的基礎(chǔ)之上,標(biāo)志著密碼學(xué)成為一門嚴(yán)謹(jǐn)?shù)目茖W(xué)。這一階段的密碼學(xué)有別于古典密碼學(xué)的方面是:這一階段對密碼學(xué)的各個方面都有了科學(xué)的描述和刻畫;密碼方案都以單向函數(shù)的存在為前提,許多方案的存在與單向函數(shù)的存在是等價的;在研究對象的安全性、方案構(gòu)造的基礎(chǔ)假設(shè)與研究對象安全性的證明等方面,都有著嚴(yán)格精準(zhǔn)的數(shù)學(xué)描述、刻畫和證明過程。3.現(xiàn)代密碼學(xué)時期第二階段(1976—1994)1976年,Diffie和Hellman在他們的開創(chuàng)性論文“NewDirectionsinCryptography”中首次提出了公鑰密碼學(xué)的概念。他們突破了傳統(tǒng)密碼學(xué)中加密者與解密者必須共享相同密鑰的思想,首次表明在發(fā)送端和接收端無共享密鑰傳輸?shù)谋Ｃ芡ㄐ攀强赡艿?即加密密鑰和解密密鑰可以不同,加密密鑰可以公開,只需要保密解密密鑰,從公開密鑰難以推導(dǎo)出相應(yīng)的密鑰,這就形成了公開密鑰密碼學(xué),簡稱公鑰密碼學(xué)。公鑰密碼學(xué)的提出開創(chuàng)了密碼學(xué)的新紀(jì)元,使得密鑰協(xié)商、數(shù)字簽名等密碼問題有了新的解決辦法,也為密碼學(xué)的廣泛應(yīng)用奠定了基礎(chǔ)。4.現(xiàn)代密碼學(xué)時期第三階段(1994年之后)1994年,Shor提出了量子計算機模型下分解大整數(shù)和求解離散對數(shù)的多項式時間算法。從這個意義上講,如果人們能夠在實際中實現(xiàn)“Shor大

數(shù)

因

子

化”的

量

子

算

法,則RSA、ElGamal等經(jīng)典的公鑰加密體制將不再安全。因此,量子計算會對由傳統(tǒng)密碼體系保護的信息安全產(chǎn)生致命的打擊,這對現(xiàn)有保密通信提出了嚴(yán)峻挑戰(zhàn)。為了抵御量子計算的攻擊,后量子密碼學(xué)應(yīng)運而生。典型的后量子密碼算法主要包括基于格的公鑰密碼體制、基于編碼(線性糾錯碼)的公鑰密碼體制、基于多變量多項式方程組的公鑰密碼體制、基于哈希函數(shù)的數(shù)字簽名等。直到現(xiàn)在,世界各國仍然高度重視對密碼的研究,密碼學(xué)已經(jīng)成為結(jié)合物理、量子力學(xué)、電子學(xué)、語言學(xué)等多個專業(yè)的綜合科學(xué),出現(xiàn)了量子密碼、混沌密碼等先進理論。隨著計算機技術(shù)和網(wǎng)絡(luò)技術(shù)的發(fā)展、互聯(lián)網(wǎng)的普及和網(wǎng)上業(yè)務(wù)的大量開展,人們更加關(guān)注密碼學(xué),也更加依賴密碼技術(shù)。密碼技術(shù)在信息安全中扮演著十分重要的角色。1.2保密通信的基本模型保密是密碼學(xué)的核心目的。密碼學(xué)的基本目的是面對攻擊者Oscar,在被稱為Alice和Bob的通信雙方之間應(yīng)用不安全信道進行通信時保證通信安全。圖1-3給出了保密通信的基本模型。在保密通信過程中,Alice和Bob分別稱為信息的發(fā)送方和接收方,Alice要發(fā)送給Bob的信息稱為明文(Plaintext)。為了保證信息不被未經(jīng)授權(quán)的Oscar識別,Alice需要使用密鑰(Key)對明文進行加密(Encryption),加密得到的結(jié)果稱為密文(Ciphertext)。密文一般是不可理解的。Alice將密文通過不安全的信道發(fā)送給Bob,同時通過安全的通信方式將密鑰發(fā)送給Bob。Bob在接收到密文和密鑰的基礎(chǔ)上,可以對密文進行解密(Decryption),從而獲得明文。對于Oscar來說,他可能會竊聽到信道中的密文,但由于得不到加密密鑰,所以無法知道相應(yīng)的明文。1.3密碼學(xué)的基本概念在圖1-3給出的保密通信的基本模型中,根據(jù)加密和解密過程所采用密鑰的特點可以將加密算法分為兩類:對稱加密算法,又稱單鑰密碼算法;非對稱密碼算法,又稱雙鑰密碼算法。對稱加密算法也稱為傳統(tǒng)加密算法,是指解密密鑰與加密密鑰相同或者能夠從加密密鑰中直接推算出解密密鑰的加密算法。通常在大多數(shù)對稱加密算法中解密密鑰與加密密鑰是相同的,所以這類加密算法要求Alice和Bob在進行保密通信前,通過安全的方式商定一個密鑰。對稱加密算法的安全性依賴于密鑰的管理。非對稱密碼算法也稱為公鑰加密算法,是指用來解密的密鑰不同于進行加密的密鑰,也不能夠通過加密密鑰直接推算出解密密鑰。一般情況下,加密密鑰是可以公開的,任何人都可以應(yīng)用加密密鑰來對信息進行加密,但只有擁有解密密鑰的人才可以解密出被加密的信息。在以上過程中,加密密鑰稱為公鑰,解密密鑰稱為私鑰。在圖1-3所示的保密通信的基本模型中,為了在接收端能夠有效地恢復(fù)出明文信息,要求加密過程必須是可逆的?？梢?加密方法、解密方法、密鑰和消息(明文、密文)是保密通信中的幾個關(guān)鍵要素,它們構(gòu)成了相應(yīng)的密碼體制(CipherSystem)。密碼體制包括以下要素:(1)M:明文消息空間,表示所有可能的明文組成的有限集。(2)C:密文消息空間,表示所有可能的密文組成的有限集。(3)K:密鑰空間,表示所有可能的密鑰組成的有限集。(4)E:加密算法集合。(5)D:解密算法集合。該密碼體制應(yīng)該滿足的基本條件是:對任意的key∈K,存在一個加密規(guī)則ekey∈E和相應(yīng)的解密規(guī)則dkey∈D,使得對任意的明文x∈M,ekey(x)∈C且dkey(ekey(x))=x。在以上密碼體制的定義中,最關(guān)鍵的條件是加密過程具有可逆性,即密碼體制不僅能夠?qū)γ魑南應(yīng)用ekey進行加密,而且可以使用相應(yīng)的dkey對得到的密文進行解密,從而恢復(fù)出明文。顯然,密碼體制中的加密函數(shù)必須是一一映射的。我們要避免在加密時x1≠x2,而對應(yīng)的密文ekey(x1)=ekey(x2)=y的情況,這時通過解密過程無法準(zhǔn)確地確定密文y對應(yīng)的明文x。自從有了加密算法,對加密信息的破解技術(shù)應(yīng)運而生。加密的對立面稱作密碼分析,也就是研究密碼算法的破譯技術(shù)。加密和破譯構(gòu)成了一對矛盾體,密碼學(xué)的主要目的是保護通信消息的秘密以防止其被攻擊。密碼分析是指在不知道密鑰的情況下恢復(fù)出明文。根據(jù)密碼分析的Kerckhoffs原則(即攻擊者知道所用的加密算法的內(nèi)部機制,不知道的僅僅是加密算法所采用的加密密鑰),可將常用的密碼分析攻擊分為以下4類:(1)唯密文攻擊:攻擊者有一些消息的密文,這些密文都是用相同的加密算法進行加密得到的,攻擊者的任務(wù)就是恢復(fù)出盡可能多的明文,或者能夠推算出加密算法采用的密鑰,以便采用相同的密鑰解密出其他被加密的消息。(2)已知明文攻擊:攻擊者不僅可以得到一些消息的密文,而且也知道對應(yīng)的明文,攻擊者的任務(wù)就是用加密信息來推算出加密算法采用的密鑰或者導(dǎo)出一個算法。此算法可以對用同一密鑰加密的任何新的消息進行解密。(3)選擇明文攻擊:攻擊者不僅可以得到一些消息的密文和相應(yīng)的明文,還可以選擇被加密的明文,這比已知明文攻擊更為有效,因為攻擊者能夠選擇特定的明文消息進行加密,從而得到更多有關(guān)密鑰的信息,攻擊者的任務(wù)是推算出加密算法采用的密鑰或者導(dǎo)出一個算法。此算法可以對用同一密鑰加密的任何新的消息進行解密。(4)選擇密文攻擊:攻擊者能夠選擇一些不同的被加密的密文,并得到與其對應(yīng)