Algorithm 版 (精华区)

发信人: Lerry (戒网·学习), 信区: Algorithm
标  题: 公开密钥算法简介
发信站: 哈工大紫丁香 (2001年11月20日21:22:39 星期二), 站内信件

公开密钥算法简介
前言
在加密体系中，被美国官方批准并随后由国际标准化组织ISO采纳为国际标准的DES加密
体系是目前最为广泛应用的标准。DES算法通过16轮代替和置换间复杂算法的结合，使得
跟踪数据的变化是相当复杂的，籍由此种复杂性及一些未被公开的DES敏感的关键技术部
分，保证了这种算法的安全性。但单密钥DES算法经国外公司组织的利用因特网资源，可
以在数天内攻破DES密钥。虽然仍然没有采用双密钥进行重复3次DES运算的3DES加密体系
被攻破的记录，但由于符合摩尔定律的当今计算机硬件技术的飞速发展，DES体系的安全
性已经引起了相关人士的忧虑，在加上DES为对称密钥算法，即其加密和解密为同一个密
钥，这在一些场合，如不同系统间的加密信息交换，对于密钥的管理也是一个巨大的挑
战。
因此，在一些特定场合（如IC卡技术），已经或正在采用公钥体系-非对称密钥加密体系
来完成安全性控制。Diffie和Hellman最早于1976年提出了这种加密和解密采用不同密钥
的新算法，每个系统都可以公开一个密钥，而这种公开将决不会损害其体制的保密性。

这种公钥变换实际上是某种信息进行加密运算，解密时要用一种专用密钥的方法。
2、公钥体系的优点：
公钥体制相对于传统的对称密钥体系具有许多优点：其他系统可以给指定的系统发送一
份采用同一个密钥加密（即公钥）的报文，当然这份密钥对于非交换信息的系统外而言
是受保护的，防止了恶意的信息篡改和监听，如图1：系统2和系统3都用系统1的公开密
钥与系统1通讯，即使系统2知道了系统3与系统1的通讯信息时，也无法解密出来（因为
系统1的解密密钥是保密的）；而对于一个传统的对称密钥体系（如DES），每对系统间
都需要有一个互不相同的密钥，因此，通常N个系统就需要N*（N-1）/2个密钥，那么，
密钥的产生，和维护都比较困难。
3、公钥体系的基本原理：
在公钥体制中，系统拥有有一对称为（公开密钥，私有密钥）对的密钥组，这对密钥互
逆，系统可以公开其中的一个密钥。
P=D(d,E(e,P)) (1)
P=E(e,D(d,P)) (2)
其中：P=明文；D（）=解密算法；E（）=加密算法；d=私有密钥；e=公开密钥，
即，可以用私有密钥对用相应的公开密钥加密的信息进行解密，如（1）；
同时，也能用公开密钥将相应的私有密钥加密的密文解开，如（2）；
代表式（1）、（2）表明：私有密钥和公开密钥具有互换性，即公开密钥与私有密钥只
是概念的不同，其实质是没有区别的。
4、RSA加密体制
RSA加密算法于1978年提出（即为发明人Rivest,shamir,Adelman的缩写），当前在许多
场合有广泛的应用，如IC卡技术，数字签名，第三方认证（如电子商务中的SSL安全认证
控制等）。
2．1、RSA加密算法简介
假设：d=解密密钥，e=加密密钥，P=明文信息，C=明问P加密后的密文信息：
则加密过程为：明文P进行e次方运算后的结果对模数n取模，如下式所示：
C=Pemod n （3）
同样，解密过程为：
P=Cdmod n （4）
将（3）式代入（4）式，经简化后得到：
P = Cdmod n =（Pe）dmod n = (Pd)emod n
即：既加密和解密过程是互逆的，可解的；同时也说明，加密密钥和解密密钥也是互逆
的。
因此，RSA算法系统中的加密密钥e,解密密钥d和模数是整个体系中的重要元素，其中：
加密密钥组为一对整数（e,n），解密密钥为对应的（d,n）。
在密钥的产生过程中，产生足够大的2个整数p,q，得到n = p*q；并产生足够大的整数e
（实用过程中通常为1024位或512位整数），使得e与（p-1）*（q-1）互素（指二者间最
大公因子为1），在根据公式：
e*d o 1 mod（p-1）*（q-1）
产生d。这样产生的e，d，n将可以满足（3）、（4）公式。
RSA加密算法涉及了大素数的产生、算术模运算。其依据是欧拉和费尔码2位数学泰斗的
数论研究成果。从上述可以看出，只要确定了素数p和q，就能知道密钥组e,d和n（当然
通过e和n，从而计算出d是不可能的），但是由于在数学上一个大数的分解即使在理论上
也有相当的困难，目前知道的最快算法是指数时间，同时需要进行大量的大数数学运算
（对通常的计算机系统，其能表示的最大数比如长整型，也只能表示10位数），因此，
只要我们产生足够大的p,q（比如300位以上），就能完全保证加密体系的安全性。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]