密码学（Cryptography）是一门古老而年轻的科学，它的起源可以追溯到古罗马时代约公元110年的恺撒（Caesar）加密。然而，直到1949年Claude Elwood Shannon发表了《保密系统的通信理论》这篇划时代的论文，才标志着现代密码学的诞生。经典密码学所使用的密码设计和分析方法不是基于数学推理而是依赖密码学家的直觉和灵感。

凯撒密码盘

《保密系统的通信理论》为对称加密体制建立了理论基础。所谓对称加密体制，即加密和解密密钥是相同的或容易从加密密钥导出解密密钥的密码体制。对称密钥加密可以用来确保在不安全的信道中进行安全的通信，因而它看上去似乎完全解决了密码学的主要问题——秘密通信。然而事实并非如此，任何使用对称加密体制的系统，都隐含着一个假设：通信双方可以使用某种秘密的方式进行初始的密钥共享。显然，这些密钥不能简单地在不安全的通信信道中传送。使用可实现的安全通道，可以初步共享一对密钥，例如使用可信的信使服务。尽管军事和智囊机构是有条件使用这种方法来共享密钥的，但这对于普通人而言却大不可行。据说连接莫斯科和华盛顿的红线电话是“一次一密”加密的，其中的密钥是通过外交官共享的，而外交官需要随身携带着装满填充码的公文包从一个国家飞到另一个国家。另一种更加实用的让通信双方共享密钥的方法是组织一次见面会议，在此会议上产生一个随机的密钥并将密钥的备份分发给各方。

对于具有n个用户的网络，要实现用户两两间的通信需要事先存储n(n-1)/2个密钥。在用户群不大的情形，对称加密系统是有效的。但是对于大型网络，其用户群很大、分布很广，密钥的分配和存储就成了问题。而且，在“开放”的环境下，通信方无法安全地分配密钥，因此对称密钥加密是不充分的。举个例子，在网上购物时需要加密，或者要给国外的同事发邮件（发送者可能从来没有见过收件人），此时仅仅用对称密钥加密是无法解决的。总而言之，基于对称密钥加密的方法不足以解决开放系统中的安全通信问题，因为在这个开放系统中通信方无法见面，或者无法进行短暂的交互。此外，对称加密系统仅能用于对数据加解密处理，提供数据的机密性，不能用于数字签名。因而，人们迫切需要新的密码体制。

对称加密体制

1976年，Whitfield Diffie和Martin Hellman发表了一篇看似天真的题为《密码学的新方向》的文章。这篇文章的影响是巨大的。除了引入一种完全不同的看待密码学的方式外，它还使人们迈出了将密码学引出秘密领域、推入公开领域的第一步。我们引用该论文的前两段如下。

Diffie和Hellman谈到的“革命”并不是夸大其词。1976年以前，密码学家普遍认为若不首先共享密钥就进行加密是不可行的，但是Diffie和Hellman观察到世界上存在一种天然的不对称：那就是某些很容易完成但是反过来却不容易完成的行为。举个直观的例子，打碎玻璃花瓶是很容易的，但是想要从碎片再还原花瓶却是十分困难的。另一个从算法角度出发的例子是，计算两个大素数的乘积很简单，但是从一个积中找出这两个素数却很难，这正是因子分解问题。这种不对称性向人们暗示，可以构造这样一种加密方案：它不依赖于共享密钥，而是依赖于加密很“容易”，但除了指定的接收者以外其他人解密都很困难。更详细地说，一个密码方案存在两个而不是一个密钥：一个是加密密钥，被发送者用来加密信息；另一个是解密密钥，被消息的接收者用来从密文中恢复明文。这种密码方案的存在令人惊讶：即使攻击者知道加密密钥（而不是解密密钥），加密信息的保密性仍然可以受到保护。与之前介绍的对称密钥加密相对应，人们称具有这种属性的加密方案为不对称加密方案或者公钥加密方案。

在公钥加密方案中，加密密钥称为公钥，接收者可以在报纸或者网页上公开其公钥，这样每个人都能发送加密的信息给他，接收者也可以简单地通过邮件将公钥发送给感兴趣的发送方，不用担心窃听通信的攻击者也观察到这个公钥（当然假定敌手不能替换其公钥，即假定在一个公开且经认证的通道上）；解密密钥称为私钥，由接收者维护其保密性。

公钥加密体制

公钥加密的发明的确是密码学的一次革命。在20世纪80年代之前，密码学只是智囊和军队的专利，公钥技术的到来才使密码学传播到大众。公钥加密摆脱了对称密钥加密的局限性：（1）公钥加密可以使得密钥分配在公开的信道中完成，这可以简化系统的首次部署，也可以减少通信方加入或者离开时的系统维护；（2）公钥加密很大程度上减少了需要存储的密钥。即使所有的通信方都希望能安全地通信，他们仅仅需要安全地存储自己的私钥。至于其他通信方的公钥，要么当需要的时候去获取，要么以非安全（可公开读取）的方式存储；（3）公钥加密更适合于公开环境。通信各方没有事先交互，但是能够安全地进行通信，例如商人可以在线发布他的公钥，任何购物者都可以获得这个公钥并用其加密自己的信用信息。

安全的密钥交换有令人惊叹的巧妙之处。它意味着，如果你和你的朋友站在同一个房间的两端，你们可以相互喊叫，产生一对共享的密钥，并且即使其他人听到你们所有的对话内容也无法知道关于密钥的任何事。说到这里，你可能感觉不好区分都能够提供机密性的密钥交换和公钥加密。实际上，密钥交换是一种交互协议，所以要求通信双方同时在线。相比而言，加密通常不是一个交互过程，因此更适合于某些应用程序，例如安全邮件需要加密，但是当邮件发送时接收者不必在线。

值得注意的是，尽管Diffie和Hellman引入了以上三种原语，但他们只提出了密钥交换的一种构造方法。一年以后，Ron Rivest、Adi Shamir以及Len Adleman 提出了RSA问题，并且基于这个问题的困难性首次提出了公钥加密和数字签名方案，这种方案的变体目前依旧是广泛被使用的密码学方案。有趣的是，1985年El Gamal所提出的加密方案仅仅是对Diffie-Hellman密钥交换协议的轻微改动。虽然Diffie和Hellman没有成功地构造出（非交互）公钥加密方案，但是他们的密钥交换协议已经非常接近公钥加密方案了。

Ron Rivest（中）、Adi Shamir（左）与Len Adleman（右）

自公钥密码体制问世以来，密码学学者们提出了很多种公钥加密方案，它们的安全性都是基于底层数学难题的计算困难性。对于某数学难题，如果利用通用算法由公开信息计算出私钥的时间越长，那么基于这一数学难题的公钥加密系统就被认为越安全。目前用来设计安全（不考虑给予敌手量子计算能力）且实用的公钥密码系统的数学困难假设可以分为基于整数分解的假设、离散对数假设和Diffie-Hellman类假设。

接下来，我们详细说说与因子分解问题相关的著名密码学假设及相应的密码体制。

（1）整数分解假设。整数分解问题是一个最基本的数论问题。该问题理论上很容易解决，只需要试除即可，但当整数很大时，实际计算会遇到困难。经过数百年的研究，对于一般的整数分解，人们普遍认为不存在多项式时间（Probabilistic Polynomial Time, PPT）算法，但并不排除对于某些有特殊性质的整数存在高效的分解方法。

大整数的因子分解

 （2）RSA假设。尽管整数分解是一个公认的难解问题，但是直接构造基于这个假设的安全加密方案是不容易的。Rivest等在其著名的文章中提出了一个相关假设（后来被称为RSA假设），并基于此假设构造了RSA加密方案。RSA问题实际上是一个群上的问题，只不过这类群与整数分解关系密切。假设一个正整数N，那么模N的剩余类R = {0, 1, ..., N - 1}关于模N的加法和乘法运算构成一个环。这个环中的所有乘法可逆元，即所有小于N且与N互素的元素全体组成一个乘法群Q；并且在群Q中恰有phi(N)个元素，这里phi是欧拉函数。如果N = pq是两个素数的乘积，那么phi(N) = (p - 1)(q - 1)。在群Q中，每个元素均与x互素，因此由扩展的欧几里得算法可以高效地求出整数y、z使得xy + Nz = 1，即对于任何x可以高效求出其乘法逆元y mod N。

 如果知道N的分解，如N = pq，则容易求出phi(N)为N - (p + q) + 1；如果不知道N的分解，目前还没有求phi(N)的多项式时间算法。实际上，分解整数N = pq与求出的phi(N)难易程度等价。

 定义加密方案的明文空间为Q，得到对应的RSA加密方案。需要注意的是，目前我们只知道RSA加密方案的安全性是基于RSA假设的困难性，以整数分解的困难性为前提，但是没有证明其安全性是基于整数分解假设。

 RSA方案作为第一个公开发表的公钥加密方案，它对密码学发展的影响以及对公钥密码学的贡献都是难以估量的。这个方案也是目前实际应用最为广泛的公钥加密方案，在网络与无线通信中的使用较为普遍。RSA方案的三位作者Rivest、Shamir和Adleman因这项工作荣获计算机科学界最富盛名的图灵奖（2002）。

 （3）判定二次剩余假设。前面我们已经提到，对于难以分解的整数N，乘法群Q的阶数phi(N)是难以计算的。在这类群中，还有一个值得注意的问题：Q中二次剩余类的判定问题。

 著名的Goldwasser-Micali加密方案是基于二次剩余假设判定的困难性。该方案在公钥加密方案发展史上具有重要意义，它是第一个在标准模型下被证明是选择明文攻击（Chosen Plaintext Attack, CPA）安全的方案。这个方案出现的动因源自实际应用，RSA是一种确定性加密，难以满足安全性需求。举例来说，在一个班级进行班干部的选举时，候选人有三个。如果要求每个参选的同学通过网络邮件将自己推举的候选人发给负责人。为了保密，负责人要求用RSA方案的公钥加密该候选人的名字后发送。这时就会发现确定性的RSA方案的缺陷：一个想了解每个人选举内容的敌手，可以事先利用负责人的公钥分别将三个候选人的名字加密。在网络上截取每个人发送的消息，通过简单的密文比对方式，就能够确定每个人推举的候选人是哪一个。因此，密码学家们在设计实用的公钥加密方案时要求该方案的安全标准至少要达到CPA安全。

 （4）计算合数模N的平方根的困难性。在已知N的分解形式的情况下，计算关于合数模N的平方根是简单的，但是在不知道N的分解形式时，计算关于合数模N的平方根则是困难的。

 基于计算合数模的平方根的困难性，Rabin在1979年提出了一个加密方案，它形式上与RSA方案类似。但是由于上述命题成立，Rabin方案的安全性是基于整数分解的困难性的。对于RSA加密而言，目前并不知道是否有类似的结论，而RSA问题有可能比整数分解问题要简单；Goldwasser-Micali加密方案也是如此，在不用分解N的情况下有可能判定模N的二次剩余。事实上，RSA方案比Rabin方案的应用更加广泛，这似乎是由于历史因素而不是技术因素。

（5）判定复合剩余假设。这个假设是与整数分解问题相关的密码学假设，但并不知道是否等同于整数分解假设。Pallier在1999年设计了一个公钥加密方案，该方案中消息不是按比特位加密。与Goldwasser-Micalli加密方案以及可证明安全的Rabin变体方案相比，Paillier加密方案更加高效。更重要的是，Pailler加密方案还拥有很好的同态属性——加法同态性。随着云计算的发展，同态加密适用于解决数据的密态处理，极具应用前景。

公钥密码体制的诞生与发展使密码学从处理军事秘密通信的艺术成为保障全球大众化信息系统安全的技术科学。密码学的现代研究和应用范围随之不断扩大，覆盖比秘密通信多得多的内容，其体制可用来解决数字签名、密钥交换协议、认证协议、电子拍卖、选举和数字现金等诸多安全问题。现代密码学已经无处不在，它还将提速渗透到数字时代的各个角落，严正维护数字时代服务于人的信息、网络与通信安全。

（文中图片均来源于网络）

（中国科学院信息工程研究所 王明生研究员）

来源：阿狗数学AlgoMath