比赛那天刚好返校, 没怎么打, 复盘一下

checkin

猜谜一样… 直到是背包问题也不知道具体该做什么….

挂着先

baby_OCB

红明古, 下次一定学会咕咕咕咕咕

easylsb

problem

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
#!/usr/bin/python3
# encoding: utf-8
import random
import string
import sys
import os
from hashlib import sha256
import uuid
from Crypto.Util.number import *

password = b'Hidden'
flag = ('flag{' + str(uuid.uuid4()) + '}').encode()

# def proof_of_work():
# random.seed(os.urandom(8))
# proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)]).encode()
# digest = sha256(proof).hexdigest()
# printf("sha256(XXXX+%s) == %s" % (proof[4:].decode(),digest))
# printf('Give me XXXX:')
# x = read_str()
# if len(x) != 4 or sha256(x.encode()+proof[4:]).hexdigest() != digest:
# return False
# return True

def printf(message):
sys.stdout.write('{0}\n'.format(message))
sys.stdout.flush()
sys.stderr.flush()

def read_str():
return sys.stdin.readline().strip()

def read_int():
return int(sys.stdin.readline().strip())

def next_prime(a):
while not isPrime(a):
a += 2
return a

def get_prime(a):
suffix = getPrime(368)
return next_prime(a ** 2 + suffix + 1)

def generate_pubkey(key):
p, q = get_prime(getPrime(512)), get_prime(key)
n = p * q
return n

def airdrop(a):
n = generate_pubkey(a)
printf('gift: {}'.format(n))
return

def hint(n, e, c):
printf('n = {}'.format(n))
printf('e = {}'.format(e))
printf('c = {}'.format(c))
return

def leak():
p = get_prime(getPrime(512))
e = 0x1000
c = pow(bytes_to_long(flag), e, p)

hint(p, e, c)
return

def backdoor():
printf('Input your password:')
user_input = read_str()
if user_input.encode() == password:
leak()
else:
printf('Wrong')
exit(0)

if __name__ == '__main__':
# if not proof_of_work():
# exit(0)

a = getPrime(512)
print(a)
p = get_prime(a)
q = get_prime(getPrime(512))
n = p * q
e = 0x10001
max_time = 5
password_enc = pow(bytes_to_long(password), e, n)

printf('====================================',)
printf('1. Airdrop ',)
printf('2. Backdoor ',)
printf('3. Hint ',)
printf('4. Exit ',)
printf('====================================',)

try:
while True:
printf('Your choice:')
choice = read_int()
if choice == 1:
if max_time > 1:
airdrop(a)
max_time -= 1
printf('Done!')
else:
printf('Greed will destroy you!')
continue
elif choice == 2:
backdoor()
printf('Done!')
continue
elif choice == 3:
hint(n, e, password_enc)
printf('Done!')
continue
elif choice == 4:
printf('bye~')
exit(0)
continue
else:
printf('Invalid!')
continue
except:
exit(-1)

要得到flag 必须通过leak() 而要调用leak()必须知道password

看一下airdrop()函数

choice 1每次调用都会给一个gift 也就是$n$
$$
n_i = q_i (a^2 + x_i) = q_ia^2 + q_ix_i
$$

The Approximate GCD Problem

之前的比赛也有遇到过, 这次认真的再看看$AGCD$

这里是个$AGCD$问题, 所谓的$AGCD$就是近似值$GCD$

比如现在有
$$
n_0 = p_0 \cdot q \
n_1 = p_1 \cdot q \
gcd(n_0,n_1) = q
$$
这个就是一般的$GCD$问题,而$AGCD$呢就是给这里的每个$n$都加上一个$error \ \ -> \ (x)$
$$
n_0 = p_0 \cdot q + x_0\
n_1 = p_1 \cdot q + x_1\
$$
那这样要求出$q$就不能用之前的算法了. 为了解决这个问题可以把这两行合成一下
$$
p_1n_0 - p_0n_1 = p_1x_0 - p_0x_1
$$
像这种形式的一看就可以写到一个格子里面去
$$
(p_0,p_1)
\begin{pmatrix}
R&n_1 \
0&-n_0
\end{pmatrix}
=(p_0R,p_1x_0-p_0x_1)
$$
右边的向量的范数跟$R,p,x$是有关的, 而$R$是可以调整的, 所以理论上只要右边的几个参数够小, 我们是有机会找到这个向量从而求出$p_0$, 求出$p_0$就能解决$AGCD$问题了.

现在回到题目. 现在有五行式子
$$
n_0 = q_0a^2 + q_0x_0 \
n_1 = q_1a^2 + q_1x_1 \
\cdots \
n_4 = q_4a^2 + q_4x_4 \
$$
其实这里我一拿到这五行就开始构造格子做了, 但dbt👴提醒了我, $AGCD$问题右边参数越小越好, 考虑一下开方, 因为$AGCD$问题本身就是一个近似值求解GCD的问题. 所以我们在做的过程中也做点近似一般是不会影响的(?有爷爷研究过近似的一个度吗
$$
\sqrt{n_0} = \sqrt{q_0}\sqrt{a^2 + x_0} \
\sqrt{n_0} - \hat x \approx \sqrt{q_0}a \
\sqrt{n_i} = \sqrt{q_i}a + \hat x_i
$$
让右边的式子更小之后, 用五组数据构造格子
$$
\begin{pmatrix}
R&\sqrt{n_1}&\sqrt{n_2}&\sqrt{n_3}&\sqrt{n_4} \
0&-\sqrt{n_0}&0&0&0 \
0&0&-\sqrt{n_0}&0&0 \
0&0&0&-\sqrt{n_0}&0 \
0&0&0&0&-\sqrt{n_0}
\end{pmatrix}
$$
规约之后能找到向量(后面的不重要就先不写了)
$$
(R\sqrt{q_0},\cdots,\cdots,\cdots,\cdots)
$$
但在规约的时候, 因为范数的问题, 需要不断的调整$R$的值才能找我们需要的那个向量, 调整的依据就是这个$q_0$的大小, 这个大小是知道的$1024 bit$,所以最后得到的$\sqrt{q_0}$应该是$512bit$

事实上, 在我看到的blog里面, 这个R的取值是有一定的方法的, 没有搞懂具体该怎么去判断, 所以只能通过调整的方法来做这题了,

想起来自己的博客之前也有试过去推一个大概的值, 可以翻前面的看看

所以现在只需要不断的调整$R$的大小, 直到找出一个$512 bit$的真正的$\sqrt{q_0}$ ,有了$\sqrt{q_0}$就能求出$a$了,

解出$a$剩下的就是已知$p$高位了

做这题的时候发现如果只用四组数据, 不管怎么的调整$R$, 也没有办法找出想要的那个向量出来, 不知道是不是因为参数的大小, 四组数据给出的约束不够强?

解完AGCD之后就能拿到一个加密的flag, e和phi不互素, 发现e是$2^{12}$, 直接开12次平方根就行了

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
74
75
import sys

sys.path.append("/home/k1rit0/CTF/")
import myCrypto.AMM as AMM

from sage.all import *

from Crypto.Util.number import inverse, isPrime, long_to_bytes

LAM = 380
l = 5
M = [[0 for _ in range(l)] for _ in range(l)]
N = [21068286322889605292449387381402285403911455560141090214735354974440606624419616964297007580321013791067226167439872996226832500580037706653803152998537359002847432836899418650117306549893607343160006144352760334920785866221130409904894118963374929467323935674617670738402419178327965359202178162667267351040190371168301980935481660326630257816016921697149710082155701629870160350348818834688225753303057415885022226024601907498521621901308603324694768684738802528845831936410741399435491742825201984427922436831471812070309418640813794622730842698875782093607446798284303784522710493344963880678737688403891400189331,
12308853561607841041934092506744511689155586116240481655471529969953855274038227343811431655989608434591583673694139060863738492861944511267544267389946989849658784130545243679913412818685768313761630659910263680193434985838781131523993553907838129189461461476296694554655782825701774629683350764866069156868009043211117580921049441277102377562595106269789041165210135844474567428536421792003953066707002965308982249630472773112238349557943156998108879517471317999283500584387777397105486037127797366322210846034599129011995028171723686883387966414035624689126402104807914499946793228044511016295452985310557970379011,
30738697791225132085580847654714047571186902668616746842899304102159584623469816318757206927486219023390491315148910896488732403322767246394501024688827804510369382155878820868892068583525039291929122306306627213766241320525799308714371006850194133645674073652842238370607838910482032953868627367283394607836966578300168303793400060582848922857236410576441317474208136497407564188049755626445760675555940268390636610085726624705570165069943427799504990418468772678900305743541682004982830947893963522764021022122922104982911181491725457610355492465006313490505471915305370861395875195908816803244772843442663436627811,
8305502698327938163061403448570905343510072391121488812862051390404395134941843998819543534972233651342461635174480345500578515464031763529097882752145582280163441217012244252516496790390759043249994221367357315376275069348967721415258505344163223181510037360702185803627278919587509933485368201596116686196256578251198487468448008040978019816660838136301253757474040665970837583661727365857243232757366302995923446406792674664094421560455977644181219681801233665490911903627509944363786700632306093740157219837713108792604909612708233475959478546962262259340699913418281265092058666045625836471989209312154073075491,
9249057556737779363640590847304104073427145700484200097209450631890326978899167760679154628208658960714377959140386507599020762987984595928908203986925752986701463694818100098371494812801057184146507393471109418242580315774651644212154315684690259768215107765517606521494940441845123991021958309973443907208341450704221754039776849253367952771456447007511355415631917532484344389697848200615413029231558971975377100287746424454815515972611696776506127916905426006223842544245270081659891304287086426791583147370534686626291189249685625856952980692492700851557019098598454447260906380261199261945010423393013023715209 ]



for i in range(l):
N[i] = int(sqrt(N[i]))


for i in range(1,l):
M[i][i] = -N[0]
M[0][i] = N[i]
M[0][0] = 2 ** LAM
L = Matrix(M).LLL()[0]
assert L[0] % 2 ** LAM == 0

q = abs(L[0] // 2 ** LAM)
n = N[0]
a = (n - (n % q)) // q
# Know high bit of p
n = 9249057556737779363640590847304104073427145700484200097209450631890326978899167760679154628208658960714377959140386507599020762987984595928908203986925752986701463694818100098371494812801057184146507393471109418242580315774651644212154315684690259768215107765517606521494940441845123991021958309973443907208341450704221754039776849253367952771456447007511355415631917532484344389697848200615413029231558971975377100287746424454815515972611696776506127916905426006223842544245270081659891304287086426791583147370534686626291189249685625856952980692492700851557019098598454447260906380261199261945010423393013023715209
e = 65537
c = 596355871374007258796739088580480254690421307398563449520929804224579804032978250178898982384142847223103176953609592214108362545413436815340326688408982175941755069859344738153840235542651636279657627294019566968304679361239665444560606473133283058393087609946086549065553264454684624204753050326115020520403436076532095607286695957435489522985881581820635688415133423515447960953517405315231071959346343447601273197470177184887138457495799503680274625485150493280857586565387473867813858817367137470006514777542969192548145776362722942018998084778630461770023286812913356191141099060132770816764636107436181833654

_p = a**2
R = PolynomialRing(Zmod(n),'x')
x = R.gens()[0]
f = _p + x
roots = f.small_roots(X=2 ** 368,beta = 0.4)
if roots:
p = _p + int(roots[0])
print(p)
assert n % p == 0
q = n // p
phi = (p-1) * (q-1)
d = inverse_mod(e,phi)
print(long_to_bytes(pow(c,d,n)))


p = 117235409029105051846806067899523247170361728684595002856792997268214583527481018331523314373480172502868245719103537926811678162691190783273715963938227870577908696266175564889962816950193051688136250287087726752359306820791879258724210723175953346754995614733931375012961016374642411090783817788045807125779
e = 4096
c = 9565562547953889050875342796317230683573917021053842636334550812905648260474828549598393988661413478381057558054348342995403993026447829846151651076469025927491897151314215230367392957203050021568190862146104714972731651005427897872753163387978990574633850084765886249824258759820964357075803586150088309646

R = PolynomialRing(Zmod(p),'x')
R1 = [c]
R2 = []
for _ in range(12):
for r in R1:
x = R.gens()[0]
f = x ^ 2 - r
roots = f.roots()
if roots:
for root in roots:
R2.append(root[0])
R1 = R2
R2 = []
print(R1)
for m in R1:
print(long_to_bytes(m))

ezl1near

problem

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
from Crypto.Util.number import long_to_bytes , bytes_to_long , getPrime , inverse
from Crypto.Cipher import AES
import socketserver , signal
import random
import string
from hashlib import sha256
import os
flag = 'aaaaaaaaaaaaaaaa'
q = 2**24

def getrandbits(n):
return bytes_to_long(os.urandom(n // 8+1)) >> (8-n%8)

class server(socketserver.BaseRequestHandler):


def _recv(self):
data = self.request.recv(1024)
return data.strip()

def _send(self, msg, newline=True):
if isinstance(msg , bytes):
msg += b'\n'
else:
msg += '\n'
msg = msg.encode()
self.request.sendall(msg)

def proof_of_work(self):
random.seed(os.urandom(8))
proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
_hexdigest = sha256(proof.encode()).hexdigest()
self._send(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
self._send(b'Give me XXXX: ')
x = self._recv()
if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
self.send('wrong')
return False
return True

def genrsa(self):
_p = getPrime(1024)
_q = getPrime(1024)
self.n = _p * _q
self.e = 65537
self.d = inverse(self.e , (_p-1)*(_q-1))

def to_vec(self,num , length):
vec = []
while length > 0:
vec = [num % q] + vec
num //= q
length -= 1
return vec

def to_mat(self,numlist):
M =[]
for i in numlist:
M.append(self.to_vec(i , 40))
return M

def enc(self, key , m):
key = self.to_mat(key)
res = []
for i in range(40):
temp = 0
for j in range(16):
temp += m[j]* key[j][i]
temp %= q
res.append(temp)
return res
def handle(self):
# signal.alarm(120)
# self.proof_of_work()
self.genrsa()
self._send(str(self.n))
self._send(str(self.e))
secret = [1] + [2*getrandbits(23)-1 for _ in range(15)]
print(secret)
self._send(b'Please generate key for me and I will give you my secret.But you have only two chances.')
for i in range(2):
key = []
f0 = getrandbits(480)
print(f0)
key.append(f0)
self._send(str(pow(f0 , self.e , self.n)))
f0 += f0 << 480
for j in range(15):
self._send('key'+str(i+1) + ':')
c = int(self._recv())
m = pow(c , self.d , self.n)
f = m - f0
f %= self.n
key.append(f)
c = self.enc(key , secret)
self._send('Thanks, here is your cipher:' + str(c))
self._send(b'do you know the secret?')
guess = [int(i) for i in self._recv().split(b' ')]
if len(guess) == 16:
for j in range(16):
if guess[j] != secret[j]:
break
else:

self._send(b'congratulations. here is your flag:')
self._send(flag)
return 0
else:
self._send(b'L1near don\'t care.')


class ForkedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
pass

if __name__ == "__main__":
HOST, PORT = '0.0.0.0', 10000
server = ForkedServer((HOST, PORT), server)
server.allow_reuse_address = True
server.serve_forever()


流程有点长, 大概就是随机生成一个向量$secret = (1,s_0,s_1,\cdots,s_{13},s_{14})$, 我们的目标就是得到这个

一开始他会生成一个$f_0$, 并通过RSA加密然后给我们密文

中间他会让我们输入15个$key$, 但是这十五个$key$不是直接咱们输入什么就是什么的, 他会经过一个RSA的解密

最后$f_0$加上我们输入的15个$key$一起生成一个$16 \cdot 40$的矩阵$M$(一个key就生成一行)

然后计算密文
$$
secret \cdot M = (c_0,c_1,\cdots,c_{38},c_{39})
$$
这里密文我们是知道的, 我们只需要弄到$M$就能得到$secret$了

而这里$M$除了第一行, 都是我们自己构造的, 但是比较难控制,因为实际上的key和我们传过去差一个解密, 但是我们有一个$f_0$的密文, 我们可以利用RSA的乘法同态就构造$k\cdot f_0$, 这个$k$想是多少就是多少.

而且观察$M$的生成, 我们发现只要得到第一行的所有数, 我们就能还原回$f_0$, 因为$secret$的第一个固定是1, 而$M$的第一行只有后面20个才有数字, 前面的20个都是0, 所以我们只要让后面的20列除了第一行都是0就可以得到$f_0$了. 而且, 我们可以传$Enc(q^if_0)$, 让$M$的后面几行的生成就是第一行的数字往前推i个, 所以我们让$i=20$就能推到刚好只有第一行的后面$20$列是有数字的.

那么大概的思路有了, 构造$M$, 1. 必须得可逆, 才能求$secret$. 2. 后面20列是0
$$
(1,s_0,s_1,\cdots,s_{13},s_{14})
\begin{pmatrix}
0&0&\cdots&0&a_0&a_1&\cdots&a_{19} \
k_{1,0}&k_{1,1}&\cdots&k_{1,19}&0&0&\cdots&0 \
&&&\cdots \
k_{15,0}&k_{15,1}&\cdots&k_{15,19}&0&0&\cdots&0

\end{pmatrix}
\
=(c_0,c_1,\cdots,c_{19},a_0,a_1,\cdots,a_{19})
$$
我们需要这个$M$可逆, 就是要满秩, 就每次传的时候再加一个随机的系数$j$就行了, 也就是传$Enc(jq^if_0)$

构造出了上面这个, 就能利用$a_0,\cdots,a_{19}$还原$f_0$, 再用$f_0$生成整个$M$, 最后求个$M^{-1}$算回$secret$即可

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
from sage.all import *
import re
import pwn
import random
q = 2**24

def shiftf0(enc_f0,i):
a = 2 ** 480 + 1 + (i+1) * q**20
return ((enc_f0 * pow(a,e,n)) % n)

def to_vec(num , length):
vec = []
while length > 0:
vec = [num % q] + vec
num //= q
length -= 1
return vec

def to_mat(numlist):
M =[]
for i in numlist:
M.append(to_vec(i , 40))
return M


CON = pwn.remote('172.27.176.1',10000)
resp = CON.recvuntil('key1:\n').decode().split('\n')
n = int(resp[0])
e = 65537
enc = int(resp[3])
for _ in range(14):
CON.sendline(str(shiftf0(enc,_)).encode())
resp = CON.recvuntil('key1:\n').decode()
print(_,resp)
CON.sendline(str(shiftf0(enc,_+1)).encode())
resp = CON.recvuntil('key2:\n').decode().split('\n')


_res = resp[0][29:-1].split(',')
res =[]
for i in _res:
res += [int(i)]
f0 = 0
for i in res[-20:]:
f0 += i
f0 = f0 << 24
f0 = f0 >> 24
key = [f0]+ [((i+1)* q**20 * f0 ) % n for i in range(15)]
M = matrix(Zmod(q),to_mat(key))
print(M.solve_left(vector(res)))