私钥密码学

"What's that you are reading?"

"It's about Crytography."

"Like secret messages?"

"Not secret, that's the brilliant part. Messages that anyone can see but no one knows what they mean, unless you have the key."

—— The Imitation Game

私钥密码学(Private Key Crypography)

\(\newcommand{\Enc}{\text{Enc}}\newcommand{\Dec}{\text{Dec}}\newcommand{\M}{\mathcal{M}}\newcommand{\K}{\mathcal{K}}\newcommand{\C}{\mathcal{C}}\)假设A要给B发送一条消息(message)，一条消息可以看作一个（二进制的）字符串。然而，这条消息可能会被窃听者(eavesdropper)截获。为此，我们想要对这条消息做某种变换以后再发出去，使得即便被窃听者截获也不会暴露消息内容。这种变换就称为加密(encryption)，加密前的消息称为明文(plaintext)，加密后的消息称为密文(cyphertext)。接收方需要能够在接收到密文以后把密文变换回明文，这个变换称为解密(decryption)。

消息的发送方A与接收方B如何能够实现加密和解密呢？一种方法是，它们提前（在保证不被监听的时候，例如物理意义上见面）约定好一个密钥(key)，这个密钥全世界只有A和B两人知道，所以称为私钥(private key)。加密过程实际上是一个关于明文和密钥的函数，解密是一个关于密文和密钥的函数。整个过程可以描述如下：所有能够被发送的消息构成消息空间(message space)，记为\(\M\)。所有可能被选取的密钥构成密钥空间(key space)，记为\(\K\)。A,B会从\(\K\)中以某个概率分布（通常是均匀分布）选取一个私钥\(k\in \K\)，这个选取过程就是算法\(\text{Gen}\)，记作\(k\leftarrow \text{Gen}\)。如果A要发送消息\(m\in \M\)，那么他会基于密钥\(k\)用加密算法\(\text{Enc}\)生成密文\(c=\text{Enc}_k(m)\)。所有可能的密文构成密文空间(cypher space)，记为\(\C\)。B在接收到\(c\)以后基于密钥\(k\)用解密算法\(\text{Dec}_k(c)\)还原出原文。这里要求加密算法和解密算法满足关系\(\text{Dec}_k(\text{Enc}_k(m))=m\)。

在私钥密码学种，我们只要求密钥这唯一的一个信息是保密的。也就是说，我们默认窃听者已经提前掌握所有关于加密算法、解密算法、消息空间和密钥空间及其对应的概率分布等等的信息。这是合理的，因为通常一个加密算法是难以保密的，并且这也让要保护的信息减少了许多。

安全性(Security)

安全是一个相对的概念，并不存在绝对的安全。例如，攻击者总可以穷举密钥空间并逐一检查翻译出来的内容是否合理来完成破译，或者即便是随机乱猜也有大于0的概率会恰好猜对明文。那么，什么样的加密方案足以被认为是安全的呢？

完全保密(Perfect Secrecy)

最理想的加密应当是每条消息的密文都不会暴露原文的任何“信息”。这里我们所说的是信息论意义下的“信息”，要发送的消息以及其对应的密文可以看作两个随机变量\(M,C\)。因此最完美的加密应当使得\(M,C\)的互信息为0：\(I(M;C)=0\)。具体的，应当满足\(\forall m\in \M,\forall c\in C\)满足\(\Pr[M=m\mid C=c]=\Pr[M=m]\)。满足这一条件的加密方案称为完全保密方案(Perfect Secrecy Encryption)。这里的概率正是窃听者所能推测的消息空间的概率分布：窃听者会根据所有已知的信息推测各个消息的概率，概率最大的消息就最可能是真实发送的。因此，完全保密方案中窃听者所能推测的概率分布应当就是发送时的概率分布——密文被窃听并不能为窃听者提供任何帮助。因此，完全保密是理论上最安全的加密方案了。

以上完全保密条件等价于\(\forall m,m'\in \M,\Pr[\text{Enc}_K(m)=c]\)\(=\Pr[\text{Enc}_K(m')=c]\)，也即一个加密方案是完全保密的当且仅当每条密文被消息空间中的任意一条消息加密的可能性都是相等的。这是自然的，因为如果我们能够推断出消息空间中的某两条信息的概率不相等，则说明密文\(c\)势必暴露了某些信息使得这一推断能够成立。

完全保密条件还等价于“完全不可区分(perfect indistinguishable)”。其中，完全不可区分是通过实验性的方式定义的：随机抽取\(\M\)中的两条消息\(m_1,m_2\)，根据\(\text{Gen}\)生成一个密钥\(k\)加密\(m_1,m_2\)中随机的一条得到\(c\)，假设窃听者有一个确定性的程序来判断\(c\)是由\(m_1\)生成还是\(m_2\)生成。加密方案是完全不可区分的，当且仅当任何这样判定程序的正确概率都不能超过\(1/2\)（而随机乱猜本身就是\(1/2\)）。完全不可区分中再次表明，得到密文\(c\)并不能为我们区分任何两条消息提供任何信息。

完全保密是否真的可行呢？凯撒密码不是完全保密的，因为相同的字符会被加密为相同的密文字符，那么在得到密文的基础上只需观察重复的字符就可以排除掉消息空间中的一部分消息，因此密文暴露了信息。而可以证明，下面这种称为“one-time pad”的加密方案是完全保密的：假设消息是长度固定的二进制串（如果长度不同就补0），密钥是随机生成的与明文相同长度的01串。加密时，用密钥与明文做按位异或，解密时用密钥与密文做按位异或。因为做两次异或刚好抵消，所以这是一个可行的加密方案。One-time pad是完全保密的，因为对于任意给定的密文，其对应任何明文的概率都是相等的，因为密钥本身是纯随机的使得原文的每一位也变得纯随机了。

然而one-time pad的最大缺点就是密钥长度和明文长度相同，这使得密钥保存很不方便。事实上，这是完全保密本身的缺陷：任何完全保密的密钥空间都必须大于等于消息空间的大小。换言之，当消息空间和密钥空间中字符串的长度都固定时，想要完全保密则密钥的长度必须大于等于消息本身的长度。反证法，假如密钥空间小于消息空间，那么假如此时给定一条密文\(c\)，一定有一部分消息空间中的消息不可能作为对\(c\)解密的结果：因为我们用密钥空间中的一个密钥在\(c\)上运行解密程序只会得到一个结果，因此总的结果数量不可能超过密钥空间的大小，因此小于消息空间的大小。那么这部分消息也就是不可能加密成为\(c\)的，这就说明\(c\)暴露了信息。

计算安全性(Computational Security)

由此可见，完全保密在现实中几乎是不可能实现的：我们不可能总是使用与原文长度相同的密钥来加密。完全保密的要求太强了。在现实中，窃听者总是有着一些计算能力限制。如果我们能够保证密文只泄露了一点点信息，以至于窃听者即便得到了这些信息也只能在很长一段时间以后以很小的概率破解密码，我们也认为这样的加密方案是安全的。

我们为每个加密方案假定一个系数\(n\)，并认为窃听者只有关于\(n\)的多项式复杂度时间来破解密码。这样假定的好处在于，当\(n\)很大时多项式级别的复杂度已经足够大了，我们无需关心更长时间（比如指数的复杂度）以后窃听者的行为；另一方面，现有的大多数计算模型都可以被证明在多项式内和图灵机等价，这样我们的算法就具有很好的普适性；多项式还有良好的闭包性质，即调用多项式次多项式算法依然是多项式复杂度的。其次，我们希望窃听者破译密码的概率足够小，我们同样可以基于系数\(n\)定义“足够小”：称函数\(f(n)\)是可忽略的(negligible)，如果对于任意多项式\(p(x)\)都存在\(N>0\)使得\(\forall n>N\)，\(f(n)<\dfrac{1}{p(n)}\)。我们通常把这样的\(f(n)\)简记为\(\text{negl}\)。容易证明，一个可忽略的函数乘以任意多项式依然是可忽略的。

如果一个关于系数\(n\)的加密方案满足任意窃听者在关于\(n\)的多项式时间内只能以关于\(n\)可忽略的概率破译密码，那么这个密码就被称为是计算安全(Computational Secure)的。可见，与完全保密相比，我们放松了对安全的要求。什么叫关于系数\(n\)的加密方案呢？我们可以这样定义一个加密方案：密钥生成算法会接受一个输入\(n\)，输出一个长度为\(n\)的二进制随机串。这样，\(n\)越大，密钥空间也越大，安全性也就越高。

与完全保密的情形类似，我们如何给出计算安全加密方案的等价条件的描述呢？直观上，我们应当要求加密方案在多项式计算复杂性的窃听者手上只泄露可忽略的一点点信息。然而，此时我们如何描述“信息”呢？仿照完全保密中不可辨别性的定义方式，我们可以定义如下：在实验中，如果给定多项式时间的敌手任意两个消息和由其中一个消息加密而成的密文，存在一个可忽略多项式\(\text{negl}\)使得对于任意\(n\)，敌手都不能以超过\(1/2+\text{negl}(n)\)的概率分辨出原文，那么就称这个加密方案是EAV安全的(EAV指代eavesdropper)。这一安全性保证了拥有多项式算力的敌手不能以显著的概率由密文分辨明文，说明密文并没有泄露关于明文的很多信息。

伪随机(Pseudorandomness)

下面我们来构造一个具体的计算安全的加密方案。还记得在One-time pad中，我们用了一个与原文相同长度的随机串来做密钥。现在我们想要让密钥短一点。是否存在一个确定性的(deterministic)程序，它接受一个较短的随机串，输出一个“看上去随机”的更长的随机串？如果存在这样的程序，那么我们就可以用短串做密钥，然后用这个程序把串变成长度与明文相等的串再做加密。这样就实现了密钥长度短于明文长度的One-time pad。这个确定性的程序就称为一个伪随机生成器(pseudorandom generator)。

由于伪随机生成器是一个确定性的程序，由短的随机输入串，通常称为种子(seed)，不可能实现真正的更长的随机，因为样本空间大小都不同。然而在计算安全性的前提下，我们只需要保证生成器给出的输出能够以很大的概率骗过所有多项式算力的用户就可以了。具体地，我们定义满足以下条件的程序为一个伪随机生成器：给定输入\(n\)，输出一个长度为\(\ell(n)\)的串，其中\(\ell(n)>n\)。定义一个分辨器接受一个串，输出这个串是否是随机生成的。如果对于任意的多项式分辨器\(D\)，\(D\)正确判定一个真正随机的长度为\(\ell(n)\)串与正确判定一个由生成器给出的输出的串的概率只差是关于\(n\)可忽略的，那么这就是一个伪随机生成器。

以上用伪随机生成器来生成“密钥”的算法是计算安全的。假如我们不用伪随机生成器而用一个真正的随机生成器，那么这就对应着原来的One-time pad，它是完全保密的，因此任给两条消息和一条由其中一条消息加密的密文我们都只能以\(1/2\)的概率辨别原始消息。当我们把真正的随机生成器替换为伪随机生成器以后，如果我们能以超过\(1/2+\text{negl}\)的概率实现辨别，而密钥就是密文与消息的异或，那么我们也就有了辨别密钥的方法，这与伪随机生成器的定义矛盾。可见，只要伪随机生成器存在这一假设成立，以上加密算法就是计算安全的。

（待续）