數(shù)字認證：第二講v2

1、數(shù)字簽名與身份認證技術 ：第二講密碼學基礎朱巖62334905，1204A計算機與通信學院軟件工程系北京科技大學主要內容密碼學概述加密系統(tǒng)的安全分析古典與對稱密碼系統(tǒng)非對稱密碼系統(tǒng)橢圓曲線ECC密碼密鑰管理密碼學傳統(tǒng)密碼學(Cryptology)：就是研究密碼編制、密碼破譯和密碼系統(tǒng)設計的的一門綜合性科學，其包括密碼編碼學(Cryptography)： 主要研究對信息進行編碼,實現(xiàn)對信息的保護。密碼分析學(Cryptanalytics)：主要研究加密消息的破譯或消息的偽造。廣義密碼學：采用數(shù)學方法實現(xiàn)信息安全的一門科學。它是包含信息論、復雜性理論、群論、代數(shù)、糾錯碼理論等等的一門綜合學科。3北

2、京大學,朱巖,2010秋密碼學中的加密技術加密系統(tǒng)模型M：明文，C：密文，K：密鑰，Ek：加密算法，Dk：解密算法攻擊的種類：中斷（Interruption)（干擾）截?。↖nterception) (偵聽）修改（Modification）偽造（Fabrication)4北京大學,朱巖,2010秋對稱密碼體制和非對稱密碼體制當加/解密函數(shù)使用相同的密鑰時，可以將它們表示為：EK(M)=C加密函數(shù)DK(C)=M解密函數(shù)對稱密碼體制具有以下特征： DK(EK(M) )=M當加/解密函數(shù)使用不同的密鑰時，可以將它們表示為：EK1(M)=C加密函數(shù)DK2(C)=M解密函數(shù)其中，M表示明文，C表示密文，

3、K1表示加密密鑰，K2表示解密密鑰，Ek表示加密算法，Dk表示解密算法非對稱密碼體制具有以下特征： DK2(EK1(M) )=M對稱密碼體制的優(yōu)缺點優(yōu)點：加密速度快，很高數(shù)據(jù)吞吐量：十兆-百兆/秒缺點：密鑰需要謹慎保管，密鑰更新和交換困難多人通信密鑰數(shù)量會出現(xiàn)爆炸性增長N(N-1)/2不易于實現(xiàn)數(shù)字簽名非對稱密碼體制的優(yōu)缺點優(yōu)點：可以適用網(wǎng)絡的開放性要求，密鑰管理相對簡單；群組通信下，N個用戶只需要N對密鑰；密鑰分配較為簡單，不需要秘密信道和復雜協(xié)議傳送密鑰；可以實現(xiàn)數(shù)字簽名；缺點：加密速度慢，實現(xiàn)較為復雜安全性建立在計算復雜性假設下，安全性相對較低古典與對稱密碼系統(tǒng)古典密碼學算法置換密碼（S

4、ubstitution Cipher）換位密碼（Transposition Cipher）置換密碼在置換密碼中，每個字母或每一組字母被另一個字母或另一組字母來取代，從而將明文中的字母掩蓋起來，也就是在密文中將明文偽裝起來。一種常用的方法是將明文字母表移動k個字母，例如k為3，即A變成D，B變成E，C變成F，Z變成C，此時k就是這種循環(huán)移動字母表的通用加密方法的密鑰。Ek(m)=m+k mod 26Dk(c)=c-k mod 26根據(jù)映像方式的不同，可分為單表置換密碼和多表置換密碼。換位密碼換位密碼又稱代換密碼，它不更改保持明文的字母，但是重新對字母進行排序，形成新的密文序列。典型的置換密碼：美

5、國南北戰(zhàn)爭時期（1861-1865年），軍隊中曾經(jīng)使用過的“柵欄”式密碼（rail fence cipher)定義變換T(1,2,3,4,5,6,7,8,9,10)(2,4,6,8,10,1,3,5,7,9)T(1)=6, T(2)=1, T(3)=7, T(4)=2, T(6)=1, T(1)=2, T(7)=3, T(2)=4, 加密：ET(m)=mT(1),mT(2), mT(3), mT(10)解密：DT(m)=cT(1),cT(2), cT(3), cT(10)對稱密碼DES密碼IDEA密碼數(shù)據(jù)加密標準DESDES（Data Encryption Standard，數(shù)據(jù)加密標準）是由

6、IBM公司研制的一種加密算法，美國國家標準局于1977年把它作為非機要部門使用的數(shù)據(jù)加密標準。近三十年來，它一直活躍在國際保密通信的舞臺上，扮演了十分重要的角色，并經(jīng)過不斷的改進，形成一套較為完整的密碼標準。DES是一個分組加密算法，它以64位為分組對數(shù)據(jù)加密。同時DES也是一個對稱算法，即加密和解密用的是同一個算法。它的密鑰長度是56位（因為每個分組第8位都用作奇偶校驗），可以是任意的56位的數(shù)，而且可以任意時候改變。雖然有極少量的數(shù)被認為是弱密鑰，但是很容易避開。DES算法DES對64位的明文分組M進行操作，M經(jīng)過一個初始轉置被分成左半部分和右半部分M=(L0, R0)，兩部分都是32位長

7、。然后使用函數(shù)f對兩部分進行16輪完全相同的迭代運算，在運算過程中將數(shù)據(jù)與密鑰相結合。經(jīng)過16輪迭代運算后，再將左、右兩部分合在一起經(jīng)過一個末置換，就產(chǎn)生了密文。3DES簡介DES的分組長度太短（僅64位）、密鑰長度更短（僅56位），可以通過窮舉（也稱野蠻攻擊）的方法在較短時間內破解。1978年初，IBM意識到DES的密鑰太短，于是設計了一種方法，利用三重加密來有效增加密鑰長度，加大解密代價，稱為3DES。3DES 是DES算法擴展其密鑰長度的一種方法，可使加密密鑰長度擴展到128位（112位有效）或192位（168位有效）。其基本原理是將128位的密鑰分為64位的兩組，對明文多次進行普通的D

8、ES加解密操作，從而增強加密強度。3DES的模式3DES有三種不同的模式DES-EEE3，使用3個不同的密鑰進行加密；DES-EDE3，使用3個不同的密鑰，對數(shù)據(jù)進行加密、解密、再加密。DES-EEE2和DES-EDE2，與前面模式相同，只是第1次和第3次使用同一個密鑰。最常用的3DES是DES-EDE2。IDEA簡介IDEA（International Data Encryption Algorithm，國際數(shù)據(jù)解密算法）是瑞士聯(lián)邦理工學院的中國學者賴學嘉中國學者賴學嘉與著名的密碼學專家James Massey等人提出的加密算法，在密碼學中屬于數(shù)據(jù)塊加密算法（Block Cipher）類。I

9、DEA使用長度為128位的密鑰，數(shù)據(jù)塊大小為64位。從理論上講，IDEA屬于強加密算法，至今還沒有出現(xiàn)對IDEA進行有效攻擊的算法。早在1990年，賴學嘉等人在EuroCrypt90年會上提出了PES（Proposed Encryption Standard，分組密碼建議）。在EuroCrypt91年會上，賴學嘉等人又提出了PES的修正版IPES（Improved PES）。目前IPES已經(jīng)商品化，并改名為IDEA。IDEA已由瑞士的Ascom公司注冊專利，以商業(yè)目的使用IDEA算法必須向該公司申請許可，因此其推廣受到限制。非對稱密碼系統(tǒng)非對稱密碼1976年，Diffie和Hellman提出非

10、對稱密碼第一個非對稱密碼：背包問題密碼使用最廣：RSARSA密碼ElGamal密碼橢圓曲線密碼RSA密碼RSA有效性RSA的安全性b1002003005007501000時間30秒3天9年1兆年2*109年6*1015年ElGamal密碼ElGamal密碼由ElGamal在1985年提出基于離散對數(shù)問題ElGamal密碼ElGamal密碼的正確性橢圓曲線ECC密碼橢圓曲線ECC密碼Elliptic Curve Cryptosystem以高效性著稱，由Neal Koblitz和Victor Miller在1985年分別提出。ECC的安全性基于橢圓曲線離散對數(shù)問題的難解性，密鑰長度大大地減小。有限

11、域上的橢圓曲線GF(p)域上的橢圓曲線是對于固定的a、b值，滿足形如方程Y2=X3+aX+b mod(p)的所有點的集合，外加一個零點或無窮遠點。其中，a、b，X和Y在GF(p)域上取值。方程分析：Y2說明是X軸對稱函數(shù)；給定c=Y2 ，那么X3+aX+b=c是3次方程，最多有3個根，即與X軸相交最多3點；X3+aX+b必須大于等于零，這意味著x0成立，但x0只有有限區(qū)間滿足。橢圓曲線與直線相交的點P1P2PP3橢圓曲線加法令無窮遠點為O （說明說明） 如果P=（x，y），那么-P=（x,-y)如果R是過P和Q的直線與E的交點，那么P+Q=-RP+Q+R=O給定橢圓曲線上任意兩點P，Q，R，我

12、們有P+Q=Q+P :交換P-P=O；P+O=P ：零點P+(Q+R)=(P+Q)+R ：結合橢圓曲線加法Abelian群具有交互律的群（Group with communicative property）群: G, G: a set of elements : 任意元素對(a,b)上的二元操作規(guī)則（obeys）:closure: ab is also in Gassociative law:(ab)c = a(bc) 結合has identity e: ea = ae = a 幺元/零元has inverses a-1: aa-1 = e 逆元Public ciphers based on

13、an abelian groupExponentiation (repeated multiplication) in RSA and D-H algorithmIdea: Find another abelian group!In elliptic curves, we define the addition operation such that it forms an abelian groupqaaaqak mod )( mod k timeshard problemaaaak k times35Abel群 ：加法規(guī)則1：零元加法規(guī)則2：逆元加法規(guī)則3：結合律加法規(guī)則4：交換律0)(m

14、od27423pbaOOOPOPOQPPQQPRQPRQP)()(橢圓曲線的加法規(guī)則（交換群）Elliptic curve y2=x3-x on finite field Z89橢圓曲線密碼橢圓曲線的離散對數(shù)問題給定橢圓曲線E和點G隨機選擇整數(shù)k,計算Q=kG給定G,Q,計算k困難的信息在橢圓曲線上點的表示在有限域E上，任何X值對應至少2個點G=(x,y)，x是隨機的，是隨機的，y是固定的是固定的信息利用率只有信息利用率只有1/2需要進行計算平方剩余需要進行計算平方剩余EC discrete log problemexample: E23(9,17) EC:P=(16,5), Q=(4,5),

15、 determine k s.t. Q=kPBrute force method: 23 mod )179(23 mod 32xxyP=(16,5); 2P=(20,20); 3P=(14,14); 4P=(19,20)5P=(13,10); 6P=(7,3); 7P=(8,7); 8P=(12,17); 9P=(4,5)橢圓曲線加密算法選擇橢圓曲線E和生成元G 保證其DL問題是安全的用戶選擇私鑰：整數(shù) nAn用戶計算公鑰：PA=nAG加密Pm : Cm=kG, Pm+kPA, k隨機整數(shù)解密Cm: (Pm+kPA)nA(kG) = Pm+k*nAGnA*kG= PmExample: ECC

16、encryptionEC curve on Zp : y2 = x3 -x + 188G = (0, 376), p = 751As public key PA = (201, 5)Plaintext Pm=(562, 201)B selects random k=386, then encryt Pm asCm=kG, Pm+kPA= 386(0,376), (562, 201)+386(201, 5)= (676, 558), (385, 328)41 橢圓曲線上的公鑰密碼體制的優(yōu)點：速度快、安全性高、密鑰短、靈活性好。橢圓曲線密碼體制（ECC）ECC密鑰長度mRSA密鑰長度MIPS-年1

17、065121041601024101221020481020600210001078120012000010168密鑰管理密鑰管理的內容現(xiàn)代密碼系統(tǒng)的安全是由密鑰安全保證的現(xiàn)代密碼系統(tǒng)的安全是由密鑰安全保證的主密鑰（主密鑰（Main Key）又稱初始密鑰（又稱初始密鑰（Primary Key)或用戶密鑰或用戶密鑰(User key)，是參與或控制密碼變換，在一段時間內不進行更換是參與或控制密碼變換，在一段時間內不進行更換的密鑰。的密鑰。會話密鑰（會話密鑰（Session Key） 在一次通話或交換數(shù)據(jù)時使用的臨時密鑰。通常與在一次通話或交換數(shù)據(jù)時使用的臨時密鑰。通常與主密鑰相結合對消息進行加密

18、，且一報一換。主密鑰相結合對消息進行加密，且一報一換?；旌厦荑€體制第一步，數(shù)據(jù)發(fā)送者A用對稱密鑰把需要發(fā)送的數(shù)據(jù)加密。第二步，A用B的公開密鑰將對稱密鑰加密，形成數(shù)字信封，然后一起把加密數(shù)據(jù)和數(shù)字信封傳給B。第三步，B收到A的加密數(shù)據(jù)和數(shù)字信封后，用自己的私鑰將數(shù)字信封解密，獲取A加密數(shù)據(jù)時的對稱密鑰。第四步B使用A加密的對稱密鑰把收到的加密數(shù)據(jù)解開。密鑰管理的主要內容密鑰管理涉及密鑰的生成、分發(fā)、存儲、更新等一系列問題密鑰分發(fā)通信一方將會話密鑰分發(fā)給另一方的過程密鑰協(xié)商通信雙方或多方共同形成會話密鑰的過程密碼分發(fā)對稱密鑰的分發(fā)對稱密鑰的分發(fā)不基于第三方的密鑰分發(fā)前提：通信雙方共享主密鑰方法：一方直接發(fā)送“加密的會話密鑰”給另一方基于第三方的密鑰分