简介
Diffie和Hellman在1976年发表的论文中提出了公钥密码思想,但没有给出具体的方案,原因在于没有找到单向函数,但在该文中给出了通信双方通过信息交换协商密钥的算法,即Diffie-Hellman密钥交换算法,这是第一个密钥协商算法,用于密钥分配,不能用于加密或解密信息。
算法描述
算法描述:Diffie-Hellman算法的安全性基于离散对数问题,设p是一个满足要求的大素数,并且g(0< g < p)是循环群Zp的生成元,g和p公开。
- 用户A选取一个大的随机数 α(2≤α≤p−2),
计算SA=gαmod p), 并且把SA发送给用户B
- 用户B选取一个大随机数β(2≤β≤p−2),计算SB=gβmod p),并且把S_B$发送给用户A
- 用户A收到SB后,计算K=SBαmod p,用户B收到SA后,计算K=SAβmod p
可以证明K是相同的。
K=SBαmod p=(gβ)αmod p=gαβmod p=(gα)βmod p=SAβmod p=K
例题
例题1
已知p=23,g=5
用户A选择私钥α=6,计算出SA=gα mod p=56 mod 23=8,发送到用户B。
用户B选择私钥β=15,计算出SB=gβ mod p=515 mod 23=19,发送到用户A。
用户A收到SB,计算KAB=SBα mod p=196 mod 23=2
用户B收到SA,计算KAB=SAβ mod p=815 mod 23=2
这样实现了同一个密钥的分配交换。
例题2
设Diffie-Hellman方法中,公用素数p=11,生成元等于2。若用户A的公钥SA=9,则A的私钥α为多少?如果用户B的公钥SB=3,则共享的密钥K为多少?
p=11,g=2SA=2αmod 11=9Kab=9βmod 11SB=2βmod 11=3Kab=3αmod 1111t1+9=2α,(2≤α≤9)11t2+3=2β,(2≤β≤9)t1=5,t2=8,α=6,β=8Kab=98mod 11=3Kab=36mod 11=3
例题3
设Diffie-Hellman算法中,公用素数p=23,生成元等于5。若用户Alice选取了私钥a=6,那么她发送给Bob的公钥SA是多少?如果用户B的私钥b=15,则共享的密钥K为多少?请求出Bob发送给Alice的公钥,并代替Alice验证共享密钥K是否一致。
p=23,g=5,a=6SA=gamod p=56mod 23=8K=SAbmod p=815mod 23=2SB=gbmod p=515mod 23=19K=SBamod p=196mod 23=2
K一致