算法研究与密码学

罗纳德·里维斯特(Ronald L. Rivest)是长期在麻省理工学院从事研究的计算机科学家。1969年,他取得耶鲁大学数学学士学位;1974年在斯坦福大学获得计算机科学博士学位,导师为罗伯特·弗洛伊德。他的研究横跨密码学、网络安全和算法,并非只限于一个以姓名缩写命名的方案。

里维斯特与阿迪·沙米尔、伦纳德·阿德尔曼因公开密钥密码学贡献共同获得2002年度图灵奖。他也是《算法导论》的合著者之一;该教材工作与密码方案的共同发明是不同性质的贡献,涉及不同的合作者。

参考:[1]

RSA如何分离公开与秘密

三人于1978年发表RSA论文,给出可用于公钥加密和数字签名的具体构造。它选取两个大素数,将乘积作为模数公开,再安排一对具有特定模逆关系的指数。公开指数可用于一个方向的运算,秘密指数用于相应的反向运算;合法使用者不必把秘密指数交给通信对象。

若攻击者能够分解模数,便能利用两个素数恢复计算秘密指数所需的信息,因此整数分解是理解RSA安全性的关键。但“分解能够破解”不等于“任何破解都必然实现分解”,原论文也没有证明这种普遍等价。

RSA是三名作者的共同成果,不能把它归给缩写中排在首位的人。原始的模幂公式解释了公钥与私钥的关系,却不是可以不加处理地用于所有实际通信的完整安全协议。

参考:[2]

消息摘要的设计及安全边界

里维斯特还设计了MD5。1992年的RFC 1321将它说明为把任意长度消息映射为128位摘要的算法,目标之一是先压缩较长消息,再配合数字签名使用。摘要不是保存原文的加密副本,计算摘要也不是用公钥加密消息。MD5在MD4基础上作出调整,以较慢的计算换取当时认为更稳健的设计。

算法的历史地位不能代替后续安全评估。2011年的RFC 6151指出,MD5不再适合要求抗碰撞性的用途,尤其不能继续依赖它保护数字签名。所谓碰撞,是找到两个不同输入产生同一摘要;这不同于从任意摘要恢复原文,也不表示RSA等其他算法随之全部失效。该文还把普通MD5与HMAC-MD5分别讨论,体现了安全结论必须对应具体构造和用途。

参考:[3] [4]

从计算公式到可核验的系统

在投票安全方面,里维斯特参与麻省理工学院与加州理工学院的投票技术研究,曾在美国投票技术指南制定工作中负责安全与透明度相关事务。他也参与Scantegrity研究,以及风险限制审计、贝叶斯审计等选后统计核查工作。

这些方向把问题从“密码计算是否困难”扩展到“系统结果如何被检查”。投票设备、协议和审计方法各自承担不同环节,不能仅凭采用某种密码算法就宣称整个选举系统可靠。里维斯特的研究经历因而同时包含数学构造、算法分析和可验证制度工具。

参考:[1]