Java教程

一文读懂DH密钥交换算法

本文主要是介绍一文读懂DH密钥交换算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

DH 算法是 Diffie和Hellman于1976年提出了一种的密钥交换协议。这种加密算法主要用于密钥的交换,可以在非安全信道下为双方创建通信密钥,通讯双方可以使用这个密钥进行消息的加密、解密,并且能够保证通讯的安全。

换而言之,算法希望实现这样的一个效果:

通信方A和B首先各自生成密钥 D a D_a Da​和 D b D_b Db​,然后通过某种计算获得各自的公钥 P a P_a Pa​和 P b P_b Pb​,接下来,A和B互相交换公钥 P a P_a Pa​和 P b P_b Pb​。现在,A持有自己的密钥 D a D_a Da​和B的公钥 P b P_b Pb​,B持有自己的密钥 D b D_b Db​和A的公钥 P a P_a Pa​, D a D_a Da​与 P b P_b Pb​、 D b D_b Db​与 P a P_a Pa​经过某种数学运算,都能生成一个相同的加密密钥S用于通信。正在监听通信的第三方由于只得到了 P a P_a Pa​和 P b P_b Pb​,是无法计算得出密钥S的。

具体的过程如下图所示:

在这里插入图片描述

公钥 P a P_a Pa​和 P b P_b Pb​由函数 f 1 f_1 f1​计算得出,共享密钥由 f 2 f_2 f2​计算得出。这两个函数的破解难度直接影响到整个密钥交换算法的强度。

不妨选择函数为 f 2 ( a , b ) = a b f_2(a,b)=ab f2​(a,b)=ab,也就是说我们需要让等式 D a P b = D b P a D_aP_b=D_bP_a Da​Pb​=Db​Pa​成立(否则无法生成相同的密钥)。现在我们随便选择一个常量因子F,令函数 f 1 ( x ) = F ⋅ x f_1(x)=F·x f1​(x)=F⋅x,则有 D a F D b = D b F D a D_aFD_b=D_bFD_a Da​FDb​=Db​FDa​,等式 D a P b = D b P a D_aP_b=D_bP_a Da​Pb​=Db​Pa​成立了。

现在我们得出了一个简单的密钥交换策略:双方都先约定好一个常数F,假设为100好了,然后A和B各自随机生成一个密钥,假设 D a = 3 D_a=3 Da​=3, D b = 4 D_b=4 Db​=4,按照函数 f 1 f1 f1生成公钥 P a = 300 P_a=300 Pa​=300, P b = 400 P_b=400 Pb​=400,然后互相交换。现在A知道 D a D_a Da​和 P b P_b Pb​,一乘起来就是1200,B那边也是, D b ⋅ P a = 1200 D_b·P_a=1200 Db​⋅Pa​=1200,这个1200就是他们的共享密钥S。

如果只得知双方交换的公钥,是无法得出密钥S的,但是F被第三方得知的话,通信加密就会立刻被破坏。首先,这个常数F不能固定写在程序内,因为程序一旦发布,这个固定的常数就有暴露的风险,更糟糕的是,F暴露之后所有使用这个常数的会话都变得不安全了。而每次会话随机选择一个常数F,面临的问题则是双方如何在不安全信道交换F。

上述简单策略不能实现密钥交换的原因是算法过于简单并且可逆。若是只是简单的使用加减乘除进行多项式计算,基本都是可逆且能够快速计算出来的。因此,如何防止别人利用从公钥 P a P_a Pa​、 P b P_b Pb​根据函数 f 1 f_1 f1​进行逆向分解得出A或B的密钥,即不可逆,同时又可以让A和B根据公钥生成公共的密钥成了关键。(就算函数 f 1 f_1 f1​不出现在网络中,但在最坏的情况下函数 f 1 f_1 f1​会暴露)。

生成公钥的 f 1 f_1 f1​有两种实现方式:基于离散对数难题的最早版本的DH算法,和结合了椭圆曲线问题的加强版算法ECDH。

基于离散对数难题的DH算法

要实现不可逆的目标,其实也就是令函数 f 1 f_1 f1​没有反函数,例如 f ( x ) = x 2 f(x)=x^2 f(x)=x2在定义域 R R R上没有反函数。当然,只是没有反函数的话强度是不够的, y = x 2 y=x^2 y=x2中的y只有两种可能的x取值,稍微用密文试试手就知道x和-x谁才是密钥了。一个y最好对应无穷个x的值,例如 y = x m o d    p y=x\mod p y=xmodp,但是这样还不够,仍存在被暴力破解的风险。

f 1 f_1 f1​实现如下,它利用了离散对数问题的难解性:

选择一个二元组 ( g , p ) (g,p) (g,p),定义函数 f 1 ( x ) = g x m o d    p f_1(x)=g^x \mod p f1​(x)=gxmodp,其中 x ∈ ( 1 , p ) x \in (1,p) x∈(1,p)且为整数,作为公钥生成的函数。

这其中g和p都是一个常数。假设窃听者得知了公钥 P a P_a Pa​,想要计算 D a D_a Da​的话,不妨设 n ∈ N n \in N n∈N,然后有:
g D a = n ⋅ p + P a → D a = log ⁡ g ( n ⋅ p + P a ) g^{D_a}=n·p+P_a \rightarrow D_a=\log_{g}(n·p+P_a) gDa​=n⋅p+Pa​→Da​=logg​(n⋅p+Pa​)
想要解答上述算式存在时间上的问题,对于精心挑选的的g和p而言,没有多项式时间的经典算法可用于破解它们。

如何选择二元组(g,p)

如果并不关心算法参数的具体实现,这一节内容可以跳过。

二元组需要满足什么条件,才不会被轻易破解呢?

假设我们选择了一个二元组(2,7),不妨使用函数 f 1 f_1 f1​计算一下:
2 1 m o d    7 = 2 2 2 m o d    7 = 4 2 3 m o d    7 = 1 2 4 m o d    7 = 2 2^1\mod 7=2 \\ 2^2\mod 7=4 \\ 2^3\mod 7=1 \\ 2^4\mod 7=2 21mod7=222mod7=423mod7=124mod7=2
2 x m o d    7 2^x \mod 7 2xmod7的值存在一个循环,这可不是什么好消息,攻击者无需遍历1~p就有可能猜出密钥!

上面的循环,我们专门用阶来定义这种概念。

阶的定义:m为正整数,若 ( a , m ) = 1 (a,m)=1 (a,m)=1,使得 a d m o d    m = 1 a^d \mod m=1 admodm=1成立的最小正整数d,被称为a对模m的阶,记作 o r d m ( a ) ord_m(a) ordm​(a)。 ( a , m ) (a,m) (a,m)的含义为a与m互质。

我们可以证明, a , a 2 , ⋯ a o r d m ( a ) a,a^2,\cdots a^{ord_m(a)} a,a2,⋯aordm​(a)mod m m m的值两两不相等(或者说它们互不同余)。那么要想加强算法的强度,阶d最好应当等于m-1,这样意味着 a d m o d    m a^d \mod m admodm的取值范围为 [ 1 , m − 1 ] [1,m-1] [1,m−1],达到了最大化。

想要达到这个目的,我们还得回答一个问题: a d m o d    m a^d \mod m admodm中,对于任意一个m而言,a存在某个值,使得其阶d等于m-1吗?

要回答这个问题,需要引入欧拉函数的概念:

对于正整数n,欧拉函数 φ ( x ) \varphi(x) φ(x)是小于n的正整数中与n互质的数的数目。

例如 φ ( 10 ) = 4 \varphi(10)=4 φ(10)=4,与它互质的数分别为1、3、7、9。而 φ ( 7 ) = 6 \varphi(7)=6 φ(7)=6,对于质因数x而言, φ ( x ) = x − 1 \varphi(x)=x-1 φ(x)=x−1。

下面的欧拉定理能部分回答我们的问题:
若 a , m 均 为 正 整 数 , ( a , m ) = 1 , 则 a φ ( m ) m o d    m = 1 若a,m均为正整数,(a,m)=1,则a^{\varphi(m)}\mod m=1 若a,m均为正整数,(a,m)=1,则aφ(m)modm=1

上面的定理实际上告诉了我们a对模m的阶的最大值至多为 φ ( m ) \varphi(m) φ(m)。例如对于模15来说,不管如何选择底数a,它的阶最大也只可能是 φ ( 15 ) = 8 \varphi(15)=8 φ(15)=8,而不可能是我们期望的最好的值14。要想达到最好的效果,模m就必须选择一个奇质数(2是质数但它太小了),这样 φ ( m ) = m − 1 \varphi(m)=m-1 φ(m)=m−1,才有希望取到最大的阶。

不过问题还没回答完,对于某个确定的模m(比如说7),真的存在一个数a,它的阶是 φ ( m ) \varphi(m) φ(m)吗?请不要把这个问题和上面的欧拉定理混淆,虽然 a φ ( m ) m o d    m = 1 a^{\varphi(m)}\mod m=1 aφ(m)modm=1(欧拉定理)必定成立,但是不代表值 φ ( m ) \varphi(m) φ(m)是a的阶啊!

举一个很明显的例子,假设a=2,p=7,我们很容易得知 φ ( 7 ) = 6 \varphi(7)=6 φ(7)=6,而 2 6 m o d    7 = 1 2^6\mod 7=1 26mod7=1,欧拉定理确实是成立的,但重新再看看上面举的例子,我们发现 2 3 m o d    7 = 1 2^3\mod 7=1 23mod7=1,也就是说2对7的阶为3,并不是6!

让我们计算一下3对7的阶:
3 1 m o d    7 = 3 3 2 m o d    7 = 2 3 3 m o d    7 = 6 3 4 m o d    7 = 4 3 5 m o d    7 = 5 3 6 m o d    7 = 1 3^1\mod 7=3 \\ 3^2\mod 7=2 \\ 3^3\mod 7=6 \\ 3^4\mod 7=4 \\ 3^5\mod 7=5 \\ 3^6\mod 7=1 \\ 31mod7=332mod7=233mod7=634mod7=435mod7=536mod7=1
3的阶是6,也就是说对于7而言,存在一个数3的阶为 φ ( 7 ) \varphi(7) φ(7)。那么如何称呼满足这种性质的数a呢?我们再给出一个原根的定义:
若 a , m 均 为 正 整 数 , ( a , m ) = 1 , 令 a d m o d    m = 1 成 立 的 最 小 正 整 数 d , 其 满 足 d = φ ( m ) 的 话 , 则 称 a 是 模 m 的 原 根 若a,m均为正整数,(a,m)=1,令a^d\mod m=1成立的最小正整数d,其满足d=\varphi(m)的话,则称a是模m的原根 若a,m均为正整数,(a,m)=1,令admodm=1成立的最小正整数d,其满足d=φ(m)的话,则称a是模m的原根
可以证明,若p是奇质数,则模p的原根存在,而合数就不一定了,例如15就没有原根。

根据上面的推导,选择二元组的要求呼之欲出:在 ( g , p ) (g,p) (g,p)中,p应当是一个大质数,g应当为p的一个原根,这样一来想要计算出密钥 D a D_a Da​是一件相当困难的事情。

生成共同密钥

生成共同密钥的函数 f 2 f_2 f2​应当保证两边生成的密钥都是一样的,具体实现为:
对 于 A : S = f 2 ( D a , P b ) = P b D a m o d    p 对 于 B : S = f 2 ( D b , P a ) = P a D b m o d    p 对于A:S=f_2(D_a,P_b)=P_b^{D_a}\mod p\\ 对于B:S=f_2(D_b,P_a)=P_a^{D_b}\mod p 对于A:S=f2​(Da​,Pb​)=PbDa​​modp对于B:S=f2​(Db​,Pa​)=PaDb​​modp
其中p就是函数 f 1 f_1 f1​中的二元组中的p。其实我们把函数 f 1 f_1 f1​的参数扩展为两位: f ( D , g ) = g D m o d    p f(D, g)=g^D\mod p f(D,g)=gDmodp,函数 f 1 f_1 f1​和 f 2 f_2 f2​的形式是完全一致的。 我们需要证明 f ( D b , f ( D a , g ) ) = f ( D a , f ( D b , g ) ) f(D_b,f(D_a,g))=f(D_a,f(D_b,g)) f(Db​,f(Da​,g))=f(Da​,f(Db​,g))成立。以下是证明:

令 t = f ( D , g ) = g D m o d    p t=f(D, g)=g^D\mod p t=f(D,g)=gDmodp,则有 g D = k p + t g^D=kp+t gD=kp+t,反过来, t = g D − k p t=g^D-kp t=gD−kp,其中k是整数。既然 t = f ( D , g ) = g D − k p t=f(D, g)=g^D-kp t=f(D,g)=gD−kp,那么有 f ( D a , f ( D b , g ) ) = ( t ) D a m o d    p = ( g D b − k p ) D a m o d    p f(D_a,f(D_b,g))=(t)^{D_a}\mod p=(g^{D_b}-kp)^{D_a}\mod p f(Da​,f(Db​,g))=(t)Da​modp=(gDb​−kp)Da​modp

根据二项式法则展开 ( g D b − k p ) D a (g^{D_b}-kp)^{D_a} (gDb​−kp)Da​,不带有 k p kp kp的项只有一个 g D b D a g^{D_bD_a} gDb​Da​,其他带有 k p kp kp的项计算 m o d    p \mod p modp的结果都为0,因此 ( g D b − k p ) D a m o d    p = g D b D a m o d    p (g^{D_b}-kp)^{D_a}\mod p=g^{D_bD_a}\mod p (gDb​−kp)Da​modp=gDb​Da​modp基于对称性的思想,可以立刻列出 f ( D b , f ( D a , g ) ) = ( g D a − k p ) D b m o d    p = g D a D b m o d    p f(D_b,f(D_a,g))=(g^{D_a}-kp)^{D_b}\mod p=g^{D_aD_b}\mod p f(Db​,f(Da​,g))=(gDa​−kp)Db​modp=gDa​Db​modp所以, f ( D b , f ( D a , g ) ) = f ( D a , f ( D b , g ) ) f(D_b,f(D_a,g))=f(D_a,f(D_b,g)) f(Db​,f(Da​,g))=f(Da​,f(Db​,g))成立。

这篇关于一文读懂DH密钥交换算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!