加密?

本文会假设你了解过密码学,接着演示一个RSA算法实例。最后试图引发一些问题。下面进入正题。

非对称加密,又叫公开密钥加密。先看一个熟悉的场景

小明同学不厌其烦地ssh到某台机器,十年如一日地敲密码。通常情况下,这种密码又复杂又长。终于,小明受不了了。他先ssh-keygen生成密钥对,再将公钥ssh-copy-id到该机器,就此进入了免输密码时代。

这里利用的当然就是非对称加密技术。逻辑上我们拿到公钥不能推导出私钥,却能推导出加密信息,是不是有点玄学?所以现实中退而求其次,只求反向推导过程超级复杂即可。这里最常见的就是RSA算法,其名源为三个图灵奖作者的姓氏首字母。

我们直接看实例:

  • 还是小明同学。他先挑了2个质数的常量p = 3, q = 11
  • 又挑了个常量n = p × q = 3 × 11 = 33
  • 然后定义一个函数一下ϕ(n) =  (p – 1) × (q – 1) = 20
  • 小明又挑了一个不能整除ϕ(n)且小于ϕ(n)的常量 e = 7
  • 接着计算常量d,其值为e (mod ϕ(n))的逆膜元,也就是 d × e mod ϕ(n) = 1,这里暴力求解,d = 3。
  • 然后小明就忘了p 和 q是多少了…
  • 其实这里(n = 20, e = 7)就是公钥,(n = 20, d = 3)就是私钥
  • 然后我拿到公钥随即发给小明一个消息m = 12,加密消息为  [latex]c = m^e\;mod\;n [/latex] = 8
  • 小明用私钥解密[latex]m = c^d\;mod\;n [/latex] = 12,成功了,万岁~

啊…刚刚发生了什么?其实操作很简单,我们生成了密钥对,他们共享一个常量n。加密用公钥的特征量e对原始信息做乘方再膜n,解密时对加密信息用私钥的特征量d做乘方再膜n。这个方法看似莫名其妙,这是因为它的依据欧拉函数就完全不讲道理:[latex] n^{φ(n)}≡ 1 \;mod\;n[/latex]。

我不知道是否有人真正理解了这个函数的意义。无论如何,思考它用了我相当长一段时间。这个函数被用作RSA的理论依据只是时空中的巧合,这之前的200多年它仅仅只是个精妙的数学公式。翻阅整个数学史,你还会发现大量类似精妙的事物,它们的存在不为服务于任何工程学。我不清楚这是否代表了一种现实的本质,再来就非常形而上学了。

想起来,小学刚接触奇形怪状的数学原则时,这些感觉也是萦绕于心。小时候总想着以后就明白了,现在看来,我也只是习惯了它们的存在。至于为什么存在恐怕永远也搞不清楚了。

Leave a Reply

Your email address will not be published. Required fields are marked *