第2章-密碼學(xué)基礎(chǔ)知識(shí)

2.1密碼學(xué)的基本概念

2.2對(duì)稱密碼算法

2.3公鑰密碼算法第2章密碼學(xué)基礎(chǔ)知識(shí)2.1密碼學(xué)的基本概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

fA（x）=x19+x18+x17+x14+1B的生成多項(xiàng)式為

fB（x）=x22+x21+x17+x13+1C的生成多項(xiàng)式為

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

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

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

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

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

modn

解密過程：m=cd

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

modn驗(yàn)證過程：m=se

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

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

Ep(a,b)中

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

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