《PKI(公开密钥构架)》由会员分享，可在线阅读，更多相关《PKI(公开密钥构架)（10页珍藏版）》请在金锄头文库上搜索。
1、DPKI（公开密钥架构）上次谈了一些量子加密的问题，乌龟同学正好也在问WPKI，U哥解答的很清楚了，特别是最后很关键的补充。无聊之中再试着清理一下自己的头脑，也来谈谈PKI（Public Key Infrastructure，公开密钥架构）。PKI之前的加密方法（包括有名的DES算法）都有一个缺陷，就是用来解密的密钥和用来加密的密钥是相同的。这样的话，就避免不了解决发送者和接受者之间既安全又方便地传送密钥的问题了。说白了就是，我写了一封信，把它装在箱子了，再上锁，然后邮寄给你；如果我有什么好的方法将钥匙安全地送到你手中的话，你自然能打开箱子读到我的信了（假设邮差是无法暴力打开箱子的，一定要有钥
2、匙才行）。问题就是人类千百年来就是想不出怎样安全地传递这把钥匙，似乎逻辑上是不可能的。现在让我们一起看看各种方法。一把锁不够那就试试看两把锁。我还是写了一封信，把它装在箱子了，再上锁，然后邮寄给你。你收到后再加一把锁（你自己有钥匙），然后再邮寄给我。我收到后把我的锁给解开了，第三次麻烦邮差GG再把箱子递给你，这一次你收到后就能用你的钥匙打开箱子读到我的信了。注意在这个繁琐的过程当中，邮差只能接触到锁（你的和我的），但是他没办法接触到两把钥匙中的任何一把，所以不存在传递钥匙的问题。大家也许会说，这么简单的方法，用得着那么多年才想出来吗？问题在于发送信息不是真的加把锁头那么简单，加密算法其实就是一
3、个数学函数，输入是要加密的明文，输出是已加密的密文。还记得函数的一个特征吗，就是虽然函数的反函数等于本身，但是套加一个以上的函数后，如果要恢复到原来的数值，必须注意在求反函数时的次序。比如说信件明文是1，我的锁是加1（解锁当然是减1啦），你的锁是乘以2（解锁是除以2）。我先加锁，信件成了1 + 1 = 2，再发给你。你收到2后再加你的锁：2 x 2 = 4，又发给我了。我收到后把我的锁解开：4 - 1 = 3，再发给你。最后你解开自己的锁：3 / 2 = 1.5。Oops，和原来的不一样啊。函数与锁头的不同就在于求反函数时，次序很关键，而解锁的次序却是无关紧要。定义一函数y = (a x) %
4、 b（a的x次方的结果，除以b以后得到的余数）a和b都是质数。在发送任何信息之前，我们先互相见面，共同选好一对质数a和b，假设a = 17而b = 31。现在看看我们怎样利用这个函数来传送密钥再次提醒一下，我们现在讨论的不是怎样利用密钥去加密明文，而是怎样安全地传送密钥。首先我选一个数字，比如说8，将它代进函数y，得到(17 8) % 31 = 18；你也选一个数字，比如说5，也将它代进函数y，得到(17 5) % 31 = 26。接着，我打电话给你，告诉你我的计算结果18，同时你也告诉我你的计算结果26。现在，我将你给我的的计算结果26换掉y函数里的质数a，得到(26 8) % 31 = 2
5、5；你也将我给你的计算结果18换掉y函数里的质数a，得到(18 5) % 31 = 25。像变魔术一样，我们得到的结果是一样的哦（这里不给出数学上的证明）。这样，我们可以用25作为我们这次通信的密钥，然后我们可以用任何加密算法（比如DES算法）加上这个密钥来对明文进行加密。注意到质数a和b的选择是我们事先在保密的情况下选好的，在这一对质数不泄漏的前提之下，就算有第三方知道了我们交换的数字18和26，他也无法算出我们通信时所用的密钥25的。当我们要换密钥时，只需要各自重新选择一个数字后再通一次电话，或者再次见面重新选取另外一对质数。大家可以试试看下面的小程序（随意选择不同的参数）：这个方法有个缺
6、陷，假设我要将保密信件email给你，我先选一数字，代入函数后将计算结果email给你，你收到后知道我要发保密信件，也选一数字带入函数计算后再将结果发给我，我要收到你的计算结果后才能得到新的密钥，再将保密信件用密钥加密后email给你。在有时差的情况下，这一来一回有时需要两天时间。其实我也可以先做一把只有我能打开的锁头，然后复制很多份到处公开派发，谁想寄信给我的话就将信件发在箱子后用我的特制锁头上锁，再寄给我，这样问题不就解决了吗？注意到我公开派发的是锁头，钥匙却只是我自己有。这其实就是PKI的精髓了，公开密钥（public key）其实是锁头加密时用的密钥，私人密钥（private key）
7、就是钥匙解密时用的密钥。不同于上面所举的例子，这一对密钥是不一样的，不过这会不会也和“两把锁方案”一样在数学上是行不通的呢？我们知道很多操作很容易进行反向操作，恢复到原位；比如说给出一个数字，乘以2后要恢复到原数，只需要除以2就行了。但有些操作比较难以进行反向操作，比如我们将蓝色的油漆和黄色的油漆混在一起变成绿色的，要再将它恢复成蓝色和黄色的油漆就困难多了（也许是不可能）。和混合油漆相类似，选两个质数相乘后得到一合数，要再将它分解成原来的两个质数就不那么简单了。比如我们看到数字527，用笔算的话，要花一段时间测试后才能分解成17x31，但是心算17x31都不算很困难。假设我任选一对质数a和b，
8、还是假设a = 17而b = 31，它们的乘积n = 17 x 31 = 527。我再接着选一数字m（这里有一条件，m必须和(a - 1) x (b - 1) = 480互质），为了方便起见，我们就再选一质数，假设m = 11。接着，由公式(c x m) % (a - 1) * (b - 1) = 1先计算出我的私人密钥c： (c x 11) % (16 * 30) = 1 = (c x 11) % 480 = 1 = c = 131 （推出这一步需要用欧几里德算法，方法从略）现在我可以把n = 527和m = 11这对数字（公开密钥）印在我的名片上到处派发，任何人想发加密email给我时，就
9、先将信息代入函数y = (x m) % n，比如你的信息是x=65（字母A的ASCII码），那么y = (65 11) % 527= 65 (1 + 2 + 4 * 2) % 527= (65 1 % 527) x (65 2 % 527) x (65 4 % 527) 2 % 527= (65 x 9 x 81 2) % 527= 44现在你把y = 44发给我。现在我可以利用我的公开密钥c = 131来解密你的信息了：x = (y c) % n = (44 131) % 527 = 44 (1 + 10 * 13) % 527 = (44 1 % 527) x (44 10 % 527)
10、13 % 527= (44 x 36 13) % 527= 65Bingo! 现在我们看到了，加密用的公开密钥n = 527和m = 11和解密用的私人密钥c = 131是完全不同的，这就实现了公开的加密用的锁头和保密的解密用的钥匙不同的目的了。这就是RSA算法的原理。注意在这里，公开密钥527和私人密钥131是对称的，就是说用527加密过的信息可以用131去解密，反之，用131加密过的信息也可以用527去解密。大家也许会说，其实第三方可以从公开密钥n = 527和m = 11分析出527的两个质因子a = 17和而b = 31，然后再由公式(c x m) % (a - 1) * (b - 1
11、) = 1计算出我的私人密钥c = 131。不过我们知道当我选的两个质数a和b足够大时，就算用电脑计算，也不能很有效地从ab的乘积中分解出a和b的数值。在实际应用上，只要能有程序能产生一对足够大的质数，并且使得它们的随机性较大（不同发信者产生的那对质数都是不一样的），那么我们就能用这对质数的乘积作为我们的公开密钥。U哥提过：“我的Treo600用DES，一秒钟几次乃至几十次都OK，但是RSA，我等过一个小时”。DES速度快，但是它是对称密钥结构，有传送密钥上的问题；RSA虽然没有传送密钥的问题，但速度比较慢，我们可以试试看新的结合方案：我可以先用DES密钥加密我的信息，然后再用你的RSA公开密
12、钥来加密我的DES密钥，最后将两者一起发送给你。你收到后，先用你的RSA私人密钥来解开我的DES密钥，然后再利用它来解开我的DES加密信息。这样，我用RSA加密的只是DES的密钥，要加密的内容少，所以RSA的速度缺点不成问题；我用DES加密大的文件，可以利用到DES的速度优势，另一方面，我通过RSA把我的DES密钥发给你，这也利用到了RSA不存在着传送密钥的优势。这就是PGP算法的原理。除了加密（encryption）之外，我们也经常听到验证（authentication），其实验证和加密在公开密钥架构下是一对双胞胎。在加密的情况下，所有想发信给我的人，都用我提供的公开密钥对信息进行加密，而我
13、能用我的私人密钥对收到的信息进行解密。但是，我也可以反过来做，用我的私人密钥对一段无关紧要的信息进行加密，然后附加在我的明文信件发给任何有我公开密钥的人。接受者收到后可以用我的公开密钥进行解密，得到那段无关紧要的信息。这段经过私人密钥加密过的无关紧要的信息其实就是数字签名（digital signature），如果你能用我给的公开密钥解开信息的话，就说明这封信确实是我发给你的因为只有用我的公开密钥才可以解开用我的私人密钥加密过的信息。（一般认为RSA的安全性等价于大数分解质因数的难度，不过并没有严格的证明。在普通计算机上实现RSA的速度差主要是大数运算库的速度差造成的。大数运算在英语中称为ar
14、bitrary precision问题，有很多开源的library可用，我试过几个，都不怎么理想。可能极限情况也就如此了，那些library从实现上来说都是效率挺高的。另外一个流行的公密钥算法是elliptic，是基于平行线在无穷远处相交的数学假设，原理不象RSA那么容易理解，不过最终实现并不复杂，效率和RSA相比差别不是很大。公钥算法就多了，早期的DES使用64bit钥匙，但是实际上有用的是56bit，另外8个bit是奇偶校验，注意不要用奇偶校验位来作为密钥位，这样会降低被破解的难度。56bit DES在网上被一群流氓破解之后，现在时髦的是triple DES了，三次DES运算加密。不过美国
15、鬼子在过去的几年中搞了一个替代DES的算法大赛，历时3年，其实最终入选的5个算法都很优秀，包括rijndael, mars, serpent, blowfish，还有一个名字忘了，很容易查到的。最终胜出的是rijndael，该算法就成了米国的新标准，别名叫做AES，a表示advanced。所有的公密钥或者单钥算法都是公开源码随意使用的，但是公密钥算法中用到的其他库函数，比如大数运算库，就麻烦了，很多是GPL的，不能随意使用；而自己写的东西，如果不是对CPU的汇编指令很熟悉的话，性能恶臭恶臭的。这是实际开发中要仔细考虑的一个问题。QUOTE:Originally posted by 乌龟 at 2004-8-4 06:03 PM:（这里有一条件，m必须和(a - 1) x (b - 1) = 480互质）什么叫互质? 两数互质的意思是说这两个自然数的最大公约数为1，即(a, b)=1指定若干个自然数的最大公约数是指这样的一个自然数，这个自然数能够整除这几个自然数中的每一个，并且不存在一个比它大的自然数，这个自然数也可以整除这些自然数的每一个。自然数a能够整除自然数b，是指存在这样的自然数
