从公开幂次达成协商
公钥加密与密钥协商解决相关但不同的问题:此处两名参与者利用公开消息计算共同值,而非直接加密消息。我们先证明两人的计算结果相同,再问这项计算能和不能证明什么。
定义 10.1.1
(剩余类的阶与交换过程)
令 为素数, 为模 的非零剩余类。其阶 是满足 的最小正整数。由于非零剩余类构成有限乘法群, 存在。公开参数为 。Alice 选私有指数 ,Bob 在同一集合中选 ;两人分别公开
Alice 计算 ,Bob 计算 。此指数范围只定义数学实验,并非安全密钥生成的完整规范。
定理 10.1.2
(协商一致)
若双方收到对方未经修改的公开值,其计算结果相同:
证明
(诚实交付下的指数法则)
模幂的恒等式来自乘法结合律和 。指数模 化简不改变 的幂,因为在域中 。此等式证明诚实交付时的正确性,并未证明观察者不能计算结果。
例题 10.1.3
(模 23 的小型计算)
取 、、、。 的阶为 :费马(Fermat)定理给出 ,而 、;因此阶不能是 的任何真因数。公开值为 和 。双方均算得
这些极小参数只用来展示运算,并不安全。
观察者看到什么
观察者看到 。离散对数问题要求:给定 及其生成子群中的 ,找出满足 的指数 。若观察者找到这样的指数,便可计算 。此推论不证明逆命题:计算共同值和找回指数是不同问题。
概念视角结构
同一交换在另一种表示中
映射 是从加法群 到 所生成子群的同构,因此这个交换就是把指数之积 搬到该子群中。在 中以生成元 进行完全相同的交换,公开 和 (模 )。取 得 ;由于 ,观察者算出 。抽象地看两个群相同;如果存在任何困难性,它来自用模 剩余表示这个群的方式。
定理 10.1.4
(找回指数即可得到共同值)
若观察者找到任意整数 使 ,则 。
证明
( 的任何对数都足够)
由于 ,有 。指数 不必等于 : 的任何解都与 模 同余,而 的幂只取决于指数模 的值。
例题 10.1.5
(用幂次表破解小例子中的交换)
在例子中,列出幂次便可发现 ;用 和公开的 就得到共同值 。因此,仅称指数为私有数据并不能推出安全。这个有限玩具群可行地列出完整表格,而计算能力无限的观察者总能穷举有限指数范围。实际安全性是依赖指定群、实现及攻击者假设的计算性主张,不是协商恒等式证明的信息论保密性。
例题 10.1.6
(退化的指数与小的阶)
若 Alice 的指数为 ,则 ,不论 Bob 怎样选择,共同值都是 ;观察者直接由 读出结果。阶很小同样有害。模 时,剩余类 的阶为 ,所以每个公开值和每个共同值都属于 。取 、,双方都公开 ,并算得 。观察者完全知道规则:共同值为 当且仅当 ,即两个指数都是奇数。两种情形下协商仍然一致;改变的是 所生成的群的大小。
常见错误
(正确性不等于保密性)
即使群小得足以让观察者列举所有指数,诚实双方的计算仍然相等。保密主张需要威胁模型及额外假设。
为什么需要认证
反例模式
替换公开值
假设主动攻击者能替换消息,并选取指数 。攻击者把 传给 Alice,代替 Bob 的 ;把 传给 Bob,代替 Alice 的 。Alice 计算 ,攻击者也可由 算出;Bob 计算 ,攻击者也可由 算出。攻击者因此能分别建立两个共同值。双方没有认证正在与谁共享,其值也未必相同。例如在模 的例子中,攻击者取 ,向双方都发送 。Alice 算得 ,Bob 算得 ,而攻击者算得 及 。这并不与协商一致定理矛盾:失效的正是“公开值未被修改”这个假设。
认证必须把交换值与预期参与者和协议上下文绑定。真正的密钥建立协议还要规定安全参数、公开值检查、随机性、密钥导出函数及在需要时的密钥确认。本玩具计算不是协议或实现建议。
习题
快速检查
(在模 23 的例子中,验证 、 和共同值。)
用模 的反复平方。
解答 · 答案
重复平方得到公开值 、; 和 模 都化为 。
快速检查
(若 的阶为 ,为什么指数 与 给出相同公开值?)
利用 。
解答 · 答案
在域中 。
快速检查
(观察者由公开值 得知 ,如何利用 计算共同值?)
应用找回指数的定理。
解答 · 答案
计算公开值 的 次方:。
快速检查
(单靠 能否阻止上述公开值替换?解释。)
检查协商一致定理的假设。
解答 · 答案
不能。等式假设预期的公开值被送达;替换值让攻击者分别与每位参与者共享一个值。
延伸阅读
Diffie 与 Hellman,〈New Directions in Cryptography〉(1976) 提出公钥分发。NIST SP 800-56A Rev. 3 讨论离散对数密钥建立方案,并注明计划更新。