Week3 公钥密码、流密码的破解分析

定义

公钥密码是一个三元组（G,E,D）

IND-CPA

IND-CCA

简单说就是无法区分出哪个是 $m_0$ 还是 $m_1$ 加密得出的密文。

陷门函数

det：确定性 alg：算法

安全的陷门函数：单向，不可在没有sk的情况下破解。

trap-door指sk

RSA破解：中间相遇攻击

常规的RSA不是语义安全的

解释：

1. 假设有有 64bits 消息 $k$ 并获得密文 $c = k^e$
2. 如果 $k = k_1k_2$，则有 $\frac{c}{k_1^e} = k_2^e$
3. 通过预先穷举表：$c/1^e,c/2^e,c/3^e,\cdots,c/2^{34e}$
4. 再爆破 $k_2 = 0, \cdots, 2^{34}$ 并查表，即可得到 $k_1,k_2$，从而得到 $k$

解决方案：#PKCS1v1.5填充

 

解决方案：OAEP

802.11 WEP

IV过短，需要通过增加IV长度、重置IV、一次一密解决：

LFSR：Guess-and-determine attack

由于显然LFSR有较强线性性，故可以通过猜测部分寄存器的值来推断出其他寄存器的值，从而破解LFSR。