tvdat20004's blog
2973 words
15 minutes
SECCON 2024
2024-12-19
CTF Writeups
Generalized Reed-Solomon
/
ROT13
/
Gröbner basis
/
AES-GCM
/
LWE

SECCON 2024#

reiwa_rot13 (127 solves)#

  • chall.py
from Crypto.Util.number import *
import codecs
import string
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 137

key = ''.join(random.sample(string.ascii_lowercase, 10))
rot13_key = codecs.encode(key, 'rot13')

key = key.encode()
rot13_key = rot13_key.encode()

print("n =", n)
print("e =", e)
print("c1 =", pow(bytes_to_long(key), e, n))
print("c2 =", pow(bytes_to_long(rot13_key), e, n))

key = hashlib.sha256(key).digest()
cipher = AES.new(key, AES.MODE_ECB)
print("encyprted_flag = ", cipher.encrypt(flag))
  • Mục tiêu chính của bài này là tìm key để decrypt AES flag, họ cho ta 2 giá trị c1 = key^e mod n và c2 = rot13_key^e mod n. Để tìm được key, ta buộc phải tìm liên hệ của 2 giá trị key và rot13_key.
  • Để ý rằng, giả sử key là chuỗi kí tự [a0,a1,...,a9][a_0, a_1, ..., a_9], khi đó rot13_key là chuỗi [a0±13,a1±13,...,a9±13][a_0 \pm 13, a_1 \pm 13, ..., a_9 \pm 13]:
    • byte_to_long(key) = a0∗2569+a1∗2568+...+a9a_0*256^9 + a_1*256^8 + ... + a_9
    • byte_to_long(rot13_key) = (a0±13)∗2569+(a1±13)∗2568+...+a9±13=(a_0 \pm 13)*256^9 + (a_1 \pm 13)*256^8 + ... + a_9 \pm 13= byte_to_long(key) + alpha với alpha= ±13∗2569±13∗2568...±13\pm 13*256^9 \pm 13*256^8 ... \pm 13
    • Ta sẽ brute tất cả trường hợp của alpha, lập đa thức ứng với giá trị của c1 và c2 rồi tìm gcd của chúng để tìm key. Vì chỉ có 210=10242^{10}=1024 trường hợp nên brute cũng khá nhanh.
  • solve.py
from sage.all import * 
import codecs
import string
import random
from Crypto.Util.number import * 
from Crypto.Cipher import AES 
import hashlib
n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233

encyprted_flag =  b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"

def gcd_zmod(f, g):
    while g:
        f, g = g, f % g
    return f

x = Zmod(n)['x'].gen()
for i in range(2**10):
	bin_i = bin(i)[2:].zfill(10)
	offset = 0
	for j in range(10):
		if bin_i[j] == '0':
			offset -= 13 * 256**j
		else:
			offset += 13*256**j 
	f1 = x**e - c1 
	f2 = (x + offset)**e - c2 
	f = gcd_zmod(f1,f2).monic()
	if f != 1:
		print(f)
		m = f.coefficients()[0]
		key = long_to_bytes(int(-m))
		print(key)
		key = hashlib.sha256(key).digest()
		print(AES.new(key, AES.MODE_ECB).decrypt(encyprted_flag))
		quit()

image

dual_summon (63 solves)#

Đây là bài mình thấy khá hay và khó về AES-GCM, nhưng không hiểu sao nó nhiều solve đến vậy (chắc tại mình gà)

  • server.py
from Crypto.Cipher import AES
import secrets
import os
import signal

signal.alarm(300)

flag = os.getenv('flag', "SECCON{sample}")

keys = [secrets.token_bytes(16) for _ in range(2)]
# nonce = secrets.token_bytes(16)
nonce = 12*b'\0'
def summon(number, plaintext):
    assert len(plaintext) == 16
    aes = AES.new(key=keys[number-1], mode=AES.MODE_GCM, nonce=nonce)
    ct, tag = aes.encrypt_and_digest(plaintext)
    print(AES.new(keys[number - 1], AES.MODE_ECB).encrypt(16*b'\0').hex())
    return ct, tag

# When you can exec dual_summon, you will win
def dual_summon(plaintext):
    assert len(plaintext) == 16
    aes1 = AES.new(key=keys[0], mode=AES.MODE_GCM, nonce=nonce)
    aes2 = AES.new(key=keys[1], mode=AES.MODE_GCM, nonce=nonce)
    ct1, tag1 = aes1.encrypt_and_digest(plaintext)
    ct2, tag2 = aes2.encrypt_and_digest(plaintext)
    # When using dual_summon you have to match tags
    assert tag1 == tag2

print("Welcome to summoning circle. Can you dual summon?")
for _ in range(10):
    mode = int(input("[1] summon, [2] dual summon >"))
    if mode == 1:
        number = int(input("summon number (1 or 2) >"))
        name   = bytes.fromhex(input("name of sacrifice (hex) >"))
        ct, tag = summon(number, name)
        print(f"monster name = [---filtered---]")
        print(f"tag(hex) = {tag.hex()}")

    if mode == 2:
        name   = bytes.fromhex(input("name of sacrifice (hex) >"))
        dual_summon(name)
        print("Wow! you could exec dual_summon! you are master of summoner!")
        print(flag)
  • Bài này cho ta tương tác với một server, được gởi request tối đa 10 lần, với 2 mode:
    • Mode 1 cho phép ta encrypt bằng AES-GCM với 1 trong 2 key, nhưng chỉ trả về tag.
    • Mode 2 yêu cầu ta tìm plaintext sao cho khi encrypt AES-GCM bằng 2 key thì sinh ra 2 tag giống nhau. Nếu thành công thì server sẽ cho ta flag.
  • Để làm được bài này, ta cần hiểu rõ cách AES-GCM sinh tag.

How tag works?#

  • Ta có thể tham khảo từ blog này và trang wiki.
  • Đầu tiên, các block trong ciphertext sẽ được chuyển về các đa thức trong GF(2128)GF(2^{128}), sau đó chúng được đưa qua hàm GHASH. Đây là sơ đồ hàm GHASH: image
  • Cụ thể, H là AES encrypt của chuỗi gồm 16 bytes 0, dấu ⨂\bigotimes_{}^{} và dấu ⨁\bigoplus_{}^{} cũng là phép nhân và phép cộng trong GF(2128)GF(2^{128}). Do đó, hàm GHASH cũng có thể được viết lại dưới dạng một đa thức:
    • Giả sử, ta có chuỗi X = (additional_data||ciphertext||(len(A)||len(C)) được chia thành các block X1,X1,...,XnX_1, X_1,...,X_{n} f(X)=∑i=1nXi∗Hm−i+1f(X) = \sum_{i=1}^{n}X_i*H^{m-i+1} Bài này do server chỉ cho ta encrypt 1 lần 1 block nên đa thức ta sẽ là f(C)=A∗H3+C∗H2+(len(A)∣∣len(C))∗Hf(C) = A*H^3 + C*H^2 + (len(A)||len(C))*H (AA là additional_data)
    • Kết quả của hàm GHASH sẽ được xor với giá trị AES encrypt của nonce để được tag
  • Đầu tiên, để thuận tiện cho việc giải bài này, mình sẽ dùng code từ file Utils.py này chủ yếu để tiện trong việc chuyển đổi từ chuỗi byte sang đa thức trong GF(2128)GF(2^{128}) và ngược lại.
  • Hàm để send request với option 1:
def summon(pt, number):
    io.sendlineafter(b'[1] summon, [2] dual summon >', b'1')
    io.sendlineafter(b'summon number (1 or 2) >', str(number).encode())
    io.sendlineafter(b'name of sacrifice (hex) >', pt.hex().encode())
    io.recvuntil(b'tag(hex) = ')
    return bytes.fromhex(io.recvlineS().strip())

Tìm H và encrypted_nonce#

  • Bước đầu, ta cần tìm giá trị của H của aes1 và aes2
    aes1 = AES.new(key=keys[0], mode=AES.MODE_GCM, nonce=nonce)
    aes2 = AES.new(key=keys[1], mode=AES.MODE_GCM, nonce=nonce)
  • Ý tưởng để tìm là ta sẽ gởi 2 message bất kì cùng độ dài m1, m2 cùng với m1 xor m2 lên server để encrypt bằng key[0], ta thu được tag1, tag2 và tag3.
  • Ta có:
    • tag1 = A*H**3 + c1*H**2 + H*(len(A)||len(c1)) + enc_nonce
    • tag2 = A*H**3 + c2*H**2 + H*(len(A)||len(c2)) + enc_nonce
    • tag1 + tag2 = (c1 + c2)*H**2 => H = sqrt((tag1 + tag2)/(c1 + c2))
  • Có được H, ta dễ dàng tìm được enc_nonce.
m1 = 16*b'1'
m2 = 16*b'2'
tag1 = summon(m1, 1)
tag2 = summon(m2, 1)
tag3 = summon(xor(m1, m2), 1)
ad = int2field(0)
len_ = int2field(16)

comb = int2field(bytes_to_long(xor(tag1, tag2)))
ct1_ct2 = int2field(bytes_to_long(xor(m1, m2)))
H1 = comb * (1/ct1_ct2)
H1 = H1.nth_root(2)
enc_nonce1 = (H1**3*ad + H1**2 * ct1_ct2 + H1*len_) + int2field(bytes_to_long(tag3))

Tương tự với việc tìm H2 và enc_nonce2

comb = int2field(bytes_to_long(xor(tag1, tag2)))
H2 = comb * (1/ct1_ct2)
H2 = H2.nth_root(2)
enc_nonce2 = (H2**3*ad + H2**2 * ct1_ct2 + H2*len_) + int2field(bytes_to_long(tag3))

Tìm ct để thu được 2 tag giống nhau#

  • Việc này đồng nghĩa với chúng ta phải tìm ct sao cho: f1(ct) + enc_nonce1 = f2(ct) + enc_nonce2 => ct = (A*(H1**3 - H2**3) + len*(H1 - H2) + enc_nonce1 - enc_nonce2)/ (H2**2 - H1**2) (mn tự biến đổi nhé ☺️)
  • Tổng hợp lại, ta có script solve như sau:
from Crypto.Cipher import AES 
from pwn import * 
from Crypto.Util.number import *
from Utils import *
io = process(["python3", "server.py"])
# io = remote("dual-summon.seccon.games", 2222)
def summon(pt, number):
	io.sendlineafter(b'[1] summon, [2] dual summon >', b'1')
	io.sendlineafter(b'summon number (1 or 2) >', str(number).encode())
	io.sendlineafter(b'name of sacrifice (hex) >', pt.hex().encode())

	io.recvuntil(b'tag(hex) = ')
	return bytes.fromhex(io.recvlineS().strip())

m1 = 16*b'1'
m2 = 16*b'2'
tag1 = summon(m1, 1)
tag2 = summon(m2, 1)
tag3 = summon(xor(m1, m2), 1)
ad = int2field(0)
len_ = int2field(16)

comb = int2field(bytes_to_long(xor(tag1, tag2)))
ct1_ct2 = int2field(bytes_to_long(xor(m1, m2)))
H1 = comb * (1/ct1_ct2)
H1 = H1.nth_root(2)
enc_nonce1 = (H1**3*ad + H1**2 * ct1_ct2 + H1*len_) + int2field(bytes_to_long(tag3))


tag1 = summon(m1, 2)
tag2 = summon(m2, 2)
tag3 = summon(xor(m1, m2), 2)

comb = int2field(bytes_to_long(xor(tag1, tag2)))
H2 = comb * (1/ct1_ct2)
H2 = H2.nth_root(2)
enc_nonce2 = (H2**3*ad + H2**2 * ct1_ct2 + H2*len_) + int2field(bytes_to_long(tag3))

ct = (ad*(H1**3 - H2**3) + len_*(H1 - H2) + enc_nonce1 - enc_nonce2)/ (H2**2 - H1**2)
ct = long_to_bytes(field2int(ct))
print(ct)
print(bytes_to_long(summon(ct, 1)))
print(bytes_to_long(summon(ct, 2)))

io.sendlineafter(b'[1] summon, [2] dual summon >', b'2')
io.sendlineafter(b'name of sacrifice (hex) >', ct.hex().encode())
io.interactive()

image

*Tidal wave (19 solves)#

Bài này sau giải mình xem write up xong mới giải được (do skill issue), sau đây là cách hiểu của mình về solution bài này.

import random
from Crypto.Util.number import getPrime
import secrets
# from flag import flag
flag = b'test_flag'
def get_Rrandom(R):
    return secrets.randbelow(int(R.order()))

def make_G(R, alphas):
    mat = []
    for i in range(k):
        row = []
        for j in range(n):
            row.append(alphas[j]^i)
        mat.append(row)
    mat = matrix(R, mat)
    return mat

def split_p(R, p, prime_bit_length, length):
    step = ceil(prime_bit_length/length)
    res = []
    while p > 0:
        res.append(ZZ(p % (2**step)))
        p >>= step
    return vector(R, res)

def make_random_vector(R, length):
    error_range = 2^1000
    res = []
    for _ in range(length):
        res.append(R(secrets.randbelow(int(error_range))))
    return vector(R, res)

def make_random_vector2(R, length):
    error_cnt = 28
    res = vector(R, length)
    error_pos = random.sample(range(length), error_cnt)
    for i in error_pos[:error_cnt//2]:
        res[i] = get_Rrandom(R)*p
    for i in error_pos[error_cnt//2:]:
        res[i] = get_Rrandom(R)*q
    return vector(R, res)

n, k = 36, 8
prime_bit_length = 512
p = getPrime(prime_bit_length)
q = getPrime(prime_bit_length)
N = p*q
R = Zmod(N)
alphas = vector(R, [get_Rrandom(R) for _ in range(n)])
G = make_G(R, alphas)
dets = [G.submatrix(0,i*k-i,8,8).det() for i in range(5)]
double_alphas = list(map(lambda x: x^2, alphas))
alpha_sum_rsa = R(sum(alphas))^65537

keyvec = vector(R, [get_Rrandom(R) for _ in range(k)])
pvec = split_p(R, p, prime_bit_length, k)

p_encoded = pvec*G + make_random_vector(R, n)
x = make_random_vector2(R, n)
key_encoded = keyvec*G + x
print(f"{N=}")
print(f"{dets=}")
print(f"{double_alphas=}")
print(f"{alpha_sum_rsa=}")
print(f"{p_encoded=}")
print(f"{key_encoded=}")


import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
key = hashlib.sha256(str(keyvec).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
encrypted_flag = cipher.encrypt(pad(flag, AES.block_size))
print(f"{encrypted_flag=}")
  • Đây là bài tổng hợp lại của 3 bài toán con mà mình sẽ trình bày sau đây (và cái nào cũng khoai cả).

Tìm alphas: Gröbner basis#

  • Đó là bước mà ta phải tìm vector alphas từ các dữ kiện đề cho là dets, double_alphas và alpha_sum_rsa.
  • Đầu tiên, để ý rằng ma trận G = make_G(R, alphas) là ma trận chuyển vị của ma trận Vandermonde. Theo như thông tin từ wiki, ta có: image Từ đó, ta sẽ lập được các đa thức biểu diễn các det đã cho.
  • Từ dữ kiện là double_alphas, ta có cũng được các đa thức liên quan đến các phần tử trong vector alphas, từ đó dùng Gröbner basis để rút gọn.
    PR = PolynomialRing(zmod, 'x', n)
    xs = PR.gens()
    sym_alphas = vector(PR, xs)
    sym_G = make_G(PR, sym_alphas)
    polys = []
    for l in range(5):
        offset = l * 7
        poly = 1
        for i in range(8):
            for j in range(0, i):
                poly *= (xs[i+offset] - xs[j+offset])
        polys.append(poly - dets[l])
    for i in range(n):
        polys.append(xs[i]**2 - double_alphas[i])
    I = Ideal(polys)
    gb = I.groebner_basis()
    for i in gb:
        print(i)
  • Output của đoạn code trên như sau:
x35^2 + 106502442719364134109363347695169494665206224723879135571302919871347197162528368576046459190173738801441584598201613005115226654589967075243696168650875960165794300667505518784279616831677375105945353405248413775383770339596472437597634612950038247699176338503789901110765623621484205142672104326320567500816
x0 + 101167463165697523840879155236135415366380424009464416331763855106184994633902302674087295255438751596774946284741606345729143993302112286520469294367507812315056318317781265297438013015868686890078715661635388273272226617417231986427962523043300715969264411559608335541462289882989793354071670690306513709519*x35
x1 + 99816305691223099820353394198653556348673685338452752390709712662751963955018291035690933586495874204856425012304440226888304154089937984356244091799405992883850252885469253083907806945264024073842402938150768910238393582861876052386054944373525820386502846106714272089979496347781222903621586813884929103048*x35
x2 + 153947320566716262616994979410188678739855205152591327118109633632831079874904201207623989372460852121565808503574990737588802732830815358621180239941162812988178974481362876713673930653580228231369894797024458703841541697777606681268859123289780674638214333073327446050895932236334966741881459108747047657435*x35
x3 + 46659399542336213068024332009916486689825094553632368218365813655034953704942201817568253854157064388245504166146407757024451319917309905700295786319815343494402735002513497971306030063356005913518426592969826466597642398584629398113879014642476295408885955358537717006874886186944096839620200644124949825291*x35
x4 + 126970603032089926662257849183463154484387763986070588029799255070985240096894601764925666146524415192970609755156080504028700396130098402820906150916788544913930045321434831936552231144039529166191052308107994701462252263094518074205134172570410670618493241431989836612834348355333485705234623653621004090049*x35
x5 + 115508394461131230434265966592562541441480118295772381987049022892631341735888736661833392305223610800354559625226453090363759949922425321895315817754830944546620788649219943405574821438913838372662290595871423729706145914427966586662830609575957494588845127857943228556269621456937457333123492335951880013037*x35
x6 + 67870041931046547730445280063184797432293459597028690348151237822083354786352372718957590792733098879508930013579571650980080382835547822977122585570672306974838997440709110285837607224398908231023960827174994279282071268896069837414435498169117619888694478279062781261004824001371533611247008055205968911459*x35
x7 + 24398553029110400376703693451598141230041748203963027753191289213504745783444037069778370168024500310686272836682845403565282887410606919172609212330959626408043768540184381448069840251571366868345255466778720294684266113055942535915213333508027112834335738683622297868375118088422067594832286774454759842780*x35
x8 + 12183761451807958449093612944496848250760712223750397113582125081291204485939043232204005669215344544643108606104447924194577560518784865889965010974193756466598588475400518141162335642468615029937654929450511699685166375085399707022464256552429379363061684027996282179882233590027951328871071648738057153701*x35
x9 + 136283395600439917762324069683672425665271905977754374625741131631131381571945057306283556066272014713727191603504096877650248392527523580321540494478740292493256825563175718922625778845409304581876836565419832229110077250744626830556637936342385375785528837147746267716392030441762456697992109065716762836048*x35
x10 + 137781388677775019803167341660564763023011205486809068857350068074131777057103291880618696729192482660745136169006276238378360485406598262470209434413326476713818755314175276254071566041358067268989295529524825374661553869756837620775030155881714487194281870539538723842048716551308069536173876572884159145482*x35
x11 + 40022447050170079650297640809819914302194290183536692135687103304165226444531161643718985489156073578920524155702721149712467375112689527001518993125569865857136384760421621984994086354910186848710811862555146167565150643424318406707224495455455163366011675124228370243454814814469803353940490802919570540933*x35
x12 + 120966263786521814150852565413458405789011054034289779641706161373543567247236870407999300175434137147788193262998857460937305136683936270467172487642423515043082666652377496706733346560628844290711324874759575204387651533624304598192790954517777168994380501673071117206104948457691832034877688369566421276268*x35
x13 + 132961122689503792816396489813923533463353337544160342955427114699234305107032411860513530189794430586003314752218764427771069425571581230545144561573353395232729356644428585242872690321250270908179419633138107628038110692315823910364034651326849554101358397266150258020630476684609086641161097523429444286907*x35
x14 + 159279176462545296578864033595509179410587926582287026147036009880694615378965287189294803671179500655532991093569299834618333127739161076476842432855898314443078790400762726706488087765691808008455184565423598329679576799087334897411704546553884360243457644895376211484147015788224880607598286047304839569871*x35
x15 + 34807169980868726384973662496932373459025513195701386614403820227055411517151000671411095813528684636234527525283189460384821010483192915224093633698162756287836721166194219308354937612260372915060985133526124654525090877132302325000590360591346630570436251943255560968791457002066610857941700860046755639841*x35
x16 + 135941728344653619168554218682054406788447973928907913298435906533443461858841620969183570549875126730938204966328461536238552896087878757176993616217297870244396790709012585329415344955165710927389110978839472844878749793985217744019769063812491347152364172608900369021723053049591937966849976280148886515157*x35
x17 + 23022450653512113672763575288134457870864337520509152439208629951172177829969804360160254743445480528009804392118930762486706506600390483535195366718547398013829547169302737942011656985108244803051511900748651994722440069444977444110923567969194631813096457367853783284683870106054183475113035069580343560954*x35
x18 + 109497499101385973960478956409212368393890321828294047706935450802449135737197006780594678597172915930516852803812780034628215320105893463771426189888943007254092358029997308546512896695266765204467861856963664286070650239788165819844446851134019428832918009318674952192115339660095607238715708771569399215838*x35
x19 + 17649284393596838928927278310827176242509215110644386352481639332148633331772347689769852584315177880225227383888817435241415960568928130205087247521716901944147133976065732030250285301530147525056521201283295287128161451737388744898326241164907663755093951709088748838147576345829767478029082772419477723781*x35
x20 + 130320272208550606000162249968811128701555128924925284832865563977090537272377093511217362483670891200613682176584857884689416065597281384854023729012295638738457294788171665924424141182979840209635991697860390277375640005807874613276565064742340398294618866435972420736846325480518954404493956123066884546272*x35
x21 + 39101123999524075418371960194638271743945247842543623447599791358827143617840360905870500131725384519168233959470166267524033392762391083565838093889016408920456075067991209702927247019512513546515882432963122922769961496979348926444647296430777023918416291618593981106143559529205722916065184006818114143303*x35
x22 + 48199732797571512474381843081410642427988233761233604916182072056585349447595749822299392864946822100642530711165709824205455392635027910363323358595484450915165289735674539072077220503789629362663719394601149021693838846631179978798887605892673834170072894903988402483773925234470242983441802495439924061332*x35
x23 + 16665194243526064720137259674313963879120151991839610727414651302673500649858162153221648993343327185421487162449640330009856176853413856967461418999586870355231828840663851832997872589063688637889059215891619469462813800531907621060562700092290619760698514174163532494467026612760958067638436267540689263990*x35
x24 + 52249003167873639497505287660809803154813283271579860201446532098065066334523207283836965218945451995068094803937471963191889335735593020062213461560738874871773486303345263057963545007413379053318379626696793620196796750586781773365596492318231557324461271284760629230781162323519744938214940310805490247065*x35
x25 + 137793160780300611942398684838285079654158845540611353325901027340927100276010203663263055411134425794690868511147162746881189528295180032035069377375788665843850910615210644353422755227661626965661647124191627395094177496527126279657106471221142126683650879012630348182572396862913331654771241074468185614681*x35
x26 + 41913542176762718356180572385723273028037257322465353038962822254259818024858416922770774760302862807725687896509935715213699378001675000630014920308214991620727341310184703667882069399318120877751389776468482619772868513482577491507627658526865403548692237621332762006400329001675838717069103279036559905098*x35
x27 + 62499604425532139090540080719016290220708831784300706804453856969496109915462948489408851823031600962920651951049072871907217297846922891646886703161773184243984497097235420859868105460655674556771640108653411674397899745776925124142023521308515481427652856182154838392133714134935964637738869311200221013778*x35
x28 + 64812852826577729459296495819920124605061016861309162575638214007028018131310793406676855463378160896786059539813356624395559458465603826738084948197251067308637653681669233965783727763766170746923609307367066177475560251316993122498159586658613976593096131912069745844256544973066144266318756517658323906500*x35
x29 + 13930505220178812499334344928142906427788623106541586177912703458685079135242433252765674734277964006514138316612684583911134366015459508476011088285309323729658492226054360270637134300046620962139384065834504865707162953990027570442968896379626667891650442155917667277386210140165597397650993677709524354325*x35
x30 + 163789129881499257485091385047599447721323694888054183410183277442293261052541374857284497237962662620855135939824622988307595075856990986582012720735574514707815264844799567498465207543168009051376756587772897126378687641924329456116477049835116043182077902161326553265532816878880281512813885409158321330823*x35
x31 + 141078286128291606630886906203072934632408661764128821597920658704854485805633020806957657713632945031290388449823774821488941714667731518487834565143893877341057614024612832596966360591884845977083196942329404619897824672205188951576866929732021840241537949541270166963322437279028125919535326441691197810631*x35
x32 + 105847412828833745276717423602257876160277623745479589037842892793027423939057283725332111575662078806330258478369209968258679073128534166930433256734995914750252215493486176720949241044095285350205653833789446170058359729058614890245422133723660613956809251535159590261672237566016682614798340416609229149021*x35
x33 + 45711862805354534906742779943507680355899773895103554341403778288529200700102287317028309961984299852963160384174308242754253285488661259924287664351789425051741871468721865195752710664200735393651489639562227565996851319843150600380563120075590512281290529230858068062579443028375841475355563912246241773652*x35
x34 + 139803356432184693666278113668310134740282635727294542044161753517704900914391647620184933895031484521623703972833683225801039211863739895484987908680664234735385294166422528398624690126736397141969179835462084570613942444022749094252175836602057186156665379674145616238353698127375512970409990421704117995781*x35

Trừ đa thức đầu, các đa thức sau đều có dạng xi + t*x35

  • Dựa vào giá trị alpha_sum_rsa, ta dễ dàng tìm được x35, sau đó lần lượt thay vào các đa thức trên để tìm full vector alphas.
	param = sum([-gb[i].coefficients()[-1] for i in range(1, len(gb))]) + 1
	last_alpha = alpha_sum_rsa / (param ^ 65537) / (double_alphas[-1] ^ (65536//2))
	alpha = []
	for i in range(1, len(gb)):
		alpha.append(-(gb[i] - xs[i-1])(x35=last_alpha))
	alpha.append(last_alpha)
	for i in range(len(alpha)):
		assert alpha[i]**2 == double_alphas[i]

Tìm p: LWE#

  • Trong trường hợp này, ta có thể tìm pvec dựa vào việc giải bài toán CVP. Tuy nhiên, do hàng đầu tiên của G là [1,1,...,1] nên ta không thể recover chính xác số đầu tiên của pvec. Tuy nhiên ta có thể dùng Coppersmith để tìm nó và tìm p.
def get_p(G, r, N, error_range, max_s):
	k = G.nrows()
	n = G.ncols()
	GZZ = G.change_ring(ZZ)
	NI = (N) * matrix.identity(ZZ, n)
	Ik = matrix.identity(ZZ, k)
	Zero = matrix(ZZ, n, k)

	# [m1, m2, ..., mk, k1, k2, ..., kn]
	mat = block_matrix(
		[
			[GZZ      , Ik       ],
			[NI       , Zero     ]
		]
	)

	lb = [ZZ(r[i]) for i in range(n)] + [0 for i in range(k)]
	ub = [ZZ(r[i]) + error_range for i in range(n)] + [max_s for i in range(k)]
    # có thể dùng code của rkm để solve CVP
	# load("https://raw.githubusercontent.com/rkm0959/Inequality_Solving_with_CVP/refs/heads/main/solver.sage")
	# _, _, fin = solve(mat, lb, ub)
	import sys 
	sys.path.append("/mnt/e/tvdat20004/CTF/tools")
	from CVP import CVP
	fin = CVP(mat, lb, ub)[-k:]
	pbar = 0
	step = ceil(512/k)
	for i in range(k):
		pbar += zmod(fin[i] * 2^(step*i))
	
	PR.<x> = PolynomialRing(zmod)
	f = x + pbar
	x0 = f.small_roots(X=2^step, beta=0.3)[0]
	return ZZ(x0 + pbar)

Tìm keyvec: GRS#

My unintended way#

  • Cách làm này tương tự với cách mình làm ở bài MCELIECE (Google CTF 2024)
  • Bài toán đặt ra là tìm keyvec sao cho: key_encoded = keyvec*G + random_vector (mod n). Xét trên mod p, dễ thấy rằng random_vector sẽ có 22 số 0. Vì 22C836C8≈0.01\frac{22C8}{36C8} \approx 0.01, ta có thể random 8 index trong vector và hi vọng tại các index đó tất cả các phần tử đều bằng 0. Khi tìm được các index thì ta có thể thiết lập hệ phương trình tuyến tính và tìm keyvec mod p. Tương tự cho việc tìm trên mod q, cuối cùng ta dùng CRT để khôi phục keyvec.
def get_keyvec(G, p,q, key_encoded):
	Fp = GF(p)
	Fq = GF(q)
	while True:
		idx = sorted(random.sample(range(36), 8))
		key_encoded_p = vector(Fp, key_encoded)
		keyvec_p = get_keyvec_mod(Fp, G, key_encoded_p, idx)
		sample_error = key_encoded_p - keyvec_p*G
		idx = []
		for i in range(len(sample_error)):
			if int(sample_error[i]) > 0:
				idx.append(i)
		if len(idx) != 14:
			continue
		idx = idx[:8]
		key_encoded_q = vector(Fq, key_encoded)
		keyvec_q = get_keyvec_mod(Fq, G, key_encoded_q, idx)
		keyvec = []

		for i in range(8):
			keyvec.append(crt([int(keyvec_p[i]), int(keyvec_q[i])], [p,q]))
		return vector(Zmod(p*q), keyvec)
  • Có được keyvec, công việc còn lại chỉ là decrypt ra flag.
from math import comb 
import random
import itertools
N=164154991219443437626081332614158730243917037448199716655783585386114084944921014678446140961950779185987551082302233189672777124070342896078792406421295367843743938975018623106720031195121691323765575499580580898542615857150538031740984848418002758286176739690774217960569804300041578781846805528383738052213
dets=[121915670423707921083577303353189290105753205383086881070909346847225721867189982304974229518005262154762849226647440342352684619218902684092877409646116087748803226587133413523670397361656258896033054738138430731654935305944293063008598790319170718134139499489852902861615117239766986756325340620341359067059, 63343907682857872607878509945567224921486563246612523881799516305479378868588450586885797937963326267999856247491496316934335364287874172156617589213358253481042121811294542969712559236194280744424138336229118925434936952405022974349635501863559419746472305473002537267130657528843088873920749884958517776126, 59960940183998431136384918539675756934170966091163467968520767153325645962136560671200068950396298697758136800457041389740969533526365341358324980190789364851288082349097074921667208036518844755233710743624208158407186069232568793687577332891891135060205909769204793547540419736438724970172276973830128775865, 108829408922942286612721982361373572260936023961587946486169403040578253579440829820239010566478578127114799035116326113203711182797112095383021696613374475555658419352073960982578022913638292695421891513852370755068743452809789583651874851084460405580493329353438531990864035467217374707867753237831662340107, 136082277584358575685361011661023085616417237875634179263934704936748315191376928549108194130709358128225664890650216073807367168153144412681870265723476036946837931149035233619755229818204514469041841986545121479167294681734086084733870313961011752655615997585957760731230746666214789210698880358229532415019]
double_alphas=[35976734624879755076455546910624448429959110096420446915522201441214317873079403405124151580270840526492943605740690902430682201738350736215988513774269809076824070253694907241328151914110223882223519124576652872065762376686706012584107268294871909276147135161647110820491522435257355439956983009752615225316, 41929841433364620768930436553939939226147302719747291382882277807486429362374305549200095497594235040370231384277903931053038815220394948440924879470334163225467720360310759024975422849054739415395725991044381502099896399361289805538946601577381059204483874844362784316221294954614171482991957931485813308579, 100547449434142104055114023443315037664493224370916362056937424202176345896609659825070877543812641245277367713064783150812199320588918807953955650569145460369545472494020828621888898364519792631370926183688770458407520869099059437179429342181626401659569553655598330646055509026472527160820737739110878236137, 91518817961778584320929039126279744748940103953769587691825178329705657874684773624316790802396345930926479866453006699915520928582307623610252570796031434001820668350009680289941239045917208419522621120759719064705431452247827183573288040180337187496252847995095834948736164779407456177559436559467020385334, 62316109029508031780652419616264560468599678224746561277597239495871703546118491999216069473026547355949546656145458252722781555646204543526902508048762056616064290195832178667018452846264137349612069453286030414881738989809681189625553529633417168200156045463758802482841856869690681512850398316875039523409, 115868161342525675340016896937309904700095308311039634169749090137087394203148654309806058770246045028348096758474128772639352140327181844581828606266074694049857703794539626378219869823497392326000342290381935026784451322642140001480009767807203228335741924648224785785918503256265049290112556572045761666371, 16086560834405282091375940290951278036247174390915083585386080415103993736350578660099670226864434013444530004015833441516838220163021736309205431717757797919540626073067610694184658630046575345609942776979756194618648293182279331715976763919729226448301521700232385776249532055572056475474870551498347728030, 141575005459307021588084407648402988153702745909796771599597295462927640822173091027699074030629995050118609967694014779262804362593505355390827708882415903781314526593437437022053831158358170777498834049655665462591683454287689365558154486615702566762032949150004109884744132239220334740608769900222567615449, 96881895711292971115231774400582898229460336408567734776758234067609470090604415694667705528660502303056465416290085600662914502502270016645468272256428746603430865104055118751958729087395260239043367759492536124852275293614909619610316513008719031942074448810716094916944698789037732837090885679415532074448, 106790085136134347213961955180572211708729366477696958769234639423855807702823293431846124690314000285731409612719017795170484697598119442174006078713564206866451553921734418845045908826920428242369075983859165228121379600218918637536239397782945473882322256902502267962262388949128175067146018338181596375178, 64237262906961704558713375465849407688367424369343725218424070839236770377214894834760852353334968130824709181617670665428260823173116756879922764250032565901197436821471877498699325239185567340767750533646135872024225664053217702144015558413564974731381186207405888531232968979589353771751906766095653262003, 62845783156553851206350291462739136211462687399996526568519854925680224089068999331307309324615852506217424307051301236421767187527005114044884156660463353264083874693002115090219106937478524166594329809826428932604325191007596749751175248988757038478243208003732029215759328248350643856922078813121789237941, 117030644054989520221802957470544223316754221477429313384830717410184079381288539373616605512466270973525163904234474514571509317794619932213950814149168970599650614591685708235719586343718803640842989407200781802763681542792498064507859763859201178412862436952898741837690157537837993053600803399928209734678, 156366374855343902274634752230450681870996102356245930278826013440402993969950080570265443443274003273932288191405152845592060604630242084227534650890143829235103329546227009099250464620722477565211664143159497375030651693013648813090549078032965889189453737288681774185523747899619308430045018844694186674835, 57918923332317241429999668693508499358564615083472227185434676955255005067055207314205601229604081520331453034228032983015010565219224582119690364210253454179396136787559485001396345310002641870106582387641902625916857028008432062866965410953709151596147542058228053948597543939060228645435617715231248352768, 45633193930929828414386713401863625591395174339494220840697768956129688949062085911848804901408715231245290921225495827382953674866347926179030425951255504112350258934116937757723725213384598121993110281669102865940657853326993888288042401577571370218389522174571287028736533158825742323682474835802536159283, 70792422649666366567754147576248420867486437845705497665094426137043507090046528345939602896037615796018531882554934301631351140490726031240908303280642218440637882169304216206729175459114680415606299114257885513450413364790749422389500869860756341506495048757120512268773595226936220544182508732222278438149, 48528739215257516746775449491370718284155592205449296781406474636114784163493916428173000876180431602689043153521923866039433187364592471745282291185306423644670629285149077643915745180340584222712193552744467862868969301721792068326692809656420036287195343609180926543236413385212714979759367088292306015734, 134569284321762303860634420922505518689744753939099682738804438388007986365217787301946543070508317549258231025825489884946494887455319485933135542581575754167204752690545266068858612808635951273453674583175539981840134461552563395007595119982201855624469978938609828692438316950428018485897224891068651221480, 147679586069710037293289178114385018672442214310569713959936800022589099629926627039224231752647558544565329923294749028387571284423097615025816527180620441222332844888637480581314214781577049167634487990854629380109388162894934646784936186158429771659711763611673443977947886079421509532269541866230566384816, 2640766511029331555549302762192903066801360146412802862818670197997816043033834451652387695255947926172390330726798330869554431037755823477547238746862532023213163183851397976865087860787851411977182817279921536193195213207584969196899949683844509275767082132795549123964915110817486140481196733541817010705, 13357619943809643799559678392194537623999021094029705256850828535073926783373843310224931097963524042285281186063624695644026081373917890998427574447259677342225039171886678464500696007657495797659980863970319028520771708434732767196180204317968655371261529129227353616013889761268613375611224778784826150721, 51295512320726308285655892617044514792893204874689759147372214174708125954380509548709327390975133651268661507913077971227623313439957780730176410103965276840497164645065286649306004797095166919501651558815374845229719558290798722715912515080248435836079534514735907613656803755784577377003359584471488794188, 5998376427560150421714174028484574891417111466342296337287788023345021435021212564757979143030557643112137110417668772738220944197025158960854040073572600685339702643156452664232530867996157096871229820522622176782190901419668370973135038556550398643978514476654003573182778309959292325932984254245617216074, 82239885017193812725844819099621700398562610581637521478254777821044798288489732571701634643779727526519063283530447453387911023097101313619227369077691619594113133792630763990200657565002531095229512883190136680294897911445844450830340980050985395703313686662437003998163656938379726130672479115670573351416, 13956251017227024809944306611520986059246784943055346201343185905745218779409265454032938826848460697068216379964514211312640909189185889307730763981853008646182630165812454068795824166680569362828242403207726355369116814150999874110740080127893655756048368131174600235539138067668079374853661184102125786108, 72787616230402759030225880152781963899639486926040981029892476895566710302259474973698729085878950720946918943027689660756398633255975238966451217320015430723703593875403985161634826218839618019096175149597184978019707082137594738386479537034946690628366496660025456545316066709252885826405142277551905565509, 9809691946987375275388230063563503455503823329470161009741811366961048235752126618679612189863570614295540379930321728024786784117653327227290986637662210533316563807592904405872887559810433371553101316520065601891822528011678224033925821986985923499451436047975327127813032032295236440058317622228296171877, 27425804172289095143067474093494429032970216485813136745505270417995570456004156348545593234399744586643675924284965092723333189239876443263975574466972450551368599180929425206832878706286773342943655458478868200352621321860231818152585723066319475740975964305702744839507896055171524733071416651490971536131, 156146840019461214729565635134751218555741695955421153677396116818657467798939644427776916173638376343491383681350144388073180131386840901579960755694322987185882603130633130053805341338854200770799309566383131101246324896209221985972282042344530437757359339213721077320096282472911825111438910542082628743779, 110584252686181967620214138267450550355373618692514793524435448260892563287967748252983906136062800397855215330196749183330014639760123627401390494582660290439744009062639881830832807688227989575319018880558292603451275479217805406763957399401603714429550051157785214893981581952657960140669527317864786468505, 27677932761748796568630546582704763531623156679453363307762465881258667835012015505262877270146428310205943590935571955798207428723434191063474496920745268408764377544314301450736597712866330348919131232574454679059627092682891387698470697377739962384799403773422020187066589714840143262953492550282805352657, 51516993874973208457649860608327755512042548667174080056934496053342648205507409364823022746122029138819703656898320011798739856892411842284597757073674859607231771427530026978782024963959826326749808207050745827368645517231565199017846649984132335888132556619199355021638975432432968719348254372927670791722, 54294270361651122898452893490559207130765777770203502786624646800300240821134536927597147926091634726889574387545873303044731355296099529307087826339173726311055981562139453930012936404573077320978207695065869897869918005459661493024529867530613348550300900414397308386150135682580324135605918750033791632132, 77488017421949167680650215520753126928767880905928831395766001001290459741860675435289028292515941655870102756918755692075509042862685544780818757231993826509316073070482281687133358280492680848369517953787254614558885071303963402032979366660349456698204080296369064031308740423909983963171997659265414533097, 57652548500079303516717984918989235578710812724320581084480665514766887782392646102399681771777040384545966484100620184557550469480375820835096237770419407677949638307513104322440414363444316217820222094332167123158845517554065594143350235467964510587000401186984316849804180678557373639174701202063170551397]
alpha_sum_rsa=30376441743407240457619770605083020358327364593038851898214086311740828847021656591039214266926585578429330416361902674439939768290731416865031512646209598394537835243441571687566707074614160908195797756824313238963968334537887170500635455862450724181328809238140951460590623319709265869226616018482317589780
p_encoded=(80471099449452624968205295751730888524460741553996297992497597657215211697549806913709807262796923948571814530644971883151042150938045734795330359525899049783096035442032467640594153252890603709380603004118743345482915095598365767899846529558283676670722842204387539447331823052215118214114048940047722753351, 90785745775957709252476591404645638324098559928113559116902820052136199303649556842199070850127940890532658087380842276215650216797317023370001822253263255761532630749769947597187374634421677169016346694409691891564946979397283784187859879813700474274197450114466126660085168405420035079580462958565509914745, 5965366785005534515889132637596331970859971476610528592160659056562856697145934611656659705398363983849561018769627895864290612274264606565158744833326896047651669995966085449904961751367673571443429825241823058603791183336087183721727081845120055326789001448697124084900213371321795041907386531929913436722, 31760079729653511014915597037877381887353490294697227756596603890040422064290031701479127384116273140050090586327411371098278341620767616695719894431032102780395351992907941192679611552583841495797391191131754201561001772871761109276859532173258028172938617623609275905686994485875796189990578533003909020979, 41269953752439631684309420756601921374947830901474121521584970891630655126311139950397688187478564015148471863732092921594026467708192928128603063529939599551179353658408125849157666058187738287412557098347523691286572776915611257271707736497627542217926949117043051608106440900412671687417898398648172408968, 134539758908087404459662546174081618407345337970144850817321428416892688906928700692389687136432352645608147775511691146360886418046816767347334532645047625934805966169916656887678698245628195923721294184952613885586442827000420567496973236266931160545858047808479191029912037002002837839671235361190576371617, 59199534097164109971475039026406192507045362952043735645637391726278564979377853940408349137350172146830195643413660165903076781428830194255429684688438247545978237997088025426418599890557646396932048313995283703459612948692145301651463922984944645347822423376892850647287384894246159946205444364857369210630, 142668218994176291107094867409120677916236135272899532569733455541091205865914816997128371735260318344977912254946836903515006614235547968013379933299858739799378172489885666167337130448475491689028769194176457354266832706887925734108799841907754107664862738064873260391423475184056401359791386161811976551335, 29230245617444079758106014481729918809546440702518378842587063667257842712910354001358088859210493491851467812678352154510516854694474187711866787967202923343679329748544406256271118162719235240470082621421834184954476495195983884467978041380189009785363575061159170635061165218009548496336587665097234368687, 28077612427130351475177150833658372048142710976234828693854836970120575417704833774626109687431496684811728536571557405113938178055692505981995145397227070749140856572142429426633795930379908694194139519895017079483240605724111989169161392806313495168661584434370082811275898124623624580355450408631274259358, 76448103435412300926608179088190472615011809978116294716618039961675317533032756785363788210216599766269129023705196036187648497830939394215779401616200550923701771923710743240974704032773674379934364409446538077617446146459334500024683944431983283454040349470541526859545716428532527043778313285284679910128, 108269188925272063962540415598388652539623036634338694129192862312641584520666587383979062314892397468093763578008725486734596212500991617371536115930242818646409355478158365481901063853095085412542527152880836826536041980108399389488811907907306286461495260428234705013798146077552607655447036284355932515712, 14095111009494820656584827499875601696439630472040509228585937371159061579074282442723602384253950471341251736097476902060180086728895295754799731620825936822863993179433854680063959243786086505288496405220584182820955522166484038019124879277745241315474534903540544240126395182755860502041004969941632063141, 44034954309487558014434950569728607699072863629765317505822332782599674014141619044635392294742641496294706892668562745034036406442211455900633915296435444968578964064990807280676445141702798230001246852814342825710953222137864863467448427177410876799970750030062032477612212343459902751758012251171704714519, 145092454710486842489502724712005852536049629211674897802347391925004671189295184110099055235003682967611488073435275438573519340999311894802290601175003017067063465054827249511720391054161322169629030591223223764940784650088159249530034367740863028089734948942881044281891573528150542598319559315025955798226, 31119948216720513479136061432228526560948445331186705049414470835147479515481258611504647590076330317241827347846428347233257984975302095042416052543118246053638312958880712148441776512443097523358306469794102289248911466717817169602010988231689113387296138088738341161697087587573436927135535070329985595867, 113910544536412437906979684084740671235172506108121007747253458960364586211068492976465883633312525402666880083490086668914684952392786164358316197632355210580245424696296070905661302021563078522256728091962416665854963000839549668080384435922725203069566964917484014969034932347049761291800289239172447123034, 138980472456552600105431597101851850174623115389900514646606154329752721985236695108804305716446563934097218727880853244496051957089629538725751610187549106702228057342359475783209043826864576279524843214354385278562428194401996290045141809672319702892635636333342015513111651830161119505450624974471534512938, 99547001998212505235294679506451539263612994846346926640391653094478320752390115245365086222699738926008132583522255353735104363807933086102304423235629109750589713255949437137352112008737253364724947138492403390740852935501820443949714296762150206037582566290610493394694476240189613904837869364602988749116, 128116248118460617542222941309288663909890101740305445086783214999514940518287121235275892456838214525340291585837625323587131782796435735164641109071938614115208387428926940117433366695212520829643624459655067356944324578559507564855546709980496558613684222230004451410315676477132876396815371568645291183183, 125634328319139704686177238413145894582443512839927698324665828925833375196297624525696782242333641072330610392198278682826921370007988857356031809261595898191013291397638449977666993759786510924708864739171723834421119695871826712027234944011249090303523404538694406319713968286387489261224774929705349338712, 43014126347327199476732134625007873637009086447231410782230664180258375295658231878432865318366990840929929651481317540249632963332773666324663637492906226322960151317407544401045354550822048406469872821293941519038308411807305334105320016485923491535330655313617154766476874942536354114396055313272678108330, 50714247647041931454372920173256605796981129712736715434901470296629102639570736250510140594651958385978936108043372742323606777690367326916859093251886722350611321087087208575859978297554165841248882877556552629337192332871483310485006774563091850680235901099168149812208379862405928373712744177770430455054, 99696176739555253009556924676403903294295279959100754438111780351016342433261305918400413594102512024312796884198846085569468445879909151325942848711635073218921350777734121498696812353593003336529754683660008260561595413208269078035261676366340527982900490824685774005160435596605567782137068595698635822146, 98918861969599773325911296078432425147196324331083837119712208201093292538314353072204384690379806975774232816402417305854721976264354820958868496192954669036966910735247731870749492686091886409756691533926441265174109904957528674808951951874732882202627926559346767091117850255522750251236676799538661865492, 79796797021066003933769894676548293860432652437721970661577368791925921390254381086103447420524107778774366365811040475066863973590662049921313503799324043758906731363573523438637559718435449258593380752319883732498983804677925453295153854871366627151026631556331505791896887054831315313465312403093487258192, 106017554059137051618029161069181027517251330144385729137935523197632201512644057322660243298658449804371583006111780382341699054758215824045878374024176412815419290753845491369383165995154307151900868313084020159497373604632053430369540571077556126488005052742649871431580002955237429164780066663278670828419, 51599438013187689115014441414570278339319329143951150377942586775835515747195159219390156915414842484381385182644604556357730271058366667056764092416499070123342477833880058274928704008547833013460272285682031948195706189636264818213416677627924184311474108473562403596199078038886370006760492663488744867467, 46132015805514609160298575829508830618527269068949383302345892467793990934138068955280592193053385926364930984734995507158642584642677310192393801339018946948063548869075986728649085348679018430644078937535628095594993982460985798076497282772665224238543277367743606212986604632894002436245312027589194737891, 126401138189977864234610464974598083837862216453461072374388992110042910011361616181138178359964713526219623529490986794356666568119586853284486711968627535081832950291461068238381616642429429345019096606482292381994277992888656065068924926448098732132896204635897551633695238494270400391939595115526510552399, 10281560500372807074407372573799521881394549683702019209780179961615717342016603632547814108448235297496649433024087808977201140766798457087752435077342372142696332134023602999748114959655036962618960469290325435963210869396609352811647615878959105429808598807082144041314880674683002280719539311366724801964, 137919066308248846311616875335806472199469948624303720484897602054394336279776055900845911641420587041515951438634474181337628157347257533236771328176989320127115749750276792206783890960405851596145947102528554103822819044323637705379928407920109673104435074433910362881046494164589879296430165077747100779668, 145846450560964212227381993169517108441152443037898836602469909724428902009096378733085748189789244945054039109548623990101893131530311110303610025907240729169797748344948250754309618946407306371396572200163722078116791196711652973769232610458081466821612979469856782248420179045056511294747411994451398394941, 99937982111959810492662783532951188277701710760388504517160775739370191416248823279036221559793783585936444076178125957769143547719063404547153951825511074064739112553470180338929908361578454060689495265982543226596568177069303575723143017847107225559886026066494070459488379119776783720807730297405064248675, 149119278796268131265018313368050492456775758545603645038994609412380215491006639827036645098730433126610579064087071606399683790835721713308556666762069586261279556445455599248690711721297326472450379671172354368547370232416506441153106741019309922273832474333593057836698019114078935800429338889493290221474, 129500315175863684585786657749872353045559334482767613816680003271238079548048065045747411490432670510493319509044802400133680469511477375147073458653233176666609626591994763097434777050038938247789062259664789432895686383012873640552540942192037124133822474432941730079278253683433402163360351643891557449197)
key_encoded=(76704451833336425538713426431421069765487507997951702075405229056526479923448290931959496666748428036106544166557413697450189500863720585442784328912933804534608933194487567933592823089237532053535843319946291738770043588669048281263739612069832072688120184620673988050942640268485370522945124952201213333656, 149761724521319321701683921745638703539798020929299893640337638944307488032669604816778197271596279479609799688012332749565237835474830450361091973667944558109099396001018338097725561323422673672208279632456910399814318665104286178559088309736994668725226115994244804568178096004359287610174890705293056706008, 64266244358847249461289790457574291480524072987759266218757655247124992116978859848297614015756514457875140418862051247490813455913312868838917932880264346031212900634221078878226546876418640064598831911579123839165120465364206159567390610669455310538733729062637769842019684459337611542033534399481724470112, 84871626643611842953174939125607520766622786203262687515877490427188787260981649877080982659686767307165543976576236117351526611334699238935853440011196533316103235850166192612321320295477499001019273314633242187493999094145573886873527704714516795651612991093481514572362451658593344347962882429480340178200, 72298436622346843766968433028513715848188273045687556504293140992152633751964163818578696546632794794195383619270989418883434674393045103129872155420186945590632839913970725772602998689638551948180293746387578644625345120244831799234828666845498824014978913893049575643127345163038268454883207367157742695253, 134253607684057553700547885198292104061360185988665327462071433996167343128420972485432829842258242896050663356007353627897930262782428179001461743730785497404288348539750634861379311800511211622914701747760638225374200890321227494575398839898255701271146194499962911674927310515082260210500499779339783598155, 106463100508483737985745961120940712638110693982061567805515514454867552296824109947006429543007582000906381330404259058230547852021138897913134749698744287360633910577636961158937612005339918963181883151642513963483655451533423079356382788424609354924418985067540039622429962057402299680479914313968923730605, 76907169085856562256062975847508800538121892994730614001973122876771418407867519834641271811837307658020983789074364586616227975778003905906973827585705130339178850390653099540233084272789328783712616718041675207238652724891224751042178182454607831332180161213908138993847269481694256088816187421186562892669, 136265701759067443528409431798971967320011753179240159515408896324451176393662178295284565340891393225741595403812063195921928111656151659467329546354264828003334500590400145431255304109030893425086538148925039386309430745952858536658736809815454061174541933807856062369819110317681291561671791017729232652767, 127067774167762843700750307200704195020810989797064375709113484960055006924628060407804848582012387771395613894518823181147441046213582274875098903221285380221942673871884013147969214632693106064188338464391915663665144377225365471418322914679005998678681077045593415116162566405176058195084494644632945000752, 71888295025737721604356562221525423962536008223297350115014283531447916080119453228836519155653207511592746548984630896267715339110771646173680927634482506920325784805521148160143724020132502803877311731863963747934605100431193584224165695596775745816885467185355252739440999363729513749108261281847900405139, 80854063813740570092632421058525147785609703609053423372606443915339094457122325467824747808681094410564692746402208496942959037232977629402296020475096299673456731629167069474708124517362842855356175707927663050995832585396070601562437629260901154561013963839844123102919398742793144565089470064048987506009, 38301641448059630089959590622564998196751518576964070736947827124033723462081758596673706923128254188724648087582450482865731792946457087582151938121411877019899594624443696551754045706997214821505923276835645006187974213494467466669045305727374235336957621787295928134232426614663148091177593812093638765913, 65495087155590299726385084342458931937782542872110838766539481280007476382315908938832504985106308991284859245548438686541486234366188152770276987108606816536268457209053530866618743989663715917008846124033437453842831021959233141221127249152891452170021303841826096749590245057625680354816975685475558861492, 28919763047505361156482237586776239944273040460456210687183141770538058713467835984315176420076629329234892945640250981931937548617695251948016894955919717292391650130365776720189819627884053764814346538512177659459442533421236320279860091048223702631698474791280824555213668366240275223020760437161454189171, 77059639123096187703486451454097511163372101745278927692251119049930336201732996751702912282630344228642312479433272692271050946267820833945116510902643644502377649093469763106058542957273262433818090666938756469624808860650884570437528384599255529627925731819242003636144110290022246589085383989355528969858, 91889275896310353880089940804552622660650756378844602245174179021149522821169662152009052009788144267450472672439753943217335174845420816278819536000752797277839355014503328252631377282432562176151021136424450754077677429143612080759253159034279320323450515741612663468478179706755376639567371172439288287923, 25242795192083011389690942302023478809108768972884919973250187015881968328956115785269908930647825675449692117580024174248791062579792310965238206446601123051482970278998772747266052690115125421921288078975019479396831521500654023014191471975576498675737057475048585343565387970508265889690411607512334145984, 129483156275628919045068843910344742452634009853786810947224080028111426034004518795335338959165055879455186330976620368854579468497090766486038707694399687913687519074384468509496890836567056356159313857450234213948043650074493112096833906165363180074073985807407567563001385885850515197061156634141788214104, 96205536832301614228542622457865608379171522838718074376622339511222565676052146989267587083399499161872161455915145258558722587580542455339482440721363899166148236386636501172286111572267712759665877802843312173333404607230101502712504060863027290099443336672723202145748397970170298672418650914453569496480, 34214123818957027487235696165456788275122830433775370926588297071920848097367879775077647056055155815137433678804051229927164948818328785307889860480901937051145851130353074493965192373966908843566789841612394158728193096913271753729424954106193911551638199928045601800797792769451642861799254913080877452089, 58453998837137792877927822027054877456323891294944545218158805884472798788849061534149993577981670358217497109694766840679008027028317573869896598392700276580063824575700483419080413997755816203512526330953016741034960352885988710734471812974374429311167632156219016900889993909604249968876560497174599100986, 76808339877577161930570052152108758154683851354663227121285097131140749316302938492853193259436153158132309468690398975483277001982397783211313472166367543469610028445057958548411009023169859321679289806716265477397578832569584736145432700319763024675450237296677662759453829795224021419404260244288916473611, 25053688173095091949405065786991138801960414066093024733236289606864660177971198439198263692564931372606721075454651128106418672298013310834701068730144916992752719620619875335527842250958405897770039541820887425979254725158557653395178119648595193202023111136751688342296371351990179311557018384788206831528, 32424274883869564925790140288498473830983560445056702342488740641169884341274056208014383972386264726136046702765838648005703824879538238456853559702277447994098059604285259473139073228584112125595918926490189795891479767520976306684408188305376003021497396702605873008972130464741822181999751841650309689123, 134257014938152895322424925946076829566706358409006636878618175853547371390955126525150852433387811344940973499514422225104796362680188263359231547118901194083821747207822173450244175421087507551198340698977070951169133175131254738372199114111012977159352518242275021357619599731277645700792289154373144108186, 11215075664875243138148403065135421928804599126381024390890549553509554552370709194535922897375053006709308147573721831668095049316429179261979881698863970291619030585654036248978091467507086601332716768843126874831773114868028691357632203523272974552461833817023679263512264806759671092387187411996198137682, 5330036745470346120935902037041038451780785020343674900454075964716031796686173576529578530873797758496417347502662988138294995119950548166142570479459138063802407552952342537317346878678968180843852658575847637390666138327777764295893252793189523281931091103341597506200703627254553764907357005843567133559, 17617336526675101338092420801183690990560271557355607459044651092902587895170613851043844704590400080525325529761899479020091160215244613880923054628297111895771396828021086608361694280881239327958742392940374518060462645967667769318667205663279004203996825896212822574717882027199873745965039614821475554078, 91057523774689545709233022720011163007405589788778964784432423638363950393584486704781627020700227005133236097123348446554298242183561091739857590519485620266300795039617480675240056657475479881210901574242149538265045273640590523751797666680168537089462232597727882709804435168791893080355218744640941558468, 15001417866949649838643123667240907764404661842522385593088786586374514839139643844061168747108762751056141090110032816023176060265663012438050816537320219278476854874032410679940097404049958976091575264500817359479553266795117409998328433902940343589829871676736734718931403814505351358616434941481456232909, 145819066124732541043717544054700310546056529912569133450585346323083818808264397495172780481687060805190691436305725169311934071854529682012708140045348839626950731728499009922031205672986242857987792715698419292821309463125246971899460467326849832872971616638501798960669230958581718110612388845455129164382, 150652204632895996999954449201970184498805985347817776774858699178504376091050711224227581855584653629915707887588415918920883023848269022049448333798740437073534136889875717369319995745338664799630034320864093430859053088843571274857588314649877111704096399768421585509155210712177053699818931225912938081786, 115876732699846874110668745722046281157743035259730623617778606378847308744841773135917465033570847055141227718059128425734479323445115851311322399608811967370319428614561344811318495759746029733947656399797755298945069785442800579784259372062514025040099570470161244531849456035840394751485269479931063953770, 122805959244041853046688913145020181212329972081953394969010112779295820655709702323447328304248313063494772403682600167285355074747182890596944488496564283674465642016209562449913064367429643540374717088360929282152475527209557246904824769542336887114800552292678187426408902241602543236526522851617472814523, 161057698155174109215543668628268941051233925055577515300028938528029990285986749627195675947726516271271228281180724143007120008722366109155554261470482841537775049847845968965485525399747887417298657787173257630517340643866739581867888234688952204127063632183105719544811286422800035461602338614550271278274)
encrypted_flag=b'=7\x98\xba\x85x\x8fx\xb4\xd4_\xceN\x9b65\xd4\x04\xb3\x96\xa3N\xb4\\\xd3|\xc6uoj\x05\xdc0\xebB\xdcG\xe1j\xfa\xf3\x93\xe7\x9c\x06\xc1\xe9\xe0'

zmod = Zmod(N)
n, k = 36, 8
def make_G(R, alphas):
	mat = []
	n = len(alphas)
	for i in range(k):
		row = []
		for j in range(n):
			row.append(alphas[j]**i)
		mat.append(row)
	mat = matrix(R, mat)
	return mat

def get_alphas():
	PR = PolynomialRing(zmod, 'x', n)
	xs = PR.gens()
	sym_alphas = vector(PR, xs)
	sym_G = make_G(PR, sym_alphas)
	polys = []
	for l in range(5):
		offset = l * 7
		poly = 1
		for i in range(8):
			for j in range(0, i):
				poly *= (xs[i+offset] - xs[j+offset])
		polys.append(poly - dets[l])
	for i in range(n):
		polys.append(xs[i]**2 - double_alphas[i])
	I = Ideal(polys)
	gb = I.groebner_basis()
	for i in gb:
		print(i)
	param = sum([-gb[i].coefficients()[-1] for i in range(1, len(gb))]) + 1
	last_alpha = alpha_sum_rsa / (param ^ 65537) / (double_alphas[-1] ^ (65536//2))
	alpha = []
	for i in range(1, len(gb)):
		alpha.append(-(gb[i] - xs[i-1])(x35=last_alpha))
	alpha.append(last_alpha)
	for i in range(len(alpha)):
		assert alpha[i]**2 == double_alphas[i]
	return vector(zmod, alpha)
def Babai_closest_vector(M, G, target):
	small = target

	for i in reversed(range(M.nrows())):
		c = ((small * G[i]) / (G[i] * G[i])).round()
		small -= M[i] * c
	return target - small

def get_p(G, r, N, error_range, max_s):
	k = G.nrows()
	n = G.ncols()
	GZZ = G.change_ring(ZZ)
	NI = (N) * matrix.identity(ZZ, n)
	Ik = matrix.identity(ZZ, k)
	Zero = matrix(ZZ, n, k)

	# [m1, m2, ..., mk, k1, k2, ..., kn]
	mat = block_matrix(
		[
			[GZZ      , Ik       ],
			[NI       , Zero     ]
		]
	)

	lb = [ZZ(r[i]) for i in range(n)] + [0 for i in range(k)]
	ub = [ZZ(r[i]) + error_range for i in range(n)] + [max_s for i in range(k)]
	# load("https://raw.githubusercontent.com/rkm0959/Inequality_Solving_with_CVP/refs/heads/main/solver.sage")
	# _, _, fin = solve(mat, lb, ub)
	import sys 
	sys.path.append("/mnt/e/tvdat20004/CTF/tools")
	from CVP import CVP
	fin = CVP(mat, lb, ub)[-k:]
	pbar = 0
	step = ceil(512/k)
	for i in range(k):
		pbar += zmod(fin[i] * 2^(step*i))
	
	PR.<x> = PolynomialRing(zmod)
	f = x + pbar
	x0 = f.small_roots(X=2^step, beta=0.3)[0]
	return ZZ(x0 + pbar)

def get_keyvec_mod(F, G, key_encoded, idx):
	G = matrix(F, G).matrix_from_columns(idx)
	encoded = vector(F, [key_encoded[i] for i in idx])
	return encoded * G.inverse()

def get_keyvec(G, p,q, key_encoded):
	Fp = GF(p)
	Fq = GF(q)
	while True:
		idx = sorted(random.sample(range(36), 8))
		key_encoded_p = vector(Fp, key_encoded)
		keyvec_p = get_keyvec_mod(Fp, G, key_encoded_p, idx)
		sample_error = key_encoded_p - keyvec_p*G
		idx = []
		for i in range(len(sample_error)):
			if int(sample_error[i]) > 0:
				idx.append(i)
		if len(idx) != 14:
			continue
		idx = idx[:8]
		key_encoded_q = vector(Fq, key_encoded)
		keyvec_q = get_keyvec_mod(Fq, G, key_encoded_q, idx)
		keyvec = []

		for i in range(8):
			keyvec.append(crt([int(keyvec_p[i]), int(keyvec_q[i])], [p,q]))
		return vector(Zmod(p*q), keyvec)

alphas = get_alphas()
# alphas = [20699149574752913792436557705010942629154911271205172065385826948364639960787437401101493345324169406709183999966011742313956310318777286376146786823806307386844260907697925565506547244586010661999012771338879003614060887923260021133827208261603776539137351617568600271345399446140347439370380887540882029108,113437764708580183961680504013408838601775043065278800256542222710584263409127797565741672835534673453713448323759865945306816040191989397523138719009422328410717280198395923769529231378383643784821882067171995295789803747424698316135100362115751598985040865532431124381139484444317824768041972715765339554425, 57087461768292197401399017615467895913026526605609250833453411152610530260819701947498311297696654315653906366768105507684268734138243310574256147234111289822407433724044372623473843188080399160828387669914452040645492312852884504450212708787492790324489328700181360955151815580825689070652808128409085517784, 96710785300356464912333580664589705754266751430193513783104678607538513155126804366977768822520431830963444278369541303891116904460068287520322517453099330826707940787987202422668583783216309116987928519817867772254146987052165647405418596875386877935964715835699656181870084375766113597401663497090752976716, 136306397478870514999460335913040421184819062565256880050909842182704645035199980984301591163263255562114051664904445344243373930287434737974991049734333912437611569757219745537960782436698977139286591288738446295525012579845951858169020257910837021744602849466817954661255474346705339821975460817073152990817, 87035492723575260746729436967950740427768109442016706657221165072742625415594643636327846909150555547629858742445937191278414181030347268053276967860879298546647871735855746964504201325338449101595995849784010448559678646464889113077731798693564155052966604996504548503575491063881147722439666051030860889007, 90970853414258543808471599241719100538555871257648870748147898724077444349212878291679837917375471238968266357918351118723451743481269680214541636826391845409716475558879561698435547733743696591434122220028213386638376285710098061700696965222132908541752575537327815306351847278488641520570527505478958874880, 117995138119833001934079611961814225238357405589155663915989284544604863977252238076171320872962791921313429462025377439884409756395880691693315602108061914953491340460119800691279120173648611932624709182633800920623087445167099562794129421239968029925065485021187557265516972088438753328667556884355858222735, 130368913082631936562889776072535857531419112032138393848307004079080306087585543569808000359939558784784634382833443386939677124482146663694933032152582807102006987969671823517373830949093826739311903957624315363589132512322196710279039193867872688675263627241326315573193408361890357247892349359149923429598, 1748363759955059175038463467581104919084781997194044355534484228438125966341125118678496839036196562903921755659417896390115441529954667012074668468801870210527034202681994234325563220258553441929045926677620943315695631715091428526287347471031900899024747680926031079784798276267861768505456805362784768014, 128022084874849864110438454574899544011732130467902188042017220176382841368103692774751210195816148464949734397791800069515233837508651457117677591234351262499003745400876225344761321762960822636787920641947379688368669747777426198233459672198917596769255676429932905730087138881641244754471562324643961593625, 148257854270746306642291549136224287346529730820604157813402582132928819555388311304886225326367977027179192785842733119077829575287905458626591732620081344695785315540139901467360163847107077562009898189184878486197292620768469025880496523415463723061170386408143842395729014872952151303924502492070971276583, 87276660728377394778430729852903385829315066930544859268033399932207687806442042198984476106007478598204913604652798446235733481393376036173900921700703801809274045613745667664692505484676918360041917041329670473072258301916460548063926664920221541330208152071650756015632719586144537680636205137319786428225, 65037829072395969381150223789165375812151397196149646550511853307104279271837354375832218723095814036724666390229745521462234567562512915279681644299173542892673688054345495131047017569873242102282324147678325459162047761636856232755913600107675553351477942606325276217885792042342291495405148339630568205235, 140144493162352295771887684188155435990928540592044022320175345811725024357469259455531619307546382976760380406145701005947852380368051600841631724823838835150335607312890729071727166550832316503641395905988192230610306647355163468037975727723431159952948377017952003018510688551981911260068386335667630875610, 72334920877735849053803014122329252558890214823980916146178931564277092649873183462472305114812088361110346799942392499960768698550668140324677416007825007489611689130157216622423610654197762524270824644625979759416956183601066157843370357004333010186317185915869740475688972749162229144207803345058217126561, 126467654924937789997884151187838193527086395020214089637291211397192481248995001562661972611130279357502863417812854358270494065530652114609680806489649545728022479169311410817162022485380871231324410412829797328229539702630090330021510523545617629155214720042921604163439744723974314098347623044630789763887, 131226807154538141540062345993486564523241441272996091331061103739869726945441408558067337200462066683749813366395208276536549314757969280616299377115794823790027747240699093199892265585036618703150216466199423234492946137163944761228937090533789909034632932103970593928239721933972405036674525211472740494751, 72421575467684783948355087545067740430129561744826943443305062598134679219257315742717399012211859870176454032868314427918697217076674667503488795688868511534355768015295893297000601883202609501734055276146809392945061453677028771986686829709703128192523811004593425083578972563318784955306931294544436506081, 74089355292747671729154168851053270032888554107597350993727403238090168036319067306398928070907811777191482674251351922480240588959565375322009466167562897266942186611765259619169069463954849269659199775097227457868183588648947056507273740343845260613439926927320617100479739958212508463734115846058960564185, 65788443699552310522835369469102197826928840643683353718810370541234990411867173118967480420872736410710554010898043178696108115503306603434185039106673565783671973706387565987571238597326189597546598835913975172467649717233110733304689474804168629146241973836151440832600094307778222342134517723638038740033, 104913521583136229330345166634412707926755453952906732268843135431065795512303887235612240698778079828778311315584159255361720212579007247064381689243088708775891100607147359331613669551537427783530235907329863386632626603115987195814690139819767580405426308147906363220830107658044485849319096979431403948200, 66620137447662354854047514327431957840507381052394483006877222060943187157907408546337963785899093169350598392172926444579068957323728790537496565351073140628626327637451313034317370604106290863205214329013272924337714944268339873063768684384444596011876591644906705722930725234736425384033898588904751715475, 158173646752250566155655552232822172820873412000735165839117807554880633563821094145723804179533513794987676340031052558475928267290150906947510235789137458459791021713991055485476220063130724258910299814144830653205411477317283772820662224834956004613442488646603623364098231043557326711151957194593151943556, 41652238796062891007217549824240736860621646138206177488236167227288741924003819228122049477765188025183962922340777288845571348665411176084822329707072485646607759285688395293467378868762968304015028302360175281170423505028305661390936567814575299615423337308934841692885711509659029712012652232078090585436, 50901825266924910692424655680719669018973857208083348400544077031321655462619420066562494002946657494187726408741021423296527967342904022316985917530944725050007367887541899919796086058813320618538194561071467595105288671339375684498143982168889430347756990024622435291857992337053036491317680269305078107656, 132846331162799498047094614326590180887064417593037157928038413330357752483347979669452078248704708442147613415396683042279382809313538662831836910349403286418924424378658703468729918439662139091571135281599034604619006406082833178887779665969147893358012463619942353514119646627879724700673427567072959609915, 51562611789602276387919140845279465917662767108943084314601076920963249946641754523486434969386848622508893161622841363409337607321137978827194704580757770491959759882996522659526525719629111082947909444888236065754727579702525101299508997573085888552755086301205080076623709026033675889869013866842123491653, 40134669013602302370294036367132465342846581865432625994647728036270465141796841851128355934582503547316586041057485220381116031855546395603527099167290823383795882986131479584562012976995846767342018958821922046107036597795119071136087001059512074875837444646618143614164944844340595978855348810359254113617, 100358267795585936816033398761251376663696815311681489006095639961720448313473979634385357883005488110399665224739708868546629823254260064599529948814737912681448655999613133184167769749907077242120610953466654281539004530652470028837197084276740000756913773614776344692969158182811999283712759700973294117095, 132514462780969683168121984679722827545427235403785774464266459122549432566079319206864909343467902029306200501919986189194435211943114837743016742821097124779068426359298538591199584781290508854398372805788362803897367094893205852941184504205125709864736668312719827638166312806351289489422281697532244930587, 91200993244244696976394468546138723683603443436651866915535520070837990263747620844264538614780093375946244058114430166035540096004734188878265654471180100137838909699400765171837792227270228117846654612262165610176994722599063799203828330989990492367288008351400023771130336913090800805705711982181438604679, 33620782771024142836250168187144887981294099836011161591187659650513641221085550798695343288334416818380232548965362640864259352084789815862797188178403012220704718811832680675030824890191677005075691636701898731158196154350127843948515018118326222952220717362128985817233839272309864666323127971549484773865, 153662020588099711056553359860888316438302022829320541005490865075606527076054389251774653215783169557256591298842102021519616664848272890030178825215963131745827283105814817579009732316292576009855990590813406346347072872050792845127641827736448322776462336740891664510017151820869604453989965928434152771454, 136282132216514738905978417815194961433991431272538689105833304825462783710839902238129358862535601837066897817182315797880586726464355182506745964130257238459992558834645608839519363929954632615532893058531933349141451704824618032771292347915988687316793795838432363494729243302111295693973916461434852504858, 157158480860881128942242345859388203041798321724396284345609554312371191787800622789195594842987102309324137663050404147853315103748223812793629602071870102239907304551641000803511584465557848170886435373291777195279429440616707499103200431641178932902601450511084209643627763684070798626508442372434096123543]
print(alphas)
G = make_G(zmod, alphas)
step = 512//k
p = get_p(G, p_encoded, N, 2^1000, 2**step)
# p = 12565690801374373168209122780100947393207836436607880099543667078825364019537227017599533210660179091620475025517583119411701260337964778535342984769252959

print(p)

assert N % p == 0 
q = N // p

keyvec = get_keyvec(G, p, q, key_encoded)
import hashlib 
from Crypto.Cipher import AES  
key = hashlib.sha256(str(keyvec).encode()).digest()
print(AES.new(key, AES.MODE_ECB).decrypt(encrypted_flag))

image

Intended way:#

  • Lúc đọc write-up, mình có biết được đây là bài toán của Generalized Reed-Solomon (GRS) và trong Sagemath có implement hàm để decode được keyvec mod p và mod q.
def test_p(p, c, alphas):
    F = GF(p)
    alphas = alphas.change_ring(F)

    l = []
    for i in range(n):
        l.append(F(i))
    row = []

    G = make_G(F, alphas)

    C = codes.GeneralizedReedSolomonCode(alphas, k)

    return C.decode_to_message(c)

def get_keyvec(alphas, p, q):
    R = Zmod(N)
    G = make_G(R, alphas)
    from params import key_encoded
    key_encoded = vector(key_encoded)
    alphas = vector(alphas)

    mp = test_p(p, key_encoded, alphas).change_ring(ZZ)
    mq = test_p(q, key_encoded, alphas).change_ring(ZZ)

    mm = []
    for i in range(len(mp)):
        mm.append(crt([mp[i], mq[i]], [p, q]))

    return vector(mm)
SECCON 2024
https://tvdat20004.github.io/posts/ctf-writeups/seccon/
Author
tvdat20004
Published at
2024-12-19
ISITDTU CTF 2024