2023春秋杯冬季赛

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

2023春秋杯冬季赛————Crypto————Wp

赛时备战期末考，考完试复现复现

CF is Crypto Faker

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
from Crypto.Util.number import *
import initialize
import train
import valid
import test
import rec
from secret import message, flag_point

flag = b"flag{" + long_to_bytes(message) + long_to_bytes(flag_point) + b".}"

p = getPrime(512)
q = getPrime(512)
n = p * q
print("The significant parameter n: %s" % hex(n))
phi0 = (p - 1) * (q - 1)
r = rec.rec(p, q)
print("The unique parameter r: %s" % hex(r))

parameters = initialize.initialize(p, q)
wild_phi = parameters[0]
wild_e = parameters[1]
print("------")

print("Parameters are initialized to: \n  phi:%s\n" % hex(wild_phi), " e:%s" % hex(wild_e))
print("But they are wild and crazy!")
print("We have to give them a lesson!")
print("------")

parameters = train.train(wild_phi, wild_e, n, r, phi0)
trained_phi = parameters[0]
trained_e = parameters[1]
print("Parameters are trained to: \n  phi:%s\n" % hex(trained_phi), " e:%s" % hex(trained_e))
print("After training, the two naughty parameters are more and more normal.")
print("It's closer to your target!")
print("------")

parameters = valid.valid(trained_phi, trained_e, n)
y_valid = parameters[0]
print("The encrypted output in validation set is %s" % hex(y_valid))
print("After validation, the model is more and more stable.")
print("To test the real flag!")
print("------")

parameters = test.test(trained_phi, trained_e, n)
y_hat_cipher1 = parameters[0]
y_hat_cipher2 = parameters[1]
print("The final output is \n%s" % hex(y_hat_cipher1), "\n%s" % hex(y_hat_cipher2))
print("------")

initialize.py

1
2
3
4
5
6
7
8
9
10
def initialize(x, y):
    temp = []
    tip = 1
    for _ in range(2):
        if tip:
            temp.append(2023 + (x - 2023) * y - x)
            tip = 0
        else:
            temp.append(abs(x - y))
    return temp

rec.py

1
2
def rec(a, b):
    return (2023 * a + b) // a * b

train.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from secret import solvable_function


def train(x, y, u, v, phi):
    temp = []
    xx = solvable_function(x, u, v)
    loss = phi - xx
    print("The loss is %s" % hex(loss))
    x = xx + loss
    assert x == phi
    temp.append(x)
    noise = getPrime(8)
    while True:
        if y > noise:
            y = y - noise * 23
            noise = noise * 20
        else:
            break
    temp.append(y)
    return temp

test.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from secret import message, flag_point


def test(x, y, z):
    d = inverse(y, x)
    message = bytes_to_long(message)
    flag_point = bytes_to_long(flag_point)
    temp = []
    c1 = pow(message, y, z)
    c2 = pow(flag_point, y, z)
    assert message == pow(c1, d, z)
    assert flag_point == pow(c2, d, z)
    temp.append(c1)
    temp.append(c2)
    return temp

valid.py

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *


def valid(x, y, z):
    text = b'The algorithm of rsa is really a mystery in CTF.'
    temp = []
    d = inverse(y, x)
    text = bytes_to_long(text)
    cipher = pow(text, y, z)
    assert long_to_bytes(text) == long_to_bytes(pow(cipher, d, z))
    temp.append(cipher)
    return temp

output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
The significant parameter n: 0x81c5f040bfaea676120cd62c36ba7afb303561504bbf8609afa3da60fb6202ca875b0bd2a06143ebcd16fa615557ff159d97909160d68e1938b3ecaf57709b3d2698476b6dd203811b6a2ec6a6e2a7e213ab719bcd3ab49bb864b10e9c78ea3f501c0e2213dfe431043bb6f0cc2e8d77bfb43869b843af1a99ae81b87811e101
The unique parameter r: 0x4f37fe985d13ffde9867fa0063f68dea79196408b1404eadf03ea59297d629c2183a4a6a6647b6c4c99dd43bae8c4fa4691a608d20170fd42b18aef7efb3ae01cd3
------
Parameters are initialized to:
  phi:0x81c5f040bfaea676120cd62c36ba7afb303561504bbf8609afa3da60fb6202ca875b0bd2a06143ebcd16fa615557ff159d97909160d68e1938b3ecaf57709648d78eb17edb46dda768a97d57e6bd1c48657393b7c0d9c574c38cc0a3545ce7d209ade33b8ac6b31a41fe9f4ed62b4ddd7b99859b74915f2031dd2f5f0499a2f8
  e:0x2ebad696da6dda845bf03fdf34ee73d4849800de9267a5baa3c068e2d33a74727d00002fbfea775e5233087a9039d267130aa924a4f7fed3576f6ff7b8e1b2e8
But they are wild and crazy!
We have to give them a lesson!
------
The loss is -0x5144bdad7cc24f5348c5752dda0ff5fa7d72e36370d5af55eb6f590ac0764b843a06ee1a4651b8f3a6c878df56f1678454e58eaf0ede9a1eb0503dce6a1303b69e33bbaad112abb051a28d51a9fee629e89400a338bd02998568d044852f11e05572fc4a0ddacdf7342048295a4025394e77e973621a77ea5bbdb06af2cb72b2f8298e2cd16736454fd066d3d96a4f77cd094cd783ead17024de981df7ade84aa8c282b1ec6f8ec6ec4752727387ef637ba2a4eed8f83c77d5db14d297de8098
Parameters are trained to:
  phi:0x81c5f040bfaea676120cd62c36ba7afb303561504bbf8609afa3da60fb6202ca875b0bd2a06143ebcd16fa615557ff159d97909160d68e1938b3ecaf57709b3bb712fdcba325655f111918472d4353a66854ccda50b63a1047278c15a4b39cde898d054db87092958c7c05f8fa566dcd969b1ff4b7d1935c375a4af3bfc341b0
  e:0x2c22193ad9abcca2f67552fc76dd07b3ef883f3d755c95119cdf82bb6a07c970fd37e582bb49250d8efaa29b8a59c82059165c654206a9d7261f6b45a90dc69
After training, the two naughty parameters are more and more normal.
It's closer to your target!
------
The encrypted output in validation set is 0x775cbee546e7579f0a69645b59f72f5c8ff0c538dd9a6e755969dee2ffb8748073c089557801dfb8bfae15baba9a909f3addac142ad928ac7cc453c72166dda235128de12965df4308997416e054ab1ab9af55c60533c7374096aa2d05339900b3e14f7148930bf083eb1eb9fa22b9a997f85b39501d3a9bdfa08e3389b8f2fe
After validation, the model is more and more stable.
To test the real flag!
------
The final output is
0x29289e3d9275147b885b5061637564cbee3e4d9f48e52694e594f020e49da9b24d9246b2437fb2221fa86ca1a277f3fdd7ab5cad4738a02b66d47703ef816844a84c6c209c8251e8961c9ba2c791649e022627f86932d9700c3b1dc086e8b2747d0a5604955387a935464d3866dd4100b2f3d57603c728761d1d8ef7fdbdcbee
0x2b0059f88454e0e36269c809b5d5b6b28e5bab3c87b20f9e55635239331100a0a582241e7a385034698b61ebf24b519e868617ff67974cc907cc61be38755737f9a6dbeb7890ff55550b1af1ecf635112fcaaa8b07a3972b3c6728cbcf2a3973a4d7bd92affec7e065e0ae83cd36858e6d983785a3668a8b82709d78a69796af
------

仔细阅读题目会发现，$e,\phi(n),n$都已给出，求个d就可以正常解RSA了

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
from Crypto.Util.number import *

train_phi = 0x81c5f040bfaea676120cd62c36ba7afb303561504bbf8609afa3da60fb6202ca875b0bd2a06143ebcd16fa615557ff159d97909160d68e1938b3ecaf57709b3bb712fdcba325655f111918472d4353a66854ccda50b63a1047278c15a4b39cde898d054db87092958c7c05f8fa566dcd969b1ff4b7d1935c375a4af3bfc341b0
train_e = 0x2c22193ad9abcca2f67552fc76dd07b3ef883f3d755c95119cdf82bb6a07c970fd37e582bb49250d8efaa29b8a59c82059165c654206a9d7261f6b45a90dc69
cipher1 = 0x29289e3d9275147b885b5061637564cbee3e4d9f48e52694e594f020e49da9b24d9246b2437fb2221fa86ca1a277f3fdd7ab5cad4738a02b66d47703ef816844a84c6c209c8251e8961c9ba2c791649e022627f86932d9700c3b1dc086e8b2747d0a5604955387a935464d3866dd4100b2f3d57603c728761d1d8ef7fdbdcbee
cipher2 = 0x2b0059f88454e0e36269c809b5d5b6b28e5bab3c87b20f9e55635239331100a0a582241e7a385034698b61ebf24b519e868617ff67974cc907cc61be38755737f9a6dbeb7890ff55550b1af1ecf635112fcaaa8b07a3972b3c6728cbcf2a3973a4d7bd92affec7e065e0ae83cd36858e6d983785a3668a8b82709d78a69796af
n = 0x81c5f040bfaea676120cd62c36ba7afb303561504bbf8609afa3da60fb6202ca875b0bd2a06143ebcd16fa615557ff159d97909160d68e1938b3ecaf57709b3d2698476b6dd203811b6a2ec6a6e2a7e213ab719bcd3ab49bb864b10e9c78ea3f501c0e2213dfe431043bb6f0cc2e8d77bfb43869b843af1a99ae81b87811e101

d = gmpy2.invert(train_e,train_phi)

m1 = pow(cipher1,d,n)
m2 = pow(cipher2,d,n)
flag1 = long_to_bytes(m1)
flag2 = long_to_bytes(m2)
print(flag1 + flag2)
# With the method of machine learning, it is available for Crypto-er to develop the modern cryptography.Don't give up learning crypto

not winner

考点：boneh and durfee DSA线性k

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
from Crypto.Util.number import *
from gmpy2 import *
import random, os
from hashlib import sha1
from random import randrange
flag=b''
x = bytes_to_long(flag)

def gen_key():
    while True:
        q = getPrime(160)
        p = 2 * getPrime(1024-160) * q+1
        if isPrime(p):
            break
    h = random.randint(1, p - 1)
    g = powmod(h,(p-1)//q, p)
    y=pow(g,x,p)
    return p,q,g,y

def cry():
    a =
    p = getPrime(512)
    q = getPrime(512)
    d = getPrime(280)
    n = p * q
    e = inverse(d, (p - 1) * (q - 1))
    c = pow(a, e, n)
    return n,e,c

p,q,g,y=gen_key()

k1 = random.randint(1, q-1)
h1 = bytes_to_long(sha1(os.urandom(20)).digest())
r1 = pow(g, k1, p) % q
s1 = ((h1 + x*r1) * invert(k1, q))% q

n,e,c= cry()

a=
b= 17474742587088593627
k2 = a*k1 + b
h2 = bytes_to_long(sha1(os.urandom(20)).digest())
r2 = pow(g, k2, p) % q
s2 = ((h2 + x*r2) * invert(k2, q)) % q
print(n,e,c)
print(p,q,g,y)
print("h1:%s r1:%s s1:%s"%(h1,r1,s1))
print("h2:%s r2:%s s2:%s"%(h2,r2,s2))

注意到a用RSA加密了，而且$\frac{d}{n} \approx 0.2734$，超过winner的适用范围($\frac{1}{3}N^{0.25}$)，用boneh and durfee随便调调参数即可得到

$d = 1493519932573300884636712093929290985070801830526216141153447882450934993737739146621$

接下来是DSA

已知
$$
r_1 \equiv (g^{k_1}\mod p) \mod q
$$

$$
s_1 \equiv k_1^{-1}(h_1 + xr_1) \mod q
$$

$$
r_2 \equiv (g^{k_2} \mod p) \equiv (g^{ak_1+b} \mod p)\mod q
$$

$$
s_2 \equiv k_2^{-1}(h_2+xr_2)\equiv (ak_1+b)^{-1}(h_2+xr_2) \mod q
$$

由$\quad s_1\equiv k_1^{-1}(h_1+xr_1) \mod q$

可得$\quad s_1k_1 \equiv (h_1 + xr_1) \mod q$

同理$\quad s_2 \equiv (ak_1+b)^{-1}(h_2+xr_2) \mod q$

可得$\quad s_2(ak_1+b) \equiv (h_2+xr_2) \mod q$

上一个式子乘上$r_2$，下一个式子乘上$r_1$即可将x消去，得到
$$
r_2(s_1k_1-h_1) \equiv r_1(s_2ak_1 +s_2b-h_2) \mod q
$$
再化简得到
$$
k_1(r_2s_1-r_1s_2a) \equiv r_1(s_2b-h_2)+r_2h_1 \mod q
$$
至此可以求出$k_1 \equiv (r_2s_1-r_1s_2a)^{-1}(r_1(s_2b-h_2)+r_2h_1) \mod q$

$x \equiv (k_1s_1 -h_1)r_1^{-1} \mod 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
from Crypto.Util.number import *
import gmpy2

n = 98871082998654651904594468693622517613869880791884929588100914778964766348914919202255397776583412976785216592924335179128220634848871563960167726280836726035489482233158897362166942091133366827965811201438682117312550600943385153640907629347663140487841016782054145413246763816202055243693289693996466579973
e = 76794907644383980853714814867502708655721653834095293468287239735547303515225813724998992623067007382800348003887194379223500764768679311862929538017193078946067634221782978912767213553254272722105803768005680182504500278005295062173004098796746439445343896868825218704046110925243884449608326413259156482881
c = 13847199761503953970544410090850216804358289955503229676987212195445226107828814170983735135692611175621170777484117542057117607579344112008580933900051471041224296342157618857321522682033260246480258856376097987259016643294843196752685340912823459403703609796624411954082410762846356541101561523204985391564
d = 1493519932573300884636712093929290985070801830526216141153447882450934993737739146621
a = pow(c,d,n)
print(f"a = {a}")

p = 161310487790785086482919800040790794252181955976860261806376528825054571226885460699399582301663712128659872558133023114896223014064381772944582265101778076462675402208451386747128794418362648706087358197370036248544508513485401475977401111270352593919906650855268709958151310928767086591887892397722958234379
q = 1115861146902610160756777713087325311747309309771
g = 61073566757714587321114447684333928353300944355112378054603585955730395524359123615359185275743626350773632555967063692889668342544616165017003197599818881844811647270423070958521148291118914198811187731689123176313367399492561288350530256722898205674043032421874788802819858438796795768177550638273020791962
y = 23678147495254433946472657196764372220306841739888385605070426528738230369489739339976134564575544246606937803367113623097260181789372915552172469427842482448570540429192377881186772226796452797182435452490307834205012154495575570994963829345053331967442452842152258650027916313982835119514473311305158299360
(h1, r1, s1) = 535874494834828755542711401117152397489711233142, 117859946800380767356190121030392492081340616512, 26966646740134065096660259687229179143947213779
(h2, r2, s2) = 236574518096866758760287021848258048065293279716, 863199000523521111517835459866422731857447792677, 517924607931342012033031470185302567344725962419
b = 17474742587088593627

temp1 = r2*s1 - r1*s2*a
temp2 = r1*(s2*b - h2) + r2*h1

k1 = gmpy2.invert(temp1,q) * temp2
m = ((k1*s1 - h1)*gmpy2.invert(r1,q)) % q
print(long_to_bytes(m))
# l1near_k1s_unsafe
-------------已经到底啦！-------------