密码学
密码术用于和其他各方交换私密信息，密码学有着悠久的历史，涌现出了丰富多彩的故事。在二战时期就有两个著名案例，1943年，由于日本的军用加密系统不够安全，日本联合舰队总司令山本五十六也丢了性命。美国情报机关得知了山本的飞行计划，因此成功击落了他的座机。据称，尽管没有得到普遍认可，正是由于英国人靠阿兰·图灵的计算技术和专业知识破解了恩尼格玛密码机（见图13.1），解密了德军的军事情报，才使得第二次世界大战结束时间大大提前。密码学的基本思想是，假设Alice和Bob想要交换消息，并且即使对手可以读取交换的消息，也需要保持其内容的私密性。要做到这一点，Alice和Bob需要某种共享的秘密，可以用来加密和解密信息，使这些信息对彼此来说是可理解的，但对其他人来说是不可理解的。这个秘密叫作密钥。对于现代基于计算机的加密系统而言，密钥是一个由一种算法使用的大的秘密数字，该算法利用这个数字把一个几比特的信息进行转换，如果不知道这个保密数字就无法解读。密码系统必须假定攻击者知道并完全理解密码系统的工作原理，从而将所有的安全性都寄托在密钥上。与此相反的做法是假定对手不知道系统用什么加密方案、如何破解，这被称为隐匿式安全(security by obscurity)，即使可以工作，也不会长久。实际上，如果有人鼓吹他们的加密系统十分安全，却不愿说出其工作原理，那就可以确信它并不安全。密钥加密目前使用的加密系统基本可分成两类。一类是历史较长的密钥加密(secret-key cryptography)，也称对称密钥加密，因为加密和解密要使用相同的钥匙。在密钥加密系统中，使用同一个密钥对消息进行加密和解密，这个密钥由希望交换消息的各方共享。假定选用的算法完全为人所理解，而且也没有任何缺陷和弱点，那么破解消息的唯一方法就是蛮力攻击(brute force attack)，即尝试所有可能的密钥，以找出用来加密的那个。蛮力攻击很耗费时间，如果密钥有N位，穷举时间就大约和2的N次方成正比。直到21世纪初，最常用的密钥加密算法是DES（Data Encryption Standard，数据加密标准），该算法由IBM和NSA（National Security Agency，美国国家安全局）于20世纪70年代初共同开发。在任何情况下，DES总是使用56位密钥，随着计算机的运算速度越来越快，56位的长度被证明太短了。到1999年的时候，一台相当便宜的专用计算机，就可以用一天时间使用蛮力攻击破解DES密钥。这导致了具有更长的密钥的新算法的产生。这些算法中使用最多的是AES（Advanced Encryption Standard，高级加密标准），AES支持128、192和256位三种密钥长度，潜在的密钥数量非常多，用蛮力攻击就算很多年也不会有结果，除非能发现该算法的某个弱点。我们可以量化地描述这个问题。如果像GPU这样的专门处理器每秒可以执行1013次运算，那么一百万个GPU每秒可以执行1019次运算，也就是每年大约3×1026次，也就是大约290次。这距离2128还差很远，所以即使是AES-128也应该不会受到蛮力攻击的破解。AES和其他密钥加密系统面临的一个大问题是密钥分发(key distribution)：参与秘密通信的每一方都必须知道所用的密钥，所以必须有绝对安全的渠道把密钥送到通信参与方。这就存在可能没有任何安全可靠的通道来发送密钥。还有一个问题是密钥扩散(key proliferation)：要想和不相关的各方进行独立的秘密对话，就要为每组会话准备不同的密钥。这就导致密钥分发更加困难。公钥加密公钥加密采用了与密钥加密完全不同的思想，是怀特菲尔德·迪菲(Whitfield Diffie)和马丁·赫尔曼(Martin Hellman)于1976年在斯坦福发明的。在公钥加密系统里，每个人都有一个密钥对(key pair)，包含一个公钥和一个私钥。这对密钥是在数学上有关联的整数，具有如下性质：用其中一个密钥加密过的消息只能用另一个密钥解密，反之亦然。在实际使用中，公钥是真正很公开的：任何人都能拿到，一般是公布在网站上；私钥则一定要严格保持私密，是一个只有这个密钥对的主人才知道的秘密。由于不需要传送共享的密钥，这个方案有效解决了密钥分发的问题。最被广泛使用的公钥加密算法称为RSA，这个算法是麻省理工学院的三位计算机科学家罗纳德·李维斯特(Ronald Rivest)、阿迪·沙米尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)在1978年发明的，RSA就是这三位发明人姓氏的首字母缩写。RSA算法的可靠性来自于对大的合数做因式分解的难度。RSA的工作原理是生成一个很大的整数，至少500位长度的十进制数字，这个整数有两个素数因子，每个长度约为二者乘积的一半，以此作为生成公钥和私钥的基础。知道这两个素数因子的人（即私钥的持有者）能迅速解开密文，而其他人要解密就得先分解素因子。由于计算量过大，这实际上是不可能完成的。李维斯特、沙米尔和阿德曼因为发明RSA算法而获得了2002年图灵奖。