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

1、密码学与网络安全第四讲密码学基础(三) n 讨论议题 密钥分配 公钥密码算法 Diffie-Hellman密钥交换算法 背包算法 RSA算法 EIGamal算法 椭圆曲线密码算法ECCn 密钥分配（Key Distribution）建立密钥分本协议必须考虑两个因素：1） 传输量和存储量就尽可能的小；2） 每一对用户U和V都能独立计算一个秘密密钥。对于通信方A和B来说密钥分配方式由以下几种方式：1） A选择密钥并手工传递给B；2） 第三方C选择密钥分别手工传递给A,B；3） 用A、B原有共享密钥传送新密钥(采用旧密作用于+新密钥方式)；4） 与A、B分别有共享密钥的第三方C的加密连接，C就可以用

2、加密连接传送新密钥给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安全通信。l Key Distribution Center密钥分发中心 l 问题的提出1）密钥管理量的困难传统密钥管理：两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个

3、密钥，当用户量增大时，密钥空间急剧增大。如：n=100 时， C(100,2)=4,995n=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能解密用户间通信的内容n 公开密钥密码起源1） 公钥密码又称为双钥密码和非对称密码，是1976年由D

4、iffie和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-126n 公开密钥密码的重要特性1. 加密与解密由不同的密钥

5、完成；加密：XY：Y = EKU(X)；加密密钥是公开的；解密：YX： X = DKR(Y) = DKR(EKU(X)； 解密密钥是保密的；2. 知道加密算法,从加密密钥得到解密密钥在计算上是不可行的；3. 两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的)；X = DKR(EKU(X) = EKU(DKR(X)n 基于公开密钥的加密过程n 基于公开密钥的鉴别过程n 用公钥密码实现保密用户拥有自己的密钥对(KU,KR)；公钥KU公开，私钥KR保密；AB：Y=EKUb(X)B： DKRb(Y)= DKRb(EKUb(X)=Xn 用公钥密码实现鉴别条件：两个密钥中任何一个都可以用作加密

6、而另一个用作解密鉴别：AALL: Y=EKRa(X)ALL： DKUa(Y)=DKUa(EKRa(X)=Xn 公钥密钥的应用范围加密/解密：发送方用接收方的公开密钥加密报文；数字签名(身份鉴别)：发送用自己的私有密钥“签署”报文；密钥交换：两方合作以便交换会话密钥。n 基本思想和要求： 涉及到各方：发送方、接收方、攻击者； 涉及到数据：公钥、私钥、明文、密文； 公钥算法的条件：1） 产生一对密钥是计算可行的；2） 已知公钥和明文，产生密文是计算可行的；3） 接收方利用私钥来解密密文是计算可行的；4） 对于攻击者，利用公钥来推断私钥是计算不可行的；5） 已知公钥和密文，恢复明文是计算不可行的；6

7、） (可选)加密和解密的顺序可交换。这些要求最终可以归结为一个叫陷门单向函数：单向陷门函数是满足下列条件的函数f：(1)给定x，计算y=fk(x)是容易的；(2)给定y, 计算x使x=fk-1(y)是不可行的。(3)存在k，已知k 时，对给定的任何y，若相应的x存在，则计算x使fk-1(x) 是容易的。n 公钥密码基于的数学难题1） 背包问题；2） 大整数分解问题（The Integer Factorization Problem,RSA体制）；3） 有限域的乘法群上的离散对数问题(The Discrete Logarithm Problem,ElGamal体制)；4） 椭圆曲线上的离散对数问

8、题（The Elliptic Curve Discrete Logarithm Problem,类比的ElGamal体制） n 经典例子：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是

9、各不相同的整数，并且以某种排列方式组成了从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选择一个作为私有密钥的随机数XAP，并计算公开密钥Ya=aXa mod p。A对XA的值保密存放而使YA能被B公开获得。类似地，用户B选择一个私有的随

10、机数XBP，并计算公开密钥Yb=aXb mod 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是保密的，一个敌对方

11、可以利用的参数只有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 9

12、7在他们相互获取了公开密钥之后，各自通过计算得到双方共享的秘密密钥如下： K = (YB)XA mod 97 = 4436 = 75 mod 97 K = (YA)XB mod 97 = 5058 = 75 mod 97从|50，44|出发，攻击者要计算出75很不容易。 下图给出了一个利用Diffie-Hellman计算的简单协议。 用户A 用户BYbYa产生随机的Xa p计算Ya=aXa mod p计算K=YbXa mod p产生随机的Xb aj (j = 1,i-1)，这样的背包也被称为简单背包 求解： 从最大的ai开始，如果S大于这个数，则减去ai，记xi为1，否则记xi为0 如此下去，

13、直到最小的ai 例如背包序列2, 3, 6, 13, 27, 52：求解70的背包；结果为2, 3, 13, 52；所以，密文70对应的明文为110101。3、基于背包问题的公钥密码系统MH公钥算法 加密 将明文分为长度为n的块X=(x1,xn) 然后用公钥A = (a1, , an)，将明文变为密文 S = E(X) = ai xi 解密 先计算S = w-1S mod m，再求解简单背包问题S = aixi4、Eaxmple-从私钥计算公钥 私钥2,3,6,13,27,52，且 n=31, m=1052*31 mod 105= 623*31 mod 105=936*31 mod 105=8

14、113*31 mod 105= 8827*31 mod 105=10252*31 mod 105= 37 公钥62,93,81,88,102,375、Eaxmple-加密6、Eaxmple-解密7、背包密码系统的意义：1） 是第一个公钥密码系统；2） 有较好的理论价值；3） 在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷。 三、RSA算法 1977年由Ron Rivest、Adi Shamir和Len Adleman发明，1978年公布 是一种分组加密算法。 明文和密文在0n-1之间,n是一个正整数 应用最广泛的公钥密码算法 只在美国申请专利，且已于2000年9月到期1、RSA算法

15、描述RSA加、解密算法(1978 Rivest,Shamir,Adelman) 分组大小为k, 2k n 2k+1 公开密钥n（两素数p和q的乘积）（推荐p,q等长）e（与(p-1)(q-1)互素）ed1(mod(p-1)(q-1) 私人密钥d（e-1 mod(p-1)(q-1) ） 加密c=me mod n 解密m=cdmod n 2、RSA密钥生成原理 3、RSA密码体制的实现（p139）实现的步骤如下：Bob为实现者(1)Bob寻找出两个大素数p和q(2)Bob计算出n=pq和 (n)=(p-1)(q-1).(3)Bob选择一个随机数e(0e (n)，满足（e， (n)）1(4)Bob使

16、用辗转相除法计算d=e-1(mod (n)(5)Bob在目录中公开n和e作为她的公开钥。选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足0mn。加密P时，计算CPe(mod n)，解密C时计算PCd(mod n)。由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。为实现加密，需要公开(e, n)，为实现解密需要(d, n)。4、example（1）若Bob选择了p=101和q113（2）那么，n=11413, (n)=10011211200；（3）然而1120026527，一个正整数e能用作加密指数，当且仅当e不能被2，5，7所整除。假设Bob选择了e=3533

17、，（4）那么用Euclidean算法将求得：d=e -1 6597(mod 11200), 于是Bob的解密密钥d=6597.（5）Bob在一个目录中公开n=11413和e=3533（6）现假设Alice想发送明文9726给Bob，她计算：97263533(mod 11413)=5761，且在一个信道上发送密文5761。（7）当Bob接收到密文5761时，他用他的秘密解密指数（私钥）d6597进行解密：57616597（mod 11413)=97265、实现要求若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来。建议选择p和q大约是100位的十进制素数。模n的长

18、度要求至少是512比特。EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC 9796中规定n的长度位512比特位。至1996年，建议使用768位的模n。6、素数的选取 为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：(1)|p-q|很大，通常p和q的长度相同；(2)p-1 和q-1分别含有大素因子p1和q1(3)P1-1和q1-1分别含有大素因子p2和q2(4)p+1和q+1分别含有大素因子p3和q37、加密指数e的选取 为了提高加密速度，通常取e为特定的小整数，如EDI国际标准中规定e216 +1，ISO/IEC9796中甚至允许取e3。这时加密速度一般比解密速度快10倍以上。e2161优于e3之处在于它能够抵抗对RSA的小加密指数攻击8、 RSA 加密算法的缺点1)产生密钥很麻烦，受到