《深入浅出密码学》——读书笔记（更新中）

Homqyy

发布于 2023-03-06 13:28:34

8030

发布于 2023-03-06 13:28:34

h1 { text-align: center } h2 { text-align: center } .picture { text-align: center } thead th, tfoot th { text-align: left; background: grey; color: white } tbody th { text-align: left; background: Gainsboro; color:white }

深入浅出密码学-读书笔记

作者：王鸿奇
邮箱：yilupiaoxuewhq@163.com

第一章密码学和数据安全导论

古希腊时代就已经有将文字写成密文的事例，叫斯巴达密码棒（Scytable of Sparta）

密码学：

x为明文、y为密文、k为密钥、所有可能密钥组成的集合称为密钥空间（key space）
简单对称加密：替换密码
- 替换密码的密钥空间虽然很大，但是并不安全，因为可以通过“字母频率分析”来进行破解。
，判断以下条件是否满足：

d_{k_i} = x

如果该等式成立，则意味着找到了一个可能正确的密钥；否则，继续尝试下一个密钥。

密码分析 Classical Cryptanalysis：古典密码分析可以理解为从密文 y 中恢复明文 x，或反过来，从密文 y 中恢复密钥 k 的一种门科。对此，密码分析可分为两类：发现加密方法内部结构的分析攻击将加密算法看作是黑盒，蛮力攻击 Implementation Attack：我们可以通过旁道分析获得密钥，比如测量处理私钥的处理器的功耗。也可以使用信号处理技术从功耗轨迹中恢复出密钥。除功耗外，电磁辐射或算法运行时的行为都隐含着一定的密钥信息，因此也是非常有用的旁道。需要注意的是，Implementation Attack 绝大多数情况下针对的是攻击者可以物理访问（比如智能卡）的密码体制，因此，绝大多数针对远程系统的基于Internet的攻击通常不会考虑这种方法。 Social Engineering Attack：可以通过行贿、勒索、跟踪或侦探等手段来获取密钥。
定义1.3.1 Kerckhoffs原理

合适的密钥长度
- 只有在蛮力攻击是已知的最好的攻击方法时，我们才会考虑对称加密算法中的密钥长度问题。
- 对称加密算法和非对称加密算法所要求的密钥长度完全不同。
- 蛮力攻击对称算法需要的时间表：
蛮力攻击对称需要的时间表
定义1.4.1 模运算

等价类：对于一个给定模数m，选择等价类中任何一个元素用于计算的结果都是一样的。示例：余数公式：0 \le r \le m-1

a \cdot a^{-1} \equiv 1\ mod\ m

如果元素

定义1.4.3 移位密码

仿射密码：与某个数相乘
- 定义 1.4.4 仿射加密
定义1.4.4
- 解密推导：
仿射解密过程
- 仿射密码的密钥空间计算： $$ \begin{aligned} 密钥空间 &= (a可以取的值) \times (b可以取的值)\ &= 12 \times 26 = 312 \end{aligned} $$

第二章序列密码

密码编码学的主要领域：

对称密码分为：序列密码和分组密码

序列密码：单独加密每个位。序列密码分为“同步序列密码”和“异步序列密码”，异步序列密码多了个“密码反馈(Cipher Feedback, CFB)”

分组密码：每次使用相同的密钥加密整个明文位分组。
序列与分组的区别：
- 现实生活中分组密码的使用比序列密码更为广泛，尤其是在Internet上计算机之间的通信加密中。
- 由于序列密码小而快，所以它们非常合适计算资源有限的应用，比如手机或其他小型的嵌入式设备。序列密码的一个典型示例就是A5/1密码，它是GSM手机标准的一部分，常用语语音加密。但是，序列密码有时也可用于加密Internet流量，例如“RC4”。
- 以前，人们认为序列密码比分组密码要更高效。软件优化的序列密码的高效率意味着加密明文中的1位需要的处理器指令（或处理器周期）更少。对硬件优化的序列密码而言，高效率意味着在相同加密数据率的情况下，序列密码比分组密码需要的门更少（或更小的芯片区域）。然而，诸如AES的现代分组密码在软件实现上也非常有效。此外，有一些分组密码在硬件实现上也非常高效。比如PRESENT，它的效率与紧凑型分组密码相当。

2.1 序列密码

为什么可使用简单的模2加法来进行加密？模2加法的真值表： x_i | s_i | y_i \equiv x_i + s_i \ mod \ 2 —|—|— 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 0 上述表格就是一个异或门，即XOR XOR函数是完全均衡的密钥序列为s_i的本质是什么？ s_i本身不是密钥位，s_i对攻击者而言，看起来必须是随机的才具备安全性。

2.2 随机数

随机数生成器类别 TRNG（真随机数生成器）：输出是不可复制的都是基于物理过程 PRNG（伪随机数生成器）：从一个初始种子值开始通过各种计算得到序列必须拥有良好的统计属性，即它的输出近乎与TRNG相同 CSPRNG（加密安全的伪随机数生成器）密码学应用 PRNG的一个特例给定密钥序列中n个连续位，不存在一个时间复杂度位多项式的算法使得成功预测下一个位s_{n+1}的概率超过50%
定义2.2.1 无条件安全
- 如果一个密码体质在无限计算资源的情况下也不能破译，则说明它是无条件安全的或信息理论上安全的。
定义2.2.2 一次一密（OTP）一个序列密码称为一次一密必须满足一下条件：通过TRNG得到密钥序列：s_0, s_1, s_2, … 只有合法的通信方才知道密钥序列每个密钥序列位s_i仅适用一次一次一密是无条件安全的。
定义2.2.3 计算安全
- 如果为破解一个密码体制，最好的已知算法需要至少t个操作，则说明此密码体质是计算安全的。（未知是否有更好的攻击方法）
那么密钥值应为(A, B)所以，只需要能够知道两对明文和密文对即可获得两个方程，并得到A与B的解：因为得到的(A, B)
测试TRNG输出序列的统计属性的工具
- Diehard Battery of Tests of Randomness CD, 1995. http://i.cs.hku.hk/~diehard/
- NIST test suite for random number. http://csrc.nist.gov/rng/

2.3 LFSR

） LFSR有时也称为线性递归。输出计算公式为：

\tag{1} s_m \equiv s_{m-1}p_{m-1} + … + s_1p_1 + s_0p_0 \ mod \ 2

\tag{2} s_{m+1} \equiv s_mp_{m-1} + … + s_2p_1 + s_1p_0 \ mod \ 2

归纳后可得：，则LFSR可以表示为：

P(x) = x^m + p_{m-1}x^{m-1} + … + p_1x + p_0

最大长度LFSR拥有本原多项式（primitive polynomial），该多项式仅有的因子是1和多项式本身。只需要知道2m个输出位就能攻击LFSR（已知明文攻击）是一个很好的拥有良好统计属性但密码学属性非常差的PRNG

定理2.3.1 度为m的LFSR可以产生的最大序列长度为2^m – 1 必须排除全部为0的状态，如果LFSR全为0的话，则将一直陷入其中，不可能离开。

2.4 Trivium

是一个比较新的序列密码，密钥长度为80位。由三个移位寄存器组成，在得到每个寄存器的输出时使用了非线性组件。
寄存器长度分别为93，84，111
内部结构

规范寄存器|寄存器长度|反馈位|前馈位|AND输入 —|—|—|—|— A|93|69|66|91, 92 B|84|78|69|82, 83 C|111|87|66|109, 110
加密几乎所有现代序列密码都拥有两个参数：“密钥k”和“初始向量IV” IV不需要保密，只需要在每次会话时改变就行了。这样的值通常也称为nonces，表示只使用一次的数字。加密阶段初始化阶段：开始时，将80位的IV加载到寄存器A最左边的80个位置和寄存器B最左边的80个位置。除了将寄存器C中最右边3位置为1外，将三个寄存器中其他剩余的位都置为0. 热身阶段：在第一阶段中，该密码计时了4 \times 288 = 1152 次，并没有产生任何密码输出目的：为了充分随机化密码，也确保密钥序列同时取决于密钥k和IV。加密阶段：自此阶段开始产生的位就构成了密钥序列，即从第1153周期的输出位开始。

第三章数据加密标准与替换算法

3.1 DES简介

DES：Data Encryption Standard，数据加密标准
- 分组密码
- DES已经不再安全, 最终被AES取代
混淆与扩散
- 混淆（Confusion）：是一种使密钥与密文之间的关系尽可能模糊的加密操作。如今实现混淆常用的一个元素就是替换；这个元素在DES和AES中都有使用。
- 扩散（Diffusion）：是一种为了隐藏明文的统计属性而将一个明文符号的影响扩散到多个密文符号的加密操作。最简单的扩散元素就是位置换，它常用于DES中；而AES则使用更高级的Mixcolumn。
乘积密码：将若干个加密操作串联起来。
- N轮乘积密码的基本原理，其中每轮都执行一次扩散和混淆操作：
乘积密码
现代分组密码常用的分组长度为64位或128位，但如果有一个输入位发生翻转，不同分组长度的分组密码的行为都是一样的。

3.2 DES算法概述

很多（但不是全部）现代分组密码都使用了Feistel网络（实际上，AES不是Feistel密码）。除了潜在的密码学强度外，Feistel网络的另一个优势就是它的加密过程和解密过程几乎完全相同。

3.3 DES的内部结构

DES的基本构造元件为初始置换和逆初始置换、实际DES轮及其核心、f函数以及密钥编排（key schedule）
初始置换表 IP(x) 和逆初始置换表 IP^{-1}(z)
f函数：负责混淆和置换 Expansion函数 Round key：由keyschedule得到的。 S-盒首位和末位用来查找行，内部的4个位用来查找列，且行和列的开头都是0，如上图的结果为（3,2）。设计准则：每个S-盒都有6个输入位和4个输出位。任意一个输出位都不应该太接近于输入位的线性组合。如果输入的最高位和最低位都是固定的，只有中间的4个位是可变的，则每个可能的4位输出值都必须只出现一次。对于S-盒的两个输入，如果仅有1位不同，则输出必须至少有两位不同。对于S-盒的两个输入，如果只有中间两位不同，则输出必须至少有两位不同。对于S-盒的两个输入，如果开头的两位不同，但最后两位相同，则输出必须不同。对任意有6位非零差分的输入对，32对输入中至多有8对有相同的输出差分。 8个S-盒对应的32位输出的冲突（零输出差异）只有在三个相邻的S-盒的情况下才有可能。 S-盒引入了非线性，即：

S(a) \oplus S(b) \ne S(a \oplus b)

剩余的S盒不记录，有需要自行搜索即可。

置换P

密钥编排注意：DES的输入密钥通常是64位，其中每第8个位都作为前面7位的一个奇校验位。没有人清楚以这种方式规范DES的原因。任何情况下，这8个奇校验位都不是真的密钥位，也没有增加密码的安全性。所以可以说DES是一个56位的密码，而不是64位的。注意：从图中可以看出一个关键点，在经过16轮密钥编排后，我们的C0和D0正好旋转了28位，也即D_0 = D_{16} 和 C_0 = C_{16} 密钥编排的目的：实现16轮置换的方法使56个密钥位的每位都用于不同的轮密钥中；每个密钥位差不多会出现在16个轮密钥中的14个。

3.4 DES解密

DES的优势：其解密过程与加密过程在本质上是完全相同的。与加密相比，解密过程中只有密钥编排逆转了。
\begin{aligned} k_{16} &= PC \text{-} 2(C_{16}, D_{16}) \ &= PC \text{-} 2(C_0, D_0) \ &= PC \text{-} 2(PC \text{-} 1(k)) \end{aligned}
Feistel 网络中的解密

(L^d_0, R^d_0) = IP(Y) = IP(IP^{-1}(R_{16}, L_{16})) = (R_{16}, L_{16})

因此，的计算如下：首先，

L^d_1 = R^d_0 = L_{16} = R_{15}

接着， \begin{aligned} L^d_i &= R_{16 – i} \ R^d_i &= L_{16 – i} \end{aligned}

3.5 DES的安全性

密码攻击可以分为：
- 穷尽密钥搜索攻击（或蛮力攻击）
- 分析攻击
针对DES密码强度的批评主要以下两个方面：
1. DES的密钥空间太小，即该算法很脆弱，易受蛮力攻击。
2. DES S-盒的设计准则是保密的，所以有可能已经存在利用S-盒数学属性的分析攻击，只是此攻击只有DES的设计者知道。
因为利用蛮力攻击就可以容易的破解单重DES，因此对大多出应用程序而言，单重DES已经不再适用。
个可能的密钥，直到以下条件成立：

DES^{-1}_{k_i}(y) = x,\ i = 0,1,…,2^{56}-1

注意：找到错误密钥

单重DES只能用于要求短期安全性（比如几个小时）的应用或被加密数据价值较低的情况。然而，DES变体仍然很安全，尤其是3DES：
- EFF(Electronic Frontier Foundation)于1998年构建了一个硬件机器，叫Deep Crack，它使用蛮力攻击可以在56小时内破解DES，而成本才不到25万美元。
- 2006年，来自德国构建了COPACOBANA（Cost-Optimized Parallel Code-Breaker）机器，破解平均不到7天，且成本仅为1万美元。
分析攻击：
- Eli Biham和Adi Shamir发现了差分密码分析（DC），理论上可以破解任何分组密码。然而事实证明，DES的S-盒可以很好的抵抗这种攻击。
- 线性分析攻击（LC），该攻击在前面攻击LFSR的时候已经提及过。

3.6 软硬件实现

软件实现：通常指的是在桌面CPU或类似智能卡或手机的嵌入式微处理器上运行DES。
硬件实现：指的是在诸如专用集成电路（ASIC）或现场可编程们阵列（FPGA）的IC上运行DES实现。 DES的一个设计标准就是硬件实现的效率。类似E置换、P置换、IP置换和IP^{-1}置换的置换操作非常易于硬件实现，因为它们只需要布线而不需要逻辑。

3.7 DES算法替代品

AES(Advanced Encryption Standard, 高级加密标准)目前还没有被成功破译。

AES是公开竞争的结果，在寻找DES替代算法时，与Mars、RC6、Serpent和Twofish一起入围了。所有这些密码都是密码学安全的，并且非常快，在软件实现上尤其如此。

三重DES（3DES）：

3DES在硬件实现上非常搞笑，但在软件上却不那么高效。

增强DES的另一种方法就是使用“密钥漂白”：

y = DES_{k,k_1,k_2}(x) = DES_k(x \oplus k_1) \oplus k_2

该简单的修改使得DES更能抵抗穷尽密钥搜索。

轻量级密码PRESENT

轻量级通常指实现复杂度非常低的算法，尤其指硬件实现方面。比如“Trivium就是，而最有希望的分组密码就是PRESENT，它是专门为类似RFTD标签或其他严格性能或成本限制的常用计算应用而设计的。
它是一个“替换-置换网络”（SP网络），并由31轮组成。PRESENT的分组长度为64位，并支持80位和128位两种长度的密钥。
由 k_i(1 \le i \le 32) 轮密钥、一个非线性替换层（sBoxLayer）、线性按位置换（pLayer）组成。

如上图所示，其伪代码如下：

generateRoundKeys()
for i=1 to 31 do
    addRoundKey(STATE, $K_i$)
    sBoxLayer(STATE)
    pLayer(STATE)
end for

addRoundKey：在每轮刚开始的时候，轮密钥 K_i 与当前状态进行XOR操作。
sBoxLayer：PRESENT使用单个4位到4位的S-盒。这是追求硬件效能的直接结果，因为这样的S-盒的实现比8位的S-盒的实现更紧凑，S-盒的标识如下所示： x 0 1 2 3 4 5 6 7 8 9 A B C D E F S[x] C 5 6 B 9 0 A D 3 E F 8 4 7 1 2
Player：置换层表示如下所示： iP(i) 00 116 232 348 41 517 633 749 82 918 1034 1150 123 1319 1435 1551 iP(i) 164 1720 1836 1952 205 2121 2237 2353 246 2522 2638 2754 287 2923 3039 3155 iP(i) 328 3324 3440 3556 369 3725 3841 3957 4010 4126 4242 4358 4411 4527 4643 4759 iP(i) 4812 4928 5044 5160 5213 5329 5445 5561 5614 5730 5846 5962 6015 6131 6247 6363 上表的置换可以用一下方式表示：
当前内容最左边的64位组成，因此有：

K_i = \kappa_{63}\kappa_{62}…\kappa_{0} = k_{79}k_{78}…k_{16}

对于

实现：由于PRESENT的硬件优化设计过于激进，与类似AES的现代密码相比，PRESENT的软件性能不是很具有竞争力。

PRESENT-80硬件实现大概与1600个门所占的面积等价，加密一个64位明文分组需要32个时钟周期。

3.8 讨论

不少主流的分组密码也是基于Feistel网络，比如AES。Feistel网络的示例包括Blowfish、CAST、KASUMI、Mars、MISTY1、Twofish和RC6。与DES完全不同的密码就是IDEA，它将3种不同的代数结构作为原子操作。
其他最近提议的小型分组密码还包括 Clefia、HIGHT、mCrypton

待决问题

练习题：2.10：做不出来
练习题：2.11：求逆矩阵忘记了，等学了后再回来看，这个题目不错，需要记录

对称密码

替换密码
- 仿射密码
- 移位密码（凯撒密码）

讨论与扩展阅读

古典密码与摸运算

了解古典密码及其在历史中发挥的作用：
- F.L.Bauer. Decrypted Secrets: Methods and Maxims of Cyptology Springer, 4th edition, 2007
- D.Kahn. The Codebreakers. The Story of Secret Writing. Macmillan, 1967
- Simon Singh. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Anchor, August 2000
- 数论
  - 经典入门：
    - I.Nivens, H.S.Zuckerman, and H.L.Montgomery. An Introduction to the Theory of Numbers (5th Edition). Wiley, 1991
    - K.H.Rosen. Elementary Number Theory, 5th Edition. Addison-Wesley, 2005
  - 非数学专业人士，强烈推荐：Jerome A.Solinas.Efficient arithmetic on Koblitz curves. Designs, Codes and Cryptography, 19(2-3):195-249, 2000

分组密码

攻击方法[21,114]
PRESENT-128密钥编排[29]：
PRESENT优秀参考文献[29,147]
DES历史概述[165]
DES高级技术描述[106]
DES软件实现[20,106]
DES硬件实现[169,163]

研究机构和通用文献

国际密码逻辑研究学会（International Association for Cryptologic Research, IACR）
- 三个会刊：CRYPTO、EUROCRYPT、ASIACRYPT
- 研讨会：加密硬件与嵌入式系统（CHES）、快速软件加密（FSE）、公钥密码学（PKC）、密码学理论（TCC）
密码学推荐书籍：
- A.J.Menezes, P.C.van Oorschot, and S.A.VanStone. Handbook of Applied Cryptography. CRC Press, Boca Raton, Florida, USA, 1997
- Henk C.A. van TIlborg, editor. Encyclopedia of Cryptography and Security. Springer, 2005

安全系统设计

标准
- Common Criteria for Information Technology Security Evaluation. http://www.commoncriteriaportal.org/
- German Federal Office for Information Security (BSI). http://www.bsi.de/english/publications/bsi_standards/index.htm
- Federal Information Processing Standards Publications – FIPS PUBS. http://www.itl.nist.gov/fipspubs/index.htm
- International Organization for Standardization (ISO). ISO/IEC 15408, 15443-1, 15446, 19790, 19791, 19792, 21827

引用

配套学习资源网站：www.crypto-textbook.com
密码工具：https://www.cryptool.org/

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2021年10月12日，如有侵权请联系 cloudcommunity@tencent.com 删除

网络安全

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

《深入浅出密码学》——读书笔记（更新中）

《深入浅出密码学》——读书笔记（更新中）

深入浅出密码学-读书笔记