为什么需要协商密钥?
对称加密要求双方先拥有共同秘密。若 Alice 和 Bob 从未见面,直接在公开信道上传送秘密就失去了意义。Diffie–Hellman 允许双方只发送公开群元素,随后各自算出同一个群元素;它本身却不能确认对方的身份。
定义 10.2.1
(Diffie–Hellman 交换)
设公开的循环群 的素数阶为 ,以乘法记号表示,指数按模 计算。群、阶和生成元都是公开的;Alice 和 Bob 独立、均匀地从 选择秘密指数 。理想化交换如下:
- Alice 发送 ,Bob 发送 。
- Alice 计算 ,Bob 计算 。
- 由 ,双方均得到 。
这个等式证明的是正确性,不是保密性。窃听者看到 ,必须在不知道指数的情况下计算或区分关于 的信息。实际系统通常将群元素及具有协议含义的通信记录编码交给合适的密钥派生函数,而不是直接把群元素当成任意长度的加密密钥。
例题 10.2.2
(模 23 的交换)
在模 的非零剩余类中, 的阶为 :,而它的阶不是 。取子群 。Alice 选择 ,发送 ;Bob 选择 ,发送 。Alice 算得 ,Bob 算得 ;也可直接算 。这个小群便于手算,却没有实际安全性。
被动安全性究竟说了什么?
定义 10.2.3
(计算与判定 Diffie–Hellman 问题)
计算 Diffie–Hellman 问题(CDH)要求从 计算 ,其中 独立均匀取自 。判定 Diffie–Hellman 假设(DDH)则说,有效的随机算法不能区分以下两个分布:
其中 独立均匀取自 。严格而言,我们讨论随安全参数增长的一族适当群:每个概率多项式时间区分器在两个实验中输出同一指定结果的概率之差都是可忽略的。这不表示两个分布完全相同;计算能力不受限制的观察者可以求出指数并检验关系。
从离散对数到 CDH
离散对数问题要求从 求出 。知道 足以求出共享元素,但诚实协议不需要 Alice 求离散对数,因为她本来就知道自己的指数。被动窃听者则可能尝试从公开值恢复它。
定理 10.2.4
(离散对数求解器给出 CDH 求解器)
假设群运算和求幂均可有效执行。若一个算法对均匀的 以至少 的概率求出离散对数,则可构造一个 CDH 算法,对独立均匀的 至少以概率 成功。
证明
(由对数得到共享元素)
给定 ,对 运行离散对数算法,得到候选值 ,再输出 。只要模 有 ,输出就是 。因此离散对数算法成功时,CDH 算法必然成功;额外工作只需一次求幂。
常见错误
(离散对数困难不能推出 DDH)
这是单向归约:有效的离散对数算法会使 CDH 容易,但我们没有证明每个 CDH 算法都必须恢复指数。特别是,仅凭离散对数困难不能确立 DDH 假设。
例题 10.2.5
(在小群中恢复指数)
窃听者看到模 的 、。依次列出 、、、,便得到 ,进而算出 。这个小群可以穷举;例子展示一种攻击,并不声称穷举在每个群中都是最佳算法。
定理 10.2.6
(DDH 下原始共享元素是伪随机的)
假设所用群族满足 DDH,则在上述理想交换中,有效被动观察者无法以不可忽略的优势区分 和 ,其中 是独立均匀的 元素。
证明
(两个实验的等同)
均匀的 可写为 ,其中 均匀取自 。因此第一个实验恰好给出 DDH 三元组,第二个恰好给出随机三元组。任何区分这两个实验的算法本身就是 DDH 区分器,输出概率之差完全相同。
证明透视
为什么转发归约毫无损失
三个假设各在一处用到。被动性表示观察者只读取 ,从不选择公开值,所以一个 DDH 挑战就包含其全部视图;若敌手以自己的值替换 ,归约就需要一个不知道指数便无法算出的回应。指数必须恰好在 上均匀分布(包括零),因为 DDH 三元组正是以这个分布定义的。关键的一步是: 均匀时 在 中均匀,所以随机实验与随机 DDH 三元组是同一个分布,而不只是接近。
由于两种情形下的视图都完全一致,归约的优势等于观察者的优势,论证以逆否命题收尾:一个优势不可忽略的观察者,就是一个优势相同、运行时间基本相同的 DDH 区分器。若指数改为从非零剩余中抽取,则每个实验中的视图至多相差 ,等式便变成下文推导的 界。
理想选择包含指数零:若 ,则 , 也是公开的。在适当的大阶群族中,这以概率 发生,虽可忽略,但刻意输入单位元很危险。实际实现常拒绝单位元并使用非零秘密指数;将两个指数限制为非零会改变理想实验的分布,对该变体的证明必须计入这个条件化。本节不是生产协议规范。
实验、优势与归约
在被动实验中,双方诚实执行交换:观察者不选择或替换任何公开消息。先独立均匀地选取 。真实实验向观察者提供 ,随机实验则提供 。观察者输出一个比特;输出 1 表示它猜测元组来自真实实验。若两种实验中输出 1 的概率分别为 和 ,这里将区分优势定义为 。有些教材用随机猜测游戏的成功概率定义优势,数值会差一个二分之一的因子,因此需要说明约定。
归约接收 DDH 挑战元组 ,原样将 交给观察者,再原样输出观察者的比特。若挑战是真实元组,观察者看到的恰是真实交换实验;若挑战是随机元组,它看到的恰是随机实验。归约不需要求出离散对数,也没有模拟误差。按照上述约定,归约的优势与观察者的优势完全相同。因此,对于随安全参数增长的群族,若观察者有不可忽略的优势,就与该群族的 DDH 假设矛盾;这里要求观察者和转发归约都是概率多项式时间算法,并在两种实验中获得相同的公开群描述。
实验故意把第三个元素交给观察者:问题是即使同时看到公开交换记录,这个元素是否仍与独立均匀元素难以区分。这不是要求协议公开真实会话密钥。实际加密安全还依赖编码、密钥派生和后续使用方式。计算不可区分并不意味着统计上接近或完全独立。考虑所有 构成的集合:真实三元组必在其中;随机三元组在其中的概率为 ,因为前两项固定后,符合关系的第三项只有一个。因此,即使 DDH 指出有效观察者的优势可忽略,计算能力不受限制的观察者仍能以 的概率差区分。
概念视角代数
藏在指数中的秩问题
把 的指数记成域 上的矩阵:
这个组是 Diffie–Hellman 组,当且仅当该矩阵奇异,即秩为一;均匀的 使它奇异的概率为 ,正是上文所用的计数。DDH 断言:只能在指数中看到各元素的高效观察者,无法分辨秩一与秩二。
例题 10.2.7
(小群中可见的区分差异)
在上述 11 阶群中,令观察者恰在第三个元素为单位元时输出 1。真实实验中, 当且仅当模 11 有 ;其概率为 。随机实验中 的概率为 。因此该观察者的优势为 。这个简单测试已经能区分小群中的两个分布;当相应差距 相对于安全参数可忽略时,它不与渐近 DDH 假设矛盾;例如安全参数为 且 时就是如此。检查第三元素是否等于单位元即可完成这个测试。
若改为从非零剩余类中均匀选取两个指数,它们的联合分布等于原来均匀分布在 且 条件下的分布。被排除事件的概率为 。因此对真实或随机实验,条件化对任何固定观察者事件的概率影响至多 ;由三角不等式,区分优势的变化至多 。这是较宽松但明确的界,不能据此接受对手发送的单位元。
反例模式
群阶不是素数时,共享元素泄露一个比特
断言:DDH 可以在任何循环群中假设,例如模素数 的整个乘法群。模 时,元素 的阶为 。由 Euler 判别法, 当且仅当 是平方元,而 是平方元当且仅当 为偶数。所以 是平方元,当且仅当 或 是平方元。若观察者在第三个元素符合此规则时输出 1,则 、,对每个这样的 优势都是 。例如 给出 、、,三者都不是平方元。修正在于定义中的素数阶:在 阶子群中每个元素都是平方元,这个检验得不到任何信息。
主动攻击者可以替换两个消息
假设 Eve 能截获并替换公开消息。Alice 发出 、Bob 发出 ,但 Eve 选取非零 ,向 Alice 发送 代替 ,向 Bob 发送 代替 。Alice 算出 ;Eve 用截获的 和自己知道的 也能算出它。Bob 算出 ,Eve 同样能算出。Alice 和 Bob 通常得到不同的密钥,各自却都与 Eve 共享。若后续通信没有有效认证,Eve 可以根据所用加密的性质在一侧解密、另一侧重新加密。
反例模式
小群中的替换
沿用模 的例子,Eve 向双方都发送 。Alice 得到 ,Bob 得到 (均模 )。Eve 分别计算 和 。两个替换值都是 的非单位元,因此仅检查子群成员资格不能认证发送者。
要防止替换,需要有身份认证的协议。例如,可验证的签名覆盖带上下文的通信记录,其中包含双方身份和公开值;还需要可信地将验签密钥绑定到预期对方。若验签公钥本身未经认证,签名只是转移了替换问题。完整协议还要规定角色、编码、必要时的密钥确认和失败处理;这里没有证明完整的认证密钥交换方案安全。
群和公开值的检查
在某些使用未检查共享元素的协议中,若输入不在预期子群,响应可能泄露信息。例如在模 的完整乘法群中, 的阶为二。若实现用 中的整数表示 并计算 ,而攻击者能够辨认这个响应,就能获知该整数的奇偶性。模奇数 的剩余类本身没有固有的奇偶性;输入在 之外时,代表元的选择会影响结果。这是小子群攻击的示意,不是对上面被动 DDH 实验的攻击:后者的输入都在 中取样。
在本例的素数阶子群中,剩余类 属于 当且仅当 。实际协议还须规定域元素编码,拒绝格式错误或被禁止的值,并按所用群选择正确参数和检查。这些检查维护群假设,不能证明发送者身份。
手算公开值检查
例题 10.2.8
(合法子群元素与二阶元素)
取 、,接收方检查 。连续平方得到 、、,故 。又 ,所以它通过子群和非单位元检查。但对手也能发送 ;通过检查并不能识别发送者。
再看 。由于 是奇数,,子群检查会拒绝它。若有缺陷的实现仍对它求幂,私有指数代表元 和 分别给出 和 。如果攻击者能从响应或之后的可观察行为区分这两个结果,就能知道该代表元的奇偶性;仅发送 本身并不会自动泄露私有指数。
对模 的非零剩余类,测试 恰好识别这个 11 阶子群:由拉格朗日(Lagrange)定理,子群提供 11 个根;域上非零的 11 次多项式至多有 11 个根。测试包含 ,因此要求非单位元的协议还需要单独检查。不能不核对其他群的表示与协议规则,就照搬这个条件。
练习与解答
快速检查
(在上述子群中,Alice 取 ,Bob 取 。求公开值和共同元素。)
计算 与 模 ,再作一次求幂。
解答 · 答案
,,而 ;也可用 。
快速检查
(如果接收者接受 ,任意秘密指数会得到什么共享元素?这与经过认证的交换有何区别?)
把 取任意次幂。
解答 · 答案
,这是公开值。它不证明发送者身份,而已知的共享元素不能提供秘密密钥。
快速检查
(解释总是正确的 CDH 求解器如何构造 DDH 区分器。若 独立均匀且群阶为 ,计算其区分概率差。)
把第三个分量与求解器的输出比较。
解答
用求解器计算 ,当且仅当第三项等于 时输出“真实”。若求解器总是正确,真实三元组中的输出概率为 ,随机三元组中为 ,差为 。不完美求解器需要另行分析成功概率。
快速检查
(在上述攻击中,Eve 为什么无需知道 就能算出 ?只替换发给 Alice 的消息,是否必然能使 Eve 也得到 Bob 的密钥?)
把 与 都写成 的幂。
解答
对公开的 用已知的 求幂即可:。若只替换发给 Alice 的消息,Bob 仍使用 Alice 原来的 计算 ,Eve 一般不能仅凭这次替换求得 Bob 的密钥。
快速检查
(验证 未通过模 的子群检查,并说明该检查不能证明什么。)
利用 与 的奇偶性。
解答 · 答案
,所以 ,排除其属于 。即使检查通过,元素仍可能来自攻击者,而非预期对方。
快速检查
(在小群中,指数在 上均匀分布时,求真实实验与随机实验中单位元测试的概率。为何答案说明两种实验的分布并非完全相同?)
沿用单位元检验的计算。
解答 · 答案
概率分别为 和 ,相差 ,因此两种分布不相同;计算不可区分是渐近性质,不是相等。
快速检查
(验证 通过子群检查,并解释为什么它仍不能认证对方。)
使用反复平方。
解答 · 答案
如上,,且 。任何人都能发送此合法值,所以成员资格不能证明身份。