计算机入门：现代密码学 Modern Cryptography
command_block · · 个人记录
同步于知乎：Link
Coin Flip Algorithm
-
什么是 Coin Flip
Alice 和 Bob 计划去日料店约会，他们厌倦了 AA，想要以一种公平的方式选出其中一方买单。
如果在现实生活中遇到这种状况（不包括约会在内），你打算怎么解决呢？
当然是抛硬币啦。
我想不少人有过这种经历：站在朋友们中央，从口袋里摸出一枚硬币，高高抛起，看准时机摁在手背上。登登！它的正反将决定接下来的一切，所有人都将听命于你（的运气），开球还是防守？真心话还是大冒险？就此散场还是再喝一轮？等等等等……
抛硬币的确是简单可靠的办法，任何一个有生活经验的人都能瞬间想到。如果 party 开得正嗨，你准备抛硬币决定接下来干嘛，突然有人发表长篇大论，提出如何用数学代替 Coin Flip 云云，恐怕在场各位都要皱起眉头，恨不得把 nerd 写在脸上吧……
然而密码学家就是这样一群较真的家伙，这种较真并不是自娱自乐，相反，它实实在在守护了你的数据和钱包。
-
Coin Flip 有何困难之处
在密码学的世界里，Coin Flip 并不像看起来那样简单。
现实生活中，我们借助“硬币”这一道具完成了 Coin Flip。“硬币”可以视作一种随机数生成器，它以
-
定理：若双方互不信任，无法制备被两人公认的随机数生成器
（即使你有一枚完美的
50/50 硬币，你也不能向对方证明这一点）
打个比方：现在 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 的解决
为了理解这一点，我们来看看密码学中的经典道具：单向双射。
- 单向双射：函数
f 的定义域为1\sim n ，如果x\neq y 那么f(x)\neq f(y) （也就是说f 是一个双射）。已知x 求f(x) 很容易，但已知f(x) 求出x 是非常困难的。
如果存在这样一种单向双射
-
Alice 和 Bob 约定一种单向双射
f 。 -
Alice 在
1\sim n 中选择一个数x ，计算y=f(x) ，并公开展示y 。 -
Alice 在
1\sim n 中选择一个数x_0 ，Bob 猜测x 是否大于x_0 。（此时 Bob 知道y ，但他很难根据y 来计算x ） -
Alice 公开展示
x ，如果 Bob 猜错了，他买单。（Bob 可以根据f(x)=y 来验证 Alice 没有偷换x ）
我们认为 Bob 算不出任何关于
反过来讲，如果对于任何情况，Bob 都能算出正确的回答，这相当于 Bob 能够根据
哎？刚才 Game Theory 不是说 Coin Flip 不能实现吗？现在怎么又弄出来了？这就涉及到理论数学和计算科学的一个本质不同：理论可行（存在一种方案）和计算可行（存在一种可以计算的方案）。
已知
这就是计算机科学家的“悲观哲学”，如果某个问题非常难以解决（比如已知
举个具体例子，依托离散对数的难解性，可以设计如下 Coin Flip 算法：
-
Alice 选择素数
p 和原根g ，将它们公开展示。 -
Alice 在
0\sim p-2 中选择一个数x ，公开展示g^x\bmod p 。 -
Alice 在
0\sim p-2 中选择一个数x_0 ，Bob 猜测x 是否大于x_0 。 -
Alice 公开展示
x ，如果 Bob 猜错了，他买单。
（上课给的例子）依托质因数分解的难解性，也可以设计如下 Coin Flip 算法：
-
Alice 选择两个素数
p,q ，满足p,q\equiv 3\pmod 4 ，记n=pq ，公开展示n 。 -
Alice 选择一个数
x ，公开展示x^2\bmod n , 或者-x^2\bmod n 。 -
Bob 猜测展示的是
x^2\bmod n 还是-x^2\bmod n 。 -
Alice 公开展示
x ，如果 Bob 猜错了，他买单。
可以证明，如果 Bob 有很好的方法算出自己该猜什么，他就能解决质因数分解问题/离散对数问题。如果 Bob 真的靠作弊取胜，Alice 会很乐意请他一顿，因为吃完饭就可以去领图灵奖了。
Encrypted Communication
-
什么是加密通信
在日料店里面，Alice 和 Bob 想要交换一些信息，但是他们说的所有话都会被 Eve 听到，Alice 和 Bob 不想让 Eve 知道他们交换的信息，该怎么办呢？
简单起见，不妨设 Alice 和 Bob 想要交换的信息是自然数。
（注：抛硬币问题中，Alice 和 Bob 互相怀疑；通信问题中，Alice 和 Bob 互相信任，对 Eve 怀疑）
这个好办，你说，在进店之前，先约定好一个数字
可是 Alice 和 Bob 已经进入了日料店，他们已经失去了在门外面讲悄悄话的机会。即使要约定一个对付 Eve 的策略，也只能在店里公开说出来（似乎有点冒犯，如果 Eve 是好人的话）。
-
加密通信不可解决？
用信息论的话来说，Alice 和 Bob 不具有任何额外共识（比如前文所说的数字
-
加密通信的解决：Diffie-Hellman Algorithm
密码学仍然有救场的机会。1976 年，基于离散对数问题的难解性，Whitfield Diffie 和 Martin Hellman 提出了如下算法：
-
（由 Alice 或 Bob）决定一个质数
p 与原根g ，并将其公开。 -
Alice 在心里想一个数
a ，Bob 在心里想一个数b 。 -
Alice 公开
A=g^a\bmod p ，Bob 公开B=g^b\bmod p 。（由于离散对数难解，Eve 不能推理出a,b ） -
Alice 可以计算
B^a=(g^b)^a=g^{ab} ，Bob 可以计算A^b=(g^a)^b=g^{ab} 。现在两人同时得到了g^{ab} 作为共识。
有了共识之后，下一步就是通信。为了避免通信内容被 Eve 读懂，需要将其进行加密。
-
加密：设
f(x) 为加密函数，g(x) 为解密函数，满足g(f(x))=x 。如果要传递信息
x ，Alice 公开说出f(x) ，Bob 收到后计算g(f(x))=x 即可。而 Eve 不会算g ，故无法解密。我们可以利用共识
w 来构造加密函数，例如前文的f(x)=x+w,\ g(x)=x-w 。加密、解密函数中的参数（如此处的w ）被称作秘钥。
看起来
-
防御明文攻击：RSA Algorithm *
Alice 和 Bob 在日料店里加密聊天，与此同时，Eve 通过某些神秘手段，掌握了他们要交换的部分信息的明文。Alice 和 Bob 如何保护其余信息的安全？
- 明文攻击：Eve 知道某个信息
x 的明文，当 Alice 说出f(x)=x+w 时，Eve 可以计算出w ，从而破解整个加密算法。
在日料店里，你完全可以假定 Eve 是纯纯的陌生人，不知道任何关于你们的明文。但数据安全领域的实际情况是，无论保密工作再怎么好，也不可能没有任何泄露，所以防御“牵一发而动全身”的明文攻击是非常重要的。
1978 年，基于质因数分解/离散对数的难解性，Ron Rivest，Adi Shamir 和 Leonard Adleman 提出了如下算法：
-
Alice 准备两个质数
p,q ，计算n=pq,\ m=\varphi(n)=(p-1)(q-1) 。 -
找出一个数
e 满足\gcd(e,m)=1 ，计算e 模m 的逆元d 。 -
将
n,e 公开，自己保留d 。 -
Bob 希望发送信息
x （满足\gcd(x,n)=1 ，否则n 可以被分解），公开展示y=x^e\bmod n 。 -
由于
ed\bmod \varphi(n)=1 ，根据欧拉定理，Alice 计算y^d\bmod n= x^{ed}\bmod n=x 即可。
这里将
RSA 算法可以防御明文攻击（攻击需要计算离散对数）。
MPC: Secure Multi-party Computation
-
什么是 MPC
即“多方安全计算”，如果只有两方，可以缩写为 2PC。下面是一个经典的 2PC 问题：百万富翁问题（Millionaires’ Problem）。
Alice 和 Bob 很有钱（钱数为
1\sim N 中的整数），他们打算比较谁更有钱，但不想告诉对方自己具体有多少钱。
和前文的通信问题相同，不存在可信的第三方，所以下列方法是不允许的：
找来 Carle，Alice 告诉 Carle 自己的钱数
x ，Bob 告诉 Carle 自己的钱数y ，Carle 比较x,y 的大小，并告知两人。
问题在于，不能保证 Carle 不会向某一方泄露秘密，甚至不能保证 Carle 是诚实的。
-
Millionaires’ Problem 不可解决？
从信息论的视角来看，Millionaires’ Problem 毫不意外是不可解的。
设 Alice 和 Bob 的钱数为
而这一过程中泄露的公共信息只有若干次大小关系，对于旁观者而言，TA 不知道 Bob 选择的
-
Millionaires’ Problem 的解决
全诚实假设： （简单版本）假设 Alice 和 Bob 能完全互相信任。
-
Alice 准备
N 个信封，编号为1\sim N ，在信封1\sim a 中写上1 ，在信封a+1\sim N 中写上0 。 -
Alice 将信封交给 Bob，Bob 私下里打开信封
b ，如果写着1 ，说明b\leq a ，如果写着0 ，说明b>a 。
半诚实假设： 在输出方面，Alice 和 Bob 会严格遵守约定，不会虚报钱数。但在输入方面，他们可能违反约定，多看一些不该看的东西。
在这个规则下，之前的算法就不可行了。Bob 完全可以（不讲武德地）偷偷把所有信封打开，这样他就能得到
为了完成加强版的问题，我们需要一些更好的装备：
-
可交换加密：设
f(x) 为加密函数，g(x) 为解密函数，满足g(f(x))=x 。如果两个加密函数f_1,f_2 满足f_1(f_2(x))=f_2(f_1(x)) ，则称这两种加密是可交换的。RSA 加密是可交换的。对于两个秘钥
(n,d_1),(n,d_2) ，不同的加密顺序得到相同的结果（即(x^{d_1})^{d_2}=(x^{d_2})^{d_1}=x^{d_1d_2} ，类似于 D-H 算法） -
Oblivious transfer：
Alice 拥有一个数组
A_{1\sim n} ，Bob 希望选择一个A_k ，并得到它的取值。需要保证 Bob 只能得知一个数，而且 Alice 不知道 Bob 取了哪个数。
如果存在一对可交换加密
-
Alice 计算
A'_i=f_A(A_i) ，将A'_{1\sim n} ，交给 Bob。 -
Bob 挑出
A_k' ，并计算B=f_B(A_k') ，交给 Alice。（由于A' 被 Alice 加密过，Bob 不能得知原文） -
Alice 计算
B'=g_A(B)=f_B(A_k) ，交给 Bob。（由于B 被 Bob 加密过，Alice 不能得知这其来自哪个A ） -
Bob 计算
g_B(B')=A_k 。
注意，这里 Bob 同时知道了
用 Oblivious transfer 对 Alice 的信封进行包装，我们就解决了 Millionaires’ Problem。
此处还有一些小细节，不能直接令