《计算机网络安全技 术第 4章》由会员分享，可在线阅读，更多相关《计算机网络安全技 术第 4章（29页珍藏版）》请在金锄头文库上搜索。
1、第四章 公开密钥密码体制 前面介绍的对称密码体制就是传统密码体制，在传统密码体制中，加密密钥和解秘密钥是一样的，任何人只要获得加密密钥就可以得到解密密钥，从而可以对加密密钥加密的密文进行解密，获得明文。因此传统密码体制中，密钥是不公开的，任何通信的双方只有先确定密钥才能进行保密通信。,在当今信息社会里，计算机及计算机通信网络已广泛用于社会的各个领域。利用计算机网络进行资金的转移、商业谈判、采购销售等商务活动比以前更加方便快捷，而这些商务活动的信息从某种意义上来说就是财富，因此其信息的保密是人们迫切需要的。假如一个计算机网络有n个用户，那么网络就需要有n(n-1)/2个密钥。当n 较大时，这个数
2、是很大的。同时为了安全的需要，通信双方要不断的改变密钥，如此大的密钥要经常的产生、分配与更换，其困难性是可想而知的。有时甚至是不可能实现的；另方面，利用计算机网络进行以上活动，其信息的真实性也是人们迫切需要的。为了防止诈骗，通信双方必须对对方身份进行验证，有时还需要通信双方对信息进行签名，以便在发生纠纷时，能够提交第三者（如法院）进行仲裁。这一切都使传统的密码体制越来越不能适应计算机网络保密通信的要求了，人们迫切需要寻找新的密码体制。,大家知道，现实社会中存在一些所谓单向“街道”，沿着这些街道从A地到B地很容易，而从B地到A地就很难，比如说一个大城市的电话簿，给定一个人的姓名，你就可以很容易地
3、按姓氏笔画查出他的电话号码；而任意给定一个电话号码，要知道是谁的电话号码就很困难，有时需要查阅整个电话簿。这就是单向函数。 定义4.1.1 函数f (x)是单向函数，如果给定x，求f (x)是容易的；而给定f (x)，求x则是困难的，这里的难意味着即使世界上所有的计算机都用来计算这个难题，也要费很长时间。 前面介绍的整数分解、背包和离散对数的NP-问题就是单向函数。 1976年，美国学者Diffie和Hellman根据单向函数的概念提出了公开密码密钥体制，引起了密码学的一场革命。公开密钥密码体制从根本上克服了传统密码体制的困难，解决了密码分配和消息认证等问题，特别适合计算机网络系统的应用。,公
4、开密钥密码体制简称公钥体制，其基本思想是利用求解某些数学难题的困难性，它与传统密码体制不同，用户的加密密钥和解密密钥不再相同，从加密密钥求解解密密钥是非常困难的。因此用户可以公开加密密钥，登记在网络的密钥数据库中，就像把自己的电话号码公开在电话号码本上，任何人要与某个用户U通信，只要在公开的密钥数据库中查得用户U的加密密钥，用此加密密钥将明文加密为密文，将密文传送到指定用户U，任何人没有解密密钥都不能恢复出明文。用户U 可以用仅有自己知道的解密密钥对接收到的密文进行解密，恢复出明文，从而完成保密通信。 在公钥体制中，加密密钥往往就是加密变换，记为E，解密密钥往往就是解密变换，记为D。因此下面介
5、绍几种常见的公钥体制。,41 RSA体制和Rabin体制 在Siffie和Hellman提出了公开密钥密码体制的设想以后，先后由Merkle和Hellman提出了背包公钥体制，Rivest，Shamir和Adlmaml联合提出简称为RSA的公钥体制。背包密码体制稍后介绍，本节介绍RSA体制及其变形。 1 RSA体制 RSA体制是美国麻省理工学院（MIT）Rivest，Shamir和Adlerman于1978年提出来的，它是第一个成熟的、迄今为止理论上最为成功的密码体制，它的安全性基于数论中的Euler定理和计算复杂性理论中的下述论断：求两个大素数的乘积是容易计算的，但要分解两个大素数的乘积，求
6、出他们的素因子是非常困难的，它属于NP-完全类。下面讨论RSA加、解密过程。,1） 密钥生成 （1） 随机选取两个大素数（比如200位十进制数）p和q，令N = pq，随机选取两个整数e和d的积与（N）互素，即ed 1mod (N)； 注：(N)就是第二章介绍的Euler函数。 （2） 公开N，e，作为E，记作E = (N，E)； （3） 保密p，q，d与(N)作为D，记作D = (p，q，d，(N) ) (其实p，q可以丢掉，但决不能泄漏)； 2） 加密过程 （1） 在公开密钥数据库中查得用户U的公钥：E = (N，e)； （2） 将明文分组x = x1x2xr，使得每个xiN，i = 1,
7、2,r； （3） 对每组明文作加密变换 yi = E(xi)xie mod N， i = 1,2,r； （4） 将密文y = y1y2yr传送给用户U。,3）解密过程 （1） 先对每一组密文作解密变换 xi = D (yi) yid mod N （2） 合并组得到明文x = x1x2xr 。 下面证明解密过程是正确的： 设xi与N互素，即gcd(xi，N) = 1 ed 1 mod (N) 存在某个整数k，使得ed1+k(N) D(yi) yid mod N xied mod N xi1+ k(N) mod N xixi k(N) mod N xi 如果xi与N不互素，也能证明 D(yi) =
8、 xi 因此解密过程是正确的。,例4.1假设B选择p = 101和q = 113，那么n = pq = 101113 =11413，(n) = 100112 =11200；选择 e =3533，那么d = e-1 mod 11200 = 6579。B公开n =11413和e = 3533，现假设A要发送明文9226给B。A计算92263533mod 11413 = 5761，将5761通过公开信道传送给B。B收到5761后，进行解密，5761dmod 11413 = 57616597mod 11413 = 9226，从而B获得明文9226。 RSA的安全性依赖于大数的分解，但并没有从理论上证明
9、破译RSA的难度与大数分解难度等价，因为没有证明破译RSA就一定要做大数分解。即RSA的重大缺陷就是无法从理论上把握它的保密性如何，而且密码界多数人是倾向于因子分解不是NP-问题。目前，RSA实验室认为，512比特的大数n已不够安全，在1998年后应停止使用。他们建议，现在的个人应用需要用768比特的n，公司要用1024比特的n，极其重要的场合应该用2048比特的n。 RSA算法的保密强度，随着其密钥的长度增加而增加。但是，密钥越长，其加、解密所耗费的时间也越长。因此，要根据所保护信息的敏感程度、攻击者破解所要花的代价值不值得等因素来综合考虑。尤其对于商业信息领域更是如此。,2.Rabin体制
10、 根据前面的讨论，若存在能够分解两个大素数乘积的办法，那么就一定能够攻破RSA。但是人们并没有证明要攻破RSA就一定要分解两个大素数的乘积。Rabin基于RSA体制，提出了一种变形的公开密钥体制，这就是Rabin体制。从理论上可以证明要攻破Rabin体制，必须要分解两个大素数的乘积。下面介绍Rabin体制的加密过程。 1) 密钥生成 (1) 随机选取两个大素数p与q，令N = pq，随机选取整数BN； （2） 公开N，B作为E记为E = (N，B)； （3） 保密p，q作为D，记为 D =(p，q),2）加密过程 （1） 在公开密钥数据库中，查得用户U的公钥E =（N，B）； （2） 将明文分
11、组x = x1x2xr，使得每个xiN，i = 1，2，r； （3） 对每一组明文作加密变换，yi = E (xi) xi (xi +B) mod N； （4） 将密文y = y1y2yr传送给用户U。 3）解密过程 （1） 对每一组密文yi求xi2+Bxi = yi mod N的解； （2） 合并分组得到明文x =x1x2xr 。,3素性测试 在建立RSA和Rabin密码体制时，产生大的“随机素数”是必要的，在实际应用中，所用的方法实现产生一个大的随机数，然后对此进行素性检测。素性测试的方法比较多，下面介绍两种： 1）基于Legendre符号的素性测试 定理4.2.1 设P是素数，那么,这里
12、 是2.1节中定义的Legendre符号。,定理4.2.2 设n1是素数，那么,另一方面，如果n是合素，则至多有一半的整数a(1an-1)满足,根据这两个定理，我们就可以对一个随机数进行素性检测了。其过程如下： （1）随机选择一个整数a，a(1an-1)； （2）计算 ；,（3）如果 ，则回到步骤1，否则认为是 合数，退出； 重复步骤1，2，3共t次（t任意取值），如果每次都有 则一般认为n是素数。,2）概率性素性测试方法 概率性素性测试方法产生的数仅仅是伪素数，尽管其产生合数的可能性很小，但是这种可能性总是存在。其优点是产生的伪素数没有规律性，而且产生的速度也比较快。此类方法是产生大素数的主
13、要方法，其中最著名的算法有Miller Rabin算法。 定义4.2.1 设n时正整数， ，其中c是非负整数，m是正奇数，若存在正整数a，使得a1(mod n)，或对某个非负数t，0tc，满足 ，则称n通过以a为基的Miller测试。 定理 4.2.3 若n是素数，a是正整数，gcd(n，a)=1，则n必然通过以a为基的Miller测试。 亦即若gcd(n，a)=1,而不通过以a为基的Miller测试，则n不是素数。,定理4.2.4 若n为合数，则n通过以a为基的Miller测试的数目最多为(n-1)/4，1an-1。 基于定理4.2.3和4.2.4，如果n是正整数，选k个小于n的正整数，以这
14、k 个数作为基进行Miller测试,如果n是合数，k次测试全部通过的概率是（1/4）k。比如k=100，n是合数，但全部通过的概率为（1/4）100=6.2210-61，这是个很小的数，说明这样的事情几乎不会发生。 另外，还有所谓强素数和安全素数的产生的问题。,4.2 背包体制 背包公钥体制是1978年由Merkle和Hellman基于求解背包问题的困难性而提出的一种公开密钥密码体制。根据2.3的介绍，背包问题属于NP-完全问题，是比较困难的问题。虽然背包问题属于NP- 完全问题，但不是任意背包问题都是很困难的，有时也是很容易的。例如，超递增背包问题就很容易求解。 定义4.3.2 正整数序列a
15、1，a2an称为超递增的，若对任何1ln-1，有 例4.2 （1，2，4，8，16）就是一个超递增序列。 定理4.3.1 由超递增序列a1，a2an及S 确定的超递增背包问题是容易求解的。 下面讨论背包体制的加密、解密过程。,1 . 密钥生成 1）随机选取一超递增序列（e1，e2en）,作为用户的密秘密钥，记作D = (e1，e2en) 2)选取一对大的且互素的数w，N,并把背包序列（e1，e2en）变为困难的背包序列。 T(ei) we i mod N 3）将(T(e1)，T(e2)，T(en)公开作为E ，记作E=(T(e1)，T(e2)，T(en) 2. 加密过程 1)在公开密钥库中查得
16、用户的公开密钥 E = (T(e1)，T(e2)，T(en) 2)将明文表示成二元序列，并适当分组x=x1x2xr，每组长n比特 3）将每一组明文作加密变换,4）将密文y = y1y2yn传送给用户。,3 解密过程 1）计算yi w -1yi mod N 2)按照超递增向量序列（e1，e2en），从y 还原xi 3）合并分组得到明文x = x1x2xr 例4.3 设n = 10，考虑超递增序列 A（103，107，211，430，863，1718，1449，6097，13907，27610） 选取N = 55207，W = 25236，则W 1 = 1061。将超递增序列变为困难的背包向量。 E
