An_Interesting_CTF_Challenge_0x2

Posted on Edited on In Word count in article: 5.2k Reading time ≈ 5 mins.

source.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
import random
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *

from Curve import curve

FLAG = b"flag{a353219d7f10f72d781c40b754d510e7}"


def point_add(P, Q):
    x3 = (P[0] * Q[0] + D * P[1] * Q[1]) % p
    y3 = (P[0] * Q[1] + P[1] * Q[0]) % p
    return (x3, y3)


def scalar_multiplication(P, n):
    Q = (1, 0)
    while n > 0:
        if n % 2 == 1:
            Q = point_add(Q, P)
        P = point_add(P, P)
        n = n // 2
    return Q


def get_key():
    private_key = random.randint(1, p - 1)
    public_key = scalar_multiplication(G, private_key)
    return (public_key, private_key)


def get_shared_secret(P, n_k):
    return scalar_multiplication(P, n_k)[0]


curve_info = curve()
p = curve_info["p"]
D = curve_info["D"]
G = (curve_info["G.x"], curve_info["G.y"])
A, n_a = get_key()
B, n_b = get_key()

assert pow(D, (p - 1) // 2, p) == 1
assert (A[0] ** 2 - D * A[1] ** 2) % p == 1
assert (B[0] ** 2 - D * B[1] ** 2) % p == 1
print("D =", D)
print("G =", G)
print("A =", A)
print("B =", B)
shared_secret = get_shared_secret(A, n_b)

key = sha256(long_to_bytes(shared_secret)).digest()
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.encrypt(pad(FLAG, 16))
print("C =", ciphertext.hex())

task.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
import random
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from Curve import curve

FLAG = b"flag{????????????????????????????}"


def point_add(P, Q):
    x3 = (P[0] * Q[0] + D * P[1] * Q[1]) % p
    y3 = (P[0] * Q[1] + P[1] * Q[0]) % p
    return (x3, y3)


def scalar_multiplication(P, n):
    Q = (1, 0)
    while n > 0:
        if n % 2 == 1:
            Q = point_add(Q, P)
        P = point_add(P, P)
        n = n // 2
    return Q


def get_key():
    private_key = random.randint(1, p - 1)
    public_key = scalar_multiplication(G, private_key)
    return (public_key, private_key)


def get_shared_secret(P, n_k):
    return scalar_multiplication(P, n_k)[0]


curve_info = curve()
p = curve_info["p"]
D = curve_info["D"]
G = (curve_info["G.x"], curve_info["G.y"])
A, n_a = get_key()
B, n_b = get_key()

print("D =", D)
print("G =", G)
print("A =", A)
print("B =", B)
shared_secret = get_shared_secret(A, n_b)

key = sha256(long_to_bytes(shared_secret)).digest()
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.encrypt(pad(FLAG, 16))
print("C =",ciphertext.hex())

# D = 841
# G = (70210196346326018298323228783367869223089211897379057380061203281233621280100334, 101948468141045147243060203936353465018134737325641287102428542544766828444719731)
# A = (72026969273392981774418076966986362461956111553551088611979083382924817005972811, 128201817310525593386581249545813413509552341431389561637102898055038847720854727)
# B = (118405884118567563062281530746539956049083561398150145014305536274191594242083518, 190549637299382268483032246904983195711360085884080305886613955302147251245442613)
# C = a6e0d676c05ea6a75f7a4d3b73a8646df745f62adbec1d957693bc8077e59d4aeca100c5fe118cfa1c1fba4f105f2787

亏格为0的曲线 \(x^2 - Dy^2 = 1\) 上的求解离散对数的问题，求解出 A ，B的私钥后根据 DH算法计算出 AB之间的共享密钥，然后利用共享密钥求解出 AES加密。

已知量为 D，基点G，点A、B，以及密文 C

根据题目代码可知曲线上的点加算法为：\((x_1,y_1)+(x_2,y_2) = (x_1x_2+Dy_1y_2,x_1y_2+x_2y_1)\)

1
2
3
4
def point_add(P, Q):
    x3 = (P[0] * Q[0] + D * P[1] * Q[1]) % p
    y3 = (P[0] * Q[1] + P[1] * Q[0]) % p
    return (x3, y3)

p 为未知量，所以我们需要先计算出p的值，作为有限域\(F_p\)使用。

根据 \(x^2 - Dy^2 \equiv 1 (mod \ p)\) 可得方程组

\(A.x^2 - D*A.y^2 - 1 = k_1*p\)

\(B.x^2 - D*B.y^2 - 1 = k_2*p\)

求公因数即可得到 p 的值。

可以判断出 D是模p的二次剩余

1
assert pow(D, (p - 1) // 2, p) == 1  # D是模p的二次剩余

根据论文可以得到对应的映射公式，实现将曲线上的离散对数问题简化为有限域 \(F_p\) 上的离散对数问题，实现在短时间内计算出离散对数的解。

论文地址：A Note on Cyclic Groups, Finite Fields, and the Discrete Logarithm Problem

在第四页的：3 Another Class of Genus 0 Curves 章节

映射公式为： \(\phi:(x,y)⟼ x-ay\)

根据映射公式，用sage中的 discrete_log() 函数即可求出B的私钥 \(n_b\)，然后DH算法计算共享密钥 \(S = A*n_b\)

exp.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
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad,unpad
from Crypto.Util.number import *
from gmpy2 import *


def point_add(P, Q):
    x3 = (P[0] * Q[0] + D * P[1] * Q[1]) % p
    y3 = (P[0] * Q[1] + P[1] * Q[0]) % p
    return (x3, y3)


def scalar_multiplication(P, n):
    Q = (1, 0)
    while n > 0:
        if n % 2 == 1:
            Q = point_add(Q, P)
        P = point_add(P, P)
        n = n // 2
    return Q


D = 841
G = (70210196346326018298323228783367869223089211897379057380061203281233621280100334, 101948468141045147243060203936353465018134737325641287102428542544766828444719731)
A = (72026969273392981774418076966986362461956111553551088611979083382924817005972811, 128201817310525593386581249545813413509552341431389561637102898055038847720854727)
B = (118405884118567563062281530746539956049083561398150145014305536274191594242083518, 190549637299382268483032246904983195711360085884080305886613955302147251245442613)


# 计算素数 p
p = gcd((A[0] ** 2 - D * A[1] ** 2) - 1, (B[0] ** 2 - D * B[1] ** 2) - 1)

sqrt_D = int(iroot(D, 2)[0])
assert iroot(D, 2)[1] == True  # 能正确开根
assert pow(D, (p - 1) // 2, p) == 1  # D是模p的二次剩余
# 注意 sqrt_D是有限域 GF(p) 上的
g = G[0] - GF(p)(sqrt_D) * G[1]
B = B[0] - GF(p)(sqrt_D) * B[1]

# B的私钥
n_b = discrete_log(B, g)

# AB的共享密钥
shared_secret = scalar_multiplication(A, n_b)[0]

# decrypt flag
C = "a6e0d676c05ea6a75f7a4d3b73a8646df745f62adbec1d957693bc8077e59d4aeca100c5fe118cfa1c1fba4f105f2787"
c = bytes.fromhex(C)
key = sha256(long_to_bytes(shared_secret)).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(c)
print(unpad(flag,16))