失眠网,内容丰富有趣,生活中的好帮手!
失眠网 > 算法:DH算法原理

算法:DH算法原理

时间:2020-03-04 21:15:23

相关推荐

算法:DH算法原理

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} &amp;= (a ^ {X_B} \pmod{p}) ^ {X_A} \pmod{p} \\ &amp;= (a ^ {X_B}) ^ {X_A} \pmod{p} \\ &amp;= (a ^ {X_A}) ^ {X_B} \pmod{p} \\ &amp;= (a ^ {X_A} \pmod{p}) ^ {X_B} \pmod{p} \\ &amp;= {Y_A} ^ {X_B} \pmod{p} \end{aligned} YB​XA​(modp)​=(aXB​(modp))XA​(modp)=(aXB​)XA​(modp)=(aXA​)XB​(modp)=(aXA​(modp))XB​(modp)=YA​XB​(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 &amp;= a ^ {X_A} \pmod{p} \\ &amp;= 5 ^ 2 \pmod{97} \\ &amp;= 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 &amp;= a ^ {X_B} \pmod{p} \\ &amp;= 5 ^ {95} \pmod{97} \\ &amp;= 39 \end{aligned} YB​​=aXB​(modp)=595(mod97)=39​

A和B交换了公开密钥之后,计算共享密钥如下:

A计算共享密钥得

K=YBXA(modp)=392(mod97)=66\begin{aligned} K &amp;= {Y_B} ^ {X_A} \pmod{p} \\ &amp;= {39} ^ 2 \pmod{97} \\ &amp;= 66 \end{aligned} K​=YB​XA​(modp)=392(mod97)=66​

A计算共享密钥得

K=YAXB(modp)=2595(mod97)=66\begin{aligned} K &amp;= {Y_A} ^ {X_B} \pmod{p} \\ &amp;= {25} ^ {95} \pmod{97} \\ &amp;= 66 \end{aligned} K​=YA​XB​(modp)=2595(mod97)=66​

如果觉得《算法:DH算法原理》对你有帮助,请点赞、收藏,并留下你的观点哦!

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。