第2章-密碼學基礎知識

2.1密碼學的基本概念

2.2對稱密碼算法

2.3公鑰密碼算法第2章密碼學基礎知識2.1密碼學的基本概念

密碼學是一個非常龐大而復雜的信息處理系統(tǒng)，涉及信息的機密性、完整性、認證性、不可否認性等許多方面。密碼學中加密和解密信息的主要目的是使得授權人員以外的人無法讀取信息。

被加密的消息稱為明文，明文經(jīng)過加密變換成為另一種形式，稱為密文。對明文進行加密操作時所采用的一組規(guī)則稱為加密算法，對密文進行解密操作時所采用的一組規(guī)則稱為解密算法。加密算法和解密算法都依賴于一組秘密參數(shù)，分別稱為加密密鑰和解密密鑰。加密算法和解密算法統(tǒng)稱為密碼算法。

2.1.1保密通信模型2.1.2密碼算法分類2.1.3古典密碼簡介2.1.4密碼算法的安全性2.1密碼學的基本概念2.1.1保密通信模型

在不安全的信道上實現(xiàn)安全的通信是密碼學研究的基本問題。消息發(fā)送者對需要傳送的消息進行數(shù)學變換處理，然后可以在不安全的信道上進行傳輸，接收者在接收端通過相應的數(shù)學變換處理可以得到信息的正確內(nèi)容，而信道上的消息截獲者，雖然可能截獲到數(shù)學變換后的消息，但無法得到消息本身。圖2-1展示了一個最基本的保密通信模型。2.1.2密碼算法分類密碼算法是否能進行可逆的加密變換對明文信息的處理方式不同按照密鑰的使用策略的不同單向函數(shù)密碼算法雙向函數(shù)密碼算法序列密碼算法分組密碼算法對稱密碼算法非對稱密碼算法2.1.3古典密碼簡介密碼學的發(fā)展歷史大致分為三個階段：古典密碼時期、近代密碼時期和現(xiàn)代密碼時期。古典密碼歷史悠久，主要分為替換密碼和換位密碼兩種。替換密碼，即明文中每一個字符被替換成密文中的另外一個字符。換位密碼也稱為置換密碼，即明文的字母保持不變，但打亂其順序。我們將舉例介紹兩種典型的古典密碼：凱撒密碼置換密碼2.1.3古典密碼簡介凱撒密碼基本思想是：通過把字母移動一定的位數(shù)來實現(xiàn)加密和解密比如，Alice要將明文“mobileinternetsecurity”加密成密文，傳送給Bob。為了運算方便，先把字母進行數(shù)字化。圖2-2展示了字母與數(shù)字的映射關系。2.1.3古典密碼簡介加密過程如下：Alice先將明文“mobileinternetsecurity”中的字母根據(jù)圖2-2的映射關系轉(zhuǎn)換為數(shù)字：（12，14，1，8，11，4，8，13，19，4，17，13，4，19，18，4，2，20，17，8，19，24）。加密之前，雙方需要協(xié)商一個密鑰。于是Alice與Bob商定加密方式為明文字母后移6位，即加密密鑰及解密密鑰同為K=6。開始加密：將明文字母映射得到的數(shù)字代入加密函數(shù)E(m)=m+6（mod26）中計算得到：（18，20，7，14，17，10，14，19，25，10，23，19，10，25，24，10，8，0，23，14，25，4），然后把這些數(shù)字根據(jù)圖2-2的映射關系替換成字母即可得到密文“s，u，h，o，r，k，o，t，z，k，x，t，k，z，y，k，i，a，x，o，z，e”。這就是加密后的結果。2.1.3古典密碼簡介解密過程如下：解密其實就是上述加密過程的逆過程：Bob收到密文“suhorkotzkxtkzykiaxoze”，然后將密文按照圖2-2的映射關系轉(zhuǎn)換為：（18，20，7，14，17，10，14，19，25，10，23，19，10，25，24，10，8，0，23，14，25，4）。使用解密函數(shù)D(c)=c-6（mod26）將密文轉(zhuǎn)換后的數(shù)字代入計算，得到（12，14，1，8，11，4，8，13，19，4，17，13，4，19，18，4，2，20，17，8，19，24），即可還原出明文“mobileinternetsecurity”。2.1.3古典密碼簡介2.置換密碼置換密碼是通過簡單的換位來達成加密比如，Alice想用置換密碼來加密與Bob傳遞信息，事先約定密鑰為一串字母“KEYWORD”。如圖2-3所示，把A到Z中前面的字母用KEYWORD替換，后面又補充了A到Z（去掉了KEYWORD中重復的字母）。這樣就形成了加解密的字母置換表，實際中A到Z可以置換成任意的字母。這個字母置換的過程其實就是加密。相應地，解密過程的字母置換表就如圖2-4所示，將A替換成H，B替換成I，依此類推即可實現(xiàn)解密。2.1.4密碼算法的安全性對于所有的密碼算法，安全性都是其最重要的評價標準。這里所說的“安全性”，是指該密碼系統(tǒng)對于破譯攻擊的抵抗力強度。目前評價密碼算法安全性的方法有兩種：無條件安全和有條件安全，無條件安全又稱為理論上安全，有條件安全又稱為實際安全性。很多密碼算法的安全性并沒有在理論上得到嚴格證明，只是在算法思想得到實現(xiàn)之后，經(jīng)過眾多密碼專家多年來的攻擊都沒有發(fā)現(xiàn)其弱點，沒有找到破譯它的有效方法，從而認為它在實際上是安全的。2.1.4密碼算法的安全性密碼算法還有一種安全稱為“計算上是安全的”，即指破解此密碼系統(tǒng)是可行的，但是使用已知的算法和現(xiàn)有的計算工具不可能完成攻擊所需的計算量。計算安全性是將密碼算法的安全性問題與公認的數(shù)學難題掛鉤，例如，密鑰求解問題和某個NP問題。在實際場景中考慮密碼算法安全性時，還需考慮破解一個密碼系統(tǒng)所花費的成本不能超過被加密信息本身的價值，且破譯的時間不能超過被加密信息的有效生命周期。

2.2.1分組密碼2.2.2序列密碼2.2.3密碼的工作模式2.2對稱密碼算法2.2.1分組密碼

分組密碼（BlockCipher），也稱塊密碼，是將明文消息編碼表示后的數(shù)字序列劃分成固定大小的分組，然后在密鑰的控制下對各組分別進行加密變換，從而獲得等長的二進制序列的一類算法。在現(xiàn)代分組密碼中，兩個最重要的思想就是擴散和混亂。擴散，是指要將算法設計成明文中每一比特的變化盡可能多地影響到密文輸出序列的變化，以便隱藏明文的統(tǒng)計特性，我們可以形象地將其描述為“雪崩效應”。混亂，是指在加解密變換過程中明文、密鑰以及密文之間的關系要盡可能地復雜化，以防密碼破譯者通過建立并求解一些方程來進行破譯。2.2.1分組密碼分組密碼的加密過程如下：①將明文分成m個明文組M1，M2，…，Mi，…，Mm。②對每個明文分組分別作相同的加密變換，從而生成m個密文組C1，C2，…，Ci，…，Cm。在上圖所示的加密過程中，分組密碼以32位為一個分組對明文進行劃分，明文單詞“this”經(jīng)過加密變換后得到密文“}kc{”。這些加密算法是對整個明文進行操作的，即除了其中的文字以外，還包括空格、標點符號和特殊字符等。2.2.1分組密碼分組密碼的解密過程和加密過程類似，進行的操作和變換也只是對應于加密過程的逆變換。首先將收到的密文分成m個密文分組C1，C2，…，Ci，…，Cm，在相同的密鑰作用下，對每個分組執(zhí)行一個加密的逆變換，解密得到對應的明文分組M1，M2，…，Mi，…，Mm。2.2.1分組密碼典型的分組密碼算法：DES算法AES算法IDEA算法有興趣的讀者可翻閱相關密碼學書籍查看分組密碼的詳細設計2.2.2序列密碼

序列密碼又稱為流密碼，它的起源可以追溯到20世紀20年代的Vernam密碼，是對稱密碼算法的一種。

序列密碼將明文消息字符串在密鑰流的控制下逐位進行加密和解密，所以具有加解密速度快、實現(xiàn)簡單、便于硬件實施、沒有或只有有限的錯誤傳播的特點。

因此，在實際應用中，特別是在專用或機密機構中，序列密碼保持著一定的優(yōu)勢。序列密碼典型的應用領域包括無線通信、外交通信。2.2.2序列密碼序列密碼一般包含以下幾個組成部分：明文序列mi、密鑰序列ki、用于控制密鑰序列產(chǎn)生器的種子密鑰K密文序列ci。在序列密碼中，加解密運算是簡單的模2加運算，其安全性強度主要取決于密鑰序列的隨機性。序列密碼的加解密過程如圖2-6所示。2.2.2序列密碼在圖2-6中，KG是密鑰流生成器，它主要分為兩部分：驅(qū)動部分:驅(qū)動部分一般使用線性反饋移位寄存器（LinearFeedbackShiftRegister，LFSR），用于產(chǎn)生控制生成器的狀態(tài)序列，并控制生成器的周期和統(tǒng)計特性。組合部分:組合部分主要負責對驅(qū)動部分的各個輸出序列進行非線性組合。2.2.2序列密碼移位寄存器用來存儲數(shù)據(jù)，當受到脈沖驅(qū)動時，移位寄存器中所有位右移一位，最右邊移出的位是輸出位，最左端的一位由反饋函數(shù)的輸出來填充，此過程稱為進動一拍。反饋函數(shù)f(a1,…,an)是n元(a1,…,an)的布爾函數(shù)。如圖2-7所示，移位寄存器根據(jù)需要不斷地進動m拍，便有m位的輸出，形成輸出序列o1

o2…om。2.2.2序列密碼圖2-8是一個n級線性反饋移位寄存器的模型，移位寄存器中存儲器的個數(shù)稱為移位寄存器的級數(shù)，移位寄存器存儲的數(shù)據(jù)是寄存器的狀態(tài)，狀態(tài)的順序從左到右依次為從最高位到最低位。在所有狀態(tài)中，叫初態(tài)，并且從左到右依次稱為第一級、第二級、…、第n級，也稱為抽頭1、抽頭2、抽頭3、….、抽頭n。n級線性反饋移位寄存器主要是用來產(chǎn)生周期大、統(tǒng)計性能好的序列，可以產(chǎn)生2n-1個有效狀態(tài).2.2.2序列密碼

非線性組合部分主要是增加密鑰流的復雜程度，使密鑰流能夠抵抗各種攻擊。以線性反饋移位寄存器產(chǎn)生的序列為基序列，經(jīng)過不規(guī)則采樣、函數(shù)變換等操作（即非線性變換），就可以得到安全又實用的密鑰流。

不規(guī)則采樣是在控制序列作用下，對被采樣序列進行采樣輸出，得到的序列稱為輸出序列?？刂菩蛄械目刂品绞接戌娍胤绞胶统槿》绞降?，函數(shù)變換有前饋變換和有記憶變換等。

2.2.2序列密碼下面簡單介紹兩種具有代表性的序列模型。

鐘控模型圖2-9展示了一種鐘控發(fā)生器的模型。當LFSR-1輸出1時，時鐘信號被采樣，即能通過“與門”，并驅(qū)動LFSR-2進動一拍；當LFSR-1輸出0時，時鐘信號不被采樣，即不能通過“與門”，此時LFSR-2不進動，重復輸出前一位。

2.2.2序列密碼前饋模型Geffe發(fā)生器是前饋序列的一種典型模型，如圖2-10所示，其前饋函數(shù)g(x)=(x1x2)⊕(x2x3)為非線性函數(shù)，即當LFSR-2輸出1時，g(x)的輸出位是LFSR-1的輸出位；當LFSR-2輸出0時，g(x)的輸出位是LFSR-3的輸出位。

2.2.2序列密碼序列密碼通常分為兩類:同步序列密碼:若密鑰序列的產(chǎn)生獨立于明文消息和密文消息，這樣的序列密碼稱為同步序列密碼。自同步序列密碼:若密鑰序列的產(chǎn)生是密鑰及固定大小的以往密文位的函數(shù)，這樣的序列密碼稱為自同步序列密碼或非同步序列密碼.2.2.2序列密碼同步序列密碼:如圖2-11所示，ki表示密鑰流，ci

表示密文流，mi表示明文流。在同步序列密碼中，密鑰流的產(chǎn)生完全獨立于消息流(明文流或密文流)。在這種工作方式下，如果傳輸過程中丟失一個密文字符，發(fā)送方和接收方就必須使他們的密鑰生成器重新進行同步，這樣才能正確地加/解密后續(xù)的序列，否則加/解密將失敗。2.2.2序列密碼自同步序列密碼:如圖2-12所示，自同步流密碼的每一個密鑰字符是由前面n個密文字符參與運算推導出來的，其中n為定值。如果在傳輸過程中丟失或更改了一個字符，那么這一錯誤就要向前傳播n個字符。因此，自同步流密碼會出現(xiàn)錯誤傳播現(xiàn)象。不過，在收到n個正確的密文字符之后，密碼自身會實現(xiàn)重新同步。2.2.2序列密碼A5算法是GSM系統(tǒng)中主要使用的序列密碼加密算法，用于加密移動終端與基站之間傳輸?shù)男畔?。該算法可以描述為?2bit長的參數(shù)（幀號碼，F(xiàn)n）和64bit長的參數(shù)（會話密鑰，Kc）生成兩個114bit長的序列（密鑰流）的黑盒子。這樣設計的原因是GSM會話每幀含228bit，通過與A5算法產(chǎn)生的228bit密鑰流進行異或來達到保密。典型的序列密碼算法:A5算法2.2.2序列密碼A5算法是一種典型的基于線性反饋移位寄存器的序列密碼算法，構成A5加密器主體的LFSR有三個，組成了一個集互控和停走于一體的鐘控模型。其主體部分由三個長度不同的線性移位寄存器（A,B,C）組成，其中A有19位，B有22位，C有23位，它們的移位方式都是由低位移向高位。每次移位后，最低位就要補充一位，補充的值由寄存器中的某些抽頭位進行異或運算的結果來決定，比如：運算的結果為“1”，則補充“1”，否則補充“0”。在三個LFSR中，A的抽頭系數(shù)為：18，17，16，13；B的抽頭系數(shù)為：21，20，16，12；C的抽頭系數(shù)為：22，21，18，17。三個LFSR輸出的異或值作為A5算法的輸出值。A5加密器的主體部分如圖2-13所示。典型的序列密碼算法:A5算法2.2.2序列密碼2.2.2序列密碼在圖2-13中，A的生成多項式為

fA（x）=x19+x18+x17+x14+1B的生成多項式為

fB（x）=x22+x21+x17+x13+1C的生成多項式為

fC（x）=x23+x22+x19+x18+1三個線性反饋移存器的生成多項式均為本原多項式。這三個加密器的移位是由時鐘控制的，且遵循“服從多數(shù)”的原則，即從每個寄存器中取出一個中間位（圖2-13中的x,y,z，位置分別為A,B,C的第9，11，11位）并進行判斷，若在取出的三個中間位中至少有兩個為“1”，則為“1”的寄存器進行一次移位，而為“0”的不進行移位。反之，若三個中間位中至少有兩個為“0”，則為“0”的寄存器進行一次移位，而為“1”的不進行移位。顯然，這種機制保證了每次至少有兩個LFSR被驅(qū)動移位。2.2.3密碼的工作模式分組密碼算法每次加密的明文數(shù)據(jù)的大小是固定的。通常明文的長度會超過分組密碼的分組長度，此時就需要對分組密碼算法進行迭代，迭代的方法就稱為分組密碼的工作模式。常用的分組密碼的工作模式有五種：電子密碼本模式密文分組鏈接模式密文反饋模式輸出反饋模式計數(shù)器模式2.2.3密碼的工作模式電子密碼本模式（ElectronicCodeMode，ECB）在該模式下，每個分組獨立進行加解密運算，一次處理一組明文塊，每次使用相同的密鑰進行加密，不同分組間沒有任何關聯(lián)。而且這種方式不必按次序進行，可以先加密中間的分組，然后是尾部分組，最后再加密最開始的分組。2.2.3密碼的工作模式密文分組鏈接模式（CipherBlockChaining，CBC）初始向量為IV，密鑰為K。第一個明文分組被加密后，其結果被存儲在反饋寄存器中，在下一明文分組進行加密之前，它將與保存在反饋寄存器中的前一個分組的密文進行異或并作為下一次加密的輸入。同樣地，加密后的結果仍然保存在反饋寄存器中，直到最后一個分組加密后直接輸出。由此可見，每一分組的加密都依賴于所有前面的分組。在解密時，每個密文組分別進行解密，再與上一分組進行異或就可以恢復出明文。2.2.3密碼的工作模式密文反饋模式（CipherFeedbackBlock，CFB）若設分組長度為n位，初始向量為IV（n位），密鑰為K，則j比特位的CFB模式下（j在1~n之間），加密過程如下：設一個n位長的隊列，隊列初始值為IV，并把明文消息分成M個j位的比特塊；依次對每個j位比特塊明文Pj進行以下操作：用密鑰K加密隊列，把該密文最左端的j位與j位比特塊明文Pj進行異或，即可獲得其j位比特塊的密文Cj；然后把該j位比特塊密文Cj放入隊列的最右端，并丟棄隊列最左端的j位；最后把全部j位比特塊密文C1…CM依次連起來，即可得到消息密文C。2.2.3密碼的工作模式輸出反饋模式（OutputFeedback，OFB）通過將明文分組和密碼算法的輸出進行異或來產(chǎn)生密文分組，但OFB是將前一個j比特輸出分組送入隊列最右邊位置。解密是加密的一個逆過程。在OFB模式的加解密過程中，分組算法都以加密模式使用。由于反饋機制獨立于明文和密文，這種方法有時也被稱為“內(nèi)部反饋”。2.2.3密碼的工作模式計數(shù)器模式（CounterMode，CTR）采用與明文分組相同的長度來加密不同的明文組。在該模式中，分組密碼沒有直接被用來加密明文，而是用于加密計數(shù)器的輸出。計數(shù)器首先被初始化為一個值，然后隨著消息塊的增加，計數(shù)器的值會依次遞增1，計數(shù)器加1后與明文分組進行異或得到密文分組。

2.3.1公鑰密碼基本概念2.3.2RSA密碼算法2.3.3橢圓曲線密碼算法2.3.4NTRU公鑰密碼2.3公鑰密碼算法2.3.1公鑰密碼基本概念

對稱密碼算法在密鑰分配方面面臨著管理和分發(fā)的困難，而且對稱加密算法無法實現(xiàn)抗抵賴的要求，公鑰密碼算法的出現(xiàn)解決了這一難題。1976年，Diffie和Hellman首次提出了公開密鑰加密算法，在密碼學的發(fā)展史上具有里程碑式的意義。

常見的公鑰密碼算法有：RSA、ElGamal公鑰密碼算法、橢圓曲線公鑰密鑰算法（ECC）、NTRU公鑰加密算法和Rabin公鑰加密算法等。2.3.1公鑰密碼基本概念

公鑰密碼算法解決了密鑰的管理和分發(fā)問題，每個用戶都可以公開自己的公鑰，并由用戶自己保存私鑰，不被他人獲取。A加密：X->Y：Y=E(PuB(X))A用B的公鑰PuB對明文X進行加密得到YB解密：Y->X：X=D(PrB(Y))B用自己的私鑰PrB對密文Y進行解密獲得X上式中，X表示明文，Y表示加密后的密文，E表示加密，D表示解密。PuB是B的公鑰，該密鑰是公開的，A使用此密鑰加密數(shù)據(jù)傳給B；PrB是B的私鑰，由B保存且不能被外人所知，B使用此密鑰解密A用PuB加密過的數(shù)據(jù)。PuB和PrB是相互關聯(lián)的，而且是成對出現(xiàn)的。2.3.2RSA密碼算法RSA密碼算法的安全性是基于大數(shù)分解的困難性。RSA算法的密鑰產(chǎn)生和加解密過程如下所述。其中，m表示明文，c和s表示密文。密鑰的產(chǎn)生過程如下：獨立選取兩個大素數(shù)p和q（各100~200位十進制數(shù)字，根據(jù)需要的密鑰長度進行選擇）；計算n=p*q，其歐拉函數(shù)值φ(n)=(p-1)(q-1)；隨機選取一個整數(shù)e，滿足1≤e＜φ(n)，并使最大公約數(shù)gcd(φ(n),e)=1；在模φ(n)下，計算e的逆：d=e-1mod(p-1)(q-1)；以n，e為公鑰，d為私鑰（p，q不再需要，可以銷毀）。2.3.2RSA密碼算法RSA算法用于加密和解密：加密過程：c=me

modn

解密過程：m=cd

modnRSA算法用于數(shù)字簽名和驗證：簽名過程：s=md

modn驗證過程：m=se

modn2.3.3橢圓曲線密碼算法假設發(fā)送方為A，接收方為B，A需要將消息加密后傳送給B。那么，首先需要考慮如何用橢圓曲線來生成用戶B的公私密鑰對，可以分為以下三步：

構造橢圓群設E：y2=x3+ax+b（modp）是GF(p)上的一個橢圓曲線（p>3），首先構造一個群Ep(a,b)。挑選生成元挑選Ep(a,b)中的一個生成元點G=(x0,y0)，G應滿足使nG=O成立的最小的n是一個大素數(shù)。選擇公私密鑰選擇整數(shù)kB（k<n）作為私鑰，然后產(chǎn)生其公鑰PB=kBG，則B的公鑰為（E，n，G，PB），私鑰為kB。2.3.3橢圓曲線密碼算法下面介紹如何利用公私密鑰對進行加解密的運算（以下的運算都是在modp下進行的）。1.加密過程（1）發(fā)送方A將明文消息編碼成一個數(shù)m<p，并在橢圓群

Ep(a,b)中

選擇一點Pt=（xt，yt）；（2）發(fā)送方A計算密文：C=mxt+yt；（3）發(fā)送方A選取一個保密的隨機數(shù)r(0<r<n)，并計算rG；（4）依據(jù)接收方B的公鑰PB，計算Pt+rPB；（5）發(fā)送方A對m進行加密，得到數(shù)據(jù)Cm={rG，Pt+rPB，C}。2.解密過程接收方B在收到A發(fā)來的加密數(shù)Cm={rG，Pt+rPB，C}之后，進行如下操作：（1）使用自己的私鑰kB計算：Pt+rPB-kB(rG)=Pt+r(kBG)-kB(rG)=Pt（2）接收方B計算：m=(C-yt)/xt，得到明文m。2.3.4NTRU公鑰密碼NTRU是1995年由J.Hoffstein,J.Pipher和J.Silverman發(fā)明的一種密碼算法。在數(shù)學上，NTRU比RSA或ElGamal密碼還要復雜。由于它的復雜性和出現(xiàn)的時間相對較短，國內(nèi)外密碼學界針對NTRU的安全性研究仍在繼續(xù)。2.3.4NTRU公鑰密碼NTRU密碼算法的工作過程如下：密鑰生成

在NTRU公鑰密碼算法中，接收方需要生成一組公/私密鑰對。具體步驟如下：①選擇公開參數(shù)。選擇正整數(shù)參數(shù)N，p，q，其中p，q不必為素數(shù)，但是它們必須互素，且滿足gcd(N,pq)=1。②選擇多項式f(x)和g(x)。由接收方選擇兩個小系數(shù)多項式f和g，其中模q的隨機多項式的系數(shù)一般隨機地分布在區(qū)間[0,q]上，而所謂的小系數(shù)多項式的系數(shù)相對于模q的隨機多項式要小得多。接收方需要對多項式f(x)和g(x)保密，因為任何一個多項式信息泄露都可能導致密文被破解。2.3.4NTRU公鑰密碼③計算逆元Fp(x)和Fq(x)。接收方計算多項式f(x)在模p和模q時的逆元Fp(x)和Fq(x)，即Fp(x)*f(x)=1(modp,modxN-1)和Fq(x)*f(x)=1(modq,modxN-1)。如果f(x)的逆元不存在，接收方需要重新選取f(x)。④計算公鑰。計算h(x)=F