密码学院中文 密码学院中文

【科普小文】Ding式密钥协商

  • 文/密码学院
  • 日期:2022-01-04
  • 20142

1.背景

密钥协商算法主要用于在TLS/SSL等安全协议中协商会话密钥。丁式密钥协商(Ding Key Exchange)是由丁津泰教授在美国辛辛那提大学就职时提出的,该算法是第一个完整的基于错误学习问题(LWE/RLWE)的类Diffie-Hellman协议。

Diffie-Hellman(DH)密钥协商的过程如图1所示,g是公共的因子,红色的Alice和蓝色的Bob分别生成a和b,Alice和Bob如图执行交互,这样可以获得相同的数据,即

 (gb)a=(ga)b

该值即可作为会话密钥。DH密钥协商的安全性可以归约到离散对数困难问题, DH密钥协商的原型易受中间人攻击,因此实际应用中会采用其增强方案,这一点在本文中不再赘述。

图1 Diffie-Hellman密钥协商

2.Ding密钥协商介绍

图2是Ding密钥协商的基本流程,可以看出该协议的宏观过程与DH密钥协商是一致的,因此该协议可以比较容易地置换现在广泛使用的DH密钥协商。

图2 Ding密钥协商交互

与DH密钥协商不同的是,Ding密钥协商的结果kA,kB不是严格相等的,好在a是在Zq中均匀采样的,而e是值很小,因此kA和kB的差异仅在低有效的比特位。因此需要一种协调机制(Reconciliation)使双方规避误差,最终得到相同的会话密钥,这需要用到图2中红色问号部分,这个值需要称为 “信号(Signal)”。

图3 Ding密钥协商具体流程

图3中的Round和Recover函数是用于减少通信开销的一对函数。Sig函数用于生成Signal,Mod2函数用于错误协调。我们观察到,kA(ki)和kB(kj)若没有模约减的情况,则它们的奇偶性是一致的,原因在于加性误差是2的倍数,这也就是说可以用mod2的结果达成1bit的共识。但由于模数往往是奇素数,如果约减次数不同,那么最终kA(ki)和kB(kj)的奇偶性会有差异,因此在Mod2函数中实际需要确保kA(ki)和kB(kj)不能恰好“跨越”一个模数。

图4 Mod2函数中的区域翻转

如图4所示,[-q/2,q/2] 分为两个部分,[-q/4,q/4]为inner region,其他为outer region。

为了避免“跨越”一个模数,Ding的方案是将kA(ki)和kB(kj)都转换到inner region,对kA(ki)来说,如果kB(kj)发来的signal(即wj)是1,那么就执行转换,否则不执行转换。Ding的方案的容错能力是(q/4)-2。

作者:陈朝晖

参考:

[1]Ding, J.: A simple provably secure key exchange scheme based on the learning with errors problem. IACR Cryptology ePrint Archive 2012/688 (2012)

[2]https://csrc.nist.gov/CSRC/media/Presentations/Ding-Key-Exchange/images-media/DING-KEY-EXCHANGE-April2018.pdf