ACM通信

ACM通信

技术意见:为新世纪设计密码学

由苏珊·兰道
ACM通信，2000年5月，第43卷第5期，第115-120页
10.1145/332833.332853
评论

密码学曾经是将军和好奇的孩子们的领域，但信息时代的到来改变了这一切。在20世纪70年代早期，国家安全局(NSA)和国家标准局(NBS)意识到，非战斗人员需要保护他们敏感但非机密的信息。虽然美国国家安全局通常是建造密码系统的政府机构，但该机构不愿意设计供公众使用的密码系统。相反，国家统计局发布了一份公开征集密码系统的公告。IBM的回应。该公司提交了一个56位密钥的密码系统。新的算法成为数据加密标准(DES)。

业界和学术界的许多人都对DES持怀疑态度。他们的关注点集中在NSA是否在算法中设置了一个“活板门”(trapdoor)，即解密的捷径。DES的键长也有反对意见;批评者认为相对较短的键长度¹这样国安局就可以读取des加密的通信。(IBM表示，它自己的工程师坚持在寄存器到寄存器的关键数据传输中使用奇偶校验位，因此将密钥长度从原来的64缩短到56。)

在接下来的20年里，关于密码学的争论频繁发生。美国政府利用出口管制和其他法律行动的威胁，试图阻止强密码学的传播。为了建立安全的计算机系统，工业界发现对密码学的出口控制是一个严重的障碍(当然，不是唯一的障碍)。［4］

行业斗争集中在比特上:政府允许出口的产品中有多少比特?根据1992年的协议，这个神奇的数字是40位。DES是56位。除了少数例外，含有DES的产品不能出口。1996年美国国家研究委员会(National Research Council)一份关于密码政策的报告建议立即放松出口管制。直到1998年，由电子前沿基金会(Electronic Frontier Foundation)建造的一台价值25万美元的特殊用途机器在56小时内破解了一条des加密的信息。5］．(后来，通过将10万台联网的个人电脑与EFF的机器结合起来，这一时间被提高到了22小时。)当时，美国放松了出口管制，允许在出口产品中使用DES。近几个月来，出口管制已进一步放松。

回到顶部

一个新的标准

更换DES超时。处理步骤1997年，美国国家标准与技术研究所(NIST)宣布了一场替换算法的竞赛，并举行了公开会议，讨论提出的高级加密标准(AES)的标准。键长是最重要的。1996年的一个特设委员会认为，90位是目前提供20年数据安全所需的最小密钥长度[1］．NIST希望在AES退役后，更安全、更加密的文件应该保持机密。NIST确定了128位的最小密钥长度。²

鉴于政府在输出强密码学方面的不妥协态度，最初的反应是不信任的。其中一个担忧是美国国家安全局在这一过程中所扮演的角色。另一个是外国的参与;毕竟，密码分析专业知识是国际性的。这两种担忧似乎都得到了缓解。虽然NSA对候选人进行了适当的研究，但没有人抱怨它在NIST的评估中所扮演的角色。NIST允许外国参与AES竞赛。

在公共输入之后，NIST确定了直接的要求:算法必须实现对称(秘密)密钥加密，算法必须是块密码，算法必须工作在128位的块上，有三种密钥大小:128位、192位和256位。如果被选中，候选人将必须在非独家的、免版税的基础上在全球范围内可用。评估将涉及安全性、成本和实施灵活性。由于简单性有助于理解、实现和评估候选者的安全性，设计的简单性也很重要。获胜者必须在多种场合工作，包括8位处理器、智能卡、ATM网络、高清电视、语音和卫星通信。在评估程序开始的一年里，NIST将决定五名入选者，一年后，获胜者(或者获胜者snist可能会挑选不止一个)。NIST面临的最大挑战是确定候选人的实力。密码分析是一门年轻的科学，没有一个全面的理论。验证128位对称密钥算法是一次未知的航行。NIST可以使用数学参数和各种度量(例如，候选人的输出与随机排列有多少不可区分)来建立算法的安全性。 But such approaches are only as strong as the imagined attack model. At the end one is left with statements of the form: "We tried, and algorithmX不能用方法攻击吗D，l,或年代这样的做法不会激发信心。。

如果算法使用k-bit密钥，安全性的衡量标准是算法接近2的程度^k-secure，即是否有比强力搜索整个密钥空间更好的方法来破坏系统。(Kerckhoffs在18世纪首次提出的一个假设认为，密码系统的安全性应该完全取决于密钥的保密性，而不是算法的保密性。)有时算法的弱点很明显，但弱点往往需要数年才能发现。有了DES，算法的设计者显然已经知道了一种强大的攻击差分密码分析形式，但1993年发现的线性密码分析似乎是新的。DES至少在理论上确实容易受到这种类型的攻击。

回到顶部

密码系统的设计

对符号块进行加密的最简单技术是替换和换位。替换用另一个符号替换一个符号;换位是对一个块的符号进行排列。密码分析可以被看作是试图通过近似加密函数来确定明文。从这个角度来看，输入和键的线性功能是糟糕的设计选择;这样的函数很容易求解。因此，非线性函数是密码设计的基础。但是密码函数必须是可逆的，计算速度快，密钥大小和内存要求小。所以线性函数起着至关重要的作用。简单运算的适当组合，如XOR(除模2或加模2，有时写为)，替换和排列，产生的密码系统的强度大于其各部分的总和。

这些操作都是DES背后的，它是一个迭代分组密码一种基于符号块的密码系统，它依次重复一个内部函数，称为轮．目前习惯使用操作在中等大小的符号块上的原语加密数据。尽管存在非迭代的块密码(RSA)，迭代是一种自然的处理方式，因为它生成的是具有良好复杂性的小对象(这在硬件中很有用)。

某种形式的自可逆性也是有用的。这使得一个对象(一个芯片，一个软件)可以同时加密和解密。Feistel密码，其中2t位输入被分成t位半l₀，R₀和映射r轮,l_r，R_r，简洁地完成这一点。在我^th一轮，前一轮的右半部分变成了新的左半部分，l_我R_我1，而新的右半R_我是圆子键的函数吗K_我(源自键K)，以及上一轮的两部分，R_我l_我1（R_我1，K_我),是一个任意函数。解密是反向运行的算法，子密钥按相反的顺序使用。DES是一个16轮费斯特密码。

密码系统设计中的一种思想是让技术强烈地指导操作的选择，从而获得高速性能的算法复杂性。国家安全局采取了不同的策略。任何广泛部署的系统都将跨各种硬件和软件系统实现，因此该机构相信“保持简单”，并更喜欢使用基本的原语，如XOR和表查找。与浮点运算等更复杂的操作相反，这些函数的作用方式与系统架构无关。还有无数其他的权衡，其中最基本的可能是那些更容易验证的算法和那些更复杂但更难验证的算法之间的权衡。在一个块结构的密码系统中，这个特殊的问题体现在轮的问题上:应该有很多简单轮还是更少更复杂的轮?即使相对简单的密码系统在运行32轮时也可以是安全的。

系统设计人员通常从一组功能(可能是算法将在其上运行的体系结构或处理器)和一组性能约束开始。虽然密码系统设计应该是一个标准化的过程，就像桥梁建造一样，但事实是，桥梁建造更容易理解。密码系统的目的是在没有密钥的情况下使消息的解密变得极其困难。密码系统的设计有双重目标:确保密码分析是困难的，同时启用算法的安全性认证。这两项任务的复杂性以及对如何实现第二项任务的缺乏知识，通常会导致在设计密码系统时充分考虑到密码分析，而不考虑系统的可认证性。

有些经验法则是标准的。输出位不应该是输入位的线性函数;事实上，输出位元的线性函数不应是输入位元的线性函数[3.］．这并不是说线性函数不能成为密码系统的一部分，而是说该系统必须包含非线性。在块结构算法中，非线性通常是通过使用称为s盒(替换盒)的查找表来实现的。

回到顶部

Cryptanalytic攻击

迄今为止，对块结构算法最严重的攻击是微分和线性密码分析。差分密码分析，首先由以色列研究人员Eli Biham和Adi Shamir公开报道，是一种选择明文攻击，它依赖于一个固定的输入差异可能会产生一个特定的输出差异的想法。通过加密明文对X，X'与规定的位差DX＝XX，然后根据输出的差异来判断哪些关键位是“建议的”，确定关键位。

线性密码分析是由日本密码学家Mitsuru Matsui发现的，它的工作原理是找到明文、密文和密钥位之间的线性关系，这些密钥位揭示了有关密钥的信息。

让B［我)表示我^th数组的位B,B［我₁，我₂、……我_k] =B［我₁］B［我₂］.．.B［我_k),而P，C而且K分别为明文、密文和密钥。从根本上说，一个是寻求形式的关系:P［我₁，我₂、……我_一个］C［j₁，j₂,……j_b] =K［k₁，k₂、……k_c］．

在DES的情况下，微分和线性密码分析都是理论攻击而不是实际攻击。然而，这些都是非常强大的密码分析技术，不容忽视。

没有数学理论可以解释“开箱即用”的攻击。Paul Kocher利用时序和功率分析攻击成功破解了许多安全算法。利用已知的密文攻击，Kocher计时解密，以确定正在使用的操作。这揭示了哪些解密密钥位是“1”。通过这种方法，Kocher找到了Diffie-Hellman密钥交换算法中使用的指数，并将RSA算法中使用的模数因式分解[6］．功率分析攻击依赖于一个非常有效的观察结果，即加密和解密过程中所消耗的功率取决于正在执行的操作和正在处理的数据[7］．Kocher的攻击依赖于实现的物理方面，这不是密码学家之前考虑过的任何模型的一部分。

回到顶部

AES的候选人

AES候选人的截止日期是1998年6月15日。在21个提交的程序中，有15个符合NIST的标准:LOKI97(澳大利亚)、Rijndael(比利时)、CAST-256和DEAL(加拿大)、FROG(哥斯达黎加)、DFC(法国)、Magenta(德国)、E2(日本)、CRYPTON(韩国)、Hasty Pudding Cipher(美国)、MARS、RC6、SAFER+和Twofish(美国)、Serpent(英国、以色列、挪威)。^3.1999年8月，NIST公布了五个决赛项目:MARS、RC6、Rijndael、Serpent和Twofish。这些被广泛接受，还有一些支持e2作为“最佳”提交，NIST报告称NSA称这些是“适当的选择”。今年夏天将决出胜负。

对于获胜者来说，不同的厨师在加密的啤酒中加入了他们自己的配料。例如，最终入围的五个项目包括一个“扩展”费斯特尔网络(MARS)、两个标准费斯特尔网络(RC6、Twofish)、一个替换-排列网络(Serpent)和一个依赖有限场操作构造s盒(Rijndael)的算法。MARS和RC6使用乘法来执行扩散，但是MARS将关键字与数据字相乘，而RC6将关键字与数据的组合相乘。Twofish使用动态构造的“键依赖”s盒。在任何给定的回合中，Serpent实现了一个S-box的并行32个副本。没有其他决赛选手(或候选人)这样做。

回到顶部

AES决赛

我将简要介绍每一个决赛作品，解释它们背后的设计原则。完整的描述，包括实现细节，可以在NIST网站(aes.nist.gov)上找到。

在MARS中，IBM设计人员使用了完善的Feistel网络、乘法提供良好扩散特性的合理想法、所有现代处理器都支持32位数字的乘法的事实以及他们的直觉，即一个密码的顶部和底部轮使用的函数与中间轮不同的算法能够更好地抵抗微分和线性密码分析。

密码系统中的对称(圆函数中的对称，算法的开始和结束都是相同的圆函数)简化了系统的体系结构及其安全性分析。但为了阻止各种类型的攻击，MARS设计者选择让他们的算法是非对称的;后八轮MARS处理单词的顺序与前八轮不同。和中心的16轮，核心不同于第一个和最后八个混合轮。MARS的s盒是使用SHA-1 (SHA-1，安全哈希算法，是联邦信息处理标准)构建的，它应用于某些固定常数，具体来说，是的小数部分的展开而且p．(为了向用户保证算法没有活板门，算法设计者在解释他们对固定参数的选择时非常谨慎。)

搅拌轮使用，旋转，和添加，而核心使用、乘法、依赖数据的旋转和s框查找。MARS的混合轮和核心轮都很复杂，算法的关键调度也很复杂。NIST评论说，MARS的“复杂性使分析在有限的时间内变得困难”[8］．这种复杂性可能不利于火星被选为AES。

RC6是RSA安全系统的20轮费斯特密码，要简单得多。RC6在四个寄存器上运行(A, b, c, d)的32位字。RC6将四个单词成对处理，(A、B), (C, D)，并排列每轮最后一步的对(A, b, c, d) (B c d a)，从而将它们混合:

• B＝B+K₀
• D＝D+K₁
• 为我= 1,r做：

• t= (B×(2B+ 1)) <<< 5
• u= (D×(2D+ 1)) <<< 5
• 一个= ((一个t) < < <u) +K_2我
• C= ((Cu) < < <t) +K_2我＋1
• （一个，B，C，D) = (B，C，D，一个）

在哪里一个<<<b，一个“依赖数据”的旋转，意思是旋转w一些单词一个左边是最小有效对数所给出的量w位的b,一个nd的K_我的子键为圆形。(虽然一开始RC6并不是一个Feistel密码，但在一个回合中，方块上的唯一动作B而且D旋转到块吗一个而且C．因此我们可以建模l= (B，D)，R= (一个，C)和RC6是标准的Feistel网络。)除了美白前和美白后的步骤。增白很简单:用异或键材料输入(或输出)到块算法。这是为了防止攻击者获取明文/密文对。

RC6的主要时间表很简单。RC6的优势在于数据相关的旋转提供了对微分和线性密码分析的阻力，以及二次函数提供的扩散(x)＝x（2x+ 1)。

Twofish是由总部位于美国的密码咨询公司Counterpane Systems提出的，它是一个16轮的Feistel网络，有两个修改。一种是在数据进入整数函数之前和之后的位旋转。另一个改变是基于键的s框。Twofish的设计者相信动态变化的s盒可以增强安全性。

依赖键的s框是不寻常的。虽然随机构造的s盒很容易受到差分密码分析攻击，但DES的s盒被显式构造来抵抗差分密码分析。在Twofish的任何特定实例中，一些与密钥相关的s盒可能是弱的，但s盒是动态构造的这一事实使微分和线性密码分析攻击复杂化。四个s盒是不同的，由满足良好的微分和线性性质的排列构成。

s盒运算之后是矩阵乘法，对2取模的加法³²，密钥位的添加。使用位旋转来阻止依赖于s盒的字节对齐和矩阵乘法的攻击。矩阵乘法使比特扩散。加上mod 2³²提供进一步的混合。Twofish的主要日程安排相对简单。但NIST警告Twofish的整体复杂性“已经引起了一些关注”(参见[8), 53页)。

“蛇”是由来自英国、以色列和丹麦的三位密码学家发明的，是一个保守的设计。一共有32轮——数量很多——每一轮都由XORing键和中间数据、通过s盒和一个结合了固定旋转和XOR的线性函数组成(在最后一轮中，线性函数被键混合操作所取代)。虽然用于生成线性转换的规则显得特别(这里是a <<< 7, an)，它们的作用正如宣传的那样:线性变换增加雪崩。三轮之后，每个明文位影响所有数据位。

每一轮蛇有32个相同的s盒(每个4位到4位)并行应用。这就是蛇的聪明之处。这些位是独立操作的，一个32位处理器灵巧地处理128位的数据段。事实上，每一轮使用32个相同的s盒意味着s盒对位0、1、2、3的作用与对位4、5、6、7的作用相同;位8,9,10,11;等等。因此，位0,1,2,3被输入到处理器的第一个输入端，并通过一系列布尔运算进行运算，同时位4,5,6,7被输入到处理器的第二个输入端，并通过同样的运算集进行运算，以此类推。结果是位0,4，…，输出的124。现在处理器可以计算下一组输出。输入已经输入了。 Again, since the S-boxes are replicated, the same operation is done on all 32 bits of the processor. The outputs are bits 1, 5, ..., 125 of the output. This process is repeated twice more, and thus all 128 bits of output are computed. This is followed by the linear transformation that diffuses the results of the bits. During these operations, the processor is used to its fullest.

s盒是通过一个简单的程序从DES创建的，而Serpent的关键时间表是简单的。该算法的安全性建立在高轮数的基础上，对差分和线性密码分析具有很强的抵抗力。

Rijndael是由两位比利时密码学家开发的，它比其他算法更直接地依赖于代数结构。让女朋友（2⁸)是由不可约多项式定义的有限域x⁸+x⁴+x^3.+x+ 1 /女朋友(2);将128位= 16字节作为字段的元素。的元素组成的4 × 4数组女朋友（2⁸）.

Rijndael有10轮，每轮由4个操作组成:ByteSub, ShiftRow, MixColumn和AddRoundKey(最后一轮跳过MixColumn操作)。s框操作ByteSub将单个字节视为元素女朋友（2⁸)，并首先对它们求倒数(0被发送到0)，然后通过一个仿射函数映射元素。选择ByteSub操作是因为它们对微分和线性密码分析的抵抗力。的元素循环移动我^th数组的行我而MixColumn通过将列的元素视为多项式的系数并执行多项式乘法来扩散列的位。最后，RoundKey用数组元素XORs键。Rijndael的关键调度是使用异或和循环移位的简单展开。

回到顶部

决定获胜者(s)

决赛选手的优点和缺点各不相同。RC6和Rijndael的定义很简单;MARS和Twofish(在较小程度上)的设计使分析复杂化。Serpent在几乎所有平台上都很慢，但该算法有很大的“安全边际”(相对于在算法的减少轮数版本上成功的差分和线性攻击，有很高的轮数)。RC6的安全裕度很低，而MARS的安全裕度很高。

成功的候选人并不完美。所有这些都在智能卡方面存在严重问题，攻击者在加密时对卡片性能的访问受到限制。它们使用乘法和旋转使得MARS和RC6容易受到定时攻击。Twofish也是如此，尽管不如Twofish那么好。但差分功率分析攻击显示出的问题要严重得多。从100个独立块加密中提取美白过程的功率样本，一个流氓智能卡实现泄露了Twofish的所有128位密钥[2］．这并不是由于Twofishall round- 1 AES候选人同样容易受到这种攻击。有办法绕过这种穿透性，但这需要时间和空间的成本，而这两者在智能卡中都不存在。或许智能卡并不是实现国际电子商务安全所需的同样算法的合适场所。一种特殊用途的算法可能会更好。

当国家统计局在1975年提出DES时，电子世界还处于一个初具雏形的状态。很少有人预料到互联网和电子商务的惊人增长。AES是一项雄心勃勃的事业。直到20年前，在密码学领域从事公共工作的研究人员还不到几个。⁴NIST的冒险是基于这样一个想法:自DES神圣化和公钥密码学诞生以来的20多年里，间谍机构以外的密码学专业知识已经发展到可以由公共部门开发出一种保护国际商业和通信的算法。AES是一个有趣的实验，是在如此短的时间内发展起来的公共专业知识的有力背书。

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2000 ACM, Inc。

---

没有发现记录