新編密碼學 課件 第1章 緒論

1.1概述

1.2保密通信的基本模型

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

數

因

子

化”的

量

子

算

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