现代密码学总结（上篇）

现代密码学总结

（v.1.0.0版本）之后会更新内容

基本说明：

$\bullet$如果$A$是随机算法，$y\leftarrow A(x)$表示输入为$x$ ,通过均匀选择
的随机带运行$A$,并且将输出赋给$y$。
$\bullet$如果$S$是个集合，则$x\leftarrow S$表示$x$是从$S$中均匀随机选择
的。
$\bullet$ { 0 , 1 } n \{ 0, 1\} ^n {0,1}n表示的是所有长度为$n$的比特串的集合。
$\bullet$ { 0 , 1 } ≤ n \{ 0, 1\} \leq n {0,1}≤n表示的是所有长度大于 0 且最大为$n$ 的比特串的集合
$\bullet$ { 0 , 1 } ∗ \{ 0, 1\} ^* {0,1}∗表示的是所有长度大于${}^0$ 的有穷比特串的集合。
$\bullet$ $||x||$表示(正)整数$x$表示为二进制形式时的长度，首位比特为
1。注意$\log x<||x||\le \log x+1.$
$\bullet$ $|x|$表示的是二进制字符串$x$ (可能首部有多位为零)的长度或者表示实数$x$的绝对值。
$\bullet$ $x||y$ 和$\left(x,y\right)$等价，表示连接字符串 $x$ 和 $y$ 。$\bullet$ $Pr[X]$表示的是事件$X$的概率。
$\bullet$ $x:=y$意味着将值$y$赋值给$x$ 。
$\cdot$ $PPT$代表概率多项式时间。
$\bullet$ $A^{O(\cdot )}$表示的是访问预言机$O$ 的算法 A。
$\bullet$ $k$通常表示一个密钥。
$\bullet$ $(pk,sk)$公钥/私钥密钥对
$\bullet$ $negl$ 表示可忽略函数。
$\bullet$ $poly(n)$表示任意一个多项式。
$\bullet$ $Fun{c}_n$表示函数的集合，这些函数将$n$比特串映射到${}^n$比特串。
$\bullet$ $G$表示的是一个伪随机数产生器。
$\bullet$ $F$表示的是一个带密钥的函数，该函数通常是伪随机函数或者伪随机置换。
$\bullet$ $(Gen,Enc,Dec)$分别表示密钥生成、加密、解密过程，在公钥加 密 和 对 称 加 密 中 使 用 。
$\bullet (Gen,Mac,Vrfy)$ 分 别 表 示 的 是 在 消 息 鉴 别 码 中 , 密 钥 生 成 过程，鉴别标签生成过程和验证过程。
$\bullet$ $(Gen,Sign,Vrfy)$分别表示的是在数字签名方案中，密钥生成过程，签名生成过程和签名验证过程。
$\bullet$ $\mathbb{Z}$ 表 示 整 数 集 合 。
$\bullet$ $a|b$表示a整除b。
$\bullet$ ${\mathbb{Z}}_N$表示模$N$的加法群
$\bullet$ ${\mathbb{Z}}_N^{\ast }$表示模$N$可逆整数乘法群，也可以叫做模$N$的简化剩余系
$\bullet$ $\varphi (N)$表示的是${\mathbb{Z}}_N^{\ast }$中元素的个数，也就是欧拉函数
$\bullet$ $g$通常是群的一个生成元（循环群）。
$\bullet$ PRG（伪随机数生成器）
$\bullet$ 伪随机函数（PRF）
$\bullet$ 伪随机置换函数（PRP）
注意：凡是标记*都是重点内容

简介

加密：

定义：使得通信双方（发送方、接收方）能在公开网络上进行机密通信。消息发送方（接收方）能够加密（解密）消息，而窃听者无法获得关于消息的任何信息。

分类：
对称加密：发送方和接收方共享相同的密钥，加密和解密使用相同的密钥。
公钥加密：接收方拥有一对公私钥，发送方使用公钥加密，接收者使用私钥解密。（公钥加密，私钥解密）

消息认证码

可以保护通信内容的完整性。
消息发送方和接收方首先共享一个密钥，发送方为待发送的消息产生一个标识，并将消息和标识一同发送给接收方。接收方使用密钥验证标识的有效性，若验证通过，则说明消息在传递过程中没有被篡改。

哈希函数

哈希函数能够将任意长的消息映射为一个“较短的” “定长的” “抗碰撞的” 消息摘要。
抗碰撞的：
1.不同消息的消息摘要不同。
例：
对消息 “Hello, world!” 计算哈希值，得到 abc123。
对消息 “Hello, world?” 计算哈希值，得到 def456。

2.给定消息摘要，恢复出消息本身是困难的。（单向）
例：例如，假设攻击者获得了哈希值 abc123，他们无法轻易恢复出 “Hello, world!” 这一原始消息，因为哈希是单向的，不存在直接的逆操作。

数字签名

保证了被签名消息的完整性和不可否认性。（类似于手写签名）

发送者使用自己的私钥对消息进行签名，接收者使用签名者的公钥验证数字签名的合法性。（私钥签名，公钥验证）。数字签名可以看作是公钥环境下的消息认证码。

现代密码学范畴

Without attempting to provide a complete characterization,we would say that modern cryptography involves the study of mathematical techniquesfor securing digital information, systems, and distributed
computations against adversarial attacks.
——Jonathan Katz, Yehuda Lindell
《Introduction to Modern Cryptography》

In the wide sense, cryptography is concerned with any problem in which one wishes to limit the effects of dishonest users.
——Oded Goldreich
《Foundations of Cryptography Basic Tools》

语法

$\mathcal{K}：$密钥空间
$\mathcal{M}$：明文空间
$\mathcal{C}$：密文空间
加密方案(Gen; Enc; Dec)
1.$Gen\to \mathcal{K}\left(\text{概 率 性 的 }\right)$密钥生成算法。
2.$Enc:\mathcal{K}\times \mathcal{M}\to \mathcal{C}$加密算法。
3.$Dec:\mathcal{K}\times \mathcal{C}\to \mathcal{M}$解密算法。
正确性：$$\forall k\in \mathcal{K},m\in \mathcal{M}:De{c}_k(En{c}_k(m))=m$$

Kerckhoffs原则*

The cipher method must not be required to be secret, and it must be
able to fall into the hands of the enemy without inconvenience.

密码算法的安全性应该依赖密钥k的保密性, 而不应依赖于算法Gen; Enc; Dec的保密性。

理由:

1. 算法设计保密是不切实际的（逆向工程）。
2. 短密钥更容易保护、生成和替换。
3. 密码设计应该被公开讨论和分析。

古典密码

单表代换密码

移位密码*
M = C = { A , B , . . . , Z } ∗ ∼ { 0 , . . . , 25 } ∗ \mathcal{M}=\mathcal{C}=\{A,B,...,Z\}^*\sim\{0,...,25\}^* M=C={A,B,...,Z}∗∼{0,...,25}∗
K = { 0 , . . . , 25 } \mathcal{K}=\{0,...,25\} K={0,...,25}
$\begin{array}{r}{\mathsf{Enc}}_k(m_1\cdots m_{\ell })=c_1\cdots c_{\ell }\text{,其中 }{c}_i=m_i+k\mathrm{mod}26\end{array}$ ${\mathbf{Dec}}_k(c_1\cdots c_{\ell })=m_1\cdots m_{\ell }\text{, 其 中 }{m}_i=c_i-k$ mod 26

当k=3:便是熟悉的凯撒密码


攻击：
加密改变了字母的频率。
$p_i:\text{在正常的英语文本中，第}i$个字母出现的频率。
$q_i:$密文中第$i$个字母出现的频率。
$\begin{array}{c}{\sum }_{i=0}^{25}{p}_i^2\approx 0.065\\ \text{可以观察到：}\end{array}$

$$\sum _{i=0}^{25}{p}_i\cdot q_{i+j\text{ mod 26}}\approx \sum _{i=0}^{25}{p}_i^2\approx 0.065\text{ 当且仅当}j=k$$

仿射密码：
M = C = { A , B , … , Z } ∗ ∼ { 0 , … , 25 } ∗ K = { ( a , b ) ∣ ( a , 26 ) = 1 , 0 ≤ a , b ≤ 25 } E n c ⁡ k ( m 1 ⋯ m ℓ ) = c 1 ⋯ c ℓ , 其中  c i = a m i + b m o d 26 D e c ⁡ k ( c 1 ⋯ c ℓ ) = m 1 ⋯ m ℓ , 其中  m i = a − 1 ( c i − b ) m o d 26 ,  a a − 1 ≡ 1 m o d 26 \\\begin{array}{l}\\ \mathcal{M}=\mathcal{C}=\{A,B,\ldots,Z\}^{*}\sim\{0,\ldots,25\}^{*}\\ \\ \mathcal{K}=\{(a,b)\mid(a,26)=1,0\leq a,b\leq25\}\\ \\ \operatorname{\mathrm{Enc}}_{k}\left(m_1\cdots m_{\ell}\right)=c_1\cdots c_{\ell},\text{ 其中 }c_{i}=am_{i}+b\bmod26\\ \\ \operatorname{\mathrm{Dec}}_{k}\left(c_1\cdots c_{\ell}\right)=m_1\cdots m_{\ell},\text{ 其中 }m_{i}=a^{-1}\left(c_{i}-b\right)\bmod26\text{, }\\ \\ aa^{-1}\equiv1\bmod26\end{array}\\ M=C={A,B,…,Z}∗∼{0,…,25}∗K={(a,b)∣(a,26)=1,0≤a,b≤25}Enck​(m1​⋯mℓ​)=c1​⋯cℓ​, 其中 ci​=ami​+bmod26Deck​(c1​⋯cℓ​)=m1​⋯mℓ​, 其中 mi​=a−1(ci​−b)mod26, aa−1≡1mod26​

关键计算$a^{-1}$，用扩展欧几里得除法

单表代换密码：
M = C = { A , B , . . . , Z } ∗ ∼ { 0 , . . . , 25 } ∗ \mathcal{M}=\mathcal{C}=\{A,B,...,Z\}^*\sim\{0,...,25\}^* M=C={A,B,...,Z}∗∼{0,...,25}∗
$\mathcal{K}=Sym(\mathcal{M})=\mathcal{M}$的所有置换。
$$\begin{gathered} {\mathsf{Enc}}_k(m_1\cdots m_{\ell })=k(m_1)\cdots k(m_{\ell }) \\ {\mathsf{Dec}}_k(c_1\cdots c_{\ell })=k^{-1}(c_1)\cdots k^{-1}(c_{\ell }) \end{gathered}$$

攻击：
$|\mathcal{K}|=26!\ge 2^{88}$足够大！
给定英文文本（任何大致知道字母分布的其他文档）的密文，我们可以计算出置换。大密钥空间是必要的（以避免暴力破解攻击），但肯定不足以保证安全性！

多表代换密码

Vigene˙re维吉尼亚密码：

选择一串字符作为密钥，明文字符“加上”密钥字符得到密文字符，（必要时折回）。

（例如：第一个V->第t列第c行->V）

攻击：
确定密文中长度为2或者3的重复模式
巧合指数法

可证明安全理论

现代密码学基于可证明安全。

1. 提供安全目标和威胁模型的形式化安全定义（Security
   deffnition）。
2. 明确地说明所需要的假设（Assumption）。
3. 提供安全性证明（Security proof），证明算法构造在某
   些假设下达到了定义。

安全目标*

安全定义 = 安全目标 + 威胁模型

安全目标：

敌手知道$c=En{c}_k(m)$
1.敌手不应该得到密钥k。【X】（明文问题）
原因：$En{c}_k(m)=m$显然不安全
2.给定c，很难恢复整个明文m。【X】（明文问题）
原因：只加密前半部分$En{c}_k(m1,m2)=En{c}_k(m1),m2$显然不安全
3.给定c，很难恢复m的任何字符。【X】（关系）
它无法保证敌手在不获得任何特定字符的情况下
得到明文的某些关系，例如$En{c}_k(m),En{c}_k(m^{{}^{\prime }}),敌手能够获知m>m^{{}^{\prime }}$,这在有些场景下是不可接受的。

不管攻击者已经掌握了什么信息，密文都不应该泄露任何有关底层明文的额外信息。 ----------------------正确的安全目标

威胁模型*：

唯密文攻击： 最基本的攻击。敌手只能得到一个或多个密
文。
已知明文攻击： 敌手能够获得明/密文对。他的目标是推
断使用相同密钥产生的其他密文中包含的明文信息。
选择明文攻击： 敌手能够获得其任意选择的明文对应的密
文。
选择密文攻击： 敌手还可以额外获得其任意选择的密文对
应的明文。
威胁模型需要与部署方案的环境相匹配。

困难假设：
为了证明安全性，我们需要一些“困难假设”。

安全证明保证了在某种难题假设下，针对某种威胁模型下的敌手，我们可以达到某种安全目标。

对称加密

完善保密性（${\mathsf{PrivK}}_{\mathcal{A},\Pi }^{\mathsf{eav}}$）

1.m的分布和$En{c}_k(m)$的分布独立。
2.拥有无限计算能力的窃听者绝对不会获得关于M的任何信息，这样的安全性也被称为信息论安全（Information-theoretic security）。
3.密钥要和消息一样长*。
4.密钥不能复用！
5.大多数情况下如此强的安全保障是没必要的。

窃听者存在下不可区分加密：（定义*）
1.$\Pi =($Gen,Enc,Dec)具有完善不可区分性(等价于 完善保密性)当且仅当对任意敌手$\mathcal{A}$有：$\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{\text{eav}}=1]=1/2.$
2.$\Pi =($Gen,Enc,Dec) 在窃听者存在的情况下具有不可区分加密，如果对于任意 PPT 敌手$\mathcal{A}$：
$\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{\text{eav}}(n)=1]\le 1/2+$negl$(n).$
3.$\Pi =(Gen,Enc,Dec)$具备在窃听者存在的情况下的不可区分加密当且仅当对所有多项式时间敌手$\mathcal{A}$
Pr[out${}_{\mathcal{A}}($Priv${\mathrm{K}}_{\mathcal{A},\Pi }^{\text{eav}}(n,0))=1]-$Pr[out${}_{\mathcal{A}}($Priv${\mathrm{K}}_{\mathcal{A}},{\Pi }^{\text{eav}}(n,1))=1]|\le$negl$(n).$

我们将定义完善保密性的一个计算变种，其中
1.我们只考虑针对计算能力受限敌手的安全性。
2.我们允许敌手有微小的（即忽略不计的）优势，而不是“完美” 保密。
3.加密消息可以任意长！ Shannon限定不适用于计算设定。
4.保留加密密钥只能使用一次的要求。

计算安全

目标:不能被合理的计算能力以合理的概率破解。
1.仅对计算能力受限的敌手安全。
2.安全性会以极小的概率被攻破。

定义方式：
具体方法（Concrete approach）：
讨论具体实例化的安全性。通过明确限定任意（随机）敌手在最多某个特定时间内的最大成功概率，对一个给定的密码学方案的安全性进行量
化。

一个方案是(t, ε)-安全，如果任意一个运行时间最多为t的 敌手，能够以最多为ε的概率成功攻破该方案

具体方法在实际中很重要，但是很难精确地给出具体安全性定义（即给出精确的t和ε）。在一些极端情况下，给定的t和ε可能会失效。
1.精确的运行时间不是很可靠。
2.依赖于硬件的底层构造并且随时间的变化（摩尔定律）。
3.没有考虑并行化或其他计算模式的演进。

于是有：
一个算法的t个步骤 → “有效的计算”
ε → “非常接近于0”的值
也就是：
渐进方法（Asymptotic approach）：
利用计算复杂性理论的思想。
( 引 )
可忽略函数：
函数 $f:\mathbb{N}\to \mathbb{R}$是可忽略的，如果对于每个多项式$p(\cdot )$,存在一个整数$N$,使得对于所有的整数$n\ge N$,满

足$f(n)\le \frac{1}{p(n)}$,即$\forall$多项式$p(\cdot ),\exists N$使得$\forall n>N:f(n)<1/p(n).$简单来说，定义 3.4可表述为对于任意多项式$p$和所有足够大的值$n$,满足$$f(n)<1/p(n).$$

一个方案是安全的当且仅当任意多项式敌手（PPT）以可忽略的概率成功攻破一个方案。

典型的渐进安全的陈述：

一个密码方案Π是安全的，当且仅当某些底层的假设或者
组件π是安全的。

一个对称加密方案是概率多项式时间算法(Gen, Enc, Dec)的三元组：
1.密钥生成：$k_1\leftarrow$Gen$(1^n)$将安全参数$n$(一元形
式输入$)$映射为密钥$k.$典型地，Gen$(1^n)$输出$k$,$k$在 { 0 , 1 } n \{0,1\}^n {0,1}n均匀一致选取的，我们假设$|k|\ge n.$
2.加密：(概率的)加密算法Enc将$k$和$m\in {0,1}^{\ast }$映射为密文$c\leftarrow {\mathsf{Enc}}_k(m){.}^{\mathbf{b}}$
3.解密：
$m:=\mathbf{D}e{c}_k(c)\text{是 确 定 性 算 法 。 }$
正确性：
对于所有有效的安全参数 n 和所有 m ∈ { 0 , 1 } ∗ Pr ⁡ [ m = D e c k ( E n c k ( m ) ) ∣ k ← G e n ( 1 n ) ] = 1. \text{对于所有有效的安全参数}n\text{和所有}m\in\{0,1\}^*\\\Pr[m=\mathsf{Dec}_k(\mathsf{Enc}_k(m))\mid k\leftarrow\mathsf{Gen}(1^n)]=1. 对于所有有效的安全参数n和所有m∈{0,1}∗Pr[m=Deck​(Enck​(m))∣k←Gen(1n)]=1.

注：
计算安全加密方案甚至会泄露明文长度*
一个对称加密算法具备不可区分加密，当且仅当它是语义安全的。

PRG（伪随机数生成器）

伪随机性：
非正式地讲，一个分布是伪随机的，如果不能有效区分一个从该分布中选取的样本和一个从均匀随机分布中选取的
样本。
定义 一个分布序列 { \{ {D$is{t}_n{\}}_n\in \mathbb{N}-$ 其中 { \{ {D$is{t}_n\}=\ell (n)$对于某个多项式 $\ell -$是伪随机的，当且仅当对所有PPT区分
者$\mathcal{D}$,有
$$\left|\mathrm{Pr}[\mathcal{D}(U_{\ell (n)})=1]-\mathrm{Pr}[\mathcal{D}({\mathrm{Dist}}_n)=1]\right|\le \mathrm{negl}(n),$$
PRG：
一个(确定性的)多项式算法
G : { 0 , 1 } n → { 0 , 1 } ℓ ( n ) G:\{0,1\}^n\to\{0,1\}^{\ell(n)} G:{0,1}n→{0,1}ℓ(n)
是一个伪随机数生成器
当且仅当
1.(扩展性)$\forall n:\ell (n)>n.$
2. ( 伪随机性 ) { G ( U n ) } n ∈ N 2. ( 伪 随 机 性 ) \{ G( U_n) \} _{n\in \mathbb{N} } 2.(伪随机性){G(Un​)}n∈N​是伪随机分布序列。

注：
1.PRG的输出与均匀一致相去甚远。
2.PRG存在当且仅当单向函数存在。

一次一密*

参数$t\in \mathbb{N}$
M = K = C = { 0 , 1 } t . \mathcal{M}=\mathcal{K}=\mathcal{C}=\{0,1\}^t. M=K=C={0,1}t.
$\bullet$ Gen均匀一致随机选取$k\in \mathcal{K}.$
$\bullet$ Enc${}_k(m)=m\oplus k.$
$\bullet$ ${\mathrm{Dec}}_k(c)=c\oplus k.$

方案 使用PRG G : { 0 , 1 } n → { 0 , 1 } ℓ ( n ) . G:\{0,1\}^n\to\{0,1\}^{\ell(n)}. G:{0,1}n→{0,1}ℓ(n).
安全参数$n\in \mathbb{N}$
K = { 0 , 1 } n \mathcal{K}=\{0,1\}^n K={0,1}n
M = C = { 0 , 1 } ℓ ( n ) . \mathcal{M}=\mathcal{C}=\{0,1\}^{\ell(n)}. M=C={0,1}ℓ(n).
$\bullet$Gen 均匀一致随机选取$k\in \mathcal{K}.$
$\bullet$ Enc${}_k(m)=m\oplus G(k).$
$\bullet$ Dec${}_k(c)=c\oplus G(k).$

定理：如果G是一个伪随机数生成器，那么方案是在窃听者存在情况下具备不可区分加密的定长的对称加密算法。

归约证明

归约证明：假设存在$\mathcal{A}$能够攻破某些方案，那么我们可以构
造${\mathcal{A}}^{{}^{\prime }}$，使其能够攻破底层组建或解决底层计算困难问题。

证明：

证明概述：我们有 Pr$[{\tilde{b}}^{\prime }=1\mid \tilde{b}=0]=\mathrm{Pr}[b=b^{\prime }\mid \tilde{b}=0]=1/2$因为
$X_{\tilde{b}}\sim U_{\ell (n)}$和一次一密具有完善保密性。
$\mathsf{Pr}[{\tilde{b}}^{{}^{\prime }}=1|\tilde{b}=1]=\mathsf{Pr}[\mathcal{A}({\mathsf{Enc}}_k(m_b))=b|(m_0,m_1)\leftarrow \mathcal{A},b\leftarrow U_1]$
$\le 1/2+p(\underline{n}).$
如果$\mathcal{A}$攻破加密方案$\Rightarrow p(n)$不是negl$(n)\Rightarrow$
|Pr$[{\tilde{b}}^{\prime }=1\mid \tilde{b}=0]-$Pr$[{\tilde{b}}^{\prime }=1\mid \tilde{b}=1]|=p(n)$是不可忽略的$\Rightarrow$与$G$的安全性相矛盾，因为 ${\mathcal{A}}^{\prime }$攻破了它！!因此$\mathcal{A}$不存在。

CPA安全（选择明文攻击）*：

• 非适应性(non-adaptively)选择明文攻击：所有要加密的消息必须由敌手一次性选择
• 适应性 (adaptively)选择明文攻击：消息可以由敌手适应性地选择。

IND-CPA安全*：

$\Pi =($Gen,Enc,Dec)是(适应性$)IND-CPA$安全，
如果任意PPT敌手
$\begin{array}{r}\mathsf{Pr}[{\mathsf{PrivK}}_{\mathcal{A},\Pi }^{\text{сра}}(n)=1]\le 1/2+\mathsf{negl}(n).\end{array}$

伪随机函数（PRF）

·伪随机数生成器：有效地扩展一个随机种子，其输出不能和均匀一致地选取的随机字符串区分。
·伪随机函数：一个带密钥的，高效可计算的函数，该函数和随机函数不可区分。

解释：2.安全：带密钥的函数和随机函数不可区分。

伪随机置换函数（PRP）

置换（Permutation）是一种特殊的映射，其中每个输入元素都有一个唯一的输出元素，并且所有输入元素的输出都是不同的。对于伪随机置换函数而言，它要求输入的每个值都可以通过某种方式得到一个唯一的输出（即每个输入被“重新排列”到输出中）。关键在于，虽然该函数的行为满足置换的定义，但它的“随机性”是通过加密算法模拟的。

注： 如果F是一个伪随机置换并且满足${\ell }_{in}(n)\ge n$,那么F是一个伪随机函数。

强伪随机置换函数

对于置换，除了计算置换本身，还要计算置换的逆。如果允许区分器访问逆置换预言机，PRP仍是安全的，这样的PRP被称为强PRP (Strong PRP)。
定义：F: { 0 , 1 } ℓ k e y × { 0 , 1 } ℓ i n → { 0 , 1 } ℓ o u t \{0,1\}^{\ell_{key}}\times\{0,1\}^{\ell_{in}}\to\{0,1\}^{\ell_{out}} {0,1}ℓkey​×{0,1}ℓin​→{0,1}ℓout​是一个高效的带密钥的置换。F是一个强伪随机置换 (PRP),如果对于多项式时间区分器，存在一个可忽略函数negl，使得：
$$|\mathsf{Pr}[{\mathcal{D}}^{\mathsf{F}(k,\cdot ),{\mathsf{F}}^{-1}(k,\cdot )}=1]-\mathsf{Pr}[{\mathcal{D}}^{f(\cdot ),f^{-1}(\cdot )}=1]|\le \mathsf{negl}(n).$$

一个利用PRFs/PRPs的CPA安全方案：

安全性证明：
Game0：

Game1：

流密码和分组密码

注：Block cipher 不是一种加密方案！
在实际中，PRG是使用流密码实例化的。
PRP是使用分组密码进行实例化的。实际上，PRP也被称为分组密码。

具体内容（略）
永远不要使用！EBC（电码本）模式

CBC模式

IV是初始向量

如果F是伪随机置换*，那么CBC模式是CPA-安全的。
F是伪随机置换。CBC模式的主要缺点是必须按顺序进行加密。

链式CBC

链式CBC模式易受CPA攻击
链式CBC (SSL 3.0和TLS 1.0) 复用最后一个密文块作为新的IV 。这减少了带宽，因为不需要每次都发送新的IV 。
但是：不要对标准密码方案进行任何修改，即使这些修改看起来是无关紧要的。

攻击*：
在如下所示的链式CBC模式中：

$$\begin{gathered} C^{(1)}=(IV,c_1,c_2,c_3),C^{(2)}=(c_3,c_4,c_5), \\ {c}_1={\mathrm{F}}_k(IV\oplus m_1),c_4={\mathrm{F}}_k(c_3\oplus m_4). \end{gathered}$$

假设 m 1 ∈ { 0 , 1 } l , r ∈ { 0 , 1 } l , 令 m 4 = I V ⊕ c 3 ⊕ r , 我 m_1\in \{ 0, 1\} ^l, r\in \{ 0, 1\} ^l\textbf{, 令 }m_4= IV\oplus c_3\oplus r\textbf{, 我 } m1​∈{0,1}l,r∈{0,1}l, 令 m4​=IV⊕c3​⊕r, 我 

$\overline{\text{们可以观察到当}r}=m_1$时有$c_4=c_1.$

核心：构造：$m_4$
换句话说，敌手可以通过选择适当的m4来找到m1，最多尝试$2^l$次。这就是所谓的“BEAST攻击”，该漏洞被用于攻击SSL/TLS。

CFB(密文反馈)模式（不考）

加密过程：$c_i=m_i\oplus MS{B}_j(F_k(I{V}_i)),1\le i\le t$ $(MS{B}_j$表示取最高$j$位)
解密过程：$m_i=c_i\oplus MS{B}_j(F_k(I{V}_i)),1\le i\le t$

1.适用于每次处理 j 比特明文块的特定需求的加密情形, 能灵活适应数据各格式的需要。例如对于数据库加密, 要求加密时不能改变明文的字节长度。
2.CFB加密和解密都使用的是伪随机函数*, 本质上是把分组密码当成一个密钥流生产器来使用。

CFB模式特点：
1.改变初始向量会导致相同的明文块产生不同的密文块, 能够隐蔽明文的数据格式。
2.明文块的长度j可由用户来确定, 可适应用户不同的格式要求。
3.密文块$c_i$依赖于$m_i$以及所有前面的明文分组。
4.密文块$c_i$的一个或多个比特错误会影响该密文块和后续$\lceil n/j\rceil$个密文块的解密。
5.加密效率低, 一次只能完成j个bit的明文数据加密。

OFB(输出反馈)模式

对比*： 与CBC模式比较：
1.$F_k$不需要可逆，可以用任何PRF而不是PRP。
2.明文长度不需要是n的倍数，可以任意长。
3.与CBC不同的是，有状态的变体 (其中，最后$y_{\ell }$被用作下一个加密的IV ) 是安全的 (同步流密码模式) 。
4.支持预计算。仍然像CBC一样是按顺序进行的，但是$y_i$可以在得知$m_i$之前计算。$m_i$,$y_i$计算ci非常快，而且是可并行的。

计数器 (CTR) 模式

$\bullet$ 为了使用CTR模式加密具有$\ell <2^n/4$块的消息，首先均匀一致地选择 I V = { 0 , 1 } 3 n / 4 IV=\{0,1\}^{3n/4} IV={0,1}3n/4。$y_i:=F_k(IV||⟨i⟩),i=$ $1,2,\dots$,其中计数器$i$被编码为$n/4$-比特的字符串。
$\bullet IV$和计数器的长度是任意的，只要它们和为$n$。
$\bullet$ 较长的$IV$会提供更好的具体安全性，但会减少可加密消息的最大长度。
优势：
1.可完全并行！
2.可以解密单独的消息块。

如果F是一个PRF(伪随机函数)，那么CTR模式是CPA-安全的。

生日悖论

如果$q$个元素$y_1,...,y_q$是从大小为$N$的集合中独立且均匀一致选取的，那么
$$\frac{q(q-1)}{4N}\le \mathrm{Pr}[\exists i\ne j:y_i=y_j]\le \frac{q^2}{2N}$$
第一个不等式适用与任何情况。也就是，不一定必须是均匀分布。

LRCPA（左或右CPA安全）

流密码&分组密码实例化（略，不考）

SP网络

SP网络中, S表示代替, 又称为混淆层, 主要起混淆作用, P表示置换, 又称为扩散层, 主要起扩散作用。
示例图：

SP网络结构的典型应用为高级加密标准(AES)

三层：

Feistel网络

左直接得到右，右需要左异或F的（右+k）
加密过程：
$\bullet$ 它将明文平均分为左半部分$L_0$和右半部分$R_0$,经过$r(\ge$ 1)轮迭代完成整个操作过程。
$\bullet$ 假设第$i-1$轮的输出为$L_i-1$和$R_i-1$,它们是第$i$轮的输入，第$i$轮的输出为
$$L_i=R_{i-1}$$
$$R_i=L_{i-1}\oplus f(R_{i-1},k_i)$$
$\bullet$ $f$称为轮函数，$k_i$是利用加密密钥生成的供第$i$轮使用的
子密钥。

给定函数 f 1 , . . . , f d : { 0 , 1 } n → { 0 , 1 } n f_1,...,f_d:\{0,1\}^n\to\{0,1\}^n f1​,...,fd​:{0,1}n→{0,1}n
目标：构造可逆函数F： { 0 , 1 } 2 n → { 0 , 1 } 2 n \{0,1\}^{2n}\to\{0,1\}^{2n} {0,1}2n→{0,1}2n

函数$f_i$是公开的。
优点：$f_i$不需要可逆！

对于所有 f 1 , . . . , f d : { 0 , 1 } n → { 0 , 1 } n f_1,...,f_d:\{0,1\}^n\to\{0,1\}^n f1​,...,fd​:{0,1}n→{0,1}n, Feistel网 络 F: { 0 , 1 } 2 n → { 0 , 1 } 2 n \textbf{络 F: }\{ 0, 1\} ^{2n}\to \{ 0, 1\} ^{2n} 络 F: {0,1}2n→{0,1}2n是可逆的

Feistel网络结构的典型应用为数据加密标准(DES)

Feistel网络的实现与以下参数和特性有关：
分组大小: 分组越大则安全性越高, 但加密速度就越慢。
密钥大小: 密钥越长则安全性越高, 但加密速度就越慢。
轮数: 单轮结构远不足以保证安全性, 但多轮结构可提供足够的安全性。典型地, 轮数取为16。
子密钥产生算法: 该算法的复杂性越大, 则密码分析的困难性就越大。
轮函数: 轮函数的复杂性越大, 密码分析的困难性也越大。

解密过程：
Feistel解密过程本质上和加密过程是一样的, 算法使用密文作为输入, 但使用子密钥Ki的次序与加密过程相反, 即第1轮使用Kn, 第2轮使用Kn−1…,
最后一轮使用K1。这一特性保证了解密和加密可采用同一算法。

加密	解密

在加密过程中：
$L{E}_{16}=R{E}_{15}$
$\begin{array}{r}R{E}_{16}=L{E}_{15}\oplus F(R{E}_{15},K_{16})\end{array}$
在解密过程中：
$$\begin{array}{rl}& L{D}_1=R{D}_0=L{E}_{16}=R{E}_{15}\\ & R{D}_1=L{D}_0\oplus F(R{D}_0,K_{16})\\ & =R{E}_{16}\oplus F(R{E}_{15},K_{16})\\ & =L{E}_{15}\oplus F(R{E}_{15},K_{16})\oplus F(R{E}_{15},K_{16})\\ & =L{E}_{15}\end{array}$$

所以解密过程第1轮的输出为$RE15||LE15$, 等于加密过程第16轮输入左右两半交换后的结果。容易证明这种对应关系在16轮中每轮都成立。
一般地, 加密过程的第 $i$ 轮有：
$$L{E}_i=R{E}_{i-1}$$
$$R{E}_i=L{E}_{i-1}\oplus F(R{E}_{i-1},K_i)$$

因此，
$$R{E}_{i-1}=L{E}_i$$
$$L{E}_{i-1}=R{E}_i\oplus F(R{E}_{i-1},K_i)=R{E}_i\oplus F(L{E}_i,K_i)$$

DES

DES (Data Encryption Standard) 算法于1977年得到美国政府的正式许可, 是一种用56位密钥来加密*64位 *数据的方法。这是IBM的研究成果。
基本参数

• 明文分组长度: 64比特

• 密文分组长度: 64比特

• 密钥长度: 64比特

• 有效密钥长度: 56比特

• 迭代轮数: 16轮

• 每轮子密钥长度: 48比特

密钥长度为64 bits, 但有效密钥长度为56 bits——在DES加密开始之前要去掉第8, 16, 24, 32, 40, 48, 56, 64位。去掉的这8位比特用于奇偶校验, 确保密钥中不包含错误。

• 初始置换IP
  将64 bit明文的位置进行置换, 得到一个乱序的64 bit明文组, 而后分成左右两段, 每段为32 bit, 以L0和R0表示。
  可以看出, M各位的初始顺序将被恢复。ip-1(58)=1
  

• 16轮迭代运算
  16轮的迭代运算具有相同的结构, 初始置换后的明文与中间结果都被分成左右两半进行处理。同Feistel。注意：第16轮不进行左右交换操作—使加密和解密可以使用同一个算法。
  
  轮函数f(Ri−1, ki)是DES的核心:
  轮结构：
  
  

  • 扩展置换E
    将32位的输入扩展成48位
    

  • 子密钥异或

  • S盒代替 (DES中唯一的非线性变换)*
    S盒代替是将“子密钥异或”的输出结果(48位)作为S盒代替的输入, 经过变换得到32位的输出。
    
    
    每个S盒是一个4行16列的表。
    输入为$x_1,x_2,x_3,x_4,x_5,x_6$
    输出为$y_1{y}_2{y}_3{y}_4$。
    例子：

  • P盒置换
    1.P盒的各输出块的4个比特都来自不同的输入块;
    2.P盒的各输入块的4个比特都分配到不同的输出块之中;
    3.P盒的第t输出块的4个比特都不来自第t输入块。
    $P(c_1{c}_2...c_{32})=c_{16}{c}_7{c}_{28}...c_{11}{c}_4{c}_{25}$

• 逆初始置换$I{P}^{-1}$
  将16轮迭代后给出的64 bit组进行置换, 得到输出的密文组。见上述扩展置换E

• 子密钥产生

  • 初始密钥置换PC-1
  • 循环左移位
  • 压缩置换PC-2

PC-2将56位压缩到48位, 实际上是丢掉了第9, 18,22, 25, 35, 38,43和54位。

注：IP和$I{P}^{-1}$在密码意义上作用不大, 它们的作用在于打乱原
来输入x的ASCII码字划分的关系。
填充：
给定加密消息的长度是随机的，按64 bit分组时，最后一组消息长度可能不足64 bit。可以填充一些数字，通常用最后1字节作为填充指示符(PI)。它所表示的十进制数字就是填充占有的字节数。数据尾部、填充字符和填充指示符一起作为一组进行加密。

解密：

互补性：
DES算法具有下述性质。若明文组x逐位取补, 密钥k逐位取补，这种互补性会使DES在选择明文破译下所需的工作量减半。
弱密钥：
DES在每轮操作中都会使用一个子密钥。如果给定初始密钥k, 得到的各轮子密钥都相等, 我们就称k为弱密钥。弱密钥的坏处在于加密两次或解密两次就可恢复出明文。

二重DES的问题

用DES进行两次加密, 但这是否就意味着两重DES加密的强度等价于112 bit密钥的密码的强度? [X]

中途相遇攻击法(Meet-in-the-Middle Attack):
若有明文密文对$(x_i,y_i)$满足
$$y_i=E_{k_2}[E_{k_1}[x_i]]$$

则可得$E_{k_1}[x_i]=z=D_{k_2}[y_i]$

· 给定一已知明密文对$(x_1,y_1)$,可按下述方法攻击。
$\bullet$ 以密钥$k_1$的所有$2^{56}$个可能的取值对此明文$x_1$加密，并将密文$z$存储在一个表中；
$\bullet$ 所有可能的2${}^{56}$个密钥$k_2$中依任意次序选出一个对给定的密文$y_1$解密，并将每次解密结果$z$在上述表中查找相匹配的值。一旦找到，则可确定出两个密钥$k_1$和$k_2$。
具体内容留在后续更新，先省略。

三重DES

$\begin{array}{rl}& \text{加密:}\\ & y=E_{k_1}[D_{k_2}[E_{k_1}[x]]]\\ & 解密:\\ & x=D_{k_1}[E_{k_2}[E_{k_1}[y]]]\end{array}$

称其为加密-解密-加密方案，破译它的穷举密钥搜索量为$2^{112}$量级, 而用分分析破译也要超过$10^{52}$。此方案仍有足够的安全性。

AES

明文分组固定: 128 bit (Rijndael明文长度可变128, 192, 256 bit)
密钥长度可变: 128, 192, 256 bit

中间过程比较复杂，之后再补充。

一轮加密过程：

消息认证码MAC

机密性： 防止（窃听/CPA）敌手获取通过开放信道发送的消息的任何内容（消息长度除外）。
消息认证性：确保每一方都可以验证其收到的消息是由声称发送该消息的一方发送的，并且消息没有被修改过。

机密性和认证性是完全不同的目标。
加密不能保证任何认证性。消息认证性并不意味着任何机密性！
例子：
考虑具有完善保密性的一次一密。观察到$C=M\oplus K$的敌手可以将包含在密文中的明文$M$更改为$M\oplus X$,其中$X$可以是任何值。通过将$C$替换为$C\oplus X$,甚至不知道$M!$

消息认证码定义

消息认证码 (MAC) 是一个概率多项式时间 (PPT) 算法的三元组 (Gen, Mac, Vrfy)，满足以下条件：

1. 密钥生成算法
   密钥生成算法 $k\leftarrow \mathsf{Gen}(1^n)$ 将安全参数 $n$ 映射为密钥 $k$，其中 $|k|\ge n$（通常，$k$ 是从 { 0 , 1 } n \{0,1\}^n {0,1}n 均匀一致选取的）。
2. 标签生成算法
   标签生成算法 $t\leftarrow {\mathsf{Mac}}_k(m)$ 输入密钥 $k$ 和消息 m ∈ { 0 , 1 } ∗ m \in \{0,1\}^* m∈{0,1}∗，并计算一个标签 $t$。
3. 验证算法
   验证算法 $b:={\text{Vrfy}}_k(m,t)$ 输入密钥 $k$、消息 $m$ 和标签 $t$，并输出 b ∈ { 0 , 1 } n b \in \{0,1\}^n b∈{0,1}n（其中，1 表示有效，0 表示无效）。

Gen 是随机的，Mac 可能是随机的。如果 $|m|$ 被限制为 $\ell (n)$，则它是一个定长的 MAC。
正确性
对于所有有效的安全参数 $n$ 和所有消息 m ∈ { 0 , 1 } ∗ m \in \{0,1\}^* m∈{0,1}∗，
$$\mathsf{Pr}[{\mathsf{Vrfy}}_k(m,{\mathsf{Mac}}_k(m))=1\mid k\leftarrow \mathsf{Gen}(1^n)]=1$$
$\begin{array}{rl}& {\text{规范验证:通常Mac是确定性的,在这种情况下 Vrfy}}_k(m,t)\text{可以被定义为}\\ & {\mathsf{Vrfy}}_k(m,t)=1⟺{\mathsf{Mac}}_k(m)=t\end{array}$

直观的安全性：在不知道$K$的情况下，对一个“新”的消息$M^{\prime }$,应该很难找出$M^{\prime },T^{\prime }$使得
Vrfy${}_K(M^{\prime },T^{\prime })=1.$

MAC的安全性

MAC只能保证消息是由知道密钥的一方发送的。控制信道的敌手仍然可以重放、重新排序或删除消息。
可以通过使用序列号或者时间戳可以抵御上述攻击。

强 MACs

$\mathcal{A}$ 破坏了MAC的安全性，如果他能找到$(m^{\ast },t^{\ast })$ 其中$m^{\ast }\notin \mathcal{Q}$,也就是，没有明确要求$t\leftarrow {\text{Мас}}_k(m^{\ast }).$
仅仅找到一个新的$t^{\ast }\ne t{\text{ 其中 Vrfy}}_k(m^{\ast },t)=1$ 不能算是破坏了MAC的安全性。如果一个MAC满足即使仅仅是找到一个新的标签都是困难的这一更强的定义，那么这样的MAC被称为强MAC

（可以理解为单向：对于一个只能对m的标签t，找到一个新的标签很困难）

CBC-MAC

CBC-MAC vs. CBC模式加密

• 加密需要随机IV，MAC不需要IV。
• MAC 只输出最终 F 的输出，加密全部都需要输出。

对于任何多项式 ℓ，如果 F 是一个PRF，那么对于消息长度为 ℓ(n) · n 的 CBC-MAC 是安全的。

攻击：
攻击 1：
如果允许不同长度的消息，则CBC-MAC是不安全的。
发送者 S 只认证长度为 n 的消息。敌手 A 可以对于长度为 2n 的消息伪造标签。

攻击 2:接收者仅接收3块长的消息（Vrfyk(m,t) = 1 当且仅当 m 的长度为 3n 且 t = Mack(m)），但是发送者 S 认证长度为 n 的倍数的任何消息。敌手 A 可以在新消息上伪造标签。

有两种简单的变体允许任意长度的消息:

对消息进行预处理，增加前缀，例如，预先处理消息长度。
使用独立密钥 k′ 再次加密标签。这种结构被称为EMAC，或“加密MAC”。

填充预言机攻击（Padding-oracle attack）

选择密文攻击（chosen-ciphertext attack, CCA）的定义类似于选择明文攻击（CPA），但攻击者不仅可以访问加密预言机 Enck(·)，还可以访问解密预言机 Deck(·).

CCA-安全（选择密文攻击）

定义 3.33 $\Pi =($Gen,Enc,Dec) 在选择密文攻击下具有不
可区分性，或者是 CCA-安全的 如果对任意PPT敌手
$\mathrm{Pr}[$PrivK${}_4{\text{ П}}^{\text{сса}}(n)=1]\le 1/2+$negl$(n)$

哈希函数

哈希函数：
功能性：压缩

一个哈希函数(输出长度是$\ell$)是一对PPT算法(Gen,H)满足
$\begin{array}{lc}\bullet & s\leftarrow \mathsf{Gen}(1^n)\text{ 输入安全参数 }n\text{,输出密钥 }s\\ & |s|\ge n.\end{array}$
$\bullet$对于密钥$s$和 x ∈ { 0 , 1 } ∗ x\in\{0,1\}^* x∈{0,1}∗,$H(s,x)$输出 { 0 , 1 } ℓ ( n ) \{0,1\}^\ell(n) {0,1}ℓ(n)
中的一个字符串。
如果输入$x$被限制在 $x\in {\ell }^{\prime }(n),{\ell }^{\prime }(n)\ge \ell (n)\text{, 那 么 ( Gen, }$
H)是一个定长的 哈希函数，或者是压缩函数。

安全性：抗碰撞
П =(Gen,H) 是抗碰撞的，如果对于所有PPT敌手$\mathcal{A}$
$$\underbrace{{\mathsf{Pr}}_{s\leftarrow \mathsf{Gen}(1^n)}\stackrel{\stackrel{def}{=}{\mathsf{Hash}-\mathsf{coll}}_{\mathcal{A},\Pi }(n)=1}{\overbrace{[\mathcal{A}(s)\to (x\ne x^{{}^{\prime }})\wedge H(s,x)=H(s,x^{{}^{\prime }})]}}\le \mathsf{negl}(n)}.$$

HMAC

${\text{(嵌套的 MAC) NMAC}}_{k_1,k_2}(m)=H(k_2||H(k_1,m))$


HMAC是NMAC的一个更实用的变种。

1. 密钥从单个密钥 k 派生，通过与确定的 ipad, opad 异或。
2. 对于级联，使用确定的IV.
3. 安全性证明需要对 h 做更多的假设，而不仅仅是PRF.

MD5

MD5算法采用迭代型哈希函数的一般结构。

• 输入：任意长的消息

• 分组：512比特

• 输出：128比特的消息摘要

SHA-1

• SHA是基于MD4的算法, 其结构与MD4非常类似。

• 输入: 小于$2^{64}$比特长的任意消息, 分为512比特长的分组。

• 输出: 160比特长的消息摘要。

SHA-512

• 算法的输入: 小于$2^{128}$位的消息, 输入消息以1024 bit为单位进行处理

• 算法的输出: 512位的消息摘要

哈希函数的通用攻击

计算$y_i:=\mathsf{H}(x_i)$对于随机不同的$x_1,...,x_q$,我们找到碰撞的概率是$\approx q^2/2^{\ell }.$
如果我们对 $q$-查询的敌手实现抗碰撞，那么$\ell$ 必须满足$q^2/2^{\ell }\ll 1$,尤其是$\ell >2$log$(q).$
必要条件但不是充分条件！
例如，$\ell =256$可以被$q=2^{1}28$查询以确定的概率攻破。
对于(第二)原像安全，没有通用攻击的成功概率能够高于$q/2^{\ell }.$
因此，$\ell >2$log$(q)$是足够的。

去重

去重：云存储提供商将所有存储文件的哈希值存储在一个小数据库中。如果用户想上传新文件 x，检查H(x)是否已经存储了。

• 如果是，文件已经存储在云上，不需要上传，只需存储一个指针。节省带宽和存储空间。

• 如果 H 是抗碰撞的，服务器返回错误的文件。

• 客户端如何确保它得到正确的文件 F？
  可以存储短的指纹 H(F)，并检查收到的文件是否匹配！要使客户端接受错误的文件 F′不等于F，需要破坏 H 的抗碰撞性，因为它必须保证 H(F) = H(F′).

Merkle树

$\begin{array}{rl}& \bullet \text{ 如果客户端存储了很多文件 }{F}_1,F_2,...,F_{\ell }\text{,那么他可以}\\ & \bullet \text{ 存储所有 }{h}_i:=\mathsf{H}(F_i).\\ & \text{需要与 }\ell \text{ 大小线性相关的存储空间。}\\ & \bullet \text{ 本地只存储一个哈希值 }\varphi =\mathsf{H}(h_1,...,h_{\ell }).\\ & \text{需要与 }\ell \text{ 大小线性相关的通信开销来检索所有的}\\ & h_1,...,h_{\ell }.\\ & \bullet \text{ Merkle哈希树将通信开销降低到 log}\ell !\end{array}$

有：


$\begin{array}{rl}& \bullet \text{ 客户端存储 }\varphi \text{,服务器存储所有 }{F}_i\text{ 和 }h.\\ & \bullet \text{ 如果客户端请求文件,例如,}{F}_{010}\text{,服务器将 }{F}_{010}\text{ 和}\\ & \log (\ell )\text{ 个用于计算根的 }h\text{ 值(黄色标记)。客户端接如}\\ & \text{果重新计算得到的值是 }\varphi .\\ & h_{010}^{{}^{\prime }}:=\mathsf{H}(F_{010}),h_{01}^{{}^{\prime }}:=\mathsf{H}(h_{010}^{{}^{\prime }},h_{011})\\ & h_0^{{}^{\prime }}:=\mathsf{H}(h_{00},h_{01}),{\varphi }^{{}^{\prime }}:=\mathsf{H}(h_0,h_1^{{}^{\prime }}),{\varphi }^{{}^{\prime }}\stackrel{?}{=}\varphi \end{array}$
就是：对于F010，给你h011,h00,h1，然后利用树，求出大fai，然后对比这个大fai和文件大
fai是否一致。
MAC和Hash都可以用来保证数据的认证性，有什么区别？

1. MAC要求发送方和接收方在相互通信之前预先共享一个秘密密钥。
2. 哈希不需要密钥。但是，它需要一个安全的存储来维护哈希.
3. 它们适用于不同的应用场景，满足不同的需求！

数论基础及密码学中的困难问题

（这一章主要内容在信息安全数学基础不赘述）

——————————————————————————————————————————

致谢：感谢张源老师一学期的教学