巅峰极客2024_crypto

前言

应该是这个暑假里面(目前)打的最难的一场了，相比于das，他就上一个密码题啊我靠，八个小时，上了三波题，就开局一个密码，还是没写过的ECDSA加密，写不出来就很尴尬也很痛苦

题目

task

1
from ecdsa.ecdsa import *
2
from Crypto.Util.number import *
3
import hashlib
4
import gmpy2
5

6
def inverse_mod(a, m):
7
    if a == 0:
8
        return 0
9
    return gmpy2.powmod(a, -1, m)
10

11
def bit_length(x):
12
    return x.bit_length()
13

14
def get_malicious_key():
15
    a = 751818
16
    b = 1155982
17
    w = 908970521
18
    X = 20391992
19
    return a, b, w, X
20

21
class RSZeroError(RuntimeError):
22
    pass
23

24

25
class InvalidPointError(RuntimeError):
26
    pass
27

28

29
class Signature(object):
30
    """ECDSA signature."""
31

32
    def __init__(self, r, s):
33
        self.r = r
34
        self.s = s
35

36

37
class Public_key(object):
38
    """Public key for ECDSA."""
39

40
    def __init__(self, generator, point, verify=True):
41

42
        self.curve = generator.curve()
43
        self.generator = generator
44
        self.point = point
45
        n = generator.order()
46
        p = self.curve.p()
47
        if not (0 <= point.x() < p) or not (0 <= point.y() < p):
48
            raise InvalidPointError(
49
                "The public point has x or y out of range."
50
            )
51
        if verify and not self.curve.contains_point(point.x(), point.y()):
52
            raise InvalidPointError("Point does not lay on the curve")
53
        if not n:
54
            raise InvalidPointError("Generator point must have order.")
55

56
        if (
57
            verify
58
            and self.curve.cofactor() != 1
59
            and not n * point == ellipticcurve.INFINITY
60
        ):
61
            raise InvalidPointError("Generator point order is bad.")
62

63

64
class Private_key(object):
65
    """Private key for ECDSA."""
66

67
    def __init__(self, public_key, secret_multiplier):
68

69
        self.public_key = public_key
70
        self.secret_multiplier = secret_multiplier
71

72
    def sign(self, hash, random_k):
73

74
        G = self.public_key.generator
75
        n = G.order()# 获取该椭圆模数
76

77
        k = random_k % n
78

79
        p1 = k * G
80
        r = p1.x() % n
81
        if r == 0:
82
            raise RSZeroError("amazingly unlucky random number r")
83
        s = (
84
            inverse_mod(k, n)
85
            * (hash + (self.secret_multiplier * r) % n)
86
        ) % n
87
        if s == 0:
88
            raise RSZeroError("amazingly unlucky random number s")
89
        return Signature(r, s)
90

91
    def malicious_sign(self,hash, random_k, a, b, w, X):
92
        # t = random.randint(0,1)
93
        t = 1
94
        G = self.public_key.generator
95
        Y = X * G
96
        n = G.order()
97
        k1 = random_k
98
        z = (k1 - w * t) * G + (-a * k1 - b) * Y
99
        zx = z.x() % n
100
        k2 = int(hashlib.sha1(str(zx).encode()).hexdigest(), 16)
101
        #print(f'k2 = {k2}')
102
        p1 = k2 * G
103
        r = p1.x() % n
104
        if r == 0:
105
            raise RSZeroError("amazingly unlucky random number r")
106
        s = (
107
                    inverse_mod(k2, n)
108
                    * (hash + (self.secret_multiplier * r) % n)
109
            ) % n
110
        if s == 0:
111
            raise RSZeroError("amazingly unlucky random number s")
112
        return (Signature(r, s),k2)
113

114
if __name__ == '__main__':
115
    a,b,w,X = get_malicious_key()
116

117
    message1 = b'It sounds as though you were lamenting,'
118
    message2 = b'a butterfly cooing like a dove.'
119
    hash_message1 = int(hashlib.sha1(message1).hexdigest(), 16)
120
    hash_message2 = int(hashlib.sha1(message2).hexdigest(), 16)
121
    private = getRandomNBitInteger(50)
122
    rand = getRandomNBitInteger(49)
123
    public_key = Public_key(generator_192, generator_192 * private)
124
    private_key = Private_key(public_key, private)
125
    sig = private_key.sign(hash_message1, rand)
126
    malicious_sig,k2 = private_key.malicious_sign(hash_message2, rand, a,b,w,X)
127

128
    print(a,b,w,X)
129
    print(sig.r)
130
    print(malicious_sig.r)
131

132
    '''
133
    751818 1155982 908970521 20391992
134
    sig.r=6052579169727414254054653383715281797417510994285530927615
135
    malicious_sig.r=3839784391338849056467977882403235863760503590134852141664
136
    '''
137

138
    # flag为flag{uuid}格式
139
    flag = b''
140
    m = bytes_to_long(flag)
141
    p = k2
142
    for i in range(99):
143
        p = gmpy2.next_prime(p)
144
    q = gmpy2.next_prime(p)
145
    e = 65537
146
    c = pow(m,e,p*q)
147
    print(c)
148
    # 1294716523385880392710224476578009870292343123062352402869702505110652244504101007338338248714943

写题的时候有一些地方被我改了一点点，应该可以看出来（）

思路

刚拿到这个题目的时候第一想法是恢复k1再去恢复k2，第二遍读代码的时候看见 public_key = Public_key(generator_192, generator_192 * private),这就确定了这个曲线是curve_192，我又知道r，那我就可以直接去求出p，求p这里方法比较多，在网上找了个二次剩余的方法，求出p。

$z = (k1 - w * t) * G + (-a * k1 - b) * Y$ $化简成$

$z=p1+(-w)*G+(-a)*X*p1+(-b)*X*G$

那么这个题就出来了

exp

1
import hashlib
2
import gmpy2
3
from Crypto.Util.number import *
4

5
r1=6052579169727414254054653383715281797417510994285530927615
6

7
#curve_192
8
p=6277101735386680763835789423207666416083908700390324961279
9
a=-3
10
b=2455155546008943817740293915197451784769108058161191238065
11

12
def convert_to_base(n, b):
13
    if n < 2:
14
        return [n]
15

16
    temp = n
17
    ans = []
18

19
    while temp != 0:
20
        ans = [temp % b] + ans
21
        temp //= b
22

23
    return ans
24

25

26
def cipolla(n, p):
27
    n %= p
28

29
    if n == 0 or n == 1:
30
        return [n, (p - n) % p]
31

32
    phi = p - 1
33

34
    if pow(n, phi // 2, p) != 1:
35
        return []
36

37
    if p % 4 == 3:
38
        ans = int(pow(n, (p + 1) // 4, p))
39
        return [ans, (p - ans) % p]
40

41
    aa = 0
42
    for i in range(1, p):
43
        temp = pow(((i * i - n) % p), phi // 2, p)
44

45
        if temp == phi:
46
            aa = i
47
            break
48

49
    exponent = convert_to_base((p + 1) // 2, 2)
50

51
    def cipolla_mult(ab, cd, w, p):
52
        a, b = ab
53
        c, d = cd
54
        return (a * c + b * d * w) % p, (a * d + b * c) % p
55

56
    x1 = (aa, 1)
57
    x2 = cipolla_mult(x1, x1, aa * aa - n, p)
58

59
    for i in range(1, len(exponent)):
60
        if exponent[i] == 0:
61
            x2 = cipolla_mult(x2, x1, aa * aa - n, p)
62
            x1 = cipolla_mult(x1, x1, aa * aa - n, p)
63
        else:
64
            x1 = cipolla_mult(x1, x2, aa * aa - n, p)
65
            x2 = cipolla_mult(x2, x2, aa * aa - n, p)
66
    return [x1[0], (p - x1[0]) % p]
67

68
y12=(r1**3+a*r1+b)%p
69
print(cipolla(y12, p))
70

71
# sage
72

73
E = EllipticCurve(GF(p),[a,b])
74
G = E(602046282375688656758213480587526111916698976636884684818,174050332293622031404857552280219410364023488927386650641)
75
p1 = E(6052579169727414254054653383715281797417510994285530927615, 5871535981004787479780408408652175440419840647034147933664)
76
a,b,w,X=751818 ,1155982, 908970521, 20391992
77

78
z=p1+(-w)*G+(-a)*X*p1+(-b)*X*G
79
#z = (k1 - w * t) * G + (-a * k1 - b) * Y
80
print(z)
81

82
zx=2879837810202640866238433125146194557887945787271835955457
83
k2 = int(hashlib.sha1(str(zx).encode()).hexdigest(), 16)
84
print(k2)
85

86
p = k2
87
for i in range(99):
88
    p = gmpy2.next_prime(p)
89
q = gmpy2.next_prime(p)
90
print(p,q)
91

92

93
#
94

95
p=1370020847323284147745373471297398364094203631317
96
q=1370020847323284147745373471297398364094203631323
97

98
phi=(p-1)*(q-1)
99
d=inverse(65537, phi)
100
n=p*q
101
c=1294716523385880392710224476578009870292343123062352402869702505110652244504101007338338248714943
102

103
for i in range(2**16):
104
    if b'flag' in long_to_bytes(pow(c,d, p*q)+n*i):
105
        print(long_to_bytes(pow(c,d, p*q)+n*i))

这个方法绕过了k1直接去求k2
还有一个求k1的方法，貌似更简单，用大步小步算法去求解 exp

1
from ecdsa.ecdsa import *
2
import libnum
3
import re
4
import gmpy2
5
from Crypto.Util.number import *
6

7
def BSGS(G, P, x1, x2):
8
    m = ceil(sqrt(x2 - x1))
9
    baby_steps = {}
10
    current_step = G
11
    for j in trange(m):
12
        k_j = x1 + j
13
        baby_steps[current_step] = k_j
14
        current_step += G
15

16
    mP = m * G
17
    S = P
18
    for i in trange(m):
19
        if S in baby_steps:
20
            return baby_steps[S] + i * m
21
        S -= mP
22

23
    return None
24

25
# BSGS(G, P, round(2**48.9), round(2**49))
26

27
_p = 6277101735386680763835789423207666416083908700390324961279
28
def remove_whitespace(text):
29
    """Removes all whitespace from passed in string"""
30
    return re.sub(r"\s+", "", text, flags=re.UNICODE)
31
_b = int(
32
    remove_whitespace(
33
        """
34
    64210519 E59C80E7 0FA7E9AB 72243049 FEB8DEEC C146B9B1"""
35
    ),
36
    16,
37
)
38
E = EllipticCurve(GF(_p),[-3, _b])
39

40
G = generator_192
41

42
r1 = 6052579169727414254054653383715281797417510994285530927615
43
a = -3
44
Py = r1^3 + a * r1 + _b
45
Py = sqrt(Mod(Py, _p))
46
P = E(r1,Py)
47

48
# k1 = optimized_bsgs_in_range(G,P,)
49

50
c = 1294716523385880392710224476578009870292343123062352402869702505110652244504101007338338248714943
51
a = 751818
52
b = 1155982
53
w = 908970521
54
X = 20391992
55

56
k1 = 432179965122662
57

58
t = 1
59
Y = X * G
60
n = G.order()
61
z = (k1 - w * t) * G + (-a * k1 - b) * Y
62
zx = z.x() % n
63
k2 = int(hashlib.sha1(str(zx).encode()).hexdigest(), 16)
64
p = k2
65
print(P.x())
66
print(P.y())
67
print(type(P))
68
for i in range(99):
69
    p = gmpy2.next_prime(p)
70
q = gmpy2.next_prime(p)
71
e = 65537
72
d = libnum.invmod(e,(p-1)*(q-1))
73
m = pow(c,d,p*q)
74
for i in range(2 ** 16):
75
    m += p*q
76
    flag = long_to_bytes(int(m))
77
    if b"flag" in flag:
78
        print(i)
79
        print(flag)
80
        break

总结

还是太菜了，还得练，害，有些东西没有接触过，就导致看代码如懂，写题很烦躁，继续努力加油吧！

a ctfer on the load

前言

题目

task

思路

总结