DH and ElGamal

这次做到离散对数的密码,虽然原理跟着老师走了一遍,但是没有什么实战经历没有什么感觉,这里用一道题入手吧

DH协议及ElGamal加密方案的实现

背景知识

先介绍下前导知识

离散对数,DL(Discrete Logarithm)

从la佬博客la来的话

在任何群$G$中可为所有整数$k$定义一个幂数为$b^k$,而离散对数$log^b_a$是指使得 $b^k=a$的整数$k$。离散对数在一些特殊情况下可以快速计算。然而,通常没有具非常效率的方法来计算它们。公钥密码学中几个重要算法的基础,是假设寻找离散对数的问题解,在仔细选择过的群中,并不存在有效率的求解算法。

密钥交换协议,DH(Diffie Hellman)

就是以下面两位帅气大佬的名字命名的

本质上也是一种密码方案,只是因存在重大安全问题无法抵御中间人攻击而无任何实用性,但是其思想是ElGamal加密的基石

DH协议及ElGamal加密方案的实现-125e55ac.png

ElGamal加密算法

是这位来自埃及的大佬发明的

是比RSA使用更广,也就是更安全高效的密码方案

DH协议及ElGamal加密方案的实现-a4564ef7.png

2020网鼎杯-青龙组-you raise me up

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
import random

n = 2 ** 512
m = random.randint(2, n-1) | 1
c = pow(m, bytes_to_long(flag), n)
print 'm = ' + str(m)
print 'c = ' + str(c)

# m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
# c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499

已知
$$
n=2^{512}\
c=m^{flag}\ mod\ n
$$
求$flag$

显然按照一般的思维来说,这就是离散对数问题,找到这个指数flag是困难的,所以针第二个条件我们没有办法,所以我们就可以从n入手

想必n是2的512次方,比较特殊,然后可以直接求phi(n),
$$
\phi(n)=2^{511}
$$

关于求欧拉函数

关于这一步求欧拉函数,我还遇到一个小插曲,由于之前的结论
$$
(p, q)=1,n=pq\Rightarrow \phi(n)
=(p-1)\times(q-1)
$$
从这里来的惯性思维,我一直理解不了为什么不是$\phi(2^{512})=(2-1)^{512}=1$,虽然显然这个是错的

然后在查资料的过程中,发现了不少宝藏,这里有个师傅总结的求欧拉函数的方法,整理得太好了
https://blog.csdn.net/paxhujing/article/details/51353672

第一种情况

若$n=1$,则
$$
\phi(n)=1
$$

第二种情况

若$n$是质数,则
$$
\phi(n)=n-1
$$

第三种情况

若$p$是质数,$k\ge1$,则
$$
\phi(p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p})
$$
这个有必要证明下,因为上面用到的就是这条性质

还是枚举法,在$[1,p^k]$,显然只有$p,2p,3p,p^{k-1}p$与之不互素,那互素的数的个数不得是$p^k-p^{k-1}$

第四种情况

也就是RSA里面常见的,这个我之前也在作业里证明过,注意p和q不一定要是质数

若$n=p\times q$且$(p,q)=1$,则
$$
\phi(n)=\phi(p)\times \phi(q)=(p-1)\times (q-1)
$$

第五种情况

也是求欧拉函数的通式

由FTA可知,任何一个大于1的整数n,可以拆分为一系列素数幂的积$n=p^{k_1}_1p^{k_2}_2…p^{k_r}_r$,由三、四情况的结论可知
$$
\phi(n)=p^{k_1}_1p^{k_2}_2…p^{k_r}_r(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_r})
$$


$$
\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_r})
$$


那么有了第三种情况的结论,我之前的疑问也得到了解答

但是回到题目,虽然我们知道了phi(n),但是已知的RSA常见攻击,并没有针对phi(n)泄漏的,毕竟e和d都是未知

所以这道题的思路还是要转到我们今天要讲的DLP上,AKA离散对数分解问题

DLP

这里必须引入一些解DLP问题的方法,正如RSA中解大数分解问题一样,某些特殊的情况会让原本安全的加密变得有漏洞

还是一样,先使用,后搞懂

sage yyds

  • 通用的求离散对数的方法
1
discrete_log(a,base,ord,operation)

其中包含pohlig-hellman算法

  • Pollard-Rho算法
1
discrete_log_rho(a,base,ord,operation)
  • Pollard-kangaroo算法(lambda算法)
1
discrete_log_lambda(a,base,bounds,operation)
  • 大步小步算法(BSGS)
1
bsgs(base,a,bounds,operation)

至于它们的使用和适用条件,先看la佬的博客吧,这里就不展开了,主要也不会DX


回到题目,网上的解法是,因为模数n比较特殊,phi(n)可以得到完全分解,这就符合pohlig-hellman的条件,理论上可行

解题脚本

收集一下脚本

1
2
3
4
5
6
7
8
from sympy.ntheory import discrete_log
from Crypto.Util.number import long_to_bytes

n = 2 ** 512
m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499

print(long_to_bytes(discrete_log(n, c, m)))

主要有两个线程的库可以用,一个是sage自带的,一个是python中sympy库里的,不过sympy里的比较简单

DH协议及ElGamal加密方案的实现-a4040bae.png

就是求$flag=log^a_b\ mod\ n$

sage里的比较讲究,需要用Mod函数将m和c框定在模n的群里之类的意思吧

1
2
3
4
5
6
7
8
n = 2 ** 512
m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499

m = Mod(m, n)
c = Mod(c, n)

discrete_log(c, m)

前面对离散对数问题有了一个初步的概念,下面我们就进入正题,看看DH协议和ElGamal加密方案的实现

DH协议

更准确的说法应该是密钥交换协议,其实前面说它也是一种密码方案,不是很准确,因为它并不能加密指定的明文,而是生成双方都知晓,但攻击者却得不到的秘密私钥

它的流程如下

  1. 指定一个安全质数p,要求p最好是2048位的,然后在$\mathbb{Z}^*_p$中找到一个生成元g(emmmmm有效找生成元的算法不会咋整),这些Eve也能知道

  2. Alice选一个私钥x,$x\in \mathbb{Z} _{p-1}$(主要是x是在[1, p-1]这个范围里面的,但至于为什么有点忘了),得到$T_A=g^x\ mod\ p$,并将$T_A$传给Bob

  3. 同理,Bob将$T_B=g^y\ mod\ p$发给Alice,其中$T_A,T_B$,Eve也都知晓

  4. 此时,Alice可以得到$K_A=(T_B)^{x}=(g^y)^x=g^{xy}$

  5. Bob也可以得到$K_B=(T_A)^{y}=(g^x)^y=g^{xy}$

显然$K_A=K_B$,Alice和Bob从此有了他们才知道的相同的信息,对称密码的福音?

Eve虽然知道$T_A$和$T_B$,但由于离散对数问题的存在,他无法逆向得到x和y,也就得不到$g^{xy}$

DH协议的实现

老师给的这篇链接里有一些要用到的算法,不过是C的,Python就是屑,sage yyds

https://www.techiedelight.com/elgamal-encryption-algorithm-c/

改脚本是第一生产力,借鉴了里面求生成元的算法,改成Python的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def find_t(a, m, n):
y = 1
while m > 0:
r = m % 2
if r == 1:
y = (y * a) % n
a = a * a % n
m = m // 2
return y


def primitive_root(pi):
for a in range(2, pi):
flag = 1
for i in range(1, pi):
if find_t(a, i, pi) == 1 and i < pi - 1:
flag = 0
elif flag and find_t(a, i, pi) == 1 and i == pi - 1:
return a

原根就是最小生成元

但是可以看出这个算也是遍历到p的,妥妥的brute-force,32位的p都跑不出来,感觉和我的差不多

所以最后p取得16位,复现了上面DH协议的流程

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from Crypto.Util.number import getPrime
from sage import my_gcd, my_ord, l_pow
from random import randint


def find_t(a, m, n):
_y = 1
while m > 0:
r = m % 2
if r == 1:
_y = (_y * a) % n
a = a * a % n
m = m // 2
return _y


def primitive_root(pi):
for a in range(2, pi):
flag = 1
for i in range(1, pi):
if find_t(a, i, pi) == 1 and i < pi - 1:
flag = 0
elif flag and find_t(a, i, pi) == 1 and i == pi - 1:
return a


p = getPrime(16)
print("素数p :", p)
g = primitive_root(p)
print("生成元g是 : ", g)

# 私钥生成
x = randint(1, p)
y = randint(1, p)

TA = l_pow(g, x, p)
TB = l_pow(g, y, p)

KA = l_pow(TA, y, p)
KB = l_pow(TB, x, p)

assert KA == KB
print("密钥交换成功,你的私钥很安全")

运行的结果是
DH协议及ElGamal加密方案的实现-f7c0a2dc.png

看来以后还要看看怎么有效找生成元的算法(其实sage里面早就有了,看文末)

所以小节一下,显然AB共享的来自两个随机生成的随机数,两人并不能控制其内容,所以作为密钥更为合理

中间人攻击

虽然DH方案本身挺好好,但之所以说它没有的使用,是因为存在中间人攻击

(从网上抄来的,因为觉得自己对这个还有点模糊,但看了之后清楚一些)
其攻击思路如下:

  1. Alice发送公钥$T_A$给Bob, 中间人Eve截取该值,并选择了一个自己的私钥$z$,计算出自己的公钥$_C=g^c\bmod\ q$然后发送自己的公钥给Bob
  2. Bob向Alice传递自己的公钥$T_B$时,也被中间人Eve截获该值,Eve代替Bob发送它自己的公共值$T_C$给Alice
  3. 此时,Alice收到中间人Eve的公钥,Alice和EVE计算出会话密钥$K_{AC}=g^{xz}\bmod\ q$,Bob也收到中间人发送的公钥,Bob和Eve计算出会话密钥$K_{BC}=g^{yz}\bmod\ q$
  4. Alice和Bob都以为是和对方协商好了会话密钥,于是双方互相发送数据,Alice用$K_{AC}$加密数据之后发送给Bob,Eve截获该数据,用$K_{AC}$解密,即可查看Alice发送给Bob的数据,Eve还可对其进行修改,然后用$K_{BC}$加密发送给Bob,这时Bob收到的消息已经被中间人Eve窥探甚至篡改,但Bob对此毫不知情

这就是中间人攻击的原理,妙,给我感觉DH协议具有传递性哈哈哈哈哈哈

这里的理解需要注意几点,我一开始就是没搞清楚这个,举个例子就是,Alice不能100%肯定自己手中的共享私钥就是Bob手中的那个,而且他们没有办法确认,这就是一开始接触密码学里的那条悖论

对称密码,用秘密(私钥)守护秘密(明文),那怎么能确保前一个秘密的安全性,不会被Eve监听呢;如果既然有保护第一个秘密(私钥)的方法,那为什么不用这个方法来保护第二个秘密(明文)呢

密码学还讲博弈

ElGamal加密方案

最后终于到了我们的ElGamal加密算法,讲完DH,ElGamal其实已经讲完一半了

因为ElGamal和DH真的好像,正如老师上课说的,DH他们怎么就没想到ElGamal呢,明明只是一步之遥(当然是大牛的一步)

视觉疲劳了,先写代码,拿出我们熟悉的long_to_bytes,bytes_to_long

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
from Crypto.Util.number import getPrime, bytes_to_long as b2n, long_to_bytes as n2b
from sage import l_pow, my_inverse
from random import randint


def find_t(a, m, n):
_y = 1
while m > 0:
r = m % 2
if r == 1:
_y = (_y * a) % n
a = a * a % n
m = m // 2
return _y


def primitive_root(pi):
for a in range(2, pi):
flag = 1
for i in range(1, pi):
if find_t(a, i, pi) == 1 and i < pi - 1:
flag = 0
elif flag and find_t(a, i, pi) == 1 and i == pi - 1:
return a


p = getPrime(16)
print(p)
print("素数p :", p)
g = primitive_root(p)
print("生成元g是 : ", g)

# key generation
x = randint(1, p)
y = randint(1, p)

TA = l_pow(g, x, p)
TB = l_pow(g, y, p)

pk = [p, g, TA]
sk = x

# encryption
flag = b"f"
m = b2n(flag)
print(flag)
print(m)

ci = l_pow(g, y, p)
ciphertext = m * l_pow(TA, y, p) % p

# decryption
mi = ciphertext * my_inverse(l_pow(ci, x, p), p) % p
print(n2b(mi))

由于求生成元的问题所限制,p不能取得太大,这也就连带着明文不能太长,不能超过16位比特,屑,这能加密个啥

但好歹最后的结果是一样的

DH协议及ElGamal加密方案的实现-586e337d.png

手写了一下加密解密过程,打公式太耗时了

DH协议及ElGamal加密方案的实现-966d65b9.png

应该可以理解,主要就是用DH里面的共享私钥乘以明文m进行加密,然后把共享私钥作为密文的一部分发送,然后除以(这里相当于求逆元)共享私钥就是明文了

所以说,ElGamal才会和DH那么有关联,密钥共享共享的就是ElGamal里面的密钥

那么这样Alice和Bob就能通过明文对进行验证了,中间人即使改变了私钥和Alice与Bob分别建立链接,但是依旧无法知晓明文的内容,因为只有x才能将明文解密,Eve只能创造一个z,而Alice和Bob却可以通过解密出来的内容是否是乱码检查是否存在中间人(我的理解)

求原根的有效方法

1
2
3
4
5
p = getPrime(1024)

gp ('znprimroot('+str(p)+')')
# 或
pari ('znprimroot('+str(p)+')')

emmmmm好吧当我没说
DH协议及ElGamal加密方案的实现-c224eccd.png

或许可以参考这个博客里的

总结

关于ElGamal和DH的关系,到这里想必都已经挺透彻的了,DLP保证了私钥的安全性即知道$g^x$,得不到x,DH则保证了有$g^x,g^y$也得不到$g^{xy}$

这就应证了,ElGamal基于DH,DH基于DL