密码学基础与应用

1、第四讲密码学基础与应用(2) 内容提要3.1 密码学的基本概念3.2 对称密钥密码算法3.3 非对称密钥密码算法3.4 单向散列函数3.5 密钥管理和公钥基础设施(PKI)3.6 OpenSSL简介内容提要3.1 密码学的基本概念3.2 对称密钥密码算法3.3 非对称密钥密码算法3.3.1 非对称密码算法原理3.3.2 RSA算法概要3.3.3 Diffie-Hellman 密钥交换算法3.3.4 其他非对称密码算法简介3.4 单向散列函数3.5 密钥管理和公钥基础设施(PKI)3.6 OpenSSL简介3.3.1 非对称密码算法原理对称密钥密码系统的缺陷密钥必须经过安全的信道分配无法用于数字

2、签名密钥管理复杂 O(n2)非对称密钥密码，也称公开密钥密码，由Diffie, Hellman 1976年提出使用两个密钥，对于密钥分配、数字签名、认证等有深远影响基于数学函数而不是代替和换位，密码学历史上唯一的一次真正的革命公钥密码系统的加密原理每个通信实体有一对密钥（公钥，私钥）。公钥公开，用于加密和验证签名，私钥保密，用作解密和签名A向B 发送消息，用B的公钥加密B收到密文后，用自己的私钥解密PlainText加密算法解密算法ABcipherPlainTextB的私钥C的公钥B的公钥任何人向B发送信息都可以使用同一个密钥(B的公钥)加密没有其他人可以得到B 的私钥，所以只有B可以解密公钥

3、密码系统的签名原理A向B 发送消息，用A的私钥加密（签名）B收到密文后，用A的公钥解密（验证）PlainText加密算法解密算法cipherPlainTextABA的私钥A的公钥公钥密码算法的表示对称密钥密码密钥：会话密钥（Ks）加密函数：C= EKsP对密文C，解密函数：DKsC，公开密钥(KUa，KRa)加密/签名：C= EKUbP，EKRaP解密/验证：P= DKRbC，DKUaC数字签名和加密同时使用X加密（签名）加密解密解密（验证）XYZYZ= EKUb Y = EKUb EKRa (X) X= DKUaY = DKUa DKRb (Z) AB产生密钥对产生密钥对KRaKUaKRbK

4、Ub对公开密钥密码算法的要求1.参与方B容易产生密钥对（KUb, KRb）2.已知KUb，A的加密操作是容易的： C=EKUb(P)3.已知KRb，B解密操作是容易的: P=DKRb (C) =DKRb ( EKUb (P) )4. 已知KUb，求KRb是计算上不可行的；5. 已知KUb和C, 欲恢复P是计算上不可行的。公钥密码系统的应用三种用途：加密/解密：数字签名：发送方用自己的私钥签署报文，接收方用对方的公钥验证对方的签名。密钥交换：双方协商会话密钥算法加密/解密数字签名密钥交换RSAYYYDiffie-HellmanNNYDSANYN对公钥密码算法的误解公开密钥算法比对称密钥密码算法更

5、安全？任何一种算法都依赖于密钥长度、破译密码的工作量，从抗分析角度，没有一方更优越公开密钥算法使对称密钥成为过时了的技术？公开密钥很慢，只能用在密钥管理和数字签名，对称密钥密码算法将长期存在使用公开密钥加密，密钥分配变得非常简单？事实上的密钥分配既不简单，也不有效3.3.2 RSA算法简介Ron Rivest, Adi Shamir , Leonard AdlemanRSA的安全性基于大数分解的难度RSA在美国申请了专利（已经过期），在其他国家没有RSA已经成了事实上的工业标准，在美国除外 数论基础a与b的最大公因数：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的最大整数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数论基础（续）模运算是可交换的、可结合的、可分配的(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 数论基础（续）欧拉函数(n) n是正整数， (n) 是比n小且与n 互素的正整数的个数(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是素数，则(p)=(p-1), 比如(2), (5)， (11)如果p,q 是素数，则(pq)=(p) (q) (p-1)(q-1) 。比如，(10)数论基础（续）例如： 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、若整数m 和n 互素，则等价形式数论基础（续）推论：给定两个素数p, q , 两个整数 n, m ，使得n=pq, 0mn ； 则对于任意整数k ，下列关系成立： m k(n)+1 m mod n RSA算法操作过程密钥产生1. 取两个大素数 p, q , 保密; 2. 计算n=pq，公开n; 3. 计算欧拉函数(n) =（p-1）(q-1)；4. 任意取一个与(n) 互素的小整数e, 即 gcd (e, (n) )=1; 1e i= loga b ; 模运算如何？ b ai mod p = i = logab mod p ？素根（Primitive Root）a是素数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离散对数(续)对于任何整数b 和素数p 的一个素根a, 可以找到一个唯一的指数i，使得： b = ai mod p , 其中0i(p-1

11、)i 称为 b 的以a 为底模p的离散对数或指数，记为 ind a,p (b) 对比：对数运算： 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; 离散对数(续)y = gx mod p 已知 g, x , p 计算y 是容易的， 已知g, y, p , 计算x 是非常困难的 Diffie-Hellman 密钥交换过程全局公开的参数：q 是一个素数，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 密钥交换过程例： 全局公开参数： 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 提出了 数字签名算法（DSA）,并把它用户数字签名标准（DSS）只能用于数字签名算法的安全性也是基于离散对数的难度招致大量的反对，理由如下： DSA 不能用于加密或密钥分配DSA是由 NSA研制的，可能有后门DSA的选择过程不公开，提供的分析时间不充分DSA比RSA慢（1040倍）密钥长度太小（512位）DSA可能侵犯其他专利RSA是事实上的标准其他公钥密码算法(续)椭圆曲线密码系统有限域GF(2n)运算器容易构造加密速度快更小的密钥长度实现同等的安全性内容提要3.1

14、密码学的基本概念3.2 对称密钥密码算法3.3 非对称密钥密码算法3.4 单向散列函数3.4.1 概要3.4.2 MD5算法3.4.3 其他单向散列算法3.4.4 散列函数的应用3.6 密钥管理和公钥基础设施(PKI)3.7 OpenSSL简介3.4.1 单向散列函数概要Hash : 哈希函数，杂凑函数，散列函数h= H(m)H 具有如下特性：1）可以操作任何大小的报文m；2）给定任意长度的m，产生的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)是计算上不可行的。简单的散列函数纵向的奇偶校验码比特1比特2比特n分组1b11b21bn1分组2b21b22bn2.分组mb1mb2mbnm散列码C1C2CnCi= bi1 bi2 bim+3.4.2 MD5 算法简介Ron Rivest 设计, RFC 1321经历过MD2, MD4 不同的版本对任意输入均产生128bit的输出基于32位的简单操作，易于软件实现简单而紧凑，没有复杂的程序和大数据结构适合微处理器实现（特别是Intel）MD5 产生报文摘要的过程报文m1000.0长度Y0Y1YqYL-1MD5MD5MD5MD5摘要128IV512512512

16、512512512512512cv1cvqCvq+1CvL寄存器MD5 产生报文摘要的过程Step1: 填充，使报文长度为512的倍数减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 产生报文摘要的过程Step 4 : 处理每个报文分组（512 bits）。算法的核心是4轮循环的压缩函数。使用一个随机矩阵 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 的压缩函数F,T1,16 , XiG,T17,32 , Xp2iH,T33,48 , Xp3iI,T49,64 , Xp4i128+12832512YqABCDCVqCVq+1基本的MD5 操作（单步）+ : 模 232加法Xk: 512bit 输入中的第k字节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服务器上安装证书Apache配置文件：/usr/local/apache/conf/httpd.confApache 服务器证书/usr/local/apache/conf/server_cert.pemApache 服务器私钥/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 =