基于斯坦福大学 密码学一
密码分析的四个手段
唯密文攻击（Ciphtext Only Attack，COA）
定义：唯密文攻击(COA)是指仅仅知道密文的情况下进行分析，求解明文或密钥的密码分析方法。
假定密码分析者拥有密码算法及明文统计特性，并截获了一个或者多个用同一密钥加密的密文，通过对这些密文进行分析求出明文或密钥。COA已知条件最少，经不起唯密文攻击的密码是被认为不安全的。
简单理解：只知道密文，推出明文或密钥，一般用穷举攻击。
已知明文攻击（Known Plaintext Attack，KPA）（也可称为KPA安全）
定义：已知明文攻击(KPA)是指攻击者掌握了部分的明文M和对应的密文C，从而求解或破解出对应的密钥和加密算法。
简单理解：知道部分的明文和密文对，推出密钥和加密算法。
选择明文攻击（Chosen Plaintext Attack，CPA）（也可称为CPA安全）
定义：选择明文攻击(CPA)是指攻击者除了知道加密算法外，还可以选定明文消息，从而得到加密后的密文，即知道选择的明文和加密的密文，但是不能直接攻破密钥。
简单理解：知道明文就知道密文，目标为推出密钥。
选择密文攻击（Chosen Ciphertext Attack，CCA）（也可称为CCA安全）
定义：选择密文攻击(CCA)是指攻击者可以选择密文进行解密，除了知道已知明文攻击的基础上，攻击者可以任意制造或选择一些密文，并得到解密的明文，是一种比已知明文攻击更强的攻击方式。
若一个密码系统能抵抗选择密文攻击，那必然能够抵抗COA和KPA攻击。密码分析者的目标是推出密钥，CCA主要应用于分析公钥密钥体制。
简单理解：知道密文就知道明文，目标为推出密钥。
当密码系统只有承受住选择明文攻击(CPA)和选择密文攻击(CCA)，才能算是安全的。 其中，四种攻击方式对应的攻击强度为：
攻击难度：选择密文攻击(CCA)＞选择明文攻击(CPA)＞已知明文攻击(KPA)＞唯密文攻击(COA) 难易程度：选择密文攻击(CCA)＜选择明文攻击(CPA)＜已知明文攻击(KPA)＜唯密文攻击(COA)
离散概率
异或性质
（1）交换律：$ A \oplus B = B \oplus A$
（2）结合律： $( A \oplus B ) \oplus C = A \oplus ( B \oplus C )$
（3）自反性：$ A \oplus B \oplus B = A $（由结合律可推：$ A \oplus B \oplus B = A \oplus ( B \oplus B ) = A \oplus 0 = A)$
Birthday Paradox
每个人生日都不相同的概率: $$ \bar{p}(n)=1 \cdot\left(1-\frac{1}{365}\right) \cdot\left(1-\frac{2}{365}\right) \cdots\left(1-\frac{n-1}{365}\right)=\frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdots \frac{365-n+1}{365} $$ 阶乘形式为 $\frac{365 !}{365^n(365-n) !}$ 至少两人生日相同的概率就是这个结果的补 $$ p(n)=1-\bar{p}(n)=1-\frac{365 !}{365^n(365-n) !} $$
secure cipher
perfect secrecy
For every probability distribution over $M$ and $K$, every plain-text $m_0, m_1 \in M$ and every cipher text $c \in C$, the following holds: $$ \operatorname{Pr}\left[C=c \mid M=m_0\right]=\operatorname{Pr}\left[C=c \mid M=m_1\right] $$ 此定义可被解释为，密文空间的概率分布独立于明文空间的概率分布
OTP是Perfect Security 证明:
$\forall m \in M, \forall c \in C \quad \operatorname{Pr}[E(k, m)=c]=\frac{# k e y, k \in K \text { s.t. } E(k, m)=c}{|K|}$
，在OTP中 $k=m \oplus c$ ，因此对于任意的 $m, c$ 使得 $E(k, m)=c$ 的 $k$ 的个数为 1 。
所以，在OTP中对于 任意的 $m, c ， \operatorname{Pr}[E(k, m)=c]$ 是一个常数。因此OTP是perfect security。
流密码
PRG unpredictable
可忽略函数
在数学中，可忽略函数 (英语: Negligible function) 是指 对于一个函数 $\mu(x): \mathbb{N} \rightarrow \mathbb{R}$ ，如果对于任意一个正多项式 $p o l y()$ ，存在一个 $N_c>0$ ，使得对于所有的 $x>N_c$ $$ \mu(x)<\frac{1}{\operatorname{poly}(x)} $$ 那么这个函数便是可忽略的 (negligible)。通常我们把 “存在一个 $N_c>0$ ，使得对于所有的 $x>N_c$ " 简化为 “对于所有足够大的 $x^{\prime \prime}$ 。
语义安全
- 攻击者自己任意选择两个消息m0、m1（注意，这个m0、m1是攻击者自己选的）
- 攻击者把这两个消息发送给挑战者。
- 挑战者运行加密算法，加密mb，把加密结果发送给攻击者。
$\operatorname{Adv}_{S S}[A, E]=\left|\operatorname{Pr}\left[c \leftarrow E\left(k, m_0\right)\right]-\operatorname{Pr}\left[c \leftarrow E\left(k, m_1\right)\right]\right|=0$
OTP是语义安全的,因为任意的$m_i \oplus k $ 都是均匀分布的，无法区分两个实验
流密码是语义安全的
定理1: 如果一个流密码 $\mathcal{E}$ 使用的PRG $\mathcal{G}$ 是安全的，那么 $\mathcal{E}$ 是语义安全的，并且在给定 $\mathcal{E}$ 的敌手 $\mathcal{A}$ 的情况下存在对于 $\mathcal{G}$ 的敌手 $\mathcal{B}$ 满足 $S S a d v^*[\mathcal{A}, \mathcal{E}]=P R G a d v[\mathcal{B}, \mathcal{G}]_{\text {。 }}$
分组密码
PRF和PRP
PRF 取一个密钥 $K$ 和集合$X$中的元素作为输入，输出值在集合$Y$中，现在唯一要求的是存在一个有效的算法来实现这个函数。也就是说，要有 一个有效的函数来实现 $K \times X \rightarrow Y$ 的映射。 PRP 与PRF不同的是，多了一个条件，那就是要有一个算法D可以实现逆运算。 在PRP中，存在一个有效算法，能够实现映射关系 $K \times X \rightarrow X$ ，也就是说该算法能够将随机密钥 $k$ 与集合 $K \mathrm{X}$ 中的元素作为输入，同时 输出值也是集合X中的元素，那么就要求每个元素一一对应。
从本质上来说， $E(k, x)$ 是对元素 $\mathrm{x}$ 的置换，为了解密的需要，就要求E是可逆的。
安全性证明
DES
Feistel结构
令 $\mathrm{F}$ 为轮函数，并令 $K_0, K_1, \ldots, K_n$ 分别为轮 $0,1, \ldots, n$ 的子密钥。 基本操作如下: 将明文块拆分为两个等长的块， $\left(L_0, R_0\right)$ 对每轮 $i=0,1, \ldots, n$ ，计算 $$ \begin{aligned} L_{i+1} & =R_i \ R_{i+1} & =L_i \oplus \mathrm{F}\left(R_i, K_i\right) . \end{aligned} $$ 则密文为 $\left(R_{n+1}, L_{n+1}\right)$ 。 解密密文 $\left(R_{n+1}, L_{n+1}\right)$ 则通过计算 $i=n, n-1, \ldots, 0$ $$ \begin{aligned} & R_i=L_{i+1} \ & L_i=R_{i+1} \oplus \mathrm{F}\left(L_{i+1}, K_i\right) . \end{aligned} $$ 则 $\left(L_0, R_0\right)$ 就是明文。
如果轮函数是一个密码安全的伪随机函数，使用$K_i$作为种子，那么3轮足以使这种分组密码成为伪随机置换，而4轮可使它成为“强”伪随机置换（这意味着，对可以得到其逆排列谕示的攻击者，它仍然是伪随机的）。
Feistel结构轮函数
（1）、将64bit的明文右半部分(IP置换的产物，左右各有32bit)即32bit扩展为48bit：采用的是4个bit一组，分为8组，每一组前后各加1bit（增加的bit数=$218=16bit$）。其增加按照下表进行（虚线以外的为增加的bit所在位置，如：第一组前是32，即在第一组前加一个bit为整个右半部分的32bit的第32位的bit值{0,1}）：
（2）、得到的48bit扩充信息，和子密钥$K_i$进行异或操作，得到48bit的结果； （3）、将扩充信息和子密钥异或后的结果进行压缩（48bit压缩到32bit），压缩的方式是经过S盒（4*16的矩阵）进行替换，S盒函数是经过严格计算获得的，其S1盒的替换表与流程如下所示：
一个组6bit，共8组（6bit*8=48bit），即有8个S盒，每个S盒是固定的但是都是不相同的
S盒的实现就像一个编码器，只不过是6-4线的。原来的6bit作为索引，转换为索引到的4bit。
S盒的设计原则是遵循了F函数的要求来设计的，比如非线性、雪崩性、比特统计独立性等
（4）、置换运算P（经过一个P盒进行置换）：指的是将32bit压缩后的信息进行bit置换操作，改换位操作目的是打乱其原有排序规律（F函数的混乱性原则）
DES介绍
DES是使用对称秘钥的分组加密算法。具体的算法流程如下
因为加密和解密的密钥是一样的，所以称之为对称密钥。另外分组加密，是因为这种算法把明文划分为许多个等长的块(block)或分组,对每个块进行加密，最后拼接在一起。
从本质上来说，DES的安全性依赖于虚假表象，从密码学的术语来讲就是依赖于“混淆和扩散”的原则。混淆的目的是为隐藏任何明文同密文、或者密钥之间的关系，而扩散的目的是使明文中的有效位和密钥一起组成尽可能多的密文。
DES的功能是:给定64bits的Plaintext和8字节64bits的key，输出一个64bits的ciphertext。这些ciphertext可以用相同的key进行解密。
虽然 DES 一次只能加密 8 个字节，但我们只需要把明文划分成每 8 个字节一组的块，就可以实现任意长度明文的加密。如果明文长度不是 8 个字节的倍数，常用PKCS7 / PKCS5进行填充，用于把任意长度的文本填充成 8 字节的倍数长，也能方便地恢复原文。
DES算法框架
IP置换目的是将输入的64位数据块按位重新组合，并把输出分为L0、R0两部分，每部分各长32位
子秘钥生成
DES的密钥每个字节的第8位作为奇偶校验位，密钥由64位减至56位。这56位的密钥由一下的密钥置换表获得。
密钥置换表：（没有8,16,24，32,40,48,56和64这8位）
在DES的每一轮的子密钥，从这56位密钥产生出不同的48位子密钥，确定这些子密钥的方式如下：
- 将56位的密钥分成两部分，每部分28位。
- 根据轮数，这两部分分别循环左移1位或2位。每轮移动的位数如下表：
移动后，又从56位中选出48位。置换了每位的顺序，最终确定子密钥。此过程称为密钥压缩置换。压缩置换规则如下表（注意表中没有9，18，22，25，35，38，43和54这8位）：
3DES
3DES也是个一般的分组密码，有三元组$(K,M,C)$
定义三重加密,使用三个秘独立的密钥，和之前DES一样加密明文分组，它先使用密钥k3，然后用密钥k2解密，然后再用密钥k1加密
E->D->E
如果三密钥相等，k1=k2=k3，最终的效果是一个加密和一个解密抵消，又变成了正常的DES
why no 2DES
存在meet-in-the-middle attack
假设 $E$ 和 $D$ 分别是加密函数和解密函数， $k 1$ 和 $k 2$ 分别是两次加密使用的密钥，则我们有 $$ \begin{aligned} & C=E_{k_2}\left(E_{k_1}(P)\right) \ & P=D_{k_1}\left(D_{k_2}(C)\right) \end{aligned} $$ 则我们可以推出 $$ E_{k_1}(P)=D_{k_2}(C) $$ 那么，当用户知道一对明文和密文时
- 攻击者可以枚举所有的 $k 1$ ，将 $P$ 所有加密后的结果存储起来，并按照密文的大小进行排序。
- 攻击者进一步枚举所有的 $k 2$ ，将密文C进行解密得到 C1，在第一步加密后的结果中搜索 $C 1$ ，如果搜索到，则我们在一定程度上可以认为我们找到了正确的 $k 1$ 和 $k 2$ 。
- 如果觉得第二步中得到的结果不保险，则我们还可以再找一些明密文对进行验证。 假设 $\mathrm{k} 1$ 和 $\mathrm{k} 2$ 的密钥长度都为 $\mathrm{n}$ ，则原先我们暴力枚举需要 $O\left(n^2\right)$ ，现在我们只需要 $O\left(n \log _2 n\right)_0$
实际上2DES中的中间相遇是穷举中间产物即k2加密->应该是k1解密得到的，所以分别双向进行穷举
DESX
我们使用密钥k1,k2,k3，然后在加密前，用k3异或明文分组，然后用k2加密明文，然后将加密结果异或k1
更多的对于分组密码的攻击
侧信道攻击，直接检测你加密ID卡的细微电流，然后还原出秘钥
错误攻击，报错泄露原来的信息
线性分析(linear cryptanalysis)方法本质上是一种已知明文攻击方法。这种方法可用 221 个已知明文破译8-轮DES，可用 247 个已知明文破译16轮DES。该种方法在某些情况下，可用于唯密文攻击，线性分析的基本思想是通过寻找一个给定密码算法的有效的线性近似表达式来降低密钥的熵，，从而破译密码系统。
AES
第一步:轮秘钥加
加密第二步：字节代替
字节代替也叫做S盒变换 AES有个固定的S盒，下图即为S盒
把第一步轮密钥加后产生的每一个字节用十六进制表示 然后以十六进制的第一个数字为行，第二个数字为列，在S盒表中查找对应的数字，用这个数字来代替原先的数字，这样就完成了字节变换。（比如原字节为0x1a，就以1为行，a为列，找到表中对应的0xa2来代替0x1a的位置）
加密第三步：行移位
就是把上一步得到的矩阵每行左环移，第一行不变，第二行环移1位，第三行环移2位，第三行环移3位。
加密第四步：列混淆
将上一步得到的矩阵a左乘矩阵c，得到新的矩阵b。 这里的矩阵c是固定的(AES规定的)
如果需要加密任意长度的明文，需要对分组密码进行迭代,分组密码的迭代方式叫做分组密码的模式
| 模式 | 详细 |
|---|---|
| ECB | Electronic Code Book mode(电子密码本模式) |
| CBC | Cipher Block Chaining mode(分组密码链接模式) |
| CFB | Cipher Feedback mode |
| OFB | Output Feedback mode |
| CTR | Couter mode |
| XTS | XEX(\oplus Encrypt \oplus)Tweakable Block Cipher with CipherText Stealing |
ECB
此外，独立地对每个块加密，最后直接拼起来是不行的（这种方式称为“电子密码本”，ECB 模式。但如果明文当中有多个相同的分组，则这些明文分组就会产生相同的密文分组，这对于图片之类的数据来说几乎是致命的）。
ECB不是语义安全的
Deterministic counter mode
Many times多次使用的CPA
知道明文就知道密文，目标为推出密钥。
对于选择明文攻击，攻击者可以重复这个询问多次。
选择明文攻击的本质，如果攻击者想知道特定明文信息m的加密结果，比如使用询问J，查明文J的加密结果。他把信息0和1都设为一样的信息m，左边和右边的信息是一样的都是m，这时由于两个m一样，攻击者会收到他感兴趣的信息m的加密结果，这就是选择明文攻击的意思。攻击者可以提交信息m，收到m的加密结果。
CBC
Cipher Block Chaining mode(分组密码链接模式)
1）所有分组的加密都链接在一起，使得某一分组的密文不再仅依赖于该分组的明文，而是依赖于该分组之前（包含该分组）的所有明文分组；
2）加密过程使用了初始化向量（IV）进行了随机化。
带IV的CBC模式对于CPA攻击是语义安全的
CBC是安全的，最好是q^2*L^2远远小于|x|的值
L是加密的明文长度
q是在CPA攻击下，攻击者获得的密文数
在现实中，q的意义是我们使用密钥k加密的次数
基于新鲜值的CBC加密
这种模式里，IV被某个不随机但是唯一的新鲜值取代
好处是， 如果接受方知道新鲜值是多少，就没必要把新鲜值包含在密文里了，密文就和明文一样长了。
这种模式，需要两个独立的k和k1，k加密分组，k1加密新鲜值
用k1加密新鲜值是非常重要的
如果用k加密新鲜值，也不是CPA安全的。
CBC padding orcle
1 CBC字节翻转攻击原理
对于CBC模式的解密算法，每一组明文进行分组算法解密之后，需要和前一组的密文异或才能得到明文。第一组则是和初始向量IV进行异或。
$\mathrm{CBC}$ 字节翻转攻击的核心原理是通过破坏一个比特的密文来簛改一个比特的明文。
对于异或运算, 有以下逻辑:
相同字符之间异或运算的结果为 0 , 即 $1 \oplus 1=0$
任何字符与 0 异或运算结果为原字符, 即 $1 \oplus 0=1$
假设现在我们有第 $N-1$ 组密文某一位的值 $A$, 以及第 $N$ 组密文相同位置经过分组解密后的值 $B$, 于是我们能够很容易得到第 $N$ 组该位置上的明文 $C$
$$
A \oplus B=C
$$
如果我们破坏第 $N-1$ 组的密文 $A$, 将其与明文 $C$ 进行异或运算 $A \oplus C$, 由异或的性质可以得到下式
$$
A \oplus C \oplus B=C \oplus C=0
$$
可以看见, 现在计算出的明文变成 $了$ 了, 现在我们可以将明文随意更改成我们想要的字符。只需要在上一组的密文异或我们想要的字符即可, 假设我们想将明 文 $C$ 更改为 $X$, 可以由下式得出
$$
A \oplus C \oplus X \oplus B=C \oplus C \oplus X=X
$$
CTR
CTR模式还有一种基于新鲜值的计数器模式
IV不是真随机的，是一个新鲜值，可计数的
把AES的128位分组，左64位作为新鲜值，计数器是0到2的64次方
CTR：一个AES密钥可以用2的64次
CBC：一个AES密钥可以用2的48次
消息完整性Message integrity
S(k,m) outputs t in T
安全的MAC系统
⇒ attacker cannot produce a valid tag for a newmessage
⇒ given (m,t)attacker cannot even produce (m,t’) for t’ ≠ t
如何把短的MAC转化为长的MAC
两种方法：
- ECBC-MAC 应用在银行业又叫CMAC
- HMAC应用在网络协议
加密的CBC-MAC。简称ECBC
我们把最大信息长度界定为L取信息，分割成分组。每个分组和底层函数f的分组一样长。CBC运行，但不输出中间值。
这种情况下标签为N位长。截断标签。
最后一步加密是干什么的。
如果没有最后一步，叫做raw CBC 函数,原CBC并不安全。最后一步对于MAC的安全性很重要
而MAC在生成时会使用一个密钥附加在消息之前：这确保不仅消息未被修改，而且发送者也是我们所期望的：否则攻击者无法知道用于生成的code的密钥。【考虑发送方和接收方共享一个密钥，在hash时附上密钥一起进行哈希】
MAC padding
CMAC
CMAC，使用一个随机的补齐函数，不用加假分组。
用了三个密钥，也称三密钥机制。
如果是有补位，用k1异或，没有补位用k2异或
先用ISO的方法，补100….但是我们还要把最后一个分组和密钥k1xor
好处是没有最后的加密步骤，不用加假分组。
CMAC 和CBC-MAC有同样的安全性。
Collision Resistance
条件1，有一个MAC可以加密短信息，比如AES
条件2，有一个哈希函数是抗碰撞的。 SHA256
这种方式和MAC相比较，如果用MAC，我们需要一个密钥来验证单个文件的标签，但我们不需要一个只读的公共空间。
用抗碰撞的哈希函数，我们不需要一个密钥来验证，任何人都可以验证。
数字签名可以在完整性和资源（不需要只读公共空间）两方面都达到最优
Hash(不需要key)， MAC（带key），HMAC(带key)
这种生日攻击可以在2的n/2次内找到可能的碰撞，低于2的64次是危险的。
所以我们一般不用128位输出的哈希。用256。
The Merkle-Damgard Paradigm
其中，基于Merkle-Damgard paradigm的迭代哈希函数如图1所示。首先对待发送消息 $M$ 进行 处理，对它进行填充（ $\hat{M} \leftarrow M | \mathrm{PB})$ ，使得 $M$ 的长度为 $l$ 的整数倍，随后被分割为多个 -块，即 $\hat{M}=m_1\left|m_2\right| \cdots | m_s$ ，其中 $m_1, \ldots, m_s \in{0,1}^{\ell} \space h: \mathcal{X} \times \mathcal{Y} \rightarrow \mathcal{X}$ 是一个 哈希函数，被称为 $H$ 的压缩函数(compression functions)。 $\mathcal{Y}$ 是每个数据块 $m_i$ 的变量空间。 常数 $I V$ 为initial value。
消息被分成了很多个block，最开始的初始化向量和第一个block进行f操作，得到了的结果再和第二个block进行操作，如此循环进行，最终得到了最后的结果。
构建安全压缩函数，使得压缩函数是抗碰撞的。
现在的问题就是如何构造冲突避免的压缩函数 ℎ 。目前使用最频繁的构造方法是Davies-Meyer。
综上，当 |X| 足够大时，在ideal cipher model下，Davies-Meyer哈希函数 ℎ(DM)是冲突避免的。
SHA-256
SHA-256是Merkel-Damgard机制，还使用了Davies-Mayer压缩函数。
对于任意长度的消息，SHA256都会产生一个256位的哈希值，称作消息摘要。这个摘要相当于是个长度为32个字节的数组，通常有一个长度为64的十六进制字符串来表示，其中1个字节=8位，一个十六进制的字符的长度为4位。
哈希长度拓展攻击（Hash Length Extension Attack）是一种利用哈希函数的特性，在已知哈希值的情况下，计算出原始数据的扩展值的攻击方式。
攻击者可以通过构造特定的数据块，使得这些块的处理结果可以被利用来计算出原始数据的扩展值。
攻击步骤如下：
- 攻击者获取原始数据的哈希值和部分原始数据。
- 攻击者利用哈希函数的工作方式，计算出原始数据的哈希值中的中间状态，并将该中间状态保存下来。
- 攻击者构造一段数据块，使得这段数据块可以被加到原始数据的后面，并且构造的数据块中包含攻击者想要添加到原始数据末尾的内容。
- 攻击者利用保存的中间状态和构造的数据块，计算出原始数据加上构造数据块后的哈希值，从而得到原始数据的扩展值。
由于哈希函数的工作方式和输出长度是公开的，攻击者可以通过简单的计算来生成有效的扩展值，而不需要知道原始数据的内容。
HMAC
$$ \text { HMAC: } \quad S(k, m)=H(k \oplus o p a d | H(k \oplus i p a d ~ |m ~) ~) $$
这些密码本ipad 和opad，是固定的常数。标准中给出了。512位常数，永不改变。
Authenticated Encryption
认证加密是一个密码，通常是一个加密算法，取密钥，信息为输入，还可选一个新鲜值，输出一个密文，解密算法通常输出一个信息。但是这个解密算法可以输出一个特殊符号叫做底，当解密算法输出底时，意味着密文是无效的，应当被忽略，唯一的要求是这个底不在信息空间里，这个唯一的符号表示密文应当被拒绝。
证明，认证加密可以抵抗选择密文攻击。
他是一个极为强大的攻击者，他可以获得除了挑战密文外，任意密文的解密结果，但他依然不能区分他是在实验0还是实验中。
第一个例子在SSL协议里，SSL组合加密和MAC，希望能获得认证加密，组合方法如下：取密文m，然后计算明文m和MAC，使用MAC密钥kI，计算明文m的标签，然后你可以将标签附在明文后面，然后加密这个明文和标签的联结，得到最终的密文。这是一号方案。
第二个方案是在IPsec中，取明文，首先加密这个明文，然后计算得到的密文的标签，大家注意到这个标签是基于得到的密文计算的。
第三个方案是来自SSH协议的，这里，SSH取明文，使用CPA安全的加密机制加密明文。然后，把明文标签附在后面。IPsec与SSH不同之处在于，IPsec中，标签是根据密文计算的，在SSH中，标签是根据明文计算的。
SSH这种，因为MAC前面算法的输出会泄露明文中的一些位，不建议使用。
IPsec更为推荐。计算密文的标签时，我们用这个标签给密文上锁，确保没有人可以产生一个不同的密文，可以确保任何对密文的修改都会被解密者检测出来，因为MAC无法验证。
SSL, mac-then-enc
IPsec, enc-then-mac
SSH, enc-and-mac`
TLS
下面来看记录协议的工作细节，这里展示这个强制性的密码套件，加密使用 AES-CBC，MAC 使用 HMAC-SHA1。记住 TLS 使用了一个 MAC，然后加密。
我们看浏览器给服务器发送数据，使用的是从浏览器到服务器的密钥，这个密钥本身是由一个 MAC 密钥和一个加密秘钥组成，两个单独的密钥在会话起始阶段就被协商好了。所以总共来说有四个密钥，两个是 MAC 密钥，两个是加密秘钥，每个被使用在合适的方向。
蓝色部分是 TLS 数据包的结构图，它以一个报文头开始，包含了数据包的类型、协议版本号以及数据包的长度，注意到数据包的长度是以明文形式发送的。加密数据、加密特定记录时，
加密流程如下：取密钥，数据，当前状态为输入，然后如下工作。
首先是取 MAC 的实际的封装操作，可以看到报文头也在 MAC 的计算中，另外计数器的当前值也在 MAC 的计算中，当然所有计数器增加以表示有一个记录被发送了。及时计数器的值包含在标签里，但计数器的值实际上永远不会在记录中发送。他不用被放在记录里发送的原因是，另一端的服务器已经知道了计数器的值，所以它不需要在记录中被告知计数器的值，它隐性的知道这个值。当它要验证这个 MAC 时，它可以使用它认为的计数器的值来验证这个 MAC。
这些计数器具备新鲜值的功能，没有理由把新鲜值放在记录里，因为双方实际上都知道每个收到的记录的计数器。
标签计算的范围是图上这个三元组数据。
第二步是把标签附在数据后面，是先 MAC 加密，所以先计算了 MAC，这里会把数据和标签一并加密。所以报文头、数据和标签被补齐到 AES 分组。如果补齐的长度是 5 个字节，那么补齐就是简单的写 5 个 5。
第三步是用加密密钥来进行 CBC 加密，我们计算数据和标签的 CBC 加密，我们使用一个新鲜的随机 IV，它待会被嵌入到密文中。
最后，我们在结果前附上报文头、报文类型、版本号和长度。
CBC padding attacks
记得认证加密意味着系统提供 CPA 安全性，以及密文完整性。认证加密还意味着我们可以在有主动给攻击者存在的情况下，保持私密性，攻击者甚至不能以任何方式修改密文，且不被检测到。
我们还证明了认证加密可以阻止这些非常强大的选择密文攻击。不幸的是，认证加密有一个很重要的局限性，那就是它不能承受不好的实现。如果不正确的实现认证加密，那么你的实现对主动攻击将是脆弱的。
我们看标准机制，之前提到过这三个标准可以提供认证加密。实际中，当你需要使用认证加密时，你应该就使用这三个标准中的一个。我们不应该试图去自己实现认证加密。
一般情况下，当你想提供认证加密时，正确的方法是先加密然后再计算 MAC，因为无论你组合什么加密和 MAC 算法得到的结果将是认证加密。
首先，到来的密文是 CBC 加密的，然后接下来实现的程序会检查补齐格式是否正确，比如说，如果补齐长度是 5 个字节，格式应为 55555，如果格式不正确，那么密文被拒绝，这就是检查解密后的记录的末尾是否含有正确的补齐。如果补齐格式正确，那么接下来检查 MAC，检查信息标签，如果标签不正确，这个记录也会被拒绝。如果标签有效，那么剩下的数据被认为是可被认证的，于是交给应用。
由图中可以看出，在 21 毫秒内，密文会被拒绝，但是如果补齐有效，那么就要检查 MAC 了，发现 MAC 是无效的，警告仅在这点生成。换句话说，在这种情况下，会花稍微多一点的时间直到生成警告，可以看到，这平均花掉 23 毫秒。所以即使对付返回同样的警告，攻击者可以观察警告信息生成的用时，如果时间较短，他就知道补齐是无效的，如果时间较长，他就知道补齐有效，但 MAC 无效
ssh攻击
想法如下：假设攻击者截获了一个密文分组，即直接用 AES 加密的分组 m，现在攻击者想还原这个 m，强调一下，这个截获的密文只有一个分组长，一个 AES 分组。攻击者怎么办，向服务器发送一个数据包，数据包的开头是正常的，以一个序列号开头，然后他把他截获的密文 c 作为第一个分组，发送给服务器。现在，服务器该怎么办？服务器会解密第一个 AES 分组的前几个字节，他会把这前几个字节解读成数据包的长度域。接下来，服务器将期待着 len 这么多字节，在验证 MAC 之前，攻击者将一次只给服务器一个字节，这样服务器会一个字节，一个字节地读，最终，服务器会读到长度域里说的那么多的字节，他会检测 MAC 是否有效。当然，攻击者给服务器的字节都是随便弄的，因此 MAC 不会通过验证，服务器会发送一个 MAC 错误，但可以发现，攻击者在数他发送给服务器多少给字节。它能严格的知道他发送了多少个字节，当他接收到了服务器发来的 MAC 错误，这就告诉攻击者，密文 c 的前 32 位的解密结果，正好等于已经发送的字节数在看到 MAC 错误之前。那么这是一个非常聪明的攻击。
攻击者有一个密文分组 c，他想解密 c，我们假定 c 解密后，得到的明文的高 32 位是数字 5，在这种情况下，攻击者会看到如下的事情。服务器会解密挑战分组 c，会得到数字 5，并把 5 当作长度域。那么现在，攻击者会给服务器一次一个字节，在攻击者给服务器 5 个字节后，服务器说：我刚刚还原了整个数据包，让我检查 MAC。MAC 很可能是错的，服务器会发送一个坏 MAC 的错误。那么在读了 5 个字节后，攻击者会看到一个坏 MAC 的错误，然后攻击者就知道了解密后的分组的高 32 位等于数字 5. 那么就知道了 c 的高 32 位。这是一个非常重要的攻击，因为攻击者刚刚知道了密文分组解密后的高 32 位，他可以对任何他想要的密文分组实施这个攻击，他可以知道一条长信息的每个密文分组的高 32 位。
密码设计里有两个错误，第一个是，解密操作不是原子操作，换句话说，解密算法不取整个数据包作为输入，而返回整个明文作为输出，或者返回 “拒绝”，解密算法部分的解密了密文获得了长度域，然后等待指定数量的字节去还愿，然后完成了加密过程。这些非原子解密操作是很危险的，一般来说，需要避免使用他们。在这个例子里，这个非原子操作正好破坏了认证加密。
另一个问题在于，在正确的认证之前，就使用了长度域，这是另一个错误之处，不应该这么做的。所以加密的数据域不应该被使用在这个域被正确认证之前。
秘钥分发 KDF
HMAC
HMAC
·
PBKDF
首先，我们讨论密钥推导时，HKDF机制在2010年Hugo Krawczyk的文章里有所描述。
确定性加密，SIV模式在第二篇论文里有所讨论。
我们描述了EME模式，可以让我们构建一个宽分组的伪随机置换，EME模式在Halvi和Rogaway的论文里描述。
微调分组密码，引入了用于硬盘加密的XTS模式，在第四篇论文里描述。
最后，保格式加密在最后一篇论文里描述。
数论
乘法逆元
在中国剩余定理的计算里，需要求一个数字在一个模下的逆元，也就是对于给定的 $a ， b$ ，找到方 程 $a a^* \equiv 1(\bmod b)$ 的一个整数解 $a^$ 。接下来我们分析一下这个方程背后隐藏着什么。 根据同余的定义，有 $b \mid\left(a a^-1\right)$ ，也就是存在整数 $k$ 使得 $b k=a a^-1$ 。移一下项，就得 到了 $a a^-b k=1$ 。 这个形式恰好符合裴蜀定理 $a x+b y=1$ 的形式，于是 $(a, b)=1$ ，这表明 $\mathbf{a}$ ， $\mathbf{b}$ 互质是逆元 存在的必要条件。同样可以证明： $a$,b互质是 $a$ 在模 $b$ 下存在逆元的充分条件。
扩展欧几里得
费马小定理
费马小定理: $p$ 为质数， $a$ 为任意自然数，则
$a^p \equiv a(\bmod p)$
陷门函数PK加密
公钥与私钥的产生 叚设Alice想要通过不可靠的媒体接收Bob的私人信息。她可以用以下的方式来产生一个公钥和一个私钥:
-
随意选择两个大的素数 $p$ 和 $q ， p$ 不等于 $q$ ，计算 $N=p q$ 。
-
根据欧拉函数，求得 $r=\varphi(N)=\varphi(p) \times \varphi(q)=(p-1)(q-1)$
-
选择一个小于 $r$ 的整数 $e$ ，使 $e$ 与 $r$ 互质。并求得 $e$ 关于 $r$ 的模逆元，命名为 $d$ (求 $d$ 令 $e d \equiv 1(\bmod r)$ )。 (模逆元存在，当且仅当 $e$ 与 $r$ 互质)
-
将 $p$ 和 $q$ 的记录销毁。 $(N, e)$ 是公钥， $(N, d)$ 是私钥。Alice将她的公钥 $(N, e)$ 传给Bob，而将她的私钥 $(N, d)$ 藏起来。
加密消息 叚设Bob想给Alice送消息 $m$ ，他知道Alice产生的 $N$ 和 $e$ 。他使用起先与Alice约好的格式将 $m$ 转换为一个小于 $N$ 的非负整数 $n$ ，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。 叚如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为 $n$ 。用下面这个公式他可以将 $n$ 加密为 $c$ : $$ c=n^e \bmod N $$ 计算 $c$ 并不复杂。Bob算出 $c$ 后就可以将它传递给Alice。 解密消息 Alice得到Bob的消息 $c$ 后就可以利用她的密钥 $d$ 来解码。她可以用以下这个公式来将 $c$ 转换为 $n$ : $$ n=c^d \bmod N $$ 得到 $n$ 后，她可以将原来的信息 $m$ 重新复原。 解码的原理是 $$ c^d \equiv n^{e \cdot d}(\bmod N) $$ 已知 $e d \equiv 1(\bmod r)$ ，即 $e d=1+h \varphi(N)$ 。那么有 $$ n^{e d}=n^{1+h \varphi(N)}=n \cdot n^{h \varphi(N)}=n\left(n^{\varphi(N)}\right)^h $$ 若 $n$ 与 $N$ 互素，则由欧拉定理得: $$ n^{e d} \equiv n\left(n^{\varphi(N)}\right)^h \equiv n(1)^h \equiv n \quad(\bmod N) $$ 若 $n$ 与 $N$ 不互素，则不失一般性考虑 $n=p h$ ，以及 $e d-1=k(q-1)$ ，得: $$ \begin{aligned} & n^{e d}=(p h)^{e d} \equiv 0 \equiv p h \equiv n \quad(\bmod p) \ & n^{e d}=n^{e d-1} n=n^{k(q-1)} n=\left(n^{q-1}\right)^k n \equiv 1^k n \equiv n \quad(\bmod q) \end{aligned} $$ 故 $n^{e d} \equiv n \quad(\bmod N)$ 得证。
Bleichenbacher
攻击过程如下：
- 攻击者选择一个明文 M，并将其用 PKCS#1 v1.5 方式进行填充，得到一个长度为 k 的消息 m。攻击者将该消息使用 RSA 加密算法进行加密，得到密文 c。
- 攻击者通过 padding oracle 来判断密文是否符合 padding 方式。padding oracle 可以是一个网络服务器或者其他的加密解密设备，能够根据密文是否符合 padding 方式返回不同的信息，例如返回错误码或者异常。
- 攻击者使用二分法来逐位猜测密文中的每一个字节。具体来说，攻击者将密文 c 解密得到明文 m’，并检查其是否符合 PKCS#1 v1.5 的填充规则。如果符合，说明攻击者已经猜测到了正确的字节，否则说明攻击者猜错了。
- 攻击者利用 padding oracle 来判断 m’ 是否符合 PKCS#1 v1.5 的填充规则。如果符合，说明攻击者已经还原出了正确的明文 M，否则说明攻击者猜错了。
- 重复步骤 3 和步骤 4，直到攻击者还原出了明文 M。
- Padding: RSA加密时，要对明文m填充到与模数 $n$ 一样长，才能加密
- Ciphertext manipulation： RSA 在乘法上是同态的，即 $\operatorname{Enc}\left(P_1 * P_2\right)=\operatorname{Enc}\left(P_1\right) * \operatorname{Enc}\left(P_2\right)$ ，通常的实现都没有对RSA的 密文做完整性校验 (MAC)，使得攻击者可以通过修改密文来操纵解 密后的明文
- Information leakage: 攻击者可以通过一些侧信道信息来获知解密 后的明文是否符合特定的填充格式
Elgamal
密钥生成 [编辑] 密钥生成步骤如下:
-
Alice利用生成元 $g$ 产生一个 $q$ 阶循环群 $G$ 的有效描述。该循环群需要满足一定的安全性质。
-
Alice从 ${1, \ldots, q-1}$ 中随机选择一个 $x$ 。
-
Alice计算 $h:=g^x$ 。
-
Alice公开 $h$ 以及 $G, q, g$ 的描述作为其公钥，并保留 $x$ 作为其私钥。私钥必须保密。
加密
-
使用Alice的公钥 $(G, q, g, h)$ 向她加密一条消息 $m$ 的加密算法工作方式如下:
-
Bob从 ${1, \ldots, q-1}$ 随机选择一个 $y$ ，然后计算 $c_1:=g^y$ 。
-
Bobi十算共享秘密 $s:=h^y$ 。
-
Bob把他要发送的秘密消息 $m$ 映射为 $G$ 上的一个元素 $m^{\prime}$ 。
-
Bobi计算 $c_2:=m^{\prime} \cdot s$ 。
-
Bob将密文 $\left(c_1, c_2\right)=\left(g^y, m^{\prime} \cdot h^y\right)=\left(g^y, m^{\prime} \cdot\left(g^x\right)^y\right)$ 发送给Alice。 值得注意的是，如果一个人知道了 $m^{\prime}$ ，那么它很容易就能知道 $h^y$ 的值。因此对每一条信息都产生一个新的 $y$ 可以提高安全性。所以 $y$ 也被称作临时密钥。 解密 利用私钥 $x$ 对密文 $\left(c_1, c_2\right)$ 进行解密的算法工作方式如下:
-
Alice计算共享秘密 $s:=c_1^x$
-
然后计算 $m^{\prime}:=c_2 \cdot s^{-1}$ ，并将其映射回明文 $m$ ，其中 $s^{-1}$ 是 $s$ 在群 $G$ 上的逆元。（例如：如果 $G$ 是整数模n乘去群的一个子群，那么逆元就是模逆元) 。 解密算法是能够正确解密出明文的，因为
$$ c_2 \cdot s^{-1}=m^{\prime} \cdot h^y \cdot\left(g^{x y}\right)^{-1}=m^{\prime} \cdot g^{x y} \cdot g^{-x y}=m^{\prime} . $$
DF
Diffie-Hellman密钥交换算法 Diffie-Hellman密钥交换算法的目的是使两个用户能安全交换密钥，以便在后续的通信中用该密钥对消息加密。所以这个算法本身只限于密钥交换。
Diffie-Hellman密钥交换算法的有效性建立在离散对数上，在计算离散对数是困难的才能确保秘密交换。
Diffie-Hellman密钥交换算法如图所示
有素数 $q$ 和本原根 $\alpha$ ，为公开的整数，Alice选择随机整数 $X_A ，$ Bob选择 $X_B$ ，分别计算，其中 $X_A$ 和 $X_B$ 保密，对算出的 $Y_A$ 和 $Y_B$ 公开。Alice和Bob通过计算 $K$ ，将 $K$ 作为共享的密钥。这样Alice和Bob就 完成了密钥的交换。 $X_A$ 和 $X_B$ 是私有的，攻击者只能通过 $q, \alpha, Y_A$ 和 $Y_B$ 来攻击，所以只能求离散对数 来确定密钥。 如果攻击者要对Bob进行攻击，攻击者就要求离散对数算出 $X_B=d \log _{\alpha, q}\left(Y_B\right)$ ，然后算出密钥 $K$ 。 Diffie-Hellman密钥交换算法的安全性建立在下列事实上:
-
计算素数模的幂运算相对容易，计算离散对数却非常困难
-
对大素数，求离散对数被认为是困难的
基于这样的事实，保证了Diffie-Hellman密钥交换算法的保密性。
中间人攻击 上图的协议，不能抵御中间人攻击，中间人攻击的过程如下图所示
通过上述协议，Bob和Alice以为各自共享了密钥，实际上他们都是与Darth共享密钥，所以如果Alice和Bob通过共享密钥加密传输，将会泄露各自的明文
密钥交换不能抵御上述攻击，是因为没有对通信的参与方进行认证。
扩展域GF(2^m)
加法
假设A(x)、B(x)∈GF(2^m)，计算两个元素之和的方法就是： $$ C(x)=A(x)+B(x)=\sum_{i=0}^{m-1} C_i x^i \quad c_i \equiv\left(a_i+b_i\right) \bmod 2 $$ 而两个元素之差的计算公式就是: $$ C(x)=A(x)-B(x)=\sum_{i=0}^{m-1} c_i x^i \quad c_i \equiv\left(a_i-b_i\right) \bmod 2 \equiv\left(a_i+b_i\right) \bmod 2 $$
乘法
不可约多项式
参考文献
1.ECB模式解读_chengqiuming的博客-CSDN博客_ecb模式
2.密码算法 之三：分组密码工作模式 （ECB \ CBC \ CFB \ OFB \ CTR \ XTS）浅析_cbc工作模式_KXue0703的博客-CSDN博客
3.密码学小知识(5)：唯密文攻击(COA)、已知明文攻击(KPA)、选择明文攻击(CPA)，选择密文攻击(CCA)_crypto_cxf的博客-CSDN博客