Week 2：完美安全、流密码、分组密码

完美安全

定义

对于在空间 $(\mathbb{K},\mathbb{M},\mathbb{C})$ 上的算法E，对于任意的 $m_1,m_2\in \mathbb{M},|m_1|=|m_2|$ ，任意的 $c\in \mathbb{C}$ ，都有：

$$\frac{\mathrm{\#}\{k\in \mathbb{K}:E(k,m_1)=c\}}{|\mathbb{K}|}=\frac{\mathrm{\#}\{k\in \mathbb{K}:E(k,m_2)=c\}}{|\mathbb{K}|}=\frac{1}{|\mathbb{K}|}$$

解释：对于任意两个等长的明文$m_1$和$m_2$，以及任意一个密文$c$，使用随机选择的密钥加密$m_1$得到$c$的概率，等于使用随机选择的密钥加密$m_2$得到$c$的概率，且都等于$\frac{1}{|\mathbb{K}|}$。

就是说对于任意一条明文，在对于一个密钥对应的密文空间映射中，每一个密文出现的概率都是均等的。

One-Time Pad

对于一次一密来说，当$|\mathbb{K}|\ge |\mathbb{M}|$时，既密钥长度大于等于明文长度时，一次一密可以达到完美安全。

为什么当密钥长度小于明文长度时不完美安全

假设$|\mathbb{K}|<|\mathbb{M}|$，则存在$m_1,m_2\in \mathbb{M},|m_1|=|m_2|$，使得$m_1\oplus k=m_2\oplus k$，即$m_1=m_2$，与$m_1\ne m_2$矛盾。

为什么Two-Time Pad不安全

$$\begin{gathered} C_1\leftarrow M_1\oplus K \\ {C}_2\leftarrow M_2\oplus K \end{gathered}$$$$C_1\oplus C_2=M_1\oplus M_2$$

则由于编码大多是ASCII编码，则可以通过$M_1\oplus M_2$的关系进行破解。

流密码

由于在工程实现中，一次一密要求的$\mathbb{K}\ge \mathbb{M}$显然难以实现，所以引入了伪随机数生成器PRNG来扩展密钥以求近似一次一密的效果。

PRG的安全性：不可预测性(Unpredictable)

对于算法$G:\{0,1{\}}^s\to \{0,1{\}}^n$，其中$s<n$，如果对于任意的$i<n$，给定$G(k{)}_1,G(k{)}_2,...,G(k{)}_i$，无法以非忽略概率预测出$G(k{)}_{i+1}$，则称$G$是不可预测的。

既对于已知前一个比特或者前n个比特，预测出下一个比特的概率是否大于1/2。

$$Pr[A(G(k{)}_{1,\dots ,i})=G(k{)}_{i+1}]\le \frac{1}{2}+\epsilon$$

当$\epsilon =\frac{1}{2^{32}}$时，认为是不可预测的。

更多定义

PRG的安全性：不可区分性(Indistinguishability)

伪随机数生成器的定义

既在真随机数空间 $\{0,1{\}}^n$中，伪随机数只占据其中一个子集。

统计测试

定义

假设$G:k\to \{0,1{\}}^n$ ，既G是一个生成n比特的随机数生成器，并且存在一个统计测试$A$，定义：

$$PR{G}_{adv}[A,G]=|Pr[A(G(k))=1]-Pr[A(r)=1]|\in [0,1]$$

• 如果优势Adv接近1，则说明$G(k)$和$r$很容易区分，$G$不是一个好的伪随机数生成器。
• 如果优势Adv接近0，则说明$G(k)$和$r$很难区分，$G$是一个好的伪随机数生成器。

则如果对于任意的统计测试$A$，优势$PR{G}_{adv}$是可忽略的，则称PRG是安全的具有不可区分性的

Add-on

 

 

语义安全

对于在空间 $\mathbb{K}\mathbb{,}\mathbb{M}\mathbb{,}\mathbb{C}$ 上的加密算法E:

E是完美安全的，当: $\{E(k,m_1)\}=\{E(k,m_2)\}$ , 既密文的分布概率是完全相等的

E是语义安全的，当: $\{E(k,m_1)\}\approx \{E(k,m_2)\}$ , 既密文的分布概率是计算性不可区分的

分组密码

PRF和PRP

PRF和PRP的区别在于，PRP是一个双射函数，既每一个输入对应唯一的输出，每一个输出也对应唯一的输入，而PRF则没有这个要求。

 

安全的PRF

安全的PRF

安全的PRP

安全的PRP

既对于一个安全的PRP，攻击者无法区分它和一个随机置换。