Ronald L. Rivest
罗纳德·李维斯特^[1] （1947年5月6日－），美国密码学家，美国工程院、科学院、艺术与科学院院士，ACM/IEEE/IACR Fellow。他是麻省理工学院电子工程和计算机科学部门（EECS）计算机科学的教授和麻省理工学院之计算机科学和人工智能实验室（CSAIL）的成员。他的工作涉及算法和组合学、密码学、机器学习和选举完整性等领域。其最出名的研究结果是他与阿迪·萨莫尔和伦纳德·阿德曼共同发明了 RSA 加密算法。RSA 被广泛使用在计算机安全应用上，包括 HTTPS。2002年，他与阿迪·萨莫尔和伦纳德·阿德曼一起因在公钥密码学 RSA 加密算法取得的杰出贡献而获得图灵奖。^[2]
1964年，在美国斯克内克塔迪的郊外，一位高三学生正在用一种使用带字母标记方格编程的原始语言，尝试编写一个用三条边长计算三角形面积的小程序。在那个计算机还未普及的年代，这个如今看来异常简单的程序，学生花了6周的时间才得以完成。当时也没有任何人想到，这是现代公钥密码学的奠基人罗纳德·李维斯特第一次与计算机结缘。
在彼时，电脑还是只有国家和大型机构才能维护的巨型机器，因此虽然罗纳德对计算机有着一定兴趣，但在本科期间还是学习了当时看来更加传统的数学。然而，随着1970年前后个人电脑的诞生以及互联网雏形的出现，越来越多有意思的计算机问题急需人们解决。因此当罗纳德数学本科毕业后，他就前往斯坦福大学攻读计算机专业博士，并之后专注于理论计算机科学方面的研究。在计算机的众多问题之中，他尤其对密码学和计算机安全感兴趣。
其实早在计算机发明之前，密码学就已经是各国重点研究的领域，尤其是在战时信息传递方面发挥着重要作用。当时的信息加密方法都是如今所谓的对称加密算法，即通信双方首先必须商定好一组秘钥，然后当需要通信时，一方使用这个秘钥加密，而另一方同样用这个秘钥解密。这样，就算有敌人能窃听到加密内容，没有秘钥的话也无法解出明文中的内容。然而，只要有一方的秘钥被泄露，那么任何采用这个秘钥加密的信息就将能被破译。因此在两次世界大战中，破解敌方秘钥都是各国情报部门的重点任务之一。
然而，随着互联网的出现，人们逐渐发现了对称加密方法的局限性。首先，对称加密的通讯双方在通讯之前需要先透过另一个安全的渠道交换共用的密钥，才可以安全地把密文透过不安全的渠道传送。思考一下，如果两个现实中没有见过的人想通过互联网建立一个秘密交流通道，那么他们首先需要在网上确定一组秘钥，而这个过程就可能会被其他人窃听到并盗取秘钥。其次，如果仍然想保证网络信息的安全性，那么每对用户在使用对称加密算法时，都需要使用其他人不知道的独一秘钥，这会使得收、发双方所拥有的钥匙数量巨大，密钥管理成为双方的负担。
这些问题自然也是作为理论计算机科学家的罗纳德教授想要解决的问题范畴。因此当某一天，他的一位硕士生拿着 Diffie-Hellman 提出公钥密码学设想的论文跟他说：“嘿，罗纳德教授，你可能会觉得这个设想很有趣”时，他马上发掘这个想法的潜力，并叫来自己的好朋友阿迪（Adi Shamir）和伦纳德（Leonard M. Adleman）一起实现这种加密算法，即我们今天所熟知的 RSA 算法。^[3]
RSA算法的三位创始人
那么，究竟什么是所谓的公钥密码学呢？与之前提到的对称加密不同，公钥密码学中，一个人需要构造他自己的一组公钥和私钥。其中，公钥顾名思义，是可以公开给所有人的信息，而私钥需要拥有者自己好好保管。这组公私钥对需要满足以下条件：使用私钥可以解密使用公钥加密的信息，同时使用公钥也可以解密用私钥加密的信息。同时，不使用对应秘钥的敌人无法伪造正常信息。
听起来这比对称加密要复杂很多，这是因为它同时满足了加密通信和数字签名这两个功能。为了方便理解，我们先来想之前对称加密无法解决的问题。假设网络上两个人 Alice 和 Bob 互相不认识，他们应该怎样构造加密通道并实现安全传输呢？使用公钥加密可以这样做：
- Alice 和 Bob 生成自己的公私钥对（, ） 和 （, ）。
- Alice 和 Bob 交换公钥，即 Alice 获得了，Bob 获得了。
- 当 Alice 想给 Bob 发加密消息 时，Alice 使用加密 并发送给 Bob。
- Bob 收到加密后的信息，用自己的私钥解密，得到 。
- 反之，当 Bob 想给 Alice 发消息时，同理使用 Alice 的公钥加密即可。
可以看到，在这个过程中，哪怕有人截获加密后的密文，由于他只知道公钥而不知道私钥，他也无法解出对应的明文。因此，通过神奇的公钥密码学，两个相隔万里的人也能够在互联网上安全地传输信息。
公钥密码学另一个重要功能就是数字签名。数字签名的概念就像我们手写的签名一样，是证明发信人身份的一个标志。在现实中，由于每个人的书写习惯不同，因此用一个信息的书写习惯就可以判断信息出自哪个人之手。同理在互联网中，当人们发送一个公开信息，并使用自己的私钥加密这段信息，作为数字签名也公开时，由于所有人都能用他的公钥解密签名，因此就能确认发信人的身份。同时，由于没有秘钥的人一定无法伪造信息，那么就像手写签名一样，别人也是无法伪造数字签名的。
以上就是公钥密码学的两大重要用途，其已经被广泛用于信用卡支付、电子邮件、互联网通信协议等多个领域，涉及互联网使用的方方面面。而罗纳德及他的合作者正是第一个真正实现公钥加密算法的开创者。以他们三人首字母命名的 RSA 算法，以如下巧妙的方式来构造人们的公私钥对：
- 随意选择两个不相等的大素数 和，计算 。
- 根据欧拉公式，计算 。
- 选择一个小于且与互质的整数，并求出关于的模的逆元，记作（即）。
- 销毁和 将作为公钥，()作为私钥。
现在假设我们要加密消息并传给私钥拥有者，那么密文即是。复原消息的方法为 。
罗纳德这一巧妙的构造建立在大整数分解困难性的假设上，创建了现实中的第一个可用的公钥加密方法。该方法如今仍应用在 HTTPS 传输领域，为我们每天的生活提供着便利。
参考资料
[1] https://en.wikipedia.org/wiki/Ron_Rivest
[2] https://amturing.acm.org/award_winners/rivest_1403005.cfm
[3] https://www.youtube.com/watch?v=gQJmqQrcazU
文字 | 李济宸
图片 | 除标注外源自网络
