离散对数｜ DH ｜ ElGamal

注意：若公式显示不全，请您点击它以全部显示

学习参考

引子

DH 和 ElGamal都是基于离散对数问题的。

离散对数（Discrete Logarithm）

在任何群G中可为所有整数k定义一个幂数为$b^k$，而离散对数$loga^{b}$是指使得 $b^{k}=a$的整数k。离散对数在一些特殊情况下可以快速计算。

而公钥密码学中几个加密算法的陷门是基于寻找离散对数的解的困难。

生成元

在一个群 G 中，如果 g 是 G 的生成元，即所有 G 中的所有元素都可以被表示成 $y=g^x$，此时的 x 称为 y 在 G 中的对数。

阶

设 m≥1,gcd(a,m)=1，使得 $a^d≡1(\mod m)$ 成立的最小正整数 d 称为 a 对模 m 的阶。一般将其计为 δm(a)。

满足 $a^d≡1(\mod m) $的 d 一定满足 d∣φ(m)

原根¶

当 δm(a)=φ(m) 时，称 a 是模 m 的原根，简称 m 的原根。

只有$ m=2,4,p^α,2p^α$（p 为奇素数，α 为正整数）时，模 m 的剩余系存在原根。（充要条件）

以题代入。

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

from Crypto.Util.number import *
import random

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

# m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
# c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499

可知，flag被当作e了，即：$c = m^{flag} \mod n$

那朴素的想，这里最直接的方法就是求出在mod n的前提下，求出$\log{m}^{c}$

看到n = 2**512,则：phi= 2**511

即：phi易求

离散对数分解问题（DLP）

sage中的DLP相关函数

参数说明：

求解以base为底
a的对数
ord为base的阶，可以忽略
operation可以是+与*，默认为*
bounds是一个区间(ld,ud)，需要保证所计算的对数在此区间内

函数使用

discrete_log(a,base,ord,operation)

通用的求离散对数的方法（Pohlig-Hellman+?BSGS）

Pohig-Hellman算法是一种求解光滑阶循环群上的离散对数的方法。
- 要求$a≡g^x(\mod p)$中 g必须是原根 （对于 g 不是原根的情况，需要利用原根将原方程转化成两个关于原根的离散对数问题。
- 要求阶是光滑的（p-1可拆为多个素数相乘）
discrete_log_rho(a,base,ord,operation)

求离散对数的Pollard-Rho算法

Pollard Rho算法是一种随机性的概率型算法
- 它主要解决有限的循环群上的离散对数问题。
- Pollard Rho算法主要就是利用了循环群的生成序列呈现一个 ρ 字形状。
- 适用于生成元的阶的素因子都是大数的情形
discrete_log_lambda(a,base,bounds,operation)

求离散对数的Pollard-kangaroo算法（lambda算法）
bsgs(base,a,bounds,operation)

大步小步法
- 用于解高次同余方程的问题
- 适用于模p 为质数的情况

多项式DLP(暂未见到题，没什么了解)

#Sage
def brute_dlp(gi, ci, n, lim):
	bi = gi
	for i in range(1, lim+1):
		if bi == ci:
			return i
		bi = (bi * gi) % n
	print("[-] NOT in the range")
	print("[-] Something's Wrong, you gotta check the range", lim)

def pohlig_hellman(g, c, s, n, factors):
	res = []
	modulus = []
	for q, e in factors:
		assert pow(g, s//(q**e), n) != 1
		gi = pow(g, s//(q**e), n)
		ci = pow(c, s//(q**e), n)
		dlogi = brute_dlp(gi, ci, n, q**e)
		print("[+] dlog modulo {0} == {1}".format(q**e, dlogi))
		res.append(dlogi)
		modulus.append(q**e)
	print("\n[*] res = ", res)
	print("[*] modulus = ", modulus)
	dlog = CRT(res, modulus)
	print("\n[+] dlog modulo {0} == {1}".format(prod(modulus), dlog))
	return dlog

p = 
P = PolynomialRing(Zmod(p), name='x')
x = P.gen()
n = 
g = 
nfactors = n.factor()
s = 1
for i in nfactors:
	s *= p**(i[0].degree()) - 1

print(s)
print(factor(s))
qe = 
dlog = pohlig_hellman(g, c, s, n, qe)

flag = bytes.fromhex(hex(dlog)[2:])
print("\n[*] flag = ", flag.decode())

实例

#生成64位的素数p作为模数，int为32位，超过int要在数字后加L
p=random_prime(2L**64)
 
#定义有限域GF(p)
G=GF(p)
 
#找一个模p的原根
gp ('znprimroot('+str(p)+')')
#输出Mod(rt,p)，则x是模p的原根
g=G(rt)
 
#生成私钥
x=G(ZZ.random_element(p-1))
 
#公钥y=g^x mod p，由于已经定义在GF(p)上，因此g**x就是g^x mod p
y=g**x
 
#计算离散对数的通用方法
discrete_log(y,g)==x
#n为合数（Pohlig-Hellman）
x = discrete_log(mod(b,n),mod(a,n)) 
#n为质数或质数幂（线性筛Index Calculus）
R = Integers(99)
a = R(4)
b = a^9
b.log(a)
#或
x = int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))"))
x = gp.znlog(b, gp.Mod(a, n))
 
#计算离散对数的lambda方法
discrete_log_lambda(y,g,(floor(ZZ(x)/2),2*ZZ(x)))==x
 
#小步大步法计算离散对数
bsgs(g,y,(floor(ZZ(x)/2),2*ZZ(x)))==x

回到题目，易得：

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

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

discrete_log(c, m)

接下来步入主题——DH

密钥交换协议（Diffie Hellman）

参考

以两位发明者命名的密码方案，其思想为理解ElGamal加密奠定了基础。

总体而言，密钥交换协议不是一种加密明文的算法，而是生成一个较为安全的密钥的算法。

流程

公布一个质数q(最好是2048位)，然后在Zp中找到一个生成元g，也公布出来
Alice选一个私钥$X_A$，$X_A∈Z_{p−1}$，得到公钥$Y_A = g^{X_A} \mod q$，并将$Y_A$传给Bob
Bob也选好私钥$X_B$, 得到公钥$Y_B=g^{X_B} \mod q$发给Alice
公布YA、YB
收到YB的Alice可以得到$K=(Y_B)^{X_A}=(g^{Y_B})^{X_A}=g^{X_A*Y_B} \mod q$
收到YA的Bob也可以得到$K=(Y_A)^{X_B}=(g^{Y_A})^{X_B}=g^{X_A*X_B} \mod q$

显然Alice和Bob得到了一份相同的信息，而对于攻击者而言，由YA推出XA是困难的，同理也无法得到XB，所以攻击者无法得知这相同的信息

能不能用这性质直接传递密文呢?

显然是不能的

Alice和Bob无法控制最后K的内容，所以K更适合当作其他加密体系的私钥

中间人攻击

值得一说，密钥交换协议的数学理论是自洽的、安全的

也就是说，中间人攻击不是从数学层面上硬核破解出Alice和Bob所生成的私钥

而是以欺诈的手段，下面先看一张攻击的流程图

仔细说一下

攻击者能知道g和q，于是自己随意生成两个私钥$X_{D_1}、X_{D_2}$，并用其生成两个公钥
- $Y_{D_1} = a^{X_{D_1}} \mod q$
- $Y_{D_2} = a^{X_{D_2}} \mod q$
在Alice对外公布$Y_A$时，攻击者截获它（不让Bob收到$Y_A$）,然后：

不能让Bob收不到东西，攻击者给Bob传输$Y_{D_1}$
同理，攻击者截获Bob发的$Y_B$,然后给Alice发$Y_{D_2}$
Alice以为自己收到的是Bob的，于是开始生成

$K_2=(Y_{D_2})^{X_A}=(g^{X_{D_2}})^{X_A} = g^{X_{D_2}*X_A}$
而对于攻击者，则有：

$K_2=(Y_{A})^{X_{D_2}}=(g^{X_{A}})^{X_{D_2}} = g^{X_{D_2}*X_A}$

即：攻击者获得了Alice所生成的、用来加密的密钥，也就可以破解Alice后续发的密文了
同理，Bob也有如下操作

$K_1=(Y_{D_1})^{X_B}=(g^{X_{D_1}})^{X_B} = g^{X_{D_1}*X_B}$
而对于攻击者，也有：

$K_2=(Y_{B})^{X_{D_1}}=(g^{X_{B}})^{X_{D_1}} = g^{X_{D_1}*X_B}$

同样的，Bob用这个DH协议所生成的密钥 来 加密的密文 都能被攻击者破解

值得一说，若攻击者不想让Alice与Bob察觉异样，他也能做到破解完密文后，修改明文后再加密发给另一方

而DH协议能被破解的关键则在于Alice和Bob无法确认信息的发送方，所以攻击者充当了中转站的角色分别与A、B进行DH协议

更具体的实现、以及实际渗透应用这里暂且省略

ElGamal加密算法

同样是以发明者命名的算法。

简介

ElGamal加密算法是一个基于DH密钥交换的非对称加密算法

它在1985年由塔希尔·盖莫尔提出，GnuPG和PGP等很多密码学系统中都应用到了ElGamal算法。

ElGamal加密算法可以定义在任何循环群G上，安全性取决于G上的离散对数难题。

加 \ 解密流程

流程学习参考lazzro相关博客

代码学习参考4XWi11师傅相关博客

这里依然以Alice与Bob举例，即：Alice打算给Bob发消息

加密

Bob

选择大素数p、其生成元g，以及自己的私钥x（1<x<p−1）
生成$y ≡ g^x \mod p$
公布公钥为(y,g,p)

Alice

处理一下明文格式，对明文分组，使得每组m小于十进制下的p（这里为方便理解，假设只有1组）
随机选择r（1< ri < p−1）
生成
- $c ≡ g^r \mod p$
- $c’ ≡ m * y^r \mod p$
公布密文C（c, c’）

解密

Bob

$m ≡ c’ *(c^x)^{-1} \mod p$

证明

类比

过了一遍流程后，发现Elgamal确实是基于DH协议的

相当于DH协议产生好私密的密钥K后，采用加密方式$C = m * K \mod p$，解密即：$m = C*K^{-1} \mod p$

正常而言，攻击者在不充当中间人的前提下无法得知K，也就无法得知$K^{-1}$,从而无法解出m

换句话说，收到消息后的Bob还可以用K加密他给Alice的回复,这同样也是安全的

再换言之，现实世界里中间人攻击依旧对Elgamal加密有效

（但ctf题目采用不了此方法，只能寄希望于特殊情况的离散对数可求解）

总流程

贴一下la佬的干练精简博客相关内容

实现代码

小改了下来自4XWi11师傅的代码

为与DH协议承上启下，Elgamal加解密过程相关变量名是按DH协议命名的

# sage

from Crypto.Util.number import getPrime, bytes_to_long as b2n, long_to_bytes as n2b
from gmpy2 import invert
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):  # 找对于模p的有效生成元g
    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


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

# key generation
XA = randint(1, q)
XB = randint(1, q)

YA = pow(g, XA, q)
YB = pow(g, XB, q)

pk = [q, g, YA]  # 公钥
sk = XA  # 私钥

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

ci = pow(g, XB, q)  # 密文第一部分
ciphertext = m * pow(YA, XB, q) % q  # Bob用自己的密钥XB来加密（密文第二部分）

# decryption
mi = ciphertext * invert(pow(ci, XA, q), q) % q  # Alice用自己的密钥XA即可解密
print(n2b(mi))

Elgamal数字签名

参考

签名流程

没看懂签名🤔

A要发东西，A签名后产生了r,s

那么也就是其他人利用验证里公式能确定这就是A发的密文，但验证里有m，除A之外的其他人不是不知道m吗？

那是怎么验证的？

或许是说，A还得公布$g^m$？

看完攻击后，我明白了（说到底是没明白数字签名的意义何在）签名中的m是公开的

签名的直接目的不是为了加密、保证安全性，而是让人能确定这m就是你所生成、你所发出的

至于实际应用层面，我想可以直接把上文中的m换成Elgamal加密所得的密文，对此签名即可避免中间人攻击

Harry's Blog

离散对数｜ DH ｜ ElGamal

学习参考

引子

离散对数（Discrete Logarithm）

生成元

阶

原根¶

以题代入。

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

离散对数分解问题（DLP）

密钥交换协议（Diffie Hellman）

流程

中间人攻击

ElGamal加密算法

简介

加 \ 解密流程

加密

解密

类比

总流程

实现代码

Elgamal数字签名

签名流程

相关攻击

学习参考

引子

离散对数（Discrete Logarithm）

生成元

阶

原根¶

以题代入。

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

离散对数分解问题（DLP）

密钥交换协议 （Diffie Hellman）

流程

中间人攻击

ElGamal加密算法

简介

加 \ 解密流程

加密

解密

类比

总流程

实现代码

Elgamal数字签名

签名流程

相关攻击

密钥交换协议（Diffie Hellman）