Title: 算法:DH算法原理Author: "Peng Li"<aqnote@>Date: .12.11Keywords: Math, DHCopyright:
算法:DH算法原理
离散对数的概念
原根:
如果a是素数p的一个原根,那么数值:
a(modp),a2(modp),…,a(p−1)(modp)a \pmod{p},\quad a^2 \pmod{p},\quad …,\quad a^{(p-1)} \pmod{p} a(modp),a2(modp),…,a(p−1)(modp)
是各不相同的整数,且以某种排列方式组成了从1到p-1的所有整数。
离散对数:
如果对于一个整数Y,素数p的一个原根a,可以找到一个唯一的指数Y,使得:
Y=aX(modp)(0≤X≤p−1)Y = a^X \pmod{p} (0 \leq X \leq p-1) Y=aX(modp)(0≤X≤p−1)
那么指数i称为b的以a为基数的模p的离散对数。
算法描述
Diffie-Hellman算法的有效性依赖于计算离散对数的难度,
其含义是:
当已知大素数p和它的一个原根a后,对给定的b,要计算i,被认为是很困难的;
而给定i,计算b 却相对容易。
Diffie-Hellman算法:
假如用户A和用户B希望交换一个密钥
取素数p和整数a,a是p的一个原根,公开a和p
A选择随机数 XA≤pX_A \le pXA≤p,并计算 YA=aXA(modp)Y_A = a ^ {X_A} \pmod{p}YA=aXA(modp)B选择随机数 XB≤pX_B \le pXB≤p,并计算 YB=aXB(modp)Y_B = a ^ {X_B} \pmod{p}YB=aXB(modp)
每一方都将X保密而将Y公开让另一方得到
A计算密钥的方式是:K=YBXA(modp)K = Y_B ^ {X_A} \pmod{p}K=YBXA(modp)B计算密钥的方式是:K=YAXB(modp)K = Y_A ^ {X_B} \pmod{p}K=YAXB(modp)
如果知道两个密钥: K=a(XA∗XB)(modp)K = a ^ {( X_A * X_B )} \pmod{p}K=a(XA∗XB)(modp)
证明:
YBXA(modp)=(aXB(modp))XA(modp)=(aXB)XA(modp)=(aXA)XB(modp)=(aXA(modp))XB(modp)=YAXB(modp)\begin{aligned} {Y_B} ^ {X_A} \pmod{p} &= (a ^ {X_B} \pmod{p}) ^ {X_A} \pmod{p} \\ &= (a ^ {X_B}) ^ {X_A} \pmod{p} \\ &= (a ^ {X_A}) ^ {X_B} \pmod{p} \\ &= (a ^ {X_A} \pmod{p}) ^ {X_B} \pmod{p} \\ &= {Y_A} ^ {X_B} \pmod{p} \end{aligned} YBXA(modp)=(aXB(modp))XA(modp)=(aXB)XA(modp)=(aXA)XB(modp)=(aXA(modp))XB(modp)=YAXB(modp)
由于 XAX_AXA 和 XBX_BXB 是保密的,而第三方只有a、p、YAY_AYA、YBY_BYB可以利用,只有通过取离散对数来确定密钥,但对于大的素数p,计算离散对数是十分困难的。
举例
假如用户A和用户B希望交换一个密钥。
设置p=97根源数据如下(该值是计算出来):
a=5p=97a = 5 \\ p = 97 a=5p=97
A的密钥设置为 XA=2X_A = 2XA=2
计算A公钥为
YA=aXA(modp)=52(mod97)=25\begin{aligned} Y_A &= a ^ {X_A} \pmod{p} \\ &= 5 ^ 2 \pmod{97} \\ &= 25 \end{aligned} YA=aXA(modp)=52(mod97)=25
B的密钥设置为 XB=95X_B = 95XB=95
计算B公钥为
YB=aXB(modp)=595(mod97)=39\begin{aligned} Y_B &= a ^ {X_B} \pmod{p} \\ &= 5 ^ {95} \pmod{97} \\ &= 39 \end{aligned} YB=aXB(modp)=595(mod97)=39
A和B交换了公开密钥之后,计算共享密钥如下:
A计算共享密钥得
K=YBXA(modp)=392(mod97)=66\begin{aligned} K &= {Y_B} ^ {X_A} \pmod{p} \\ &= {39} ^ 2 \pmod{97} \\ &= 66 \end{aligned} K=YBXA(modp)=392(mod97)=66
A计算共享密钥得
K=YAXB(modp)=2595(mod97)=66\begin{aligned} K &= {Y_A} ^ {X_B} \pmod{p} \\ &= {25} ^ {95} \pmod{97} \\ &= 66 \end{aligned} K=YAXB(modp)=2595(mod97)=66
如果觉得《算法:DH算法原理》对你有帮助,请点赞、收藏,并留下你的观点哦!