简介

Diffie和Hellman在1976年发表的论文中提出了公钥密码思想,但没有给出具体的方案,原因在于没有找到单向函数,但在该文中给出了通信双方通过信息交换协商密钥的算法,即Diffie-Hellman密钥交换算法,这是第一个密钥协商算法,用于密钥分配,不能用于加密或解密信息。

算法描述


算法描述:Diffie-Hellman算法的安全性基于离散对数问题,设p是一个满足要求的大素数,并且g(0< g < p)是循环群Zp的生成元,g和p公开。

  1. 用户A选取一个大的随机数 α(2αp2)α(2≤α≤p-2),
    计算SA=gαmod p)S_A=g^α mod \space p), 并且把SAS_A发送给用户B
  2. 用户B选取一个大随机数β(2βp2)β(2≤β ≤p-2),计算SB=gβmod p),S_B=g^β mod \space p),并且把S_B$发送给用户A
  3. 用户A收到SBS_B后,计算K=SBαmod pK={S_B}^α mod \space p,用户B收到SAS_A后,计算K=SAβmod pK={S_A}^β mod \space p
    可以证明K是相同的。

K=SBαmod p=(gβ)αmod p=gαβmod p=(gα)βmod p=SAβmod p=KK={S_B}^α mod \space p = {(g^β)}^α mod \space p=g^{αβ} mod \space p={(g^α)}^β mod \space p ={S_A}^β mod \space p=K

例题

例题1

已知p=23,g=5p=23, g=5

用户A选择私钥α=6\alpha = 6,计算出SA=gα mod p=56 mod 23=8S_A=g^{\alpha} \space mod \space p=5^6 \space mod \space 23=8,发送到用户B。

用户B选择私钥β=15\beta = 15,计算出SB=gβ mod p=515 mod 23=19S_B=g^{\beta} \space mod \space p=5^{15} \space mod \space 23=19,发送到用户A。

用户A收到SBS_B,计算KAB=SBα mod p=196 mod 23=2K_{AB}={S_B}^{\alpha} \space mod \space p=19^6 \space mod \space 23=2

用户B收到SAS_A,计算KAB=SAβ mod p=815 mod 23=2K_{AB}={S_A}^{\beta} \space mod \space p=8^{15} \space mod \space 23=2

这样实现了同一个密钥的分配交换。

例题2

设Diffie-Hellman方法中,公用素数p=11,生成元等于2。若用户A的公钥SA=9S_A=9,则A的私钥α\alpha为多少?如果用户B的公钥SB=3S_B=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\begin{aligned} & p=11, g=2 \\ & S_A=2^{\alpha} mod \space 11=9 \\ & Kab=9^{\beta} mod \space 11\\ & S_B=2^{\beta} mod \space 11=3 \\ & Kab=3^{\alpha} mod \space 11 \\ & 11 t_1+9=2^{\alpha},(2 \leq \alpha \leq 9)\\ & 11 t_2+3=2^{\beta},(2 \leq \beta \leq 9)\\ & t_1=5,t_2=8,\alpha=6,\beta=8 \\ & Kab=9^8 mod \space 11 =3\\ & Kab=3^6 mod \space 11 =3\\ \end{aligned}

例题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\begin{aligned} &p=23,g=5,a=6 \\ &S_A=g^a mod \space p=5^6 mod \space 23=8\\ &K={S_A}^b mod \space p=8^{15} mod \space 23=2\\ &S_B=g^b mod \space p=5^{15} mod \space 23=19\\ &K={S_B}^a mod \space p=19^6 mod \space 23=2\\ \end{aligned}

K一致