计算机入门：现代密码学 Modern Cryptography

发表于 更新于 分类于 阅读次数：

同步于知乎：Link

Coin Flip Algorithm

  • 什么是 Coin Flip

Alice 和 Bob 计划去日料店约会，他们厌倦了 AA，想要以一种公平的方式选出其中一方买单。

如果在现实生活中遇到这种状况（不包括约会在内），你打算怎么解决呢？

当然是抛硬币啦。

我想不少人有过这种经历：站在朋友们中央，从口袋里摸出一枚硬币，高高抛起，看准时机摁在手背上。登登！它的正反将决定接下来的一切，所有人都将听命于你（的运气），开球还是防守？真心话还是大冒险？就此散场还是再喝一轮？等等等等……

抛硬币的确是简单可靠的办法，任何一个有生活经验的人都能瞬间想到。如果 party 开得正嗨，你准备抛硬币决定接下来干嘛，突然有人发表长篇大论，提出如何用数学代替 Coin Flip 云云，恐怕在场各位都要皱起眉头，恨不得把 nerd 写在脸上吧……

然而密码学家就是这样一群较真的家伙，这种较真并不是自娱自乐，相反，它实实在在守护了你的数据和钱包。

  • Coin Flip 有何困难之处

在密码学的世界里，Coin Flip 并不像看起来那样简单。

现实生活中，我们借助“硬币”这一道具完成了 Coin Flip。“硬币”可以视作一种随机数生成器，它以 的概率产生 0， 的概率产生 1，更重要的是：这一概率是所有人公认的。

  • 定理：若双方互不信任，无法制备被两人公认的随机数生成器

    （即使你有一枚完美的 硬币，你也不能向对方证明这一点）

打个比方：现在 Alice 打算抛硬币解决谁买单的问题，她找出一枚硬币正准备抛，却被 Bob 拦住了。Bob 说，我怎么知道这硬币的概率是 ，万一某一面朝上概率更大呢？

这好办，Alice 说，我们先抛 次，如果差不多半数朝上、半数朝下，就几乎可以认为概率是公平的。

Bob 说，这也不行，有没有一种可能，这枚硬币有魔法，它平时表现得像一枚普通硬币，可一旦要决定谁买单，它就听你的指挥。

如果 Alice 是普通人，下一句恐怕就要提到分手了。不过作为一位密码学家（或者魔法师？），Alice 认真考虑了 Bob 的合理质疑，并给出了另一个方法。

我在纸上写一个数字 0 或者 1，然后把它倒扣在桌上，你看不到纸上写了什么，但是你可以监督我没有修改或者掉包。现在你猜测纸上是 0 还是 1，如果你猜错了，你就得买单。

这项方法的确避开了随机数生成，而且（使用信息论）可以证明，Bob 不存在比随机猜测更好的策略（因为 Bob 不具有任何关于纸上数字的信息）。

那么这就是完美的吗？并不，它抛弃了硬币，却加入了“纸张”这一道具。“纸张”可以看做一个可靠的第三方，它可以存储 Alice 一开始写下的 0/1，并且可以保证不被修改。

  • 假设：双方互不信任，且不存在一个双方都信任的第三方

如果 Alice 和 Bob 在面对面商议，Bob 的确容易监督纸张没有被掉包。但如果他们在用 WeChat 聊天，Bob 没办法亲眼监督 Alice 手上的纸。

整个密码学都建立在“怀疑”的基础上，不吝以最大的恶意揣度每个人，密码学算法的目的是让最坏（且最聪明）的坏人也乖乖就范，没有捣乱的空间，这样大家才能放一万个心。

如果存在一个双方都信任的第三方（比如 Bob 他爸），问题就太简单了，直接让 TA 制备一枚公平的硬币就行，这不是密码学感兴趣的情况。

  • Coin Flip 不可解决？

好吧，拿出一个道具，密码学就 ban 一个，硬币和纸条都不给用，接下来怎么办呢？

不能用硬币，说明方案中不能含有公认随机的成分。不能用纸条，说明只有公开的信息能被公认（只有一方知晓的信息可以随意修改，对方不会发现）。

根据 Game Theory，任何一种方案都可以被抽象为一种组合游戏，可以证明（由于游戏的每个环节都是确定的），要么 Alice 存在必胜策略，要么 Bob 存在必胜策略（即策梅罗定理），所谓公平方案压根不存在。

理论数学已经为 Coin Flip 宣判了死刑，可密码学不这么认为。密码学家说：是存在必胜策略没错，但是两人的计算能力都是有限的，我让他们算不出必胜策略，不也没关系吗？

  • Coin Flip 的解决

为了理解这一点，我们来看看密码学中的经典道具：单向双射。

  • 单向双射：函数 的定义域为 ，如果 那么 （也就是说 是一个双射）。已知 求 很容易，但已知 求出 是非常困难的。

如果存在这样一种单向双射 ，可以设计如下 Coin Flip 算法：

  • Alice 和 Bob 约定一种单向双射 。

  • Alice 在 中选择一个数 ，计算 ，并公开展示 。

  • Alice 在 中选择一个数 ，Bob 猜测 是否大于 。（此时 Bob 知道 ，但他很难根据 来计算 ）

  • Alice 公开展示 ，如果 Bob 猜错了，他买单。（Bob 可以根据 来验证 Alice 没有偷换 ）

我们认为 Bob 算不出任何关于 的信息，所以他只能随便猜。Alice 不能预知 Bob 会猜什么，她同样占不到任何便宜，而且由于 的存在，她也无法弄虚作假。在这里， 起到一个“签名”的作用。

反过来讲，如果对于任何情况，Bob 都能算出正确的回答，这相当于 Bob 能够根据 求出 。（加一层二分就行）

哎？刚才 Game Theory 不是说 Coin Flip 不能实现吗？现在怎么又弄出来了？这就涉及到理论数学和计算科学的一个本质不同：理论可行（存在一种方案）和计算可行（存在一种可以计算的方案）。

已知 求出 是理论可行的，只要把 的 都计算一遍，逐一比较即可。但是在计算上是不可行的，如果我们把 设得非常大，枚举的时间会非常夸张，反过来讲，我们的“签名”是安全可信的。

这就是计算机科学家的“悲观哲学”，如果某个问题非常难以解决（比如已知 求 ），甚至被证明不能靠计算解决，也不是一件坏事，可以反过来用这个问题来为难坏人，它会成为密码学中最可靠的盾牌。

举个具体例子，依托离散对数的难解性，可以设计如下 Coin Flip 算法：

  • Alice 选择素数 和原根 ，将它们公开展示。

  • Alice 在 中选择一个数 ，公开展示 。

  • Alice 在 中选择一个数 ，Bob 猜测 是否大于 。

  • Alice 公开展示 ，如果 Bob 猜错了，他买单。

（上课给的例子）依托质因数分解的难解性，也可以设计如下 Coin Flip 算法：

  • Alice 选择两个素数 ，满足 ，记 ，公开展示 。

  • Alice 选择一个数 ，公开展示 , 或者 。

  • Bob 猜测展示的是 还是 。

  • Alice 公开展示 ，如果 Bob 猜错了，他买单。

可以证明，如果 Bob 有很好的方法算出自己该猜什么，他就能解决质因数分解问题/离散对数问题。如果 Bob 真的靠作弊取胜，Alice 会很乐意请他一顿，因为吃完饭就可以去领图灵奖了。

Encrypted Communication

  • 什么是加密通信

在日料店里面，Alice 和 Bob 想要交换一些信息，但是他们说的所有话都会被 Eve 听到，Alice 和 Bob 不想让 Eve 知道他们交换的信息，该怎么办呢？

简单起见，不妨设 Alice 和 Bob 想要交换的信息是自然数。

（注：抛硬币问题中，Alice 和 Bob 互相怀疑；通信问题中，Alice 和 Bob 互相信任，对 Eve 怀疑）

这个好办，你说，在进店之前，先约定好一个数字 ，假如谈话时要提到数字 ，就说成 ，对方听到之后减去 就得到正确的信息。而 Eve 不知道 的存在，必然一脸懵逼啊！

可是 Alice 和 Bob 已经进入了日料店，他们已经失去了在门外面讲悄悄话的机会。即使要约定一个对付 Eve 的策略，也只能在店里公开说出来（似乎有点冒犯，如果 Eve 是好人的话）。

  • 加密通信不可解决？

用信息论的话来说，Alice 和 Bob 不具有任何额外共识（比如前文所说的数字 ），而他们的目的（通信）则是在两人之间产生一项新的共识，即共识的无中生有。信息论告诉我们这不可能，因为 Alice、Bob 和 Eve 所具有的初始共识完全相同，他们的地位是对称的。

  • 加密通信的解决：Diffie-Hellman Algorithm

密码学仍然有救场的机会。1976 年，基于离散对数问题的难解性，Whitfield Diffie 和 Martin Hellman 提出了如下算法：

  • （由 Alice 或 Bob）决定一个质数 与原根 ，并将其公开。

  • Alice 在心里想一个数 ，Bob 在心里想一个数 。

  • Alice 公开 ，Bob 公开 。（由于离散对数难解，Eve 不能推理出 ）

  • Alice 可以计算 ，Bob 可以计算 。现在两人同时得到了 作为共识。

有了共识之后，下一步就是通信。为了避免通信内容被 Eve 读懂，需要将其进行加密。

  • 加密：设 为加密函数， 为解密函数，满足 。

    如果要传递信息 ，Alice 公开说出 ，Bob 收到后计算 即可。而 Eve 不会算 ，故无法解密。

    我们可以利用共识 来构造加密函数，例如前文的 。加密、解密函数中的参数（如此处的 ）被称作秘钥。

看起来 就是一个符合要求的加密函数，的确，但在某些更坏的情况下，这个函数并不安全。

  • 防御明文攻击：RSA Algorithm *

Alice 和 Bob 在日料店里加密聊天，与此同时，Eve 通过某些神秘手段，掌握了他们要交换的部分信息的明文。Alice 和 Bob 如何保护其余信息的安全？

  • 明文攻击：Eve 知道某个信息 的明文，当 Alice 说出 时，Eve 可以计算出 ，从而破解整个加密算法。

在日料店里，你完全可以假定 Eve 是纯纯的陌生人，不知道任何关于你们的明文。但数据安全领域的实际情况是，无论保密工作再怎么好，也不可能没有任何泄露，所以防御“牵一发而动全身”的明文攻击是非常重要的。

1978 年，基于质因数分解/离散对数的难解性，Ron Rivest，Adi Shamir 和 Leonard Adleman 提出了如下算法：

  • Alice 准备两个质数 ，计算 。

  • 找出一个数 满足 ，计算 模 的逆元 。

  • 将 公开，自己保留 。

  • Bob 希望发送信息 （满足 ，否则 可以被分解），公开展示 。

  • 由于 ，根据欧拉定理，Alice 计算 即可。

这里将 称作公钥， 称作私钥。

RSA 算法可以防御明文攻击（攻击需要计算离散对数）。

MPC: Secure Multi-party Computation

  • 什么是 MPC

即“多方安全计算”，如果只有两方，可以缩写为 2PC。下面是一个经典的 2PC 问题：百万富翁问题（Millionaires’ Problem）。

Alice 和 Bob 很有钱（钱数为 中的整数），他们打算比较谁更有钱，但不想告诉对方自己具体有多少钱。

和前文的通信问题相同，不存在可信的第三方，所以下列方法是不允许的：

找来 Carle，Alice 告诉 Carle 自己的钱数 ，Bob 告诉 Carle 自己的钱数 ，Carle 比较 的大小，并告知两人。

问题在于，不能保证 Carle 不会向某一方泄露秘密，甚至不能保证 Carle 是诚实的。

  • Millionaires’ Problem 不可解决？

从信息论的视角来看，Millionaires’ Problem 毫不意外是不可解的。

设 Alice 和 Bob 的钱数为 ，如果对于任意 ，都可以成功比较，那么利用 进行二分， Bob 就能得到 的具体取值。

而这一过程中泄露的公共信息只有若干次大小关系，对于旁观者而言，TA 不知道 Bob 选择的 ，所以不能获得信息。也就是说，实现了信息的秘密传输，而上一节中我们证明了信息不能秘密传输，矛盾。

  • Millionaires’ Problem 的解决

全诚实假设： （简单版本）假设 Alice 和 Bob 能完全互相信任。

  • Alice 准备 个信封，编号为 ，在信封 中写上 ，在信封 中写上 。

  • Alice 将信封交给 Bob，Bob 私下里打开信封 ，如果写着 ，说明 ，如果写着 ，说明 。

半诚实假设： 在输出方面，Alice 和 Bob 会严格遵守约定，不会虚报钱数。但在输入方面，他们可能违反约定，多看一些不该看的东西。

在这个规则下，之前的算法就不可行了。Bob 完全可以（不讲武德地）偷偷把所有信封打开，这样他就能得到 的具体取值。

为了完成加强版的问题，我们需要一些更好的装备：

  • 可交换加密：设 为加密函数， 为解密函数，满足 。如果两个加密函数 满足 ，则称这两种加密是可交换的。

    RSA 加密是可交换的。对于两个秘钥 ，不同的加密顺序得到相同的结果（即 ，类似于 D-H 算法）

  • Oblivious transfer：

Alice 拥有一个数组 ，Bob 希望选择一个 ，并得到它的取值。需要保证 Bob 只能得知一个数，而且 Alice 不知道 Bob 取了哪个数。

如果存在一对可交换加密 ，解决方法如下：

  • Alice 计算 ，将 ，交给 Bob。

  • Bob 挑出 ，并计算 ，交给 Alice。（由于 被 Alice 加密过，Bob 不能得知原文）

  • Alice 计算 ，交给 Bob。（由于 被 Bob 加密过，Alice 不能得知这其来自哪个 ）

  • Bob 计算 。

注意，这里 Bob 同时知道了 和 ，构成一组密文/明文，这要求加密方法 可以防御明文攻击。前文的 RSA 算法正符合这一要求。

用 Oblivious transfer 对 Alice 的信封进行包装，我们就解决了 Millionaires’ Problem。

此处还有一些小细节，不能直接令 ，这样 中会出现大量重复的数字，Bob 只需要数一数重复次数就能推理出 0/1 的个数。解决的方法是对输入“加盐”（即冗余信息），使得输入基本不相同，比如用随机偶数代表 ，随机奇数代表 。