Diffie-Hellman密钥交换算法

简介

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

算法描述

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

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

$K={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=5$

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

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

用户A收到$S_B$，计算$K_{AB}={S_B}^{\alpha} \space mod \space p=19^6 \space mod \space 23=2$

用户B收到$S_A$，计算$K_{AB}={S_A}^{\beta} \space mod \space p=8^{15} \space mod \space 23=2$

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

例题2

设Diffie-Hellman方法中，公用素数p=11,生成元等于2。若用户A的公钥$S_A=9$，则A的私钥$\alpha$为多少？如果用户B的公钥$S_B=3$，则共享的密钥K为多少？

$\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是否一致。

$\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一致