04密码学与网络安全第四讲

密码学与网络安全 第四讲密码学基础(三)  讨论议题 • 密钥分配 • 公钥密码算法 – Diffie-Hellman密钥交换算法 – 背包算法 – RSA算法 – EIGamal算法 – 椭圆曲线密码算法ECC

 密钥分配（Key Distribution） 建立密钥分本协议必须考虑两个因素： 1） 传输量和存储量就尽可能的小； 2） 每一对用户U和V都能独立计算一个秘密密钥。 对于通信方A和B来说密钥分配方式由以下几种方式： 1） A选择密钥并手工传递给B； 2） 第三方C选择密钥分别手工传递给A,B； 3） 用A、B原有共享密钥传送新密钥(采用旧密作用于+新密钥方式)； 4） 与A、B分别有共享密钥的第三方C的加密连接，C就可以用加密连接传送新密钥给A和/或B。 • N个用户集需要N(N-1)/2个共享密钥。 简单的密钥分配： 1）A产生公/私钥对{ PUa ，PRa}并将PUa和其标识IDa的消息发送给B； 2）B产生秘密钥KS，并用A的公钥对KS，加密后发送给A； 3）A计算D（PUa E（PUa，KS）得出秘密钥KS。因为只有A能解密该消息，只有A和B知道KS； 4）A丢掉PUa ，PRa，B丢掉PUa 。 A和B 可以用传统的密码和会话密钥KS安全通信。  Key Distribution Center密钥分发中心  问题的提出 1）密钥管理量的困难 传统密钥管理：两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如： n=100 时， C(100,2)=4,995 n=5000时， C(5000,2)=12,497,500 （2）数字签名的问题 传统加密算法无法实现抗抵赖的需求。 密钥分发 1） 每个用户与KDC有共享主密钥(Master Key)； 2） N个用户，KDC只需分发N个Master Key； 3） 两个用户间通信用会话密钥(Session Key)； （会话密钥：端系统之间的通信使用一个临时的密钥进行加密，这个密钥叫会话密钥） 4） 用户必须信任KDC； 5） KDC能解密用户间通信的内容  公开密钥密码起源 1） 公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见划时代的文献：W.Diffie and M.E.Hellman, New Directrions inCryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976,PP.644-654； 2） RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的, Communitions of the ACM. Vol.21.No.2.Feb. 1978, PP.120-126  公开密钥密码的重要特性 1. 加密与解密由不同的密钥完成； 加密：X→Y：Y = EKU(X)；加密密钥是公开的； 解密：Y→X： X = DKR(Y) = DKR(EKU(X))； 解密密钥是保密的； 2. 知道加密算法,从加密密钥得到解密密钥在计算上是不可行的； 3. 两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的)； X = DKR(EKU(X)) = EKU(DKR(X))  基于公开密钥的加密过程  基于公开密钥的鉴别过程

 用公钥密码实现保密 •用户拥有自己的密钥对(KU,KR)； •公钥KU公开，私钥KR保密； •A→B：Y=EKUb(X) •B： DKRb(Y)= DKRb(EKUb(X))=X  用公钥密码实现鉴别 •条件：两个密钥中任何一个都可以用作加密而另一个用作解密 •鉴别：A→ALL: Y=EKRa(X)

ALL： DKUa(Y)=DKUa(EKRa(X))=X  公钥密钥的应用范围 •加密/解密：发送方用接收方的公开密钥加密报文； •数字签名(身份鉴别)：发送用自己的私有密钥“签署”报文； •密钥交换：两方合作以便交换会话密钥。

 基本思想和要求： • 涉及到各方：发送方、接收方、攻击者； • 涉及到数据：公钥、私钥、明文、密文； • 公钥算法的条件： 1） 产生一对密钥是计算可行的； 2） 已知公钥和明文，产生密文是计算可行的； 3） 接收方利用私钥来解密密文是计算可行的； 4） 对于攻击者，利用公钥来推断私钥是计算不可行的； 5） 已知公钥和密文，恢复明文是计算不可行的； 6） (可选)加密和解密的顺序可交换。 这些要求最终可以归结为一个叫陷门单向函数： 单向陷门函数是满足下列条件的函数f： (1)给定x，计算y=fk(x)是容易的； (2)给定y, 计算x使x=fk-1(y)是不可行的。 (3)存在k，已知k 时，对给定的任何y，若相应的x存在，则计算x使fk-1(x) 是容易的。  公钥密码基于的数学难题 1） 背包问题； 2） 大整数分解问题（The Integer Factorization Problem,RSA体制）； 3） 有限域的乘法群上的离散对数问题(The Discrete Logarithm Problem,ElGamal体制)； 4） 椭圆曲线上的离散对数问题（The Elliptic Curve Discrete Logarithm Problem,类比的ElGamal体制）

 经典例子： 1） Diffie-Hellman密钥交换算法； 2） 背包算法； 3） RSA算法； 4） EIGamal算法； 5） 椭圆曲线密码算法ECC 一、 Diffie-Hellman密钥交换 Diffie-Hellman密钥交换算法的有效性依赖于计算离散对数的难度。简言之，可以如下定义离散对数：首先定义一个素数p的原根，为其各次幂产生从1 到p-1的所有整数根，也就是说，如果a是素数p的一个原根，那么数值 a mod p, a2 mod p, ..., ap-1 mod p 是各不相同的整数，并且以某种排列方式组成了从1到p-1的所有整数。 对于一个整数b和素数p的一个原根a，可以找到惟一的指数i，使得 b = ai mod p 其中0 ≤ i ≤ (p-1) 指数i称为b的以a为基数的模p的离散对数或者指数。该值被记为inda ,p(b)。 基于此背景知识，可以定义Diffie-Hellman密钥交换算法。该算法描述如下： 1、有两个全局公开的参数，一个素数P和一个整数a，a是P的一个原根。 2、假设用户A和B希望交换一个密钥，用户A选择一个作为私有密钥的随机数XA获得。类似地，用户B选择一个私有的随机数XBmod p 。B对XB的值保密存放而使YB能被A公开获得。 3、用户A产生共享秘密密钥的计算方式是K=YbXa mod p。同样，用户B产生共享秘密密钥的计算是K=YaXb mod p。这两个计算产生相同的结果：

K = (YB)XA mod P = (aXB mod P)XA mod P = (aXB)XA mod P （根据取模运算规则得到）

= aXBXA mod P = (aXA)XB mod P = (aXA mod P)XB mod P = (YA)XB mod P 因此相当于双方已经交换了一个相同的秘密密钥。 4、因为XA和XB是保密的，一个敌对方可以利用的参数只有P、a、YA和YB。因而敌对方被迫取离散对数来确定密钥。例如，要获取用户B的秘密密钥，敌对方必须先计算 XB = inda ,P(YB) 然后再使用用户B采用的同样方法计算其秘密密钥K。 Diffie-Hellman密钥交换算法的安全性依赖于这样一个事实：虽然计算以一个素数为模的指数相对容易，但计算离散对数却很困难。对于大的素数，计算出离散对数几乎是不可能的。 下面给出例子。密钥交换基于素数P = 97和97的一个原根a = 5。A和B分别选择私有密钥XA = 36和XB = 58。每人计算其公开密钥 YA = 536 = 50 mod 97 YB = 558 = 44 mod 97 在他们相互获取了公开密钥之后，各自通过计算得到双方共享的秘密密钥如下： K = (YB)XA mod 97 = 4436 = 75 mod 97 K = (YA)XB mod 97 = 5058 = 75 mod 97 从|50，44|出发，攻击者要计算出75很不容易。 – 下图给出了一个利用Diffie-Hellman计算的简单协议。 用户A 用户B

` 2、Diffie-Hellman密钥交换的攻击 Yb

Ya 产生 随机的Xa < p 计算Ya=aXa mod p 计算K=YbXa mod p 产生 随机的Xb < p 计算Yb=aXbmod p 计算K=YbXbmod p