Trusted 3^rd parties

两个用户可以通过共享一个密钥来保护通信数据，那么，这两个用户是如何产生这个共享密钥的？

密钥管理

试想，世界上有 n 位用户，那么这些用户如何管理这些密钥？

假设 n=4 ，一种方案是，每一对用户共享一对密钥，这样用户需要管理的共享密钥太多。

有一种方法叫在线可信任第三方，使用 TTP 表示可信任第三方，每个用户与可信任第三方共享一个单独的密钥，这个设计的好处是每个用户只需记住一个密钥。当 Alice 想和 Bob 通信时会发生什么？

双方必须参加某个特定协议，在协议的最后，他们会共享一个密钥 K_AB ，而攻击者不能知道 K_AB ，Alice 想和 Bob 如何生成这一共享密钥 K_AB ？

看一个玩具协议，这个协议对窃听是安全的，对篡改或主动攻击不安全，Alice 有她的密钥 $k_A$ ，Bob有他的密钥 $k_B$ ，$k_A$、$k_B$ 是与可信任第三方共享的。这个协议如下工作：

Alice 开始时会发送一条信息，给可信任第三方，说她想要一个密钥用于和Bob通信，可信任第三方会选择一个随机密钥 k_AB ，那么可信任第三方生成了他们的共享密钥，他会回复一条信息给 Alice ，这条信息包含两部分，①使用 $k_A$ 加密的信息，这个密钥在 Alice 和 Bob 之间使用，k_AB 包含在这条信息里，即，这里被加密的信息是，k_AB 加上“这个密钥是Alice 和 Bob的共享密钥”这一事实。②票据，这个票据是为 Bob 加密的信息，是使用 $k_B$ 加密的，加密的信息依然是“这个密钥在 Alice 和 Bob 之间使用”，然后 TTP 把这个事实附在密钥 k_AB 后面。这里使用的加密系统 E 是一个 CPA 安全密码，当 Alice 想与 Bob 通信时，Alice 会解密给她的那部分信息得到密钥 k_AB ，然后把票据给 Bob ，Bob 收到这个票据，使用 $k_B$ 解密得到密钥 k_AB ，他们就有了共享密钥。

为什么这个协议是窃听安全的？

当我们只考虑对窃听的安全时，窃听者在这个协议中看到两个密文，我们的目标是，窃听者没有任何关于交换密钥 k_AB 的信息，这点可由密码 E,D 的 CPA 安全性直接得到。

对于每个密钥交换，TTP是必须使用的，这个协议的另一个性质是，TTP 知道所有的会话密钥，如果 TTP 被破解了，那么攻击者可以轻松获得所有系统中用户之间已经交换过的密钥。这个机制的优点是，它只使用对称密钥密码学，是快速有效的。

这个协议对主动攻击是完全不安全的，如，重放攻击：

设想 Alice 从 Bob 那里订购了一本书，Bob 接收了这本书的付款，然后发给 Alice 一份这本书的拷贝，交易完成。设想攻击者记下了 Alice 和在线商家 Bob 的会话，稍后向 Bob重放这段会话，Bob 就会认为，Alice刚刚重新订购了这本书的另一份拷贝，Bob 就会再收一次 Alice 的钱，然后发给 Alice 这份拷贝，所以，重放会话会对 Alice 造成巨大危害

我们能否设计出密钥交换协议，对窃听和主动攻击都保持安全呢？我们能否设计出安全的密钥交换协议，但不需要一个在线的可信任第三方呢？答案是可能的。事实上，这是公钥密码学的起点，思路如下：

①由 Ralph Merkle 于1974年提出。

②由 Diffie 与 Hellman 于 1976年提出。

③由 Rivest，Shamir，Adleman 于1977年提出。

近年的新想法：①基于身份的加密（IBE）2001。②泛函加密，2011。

Merkle Puzzles

不借助可信第三方的密钥交换协议。

这里我们通常的设定是，有 Alice 和 Bob ，他们想生成一个共享密钥，他们互相发送信息，在协议的最后，他们必须获得某个双方都知道的共享密钥 k ，窃听通信流量的攻击者绝对无法得知这个 k 是什么，目前，我们只关心监听会话的攻击者，我们将看到三个协议来达到这一目标。

能借助对称密码学做到吗？可不可以只使用分组密码或哈希函数等？答案是肯定的，但是得到的协议非常低效，在实际中从未被使用，不过这些协议非常简单，Merkle 谜题协议工作流程如下：

这个协议的主要工具叫做一个“谜题”，谜题是指难解的问题，但通过努力还是可以解出的。假设我们有一个对称密码，使用 128 位密钥，以 AES 为例，假设我选择的 AES 密钥的前 96 位都是 0 ，只有剩下的 32 位是非零的，并随机选取的。现在我加密一段固定的明文，比如“message”，使用 128 位密钥，大部分位都是 0 ，加密的结果叫做“谜题”，称之为谜题是因为不难找到密钥 P ，只需要尝试 2^32 种可能性，看是否得到明文“message”，如果是的话，就知道已经发现了正确的 P 。

Merkle谜题协议工作方式如下：

Alice 开始时生成大量的谜题，特别地，她将生成 2^32 个不同的谜题，对于每个谜题，她生成的方法如下：选择一个 32 位随机谜题 $P_i$ ，i 从 1 遍历到 2^32 ，然后她再选择两个值 $x_i$ 和 $k_i$ ，每个 128 位，现在她会使用谜题 $P_i$ 作为一个 AES 密钥，前 96 位都是 0 ，后 32 位非零，所以这个密钥的熵是 32 位，如果只有 2^32 个密钥，现在他要使用这个密钥加密的明文是下图中红色部分的信息，她对所有的谜题都这么做得到了 2^32 个不同的谜题，然后把所有的谜题发送给 Bob 。

Bob 接收了 2^32 个不同的谜题，他只选择其中一个，不需要记住所有的谜题，比如说他选择了谜题 j ，他花了 2^32 的时间来解决这个谜题，他要检查明文的前面部分是否以“Puzzle”开头，如果是，Bob 就知道了他正确的解决了这个谜题，然后他就获得了嵌在谜题里的数据 $x_j$ 和 $k_j$ ，$x_j$ 是这个谜题的标记，$k_j$ 是他们要使用的秘密信息，然后他把 $x_j$ 发送给 Alice ，$k_j$ 自己保留，作为秘密。

Alice 查找谜题数据库，她会查到谜题 $x_j$ ，就知道了 Bob 选择的密钥 $k_j$ ，他们就有了这个共享密钥。

窃听者看着 n 个谜题发送过去，看到 Bob 返回了一个 $x_j$ ，攻击者并不知道 Bob 解的是哪个谜题，他看到的只是谜题中的随机值，为了破解这个协议，窃听者会解决所有的谜题，直到他找到正确的谜题里面有 $x_j$ ，那么攻击者就会还原 $k_j$ ，那么，攻击者要做多少工作？$n^2$ 。

我们能否只使用对称密码，做得比平方鸿沟更好呢？答案是未知的，我们不知道平方鸿沟是否是我们所能做到的最好的结果。

事实上，如果我们把分组密码或哈希函数当作黑盒神谕来使用，换句话说，参与者只能询问分组密码或询问哈希函数在特定点的值并获得结果，如果这些是参与者所能做到的全部，换句话说，参与者不能实际使用分组密码或哈希函数的实现，那么事实上有一个结果告诉我们，如果参与者只能询问分组密码在 n 个点的值，那么总有一个攻击运行在 n 平方的时间里。这就是说，如果你只能使用分组密码作为一个黑盒进行询问，那么无论交换什么密钥，这个密钥交换总有一个平方时间的攻击。

我们发现，我们需要比分组密码和哈希函数更多的技术，实际上，我们需要具备非常特殊性质的函数，为了构建这些函数，我们实际上必须依赖于某些代数。

The Diffie-Hellman protocol

Diffie-Hellman 协议

这是我们第一个实用的密钥交换机制。

Alice 和 Bob 素未谋面，却想交换一个共享密钥，然后他们可以使用这个密钥来用于相互安全通信，我们只看对窃听攻击的安全性，攻击者不能篡改网络中的数据，在密钥交换协议的最后，Alice 和 Bob 应该有一个共享密钥，但窃听攻击者无法知道交换的密钥是什么。我们能否做与Merkle谜题协议同样的事情，但现在能获得一个指数级鸿沟，横亘在攻击者和参与者的工作之间？我们不能仅凭分组密码技术获得这个指数级鸿沟，我们必须使用拥有比对称原型更多结构的难解问题，那么我们使用一点代数。

Diffie-Hellman 协议是如何工作的呢？

首先，我们选某个固定的大质数，记为 p ，然后我们选一个固定的整数 g ，g 正好在从 1 到 p 的范围中，这里的 p 和 g 是 Diffie-Hellman 协议的参数，它们一经选择就不再改变。这个协议如下工作：

开始时， Alice 选择某个随机数 a ，范围是 1 到 p-1 ，然后她将计算 $g^a$ (mod p) ，这是可以有效计算的，我们把这个计算的结果记为 A ，发送给 Bob 。现在，Bob 做同样的事情，他选择一个随机数 b ，范围是 1 到 p-1 ，计算 $g^b$ (mod p) ，结果记为 B ，发送给 Alice 。现在他们宣布已经共享了一个密钥，那么这个共享的密钥是什么呢？我们记为 k_AB = g^(ab) (mod p) 。事实上，双方都可以计算 k_AB ，Alice 可以取值 B ，计算 $B^a$ (mod p) ，获得 g^(ab) (mod p) ，Bob 也可以做类似的事情。这个协议顺利工作的本质原因是指数的代数性质。

为什么这个协议是安全的？

窃听者能看到什么？他能看到质数 p 和生成元 g ，这些值是永远固定不变的，每个人都知道它们，攻击者还能看到 Alice 发送给 Bob 的 A 和 Bob 发送给 Alice 的 B ，那么，窃听者能计算出 g^(ab) (mod p) 吗？更一般地，我们定义 DH 函数，我们说 DH 函数定义在 g 上，给定 $g^a$ 和 $g^b$ ，能否计算 g^(ab) ？p 大约有 600 个十进制位，计算这个很大的质数模 p 乘法群上的函数，有多困难？

目前已知的事实，这个质数正好有 n 位长，计算 DH 函数已知最好的算法是一个更为一般的算法，用来计算离散对数函数，这个算法叫做普通数域筛法。这个算法的运行时间是指数级的，运行时间大约是 e 的 n 的立方根次方，事实上这个算法的运行时间的严格表达式要比这个复杂的多，这个算法有时叫做亚指数算法，因为这里的指数项正比于 n 的立方根，而不是 n ，这说明即使这个问题很难，它也不是真正的指数级时间的问题，运行时间的指数是与 n 的立方根成正比的。

看几个例子，如果你的密码有 80 位密钥，那大概需要 1000 位的模，这个算法是说我们可以以时间大约是 e 的 1024 的立方根次方解决 DH 问题，这不是很准确，事实上指数上有一些常数项。这个例子告诉大家，如果有一个亚指数级算法，即使看到这个问题规模很大，比如 1000 位，因为这个立方根的作用，其实总体并没有那么大。

如果要使用 Diffie-Hellman 协议来交换会话密钥，用于分组密码的会话密钥要有合适的密钥大小，使得密钥交换协议的安全性和之后使用的分组密码的安全性相当。

计算在椭圆曲线域上的 Diffie-Hellman 函数要比计算质数模乘法上的 Diffie-Hellman 困难得多，因为问题更加困难，可以使用小得多的代数对象。这些模在椭圆曲线上增长的不快，通常从使用模算术到使用椭圆曲线域有一个缓慢的转换。

中间人攻击

Diffie-Hellman 协议对抗主动攻击时，是完全不安全的，当存在中间人攻击时，我们需要对这个协议做些补充，让它对中间人攻击也是安全的。

这个协议为什么对主动攻击是不安全的？

假设我们有中间人 MiTM 试图窃听 Alice 和 Bob 之间的会话，协议开始时，Alice 发送 $g^a$ 给 Bob ，中间人截获了这个 $g^a$ ，他将取 Alice 发出的信息，换成他自己的信息，记为 A’ ，写成 $g^a$’ ，中间人选择了他自己的 a’ ，发送给 Bob 。

Bob并不知道中间人对通信流量做了手脚，他只能获得 A’ ，Bob 会回复他的值 B ，$g^b$ 给 Alice ，中间人截获 B ，产生自己的 b’ ，然后发送 B’=$g^b$’ 给 Alice 。

Alice 将计算她的密钥得到 g^(ab’) ，Bob 计算他的密钥 g^(ba’) ，而对于中间人，他既知道 A’ ，又知道 B’ ，他可以计算 g^(ab’) ，也可以计算 g^(ba’) ，因此现在它可以扮演中间人。

当 Alice 发送一个加密的信息给 Bob ，中间人可以轻松解密这个信息，然后中间人重新使用 Bob 的密钥加密这个信息发送给 Bob ，这样 Alice 发送信息给 Bob ，Bob 接收信息认为这个信息是安全的。中间人可以完全读到信息内容，如果他愿意，可以修改它，所以这个协议是完全不安全的。

Diffie-Hellman 协议的非互动性

这个协议可以被视为一个非互动的协议，设想我们有一组几百万用户，他们中每个都将选取一个随机的私密值，然后在他们的 Facebook 页面上写下他们对 Diffie-Hellman 协议的贡献。

现在，如果 Alice 和 Charlie 想建立一个共享密钥，他们无需相互通信，Alice 只要去 Charlie 的公共页面，Charlie 只要去 Alice 的公共页面，刹那间，他们就共享了一个密钥，Alice 知道了 g^ca ，Charlie 知道了 g^ac ，某种意义上，一旦他们在公共页面发布了他们对 Diffie-Hellman 协议的共享，他们根本不需要互相通信就能建立共享密钥。

开放问题：我们能否对多于两方的用户做这些呢？换句话说，比如我们有 4 方，所有人都在他们的 Facebook 公共页面上发布了他们的值，现在我们想只通过阅读 Facebook 页面，所有人都可以建立共享密钥。我们是否可以非互动的建立这些共享密钥？n=2 就是 Diffie-Hellman 协议；n=3 ，我们也知道怎么做，有一个已知的协议由 Joux 提出的使用了非常高级的数学；对于 n=4,5… 这个问题是完全开放的，即使只有 4 人，我们也不知道怎么做。

Public-key encryption

一个基于公钥加密的不同的方法，依然只看对窃听的安全性，不允许攻击者修改数据或实施其他形式的主动攻击。

公钥加密

就像对称加密一样，有一个加密算法和解密算法，不过这里的加密算法有一个密钥，叫做公钥 PK，这个公钥属于 Bob ，而解密算法有一个不同的密钥，叫做私钥 SK，也属于 Bob 。这两个密钥优势叫做密钥对。通常，加密这个信息的算法是，加密算法产生一个使用公钥加密的密文，当密文交给解密算法时，解密算法会输出对应的明文

公钥加密实际上由三个算法组成：密钥生成算法 G，E，D。当运行 G 时，会产生两个密钥，分别是公钥和私钥，通常，我们有一致性，即密钥生成算法输出的公钥和私钥，如果我们使用公钥加密明文，然后使用私钥解密，我们可以获得最初的明文。

公钥加密系统的安全游戏

使用与之前用过的语义安全同样的概念，但游戏不同。这里，挑战者运行密钥生成算法来产生一对公钥和私钥，他会把公钥给攻击者，挑战者对私钥进行保密。攻击者会输出两个长度相等的明文 $m_0$ 和 $m_1$ ，挑战者会给攻击者 $m_0$ 或 $m_1$ 的加密结果，我们定义两个实验，在实验0 中，攻击者得到 $m_0$ 加密的结果，在实验1 中，攻击者得到 $m_1$ 加密的结果，攻击者的目标是猜他得到的是哪个明文的加密结果，我们把他的猜测作为实验0 或实验1 的输出。在公钥加密中，没必要赋予攻击者以实施选择明文攻击的能力，因为在对称密钥系统中，攻击者必须请求他选择的明文的加密，而在公钥系统中，攻击者拥有公钥，他可以自己加密任何他想加密的明文。

我们说，如果攻击者无法区分实验0 和实验1 ，一个公钥系统 (G,E,D) 是语义安全的。

共享密钥的建立

①Alice 开始时会使用密钥生成算法为自己产生一个随机公钥、密钥对，然后把公钥 PK 发送给 Bob ，并告诉 Bob 这个信息来自 Alice 。

②Bob 会产生一个随机的 128 位值 x ，回复 Alice 这个信息来自 Bob ，他还会返回用 Alice 的公钥加密的 x 。

③Alice 收到这个密文使用私钥进行解密，解密结果会给她值 x 。

现在，x 可以被用来作为双方共享的密钥。

这与 Diffie-Hellman协议很不相同，这里双方必须有先后的通信，Bob 不能发送他的信息，直到他收到了 Alice 的信息，换句话说，Bob 不能用 Alice 的公钥加密 x ，直到他收到了 Alice 的公钥。即使在 Facebook 发布了公钥，依然需要先发送信息 x 才能建立共享密钥。但在 Diffie-Hellman协议中，双方可以在任何时候发送他们的信息，没有对信息的发送顺序的强制要求。

为什么这个协议是安全的？（只考虑对窃听的安全）

在这个协议中，攻击者看到这个公钥和用公钥加密的 x ，他想得到 x ，现在我们知道这个公钥系统是语义安全的，这意味着攻击者不能区分 x 的加密和某个随机信息的加密，它仅仅是一个随机值，攻击者不能猜到。

即使这个协议对窃听是安全的，对抗中间人攻击时，它也是完全不安全的。

中间人攻击

Alice 产生她的公钥、密钥对，中间人也产生他自己的公钥、密钥对，当 Alice 发送她的公钥给 Bob 时，中间人会截获这个公钥，然后对 Bob 说这个信息来自 Alice，Alice 的公钥是 PK’ 。

Bob 接收了这个信息，他认为自己获得了从 Alice 发来的信息，他会选择随机数 x 进行回复，它会返回用 PK’ 加密的 x ，中间人截获这个信息，他会用其他信息来代替它，他的目标是确保这个密钥交换成功，中间人应该发送什么给 Alice 呢？我们把 Bob 发送的密文记为 c ，中间人使用自己的私钥解密 c 得知 x ，然后他继续用 Alice 的公钥加密 x ，把加密值发回给 Alice ，Alice 获得 x ，完成了与 Bob 的密钥交换。

中间人也知道这个 x ，中间人可以修改 Alice 和 Bob 互发的信息，这个协议是完全不安全的。