|
引言 “强加密”是个被广泛使用的术语，但不同的人对它有不同的理解，这一点毫不奇怪。颇具代表性的是，人们常把它理解为“不可破译的加密”，这种看法具有更多的主观性。 多年以来，人们就知道一次填充密码是唯一一种本质上不可破译的密码。克劳德·香农（Claude Shannon）在1948和1949年发表的两篇学术报告中证明了这个论断。这两篇报告是现代包括密码学在内的通信理论的基础。可以说香农的贡献意义巨大，给予多高的评价都不为过。 我们已经看到，对大多数实用系统而言，使用一次填充密码并不可行。因此，大多数系统都使用了理论上可以破译的算法。当然，这并不意味着它们一定不安全。例如，如果对这类算法的所有理论上可能的攻击实施起来都太难，那么使用者就可以认为这类算法事实上是不可破译的。即便情况不是这样，在某些特定的应用中，很可能破译算法所需的资源大大超过了攻击者从破译中获得的潜在收益的价值。对于这种特定的应用情况，该算法仍能被看作是“足够安全”的。例如，假设某人要利用加密手段对某些资料实施保密，那么他必须尝试对这些资料的价值作出评估。这个过程可能并不简单。资料的价值可能不是金钱上的，而纯属个人隐私。这些无法给出定量价值评估的资料有很多显而易见的例子，比如医疗记录或其他个人详细资料。对于哪些人希望得到这些资料及其理由，也必须作出某种评估。其他需要考虑的重要因素有：这些资料需要保密的时间，还有花费、有效性、使用算法的便利性等。 当把密码术整合到某个安全解决方案中时，存在两种似乎互相冲突的选取加密算法的思路： ● 使用能提供足够保护的、安全水平最低的加密算法； ● 使用实施条件所允许的、安全水平最高的加密算法。 很清楚，对于实施者来说，很重要的一点是对算法所能提供的安全水平有很好的认识。这就是本章后面几节要讨论的内容。讨论将主要关注对称算法的密钥穷举搜索法，以及针对公钥系统所用的数学方法的攻击。当然，正如我们已经强调过的，密钥穷举搜索的时间只是给出了算法强度的上限，可能还存在其他更容易实施的攻击法。然而，我们相信算法设计已足够先进，出现了大量设计精良的加密算法，使得密钥穷举搜索法代表了最简单的攻击方式。此外，这些算法操作起来很可能还非常快。 过去，实施条件的限制常常迫使用户采纳他们能够使用的最低安全水平的措施。当先进技术赶超在前，能破译他们的密码系统时，常常带来灾难性的后果。 现实的安全性 香农曾证明：本质上说，一次填充密码是唯一的完全安全的密码系统。所以我们知道至少在理论上，大多数实际的系统都是可以破译的。这并非意味着大多数实际系统都毫无用处。一个（理论上可以破译的）密码系统也是具有实用性的，只要使用者确信攻击者不会在所涉项目的掩蔽时间内成功破译该系统即可。 我们讨论过的密钥穷举搜索法是一种基本的攻击形式。在断定一个系统是否适用于某个特定的项目之前，预期密钥穷举搜索所需的时间要比掩蔽时间长得多，这是该系统必须迈过的一道“坎儿”。当然，我们已经知道，具有大量的密钥还不能保证系统的安全；因此，这个要求只能算是判断系统可否被接受的许多检验中的第一个标准。无论如何，如果连这第一步都不能通过，那很清楚该算法是不能用的。所以我们对密码系统的第一步“检验”就是尝试确定密钥穷举搜索所需时间是否足够长，换句话说，就是密钥的数量是否足够多。 为此，设计师需要对攻击者的可用资源和能力作一些假设。他们的首要任务是估计攻击者每试算一个密钥所需的时间。很清楚，这个时间与攻击者使用的是硬件还是软件有关。如果是硬件攻击，攻击者可能会使用特意建造的设备。若对这个时间估计过低，将会导致不安全性，而过高的估计又会使安全系统的花费大大超出实际所需。 幸运的攻击者在尝试密钥穷举搜索法时，可能第一次猜测就试出了密钥。使系统具有大量密钥的作用之一就是减少这种情况出现的概率。另一种极端是，一个倒霉透顶的攻击者一直试到最后一个才找出密钥。实际情形往往是，攻击者并不需要进行全部搜索就能找到密钥。用密钥搜索法找到密钥的预期时间大约接近于完成全部穷举搜索所需时间的一半。 有一点也许值得一提。假如攻击者有足够的资料，那么他们可能会很确信只有一个密钥能把所有已知明文转变为正确的密文。然而在很多情况下，穷举搜索全部完成后也不能确认出唯一正确的密钥，而只是缩小了正确密钥候选者的范围，此时需要更多的资料来作进一步的搜索。 一旦密钥的数目确定下来，密钥穷举搜索所需的时间就可给出安全水平的上界。在很多情形下，设计者的主要目的是努力确保其他类型的攻击成功的预期时间要超过这个上界。这绝不是一项容易的任务。我们已经指出过，时间是评估攻击能否成功的正确度量值。然而进行任何计算所需的时间还依赖于各种变数，诸如攻击者的工作效率、技术及数学能力等。工作效率与攻击者所能支配的财力相关，反过来，这种财力支持在很大程度上又随着攻击成功所能取得的预期利润不同而变化。此外，在某些环境中，像能否有效利用计算机存储装置等其他因素，对攻击者来说也都是十分重要的。考虑到上述种种因素，我们仍然可以肯定地说：如此复杂的判断方式，确实是判定一个给定的系统对某种特定的应用来说是否足够安全的标准手段。 实际的密钥穷举搜索 虽然我们不想引入任何复杂的计算，但也许告诉读者某些事实是有价值的，它们可以让我们对某些情况下密钥的数目有一些“感性”认识。很明显，任何一位商业应用系统的设计者，都会希望他设计的系统在（至少）几年内应是安全的，因此他必须考虑技术进步的影响。这经常要借助于一条相当粗略的经验法则的帮助，该法则就是摩尔定律【1】，它认为在成本不变的情况下，计算能力每18个月增长一倍。 为了对密钥数目大小有感性认识，我们来注意以下事实：一年有31,536,000秒，它大约在224与225之间。如果有人能够每秒钟试算一个密钥，那么他一年可搜索225个密钥。如果他有一台计算机能够每秒试算100万个密钥，那么搜索225个密钥所需要的时间大大少于一分钟。这是一个巨大的变化，虽然看起来十分简单，但它标志着计算机的问世已经影响到系统安全所需的密钥数。在讨论密码算法时，一些作者关注密钥本身的大小，另一些作者关注密钥的数量。我们回忆一下，长度为s的信息有2s个比特模式，它意味着，如果每个可能的比特模式都代表一个密钥，那么说一个系统有s比特长的密钥，等价于说它有2s个密钥。还要注意，如果每一可能的比特模式代表一个密钥，只要在密钥长度上额外加一个比特，其效果则是密钥个数的加倍。 最著名的对称分组密码是数据加密标准（DES）。它发布于1976年，在金融部门得到了广泛的应用。DES有256个密钥，自它首次面世以来，有关它的加密水平是否足够“强”的问题，人们一直争论不休。在1998年，一个名叫电子前沿基金会（EFF）的组织设计并制造了一块专用硬件，用于对DES密钥进行穷举搜索，总造价约达250,000美元，它大概能用5天左右的时间找出一个密钥。尽管EFF没有宣称他们已优化了自己的设计，但该设计已被认为是提供了评价目前这项技术所处状态的标准。粗略地说，就是花250,000美元就能够建造一台机器，它能在一周左右的时间内对256个密钥搜索一遍。由上述事实我们可以推断：通过增加成本或增加密钥数目，并考虑到像摩尔定律那样的影响之后，我们可以在指定花费的条件下，非常粗略地估算出在不久的将来任一时期搜索指定数目的密钥所需的时间。 除了专用硬件之外，现在已经有了其他一些众所周知的穷举搜索的尝试，典型的做法是把基于开放网络的密钥搜索的计算能力累加起来。最有意义的大概要属1999年1月所完成的一次搜索。它将EFF的硬件和互联网上的协作结合起来，参与搜索的有100,000台计算机，用不到一天的时间就找出了56比特的DES密钥。 我们之所以关注DES的密钥搜索，是因为DES是一种受到高度重视的算法。在20世纪70年代中期刚设计出来时，它被认为是很强的。现在，虽只过了25年，但DES的密钥可以在不到一天的时间内被找出来。值得注意的是，无论是现在的DES用户还是DES的设计者都未对近期搜索DES密钥的成功表示惊讶；设计者早就告诫说（1976年），它只能用15年。大多数DES的近期用户现在使用的是称为三重DES的算法，其中的密钥是两个或是三个DES密钥（即其长度为112或168比特）。三重DES如下图所示，用两个DES密钥k1和k2来加密，其中E和D分别表示加密和解密。
有两个密钥的三重DES 为了见识在密钥上额外添加8个比特后的戏剧性效果，我们看一下在1998年初开始的一个对所谓RC5算法的64比特密钥进行的联网搜索。经过超过1,250天对大约占潜在密钥总量44％的密钥的试算，还没有找出那个正确的密钥。 2001年，美国国家标准与技术研究所（NIST）公布了一个新的加密算法，“可用于保护电子数据资料”。它被称为高级加密标准（AES），是从NIST所征集的几个算法中选出来的。征集的要求是让对称分组密码能使用128、192和256比特去加密和解密区组大小为128比特的数据。被选出的这个算法定名为Rijndael，是由两个比利时人琼·达曼（Joan Daemen）和文森特·赖伊曼（Vincent Rijmen）设计的。因为AES使用的最小密钥长度是128比特，它似乎足以抵御基于现有技术的密钥穷举搜索法。 我们已经提到过依据摩尔定律可以对现有技术在今后若干年内的进步给出粗略的估计。但摩尔定律并未考虑到革命性的新技术可能产生的巨大影响。量子计算就属于这类新技术。量子计算利用量子态进行演算，它允许采用平行计算的方式。目前科学家仅制造出很小的量子计算机，因此从本质上说，它还仅是一个理论概念。然而，一旦量子计算机变成现实，形势将发生巨变。现在世界各地都投入了可观的资金，支持量子计算可行性的研究。如果足够精微的量子计算机能制造成功，它将显著地提高密钥穷举搜索的速度。粗略估计它能在给定时间内搜索长度比现在增加一倍的密钥。因此，粗略地说，量子计算机搜索2128个密钥就像现在搜索264个密钥一样快。 研究者对建造量子计算机的可能性持谨慎态度。无论如何，该领域存在着一些乐观的情绪，我们不应忽略其成功的可能性。 对公钥密码系统的攻击 非对称算法的密钥比对称算法的要长。然而，这并不意味着非对称算法就一定比对称算法更强一些。攻击非对称密码，一般不用密钥穷举搜索法。比较容易的办法是去攻击其中所使用的数学问题。例如对RSA，设法找出模N的因子要比对所有可能的解密密钥进行密钥穷举搜索更容易一些。 为了说明最近的数学进步是如何影响了公钥密码术的应用，我们来关注RSA和因子分解。其他公钥系统的情况也类似，只是各自依赖的数学问题不同。 因子分解技术在过去30年间有了惊人的进步。这归功于理论和技术两方面的进步。在1970年，一个39位数（2128＋1）被分解为两个素因子的乘积。这在当时被认为是一个重大的成就。1978年RSA首次发表时，论文中提出了分解一个129位数作为挑战性的问题，奖金为100美元。在这之后出现了一系列这样的挑战。这个数直到1994年才被因子分解成功，而且分解过程中利用了世界范围的计算机网络。 除了摩尔定律，在数学上改进因子分解技术的可能性，也是确定RSA密钥大小所必须考虑的一个因素。我们来看看被称为一般数域筛法（GNFS）的数学革新所引起的巨大影响，该方法发表于1993年。使用以前所知算法分解给定大小的数所耗费的资源，若用于新方法中可以分解大得多的数。例如，分解150位数这一等级的数所需的资源，现在可以用来分解接近180位的数。这个数学方面的进展比人们对纯粹的技术进步的预想领先了好几年。 1999年，有155位的挑战性数字RSA-512的因子分解就是用这种技术完成的。这次因子分解费时不到8个月，而且又一次利用了世界各地的计算机联网作业。这个数学问题复杂性的一个表现就是在工作的最后阶段要解方程数超过600万的联立方程组。在它之后，《码书》中又提出了一个挑战，要求分解一个512比特的模。这些因子分解意义重大，因为这样大小（155位的数，或512比特的数）的模是几年前公钥密码术中常用的。 对于RSA算法，现在一般推荐使用从640到2,048比特的模，具体采用多大的模依安全性要求的强弱而定。一个2,048比特的数在十进制数系中有617位。为了显示这个数有多大，我们列出有617位的RSA挑战性数字。第一个能成功分解它的团队将获得荣誉和200,000美元的奖金。
在讨论密钥穷举搜索时，我们提到过量子计算机的潜在影响。虽然它会引起对称密钥长度的极大增加，但毫无疑问的是密码界会适应它的存在，并能继续安全地使用对称算法。但对公钥密码而言就未必如此了。量子计算对公钥系统来说是个更为严重的威胁，例如因子分解会变得非常容易。幸运的是，即使是最乐观的量子计算的狂热派，他们也预言至少20年内不会出现大型的量子计算机。（弗雷德·派珀） 注释 【1】 摩尔定律（Moore's law），又译“莫尔定律”。 |
|
|
