算法传奇 数学之美
2015-09-01
任何科学思想或理论的诞生都有它的背景，其中也往往伴随着有很多迷人的故事。
一、密码学就是数学理论的不断完善的过程
1900年，德国数学家大卫•希尔伯特(David Hilbert)在巴黎举行的第二届国际数学家大会上，作了题为《数学问题》的演讲，提出了23道最重要的数学问题。
其中第10个问题是这样的：“是否存在一种有限的、机械的步骤能够判断’丢番图方程’是否可解？”而他提到到“丢番图方程”的名字，则是来源于公元200年到300之间的希腊数学家丢番图，后者曾提出这些方程并进行研究但没有找到答案。这个关于证明步骤的定义，用今天的话说就是算法。
1936年，艾伦•麦席森•图灵(就是电影《模仿游戏》的主角)在他的重要论文《论可计算数及其在判定问题上的应用》里，提出了“图灵机”的一种设备，证明了这样的机器有能力解决任何可想像的数学难题。尽管没有一台图灵机会有实际用途，但这却是现代密码学的核心思想，也是密码算法的直观形象和精确定义。
随着时间的推移，很多认为不可破解的密码都一一被破译，例如著名的“维吉尼亚密码”在早期被称其是不可破译的。但后来于19世纪完全破解；二战时期的ENIGMA密码机当初也认为是不可破解的，但后来也被图灵带领的团队破解了。那是否存在不可破解的密码呢？相信很多人都会说不存在，但通过数学理论证明，答案却是肯定存在的。
二、存在理论上不可破解的加密方法吗？
二战时期，美国数学家香农在贝尔实验室，证明了一次性密钥是无法被破译的。香农同时证明了一个无法被破译的密码系统的密钥必须有以下特征：完全随机、不能重复使用、保密；和明文一样长。不满足这些条件的加密方法都可以以暴力攻击法破解。
事实上在我们的实际应用中，这样的条件不能完全满足。但依照这样的理念，现代密码学倡导的是“计算上不可行”。也就是说，即以目前的人力、物力、财力、计算机运算能力、在密钥的有效时间内是无法到达的。
这里面还有几条有趣的原则：
1)公开密钥体系提出：即使公开密码系统的任何细节，只要保护好密匙，它就是安全的。这就是国家密码管理局逐渐公开了SM2/SM3/SM4(还可能公开SM9)这些商密算法的原因。
2)如果密码破解的成本远高于得到的利益，这个机制也是安全的。
索尼开发的PlayStation 3游戏机具有很强大的计算能力，甚至加入美国斯坦福大学的“Folding@home”计划：利用PS3的处理器在闲置的适合来支援该项目科学运算。2009年，著名的LACAL实验室使用200台具备6核协处理器的PS3机器，从2009年的1月13日开始计算112位离散对数的难题，一直运行到7月8日才完成，耗时半年时间。国家SM9算法采用的椭圆曲线算法强度超过这个强度的5000万倍，即使考虑到CPU的摩尔定律运算能力不断翻番，如使用现在100台高性能电脑运算，则大约需要运算150万年！如按照亚马逊云2015年价格来计算，需要花费16亿亿亿美元才破解。所以，使用现代密码技术：“再也不担心我的秘密了”！
随着现代密码学的发展，破解已经逐渐变成计算上不可能，于是开始诞生了例如美国CISPA这样的法案，原因很简单：因为不借助法律手段，加密在现有的技术条件下是无法破解的。
三、SM9算法的发展，演绎数学之美
我们已经进入了云计算、移动智能终端的时代。可谁能想到，最适合在云存储、智能终端安全、物联网安全、电子邮件安全这些今天热门话题中使用的加密算法：IBC标识密码算法(即国家商密SM9算法)，却最早确诞生在没有云计算的30多年前。
1984年，以色列科学家AdiShamir提出了基于身份的密码算法理论。2000年左右，基于标识的密码算法有了突破性的进展，研究人员设计了大量的标识密码算法。在2000年，三位日本密码学家提出了使用椭圆曲线上的双线性对设计基于标识的密码系统的思路；在2001年，斯坦福大学的密码学家提出了两个采用双线性对的标识加密算法。在接下来的五、六年间研究人员发表了数千研究基于双线性对的密码算法的论文，提出了大量的新密码技术方案。2006-2008年期间，中国的标识密码算法也得以研制和鉴定，颁发算法型号SM9。
Adi Shamir在1984年的论文结束时候，描述IBC应用的畅想：“每个人都可以用IBC这种新型的个人身份卡来签发电子支票、信用卡、法律文件和电子邮件…”30多年过去了，文中的想法还仅只有电子邮件才慢慢开始实现，现在每个人都可以在互联网上，下载奥联Omail加密程序、奇虎360加密邮程序来实现个人的电子邮件加密，还可以到网络安全宣传周去现场体验国家信息中心的SM9加密邮箱。可见相对电子元件、互联网这些技术的快速发展而言，密码算法的发展只能以慢速来形容。因为数学理论需要随着时间的发展慢慢沉淀，才能演绎出智慧的光芒。