浅谈公钥密码

前篇文章谈到一个非对称密钥加密系统,觉得很是神奇,一直想找一个实例,最近查阅了一些资料,google了一下,找到一些,分享一下。

它的用途有很多,数字证书啊,https啊,我感触最深的就是那个ssl加密,感觉很神奇,试想你和网站中间的路由一直在监听你们的传输数据,甚至从发送证书开始,只要通过ssl加密,它就不能窃取了(当然没那么绝对)。

首先看左图,有一个RSA看到了吧,他是很关键的一个密码加密系统,gmail网站有一个公钥,它是对所有人公开的,任何访问它的人都可以得到,用它可以进行加密;然后它还有一个密钥,通过密钥就可以对加密内容解密,gmail的任务是保管好密钥,任何人都不能得到。

大家可能会在网上搜到两个大素数的积分解困难等关键字,却不太明白具体的原理,我在这儿举个例子,例子是在一本叫《公钥密码学》上看到的,很简单,能让我们懂得基本原理。

参数生成:

(1) 选取两个大素数p和q (保密)

(2) 计算n=pq(公开的系统参数),γ=(p-1)(q-1)(保密)

(3) 随机选取整数e(公开的加密密钥),使得gcd(e, γ)=1

(4) 计算d(保密,私人密钥),使得ed≡1(mod γ),即d=e-1(mod γ)

(5) 加密:c=me mod n

(6) 解密:m=cd mod n

举一个实际的例子:

p = 11, q = 23,则 n = pq = 253

γ=(p-1)(q-1) = 220

选取加密密钥 e = 3,显然gcd(3, 220) = 1,求得 d = 147。

对于明文 m = 165,有密文 c ≡ 165 * 165 * 165 mod 253 ≡ 110

对于密文 c = 110,有明文 m ≡ 110^147 mod 253 ≡ 165

看,上述就是一个简单加密,解密的例子,你可能会说p, q岂不是很容易猜出来,请记住“两个素数的积分解困难”,很大的!

完成这步之后,客户端浏览器按照服务器的只是生成128位的RC4对称密钥,你可能会问,这个时候为什么不用非对称的?因为效率!非对称虽然有很多的好处,但是有效率限制,再说双方通过RC4传输,通过刚才的非对称加密已经保证这个RC4密钥的安全性了,为什么还要再用非对称呢。

当然这个RC4不是绝对的,服务器也可能要求使用别的加密方法,例如微软的live用的是128位的AES,QQ邮箱用了256位的AES,但他们都是对称密钥加密。

顺便再提一嘴MD5,本来和密码没什么关系,但是学习的过程中,仿佛在说不可能有两个MD5一样的不同文件。我就一直在想,如果通过一个128位的字符串就能表示几G的电影,岂不是说任何文件都能压缩到128个字节,或者说128位字符串能表示所有文件?

其实是我的理解错误,MD5的算法网上有很多,大家看一下就会发现,确实文件之修改一点点都会造成MD5的值发生变化。

它的要求是:
对任何给定的码h,寻找x使得H(x)=h在计算上,是不可行的,称为单项性;
对任何给定的分组x,寻找不等于x的y,使得H(y)=H(x)在计算上是不可行的。称为弱抗冲突;
寻找对任何的(x,y)对,使得H(y)=H(x)在计算上是不可行的,称为强抗冲突;

看,上述的都是强调在计算上,上网搜一下MD5碰撞,你就会发现存在两个不同文件MD5值相同。

好,今天到这里,文章可能有疏漏,请指正!

原创文章,转载请注明: 转载自yongxiu

本文链接地址: https://yongxiu.net/201104/12198.html

1 thought on “浅谈公钥密码

Comments are closed.