2023蓝帽杯

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 1.5k 阅读时长 ≈ 6 分钟

蓝帽杯2023——Crypto

初赛

DHRSA

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
# sage
from sage.all import *
from Crypto.Util.number import getPrime,getStrongPrime, isPrime, bytes_to_long
from secret import r,g
from secret import flag

assert r.bit_length() == 512 and isPrime(r)
FLAG = bytes_to_long(flag)

def gen_DH_key(g,r):
    x = randint(2,r-1)
    return x, pow(g,x,r)

def gen_RSA_parameters(g,r):
    main_key = gen_DH_key(g,r)
    sub_key = gen_DH_key(g,r)
    x, X = main_key
    w, W = sub_key
    print(f"[+] Public DH Keys { X = }")
    print(f"[+] Public DH Keys { W = }")
    while True:
        c, C = gen_DH_key(g,r)
        t1 = randint(0,1)
        t2 = randint(0,1)
        p = ZZ(C * W^t1 * pow(X, c, r) % r)
        if not is_prime(p):
            continue
        q = ZZ(pow(W, -t2, r) * pow(X, -c, r) % r)
        if not is_prime(q):
            print(f"[+] Try {c ,C}")
            continue
        return p,q
    
p, q = gen_RSA_parameters(g,r)
n = p*q
e = 65537
c = pow(FLAG,e,n)
print(f"{ c = }")
print(f"{ n = }")

$p = C \times W^{t_1} \times (X^c \mod r),q = (W^{-t_2} \mod r)\times (X^{-c} \mod r) \mod r$

因为$t_1,t_2$只取0或1

列出所有情况

①：当$t_1 = t_2 = 0$时，$p = C \times (X^c \mod r) \mod r \times (X^{-c} \mod r) \mod r$

则$n = C \mod r$

②：当$t_1 = 1,t_2 = 0$时，$p = C \times W \times (X^c \mod r) \mod r,q = X^{-c} \mod r$

则$n = CW \mod r$

③：当$t_1 = 0,t_2 = 1$时，$p = C\times(X^c \mod r) \mod r$，$q = (W^{-1}\mod r) \times(X^{-c}\mod r)\mod r$

则$n = CW^{-1} \mod r$

④：当$t_1=t_2 = 1$时，$p = C \times W \times(X^c \mod r),q = (W^{-1} \mod r)\times(X^{-c}\mod r)\mod r$

则$n = C \mod r$

四种情况都需要知道$r$

题目给出很多$C_i \equiv g^{c_1} \mod r$

如果存在一组$a_1,a_2,\dots ,a_n$，使得$a_1c_1 + \dots + a_nc_n=0$

则有$\prod_{i=1}^nC_i^{a_i} = g^{\sum_{i=1}^na_ic_i} = g^0 \equiv 1 \mod r$

找到两组这样的$a_1,a_2,\dots ,a_n$

构造格
$$
\begin{pmatrix}
1 & 0 & \dots & 0 & Kc_1 \
0 & 1 & \dots & 0 & Kc_2 \
\vdots & \vdots & \ddots & \vdots & \vdots\
0 & 0 & \dots & 1 & kc_n
\end{pmatrix}
$$
乘上K为了让规约的可能性更大

规约后得到$\vec{c} = (a_1,a_2,\dots,a_n,0)$

求得$r$之后，共模攻击求$g$

尝试4种情况，求出最后构造$p,q$的$C_ = n$或$C_ = nW \mod n$或$C_ \equiv nW^{-1} \mod r$

再求出$g^{c_} \equiv C_ \mod r$

求出$c_$即可恢复$p,q$

exp:

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
import gmpy2
from Crypto.Util.number import *

cs = [...]
es = [...]

n = len(es)
t = 2^5

L = Matrix.identity(n)

last_col = [i*2^5 for i in es]

L_last_col = Matrix(ZZ,len(last_col),1,last_col)
L = L.augment(L_last_col)

L = L.LLL()
May = []
for i in L:
    if i[-1] == 0:
        May.append(i) #几个符合条件的向量

R = []
for i in range(len(May)):
    for j in range(len(May)):
        if i != j:
            xx = product([ZZ(y) ^ x for x, y in zip(May[i][: -1], cs)])
            yy = product([ZZ(y) ^ x for x, y in zip(May[j][: -1], cs)])
            r = gcd(xx.numer() - xx.denom(), yy.numer() - yy.denom())
            if r not in R:
                R.append(r) #求出可能的r值
# print(R)
# 检验后知道r
r = 10667924450645948100608927157603781268991945924055943816082403476371801785989561454936076097627912279097114498936308342036099904242687703932444772733243819
# 共模攻击求g
for i in range(len(cs)):
    for j in range(len(cs)):
        if i != j:
            c1 = cs[i]
            c2 = cs[j]
            e1 = es[i]
            e2 = es[j]
            try:
                t = gmpy2.gcd(e1,e2)
                if t == 1:
                    s,x,y = gmpy2.gcdext(e1,e2)
                    g = (pow(c1,x,r)*pow(c2,y,r))%r
                    for k in range(len(es)):
                        if pow(g,es[i],r) == cs[i]: #检验g是否正确
                            print(g)
                            break
            except:
                continue
# 检验后求得g
g =6019887080267290264230260653584196278384320835640816590398803560025633855808434001764263669714920086295176455397726166743099512294951861972283858355052731
X =197551296081022143608034360606381334253374533627365455002683616928330857539205836504075700389569213696043700490195977045586318090211726350917451410932216
W =10625560347436147537644301075885059900758953251551866239435327407977591190018531918316486861730777808988185029637608372445416280896280058313924537678128258
c =61040814411609979711931510878805548760848686739454567580358315369154260598969544907138563610735920809370306294050956464828615417082277087799410050319871691154003766481799397897519555113273982347768485719165972634089532894585256662433949694618032747408071953491187718726218120284389638124624152241321006634774
n =66022752859576751705544115674843820574619778139841743306742674741819040147745776264697779394213058328572691946505564202779552568613562176486470653760142864852745249430164256770469301179840812051842363261404790355057115296671805975126795017665392798621718740402876024901551851638786170466127104615340863081593
C_ = n * W % r
c_ = discrete_log(mod(C_,r),mod(g,r))
print(c_)
print(pow(g,c_,r) == C_) #检查c_是不是正确
c_ =9459072654036531380057822508623309360299476015001753632088039036432789857424193280036533227566474452833834253934061279659663650834198718093112487222065271
p = ZZ(C_ * W^0 * pow(X, c_, r) % r)
q = ZZ(pow(W, -1, r) * pow(X, -c_, r) % r)
print(p)
print(q)
n =66022752859576751705544115674843820574619778139841743306742674741819040147745776264697779394213058328572691946505564202779552568613562176486470653760142864852745249430164256770469301179840812051842363261404790355057115296671805975126795017665392798621718740402876024901551851638786170466127104615340863081593
phi = (p-1)*(q-1)
d = gmpy2.invert(65537,phi)
m = pow(c,d,n)
print(long_to_bytes(int(m)))

半决

ezrsa

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy
from Crypto.Util.number import bytes_to_long
from fractions import Fraction

flag = "***"

assert gmpy.is_prime(p) * gmpy.is_prime(q) > 0
assert Fraction(p, p + 1) + Fraction(q + 1, q) == Fraction(2 * s - X, s + Y)
print('p / (p + 1) + (q + 1) / q) == (2 * s - %s) / (s + %s)' % (X, Y))

n = p * q
c = pow(bytes_to_long(bytes(flag, "utf-8")), 0x10001, n)
print('n =', n)
print('c =', c)

$\because \frac{p}{p+1}+\frac{q+1}{q} = \frac{2n+p+q+1}{n+q} = \frac{2s-X}{s+Y}$

假设$n+q = s+Y$，$2n+p+q+1 = 2s-X$

再联立$n = p\times q$

三个方程

①：$n+q = s+Y$

②：$2n+p+q+1 = 2s-X$

③：$n = p\times q$

解3个未知量

exp:

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
#sage
from Crypto.Util.number import *
import gmpy2

X = 153801856029563198525204130558738800846256680799373350925981555360388985602786501362501554433635610131437376183630577217917787342621398264625389914280509
Y = 8086061902465799210233863613232941060876437002894022994953293934963170056653232109405937694010696299303888742108631749969054117542816358078039478109426
n = 161010103536746712075112156042553283066813155993777943981946663919051986586388748662616958741697621238654724628406094469789970509959159343108847331259823125490271091357244742345403096394500947202321339572876147277506789731024810289354756781901338337411136794489136638411531539112369520980466458615878975406339
e = 65537
c = 15380535750650959213679345560658190067564859611922563753882617419201718847747207949211621591882732604480600745000879508274349808435529637573773711729853565120321608048340424321537282281161623712479117497156437792084977778826238039385697230676340978078264209760724043776058017336241110097549146883806481148999

var('p')
var('q')
var('s')
f1 = n+q - s - Y
f2 = 2*n+p+q+1-2*s+X
f3 = p*q-n

# ans = solve([f1,f2,f3],[p,q,s])
# print(ans)

p = 12604273285023995463340817959574344558787108098986028639834181397979984443923512555395852711753996829630650627741178073792454428457548575860120924352450409
# print(isPrime(p))
# print(p.bit_length())
q = n // p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(int(m)))

Dual ECDSA——不会

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
from sage.all import *
from hashlib import sha256
from Crypto.Util.number import long_to_bytes, bytes_to_long
from math import ceil
from random import randint

# safe curve parameters
# NIST P-256
NIST_256 = (
    NIST_256_P := 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff,
    NIST_256_K := GF(NIST_256_P),
    NIST_256_A := NIST_256_K(0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc),
    NIST_256_B := NIST_256_K(0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b),
    NIST_256_CURVE := EllipticCurve(NIST_256_K, (NIST_256_A, NIST_256_B)),
    NIST_256_GEN := NIST_256_CURVE(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5),
    NIST_256_ORDER := 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 * 0x1
)
NIST_256_CURVE.set_order(NIST_256_ORDER)

# NIST P-521
NIST_521 = (
    NIST_521_P := 0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff,
    NIST_521_K := GF(NIST_521_P),
    NIST_521_A := NIST_521_K(0x01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc),
    NIST_521_B := NIST_521_K(0x0051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00),
    NIST_521_CURVE := EllipticCurve(NIST_521_K, (NIST_521_A, NIST_521_B)),
    NIST_521_GEN := NIST_521_CURVE(0x00c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66, 0x011839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650),
    NIST_521_ORDER := 0x01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409 * 0x1
)
NIST_521_CURVE.set_order(NIST_521_ORDER)

FLAG = open("./flag", "rb").read()
assert len(FLAG) == 64


class Dual_EC():

    def __init__(self, state=None, defaul_curve=True) -> None:
        if state == None:
            self.state = randint(1, 2**256)
        else:
            self.state = state
        if defaul_curve:
            self.init_curve(None)

    def init_curve(self, paras: tuple or list) -> None:
        if paras == None:
            self.Curve = NIST_256_CURVE
            # replace the generator
            self.g = NIST_256_GEN * self.state
            self.curve_order = NIST_256_ORDER
            self.P = randint(1, 2**20) * self.g
            self.Q = randint(1, 2**20) * self.g
        # customized curve
        else:
            Curve, P, Q = paras
            if not Curve.is_on_curve(P) or not Curve.is_on_curve(Q):
                raise ValueError("Points are not on the curve")
            self.Curve = Curve
            self.g = Curve.gen(0)
            self.P = P
            self.Q = Q

    def _update(self):
        self.state = int((self.state * self.P).xy()[0])

    def round(self) -> None:
        # extract the high 240 bits
        out = int((self.state * self.Q).xy()[0]) >> 16
        self._update()
        return out

    def random_bytes(self, n: int) -> int:
        rounds = ceil(n*8/240)
        out = 0
        for _ in range(rounds):
            out = (out << 240) + self.round()
        return long_to_bytes(out >> (rounds*240 - n*8), n)

    def random_bit_integer(self, n: int) -> int:
        rounds = ceil(n/240)
        out = 0
        for _ in range(rounds):
            out = (out << 240) + self.round()
        return out >> (rounds*240 - n)


class ECDSA():
 
    def __init__(self) -> None:
        self.prng = Dual_EC()
        self.hashfunc = sha256
        self.curve_bits = 521
        self.curve = NIST_521_CURVE
        self.generator = NIST_521_GEN
        self.order = NIST_521_ORDER
        self.pri_key = self.prng.random_bit_integer(self.curve_bits)
        self.pub_key = self.pri_key * self.generator

    def set_curve(self, curve: EllipticCurve) -> None:
        self.curve = curve
        self.generator = curve.gen(0)
        self.order = curve.order()
        self.curve_bits = self.order.nbits()

    def set_pri_key(self, d: int) -> None:
        self.pri_key = d
        self.pub_key = d * self.generator

    def sign(self, msg: bytes) -> tuple:
        k_bytes = self.prng.random_bytes(self.curve_bits//8)
        k = int(self.hashfunc(k_bytes).hexdigest(), 16)
        P = k * self.generator
        r = int(P.xy()[0])
        k_inv = int(inverse_mod(k, self.order))
        e = int(self.hashfunc(msg).hexdigest(), 16)
        s = (e + self.pri_key*r) * k_inv % self.order
        return (r, s)

    def verify(self, msg: bytes, signature: tuple) -> bool:
        r, s = signature
        if not (0 < r < self.order and 0 < s < self.order):
            return False
        e = int(self.hashfunc(msg).hexdigest(), 16)
        w = int(inverse_mod(s, self.order))
        u1 = e * w % self.order
        u2 = r * w % self.order
        P = u1 * self.generator + u2 * self.pub_key
        return int(r) == int(P.xy()[0])

    def embed_secret(self, msg: bytes) -> tuple:
        S = self.curve.lift_x(ZZ(bytes_to_long(msg)))
        K = self.prng.random_bit_integer(self.curve_bits)
        return K * S


if __name__ == "__main__":
    SIGNER = ECDSA()

    sig1 = SIGNER.sign(b"AN INFAMOUS PRNG NAMED DUAL_EC BACKDOORED BY NSA, FINALLY CONFIRMED BY SNOWDEN IN 2013.")
    sig2 = SIGNER.sign(b"NO ONE CAN EXTRACT THE BACKDOOR! UNLESS YOU CAN BREAK THE ECDSA SIGNATURE SCHEME / ECDLP!")
    emb_flag = SIGNER.embed_secret(FLAG)

    print(f"pub_key = {SIGNER.pub_key.xy() }")
    print(f"P = {SIGNER.prng.P.xy() }")
    print(f"Q = {SIGNER.prng.Q.xy() }")
    print(f"{sig1 = }")
    print(f"{sig2 = }")
    print(f"emb_flag = {emb_flag.xy() }")
-------------已经到底啦！-------------