例题

Elgamal

题目描述

题目啥也没有说，就是写了了名字 Elgamal。

Elgamal.py 文件如下：

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
55
56
57
58
59
60
61
62
63
64
65
from Crypto.Util.number import *
from key import FLAG

def keygen(size):
    q = getPrime(80)
    k = getPrime(944)   
    while True:
        p = q * k + 1
        if isPrime(p):
            break
        k += 1
    g = 2
    while True:
        if pow(g, q, p) == 1:
            break
        g += 1
    A = getRandomInteger(size) % q
    B = getRandomInteger(size) % q
    x = getRandomInteger(size) % q
    h = pow(g, x, p)
    return (g, h, A, B, p, q), (x)

def rand(A, B, q):
    global rand_state
    rand_state, ret = (A * rand_state + B) % q, rand_state
    return ret

def encrypt(pubkey, m):
    g, h, A, B, p, q = pubkey
    assert 0 < m <= p
    r = rand(A, B, q)
    c1 = pow(g, r, p)
    c2 = (m * pow(h, r, p)) % p
    return (c1, c2)

rand_state = getPrime(1024)
pubkey, privkey = keygen(1024)

m = bytes_to_long(FLAG)
c1, c2 = encrypt(pubkey, m)
c1_, c2_ = encrypt(pubkey, m)

print(c1, c2)
print(c1_, c2_)

s0 = 543263588863771657634119
s1 = 628899245716105951093835
s2 = 78708024695487418261582
s3 = 598971435111109998816796
s4 = 789474285039501272453373

assert ( A * s0 + B ) % q == s1
assert ( A * s1 + B ) % q == s2
assert ( A * s2 + B ) % q == s3
assert ( A * s3 + B ) % q == s4

p = 65211247300401312530078141569304950676358489059623557848188896752173856845051471066071652073612337629832155846984721797768267868868902023383604553319793550396610085424563231688918357710337401138108050205457200940158475922063279384491022916790549837379548978141370347556053597178221402425212594060342213485311
g = 27642593390439430783453736408814717946185190497201679721975757020767271070510268596627490205095779429964809833535285315202625851326460572368018875381603399143376574281200028337681552876140857556460885848491160812604549770668188783258592940823128376128198726254875984002214053523752696104568469730021811399216
h = 54585833166051670245656045196940486576634589000609010947618047461787934106392112227019662788387352615714332234871251868259282522817042504587428441746855906297390193418159792477477443129333707197013251839952389651332058368911829464978546505729530760951698134101053626585254469108630886768357270544236516534904

c1 = 60724920570148295800083597588524297283595971970237964464679084640302395172192639331196385150232229004030419122038089044697951208850497923486467859070476427472465291810423905736825272208842988090394035980454248119048131354993356125895595138979611664707727518852984351599604226889848831071126576874892808080133
c2 = 48616294792900599931167965577794374684760165574922600262773518630884983374432147726140430372696876107933565006549344582099592376234783044818320678499613925823621554608542446585829308488452057340023780821973913517239972817669309837103043456714481646128392677624092659929248296869048674230341175765084122344264
c1_ = 42875731538109170678735196002365281622531058597803022779529275736483962610547258618168523955709341579773947887175626960699426438456382655370090748369934296474999389316334717699127421889816721511602392591677377678759026657582648354688447456509292302633971842316239774410380221303269351351929586256938787054867
c2_ = 64829024929257668640929285124747107162970460545535885047576569803424908055130477684809317765011143527867645692710091307694839524199204611328374569742391489915929451079830143261799375621377093290249652912850024319433129432676683899459510155157108727860920017105870104383111111395351496171846620163716404148070

知识点

本题的考察点有以下几个：

  1. 如何通过线性方程组构造等式求解模数。
  2. 欧拉定理的变形和利用。
  3. 有限域上的开根。

构造等式求解模数

这个就是考验基本的数学观察力，还是比较容易想到的。给出下面的方程组含有 4 个方程，3 个未知数为 $A$ ，$B$ ， $q$​​ ，所以理论上我们是可以求解的。

方程组的解法一般都是消元法（代入消元、加减消元），这里加减消元一下：

这个减法看着不舒服，不妨换元一下，令 $ai = (s{i+1} - s_i)$ 。则上述方程组可以写为：

现在成功消元了 $B$ ，接下来就考虑想办法消元 $A$ 。但是这是有模的情况，未知数 $q$ 是模数，不能与普通的方程组求解一般，不好看出来怎么消元。那可以将上述的方程全部进行化解规约（由递推式到通项公式。

由此可以看出，$a_2$ 和 $a_1$ 差的就是一个 $a_0$ ，所以可以试试：

移项就可以得到 $0$​​ 。通过代换的方式，消掉了未知数 $A$ 。

等式左边全部是已知的，右边只有模数 $q$ 。上述式子的含义就是 $q | a_2 \times a_0 - a_1^2$ 。如果 $a_2 \times a_0 - a_1^2$ 是负数，则可以交换为 $a_1^2 - a_2 \times a_0$​ 交换的结果也是 $0$ 。

于是就简单啦，直接将左边进行因数分解，再找到合适的位数的质因数就大概率是 $q$​ 。

这里不能考虑大数分解困难，因为左边的数有很多的质因数，分解起来是很容易的。

求解了 $q$ 就一瞬可以求解 $A$ 和 $B$ 了。

欧拉函数的变形和利用

欧拉函数的原始形式为 $a^{\varphi(p)} \equiv 1 \pmod p, gcd(a, p) = 1$ 。

现在已知条件如下：

符号解释：

$A$ , $B$ , $p$ , $q$ , $g$ , $h$ , $c1$ , $c_1\$ , $c2$ , $c_2\$ 都是题目中相关参数，意义与题中一致，其中 $p$ 和 $q$ 都是质数，这些数都是已知的。

$x$ 是题中的私钥，是未知的。

$r1\$​ 与 $r_1$​​ 为生成的随机数，只知道两者之间存在关系，但是两者都未知。

$m$ 则是 flag 即是我们所要求的。

求解过程：

可以看到推导到最后，右侧的 $c2\^{-1} \times h^{-B} \times c_2^{-A}$​ 和 $p$​ 都是已知的。

有限域上开根

此时，让我们回顾一下，RSA 算法的求解原理（本质就是欧拉函数）。

$(e, n)$​ 是公钥， $(d,n)$​​ 是私钥。 当拿到一个密文 $c \equiv m^e \pmod n$ 时是如何求解明文 $m$​​ 的呢？有没有感觉好像并没有开有限域的方，它也可以求解出来呀？

那是因为求解过程中， $gcd(e,\varphi(n)) = 1$​ 所以存在 $d$​ 使得 $e \times d \equiv 1 \pmod {\varphi(n)}$​ 。

即 $e \times d + \varphi(n) \times y = 1$ 是有解的。

根据裴蜀定理，上述方程有解的前提是 $gcd(e, \varphi(n))|1$ ，则 $gcd(e,\varphi(n)) = 1$

而本题中 $gcd(A-1, \varphi(p)) = 7438$​​​ ，所以 $(A-1) \times x + \varphi(p) \times y = 1$​​​ 是不存在解的。

但是 $(A-1) \times x + \varphi(p) \times y = gcd(A-1, \varphi(p))$​ 则是一定有解的。

即我们可以找到一个 $d’$​​​ 使得 $(A-1) \times d’ + \varphi(p) \times y = gcd(A-1, \varphi(p))$​​​ 即 $(A-1) \times d’ \equiv gcd(A-1, \varphi(p)) \pmod {\varphi(p)}$。

令 $d = gcd(A-1, \varphi(p)), a = \frac{A-1}{d},$

那么 $(m^{(A-1)})^{d’} \equiv m ^{(A-1) \times d’} \equiv m ^ {k \times \varphi(p) + d} \equiv (m^{\varphi(p)})^k \times m^d \equiv 1^k \times m^d \equiv m^d \pmod p$ 。​​

如此求出了 $m^d$​ ，但是就不得不进行有限域上的开根了。这里是利用的 Adleman-Manders-Miller rth Root Extraction Method paper 的方法。原理有点小复杂，反正遇到这种问题直接调用这个现成的代码就好。

但是这个方法只能求出来满足条件的一个特解，而开 $n$ 次方根，理论上是有 $n$ 个的，那怎么通过一个特解来得到通解呢？。

可以通过 $i^n \equiv 1 \pmod p$​来实现。即

若 $x_0^n \equiv y \pmod p$ 并且 $i^n \equiv 1 \pmod p$ 则 $x_0^n \times i^n \equiv 1 \pmod p$ 则 $(x_0 \times i)^n \equiv 1 \pmod p$ 所以 $x = x_0 \times i$ 就是一组解，通过遍历所有的 $i$ 即可以找到所有的解，故 $x = x_0 \times i$ 就是通解。

更简单粗暴的方法就是直接顺次枚举，一会就试出来了。

题目详解

先总览一下代码：

1~2 行在导入包。

4~34 行在定义函数。

36 行生成了一个随机的 1024 bit 的质数 rand_state 。

37 行应该是生成了相关密钥，并传入了一个 1024 的参数，应该和密钥的位数有关。

39 行在处理我们亲爱的 flag。

40~41 行在对 flag 进行操作，看样子应该是在进行加密，我们应该重点关注这个地方。

43~44 行将加密后的结果打印给了我们。也就是密文我们是已知了。但是统一明文连续加密了两次，这个操作是有风险的。

46~50 行定义了 4 个数字。

52~55 行给了 4 个等式。这一看就是一个数学题，再一看已知量，就知道这几个未知数 $A,B,q$​ 是可以求出来，那就不管有没有用，先求出来再说。（求法见第一个知识点。

57~64 行就是给出了相关的参数作为已知， $p, g, h, c1, c_2, c_1\, c2\$ 。

现在来细细分析代码：

keygen 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def keygen(size):
    q = getPrime(80)
    k = getPrime(944)  # 生成两个质数，一大一小
    while True: # 也就是说 p 是一个质数,同时 p%q=1
        p = q * k + 1
        if isPrime(p):
            break
        k += 1
    g = 2
    while True: # 找到一个 g 使得 pow(g,q,p) = 1
        if pow(g, q, p) == 1:
            break
        g += 1
    A = getRandomInteger(size) % q
    B = getRandomInteger(size) % q
    x = getRandomInteger(size) % q # 随机取了三个整数
    h = pow(g, x, p) # 根据 elgamal 的加密方式， h 应该就是公钥，x 就是私钥了。
    return (g, h, A, B, p, q), (x)

分析完毕，除了 $p$ 同时满足关系 $p \equiv 1 \pmod q$ 外，没啥异常。

rand 函数

1
2
3
4
def rand(A, B, q):
    global rand_state # 36 行生成的随机数，看来是作为了种子
    rand_state, ret = (A * rand_state + B) % q, rand_state # 两次产生的随机数之间是有计算关系的
    return ret

分析完，发现敏感点，这样的自定义“随机”函数，多次生成的“随机数”之间是有代数关系的，即随机数之间完全不随机了，这是非常危险的。

encrypt 函数

1
2
3
4
5
6
7
def encrypt(pubkey, m): # 公钥 和 flag
    g, h, A, B, p, q = pubkey
    assert 0 < m <= p
    r = rand(A, B, q) # 生成了一个自定义随机数
    c1 = pow(g, r, p)
    c2 = (m * pow(h, r, p)) % p
    return (c1, c2) # 返回加密结果

虽然这个加密函数才是重头戏，因为其直接与我们的 flag 相关。但是这个加密函数，确实没啥问题，就是 Elgamal 标准的加密方式。

那可就难了，至少 Elgamal 目前的安全性还是很够的，不可能去解决离散对数问题。那问题在哪里呢？

现在回顾发现的问题：

  1. 同一明文连续加密了两次。
  2. 随机数不随机了。

单独看都是有风险，放一起就是大漏洞！

Elgamal 的加密中，严格要求生成的随机数 r 不能重复使用，更不能对同一明文进行加密。而此处虽然两次加密没有使用相同的随机数 r 但是两次使用的随机数之间有代数关系，可以互相推导，这就有问题：可以结合两次加密的结果构建方程组进行解方程。

于是，才有了前面知识点中，欧拉函数的变形利用。这就是发现这一点后，开始将所以已知量罗列出来，开始尝试着手构建方程并解方程。

参考代码

有了前面的分析之后，就可以很简单地写出代码了

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import time
import random
from Crypto.Util.number import long_to_bytes
import gmpy2

def factor_to_get_q(temp):
    # 对 temp 进行因式分解
    factors = factor(temp)
    for i in factors:
        if i[0].nbits() == 80:  # 80, 刚好 80 bits
            return gmpy2.mpz(i[0])
    raise Exception("fail to get q")

def get_A_B_q():
    s0 = 543263588863771657634119
    s1 = 628899245716105951093835
    s2 = 78708024695487418261582
    s3 = 598971435111109998816796
    s4 = 789474285039501272453373

    a0 = s1 - s0
    a1 = s2 - s1
    a2 = s3 - s2

    temp = a1 * a1 - a2 * a0 
    
    q = factor_to_get_q(temp)
    A = a1 * gmpy2.invert(a0, q) % q# = gmpy2.mpz(12742153496769814072597)
    B = (s1 - A * s0) % q # = gmpy2.mpz(3035433788765894539799)

    return A, B, q

def AMM(o, r, q):
    """
    pow(x, r, q) = o --> return x
    """
    start = time.time()
    # print('\n----------------------------------------------------------------------------------')
    # print('Start to run Adleman-Manders-Miller Root Extraction Method')
    # print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    # print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    # print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    # print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            # print('[+] Calculating DLP...')
            j = - dicreat_log(a, d)
            # print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c ^ r
    result = o^alp * h
    # end = time.time()
    # print("Finished in {} seconds.".format(end - start))
    # print('Find one solution: {}'.format(result))
    return result


def exgcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = exgcd(b % a, a)
        return (g, y - (b // a) * x, x)

def crack():
    c1 = gmpy2.mpz(60724920570148295800083597588524297283595971970237964464679084640302395172192639331196385150232229004030419122038089044697951208850497923486467859070476427472465291810423905736825272208842988090394035980454248119048131354993356125895595138979611664707727518852984351599604226889848831071126576874892808080133)
    c2 = gmpy2.mpz(48616294792900599931167965577794374684760165574922600262773518630884983374432147726140430372696876107933565006549344582099592376234783044818320678499613925823621554608542446585829308488452057340023780821973913517239972817669309837103043456714481646128392677624092659929248296869048674230341175765084122344264)
    c1_ = gmpy2.mpz(42875731538109170678735196002365281622531058597803022779529275736483962610547258618168523955709341579773947887175626960699426438456382655370090748369934296474999389316334717699127421889816721511602392591677377678759026657582648354688447456509292302633971842316239774410380221303269351351929586256938787054867)
    c2_ = gmpy2.mpz(64829024929257668640929285124747107162970460545535885047576569803424908055130477684809317765011143527867645692710091307694839524199204611328374569742391489915929451079830143261799375621377093290249652912850024319433129432676683899459510155157108727860920017105870104383111111395351496171846620163716404148070)

    p = gmpy2.mpz(65211247300401312530078141569304950676358489059623557848188896752173856845051471066071652073612337629832155846984721797768267868868902023383604553319793550396610085424563231688918357710337401138108050205457200940158475922063279384491022916790549837379548978141370347556053597178221402425212594060342213485311)
    g = gmpy2.mpz(27642593390439430783453736408814717946185190497201679721975757020767271070510268596627490205095779429964809833535285315202625851326460572368018875381603399143376574281200028337681552876140857556460885848491160812604549770668188783258592940823128376128198726254875984002214053523752696104568469730021811399216)
    h = gmpy2.mpz(54585833166051670245656045196940486576634589000609010947618047461787934106392112227019662788387352615714332234871251868259282522817042504587428441746855906297390193418159792477477443129333707197013251839952389651332058368911829464978546505729530760951698134101053626585254469108630886768357270544236516534904)

    A, B, q = get_A_B_q()

    # d'
    d, d1, y = exgcd(A-1, p-1)
    a = (A-1) // d

    # c2_^(-1)
    c2__invert = gmpy2.invert(c2_, p)

    m7438 = pow(c2__invert * pow(h, B, p) * pow(c2, A, p) % p, d1, p)

    x0 = AMM(m7438, d, p)

    for l in range(d):
        flag = long_to_bytes(pow(l, p//d, p)*x0%p)
        if b"flag" in flag:
            print(flag)
            break
 
crack()

最后，flag 如下：

b’flag{19e9f185e6a680324cedd6e6d9382743}’