曹珍富博士报告会：密码学与信息安全(3)

    
    关于现代密码的几项标志性工作是这样的。首先是1978年RSA方案的提出，这是R、S、A作为姓氏打头字母的三个人提出的，大家知道他们三人今年刚刚获得了计算机领域的最高奖，图灵奖。他们因为这样一项重要的成就而获奖，这个成就我们把它列在下面，很简单。就是选择两个大素数p，q，然后乘起来叫做N = pq，计算一下N的欧拉函数，比如说用t来表示，再计算e，d满足ed = 1(mod t)，e是加密指数，d是解密指数，加密是计算信息m的e次方，即计算y = m^e(mod N)，其中信息m不妨设为m < N；解密就是计算y的d次方，即计算y^d = m(mod N)。这个工作看起来很简单，它仅仅用到非常基本的知识，但是这项工作的意义很大，二十多年来一直广泛的被使用，虽然它的安全性最近也受到了考验，很多情形已经不安全。1979年Shamir提出秘密共享算法，就是门限方案，他把秘密D分成n个秘密碎片D_1, …, D_n，其中知道任意k个碎片都可以很容易的恢复D，用熵（度量不确定性）函数H来表示，值为零，即任意知道k个碎片时D的不确定性为零，也就是说D被完全确定。任意知道少于k个秘密碎片，就如同一个秘密碎片不知道时是一样的，也就是说秘密D是完全不确定的，这就是秘密共享方案，或者叫门限方案。Shamir给出了这个方案用有限域上线性方程组来实现的一种方法。1982年也是一个重要的概念，是Goldwasser、Micali提出了概率加密算法，每一位安全性都得到了证明，同时又证明基于二次剩余假设，所以安全性还等价于大整数分解；二次剩余假设是：已知A和N，由X^2 = A (mod N)求出所有的X，即求模N的所有平方根问题，是一个很难的问题。基于这样的假设，可以做出一系列的密码方案，他们的概率加密方案在下面。就是除了选择两个大素数p，q，计算N = pq以外，还选择一个s，选择这个s使得s对N的Jacobi符号是1，但s是mod N的二次非剩余。于是s, N是Goldwasser-Micali概率加密系统的公开密钥，p，q是系统的秘密密钥。明文是二进制形式，设为m = m_1…m_n，每个m_i = 0或1，则密文为E_1…E_n，这里E_i等于B_i的平方mod N，如果m_i是0的话；如果m_i是1的话，就等于s乘以B_i的平方mod N，这里B_i是任选的n个随机数。从密文产生的过程中可以看出，解密是很简单的，只需要计算E_i 是mod N的二次剩余还是二次非剩余。这个密码系统也有一个致命的弱点，就是密文扩展太大。为了实现这种方案，就需要对它进行研究，比如说递归实现等等。我们这里仅仅提出概念。1982年Shamir利用LLL—算法攻破了Merkle-Hellman一次背包密码算法，后来一般的低密度一次背包密码都可攻破，即凡是密度小于0.645的一次背包都可以攻破，这是背包密码后来很少有人再去做的原因。但近年来还是有人继续研究背包密码。1986年Goldwasser，Micali等提出了零知识证明协议，并基于二次剩余假设提出了一个具体的零知识证明协议，零知识证明协议包含证明者P和验证者V两方，假设P得到了一个定理，刚才我已经在前面解释过，P宣布了比如说他有大整数的有效分解方法，他要让验证者V相信他确实有大整数的有效分解方法，但P又不想泄漏有关分解方法的任何信息给验证者V，验证的方法如下：V随便选择一个大整数，比如说N等于pq，是两个4k+3型的大素数的乘积（这个选择可以是任何用户的RSA公钥中的大整数N），为了能够证明P具有分解N的能力，V首先选择X计算它模N的四次方，余数叫做Y，即计算Y满足Y = X^4 (mod N)。V将Y交给P，并要求P计算出X模N的平方，就是算出Y模N的平方根。已经证明算出Y模N的平方根，而且还要从所有平方根中选出唯一的模N的二次剩余的那个，是等价于大整数N的分解的。所以只要P具有分解N的能力，就必然能有效的算出Y模N的平方根。验证者这个过程是可以多次重复的。因为如果就一次的话，可能P的机遇很好，有可能碰出，但经过这样多次的实验，P的运气好的概率是很小的，几乎就是零。在这个过程中，P没有告诉V他的大整数具体分解的方法，也没有告诉V大整数被分解的结果。
    这里列出了以后新的发展和新的概念，比如说1990年门限密码学提出，另外1990年又提出差分攻击，1993年提出了线性攻击，这两种攻击都是针对对称密码算法；1993年美国政府宣布了托管加密标准，这个标准在1994年2月份政府采用，这个标准在国际上引起了很多的争议，比如说两个用户之间通信他们是合法的通信，你如果也去监听的话，你怀疑他做了非法交易去监听，就侵犯了人家的隐私权，在美国非常讲究人权的国家，他这样做引起了很多的议论和争议。1996年有一个新的概念提出，就是代理签名，一个公司的总经理，他因为有事出差，不能完成公司的签名，或者是公司很忙，不能出差去外地完成某个签名，这些情况下他都要找一个人做他的代理，这个代理人来帮他完成他的签字。传统来说把他的印章带去就可以，但是在网上完成这个过程就需要提出具体的代理签名方案。在2000年10月份，美国国家标准和技术协会通过在全球广泛征集公布了新的加密标准，就是AES，这么做的原因主要是由于它以前的数据加密标准DES不安全了，现在使用这样一个新的加密标准，就是AES；详细内容不再介绍了。