2024VCTF

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

2024 第一届VCTF纳新赛——Crypto

狂飙

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import os
from flag import flag
from Crypto.Util.number import *
from Crypto.Cipher import AES
m = 88007513702424243702066490849596817304827839547007641526433597788800212065249
key = os.urandom(24)
key = bytes_to_long(key)
n=m % key
flag += (16 - len(flag) % 16) * b'\x00'
iv = os.urandom(16)
aes = AES.new(key,AES.MODE_CBC,iv)
enc_flag = aes.encrypt(flag)

print(n)
print(enc_flag)
print(iv)


#103560843006078708944833658339172896192389513625588
#b'\xfc\x87\xcb\x8e\x9d\x1a\x17\x86\xd9~\x16)\xbfU\x98D\xfe\x8f\xde\x9c\xb0\xd1\x9e\xe7\xa7\xefiY\x95C\x14\x13C@j1\x9d\x08\xd9\xe7W>F2\x96cm\xeb'
#b'UN\x1d\xe2r<\x1db\x00\xdb\x9a\x84\x1e\x82\xf0\x86'

$$
\because n \equiv m \mod key
$$

$$
\therefore m - n = t\times key
$$

利用sagemath自带的函数divisors()即可获得$t\times key$的所有因子，即使有多个因子，该函数会自动求出各种不同组合因子的乘积

exp

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

m = 88007513702424243702066490849596817304827839547007641526433597788800212065249
n = 103560843006078708944833658339172896192389513625588
c = b'\xfc\x87\xcb\x8e\x9d\x1a\x17\x86\xd9~\x16)\xbfU\x98D\xfe\x8f\xde\x9c\xb0\xd1\x9e\xe7\xa7\xefiY\x95C\x14\x13C@j1\x9d\x08\xd9\xe7W>F2\x96cm\xeb'
iv = b'UN\x1d\xe2r<\x1db\x00\xdb\x9a\x84\x1e\x82\xf0\x86'

temp = m - n

for i in divisors(temp):
    if 184 <= int(i).bit_length() <= 192 and temp % i == 0:
        key = long_to_bytes(int(i))
        aes = AES.new(key,AES.MODE_CBC,iv)
        flag = aes.decrypt(c)
        if b"flag" in flag:
            print(flag)
            # flag{cf735a4d-f9d9-5110-8a73-5017fc39b1b0}

RRSA

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

def genprime():
	o = getPrime(300)
	while True:
		r = random.randint(2**211,2**212)
		if isPrime(o*r+1):
			return o,o*r+1
o1,p = genprime()
o2,q = genprime()
n=p*q
g = random.randint(2,n)
order = o1*o2

a = pow(g, (p-1)*(q-1)//order, n)
assert pow(a,order,n)==1

m = bytes_to_long(flag)
e = 65537
c = pow(m,e,n)
print(f'n={n}')
print(f'c={c}')
print(f'a={a}')
print(f'o={order}')
n=44435425447782114838897637647733409614831121089064725526413247701631122523646623518523253532066782191116739274354991533158902831935676078270115998050827358178237970133151467497051097694866238654012042884894924846645692294679774577780414805605811029994570132760841672754334836945991390844881416693502552870759
c=41355409695119524180275572228024314281790321005050664347253778436753663918879919757571129194249071204946415158483084730406579433518426895158142068246063333111438863836668823874266012696265984976829088976346775293102571794377818611709336242495598331872036489022428750111592728015245733975923531682859930386731
a=39844923600973712577104437232871220768052114284995840460375902596405104689968610170336151307934820030811039502338683925817667771016288030594299464019664781911131177394369348831163266849069740191783143327911986419528382896919157135487360024877230254274474109707112110411601273850406237677432935818199348150470
o=1745108106200960949680880500144134006212310627077303652648249235148621661187609612344828833696608872318217367008018829485062303972702933973340909520462917612611270028511222134076453

非预期

由题意知:
$$
p = o_1r_1 + 1 \quad q = o_2r_2 + 1
$$

$$
\therefore n = o_1r_1o_2r_2 + o_1r_1+o_2r_2 + 1
$$

$$
\phi(n) = o_1r_1o_2r_2
$$

注意到$o_1o_2$的数量级为600bit，而$o_1r_1,o_2r_2$的数量级只有512bit

用n去除$o_1o_2$可以得到$r_1r_2$

再乘回$o_1o_2$即可得到$\phi(n)$

exp

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

e = 65537
n=44435425447782114838897637647733409614831121089064725526413247701631122523646623518523253532066782191116739274354991533158902831935676078270115998050827358178237970133151467497051097694866238654012042884894924846645692294679774577780414805605811029994570132760841672754334836945991390844881416693502552870759
c=41355409695119524180275572228024314281790321005050664347253778436753663918879919757571129194249071204946415158483084730406579433518426895158142068246063333111438863836668823874266012696265984976829088976346775293102571794377818611709336242495598331872036489022428750111592728015245733975923531682859930386731
a=39844923600973712577104437232871220768052114284995840460375902596405104689968610170336151307934820030811039502338683925817667771016288030594299464019664781911131177394369348831163266849069740191783143327911986419528382896919157135487360024877230254274474109707112110411601273850406237677432935818199348150470
o=1745108106200960949680880500144134006212310627077303652648249235148621661187609612344828833696608872318217367008018829485062303972702933973340909520462917612611270028511222134076453

phi = n // o * o
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
# flag{0228FC7F-C865-BD0F-F124-9F9860B3542B}

预期

$$
\because \phi(n) = o\times r_1\times r_2
$$

$$
\phi(n) = (p-1)(q-1) = n - (p+q)+1
$$

有
$$
p+q = n + 1 - o\times r_1\times r_2
$$
构造格

平衡一下目标向量，最终构造的格为

求出p + q后即可很容易分解n

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2

n=44435425447782114838897637647733409614831121089064725526413247701631122523646623518523253532066782191116739274354991533158902831935676078270115998050827358178237970133151467497051097694866238654012042884894924846645692294679774577780414805605811029994570132760841672754334836945991390844881416693502552870759
c=41355409695119524180275572228024314281790321005050664347253778436753663918879919757571129194249071204946415158483084730406579433518426895158142068246063333111438863836668823874266012696265984976829088976346775293102571794377818611709336242495598331872036489022428750111592728015245733975923531682859930386731
a=39844923600973712577104437232871220768052114284995840460375902596405104689968610170336151307934820030811039502338683925817667771016288030594299464019664781911131177394369348831163266849069740191783143327911986419528382896919157135487360024877230254274474109707112110411601273850406237677432935818199348150470
o=1745108106200960949680880500144134006212310627077303652648249235148621661187609612344828833696608872318217367008018829485062303972702933973340909520462917612611270028511222134076453
e = 65537

Ge = Matrix(ZZ,[
    [2^90,-o],
    [0,n+1]
])

paddq = Ge.LLL()[0][-1]
p_q = gmpy2.iroot((paddq^2 - 4*n),2)[0]

p = (paddq + p_q) // 2
q = n // p

d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(bytes.fromhex(hex(int(m))[2:]))
# flag{0228FC7F-C865-BD0F-F124-9F9860B3542B}
-------------已经到底啦！-------------