流密码

英文: Stream cipher.
别名: State cipher.

一次性密码本 (One-time pad, OTP)

$$\begin{gathered} E(k,m)=k\oplus m \\ D(k,c)=k\oplus c \end{gathered}$$

一致性方程:

$$D(k,E(k,m))=k\oplus (k\oplus m)=(k\oplus k)\oplus m=0\oplus m=m$$

密钥 k 的长度和明文相等.

template <std::size_t N>
std::bitset<N> E(const std::bitset<N>& key, const std::bitset<N>& plaintext) {
    return key ^ plaintext;
}

一次性

假设使用同一个密钥加密了两份密文:

$$\begin{gathered} c_1=m_1\oplus k,c_2=m_2\oplus k \\ \begin{array}{rl}{c}_1\oplus c_2& =m_1\oplus k\oplus m_2\oplus k\\ & =m_1\oplus m_2\oplus k\oplus k\\ & =m_1\oplus m_2\oplus 0\\ & =m_1\oplus m_2\end{array} \end{gathered}$$

只要截获了两份密文, 即可通过异或的交换律/归零律和恒等律可以得出对应明文异或的结果. 因此 OTP 的密钥只能使用一次.

优点

OTP 满足以下条件则无法破译:

1. 密钥 k 的长度至少和明文相等.
2. 密钥是在密钥空间中均匀分布的真随机数.
3. 密钥不能自重复.
4. 密钥不可能泄露.

完善保密性 (Prefect secrecy)

密文不应该揭露任何明文的信息.

$$\mathrm{\forall }{m}_0,m_1\in \mathcal{M}\mathcal{(}\mathcal{|}{\mathcal{m}}_{\mathcal{0}}\mathcal{|}\mathcal{=}\mathcal{|}{\mathcal{m}}_{\mathcal{1}}\mathcal{|}\mathcal{)}\mathcal{\text{ and }}\mathcal{,}\mathrm{\forall }\mathcal{c}\in \mathcal{C}\mathcal{\$}\mathcal{\$}\mathcal{\$}\mathcal{\$}\mathcal{P}\mathcal{r}\mathcal{[}\mathcal{E}\mathcal{(}\mathcal{k}\mathcal{,}{\mathcal{m}}_{\mathcal{0}}\mathcal{)}\mathcal{=}\mathcal{c}\mathcal{]}\mathcal{=}\mathcal{P}\mathcal{r}\mathcal{[}\mathcal{E}\mathcal{(}\mathcal{k}\mathcal{,}{\mathcal{m}}_{\mathcal{1}}\mathcal{)}\mathcal{=}\mathcal{c}\mathcal{]}\mathcal{w}\mathcal{h}\mathcal{e}\mathcal{r}\mathcal{e}\mathcal{k}\underleftarrow{\mathcal{R}}\mathcal{K}$$

缺点

因为 $|\mathcal{K}\mathcal{|}\ge \mathcal{|}\mathcal{M}\mathcal{|}$, 难以在实践中使用.

流密码

OTP 虽然具有完善保密性, 但在及时的网络通信中不实用, 因为密钥的长度大于或等于明文, 因此加密没有意义.
流密码在 OTP 的基础上进行了一些改动, 用安全性换取实用性.

伪随机数生成器 (Pseudorandom generators, PRG)

为了使 OTP 更具实用性, 可以将较短长度的密钥通过 PRG 拓展成和密文一样长的拓展后的密钥.
伪随机数生成器应该是不可预测的, 否则可以通过其中一段明文和密文得出密钥的一部分, 然后预测密钥的其他部分.
如线性同余随机数生成器 (Linear congruential generator), 虽然在统计学上具有良好的性质, 但容易预测.

// 先将 N 位的密钥拓展至 M 位, 然后再使用 OTP 进行加密
template <typename PRNG, std::size_t N, std::size_t M>
std::bitset<M> E(const std::bitset<N>& key, const std::bitset<M>& plaintext) {
    static_assert(N < M, "");
    std::bitset<M> extended_key;
    PRNG engine(key.to_ulong());
    for (std::size_t size = 0; size < M;
        size += sizeof(typename PRNG::result_type) * sizeof(unsigned char)) {
        extended_key |= engine() << size;
    }
    return E(extended_key, plaintext);
}

拓展

• VENONA 项目.
• 线性同余随机数生成器.

评论