跳转至

流密码

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

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

\[ E(k, m) = k \oplus m \\ D(k, c) = k \oplus c \]

一致性方程:

\[ 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;
}

一次性

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

\[ c_1 = m_1 \oplus k,\ c_2 = m_2 \oplus k \\ \begin{align} 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{align} \]

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

优点

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

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

完善保密性(Prefect secrecy)

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

\[ \forall m_0, m_1 \in \cal{M} (|m_0| = |m_1|) \text{ and }, \forall c \in \cal{C} $$ $$ Pr[E(k, m_0) = c] = Pr[E(k, m_1) = c] \, where \, k \underleftarrow{R} \cal{K} \]

缺点

因为 \(|\cal{K}| \geq |\cal{M}|\), 难以在实践中使用.

流密码

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);
}

拓展

评论