1. 密码学专题 - 基础知识

作者: furnace | 来源:发表于2020-05-10 11:05 被阅读0次

密码学专题 - 基础知识

1. 基础知识

1.1 术语

1.1.1 发送者和接收者

假设发送者 (sender) 想发送消息给接收者 (receiver)，并且想安全地发送消息：她想确信窃听者不能阅读发送的消息。

1.1.2 消息和加密

消息 (message) 称为明文 (plaintext)。用某种方法伪装消息以隐藏它的内容的过程称为加密 (encryption)，被加密的消息称为密文 (ciphertext)，而把密文转变为明文的过程称为解密 (decryption)。图 1-1 表明了这个过程。

加密和解密.jpg

使消息保密的技术和科学叫做密码编码学 (cryptography)，从事此行的人叫做密码编码者 (cryptographer)，密码分析者 (cryptoanalyst) 是从事密码分析者的专业人员，密码分析学 (cryptanalysis) 就是破译密文的科学和技术，即揭穿伪装。密码学 (cryptology) 作为数学的一个分支，包括密码编码学和密码分析学两部分，精于此道的人称为密码学家 (cryptologist)，现代的密码学家通常也是理论数学家。

明文用 M 或 P 表示，它可能是位序列、文本文件、位图、数字化的语音序列或数字化的视频图像等。对于计算机，M 指简单的二进制数据。明文可被传送或存储，无论哪种情况，M 指待加密的消息。

密文用 C 表示，它也是二进制数据，有时和 M 一样大，有时比 M 大 (通过压缩和加密的结合， C 有可能比 P 小。仅通过加密通常做不到这点)。加密函数 E 作用于 M 得到密文 C，可用数学公式表示：
$E(M) = C$

相反地，解密函数 D 作用于 C 产生 M：
$D(C) = M$

先加密后再解密，原始的明文将恢复，故下面的等式必须成立：
$D(E(M)) = M$

1.1.3 鉴别、完整性和抗抵赖

除了提供机密性外，密码学通常还有其他的作用：

鉴别 (authentication)：消息的接收者应该能够确认消息的来源；入侵者不可能伪装成他人。
完整性 (integrity)：消息的接收者应该能够验证在传送过程中消息没有被修改；入侵者不可能用假消息代替合法消息。
抗抵赖 (nonrepudiation)：发送者事后不可能虚假地否认他发送的消息。

这些功能是通过计算机进行社会交流到头重要的需求，就像面对面交流一样。某人是否就是他说的人；某人的身份证明文件 (驾驶执照、学历或者护照) 是否有效；声称从某人那里来的文件是否确实从那个人那里来的；这些事情都是通过鉴别、完整性和抗抵赖来实现的。

1.1.4 算法和密钥

密码算法 (cryptographic algorithm) 也叫做密码 (cipher)，是用于加密和解密的数学函数 (通常情况下，有两个相关的函数；一个用作加密，另一个用作解密)。

如果算法的保密性是基于保持算法的秘密，这种算法称为受限制的 (restricted) 算法。受限制的算法具有历史意义，但按现在的标准，它们的保密性已远远不够。大的或经常变换的用户组织不能使用它们，因为如果有一个用户离开这个组织，其他的用户就必须改换另外不同的算法。如果有人无意泄露了这个秘密，所有人都必须改变他们的算法。

更糟的是，受限制的密码算法不可能进行质量控制或标准化。每个用户组织必须有他们自己的唯一算法。这样的组织不可能采用流行的硬件或软件产品，因为窃听者可以买到这些流行产品并学习算法，于是用户不得不自己编写算法并予以实现，如果这个组织中没有好的密码学家，那么他们就无法知道他们是否拥有安全的算法。

尽管有这些主要缺陷，但受限制的算法对低密级的应用来说还是很流行的，用户或者没有认识到或者不在乎他们系统中存在的问题。

现代密码学用密钥 (key) 解决了这个问题，密钥用 K 表示。 K 可以是很多数值里的任意值。密钥 K 的可能取值范围叫做密钥空间 (keyspace)。加密和解密运算都使用这个密钥 (即运算都依赖于密钥，并用 K 作为下标表示)，这样，加/解密函数现在变成：
$E_k(M) = C$

$D_k(C) = M$

这些函数具有下面的特性 (见图 1-2)：
$D_k(E_k(M)) = M$

使用一个密钥的加解密.jpg

有些算法使用不同的加密密钥和解密密钥 (见图 1-3)，也就是说，加密密钥 $K_1$ 与相应的解密密钥 $K_2$ 不同，在这种情况下：
$E_{K_1}(M) = C$

$D_{K_2}(C) = M$

$D_{K_2}(E_{K_1}(M)) = M$

所有这些算法的安全性都基于密钥的安全性，而不是基于算法细节的安全性。这就意味着算法可以公开，可以被分析。可以大量生产使用算法的产品。即使偷听者知道你的算法也没有关系。如果他不知道你使用的具体密钥，他就不可能阅读你的消息。

使用两个密钥的加密解密.jpg

密码系统 (cryptosystem) 由算法以及所有可能的明文、密文和密钥组成。

1.1.5 对称算法

基于密钥的算法通常有两类：对称算法和公开密钥算法。对称算法 (symmetric algorithm) 有时又叫做传统密码算法，就是加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加密/解密密钥是相同的。这些算法也叫做私密密钥算法或单密钥算法，它要求发送者和接收者在安全通信之前，商定一个密钥。对称算法的安全性依赖于密钥，泄露密钥就意味着任何人都能对消息进行加/解密。只要通信需要保密，密钥就必须保密。

对称算法的加密和解密表示为：
$E_k(M) = C$

$D_k(C) = M$

对称算法可分为两类。一次只对明文中的单个位 (有时对字节) 运算的算法称为序列算法 (stream algorithm) 或序列密码 (stream cipher)。另一类算法是对明文的一组位进行运算，这些位组称为分组 (block)，相应的算法称为分组算法 (block algorithm) 或分组密码 (block cipher)。现代计算机密码算法的典型分组长度为 64 位 —— 这个长度大到足以防止分析破译，但又小到足以方便使用 (在计算机出现前，算法普遍地每次只对明文的一个字符运算，可以认为序列密码是对字符序列的运算)。

1.1.6 公开密钥算法

公开密钥算法 (public-key algorithm，也叫做非对称算法) 是这样设计的：用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来 (至少在合理假定的长时间内)。之所以叫做 “公开密钥” 算法，是因为加密密钥能够公开，即陌生者能用加密密钥加密信息，但只有用相应的解密密钥才能解密信息。在这些系统中，加密密钥叫做公开密钥 (public-key，简称公钥)，解密密钥叫做私人密钥 (private-key，简称私钥)。私人密钥有时也叫做秘密密钥。为了避免与对称算法混淆，此处不用秘密密钥这个名字。

用公开密钥 K 加密可表示为：
$E_K(M) = C$

虽然公开密钥和私人密钥不同，但用相应的私人密钥解密可表示为：
$D_K(C) = M$

有时消息用私人密钥加密而用公开密钥解密，这用于数字签名。尽管可能产生混淆，但这些运算可分别表示为：
$E_K(M) = C$

$D_K(C) = M$

1.1.7 密码分析

密码编码学的主要目的是保持明文 (或密钥，或明文和密钥) 的秘密以防止偷听者 (也叫对手、攻击者、截取者、入侵者、敌手或干脆称为敌人) 知晓。这里假设偷听者完全能够截取发送者和接收者之间的通信。

密码分析学是在不知道密钥的情况下，恢复明文的科学。成功的密码分析能恢复消息的明文或密钥。密码分析也可以发现密码体制的弱点，最终得到上述结果 (密钥通过非密码分析方式的丢失叫做泄露 (compromise))。

对密码进行分析的尝试称为攻击 (attack)。荷兰人 A. Kerckhoffs 最早在 19 世纪阐明密码分析的一个基本假设，这个假设就是秘密必须全寓于密钥中。Kerckhoffs 假设密码分析者已有密码算法及其实现的全部详细资料 (当然，可以假设中央情报局 (CIA) 不会把密码算法告诉摩萨德 (Mossad)，但摩萨德也许会通过某种方法推导出来)。在实际的密码分析中并不总是有这些详细信息，不过应该如此假设。如果不能破译算法，即便了解算法如何工作是徒然的。如果连算法的知识都没有，就肯定不可能破译它。

常用的密码分析攻击有四类，当然，每一类都假设密码分析者知道所用的加密算法的全部知识。

Kerckhoff 原则

加密方案的安全性必须仅仅依赖于对密钥 K 的保密，而不依赖于对算法的保密。

1.1.7.1 唯密文攻击 (ciphertext-only attack)

密码分析者有一些消息的密文，这些消息都用相同加密算法加密。密码分析者的任务是恢复尽可能多的明文，或者最好能推算出加密消息的密钥，以便可采用相同的密钥破解其他被加密的消息。

已知： $C_1 = E_K(P_1), C_2 = E_K(P_2), ..., C_i = E_K(P_i)$

推导出： $P_1, P_2, ..., P_i$ ；K 或者找出一个算法从 $C_{i+1} = E_K(P_{i+1})$ 推导出 $P_{i+1}$ 。

唯密文攻击就是大多数人谈到攻破一个加密系统时所指的攻击。这是这样一种情形，Alice 和 Bob 对他们的数据进行了加密，攻击者得到的只有密文。在只知道密文的情况下试图解密一个消息就称为唯密文攻击，这是最困难的一种攻击方式，因为已知的信息量最少。

1.1.7.2 已知明文攻击 (known-plaintext attack)

密码分析者不仅可得到一些消息的密文，而且也知道这些消息的明文。分析者的任务就是用加密信息推出用来加密的密钥或导出一个算法，此算法可以对用相同密钥加密的任何新消息进行解密。

已知： $P_1, C_1 = E_K(P_1), P_2, C_2 = E_K(P_2), ..., P_i, C_i = E_K(P_i)$

推导出：密钥 K，或从 $C_{i+1} = E_K(P_{i+1})$ 推导出 $P_{i+1}$ 的算法。

已知明文攻击是一种同时知道明文和密文的攻击。显然，这种攻击的目标是获得解密密钥。乍一看这好像令人难以置信，如何知道明文呢？实际上，在很多情况下都可以获得通信的明文。有时候一些消息是容易预测的，比如 Alice 在外度假，她的电子邮件自动回复设置为能够给每一封收到的电子邮件回复 “我在度假”，攻击者要以给 Alice 发送一封电子邮件，然后读取答复得到自动回复的具体内容，那么当 Bob 发送一个电子邮件给 Alice 时，也会有同样的自动回复，不过这一次是加密的，现在攻击者就得到了一条消息的密文和明文。如果能够得到密钥，就可以解密 Alice 和 Bob 使用这个密钥交互的其他所有消息。后一部分非常重要，值得重述一遍：通过一些明文-密文对获得密钥，然后使用密钥来解密其他密文。

另外一个典型的例子是，Alice 将同一个消息发送给多个人，包括攻击者，现在攻击者就得到了 Alice 发给其他所有人的明文和密文副本。

还有可能 Alice 和 Bob 正在发送一个新闻稿的草稿给对方，一旦这个新闻稿发布，攻击者就得到了明文及其密文。

即使不知道完整的明文，也经常可以知道它的一部分。电子邮件的开头一般都是可以预测的，或者结尾有一个固定的签名，IP 包的包头也是非常容易预测的，利用这些可预测的数据就可以获得一部分明文，我们把这种攻击也归类为已知明文攻击。

已知明文攻击比唯密文攻击更强大。攻击者可以得到比唯密文攻击中更多的信息，这些额外的信息当然会有帮助。

1.1.7.3 选择明文攻击 (chosen-plaintext attack)

分析者不仅可得到一些消息的密文和相应的明文，而且他们也可选择被加密的明文。这比已知明文攻击更有效，因为密码分析者能选择特定的明文块进行加密，那些块可能产生更多关于密钥的信息。分析者的任务是推出用来加密消息的密钥或导出一个算法，此算法可以对用相同密钥加密的任何新消息进行解密。

已知： $P_1, C_1 = E_K(P_1), P_2, C_2 = E_K(P_2), ..., P_i, C_i = E_K(P_i)$ ，其中 $P_1, P_2, ..., P_i$ 可由密码分析者选择。

推导出：密钥 K，或从 $C_{i+1} = E_K(P_{i+1})$ 推导出 $P_{i+1}$ 的算法。

选择明文攻击比已知明文攻击更强大。现在攻击者可以选择特殊准备的明文，这些明文的选取是为了更易于攻击该系统，攻击者可以选择任意数量的明文，并得到相应的密文。同样，这种攻击在现实中并不是不切实际的，在很多情况下攻击者可以选择被加密的数据。Alice 经常从外界的信息源 (比如，可能受到攻击者影响的信息源) 得到信息，然后以加密形式转发给 Bob。例如，攻击者可以发送一封电子邮件给 Alice，而且他知道 Alice 肯定会转发给 Bob。

选择明文攻击是很合理的，一个好的加密算法应该能够抵抗选择明文攻击。如果有人声称选择明文攻击与他们的系统无关，我们一定要持怀疑态度。

这种攻击有两个变种：一种是离线攻击，攻击者在得到密文之前，要准备好所有想要加密的明文消息；另一种是在线攻击，攻击者可以根据已经得到的密文选择新的明文。大多数情况下两者的区别可以忽略，我们通常也只讨论在线形式的攻击，这是两者中比较强的一个。

1.1.7.4 自适应选择明文攻击 (adaptive-chosen-plaintext attack)

这是选择明文攻击的特殊情况。密码分析者不仅能选择被加密的明文，而且也能基于以前加密的结果修正这个选择在选择明文攻击中，密码分析者还可以选择一大块被加密的明文。而在自适应选择密文攻击中，可选取较小的明文块，然后再基于第一块的结果选择另一个明文块，以此类推。

另外还有至少三类其他的密码分析攻击。

1.1.7.5 选择密文攻击 (chosen-ciphertext attack)

密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文。例如，密码分析者访问一个防窜改的自动解密盒，密码分析者的任务是推出密钥。

已知： $C_1, P_1 = D_K(C_1), C_2, P_2 = E_K(C_2), ..., C_i, P_i = E_K(C_i)$

推导出：K。

这种攻击主要用于公开密钥算法。选择密文攻击有时也可有效地用于对称算法 (有时选择明文攻击和选择密文攻击一起称为选择文本攻击 (chosen-text attack))。

“选择密文” 这个术语其实不太恰当，实际上应该称为 “选择密文和明文攻击”，但是这样显得太长了。在选择明文攻击中，攻击者可以选择明文值；而在选择密文攻击中，攻击者既可以选择明文值也可以选择密文值。对每个选择的明文，攻击者可以得到相应的密文，而且对每一个选择的密文也可以得到相应的明文。

显而易见，选择密文攻击比选择明文攻击更强大，因为攻击者有更多的自由，但是目标仍然是获得密钥，得到密钥之后就可以解密其他密文。再次强调一下，任何合理的加密方案都应该能够抵抗选择密文攻击。

1.1.7.6 选择密钥攻击 (chosen-key attack)

这种攻击并不表示密码分析者能够选择密钥，它只表示密码分析者具有不同密钥之间关系的有关知识。这种方法有点奇特和晦涩，不是很实际。

1.1.7.7 软磨硬泡攻击 (rubber-hose cryptanalysis)

密码分析者威胁、勒索、或者折磨某人，直到他给出密钥为上。行贿有时称为购买密钥攻击 (purchase-key attack)。这些是非常有效的攻击，并且经常是破译算法的最好途径。

1.1.8 算法的安全性

根据被破译的难易程度，不同的密码算法具有不同的安全等级。如果破译算法的代价大于加密数据的价值，那么你可能是安全的。如果破译算法所需要的时间比加密数据保密的时间更长，那么你可能是安全的。如果用单密钥加密的数据量比破译算法需要的数据量少得多，那么你可能是安全的。

我说 “可能”，因为在密码分析中总有新的突破。另一方面，随着时间的推移，大多数数据的价值会越来越小。而数据的价值总是比解除保护它的安全性的代价更小，这点是很重要的。

Lars Knudsen 把破译算法分为不同的类别，安全性的递减顺序为：

全部破译 (total break)。密码分析者找出密钥 K，这样 $D_K(C) = P$ 。
全盘推导 (global deduction)。密码分析者找到一个代替算法 A，在不知道密钥 K 的情况下，等价于 $D_K(C) = P$ 。
实例 (或局部) 推导 (instance (or local) deduction)。密码分析者从截获的密文中找出明文。
信息推导 (information deduction)。密码分析者获得一些有关密钥或明文的信息，这些信息可能是密钥的几位、有关明文格式的信息等。

如果不论密码分析者有多少密文，都没有足够的信息恢复出明文，那么这个算法就是无条件保密的 (unconditionally secure)。事实上，只有一次一密乱码本，才是不可破的 (给出无限多的资源仍然不可破)。所有其他的密码系统在唯密文攻击中都是可破的，只要简单地一个接一个地去尝试每种可能的密钥，并且检查所得明文是否有意义，这种方法叫做蛮力攻击 (brute-force attack)。

密码学更关心在计算上不可破译的密码系统。如果算法用 (现在或将来) 可得到的资源都不能破译，这个算法刚被认为是计算安全的 (computationally secure，有时称做强的)。准确地说，“可用资源” 就是公开数据的分析整理。

可以用不同方式衡量攻击方法的复杂性：

数据复杂性 (data complexity)。用于攻击输入所需要的数据量。
处理复杂性 (processing complexity)。完成攻击所需要的时间，也经常称做工作因素 (work factor)。
存储需求 (storage requirement)。进行攻击所需要的存储量。

作为一个法则，攻击的复杂性取这三个因数的最小值。有些攻击包括这三种复杂性的折中：存储需求越大，攻击可能越快。

复杂性用数量级来表示。如果算法的处理复杂性是 $2^{128}$ ，那么破译这个算法也需要 $2^{128}$ 次运算 (这些运算可能非常复杂和耗时)。假设你有足够的计算速度去完成每秒钟 100 万次运算，并且用 100 万个并行处理器完成这个任务，那么仍需花费 $10^{19}$ 年以上才能找出密钥，那是宇宙年龄的 10 亿倍。

当攻击的复杂性是常数时 (除非一些密码分析者发现更好的密码分析攻击)，就只取决于计算能力了。在过去的半个世纪中，计算能力已得到显著提高，并且没有理由认为这种趋势不会继续。许多密码分析攻击用并行处理机进行计算非常理想：这个任务可分成亿万个子任务，且处理之间不需要相互作用。一种算法在现有技术条件下不可破译就简单地宣称是安全的，未免有些冒险。好的密码系统应该设计成能抵御未来许多年后计算能力的发展。

1.1.9 生日攻击

生日攻击得名于生日悖论。如果一个房间里有 23 个人，那么其中两个人生日相同的概率超过 50%，这个概率大得令人不可思议，因为一共有 365 个可能的生日。如果一个房间里有 41 个人，那么其中两个人生日相同的概率超过 90%。

那什么是生日攻击呢？这种攻击依赖于一个事实：相同的值 (也称为碰撞) 出现得比我们预料的要快得多。在一个保护金融交易的系统中，假设每一笔交易都使用新的 64 位的认证密钥 (为了简单起见，我们假设没有使用加密)，那么一共有 $2^{64}(=18 \times 10^{18})$ 个可能的密钥值，所以这样应该是很难攻破的，对吗？不！在大约 $2^{32}(=4 \times 10^{9})$ 次交易之后，攻击者就可以预料到有两次交易使用了相同的密钥。假设认证的第一条消息总是相同的："Are you ready to receive a transaction?" 那么如果两次交易使用了相同的认证密钥，它们第一条消息的 MAC 值就是相同的，攻击者很容易就可以发现这一点，知道了两次密钥是相同的，攻击者就可以把以前交易中的消息插入正在进行的新交易中，而这些伪造的消息是被正确的密钥认证的，所以会被接受，显然这破坏了金融交易系统。

一般来说，如果一个元素可以取 N 种不同的值，那么随机选择了大约 $\sqrt N$ 个元素之后，就可以预期出现第一次碰撞 (这里我们不考虑计算的细节，但 $\sqrt N$ 是非常接近的)。对于生日悖论来说，N=365，从而 $\sqrt N \approx 19$ ，实际上出现相同生日的概率超过 50% 所需要的人数是 23，但是对于我们来说 $\sqrt N$ 已经十分接近了，而且这也是密码学中常用的近似值。可以这样理解，如果选择 k 个元素，那么有 $k(k-1)/2N$ 对元素，每一对元素有 $1/N$ 的机会是相等的，所以出现碰撞的概率接近 $k(k-1)/2N$ ，当 $k \approx \sqrt N$ 时，这个值就接近 50% 了。

大多数时候我们讨论 n 位的值，因为有 $2^n$ 个可能的值，所以集合中需要 $\sqrt {2^n} = 2^{n/2}$ 个元素才能预期出现一次碰撞。我们将经常谈到 $2^{n/2}$ 这个界，或称为生日界。

Python 代码

文件 birthday_attack.py：

def attack(n: int):
    for i in range(2, n):
        days = 365.0
        ratio = 1.0
        for k in range(0, i):
            ratio = ratio * ((days - k) / days)
        ratio = 1 - ratio

        print('ratio for %2d pepole is %f' % (i, ratio))

if __name__ == '__main__':
    attack(25)

运行结果如下：

$ python3 birthday_attack.py
ratio for  2 pepole is 0.002740
ratio for  3 pepole is 0.008204
ratio for  4 pepole is 0.016356
ratio for  5 pepole is 0.027136
ratio for  6 pepole is 0.040462
ratio for  7 pepole is 0.056236
ratio for  8 pepole is 0.074335
ratio for  9 pepole is 0.094624
ratio for 10 pepole is 0.116948
ratio for 11 pepole is 0.141141
ratio for 12 pepole is 0.167025
ratio for 13 pepole is 0.194410
ratio for 14 pepole is 0.223103
ratio for 15 pepole is 0.252901
ratio for 16 pepole is 0.283604
ratio for 17 pepole is 0.315008
ratio for 18 pepole is 0.346911
ratio for 19 pepole is 0.379119
ratio for 20 pepole is 0.411438
ratio for 21 pepole is 0.443688
ratio for 22 pepole is 0.475695
ratio for 23 pepole is 0.507297
ratio for 24 pepole is 0.538344
ratio for 25 pepole is 0.568700
ratio for 26 pepole is 0.598241
ratio for 27 pepole is 0.626859
ratio for 28 pepole is 0.654461
ratio for 29 pepole is 0.680969
ratio for 30 pepole is 0.706316
ratio for 31 pepole is 0.730455
ratio for 32 pepole is 0.753348
ratio for 33 pepole is 0.774972
ratio for 34 pepole is 0.795317
ratio for 35 pepole is 0.814383
ratio for 36 pepole is 0.832182
ratio for 37 pepole is 0.848734
ratio for 38 pepole is 0.864068
ratio for 39 pepole is 0.878220
ratio for 40 pepole is 0.891232
ratio for 41 pepole is 0.903152

1.1.10 中间相遇攻击

中间相遇攻击和生日攻击属于同一类 (我们将这两种攻击统称碰撞攻击)，不过中间相遇攻击更加常见而且更加有用。我们可以自己选择构造一个密钥表，而不用等待密钥重复出现。

我们再回到前面的金融交易系统的例子，每次交易都使用一个新的 64 位密钥来进行认证。使用中间相遇攻击，攻击者可以进一步攻破系统。攻击者首先随机选择 $2^{32}$ 个不同的 64 位密钥，然后对每一个密钥计算消息 "Are you ready to receive a transaction?" 的 MAC 值，并把 MAC 结果和密钥都保存在一张表中。接着窃听每一次交易，并检查第一条消息的 MAC 是否出现在他的表中，如果 MAC 出现在表中，那么这次交易的认证密钥将很有可能与攻击者计算这个 MAC 值使用的密钥是相同的，而且这个密钥与 MAC 值一起存储在表中。既然攻击者知道了认证密钥，就可以在交易中插入他选择的任意消息 (生日攻击只允许攻击者插入以前交易的消息)。

攻击者需要窃听多少次交易呢？他预先计算了所有密钥中 $1/2^{32}$ 的密钥对应的 MAC 值，所以每次系统选择一个密钥都有 $1/2^{32}$ 的概率选到攻击者能够识别的密钥，于是经过 $2^{32}$ 次交易之后，攻击者能够期望有一次交易使用的密钥是他预先计算 MAC 时使用的密钥。攻击者总的工作量大约是 $2^{32}$ 步预先的计算以及窃听 $2^{32}$ 次交易，比起尝试 $2^{64}$ 个可能的密钥来，这份工作量小多了。

同生日攻击相比，中间相遇攻击更具灵活性。简单地说，假设我们有 N 个可能的值，第一个集合有 P 个元素，第二个集合有 Q 个元素，那么一共有 PQ 对元素，每一对元素相等的概率为 $1/N$ ，如果 $PQ/N$ 接近于 1，我们就可以预测有一次碰撞。最有效的选择是 $P \approx Q \approx \sqrt N$ ，这正好就是生日界。中间相遇攻击还可以提供额外的灵活性，有时候获得一个集合中的元素比获得另一个集合中的元素要更容易一些，只要满足唯一的要求 PQ 接近于 N，如可以选择 $P \approx N^{1/3},Q \approx N^{2/3}$ 。在上述例子例子中，攻击者可以对第一个消息建立由 $2^{40}$ 个可能的 MAC 值组成的列表，期望在偷听了 $2^{24}$ 次交易之后找到第一个认证密钥。

当我们从理论上分析一个系统被攻破的难易程度时，通常使用两个大小均为 $\sqrt N$ 的集合，因为这样攻击者需要执行的步骤最少。如果想证明一个集合的元素比获得另一个集合的元素更困难，则需要进行更详细的分析。如果想要在实际中进行中间相遇攻击，则需要小心地选择集合的大小，以尽可能小的代价来保证 $PQ \approx N$ 。

1.1.11 中间人攻击

@TODO

1.2 计算机算法

计算机密码算法有多种，最通用的有以下三种：

数据加密标准 (Data Encryption Standard，DES) 是最通用的计算机加密算法。DES 是美国和国际标准，它是对称算法，加密和解密的密钥是相同的。
RSA (根据它的发明者命名，即 Rivest、Shamir 和 Adleman) 是最流行的公开密钥算法，它能用作加密和数字签名。
数字签名算法 (Digitial Signature Algorithm，DSA，用做数字签名标准的一部分)是另一种公开密钥算法，它不能用做加密，只用做数字签名。

1.3 安全等级

只要有足够的努力，任何密码系统都能被成功地攻击，真正的问题在于需要多少工作量去攻破一个系统。要确定一个攻击的工作量，一种简单的方法是把它与穷举搜索进行比较。所谓穷举搜索攻击，就是对某一目标 (例如密钥) 尝试所有的可能值。如果一个攻击需要 $2^{335}$ 个步骤，那么它就相当于对一个 235 位的值进行穷举搜索。

目前设计的任何系统实际上都需要至少 128 位的安全等级，也就是说，任何攻击都至少需要 $2^{128}$ 个步骤。当前设计的每个成功的新系统都应该能够运转 30 年，并且在最后一次使用之后，应该为数据提供至少 20 年的保密性，所以我们的目标是保证未来 50 年的安全性。这是一个相当高的等级，已经有一些工作根据摩尔定律进行了推断并用于密码学。128 位的安全等级是足够的，我们也可认为 100 位或者 110 位就足够，但是密码原语使用的参数大多为 2 的幂，于是我们这里使用 128 位。

安全等级的概念仅仅是近似的。我们只是度量了攻击者必须做的工作量，而忽略了诸如内存、系统交互等因素。但是仅仅度量攻击者的工作量就已经十分困难了，而将这个模型复杂化会使安全性分析更加困难，而且忽略关键因素的可能性会大大增加。由于采取简单而保守的方法代价相对较低，所以我们采用简单的安全等级概念。然而，安全等级是对手访问权限的函数：对手只能进行已知明文攻击还是可以进行选择明文攻击？对手可以掌握多少个加密消息？

1.4 性能

安全性不可能免费得到。虽然许多密码学家想让密码算法尽量高效，但有时这些算法还是被认为效率很低。

1.5 复杂性

一个系统越复杂，就越可能有安全问题。实际上，复杂性是安全性的最大障碍，这是一个很简单的准则，但是需要一段时间才能真正理解它。

我们知道使一个系统简单的唯一办法就是把它模块化。在进行软件开发时，我们都已经知道这一点，但是这次我们不能使其有任何错误，所以在模块化的时候必须非常仔细，这样就得到了第二条准则：正确性必须是一个局部性质。换言之，无论系统的其他部分如何工作，系统的每一部分都应该正确运转。我们不愿意听到 “这不会是一个问题，因为系统的其他部分绝不会让这种情况发生” 的说法，其他部分可能有错误，也可能在将来的某个版本中发生变化，所以系统的每个部分都应该为自己的功能负责。

项目源代码

项目源代码会逐步上传到 Github，地址为 https://github.com/windstamp。

Contributor

Windstamp, https://github.com/windstamp