11. Key Management and the Public-Key Revolution

提示

对称秘钥管理和公钥革命

11.1 密钥分发与密钥管理

在之前的章节中，我们已经看到私钥密码学如何用于确保两个在不安全通道上通信的参与方的保密性和完整性，前提是这两个参与方持有一个共享的秘密密钥。然而，自第1章以来我们一直拖延的问题是：

$$\text{这些参与方如何在首次建立通信之前共享一个秘密密钥呢？}$$

显然，密钥不能简单地通过不安全的通信渠道传输，因为监听的攻击者将能够观察到密钥，导致密钥不再保密。因此，必须使用其他机制来实现密钥的共享。

在某些情况下，通信参与方可能具有一个安全通道，可以用来可靠地共享一个秘密密钥。一个常见的例子是当两个通信参与方在某个时间点物理上位于同一地点，这时他们可以共享一个密钥。或者，通信参与方可能能够使用一个受信任的快递服务作为安全通道。值得强调的是，即使参与方在某个时刻可以访问安全通道，这并不使私钥密码学无用：在第一个例子中，参与方在某个时刻具有一个安全通道，但以后没有了；在第二个例子中，利用安全通道可能比通过不安全通道通信更慢且更昂贵。

以上方法已经在政府、外交和军事领域用于密钥共享。例如，上世纪60年代连接莫斯科和华盛顿的“红色电话”就是使用一次性密码本进行加密，密钥由飞往对方国家的信使共享，他们携带着打印出来的密钥本。这样的方法也可以在公司中使用，例如在新员工第一天上班时，为中央数据库和新员工建立一个共享密钥。（我们在下一节中会再次提到这个例子。）

然而，依赖于安全通道来分发密钥，在许多其他情况下效果并不好。例如，考虑一个大型跨国公司，在这种公司中，每一对员工都可能需要能够与其他员工安全地通信，同时通信内容也要保护不被其他员工看到。每一对员工为了能够安全地通信，都需要面对与其他员工见面的不便；对于在不同城市工作的员工来说，甚至可能不可能进行见面。即使当前的员工群体以某种方式相互之间能够安全地共享密钥，另一个重要的缺点是每个员工都必须管理和存储N-1个秘密密钥（与公司中其他员工一一对应的密钥）。实际上，这可能严重低估了每个用户所存储的密钥的数量，因为员工可能还需要与远程资源（例如数据库、服务器、打印机等）安全通信所需的密钥。密钥的扩散是一个重大的后勤问题。

此外，所有这些密钥都必须安全地存储。密钥的数量越多，保护它们就越困难，密钥被攻击者窃取的机会就越高。计算机系统往往被病毒、蠕虫和其他形式的恶意软件感染，这些恶意软件可以窃取秘密密钥，并悄悄地通过网络发送给攻击者。因此，在员工的个人计算机上存储密钥并不总是安全的解决方案。

需要明确的是，秘密密钥的潜在泄露始终是一个值得关注的问题，而不管每个参与方持有的密钥数量如何。然而，当只需存储少量密钥时，有很好的解决方案来应对这个威胁。目前的典型解决方案是将密钥存储在安全硬件中，例如智能卡。智能卡可以使用存储的秘密密钥进行加密计算，确保这些密钥永远不会进入用户的个人计算机。如果设计得当，智能卡比个人计算机更能抵抗攻击，例如，它通常无法被恶意软件感染，因此是保护用户秘密密钥的好手段。不幸的是，智能卡的存储容量通常相当有限，因此无法存储数百（或数千）个密钥；此外，智能卡可能有些昂贵，并且如果丢失可能难以替代。

然而，以上概念在“封闭”组织中的应用是可行的，这些组织由一群明确定义的用户组成，他们都愿意遵循相同的密钥分发和存储策略。然而，在“开放系统”中，这些概念可能不再适用，其中用户具有短暂的交互，无法安排面对面会议，甚至可能不知道彼此的存在，直到第一次想要进行通信的时候。实际上，这种情况比人们最初意识到的要普遍得多：考虑从以前从未购买过任何东西的互联网商家处发送信用卡信息，或者向一个从未见过面的人发送电子邮件。在这些情况下，仅靠私钥密码学是无法提供解决方案的，我们必须进一步寻找适当的解决方案。

综上所述，与私钥密码学相关的问题至少有三个不同的问题。第一个问题是密钥分发，第二个问题是存储和管理大量的秘密密钥，第三个问题是私钥密码学在开放系统中不适用。

11.2 一个部分解决方案：密钥分发中心

为了解决上一节中提到的一些问题，我们可以使用密钥分发中心（KDC）来建立共享密钥。考虑一下所有员工都必须能够安全通信的大型公司。在这样的情况下，我们可以利用这样一个事实：所有员工都可能信任某个实体，比如系统管理员，至少在与工作相关的信息的安全性方面是如此。这个可信的实体可以充当KDC，并帮助所有员工共享成对密钥。

当新员工加入时，KDC可以与该员工共享一个密钥（在安全的位置面对面共享）。与此同时，KDC还可以在该员工和所有现有员工之间分发共享密钥。也就是说，当第$i$个员工加入时，KDC可以（除了在其与新员工之间共享一个密钥之外）生成$k_1,\dots ,k_{i-1}$这$i-1$个密钥，并将这些密钥给新员工，然后使用已经与KDC共享的密钥加密密钥$k_j$，并将其发送给第$j$个现有员工。在此之后，新员工与每个其他员工（以及KDC）都共享一个密钥。

一种更好的方法，可以避免要求员工存储和管理多个密钥，是以在线方式利用KDC，在两个员工希望进行安全通信时“按需”生成密钥。与以前一样，KDC会与每个员工共享（不同的）密钥，这可以在每个员工的第一天工作时安全地完成。假设KDC与员工Alice共享密钥$K_A$，与员工Bob共享密钥$K_B$。在以后的某个时间点，当Alice希望与Bob进行安全通信时，她只需向KDC发送消息“我，Alice，想和Bob通话”。（如果需要，此消息可以使用Alice与KDC共享的密钥进行认证。）然后，KDC会选择一个新的、随机的密钥——称为会话密钥$k$，并使用$K_A$加密该密钥$k$发送给Alice，并使用$K_B$加密该密钥$k$发送给Bob。（这个协议过于简单，不能在实践中使用；请参考下面的进一步讨论。）一旦Alice和Bob都获取了这个会话密钥，他们可以使用它进行安全通信。在结束对话时，他们应该擦除会话密钥，因为如果他们想在以后的某个时间进行通信，他们可以随时再次联系KDC。

考虑这种方法的优势：

1. 每个员工只需要存储一个长期的秘密密钥（即与KDC共享的密钥）。员工仍然需要管理和存储会话密钥，但这些是短期密钥，在通信会话结束后会被擦除。

   • 这样，员工只需要记住一个长期密钥，大大简化了密钥的管理。而会话密钥是临时的，通常存储在内存中，并在通信会话结束后被销毁，不会占用过多的存储空间。

2. KDC需要存储许多长期密钥。然而，KDC可以放置在安全的位置，并采取最高级别的网络攻击防护措施。

   • KDC作为一个可信实体，负责存储和分发长期密钥。由于它在安全位置，受到严格的保护，可以减少密钥泄露的风险。

3. 当新员工加入组织时，只需在该员工与KDC之间建立一个密钥。其他员工无需更新他们持有的密钥集合。

   • 这简化了密钥分发过程，新员工只需要在入职的第一天与KDC建立密钥即可。其他员工无需进行任何操作，仍然可以使用之前建立的密钥与新员工进行安全通信。

因此，KDC可以解决私钥加密中的两个问题：简化密钥分发和降低密钥存储的复杂性。在一个拥有单一可信实体的大型组织中，KDC可以让私钥加密变得更加实用。

然而，依赖KDC也存在一些缺点：

1. 对KDC的成功攻击将导致整个系统的完全崩溃：攻击者可以破坏所有密钥，然后监听所有的网络流量。这使得KDC成为一个高价值的目标。需要注意的是，即使KDC对外部攻击有良好的保护，仍然存在内部攻击的可能性，比如由具有KDC访问权限的员工（例如IT经理）进行的攻击。

2. KDC是单点故障：如果KDC宕机，安全通信将暂时不可能。如果员工不断地与KDC联系并请求建立会话密钥，KDC的负载可能非常高，从而增加了其可能失败或响应缓慢的机会。

针对第二个问题的一个简单解决方案是复制KDC。这在实践中是有效的，但也意味着系统现在有更多的攻击点。添加更多的KDC也会增加添加新员工的难度，因为更新必须安全地传播到每个KDC。

使用KDC进行密钥分发的协议。文献中有许多用于使用KDC进行安全密钥分发的协议。我们特别提到Needham-Schroeder协议，它是Kerberos的核心，Kerberos是一种重要且广泛使用的服务，用于执行身份验证并支持安全通信。（Kerberos在许多大学和公司中使用，在Windows和许多UNIX系统中是支持安全网络身份验证和通信的默认机制。）

我们只强调该协议的一个特性。当Alice联系KDC并要求与Bob进行通信时，KDC不会像之前描述的那样同时将加密的会话密钥发送给Alice和Bob。相反，KDC会将会话密钥分别使用Alice的密钥和Bob的密钥加密后发送给Alice。然后Alice将第二个密文转发给Bob，如图11.1所示。第二个密文有时被称为"ticket"，可以看作是允许Alice与Bob通信的凭证（同时也使Bob确信他正在与Alice通信）。实际上，尽管我们在讨论中没有强调这一点，基于KDC的方法还可以提供一个执行身份验证的有用手段。同时注意，Alice和Bob不一定都是用户；Alice可能是一个用户，而Bob可能是一个资源，如远程服务器、数据库或打印机。

设计该协议的方式是为了减轻KDC的负担。在描述的协议中，KDC不需要对Bob发起第二个连接，也不需要担心当Alice启动协议时Bob是否在线。此外，如果Alice保留了"ticket"（以及她的会话密钥的副本），那么她可以通过简单地将"ticket"重新发送给Bob来重新启动与Bob的安全通信，而完全不涉及KDC。（在实践中，"ticket"会过期，并且最终需要更新。但是在一定的可接受时间段内，会话可以重新建立。）

最后要指出的是，在实践中，Alice与KDC共享的密钥可能是一个简短、易于记忆的密码。在这种情况下，将会出现许多额外的安全问题需要解决。此外，我们在暗示一个只进行被动监听而不会主动干扰协议的攻击者。对于如何处理此类问题，感兴趣的读者可以参考本章末尾的参考文献。

11.3 密钥交换与Diffie-Hellman协议

虽然KDC和像Kerberos这样的协议在实践中被使用，但这些解决密钥分发问题的方法仍然需要在某个时刻使用一个私有且经过认证的信道来共享密钥。（特别是，我们假设在KDC和员工在其第一天工作时之间存在这样一个信道。）因此，它们仍然无法解决在像互联网这样的开放系统中的密钥分发问题，因为两个希望通信的用户之间可能没有私有信道可用。

为了实现在没有私有信道的情况下进行私密通信，需要采用完全不同的方法。在1976年，Whitfield Diffie和Martin Hellman发表了一篇题为“密码学的新方向”的论文。在这篇论文中，他们观察到世界上通常存在着不对称性；特别地，有些操作可以很容易地执行，但是很难逆转。例如，可以在没有钥匙的情况下（即容易地）锁上挂锁，但无法重新打开。更引人注目的是，打碎一个玻璃花瓶很容易，但是将它重新组装在一起非常困难。在算法上（对于我们的目的更相关），很容易将两个大质数相乘，但是从它们的乘积中恢复这些质数则很困难。（这正是前面章节中讨论的因子分解问题。）Diffie和Hellman意识到这样的现象可以用来推导出安全的密钥交换协议，使得两个参与方可以通过在公共信道上进行通信，并执行对手无法逆转的操作来共享一个秘密密钥。

安全密钥交换协议的存在非常令人惊奇。这意味着你和你的朋友可以通过在一个房间里大声喊叫（并进行一些本地计算）来协商一个秘密，而这个秘密对于任何其他人都是未知的，即使他们听到了所有的话。事实上，在1976年之前，人们普遍认为在没有通过私有信道共享一些秘密信息之前，无法进行安全通信。

Diffie和Hellman的论文产生了巨大的影响。除了引入了一种根本性的新的密码学视角，这也是将密码学从私有领域引入公共领域的首要步骤之一。我们引用他们论文的前两段：

“我们今天站在密码学革命的边缘。廉价数字硬件的发展使其摆脱了机械计算的设计限制，将高等级加密设备的成本降低到可以用于商业应用，如远程取款机和计算机终端。”

“反过来，这些应用程序对新类型的密码系统产生了需求，以最大程度地减少安全密钥分发通道的必要性……同时，信息论和计算机科学的理论发展有望提供可证明安全的加密系统，将这古老的艺术变成一门科学。”

Diffie和Hellman并没有夸大其词，他们所说的革命在很大程度上归功于他们的工作。

在本节中，我们介绍了Diffie-Hellman密钥交换协议。我们证明了它对于窃听对手的安全性，或者等价地说，我们假设各方通过一个公开但经过认证的信道进行通信（因此攻击者无法干扰他们的通信）。对于窃听对手的安全性是相对较弱的保证，在实践中，密钥交换协议必须满足比我们目前讨论的更强的安全性概念。（此外，在这里我们感兴趣的是通信双方没有先前共享信息的情况，因此没有办法阻止攻击者冒充其中一方。我们稍后会回到这一点。）

基本情况及安全定义。 考虑这样一种情形，通信双方Alice和Bob运行协议产生一对共享的保密密钥；把该协议记为$\mathrm{\Pi }$(这样$\mathrm{\Pi }$可以看作是协议中给Alice和Bob的一组指令)。首先Alice和Bob持有安全参数$1^n$,然后(相互独立地)随机选择并执行协议$\mathrm{\Pi }$。在协议的最后，Alice和Bob分别输出密钥$k_A$和$k_B\in \{0,1{\}}^n$。对$\mathrm{\Pi }$协议最基本的要求是$k_A=k_B$(对所有Alice和Bob的随机选择)。由于只需要让协议满足这个要求，简单地称：诚实地执行$\mathrm{\Pi }$协议产生了密钥$k=k_A=k_B$。

现在我们转向定义安全性。直观上讲，密钥交换协议是安全的，如果由Alice和Bob输出的密钥$k$对于一个窃听者是完全隐藏的。这可以通过要求在协议的执行中，一个窃听者无法将由该执行生成的密钥$k$（现在由Alice和Bob共享）与一个长度为$n$的均匀密钥区分开来来进行形式化定义。这种定义要求比仅仅要求窃听者无法完全猜测$k$更加严格，而且当Alice和Bob随后将$k$用于某些密码学应用时，这种更严格的定义是必要的（例如，作为私钥加密方案的密钥）。

我们现在来定义实验过程。假设Π是一个密钥交换协议，$A$是一个对手，$n$是安全参数。我们有以下实验：

敌手$A$得到副本trans表示A窃听整个协议执行的过程，即敌手可看到通信双方之间的所有通信。当然，在现实世界中，$A$不会得到任何密钥；上面实验中的敌手得到只是作为一个手段来定义敌手$A$攻破$\mathrm{\Pi }$。也就是说，如果敌手A可以正确地区分$\hat{k}$是执行协议得到的密钥，还是一个独立于副本的完全随机的密钥，那么敌手就成功地攻破了$\mathrm{\Pi }$。正如预期的一样，如果敌手成功的可能性上限大于1/2的部分可忽略，则认为Ⅱ是安全的。即：

定义11.1 如果对每个概率多项式时间的敌手$\mathcal{A}$,都存在一个可忽略函数$negl$,满足下列公式则密钥交换协议Ⅱ在存在窃听者的情况下是安全的。

$$\mathrm{Pr}[{\mathrm{KE}}_{\mathcal{A},\mathrm{\Pi }}^{\mathrm{eav}}(\eta )⟹1]\le \frac{1}{2}+negl(\eta ).$$

密钥交换协议的目的几乎总是生成一个共享密钥k，它将被双方用于进一步的加密目的，例如，使用经过身份验证的加密方案对其随后的通信进行加密和身份验证。直观地说，使用由安全密钥交换协议生成的共享密钥应该与使用通过私有通道共享的密钥“一样好”。有可能正式证明这一点；请参见练习11.1。

Diffie-Hellman密钥交换协议。现在我们描述一下Diffie和Hellman原始论文中提出的密钥交换协议（虽然他们的描述没有我们这里那么正式）。设$\mathcal{G}$是一个概率多项式时间算法，它以安全参数$1^n$为输入，输出一个循环群$\mathbb{G}$的描述，群的阶为$q$（$||q||=n$），以及一个生成元$g\in \mathbb{G}$。（参见第9.3.2节。）Diffie-Hellman密钥交换协议被正式地描述为构造11.2，并在图11.2中进行了说明。

在我们的描述中，我们假设Alice生成$(\mathbb{G},q,g)$并将这些参数作为她的第一条消息发送给Bob。实际上，这些参数是标准化的，并且在协议开始之前双方都知道。在这种情况下，Alice只需要发送$h_A$，而Bob不需要等待接收Alice的消息就可以计算并发送$h_B$。

很容易看出协议是正确的：Bob计算密钥$k_B=h_A^y=(g^x{)}^y=g^{xy}$，而Alice计算密钥$k_A=h_B^x=(g^y{)}^x=g^{xy}$，因此$k_A=k_B$。（敏锐的读者会注意到，共享密钥是一个群元素，而不是比特串。我们将在稍后回到这一点。）

这里的$h_A$和$h_B$实际上是Diffie-Hellman密钥交换协议中的协商公钥，而$x$和$y$是各自的私密随机数。通过使用协商公钥和私密随机数的幂运算，Alice和Bob最终得到相同的共享密钥，实现了安全的密钥交换。

需要注意的是，由于离散对数问题的难解性，即使在公开通信渠道上，对手也无法轻易地获得$h_A$和$h_B$的值，从而确保了密钥交换的安全性。同时，由于使用了循环群中的指数运算，所得到的共享密钥$k_A$和$k_B$是相同的。

Diffie和Hellman没有证明他们的协议的安全性；实际上，适当的概念（包括定义框架和制定精确的假设）还没有形成。让我们看看为了使协议安全需要什么样的假设。Diffie和Hellman首先观察到，这里安全的一个最小要求是相对于$\mathcal{G}$离散对数问题是困难的。如果不是这样，那么给定传输记录（其中特别包括$h_A$），攻击者可以计算出其中一个参与方的秘密值（即$x$），然后轻松地使用该值计算出共享密钥。因此，离散对数问题的困难性对于协议的安全性是必要条件。然而，它并不是充分条件，因为可能存在其他的方法计算密钥$k_A=k_B$，而无需明确地计算$x$或$y$。仅满足计算性Diffie-Hellman假设——即从传输记录中计算整个密钥$g^{xy}$是困难的——也是不够的。根据Definition 11.1所要求的是，对于给定$g$、$g^x$和$g^y$，共享密钥$g^{xy}$对于任何攻击者都应该与均匀密钥不可区分。这正是Section 9.3.2中引入的决策性Diffie-Hellman假设。

正如我们将看到的，协议的安全性证明几乎立即可以从决策性Diffie-Hellman假设中得出。这并不奇怪，因为决策性Diffie-Hellman假设是在Diffie和Hellman发表论文后引入的，作为抽象Diffie-Hellman协议（猜测的）安全性背后的属性的一种方式。鉴于此，可以合理地问，通过在这里定义和证明安全性是否有所收获。在本书的这一部分，希望您已经相信答案是肯定的。对密钥交换协议进行准确的安全性定义迫使我们思考我们想要的确切安全性质；指定一个精确的假设（即决策性Diffie-Hellman假设）意味着我们可以独立于任何特定应用来研究该假设，并且一旦我们相信它是合理的，就可以基于它构建其他协议；最后，证明安全性表明该假设确实足以使协议满足我们所期望的安全性定义。

在我们的安全性证明中，我们使用了Definition 11.1的修改版本，其中要求共享密钥与G中的均匀元素不可区分，而不是与均匀的n位比特串不可区分。然而，在实际应用中，需要解决这种差异——毕竟，群元素通常不适用作密码学密钥，并且均匀群元素的表示通常不是均匀的比特串。在我们的证明后，我们将简要讨论一种标准的方法来解决这个问题。目前，我们让${\widehat{KE}}_{A,\mathrm{\Pi }}^{eva}(n)$表示一个修改后的实验，在该实验中，如果b = 1，则$\hat{k}$是从$\mathbb{G}$中均匀选择的，而不是从$\{0,1{\}}^n$中均匀选择的。

Definition11.1 如果$\mathcal{G}$相关判定性Diffie-Hellman问题是困难的，则Diffie-Hellman秘钥交换协议$\mathrm{\Pi }$在窃听者存在的情况下是安全的（根据修改的实验${\widehat{KE}}_{\mathcal{A},\mathrm{\Pi }}^{eav}(n)$）。
证明 证明所依据的直觉已经在上面给出，下面给出详细说明。取$\mathcal{A}$作为一个PPT攻击者。由于$Pr[b=0]=Pr[b=1]=1/2$,有

$$\begin{array}{rl}Pr[{\widehat{\mathsf{K}E}}_{\mathcal{A},\mathrm{\Pi }}^{\mathsf{eav}}(n)=1]& =\frac{1}{2}\cdot Pr[{\widehat{\mathsf{K}E}}_{\mathcal{A},\mathrm{\Pi }}^{\mathsf{eav}}(n)=1\mid b=0]+\frac{1}{2}\cdot Pr[{\widehat{\mathsf{K}E}}_{\mathcal{A},\mathrm{\Pi }}^{\mathsf{eav}}(n)=1\mid b=1].\end{array}$$

在实验${\widehat{KE}}_{\mathcal{A},\mathrm{\Pi }}^{eav}(n)$中敌手收到$(\mathbb{G},q,g,h_1,h_2)$表示执行协议的副本，$\hat{k}$要么是通信方计算出来的真实秘钥$g^{xy}$(如果b=1)，要么是一个随机的群元素（如果b=0）。区分这两种情况和解决判定性Diffie-Hellman问题是等价的，使用下方公式：

$$\begin{array}{rl}Pr[{\widehat{\mathsf{KE}}}_{\mathcal{A},\mathrm{\Pi }}^{\mathsf{eav}}(n)=1]& =\frac{1}{2}\cdot Pr[{\widehat{\mathsf{KE}}}_{\mathcal{A},\mathrm{\Pi }}^{\mathsf{eav}}(n)=1\mid b=0]+\frac{1}{2}\cdot Pr[{\widehat{\mathsf{KE}}}_{\mathcal{A},\mathrm{\Pi }}^{\mathsf{eav}}(n)=1\mid b=1]\\ & =\frac{1}{2}\cdot Pr[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^{xy})=0]+\frac{1}{2}\cdot Pr[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^{xy})=1]\\ & =\frac{1}{2}\cdot (1-Pr[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^{xy})=1])+\frac{1}{2}\cdot Pr[\mathcal{A}(\mathbb{G},q,g^x,g^y,g^z)=1]\\ & =\frac{1}{2}+\frac{1}{2}\cdot (Pr[\mathcal{A}(\mathbb{G},q,g^x,g^y,g^z)=1]-Pr[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^{xy})=1])\\ & \le \frac{1}{2}+\frac{1}{2}\cdot |Pr[\mathcal{A}(\mathbb{G},q,g^x,g^y,g^z)=1]-Pr[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^{xy})=1]|.\end{array}$$

其中最后三行的概率由$\mathcal{G}(1^n)$从$(\mathbb{G},q,g)$上输出，$x,y,z\in {\mathbb{Z}}_q$。（注意，由于g是生成元，当z在${\mathbb{Z}}_q$均匀分布时，$g^z$是$\mathbb{G}$上均匀分布的一个元素。）如果判定性Diffie-Hellman假设相对于$\mathcal{G}$是困难的，这就意味着存在一个可忽略的函数$negl$满足：

$$|Pr[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^z)=1]-Pr[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^{xy})=1]|\le \text{negl}(n).$$

因此，

$$\mathrm{Pr}[{\widehat{\text{KE}}}_{\mathcal{A},\mathrm{\Pi }}^{\text{eav}}(n)=1]\le \frac{1}{2}+\frac{1}{2}\cdot \text{negl}(n),$$

证毕。

随机群元素与随机串的比较。 前面的定理表明，Diffie-Hellman协议中Alice和Bob输出的密钥在多项式时间窃听者面前是不可区分的，可以视为均匀的群元素。然而，为了将密钥用于后续的加密应用，同时满足Definition 11.1的要求，输出的密钥应该是与合适长度的均匀比特串不可区分的。可以通过让参与方将它们各自计算得到的共享群元素$g^{xy}$应用适当的密钥派生函数（见Section 6.6.4）来修改Diffie-Hellman协议，从而实现这一点。

主动攻击者。到目前为止，我们只考虑了窃听攻击者。虽然窃听攻击是最常见的攻击方式（因为最容易实施），但它们并不是唯一可能的攻击。主动攻击，即攻击者向一个或两个参与方发送自己的消息，也是一个令人担忧的问题，任何实际使用的协议都必须对此类攻击具有抵抗力。在考虑主动攻击时，可以简单地区分冒充攻击和中间人攻击。前者是攻击者在与另一方进行交互时冒充其中一方的身份，而后者是指诚实方之间正在执行协议，而攻击者拦截和修改从一方发送到另一方的消息。我们不会对这两类攻击定义形式化的安全性，因为这样的定义非常复杂，并且不能在参与方事先共享一些信息的情况下实现。尽管如此，值得注意的是，Diffie-Hellman协议对中间人攻击是完全不安全的。事实上，中间人攻击者可以通过特定方式操作，使得Alice和Bob分别终止协议并生成不同的密钥$k_A$和$k_B$，而这两个密钥都为攻击者所知，然而Alice和Bob都无法察觉到任何攻击的发生。我们将这种攻击的细节留作练习。

实际应用中的Diffie-Hellman密钥交换。基本形式的Diffie-Hellman协议通常在实践中不被使用，因为它对中间人攻击不安全，如前所述。然而，这并不影响它的重要性。Diffie-Hellman协议首次展示了非对称技术（以及数论问题）可以用于解决密钥分配问题。此外，Diffie-Hellman协议是一些标准化的、对中间人攻击具有抵抗力的密钥交换协议的核心，这些协议在当今广泛使用。一个值得注意的例子是TLS；详见Section 13.7。

Diffie-Hellman 算法的实现

椭圆曲线密码学（Elliptic Curve Cryptography，ECC）是一种基于有限域上椭圆曲线的代数结构的公钥密码学方法。与非ECC密码学相比，ECC需要更小的密钥长度来提供相等的安全性（256位ECC安全性相当于3072位RSA密码学的安全性）。

为了更好地理解椭圆曲线密码学，理解椭圆曲线的基础知识非常重要。椭圆曲线是由以下形式的方程定义的平面代数曲线：

$$y^2=x^3+ax+b$$

其中，'a'是x的系数，'b'是方程的常数。该曲线是非奇异的，也就是说，它的图形没有尖点或自交（当系数域的特征等于2或3时）。

通常情况下，椭圆曲线的形状如下所示。当一条直线与曲线相交时，椭圆曲线几乎会与三个点相交。正如我们所见，椭圆曲线关于x轴对称。这个属性在算法中起着关键作用。

在椭圆曲线密码学中，有六个关键元素被广泛使用，分别是P，a，b，G，n和h。下面是对每个元素的解释：

1. P（素数）：P表示椭圆曲线所在的有限域的大小。它是一个素数，决定了椭圆曲线上的点的数量。通常情况下，P的取值越大，椭圆曲线上的点越多，安全性也会增加。

2. a（系数）：a是椭圆曲线方程中的系数，用于确定曲线的形状。对于一条椭圆曲线方程 $y^2=x^3+ax+b$，a决定了曲线在x轴上的弯曲程度。不同的a值会导致不同形状的椭圆曲线。

3. b（常数）：b是椭圆曲线方程中的常数项，也用于确定曲线的形状。对于方程 $y^2=x^3+ax+b$，b决定了曲线的位置和高度。

4. G（生成点）：G是椭圆曲线上的一个基点，也称为生成点。通过对基点G进行重复的点加法运算，可以得到椭圆曲线上的所有点。生成点G是公开的，作为椭圆曲线密码学中的一个重要参数。

5. n（阶）：n是生成点G的阶，表示通过重复加法运算，从G开始，最终回到无穷远点（曲线上的一个特殊点）。n决定了生成点G所能生成的不同点的数量。

6. h（余因子）：h是椭圆曲线的余因子，定义为曲线上的点的总数除以生成点G的阶。h = #E（椭圆曲线上的点） / n。余因子h反映了椭圆曲线上点的分布情况，通常被用于计算椭圆曲线的安全性。

这些元素共同定义了一个特定的椭圆曲线，用于椭圆曲线密码学中的密钥交换、数字签名和加密等操作。

Diffie-Hellman算法：
Diffie-Hellman算法被用于在通过公共网络交换数据时建立一个共享的秘密，该秘密可以用于秘密通信，使用椭圆曲线生成点并使用参数获取秘密密钥。

为了简化和实际实现算法，我们只考虑了4个变量，一个素数P和G（P的原根），以及两个私有值a和b。
P和G都是公开的数字。用户（比如Alice和Bob）选择私有值a和b，并生成一个密钥，并公开交换。对方接收密钥，生成一个秘密密钥，然后他们就有了相同的秘密密钥进行加密。

步骤说明：

1. Alice和Bob都可以获取到公共密钥P和G。这些是公开的数字。

2. Alice选择一个私有密钥a，而Bob选择一个私有密钥b。

3. Alice使用私有密钥a生成一个密钥：

   $$x=G^{a}modP$$

4. Bob使用私有密钥b生成一个密钥：

   $$y=G^{b}modP$$

5. Alice将生成的密钥y公开发送给Bob，而Bob将生成的密钥x公开发送给Alice。

6. Alice接收到Bob发送的密钥y，然后使用自己的私有密钥a生成一个秘密密钥：

   $$k_a=y^{a}modP$$

   Bob接收到Alice发送的密钥x，然后使用自己的私有密钥b生成一个秘密密钥：

   $$k_b=x^{b}modP$$

7. 代数上可以证明：

   $$k_a=k_b$$

8. 现在，Alice和Bob都拥有相同的秘密密钥k，用于加密和解密消息。

Example：

步骤 1：Alice 和 Bob 得到公开数 P = 23，G = 5

步骤 2：Alice 选择私钥 a = 6，
        Bob 选择私钥 b = 15

步骤 3：Alice 和 Bob 计算公开值
        Alice: x =( 5^6 mod 23) = (15625 mod 23) = 8 
        Bob: y = (5^15 mod 23) = (30517578125 mod 23) = 19

步骤 4：Alice 和 Bob 交换公钥 步骤 5：

        Alice 收到公钥 y =19，
        Bob 收到公钥 x = 8

步骤 6：Alice 和 Bob 计算对称密钥
        Alice：ka = y^a mod p = 47045881 mod 23 = 2
        Bob：kb = x^b mod p = 35184372088832 mod 23 = 2

步骤7：9是共同的秘密。

代码实现：

# Diffie-Hellman Code
def prime_checker(p):
    # 检查输入的数字是否为质数
    if p < 2:
        return -1
    elif p == 2:
        return 1
    for i in range(2, int(p ** 0.5) + 1):
        if p % i == 0:
            return -1
    return 1

def primitive_check(g, p, L):
    # 检查输入的数字是否为模p的原根
    for i in range(1, p):
        L.append(pow(g, i) % p)
    for i in range(1, p):
        if L.count(i) > 1:
            L.clear()
            return -1
    return 1

l = []
while True:
    P = int(input("请输入P的值："))
    if prime_checker(P) == -1:
        print("数字不是质数，请重新输入！")
    else:
        break

while True:
    G = int(input(f"请输入{P}的一个原根："))
    if primitive_check(G, P, l) == -1:
        print(f"数字{G}不是{P}的原根，请重新输入！")
    else:
        break

# 私钥
x1, x2 = int(input("请输入用户Alice的私钥：")), int(input("请输入用户Bob的私钥："))
while True:
    if x1 >= P or x2 >= P:
        print(f"用户的私钥应小于{P}！")
        x1, x2 = int(input("请输入用户Alice的私钥：")), int(input("请输入用户Bob的私钥："))
    else:
        break

# 计算公钥
y1, y2 = pow(G, x1) % P, pow(G, x2) % P

# 生成秘密密钥
k1, k2 = pow(y2, x1) % P, pow(y1, x2) % P

print(f"\n用户Alice的秘密密钥为{k1}\n用户Bob的秘密密钥为{k2}\n")

if k1 == k2:
    print("密钥交换成功。")
else:
    print("密钥交换未成功。")

输出：

请输入P的值：23
请输入23的一个原根：5
请输入用户Alice的私钥：6
请输入用户Bob的私钥：15

用户Alice的秘密密钥为2
用户Bob的秘密密钥为2

密钥交换成功。

11.4 公钥密码学的革命

除了密钥交换，Diffie和Hellman在他们的开创性工作中还引入了公钥（或非对称）密码学的概念。在公钥设置中（与我们之前研究的私钥设置相对应），希望进行安全通信的一方会生成一对密钥：一个公钥广泛传播，一个私钥保密。（有两个不同的密钥是使方案不对称的原因。）生成这些密钥后，一方可以使用它们来确保使用公钥加密方案接收的消息的机密性，或者使用数字签名方案发送的消息的完整性。（见图11.3）我们在这里简要介绍这些原语，并在第12和13章中对它们进行详细讨论。

在公钥加密方案中，某一方生成的公钥用作加密密钥；任何知道该公钥的人都可以使用它来加密消息并生成相应的密文。私钥用作解密密钥，并由知道该私钥的一方用于从使用匹配的公钥生成的任何密文中恢复原始消息。此外——这个类似于存在这样的东西简直让人惊讶！——加密消息的保密性即使对于知道公钥（但不知道私钥）的攻击者也是保持的。换句话说，（公共的）加密密钥对于试图解密使用该密钥加密的密文的攻击者是无用的。因此，为了进行机密通信，接收者可以简单地将她的公钥发送给潜在的发送者（无需担心窃听者观察到它），或者在她的网页或某个中央数据库中公开她的公钥。因此，公钥加密方案实现了在密钥分发方面不依赖私有信道的私密通信。

数字签名方案是消息认证码（MAC）的公钥对应物。在这里，私钥充当“认证密钥”（称为签名密钥），使知道该密钥的一方能够为其发送的消息生成“认证标签”（也称为签名）。公钥充当验证密钥，允许任何知道该公钥的人验证发送者签发的签名。与MAC类似，数字签名方案可以用于防止消息的未检测篡改；然而，在这里，安全性甚至对于知道公钥的攻击者也成立。验证是公开的（即可以由知道发送者的公钥的任何人进行），这具有深远的影响，因为这使得可以将由Alice签名的文件提交给第三方（比如法官）进行验证。这种属性称为不可否认性，并且在电子商务中有广泛的应用（例如用于签署法律文件）。数字签名还用于作为公钥基础设施的一部分安全地分发公钥，更多细节请参见第13.6节。

在他们的论文中，Diffie和Hellman提出了公钥密码学的概念，但没有给出任何候选构造。一年后，Ron Rivest，Adi Shamir和Len Adleman提出了RSA问题，并基于该问题的难度提出了第一个公钥加密和数字签名方案。他们方案的变种现在是当今最广泛使用的加密系统之一。1985年，Taher El Gamal提出了一种加密方案，它基本上是对Diffie-Hellman密钥交换协议的轻微改变，该方案的变种现在也被广泛使用。因此，尽管Diffie和Hellman没有成功构造出（非交互式的）公钥加密方案，但他们已经非常接近了。

我们总结一下公钥密码学是如何解决前文11.1节中提到的私钥密码学的限制性问题的：

1. 公钥密码学允许密钥分发通过公开（但经过认证的）渠道进行。这简化了共享的秘密密钥的分发和更新过程。

2. 公钥密码学减少了用户需要存储大量秘密密钥的需求。考虑一个大型公司的情况，在这种情况下，每对员工都需要能够进行安全通信。使用公钥密码学，每个员工只需要存储一个私钥（自己的私钥）和所有其他员工的公钥。重要的是，后者的公钥不需要保密；它们甚至可以存储在某个中央（公共）存储库中。

3. 最后，公钥密码学更适用于开放环境，其中从未相互交互的各方希望能够进行安全通信。一个常见的例子是，一家公司可以在线发布其公钥；用户在进行购买时，可以在需要时获得该公司的公钥，以便将信用卡信息加密并发送给该公司。

公钥加密的发明是密码学的一次革命。直到20世纪70年代末和80年代初，加密和密码学一般仅限于情报和军事组织领域，只有公钥技术的出现使得密码学的使用变得普遍。

为什么要研究私钥密码学？很明显，公钥密码严格比私钥密码更强；特别是，任何公钥加密方案都可以用作私钥加密方案。(进行通信的用户可以简单地同时共享公钥和私钥。如果即使窃听者知道公钥，加密信息仍然保密，那么当公钥保密时，它就明显有效！)那么，我们为什么要费心去研究私钥密码学呢？答案很简单：私钥密码比公钥密码要有效得多，并且应该在适当的设置中使用。也就是说，在通信各方有可能共享密钥的情况下，应该使用私钥加密。这包括小规模、封闭的用户系统以及磁盘加密等应用程序。因此，正如我们将在第12.3节和第13.7节中看到的那样，在公钥设置中使用了私钥加密，以获得更好的效率。