离散概率
首先有一个世界 $U$ 包含有限个元素。 $U$ 中每一个元素都有一个概率，所有元素的概率加起来等于一。 而给这些元素不同的概率就形成了不同的概率分布。比较常见的分布是均匀分布，就是所有元素的概率都相等。
事件
这个世界会发生一些事件 $A$ 每个事件都是由一些元素组成的，所以事件是 $U$ 的子集。一个事件发生的概率就是这个子集 $A$ 中所有元素概率之和。
假设有两个事件 $A$ 和 $B$ 如果满足 $p(A\cap B) = p(A)p(B)$ 我们就说这两个事件是独立的，发生 $A$ 不会影响发生 $B$ 的概率。我们也可以理解为：在世界 $U$ 中发生 $B$ 的概率和在 $A$ 中发生 $B$ 的概率相等 \(p(B) = \frac{p(A \cap B)}{p(A)}\) 例如掷色子结果为偶数这个事件与结果小于3这个事件就是独立的，因为无论有没有结果小于3这个事件，结果为偶数的概率都是 $\frac12$ 但是结果为偶数与结果小于4就不独立了。因为当结果小于4时结果为偶数的概率为 $\frac13$
随机变量
随机变量 $r$ 是沟通两个世界 $U$ $V$ 的桥梁，他是一个 $U$ 到 $V$ 的函数， $r$ 和 $U$ 共同定义了 $V$ 的一个分布。这个定义有点奇怪，因为涉及到具体的随机元素如何产生。 但我们可以把他理解为 $r$ 是一个取值范围为 $V$ 的随机变量。而 $r$ 定义了 $V$ 的一个分布。（说人话就是定义了 $V$ 上每个元素可能出现的概率）
一个均匀随机变量 $r$ 输出 $V$ 中任何一个元素的概率都是相等的。相当于概率分布是均匀分布。 \(r\xleftarrow{\text{R}}V\)
我们有了随机变量之后就可以在一些算法中加入随机性，让他成为一个随机算法。相比于确定算法 $y=F(m)$ 随机算法引入了一个均匀随机变量 $y’=F(m, r)$ 前者有一个确定的结果 $y$ 而后者返回的是一个随机变量 $y’$ 当 $F(m, r)$ 是可逆函数的时候， $y’$ 也是一个均匀随机变量，他的取值范围就是 $F(m, r)$ 所有可能的结果。（注意这里 $m$ 是固定的而 $r$ 是随机变量）
如果有两个 $V$ 上的随机变量， $X, Y$ 当满足 $\forall{a, b} \in V : p(X=a,Y=b) = P(X=a)P(Y=b)$ 这两个随机变量就是独立的。我们无法从一个随机变量推测出任何另一个随机变量的信息。这个独立和事件的独立不太一样，事件的独立是同一个分布内的两个子集独立，而每个随机变量都代表了 $V$ 上的一个分布。
关于随机变量，有一个著名的生日悖论：如果我们观察同一个随机变量很多次，大概在 $1.2\times\sqrt{\vert{U}\vert}$ 次的时候我们看到重复元素的概率大于 $\frac12$。
异或
现在我们重点关注这样一个世界 $U=\{0,1\}^n$ 其中每一个元素都是由一个 $n$ 比特串构成的。其中有两个独立随机变量 $X,Y$。 $X$ 是任意分布的随机变量，而 $Y$ 是一个均匀分布的随机变量。那么由 $X,Y$ 经过异或运算得到的随机变量 $Z=X \oplus Y$ 是一个均匀分布的随机变量。异或的这个独特性质让他成为密码学中非常重要的工具。（密码学本质就是各种东西异或到一起XD）
证明的方式也非常简单。我们来计算 $Z$ 是任何一个元素的概率 $P(Z=z)$ 。对于 $U$ 中任何一个 $X=x$ 我们都可以找到一个 $Y=y$ 让 $x \oplus y_x = z$ 。而 $X,Y$ 独立，我们可以得出
\[p(Z=z) = \sum_{x \in V} p(X=x)p(Y=y_x)\]因为 $Y$ 是一个均匀分布，所以 $p(Y=y_x) = \frac{1}{\vert{U}\vert}$ 提取公因子得出
\[p(Z=z) = \frac{1}{\vert U\vert}\sum_{x \in V} p(X=x)\]后一项就是 $V$ 中所有元素概率之和为1，所以得出 $Z$ 是一个均匀随机变量
\[p(Z=z) = \frac{1}{\vert U\vert}\]对称加密算法
对称加密算法由一组高效的算法组成，分别是加密算法 $E$ 和解密算法 $D$ 。加密算法 $E(k, m) = c$ 输入一个原文 $m \in M$ 和一个密钥 $k \in K$ ，输出一个加密文本 $c \in C$ 。而解密算法 $D(k, c) = m$ 输入加密文本和密钥，输出原文。 $K, M, C$ 分别是密钥空间，原文空间和加密文本空间。显然 $D(k, E(k, m)) = m$。
One Time Pad
One Time Pad是一个安全的对称加密算法他的原文空间，密钥空间和加密文本空间都是n位的串 $M = C = K = \{0, 1\}^n$ 他的定义也很简单
\[\begin{eqnarray} E(k, m) = k \oplus m \\ D(k, c) = k \oplus c \end{eqnarray}\]One Time Pad非常高效，同时他需要一个非常长的密钥来进行加解密，有方式传输这个密钥不如直接用这个方式传输原文。
我们还需要评估他的安全性。一个加密算法是否安全主要看他的加密文本是否包含了原文的任何信息。如果加密文本不包含任何原文的信息，这个加密算法就是一个完美的加密算法。
换句话说，如果一个加密算法是完美的，那么由这个加密算法算出来的加密文本 $c$ 对应的原文是任何一个 $m \in M$ 的可能性都是相等的。这个定义很容易理解，我无法通过加密文本去推测出原文更可能是那些取值。这个定义的公式是 \(\forall{m_0, m_1} \in M, \forall{c} \in C, k\xleftarrow{\text{R}}K : p(E(k, m_0) = c) = p(E(k, m_1) = c)\) 这里可以用概率是因为k是一个随机变量。
通过异或的特性，我们就可以得出One Time Pad是一个完美的加密算法。这能保证仅用加密文本是无法攻击这个算法的。但是这不代表加密算法不会被别的手段攻击。
看起来One Time Pad是一个非常简单又完美的加密算法，除了他非常长的密钥。可以证明，非常长的密钥是保证完美性的必要条件，只有当密钥长度大于等于原文长度时，加密算法才可能是完美的。