BeginCTF

发表于 分类于 阅读次数： Waline： 本文字数： 2k 阅读时长 ≈ 7 分钟

2024BeginCTF——Crypto——部分题解

fake_n

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

def fakeN_list():
    puzzle_list = []

    for i in range(15):
        r = getPrime(32)
        puzzle_list.append(r)

    p = getPrime(32)
    q = getPrime(32)
    com = p*q

    puzzle_list.append(com)

    return puzzle_list

def encrypt(m,e,fake_n_list):

    fake_n = 1
    for i in range(len(fake_n_list)):
        fake_n *= fake_n_list[i]

    really_n = 1
    for i in range(len(fake_n_list)-1):
        really_n *= fake_n_list[i]

    c = pow(m,e,really_n)

    print("c =",c)
    print("fake_n =",fake_n)

if __name__ == '__main__':
    m = bytes_to_long(flag)
    e = 65537
    fake_n_list = fakeN_list()
    encrypt(m,e,fake_n_list)

'''
c = 6451324417011540096371899193595274967584961629958072589442231753539333785715373417620914700292158431998640787575661170945478654203892533418902
fake_n = 178981104694777551556050210788105224912858808489844293395656882292972328450647023459180992923023126555636398409062602947287270007964052060975137318172446309766581
'''

加密用的n是15个素数之积，给的n是17个素数之积

不知道是哪15个，爆破一下即可

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

c = 6451324417011540096371899193595274967584961629958072589442231753539333785715373417620914700292158431998640787575661170945478654203892533418902
n = 178981104694777551556050210788105224912858808489844293395656882292972328450647023459180992923023126555636398409062602947287270007964052060975137318172446309766581
phi = 1
e = 65537
primes = []
for i in factor(n):
    primes.append(i[0])
for i in trange(len(primes)):
    print(f"i={i}")
    for j in range(1,len(primes)):
        if i!=j:
            really_n = n // (primes[i]*primes[j])
            phi = euler_phi(really_n)
            d = gmpy2.invert(e,phi)
            m = pow(c,d,really_n)
            flag = long_to_bytes(int(m))
            if b"begin" in flag:
                print(flag)
                break
                # begin{y0u_f1nd_th3_re4l_n}

Hard_ECC

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from flag import flag

A = [0,
     3,
     0,
     973467756888603754244984534697613606855346504624,
     864199516181393560796053875706729531134503137794]
p = 992366950031561379255380016673152446250935173367
ec = EllipticCurve(GF(p), [A[0], A[1], A[2], A[3], A[4]])
T = ec.random_point()
secret = int.from_bytes(flag, 'little')
Q = T * secret
print(T, Q)
# (295622334572794306408950267006569138184895225554 : 739097242015870070426694048559637981600496920065 : 1)
# (282367703408904350779510132139045982196580800466 : 411950462764902930006129702137150443195710071159 : 1)

解$Q = secret \times T$

exp:

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

A = [0,
     3,
     0,
     973467756888603754244984534697613606855346504624,
     864199516181393560796053875706729531134503137794]
p = 992366950031561379255380016673152446250935173367
ec = EllipticCurve(GF(p), [A[0], A[1], A[2], A[3], A[4]])

T = ec(295622334572794306408950267006569138184895225554,739097242015870070426694048559637981600496920065)
Q = ec(282367703408904350779510132139045982196580800466,411950462764902930006129702137150443195710071159)
m = T.discrete_log(Q)
print(long_to_bytes(int(m)))
# }?drah_si_ti{nigeb
# begin{it_is_hard?}

PAD

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
import random, math

from Crypto.Util.number import *
from flag import flag
flag=flag[:64]
assert len(flag) == 64

class RSA():
    def __init__(self, m: int):
        self.p, self.q, self.e, self.m = getPrime(512), getPrime(512), getRandomRange(1,8), m
        self.n = self.p * self.q
    def Publickey(self):
        return (self.n, self.e,self.c)
    def Encrypt(self):
        pad = PAD(m=self.m, e=0)
        pad.PAD()
        self.c = (pad.e,pow(pad.M, self.e, self.n))
class PAD():
    def __init__(self, m: int, e):
        self.e, self.m, self.mbits = e, m, m.bit_length()
        if e == 0:
            self.e = getRandomRange(2, 7)
    def PAD(self):
        self.M = pow(self.e, self.mbits) + pow(self.m, self.e)
GIFT = bytes_to_long(flag)
with open("GIFT.txt", "w") as f:
    for i in range(40):
        rsa = RSA(m=GIFT)
        rsa.Encrypt()
        f.write(str(rsa.Publickey()) + "\n")

flag长度为64，先默认m.bit_length() = 512

记pad_e为$e_1$，加密用的e为$e_2$

从题意可以知道 $c \equiv (e_1^{512}+m^{e_1})^{e_2} \mod n$

因为$e_2$取值从1~8

当$e_1 = 2,e_2 = 1$这个特殊值的时候，有 $c \equiv (2^{512} + m^2) \mod n$

$m^2 \equiv (c - 2^{512}) \mod n$

开根号即可

exp

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

(n,e,(pad_e,c)) = (105489743033600776618404736924014082773234739025040235918547880079849719971737127359304073614094075884043630513694448370483208184306027684643273284267932051217742004175757404293643624264846421545917186078199365762796141089940330731024030929168374696605389962930325106070659194496163327222019090112724836643593, 1, (2, 26557762379124264922132214420209728936796452559751033517820166259647971200493029434772959145551662395540203237914969022639479368547265045300822940244603592956901947131088363115332681941180989239355596363143445708865429254462912210194997411474244175252940834791770566886483490068164580622099300335891131365129))

temp = (c - pow(pad_e,512)) % n
m = gmpy2.iroot(temp,2)[0]
print(long_to_bytes(m))
# begin{8E6C79D2-E960-C57A-F3E4-A52BC827ED6B_Dragon_Year_happy!!!}

PAD_revenge

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

assert len(flag) == 64

class RSA():
    def __init__(self, m: int):
        self.p, self.q, self.e, self.m = getPrime(256), getPrime(256), getRandomRange(1,9), m
        self.n = self.p * self.q
    def Publickey(self):
        return (self.n, self.e,self.c)
    def Encrypt(self):
        pad = PAD(m=self.m, e=0)
        pad.PAD()
        self.c = (pad.e,pow(pad.M, self.e, self.n))
class PAD():
    def __init__(self, m: int, e):
        self.e, self.m, self.mbits = e, m, m.bit_length()
        if e == 0:
            self.e = getRandomRange(1, 9)
    def PAD(self):
        self.M = pow(self.e, self.mbits) + pow(self.m, self.e)
GIFT = bytes_to_long(flag)

with open("GIFT.txt", "w") as f:
    for i in range(100):
        rsa = RSA(m=GIFT)
        rsa.Encrypt()
        data=rsa.Publickey()
        if data[1]*data[2][0]<=2:
            continue
        f.write(str(data) + "\n")

和上题的区别在于，n变小了，且避免上面一题的非预期

但这题还是存在非预期的情况

非预期

还是

根据$c \equiv (e_1^{512}+m^{e_1})^{e_2} \mod n$

取3组$e_1 = 3,e_2 = 1$的数据
$$
c_1 \equiv (3^{512}+m^3) \mod n_1
$$

$$
c_2 \equiv (3^{512}+m^3) \mod n_2
$$

$$
c_3 \equiv (3^{512}+m^3) \mod n_3
$$

用中国剩余定理把它弄成一个$C \equiv (3^{512} + m^3) \mod N$

再对C开3次方即可

exp:

1
2
3
4
5
6
7
8
9
10
11
# sage
import gmpy2

(n0,e,(e0,c0)) =  (4205338792881421548510609645647062608905484696099258750943039118994520455106270839395319116980996505132271552239717225130972438536887110724158402296232289, 1, (3, 590242556810530557883636062945321456666605165279521102134969558150863508014273375308372904949297413593224978273122299933502842450872249868557340596692448))
(n1,e,(e1,c1)) =  (7050174313884434729593139368893291621548368062755985279847850232740992709140864927641348128276777490337461431355020263819014375471971053422267553276559149, 1, (3, 2893746834891731849952475353675823291920101887211621827992533553019484178344684430992593454765874180526901317935813716254980891868014768672217101779002964))
(n2,e,(e2,c2)) =  (7695312868320303154724182556869744062740975850081486948529306458791551745279043014584922518803724721857725624240269226703220670466322322864253572576548333, 1, (3, 4853546005581242275031566639028865993927807758919394191424484984623935750674499388240409403735193793296025751636464209778684176500380928091202873126090673))

C = CRT_list([c0,c1,c2],[n0,n1,n2])
N = n0*n1*n2
m = gmpy2.iroot(C,3)[0]
print(bytes.fromhex(hex(int(m))[2:]))

预期

exp

找几组合适的数据，再用Hastad’s Attack

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

mbits=79*8+7
with open("output.txt","r") as f:
    data=[eval(i) for i in f.readlines()]

for k in range(2,20):
    n,e,c=[],[],[]
    for i in range(len(data)):
        if data[i][1]*data[i][2][0]==k:
            n.append(data[i][0])
            e.append((data[i][1],data[i][2][0]))
            c.append(data[i][2][1])
    if len(c)>=7:
        break

# print(n)
# print(e)
# print(c)

bit = 511
N = prod(n)
temp = [[1 if i == j else 0 for i in range(len(e))] for j in range(len(e))]
T = [CRT_list(temp[i],n) for i in range(len(e))]
pad = [pow(e[i][-1],bit) for i in range(len(e))]

R.<x> = PolynomialRing(Zmod(N))
f0 = (pad[0] + x^e[0][1])^e[0][0] - c[0]
f1 = (pad[1] + x^e[1][1])^e[1][0] - c[1]
f2 = (pad[2] + x^e[2][1])^e[2][0] - c[2]
f3 = (pad[3] + x^e[3][1])^e[3][0] - c[3]
f4 = (pad[4] + x^e[4][1])^e[4][0] - c[4]
f5 = (pad[5] + x^e[5][1])^e[5][0] - c[5]
f6 = (pad[6] + x^e[6][1])^e[6][0] - c[6]

g = T[0]*f0 + T[1]*f1 + T[2]*f2 + T[3]*f3 + T[4]*f4 + T[5]*f5 + T[6]*f6
g = g.monic()
roots = g.small_roots(X=2^511,epsilon=0.03)
print(roots)
for i in roots:
    flag = long_to_bytes(int(i))
    if b"begin" in flag:
        print(flag)

OEIS2

task.py

1
2
3
4
5
6
7
from hashlib import *

upper = 2**28 + 5
res = 1
for i in range(1, upper + 1):
    res *= i
flag = 'Beginctf{' + sha256(str(sum([int(i) for i in str(res)])).encode()).hexdigest() + '}'

半途换了附件有点难受，对着$n^n$查了很久

利用gamma函数近似计算阶乘：$\gamma(n+1) = n!$

然后计算每位数之和

时间要比较久，耐心等等

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
from hashlib import *
from tqdm import tqdm

x = 2^28 + 5
temp = str(gamma(x+1))

res = 0
for i in tqdm(temp):
    res += int(i)
    
flag = 'Beginctf{' + sha256(str(res).encode()).hexdigest() + '}'
print(flag)
# Beginctf{c60a2e5c9e9572ed848776f282a9c90d6ca0fe29f8308b0b9b43c61d493133e9}

我玩青水的

task.py

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

m = bytes_to_long(flag)
e = 2
p = getPrime(512)
c = pow(m, e, p)

print(f"p = {p}")
print(f"c = {c}")

'''
p = 7709388356791362098686964537734555579863438117190798798028727762878684782880904322549856912344789781854618283939002621383390230228555920884200579836394161
c = 5573755468949553624452023926839820294500672937008992680281196534187840615851844091682946567434189657243627735469507175898662317628420037437385814152733456
'''

解二次同余方程$c \equiv m^2 \mod p$

参考：二次剩余问题x的求解及代码实现（python）_gmpy2.powmod-CSDN博客

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

p = 7709388356791362098686964537734555579863438117190798798028727762878684782880904322549856912344789781854618283939002621383390230228555920884200579836394161
a = 5573755468949553624452023926839820294500672937008992680281196534187840615851844091682946567434189657243627735469507175898662317628420037437385814152733456
e = 2
k = 0

P = p - 1
if p % 4 == 3:
    print(pow(a,(p + 1)//4,p))
else:
    while P % 2 == 0:
        P //= 2
        k += 1
    q = 2
    while q:
        l = pow(q,(p-1)//2,p)
        if l == p - 1:
            break
        q = sympy.nextprime(q)
    b = pow(q,P,p)
    x = [0 for i in range(k)]
    re_a = gmpy2.invert(a,p)
    x[k-1] = pow(a,(P+1)//2,p)
    for i in range(1,k):
        m = re_a * pow(x[k-i],2)
        n = pow(2,(k-i-1))
        if pow(m,n,p) == p-1:
            j0 = 1
            x[k-i-1] = x[k-i]*pow(b,j0*(2**(i-1))) % p
        else:
            j1 = 0
            x[k-i-1] = x[k-i] % p
    print(long_to_bytes(x[0]))
    # begin{quadr4ticresidue_i5_s0_3asy}

begin_rsa

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
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
m = bytes_to_long(flag)

while True:
    e = 65537
    p1 = getPrime(512)
    q1 = getPrime(512)
    n1 = p1 * q1
    p1_xor_q1_low = (p1 ^ q1) & ((1 << 402) - 1)
    if p1_xor_q1_low >= 10**121 and p1_xor_q1_low <= 10**122 - 1:
        p2 = next_prime(p1_xor_q1_low)
        q2 = int(str(p2)[61:] + str(p2)[:61])
        n2 = p2 * q2
        if isPrime(p2) and isPrime(q2):
            delta = p2 - p1_xor_q1_low
            c = pow(m, e, n1)
            print(f"delta = {delta}")
            print(f"n1 = {n1}")
            print(f"n2 = {n2}")
            print(f"c = {c}")
            break

'''
delta = 61
n1 = 150838784531830142890659431841610000561921043629625618437510373123377520444955469509903631548754842609295975005302780725591929018884805452687677684641162979092069629817740554095750189248769936750051172301891394503776919559958638203717583333429953061416588208428893436430392654983424277005324307321992921302331
n2 = 102603788692700558034198259394482879736866145355211103067657972779629890324418113112441175321034955422723378003769267804892308121194871227786783930178021669484220789624643889449429959522560822967157677629720685465873700893389751397027159036419
c = 100199300622156732994823007073822662584719346985430234367094043002848132740563819931486477742264272832060136969084318984512567787814048659200236334994498141562184235841854521058494238451300610422156322926341430748222140189349893444976932184031798101999886029853099171189139509539715437105818418407563733036131
'''

step1

先分解$n_2$，类似2020黑盾杯——Change

$p = p_{high} \times 10^{61} + p_{low}$，$q = p_{low}\times 10^{61} + p_{high}$

所以$n = (p_{high}\times p_{low})\times 10^{122} + (p_{high}^2 + p_{low}^2)\times 10^{61} + p_{hgih}\times p_{low}$

因为$p_{high}$和$p_{low}$都是十进制下61位的数

所以$(p_{high}\times p_{low}){high} = \frac{n}{10^{183}}$，$(p{high}\times p_{low})_{low} = n % 10^{61}$

这样我们便可以得到$(p_{high}\times p_{low})$

之后联立下列俩方程求解即可
$$
(p_{high}\times p_{low}) = p_{high} \times p_{low}
$$

$$
n - (p_{high}\times p_{low})10^{122} - p_{high}\times p_{low} = 10^{61}(p_{high}^2 \times p_{low}^2)
$$

Step2

剪枝得p低400位，再用copperSmith

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
#sage
from sympy.solvers import solve
from sympy.abc import h,l
from Crypto.Util.number import isPrime
import gmpy2

delta = 61
n1 = 150838784531830142890659431841610000561921043629625618437510373123377520444955469509903631548754842609295975005302780725591929018884805452687677684641162979092069629817740554095750189248769936750051172301891394503776919559958638203717583333429953061416588208428893436430392654983424277005324307321992921302331
n2 = 102603788692700558034198259394482879736866145355211103067657972779629890324418113112441175321034955422723378003769267804892308121194871227786783930178021669484220789624643889449429959522560822967157677629720685465873700893389751397027159036419
c = 100199300622156732994823007073822662584719346985430234367094043002848132740563819931486477742264272832060136969084318984512567787814048659200236334994498141562184235841854521058494238451300610422156322926341430748222140189349893444976932184031798101999886029853099171189139509539715437105818418407563733036131
e = 65537

R.<x> = PolynomialRing(Zmod(n1))

def factor_N2(n):
    pq_high = n // pow(10,183)
    pq_low = n % pow(10,61)
    pq = pq_high * pow(10,61) + pq_low
    
    f1 = pq - h*l
    f2 = (n - pq*pow(10,122) - pq) - pow(10,61)*(h**2 + l**2)
    s = solve([f1,f2],[h,l])
    for i in s:
        p_high,p_low = int(i[0]),int(i[1])
        p = int(p_high * pow(10,61) + p_low)
        q = int(p_low * pow(10,61) + p_high)
        if p > 0 and q > 0 and isPrime(p) and isPrime(q):
            return p,q
        
def factor_N1(tp,tq):
    if len(tp)==400:
        p_low = int(tp,2)
        try:
            f = x*(2**400)+p_low
            res = f.monic().small_roots(X=2^112, beta=0.4)
            if res != []:
                p = res[0]*(2**400)+p_low
                if n1%p==0:
                    q = n1//int(p)
                    phi = (p-1)*(q-1)
                    d = inverse_mod(e,phi)
                    m = pow(c,d,n1)
                    flag = bytes.fromhex(hex(m)[2:])
                    if b'begin' in flag:
                        print(flag)
                        return 
                    
        except:
            pass
    else:
        k = len(tp)
        p1 = int(tp,2)
        q1 = int(tq,2)
        if (p1^^q1)%(2**k)==p_xor_q%(2**k) and (p1*q1)%(2**k)==n1%(2**k):
            factor_N1('1' + tp, '1' + tq)
            factor_N1('1' + tp, '0' + tq)
            factor_N1('0' + tp, '1' + tq)
            factor_N1('0' + tp, '0' + tq)

p2,q2 = factor_N2(n2)
print(f"p2 = {p2}")
print(f"q2 = {q2}")
p_xor_q = p2 - delta
factor_N1('1','1')
# begin{just_the_beginning_of_the_RSA}
-------------已经到底啦！-------------