密碼學(xué)基礎(chǔ)與應(yīng)用

1、第四講密碼學(xué)基礎(chǔ)與應(yīng)用(2) 內(nèi)容提要3.1 密碼學(xué)的基本概念3.2 對稱密鑰密碼算法3.3 非對稱密鑰密碼算法3.4 單向散列函數(shù)3.5 密鑰管理和公鑰基礎(chǔ)設(shè)施(PKI)3.6 OpenSSL簡介內(nèi)容提要3.1 密碼學(xué)的基本概念3.2 對稱密鑰密碼算法3.3 非對稱密鑰密碼算法3.3.1 非對稱密碼算法原理3.3.2 RSA算法概要3.3.3 Diffie-Hellman 密鑰交換算法3.3.4 其他非對稱密碼算法簡介3.4 單向散列函數(shù)3.5 密鑰管理和公鑰基礎(chǔ)設(shè)施(PKI)3.6 OpenSSL簡介3.3.1 非對稱密碼算法原理對稱密鑰密碼系統(tǒng)的缺陷密鑰必須經(jīng)過安全的信道分配無法用于數(shù)字

2、簽名密鑰管理復(fù)雜 O(n2)非對稱密鑰密碼，也稱公開密鑰密碼，由Diffie, Hellman 1976年提出使用兩個密鑰，對于密鑰分配、數(shù)字簽名、認證等有深遠影響基于數(shù)學(xué)函數(shù)而不是代替和換位，密碼學(xué)歷史上唯一的一次真正的革命公鑰密碼系統(tǒng)的加密原理每個通信實體有一對密鑰（公鑰，私鑰）。公鑰公開，用于加密和驗證簽名，私鑰保密，用作解密和簽名A向B 發(fā)送消息，用B的公鑰加密B收到密文后，用自己的私鑰解密PlainText加密算法解密算法ABcipherPlainTextB的私鑰C的公鑰B的公鑰任何人向B發(fā)送信息都可以使用同一個密鑰(B的公鑰)加密沒有其他人可以得到B 的私鑰，所以只有B可以解密公鑰

3、密碼系統(tǒng)的簽名原理A向B 發(fā)送消息，用A的私鑰加密（簽名）B收到密文后，用A的公鑰解密（驗證）PlainText加密算法解密算法cipherPlainTextABA的私鑰A的公鑰公鑰密碼算法的表示對稱密鑰密碼密鑰：會話密鑰（Ks）加密函數(shù)：C= EKsP對密文C，解密函數(shù)：DKsC，公開密鑰(KUa，KRa)加密/簽名：C= EKUbP，EKRaP解密/驗證：P= DKRbC，DKUaC數(shù)字簽名和加密同時使用X加密（簽名）加密解密解密（驗證）XYZYZ= EKUb Y = EKUb EKRa (X) X= DKUaY = DKUa DKRb (Z) AB產(chǎn)生密鑰對產(chǎn)生密鑰對KRaKUaKRbK

4、Ub對公開密鑰密碼算法的要求1.參與方B容易產(chǎn)生密鑰對（KUb, KRb）2.已知KUb，A的加密操作是容易的： C=EKUb(P)3.已知KRb，B解密操作是容易的: P=DKRb (C) =DKRb ( EKUb (P) )4. 已知KUb，求KRb是計算上不可行的；5. 已知KUb和C, 欲恢復(fù)P是計算上不可行的。公鑰密碼系統(tǒng)的應(yīng)用三種用途：加密/解密：數(shù)字簽名：發(fā)送方用自己的私鑰簽署報文，接收方用對方的公鑰驗證對方的簽名。密鑰交換：雙方協(xié)商會話密鑰算法加密/解密數(shù)字簽名密鑰交換RSAYYYDiffie-HellmanNNYDSANYN對公鑰密碼算法的誤解公開密鑰算法比對稱密鑰密碼算法更

5、安全？任何一種算法都依賴于密鑰長度、破譯密碼的工作量，從抗分析角度，沒有一方更優(yōu)越公開密鑰算法使對稱密鑰成為過時了的技術(shù)？公開密鑰很慢，只能用在密鑰管理和數(shù)字簽名，對稱密鑰密碼算法將長期存在使用公開密鑰加密，密鑰分配變得非常簡單？事實上的密鑰分配既不簡單，也不有效3.3.2 RSA算法簡介Ron Rivest, Adi Shamir , Leonard AdlemanRSA的安全性基于大數(shù)分解的難度RSA在美國申請了專利（已經(jīng)過期），在其他國家沒有RSA已經(jīng)成了事實上的工業(yè)標準，在美國除外 數(shù)論基礎(chǔ)a與b的最大公因數(shù)：gcd (a, b)gcd(20, 24)=4 , gcd (15, 16)

6、=1如果gcd(a, b)=1 ，稱a與b 互素模運算 moda= q n +r 0rn ; q=a/n ; x 表示小于或等于x的最大整數(shù)a=a/nn + (a mod n) , r = m mod n 如果 (a mod n )= (b mod n) ，則稱a 與b 模n同余，記為 a b mod n 例如， 23 8 mod 5 , 8 1 mod 7數(shù)論基礎(chǔ)（續(xù)）模運算是可交換的、可結(jié)合的、可分配的(a+b) mod n = (a mod n ) + (b mod n) ) mod n(a-b) mod n = ( (a mod n) (b mod n) ) mod n(ab) mod

7、 n = ( (a mod n ) （b mod n) ) mod n (a (b+c) ) mod n = ( a b) mod n + (a c) mod n冪,模運算 ma mod n m2 mod n = (mm) mod n = (m mod n ) 2 mod n m4 mod n = (m2 mod n ) 2 mod n m8 mod n = ( (m2 mod n )2 mod n )2 mod n m25 mod n = (m m8 m16) mod n 數(shù)論基礎(chǔ)（續(xù)）歐拉函數(shù)(n) n是正整數(shù)， (n) 是比n小且與n 互素的正整數(shù)的個數(shù)(3)=|1, 2| =2 (4)

8、=|1, 3| =2 (5)=|1, 2, 3, 4 | =4 (6)=|1, 5| =4 (7)=|1, 2, 3, 4, 5, 6| =6(10)=|1, 3, 7, 9| =4 (11)=|1, 2,3,4,5,6, 7,8, 9,10| =10 如果p是素數(shù)，則(p)=(p-1), 比如(2), (5)， (11)如果p,q 是素數(shù)，則(pq)=(p) (q) (p-1)(q-1) 。比如，(10)數(shù)論基礎(chǔ)（續(xù)）例如： m=3, n=10; (10)=4 m(n)=34=81 ; 81 mod 10 = 1 即 81 1 mod 10 34+1 = 243 3 mod 10 歐拉定理

9、若整數(shù)m 和n 互素，則等價形式數(shù)論基礎(chǔ)（續(xù)）推論：給定兩個素數(shù)p, q , 兩個整數(shù) n, m ，使得n=pq, 0mn ； 則對于任意整數(shù)k ，下列關(guān)系成立： m k(n)+1 m mod n RSA算法操作過程密鑰產(chǎn)生1. 取兩個大素數(shù) p, q , 保密; 2. 計算n=pq，公開n; 3. 計算歐拉函數(shù)(n) =（p-1）(q-1)；4. 任意取一個與(n) 互素的小整數(shù)e, 即 gcd (e, (n) )=1; 1e i= loga b ; 模運算如何？ b ai mod p = i = logab mod p ？素根（Primitive Root）a是素數(shù)p 的一個素根，如果a

10、mod p, a2 mod p , , ap-1 mod p 是1到p-1的排列p= 19, a i mod p, i=1,2,3,18aa2a3a4a5a6a7a8a9a10a11a12a13a14a15a16a17a18111111111111111111248161371491817151136125101398515726181610111441217131416791711651416791711651561117971641561117971641離散對數(shù)(續(xù))對于任何整數(shù)b 和素數(shù)p 的一個素根a, 可以找到一個唯一的指數(shù)i，使得： b = ai mod p , 其中0i(p-1

11、)i 稱為 b 的以a 為底模p的離散對數(shù)或指數(shù)，記為 ind a,p (b) 對比：對數(shù)運算： i = log a （b） mod p inda,p (1)=0, 因為 a0 mod p =1 mod p =1; inda,p (a)=1 因為 a1 mod p =a mod p =a; 離散對數(shù)(續(xù))y = gx mod p 已知 g, x , p 計算y 是容易的， 已知g, y, p , 計算x 是非常困難的 Diffie-Hellman 密鑰交換過程全局公開的參數(shù)：q 是一個素數(shù)，a q , a是q 的一個素根A 選擇一個私有的XA, XA q計算公開的YA, YA= a XA mo

12、d q B 選擇一個私有的XB, XB q計算公開的YB, YB= a XB mod q YAYBA計算會話密鑰K=(YB) XA mod q B計算會話密鑰K=(YA) XB mod q EK(m)Diffie-Hellman 密鑰交換過程例： 全局公開參數(shù)： q=97, a = 5 ( 5是97 的素根） A選擇私鑰 XA=36 , B 選擇私鑰 XB=58 A 計算公鑰 B 計算公鑰 YA= 5 36 mod 97 = 50 YB= 5 58 mod 97=44 A 與 B 交換公開密鑰 A 計算會話密鑰 K = YBXA mod q = 4436 mod 97= 75 B 計算會話密鑰

13、 K = YAXB mod q = 4436 mod 97= 75 3.3.4 其他公鑰密碼算法DSA1991年, NIST 提出了 數(shù)字簽名算法（DSA）,并把它用戶數(shù)字簽名標準（DSS）只能用于數(shù)字簽名算法的安全性也是基于離散對數(shù)的難度招致大量的反對，理由如下： DSA 不能用于加密或密鑰分配DSA是由 NSA研制的，可能有后門DSA的選擇過程不公開，提供的分析時間不充分DSA比RSA慢（1040倍）密鑰長度太小（512位）DSA可能侵犯其他專利RSA是事實上的標準其他公鑰密碼算法(續(xù))橢圓曲線密碼系統(tǒng)有限域GF(2n)運算器容易構(gòu)造加密速度快更小的密鑰長度實現(xiàn)同等的安全性內(nèi)容提要3.1

14、密碼學(xué)的基本概念3.2 對稱密鑰密碼算法3.3 非對稱密鑰密碼算法3.4 單向散列函數(shù)3.4.1 概要3.4.2 MD5算法3.4.3 其他單向散列算法3.4.4 散列函數(shù)的應(yīng)用3.6 密鑰管理和公鑰基礎(chǔ)設(shè)施(PKI)3.7 OpenSSL簡介3.4.1 單向散列函數(shù)概要Hash : 哈希函數(shù)，雜湊函數(shù)，散列函數(shù)h= H(m)H 具有如下特性：1）可以操作任何大小的報文m；2）給定任意長度的m，產(chǎn)生的h的長度固定；3）給定m 計算h=H(m) 是容易的；4）給定h, 尋找m，使得H(m)=h是困難的；5）給定m ，要找到m,m m 且 H(m)=H(m)是計算上不可行的；6）尋找任何(x,y)

15、 ，xy ，使得H(x) =H(y)是計算上不可行的。簡單的散列函數(shù)縱向的奇偶校驗碼比特1比特2比特n分組1b11b21bn1分組2b21b22bn2.分組mb1mb2mbnm散列碼C1C2CnCi= bi1 bi2 bim+3.4.2 MD5 算法簡介Ron Rivest 設(shè)計, RFC 1321經(jīng)歷過MD2, MD4 不同的版本對任意輸入均產(chǎn)生128bit的輸出基于32位的簡單操作，易于軟件實現(xiàn)簡單而緊湊，沒有復(fù)雜的程序和大數(shù)據(jù)結(jié)構(gòu)適合微處理器實現(xiàn)（特別是Intel）MD5 產(chǎn)生報文摘要的過程報文m1000.0長度Y0Y1YqYL-1MD5MD5MD5MD5摘要128IV512512512

16、512512512512512cv1cvqCvq+1CvL寄存器MD5 產(chǎn)生報文摘要的過程Step1: 填充，使報文長度為512的倍數(shù)減64Step2: 附加長度，將填充前的報文長度寫入最后的64比特，總長度N=L512Step3: 初始化MD 緩存，4個32bit的寄存器（A,B,C,D）,共128 bitsA= 01 23 45 67 B= 89 AB CD EFC=FE DC BA 98D=76 54 32 10MD5 產(chǎn)生報文摘要的過程Step 4 : 處理每個報文分組（512 bits）。算法的核心是4輪循環(huán)的壓縮函數(shù)。使用一個隨機矩陣 T i= 232 abs (sin (i) )

17、 i=1,2,.64CV0= IVCVq+1= SUM32 ( CVq, RFIYq ,RFHYq , RFG Yq ,RFFYq ,CVq Step 5 : 輸出 。 所有L 個 512 bit 的分組處理完之后，第L階段的輸出便是128bit 的報文摘要MD5 的壓縮函數(shù)F,T1,16 , XiG,T17,32 , Xp2iH,T33,48 , Xp3iI,T49,64 , Xp4i128+12832512YqABCDCVqCVq+1基本的MD5 操作（單步）+ : 模 232加法Xk: 512bit 輸入中的第k字節(jié)Ti ： T 矩陣中第i 個32 bitABCDABCD+ new.pe

18、m證書簽名Openssl ca -policy policy_anything -out newcert.pem -config /usr/local/ssl/f -infiles new.pem在Apache服務(wù)器上安裝證書Apache配置文件：/usr/local/apache/conf/httpd.confApache 服務(wù)器證書/usr/local/apache/conf/server_cert.pemApache 服務(wù)器私鑰/usr/local/apache/conf/server_key.pemCA 證書：/usr/local/ssl/cert/cacert.pem實例在客戶端安裝

19、CA證書#!/usr/local/bin/perlrequire 5.003;use strict;use CGI;my $cert_dir = /opt/dev/ssl/private;my $cert_file = CAcert.pem;my $query = new CGI;my $kind = $query-param(FORMAT);if($kind eq DER) $cert_file = CAcert.der; my $cert_path = $cert_dir/$cert_file;my $data = ;open(CERT, $cert_path);while() $data

20、 .= $_; close(CERT);print Content-Type: application/x-x509-ca-certn;print Content-Length: , length($data), nn$data;1;申請客戶端證書 申請客戶端證書Sub SubmitRequestOn Error Resume NextDim szPKCS10,DN,i,MessageDim countryName,localityName,organizationName,OrganizationalUnitName,commonName,emailAddressi=document.Req

21、Form.countryName.options.selectedIndexcountryName=document.ReqForm.countryName.options(i).valuelocalityName=document.ReqForm.localityName.valueorganizationName=document.ReqFanizationName.valueorganizationalUnitName=document.ReqFanizationalUnitName.valuecommonName=document.ReqFmonName.valueemailAddre

22、ss=document.ReqForm.emailAddress.valueIf len( countryName ) =0 ThencountryName=CNEnd IfDN = C= + countryName + ;If len( localityName ) 0 ThenDN = DN + L= + localityName + ;End IfIf len( organizationName ) 0 ThenDN = DN + O= + organizationName + ;End IfIf len( organizationalUnitName ) 0 ThenDN = DN +

23、 OU= + organizationalUnitName + ;End IfIf len( commonName ) 0 ThenDN = DN + CN= + commonName + ;End Ifif len( emailAddress) ThenDN = DN + Email= + emailAddress + ;End If申請客戶端證書IControl.KeySpec = 1CertUsage = .2i = document.all.CSP.options.selectedIndexICviderName = document.all.CSP.options(i).textICviderType = document.all.CSP.options(i).valueIf document.ReqForm.USERPROTECT.value = 1 ThenIControl.GenKeyFlags = 2ElseIControl.GenKeyFlags = 0End IfszPKCS10 = szPKCS10 =