补充 Diffie-Hellman密钥交换.ppt

基础:原根(primitive root)
Euler定理表明,对两个互素的整数a,n,
a(n)  1 mod n
定义:存在最小正整数m(n) (m|(n)),使得
am  1 mod n
若对某个a,m=(n),则称a是n的一个原根
对于素数p,若a是p的一个原根,则:
a,a2, …,ap-1关于p两两不同余,从而构成了p的非0剩余类,即与{1,2,…,(p-1)}关于模p等价.
离散对数
若a是素数p的一个原根,则对任意整数b,b0 mod p,存在唯一的整数i, 1i(p-1),使得: bai mod pi称为b以a为基模p的指数(离散对数),记作inda,p(b).容易知道: inda,p(xy)= [inda,p(x)+inda,p(y)] mod (p) inda,p(xr)= [rinda,p(x)] mod (p)
离散对数的计算: ygx mod p
已知g,x,p,计算y是容易的
已知y,g,p,计算x是困难的
Diffie-Hellman密钥交换
允许两个用户可以安全地交换一个秘密信息,用于后续的通讯过程
算法的安全性依赖于计算离散对数的难度
算法:
双方选择素数q以及q的一个原根r
A选择X<q,计算XA=rXmod p, AB: XA
B选择Y<q,计算YB=rYmod p, BA: YB
A计算: (YB)X(rY)XrXYmod p
B计算: (XA)Y(rX)YrXYmod p
双方获得一个共享密钥(rXYmod p)
素数q以及q的原根r可由一方选择后发给对方
Diffie-Hellman密钥交换的攻击
replay攻击
中间人攻击图示
A
B
K = rxy
E
A
B