密码的秘密世界

在硬件和软件行业中创建安全环境的竞技场在某种程度上被神秘和误解所笼罩。当然，有些类型的密码是相对简单的。例如，有一种叫做凯撒密码，这是最多产、最简单的加密技术之一。

基本上，这只是将两个字母对齐，并将其中一个字母移动一定数量的位置。在数学上，这可以表示为: ；在发送端，和 在接收方。图1显示了一个简单的密码轮和一个移位示例。所有人需要做的就是正确地对齐轮子并替换字符。

图1:基本密码轮。

最基本的配置只是移动一个字母。在这种情况下，一个字母中的A在另一个字母中就是B。这将把所有内容都向右或向左移动一个字母，这取决于发件人是发件人还是收件人。多年来，这一直是高中学生之间的主要加密方式。

另一个简单的方案，称为Atbash，可以追溯到最初的希伯来字母。这是把字母表中的字母颠倒过来。例如，A变成Z, B变成Y，等等。

在另一端，存在着超级复杂的密码，有些密码非常机密，除了始作俑者之外，没有人真正了解它们。但不太可能有一个候选人被认为是“顶级”人选。在这种规模下，它实际上取决于应用程序，因为有几个元素可以组合起来提供不同的密码功能。但一般来说，涉及AES、RSA或流和块的复杂密码可以变得非常强大和安全。当然，还有QKD，所有不可破解密码的鼻祖。

在所有这一切的表面之下是非常复杂的，无论是发生了什么，还是谁在做这件事。让我们深入研究一下。

谁是密码专家?
Microsemi SoC产品组高级首席产品架构师Richard Newell说:“大多数人不应该尝试开发密码。“要正确破译密码是非常困难的，必须是专家。世界上没有那么多专家。”

Rambus企业解决方案技术副总裁Steven Woo表示同意:“关键的挑战之一是，随着时间的推移，如何开发一种难以破解的密码，以应对不断增长的计算能力。”这是密码开发中一个非常重要的度量。

开发密码不仅仅是编写一些代码来加密数据。“这里的危险在于，当你第一次学习开发密码时，你会倾向于认为它并不那么困难，”纽维尔说。“这会让你误以为自己知道得比实际多。”

在大多数情况下，最终的结果是密码系统的失败。开发者还需要考虑其他指标。

“只要有足够的时间和资源，任何密码都可以被破解，”Woo说。“作为密码开发人员最重要的方面之一是知道如何找到一个甜蜜点，在那里它变得太费力气了，它接近临界点，不值得黑客花费时间和金钱来破解它们，他们就放弃了。了解密钥的构造方式也很重要，这样你就能理解破解密码需要花费的时间和精力。”

从设计的角度来看，设计最优密码需要非常丰富的知识。要成为一流的密码设计师，首先必须成为密码分析方面的专家。密码分析是研究分析密码系统的科学和方法，了解它们是如何工作的，以及如何被破解的。这需要了解如何分析密码算法，了解外围领域，如侧通道攻击是如何工作的。它还需要能够发现算法实现中的弱点，而不仅仅是算法本身。

要知道密码上可能存在哪些类型的数学攻击是非常困难的，这是设计一个好的密码的先决条件。这需要很长时间和大量的知识才能开始从数学的角度理解发生了什么。再加上指标的实用性，成为顶级密码分析人员需要大量的工作和理解。

此外，一个人必须是密码学和密码学方面的专家，密码学是一门整体科学，通常被视为使用密码保护攻击目标(数据)。

有什么新鲜事
当今密码学的两个热门话题是线性和微分密码分析。这些是测量密码中任何类型或数学缺陷的能力，而不可能被对手利用。

“对于目前的加密方法，传统的想法是算法不需要保密，”Woo说。“这是需要保密的钥匙。”

到目前为止，这可能是人们的心态，但在当今巨大的处理能力下，保守关键的秘密可能还不够。“通过监控芯片发出的噪音，你就能推断出密钥的一些信息，因为你知道算法，”Woo说。

这就是微分密码分析和线性密码分析都能起作用的原因之一，也是为什么有了保护算法和密钥的新势头。多轮密码(如DES)的复杂性使得它们很难被破解，即使有人已经获得了某些对应的明文和密文。要确定已使用的相应密钥仍然非常困难。

差分密码分析
这就是差分密码分析发挥作用的地方。假设，通过一些不寻常的情况，获得了与特定的未知密钥相关的大量对应的明文和密文块。使用差分密码分析，分析人员(或黑客)通常可以获得关于未知密钥的一些比特的线索。这大大缩短了获取密钥所需的时间。

图2:差分密码分析过程。来源:theamzingking.com

例如，如果已经运行了两轮DES，现在已知输入和输出，那么确定使用的两个子键就变得相对容易，因为两个f函数的输出都已经实现。这种方法相对简单。

这个技术对我们来说就是一个s盒。每个s盒，有四个可能的输入，将产生已知的输出。在本例中，每个子密钥的长度为48位。然而，密钥本身是56位长。现在它变成了解决问题的锻炼。子密钥被分为8组(每组6位)，问题是确定四种可能性中哪一组(每组6位)为真。

这对于两轮DES非常有效。如果回合数增加到4轮，难度就会增加至少一个数量级。然而，有一个真理，无论运行多少轮，输出仍然取决于输入和密钥。假设回合数有限，并且s -box中没有缺陷，最终会有一些成功，其中一个或多个输出位将与输入位和关键位的组合具有一定的相关性。

在理想情况下，相对于关键位，这种相关性应该是绝对的。这是因为在这个例子中，只有一个键要解。这并不意味着它每次都有效，甚至大多数时候都有效。关于输入和输出位，还有很多对需要测试。

现在，通过增加DES的轮数来推断这一点。显然，输入和输出变量的增加存在非线性关系，因此复杂性也非线性地增加。

在这种情况下，微分密码分析可以采用不同的方法，即找到更微妙的相关性。例如，不是假设一个特定的位在输入端是1——然后根据上面的方法，它在输出端是0或1——而是期望改变位将会或不会改变输出端的位。

差分密码分析可以形成一种模式，即在输入和输出时，哪些位都发生了变化。这个技术就是关于简化。它采用复杂的明文或密文，并寻找表现为更简单的近似的异常。基本原理是，无论要分析的密码是什么，都具有这样的特征:如果存在一个常数X，使得给定许多对明文a, B，使得B = a XOR X，如果某个关于密钥的陈述是正确的，对于某个常数Y, E(B,k) = E(a,k) XOR Y将是正确的，其概率略高于随机给出的概率。

简单地说，微分密码分析有能力通过缩小领域到更多的概率可能性来去除一些细节，而不仅仅是暴力破解。

线性密码分析
相比之下，线性密码分析方法不搜索分组密码可能表现为更简单的密码的孤立点。这种方法由三菱的Mitsuru Matsui开发[见参考文献1]，解决了完整的密码。它的方法围绕着试图将分组密码作为一个整体来简化，而不是通过尝试开发一个更简单的完整分组密码的近似。

图3:线性密码分析过程。来源:theamzingking.com

其原理可以比喻为在计算机辅助断层扫描中，通过对物体进行多次一维扫描来生成二维切片。对于大量的明文-密文对，这是可行的。第一个过程是找到一个密钥，可以从简化的密码生成这对密钥。这产生的密钥位很可能具有实际密码的相应密钥位的值。它是这样做的。

与DC一样，这假设对随机明文和相应密文的集合有一定的了解。其基本概念是用一个线性表达式近似地计算密码的某部分操作，该操作使用一个异或(XOR)，用 ．方程的形式为:

X = [X1, X2，…]，Y^j表示输出Y的第j位;= [y1, y2，…]本质上，这个方程表示u个输入位和v个输出位的异或“和”。在线性密码分析中，这个公式可以用来找到可能出现的概率高于或低于正常值的变体。

为什么这样做很有趣。如果你只是随机选择u + v位的值，并将它们代入方程，那么表达式保持不变的概率将是，精确地，1/2。它会无限延伸下去。然而，在线性密码分析中，与1/2概率的偏差是可以利用的表达式。因此，当偏差离1/2的概率越远时，应用线性密码分析的结果就越可识别。

这里有一个例子。让我们假设一个给定的方程将产生一个1，概率略高于1/2。然后，对于给定的密钥XOR-ing，运行大量的明文和相应的密文，将产生的结果将是1，略多于0。这就是上一段所讨论的偏差。一旦为每对获取了足够数量的明文/密文对，则方程是明文、密文和密钥中每个部分的异或。因为对于每一对明文和密文都是已知的，所以方程将产生少数关键位的异或值。为什么这是有效的，因为方程是“正确的”，只是它是工作的比例，所以有了足够多的对，一个模式开始出现作为大多数，它可以用一个很大的概率，它是一个关键。如果这个过程重复了足够多的次数，理论上，所有的关键位都应该能够确定。

底线
这两种方法都是有效的密码方法。但是，只要略读设计和逆向工程所需的各种密码的表面，就会显示出在这个领域处于领先地位是多么具有挑战性。

要成为一名顶尖的密码分析师，你必须既是设计师又是攻击者。一个人还必须了解高级和复杂的数学，如微分和线性分析等，才能建立和拆除密码。此外，还必须了解当前使用的无数密码，如RSA、AES、SHA、ECC及其所有细微差别。

世界上大多数人对密码分析的复杂性一无所知。有些人认为他们有，这就是为什么今天密码学有这么多失败的原因。但最终那些需要密码学的人将转向真正的专家——尤其是当物联网世界真正开始发展的时候。

术语表
AES -高级加密标准
DES -数据加密标准
DC -差分密码分析
椭圆曲线密码
线性密码分析
量子密钥分发
RSA-它的创建者Ron Rivest, Adi Shamir和Leonard Adleman的姓氏的首字母
SHA -安全哈希算法
异或-一种数字逻辑门，有两个或多个输入，一个输出执行分离。异或门的输出只有当它的一个输入为真时才为真，而不是两个输入都为真

参考文献1:M. Matsui，“DES密码的线性密码分析方法”，密码学进展，EUROCRYPT ' 93(计算机科学讲座笔记no.;765)， Springer-Verlag，页386-397,1994。