02流密码

密码

由加密和解密两个算法E、D组成，也可以定义为一个三元组$(\mathcal{K},\mathcal{M},\mathcal{C})$:（密钥空间，明文空间，密文空间）
E通常为一个随机算法，D是确定算法

有效

可以自己决定什么是有效，例如：多项式时间、特定时间

一次性密码本 The One Time Pad

明文空间 = 密文空间 = { 0 , 1 } n \{0,1\}^n {0,1}n

$c:=E(k,m)=k\oplus m$
$m=D(k,c)=k\oplus c$

缺点：密钥需要与明文一样长，因此在实际中很难使用，如果Alice能够安全传输密钥给Bob，那她一定可以安全传输同样长度的明文给Bob

密码的安全性

密码无法揭露明文的任何信息，一个密文c，由明文$m_1$或$m_2$加密得来的概率是一样的，即无法由密文反推出明文

密钥在密文空间中均匀分布： $k\stackrel{R}{⟵}\mathcal{K}$（R表示Random、均匀分布）

证明：

对任意的$m,c$，$E(k,m)=c$ 的概率等于所有能够使其成立的$k$，除以总的$k$的个数，即：

$Pr[E(k,m)=c]=\frac{\#keys,k\in \mathcal{K},s.t.E(k,m)=c}{|\mathcal{K}|}$ 可以看出只需要分子是一个常数，即为完美安全（key就是k）

在一次性密码本中，由于 $c=k\oplus m\Rightarrow k=c\oplus m$，k是唯一的

因此一次性密码本实际上是完美安全的，没有唯密文攻击

对于完美安全的密码，密钥空间的大小 $\ge$ 明文空间的大小：$|\mathcal{K}|\ge |\mathcal{M}|$

流密码

由于一次性密码本虽然是完美安全，但是不实用。于是基于一次性密码本的思想，改造出了流密码

idea：把随机的key替换成伪随机的。流密码不是完美安全的，因为密钥比明文短

PRG（伪随机数发生器）：取一个随机种子s，把它映射成一个很长的比特序列，比如种子可能只有128位，但可以扩展成很长的字符串。

函数G本身没有随机性，它是一个可以有效计算的确定性函数，唯一有随机性的东西是随机种子s。输出应该是“看起来随机的”。
PRG的性质：
不可预测性：可预测指的是，给定一段序列，推算出后面一位的概率$>=1/2+ϵ,ϵ>=1/2^{30}$
($ϵ<=1/2^{80}$ 时被认为是可忽略的)

可忽略和不可忽略

$ϵ(\lambda )=1/2^{\lambda }$：negligible
$ϵ(\lambda )=1/{\lambda }^{1000}$：non-negligible
G : s ∈ { 0 , 1 } s → { 0 , 1 } n , n > > s G:s \in \{0,1\}^s \rightarrow \{0,1\}^n,n>>s G:s∈{0,1}s→{0,1}n,n>>s

新的安全定义

虽然流密码不是完美安全的，但仍然被视作是安全的。隐私的定义

针对一次性密码本的攻击

同一个OTP加密不同的两个信息

原理：$c_1\oplus c_2=m_1\oplus m_2$
例如：网络通信WEP、硬盘上资料改写的具体位置

no integrity 攻击者对密文进行修改，影响解密后的值，并且用户无法检测

流密码的实际应用

RC4（垃圾）

面向软件设计
缺陷：某些特殊输出的概率大于平均概率，并且密钥之间存在联系

CSS（垃圾）

面向硬件设计
利用了LFSR，多个LFSR组合
缺陷：可以枚举其中一个LFSR的初始状态，结合该LFSR的输出和已知信息，算出另一个LFSR的输出，根据LFSR的特点来判断计算出的结果是否正确，从而暴力破解出两个LFSR的初始状态

eStream：Salsa 20（比较安全）

同时面向硬件和软件
密钥种子seed（k）、新鲜值nonce（r）、可逆函数H
r 不同，$（k;r）$对不同，因此 k 可以重用
先构造一个64位的东西，应用多次H，得到的输出加上最初的64位，得到最终的值

PRG 的定义

定义：【发生器的输出】 与【 随机序列】 无法区分:

以下两个输出无法区分
$k\stackrel{R}{⟵}\mathcal{K}$, output $G(k)$
r ⟵ R { 0 , 1 } n r\stackrel{R}{\longleftarrow} \{0,1\}^n r⟵R​{0,1}n, output $r$

统计测试

函数$A(x)$
$A(x)=0$：不随机
$A(x)=1$：随机

随机：

• 0的个数和1的个数差不多： $|\#0(x)-\#1(x)|<=10\sqrt{n}$
• 00的出现的概率差不多是1/4：$|\#00(x)-n/4|<=10\sqrt{n}$
• 连续出现的0的个数最多的Log级别的：max-run-of-$0(x)<=10{\log }_2(n)$
• ……

当很多方法都说这个发生器生成的字符串是随机的，就是一个好的发生器

Advantage

这个统计测试对发生器G的优势是：

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

Adv 接近1，说明G和随机差别很大
Adv 接近0，说明A无法区分G和随机

无法区分出真随机和伪随机

例如一个G，输出的最高位是1的概率是2/3
A（(x)：如果最高位是1输出1，否则输出0
则： $Ad{v}_{PRG}[A,G]=|Pr[A(G(k))=1]-Pr[A(r)=1]|=|2/3-1/2|=1/6$
即：A以优势1/6破解了发生器G

安全的PRG的定义

对任意的有效的统计测试A，它对G的优势$Ad{v}_{PRG}[A,G]$是可以忽略的，即统计测试无法区分PRG的输出和真随机序列，

我们是否能构造一个PRG并且证明它是一个安全的PRG？
不可。因为证明这个等于证明：$P\ne NP$

即使不能严格证明一个PRG是安全的，但还是有很多PRG的候选方案

Yao’82：an unpredictable PRG is secure

安全的PRG：对任何位置l，不可能根据前l位推测出第l+1位
如果一个PRG可预测，那A对它的优势就是 $ϵ$，即不安全

两个分布在计算上不可区分

两个分布$P_1,P_2$
计算上不可区分：$P_1\approx P_2$，即对所有统计测试A，它区分两个分布的优势是可忽略的
一个PRG是安全的，当 { k ⟵ R K : G ( k ) } ≈ p u n i f o r m ( { 0 , 1 } n ) \{k\stackrel{R}{\longleftarrow} \mathcal{K}:G(k)\} \approx _p uniform(\{0,1\}^n) {k⟵R​K:G(k)}≈p​uniform({0,1}n)

密码的安全

定义安全的视角：攻击者可以做什么，攻击者企图做什么

• ？无法还原密钥——反面例子：$E(k,m)=m$
• ？无法还原整个明文——反面例子：$E(k,m_0||m_1)=m_0||E(k,m1)$，即使不能恢复全部明文，也能够恢复大部分明文了
• 香农安全

语义安全Semantic Security （one-time key）

实验：EXP，for $b=0,1$，$W_b:=[$event that $EXP(b)=1]$
攻击者发送两个长度一样的信息$m_0,m_1$
在实验0里，挑战者输出$m_0$的加密$c_0$，在实验1里，挑战者输出$m_1$的加密$c_1$
攻击者拿到一个$c$，无法区分自己处于实验1还是实验0

证明使用安全的PRG的流密码是语义安全的：

• 方法1： 要证明安全PRG可以推出流密码E是语义安全的，可以使用反证法：
  如果流密码E不安全（优势不可忽略），则G也不安全（优势更加不可忽略）
  构造一个与之“等价”（准确的说是充分条件）的公式：$Ad{v}_{SS}[A,E]\le 2\ast Ad{v}_{PRG}[B,G]$
  只要证明：对于任意的语义安全流密码的攻击者A，都存在一个PRG的攻击者B，使得该公式成立，则反证成立，则原式成立

  思路，加入两步将$G(k)$替换成真正的随机串$r$的辅助操作（不理解可以先看方法2）
  数学原理：$|A+B|\le |A|+|B|$

  证明：

  $Ad{v}_{SS}[A,E]=|Pr[W_0]-Pr[W_1]|=|Pr[W_0]-Pr[R_0]+Pr[R_0]-Pr[R_1]+Pr[R_1]-Pr[W_1]|\le |Pr[W_0]-Pr[R_0]|+|Pr[R_0]-Pr[R_1]|+|Pr[R_1]-Pr[W_1]|=2\ast Ad{v}_{PRG}[B,G]$

• 方法2：（参考b站UP：Alice-Bob，更好理解但道理是一样的）

  安全的PRG，即$G(k)$与$r$不可区分

  1. 因为$G(k)$与$r$不可区分，所以$r\oplus m_0$和$G(k)\oplus m_0$无法区分 （1）
  2. 因为OTP是完美安全，所以肯定语义安全，所以$r\oplus m_0$和$r\oplus m_1$无法区分（2）
  3. 同（1），所以$r\oplus m_1$和$G(k)\oplus m_1$无法区分 （3）
  4. 所以，$G(k)\oplus m_0$和$G(k)\oplus m_1$无法区分

  $G(k)$语义安全，得证。