指数i称为b的以a为基数的模p的离散对数或者指数。该值被记为inda ,p(b)。
基于此背景知识,可以定义Diffie-Hellman密钥交换算法。该算法描述如下:
1、有两个全局公开的参数,一个素数q和一个整数a,a是q的一个原根。
2、假设用户A和B希望交换一个密钥,用户A选择一个作为私有密钥的随机数XA<q,并计算公开密钥YA=aXA mod q。A对XA的值保密存放而使YA能被B公开获得。类似地,用户B选择一个私有的随机数XB<q,并计算公开密钥YB=aXB mod q。B对XB的值保密存放而使YB能被A公开获得。
3、用户A产生共享秘密密钥的计算方式是K = (YB)XA mod q。同样,用户B产生共享秘密密钥的计算是K = (YA)XB mod q。这两个计算产生相同的结果:
K = (YB)XA mod q
= (aXB mod q)XA mod q
= (aXB)XA mod q (根据取模运算规则得到)
= aXBXA mod q
= (aXA)XB mod q
= (aXA mod q)XB mod q
= (YA)XB mod q
因此相当于双方已经交换了一个相同的秘密密钥。
4、因为XA和XB是保密的,一个敌对方可以利用的参数只有q、a、YA和YB。因而敌对方被迫取离散对数来确定密钥。例如,要获取用户B的秘密密钥,敌对方必须先计算
XB = inda ,q(YB)
然后再使用用户B采用的同样方法计算其秘密密钥K。
Diffie-Hellman密钥交换算法的安全性依赖于这样一个事实:虽然计算以一个素数为模的指数相对容易,但计算离散对数却很困难。对于大的素数,计算出离散对数几乎是不可能的。
下面给出例子。密钥交换基于素数q = 97和97的一个原根a = 5。A和B分别选择私有密钥XA = 36和XB = 58。每人计算其公开密钥
YA = 536 = 50 mod 97
YB = 558 = 44 mod 97
在他们相互获取了公开密钥之后,各自通过计算得到双方共享的秘密密钥如下:
K = (YB)XA mod 97 = 4436 = 75 mod 97
K = (YA)XB mod 97 = 5058 = 75 mod 97
从|50,44|出发,攻击者要计算出75很不容易。