Digd0g's Blog

浅谈Diffie-Hellman

发表于 更新于 分类于 ，
本文字数： 1.8k 阅读时长 ≈ 7 分钟
       
-------------已经到底啦！-------------
 

公共密钥加密，又称非对称加密，是一种密码学算法类型，这种算法需要两个密钥，一个是私人密钥，另一个则是公开密钥。我们将公钥公之于众进行加密，而保存私钥用于解密。这种算法的优点是不需要经过安全渠道传递密钥，简化了密钥管理过程

1976年，Whitfield Diffie 和 Martin Hellman 发表的论文 New directions in cryptography 展示了一种算法，表明非对称加密或是公共密钥加密是可行的；整个学界哗然，划时代的密码体制就此诞生了。现代密码学的溯源其实反反复复也最终还是追随到Diffie and Hellman这两位人身上。可以说，称Diffie-Hellman 密钥交换算法为密码学史上的革命也丝毫不为过。新生的现代密码学，为我们个人通信、商业机密的传送提供了强有力的保障。比如 Https 协议的 TSL(Transport Layer Security)以 DH 算法作为密钥交换算法。

Diffie-Hellman算法原理

手上保存私钥，公开公钥；在离散对数中，由K求出k很难，通过公钥解出私钥几乎是不可行的。也就是说算法的安全性是基于离散对数的复杂度

$$
K=k_b^amodn=(g^bmodn)^amodn=g^{ba}modn=(g^amodn)^bmodn=k_a^bmodn=K
$$

通过下面这张图或许能更直白地理解数学概述的抽象原理：

该算法的唯一目的是为了让用户能够安全交换密钥得到一个共享的会话密钥，算法本身不具备加密解密的功能。

由于DH在传输n，g时并无身份验证，如果攻击者可以在信道的中央窜改两边收发的消息，就可以假扮身份完成两次Diffie-Hellman密钥交换。这样攻击者就可以解密全部的信息。所以在替换双方传输时的数据有机会被实施中间人攻击

应运而生的是Oakley算法——对Diffie-Hellman密钥交换算法的优化，它保留了后者的优点，同时克服了其弱点。

Oakley算法具有五个重要特征：

  1. 它采用称为cookie程序的机制来对抗阻塞攻击。

  2. 它使得双方能够协商一个全局参数集合。

  3. 它使用了现时来保证抵抗重演攻击。

  4. 它能够交换Diffie-Hellman公开密钥。

  5. 它对Diffie-Hellman交换进行鉴别以对抗中间人的攻击。

Oakley可以使用三个不同的鉴别方法：

  1. 数字签名：通过签署一个相互可以获得的散列代码来对交换进行鉴别；每一方都使用自己的私钥对散列代码加密。散列代码是在一些重要参数上生成的，如用户ID和现时。

  2. 公开密钥加密：通过使用发送者的私钥对诸如ID和现时等参数进行加密来鉴别交换。

  3. 对称密钥加密：通过使用某种共享密钥对交换参数进行对称加密，实现交换的鉴别。

与RSA的区别

每次会话时都产生随机的（a,b）值，未来的密钥泄漏并不会破解之前的会话密钥。这也说明了迪菲-赫尔曼密钥交换是支持前向保密的

Elgamal 公钥加密算法

基于迪菲-赫尔曼密钥交换演化出来的 ElGamal 加密算法，可以用来加密/解密消息，但是由于一些历史原因以及 RSA 公钥加密算法的巨大商业成功，ElGamal 加密算法并不流行。
$$
Alice 选取一对 (g,p), a作为【私钥】，然后计算出 A=g^a 作为【公钥】。\
Alice 将 (g,p,A)公布给所有人。\Bob 现在想给 Alice 传送一条信息 m. 于是 Bob 选取一个随机数 k, 计算出c_1=g^k, \quad c_2=mA^k \quad \SEND Alice(c_1,c_2)
$$

Alice’s operation
$$
calculate \quad c_1^{-a}·c_2=g^{-ka}·m·g^{ak}=m
$$
Alice成功获取m

Elgamal 的安全性与 DH 是一致的

产生密钥
$$
首先选择一个素数p和两个小于p的随机数g和x，计算y\equiv g^xmodp.以(y,g,p)作为公钥，x作为私钥
$$
加密明文M
$$
首先选择一个和p-1互素的整数k，计算C_1 \equiv g^kmodp,C_2 \equiv y^kmod p,密文C=(C_1,C_2)
$$

解密
$$
M= \frac{C_2}{C_1^X}modp=\frac{y^kM}{g^{kx}}modp=\frac {y^kM}{y^{k}}modp=Mmodp
$$

基于椭圆曲线的 Diffie-Hellman 密钥交换

$$
首先约定好一个Abel群构成的E_p(a,b),E_p(a,b)的一个生成元G(x_1,y_1)\G的阶要满足素数并且nG=O（n\in最小正整数）E_p(a,b)和G作为公开参数。
$$

$$
令Alice保存n_A,Bob保存n_B\quad P=n_pG产生E_p(a,b)上的一点作为公开钥\计算Alice的K=n_AP_B,Bob的 K=n_BP_A
$$

例如

1
2
3
4
5
6
7
8
9
10
E = EllipticCurve(GF(3851), [324, 1287])
G = E(920, 303)

nA = 1194
PA = nA * G
nB = 1759
PB = nB * G

KA.xy(), KB.xy()
# ((2067, 2178), (3684, 3125))

$$
P_A\neq P_B,\quad but\quad K_A=K_B
$$

1
2
3
4
5
#密钥协商 共享密钥
print((nA * PB).xy())
# (3347, 1242)
print((nB * PA).xy())
# (3347, 1242)

椭圆曲线 上的Elgamal 公钥密码体制

$$
首先约定好一个E_p(a,b),将明文m嵌入曲线点p_m,做加密变换；\取E_p(a,b)的一个生成元G(x_1,y_1),E_p(a,b)和G作为公开参数。
$$

$$
Alice选取n_A,P=n_AG为公开钥，Bob选取随机数k,生成密文C_m=\lbrace kG,P_m+kP_A\rbrace
$$
$$
C_1=k·G, \quad C_2=M+k·P_A
$$

Alice受到后解密
$$
C_2-n_AC_1=M+k·P_A-n_AkG=M
$$
举个梨子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# ----- Alice 公开公钥 -----
E = EllipticCurve(GF(3851), [324, 1287])
G = E(920, 303)

nA = 1194
PA = nA * G

print(PA.xy())
# (2067, 2178)


# ----- Bob 发送信息 -----
M = E.lift_x(233)
k = 123

C1 = k * G
C2 = M + k * PA
C1.xy(), C2.xy()
# ((2525, 1772), (255, 2423))


# ----- Alice 接受信息 -----
msg = C2 - nA * C1
msg.xy()
# (233, 495)

椭圆曲线密码体制的优点

与基于有限域于上离散对数体系相比

  1. 安全性高
    $$
    攻击有限域上的离散对数问题是有指数积分法，运算复杂度为O(exp\sqrt[3]{(logp)(loglogp)^2}),p是模素数
    $$

    $$
    目前攻击椭圆曲线上的离散对数问题只适合攻击任何循环群上离散对数问题的大步小步法，\运算复杂度为O(exp(log\sqrt {p_{max}})) \quad p_{max}是椭圆曲线上Abel群的阶的最大素因子
    $$

  2. 密钥量小

    复杂度对比，椭圆曲线所需密钥长度更短

  3. 灵活性好

    椭圆曲线可以通过更改曲线参数实现不同的曲线，形成不同的循环群，比有限域上固定好的循环群更加丰富且多选择

ECC和RSA/DSA在保持同等安全性的情况下密钥长度对比(bits)

RSA/DSA 512 768 1024 2048 21000
ECC 106 132 160 211 600

Diffie-Hellman算法主要是实现密钥交换，并没有加密解密的算法，理解起来可能有些抽象，不过不抽象也就不是数学了。椭圆曲线上的密码体系目前也只是潦草掌握，毕竟ECC和离散一样也是一座数学大山。怎么说呢，学无止境吧。

如果你读的还算尽兴的话给个赞哦👍