[K!nd4SUS 2025] Crypto

最后一个把周末的补完。这个今天问了小鸡块神终于把一个补上，完成5/6，最后一个网站也上不去不弄了。

Matrices Matrices Matrices

这个是不是叫LWE呀，名词忘了，但意思还是知道。

b = a*s +e 这里的e是高斯分成，用10000个数测试会出现2，3但猜也就是1，0

另外这里a*s是反的，需要转置一下。

from sage.all import GF, Matrix
import os, randomassert("FLAG" in os.environ)
FLAG = os.environ["FLAG"]
assert(FLAG.startswith("KSUS{") and FLAG.endswith("}"))q = 271
qf = GF(q)
m = 70
n = 30def key_gen():a = Matrix(qf, [[qf.random_element() for _ in range(n)] for _ in range(m)])s = Matrix(qf, [[ord(c)] for c in FLAG])e = Matrix(qf, [[int(round(random.gauss(0, 2/3)))] for _ in range(m)])  #噪音[-3,3] 正常[-1,0,1]b = a * s + ereturn s, (a,b)sk, pk = key_gen()
a, b = pkprint(f"a={[list(a[i]) for i in range(m)]}")
print(f"b={[list(b[i]) for i in range(m)]}")

q = 271
a = ...
b = ...
A = matrix(ZZ,a).T
B = matrix(ZZ,b).T
A1 = A.stack(B)M = block_matrix(ZZ,[[1,A1],[0,q]])
K = 256
M[30,30] = K
M[:,31:] *= K
L = M.LLL()
for i in L:if i[30] in [256,-256] and all(k in [-768,-512,-256,0,256,512,768] for k in i[30:]):print(i)v = [abs(k) for k in i[:30]]if all(0x20<=k<0x7f for k in v):print(bytes(v))#(-75, -83, -85, -83, -123, -73, -95, -103, -117, -51, -115, -115, -95, -112, -52, -114, -52, -109, -115, -95, -109, -52, -55, -55, -51, -114, -95, -58, -47, -125, 256, -256, 0, 0, -256, -256, 256, 0, 0, 0, 256, 0, 0, 0, 256, 256, 0, 0, 0, 0, -256, 0, -256, 0, 0, 256, 256, 0, 0, -512, 256, 0, -256, 0, 0, 256, 256, -512, 0, -256, -256, 0, -256, 256, 512, 256, 0, -256, 0, 0, 256, 0, 0, -256, 0, 256, -256, 0, 0, 0, 256, -256, 0, 0, 256, 256, 0, 0, 0, 0, -256)#KSUS{I_gu3ss_p4r4ms_m4773r_:/}

Lightning Fast Scrambling

名字指出是LFS，但有点问题，当一开始使用时返回的直接就是从后前前的key每次8位。

from hashlib import sha256
from base64 import b64encode, b64decode# utility wrapper for hashingdef digest(message):"Gives a bytes object representing the sha256 encoding of its argument (a sequence of bytes)"return sha256(message).digest()# utility wrapper for encoding and decodingdef base64_encode(x):"Encodes a sequence of bytes in a string, using base64 encoding"return b64encode(x).decode()def base64_decode(x):return b64decode(x, validate=True)# crypto magicdef create_key(passphrase):h = passphrase.encode()h = digest(h)k = 0for i in range(8):k <<= 8k |= h[i]return k if k else 1def secret_byte_stream(key):x = keymask = 255while True:y = xa = y & mask #返回尾部8位yield ay >>=  8x = y y >>=  1a ^= y & masky >>= 14a ^= y & masky >>= 17a ^= y & maskx |= a << 56def scramble(message, key):stream = secret_byte_stream(key)return bytes(x ^ y for x, y in zip(message, stream))# user-facing stuffdef encrypt(text, passphrase):message = text.encode()hash = digest(message)key = create_key(passphrase)e = scramble(message, key)return '#'.join(map(base64_encode, [e, hash]))def decrypt(text, passphrase):e, hash = map(base64_decode, text.split('#'))key = create_key(passphrase)message = scramble(e, key)if hash != digest(message):raise ValueError("Wrong key")return message.decode()def create_flag(secret):return "".join(["KSUS{", secret.encode().hex(), "}"])if __name__ == "__main__":secret = input("secret > ")passphrase = input("passphrase > ")flag = create_flag(secret)print("flag :", flag)challenge = encrypt(flag, passphrase)assert flag == decrypt(challenge, passphrase)print("challenge :", challenge)

由于flag头有5字节，所以只需要爆破3字节即可。通过hash值判断。

enc = 'VERY/Rjwj1U4DQZ/zyyHxSsMY1iYuOZHs//qWPVYInUz/5cxidrFCrSqco4bbVLpWjHHI4Z+JZOwOfsT#SUS/PDQPS4DlVum2aO+5+SuczHag7/rnYMBUr+pEqEU='
enc, h = map(b64decode, enc.split('#'))#由已知头得到key的后5字节,前3字节爆破
key_tail = xor(b'KSUS{', enc[:5])[::-1]for i1 in trange(256):for i2 in range(256):for i3 in range(256):key = bytes([i1,i2,i3])+key_tailkey = bytes_to_long(key)m = scramble(enc,key)if h == sha256(m).digest():print(m)#KSUS{6c6673725f6172655f6e6f745f7365637572653038363834363137}

Feistel <3

这个代码有点长

from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes
from Crypto.Util.Padding import pad
import os, signalassert("FLAG" in os.environ)
FLAG = os.environ["FLAG"]
assert(FLAG.startswith("KSUS{") and FLAG.endswith("}"))def xor_bytes(bytes_a, bytes_b):return bytes(a ^ b for a, b in zip(bytes_a, bytes_b)).ljust(2, b'\x00')def f(sub_block, round_key, modulus):return long_to_bytes((bytes_to_long(sub_block) + pow(65537, bytes_to_long(round_key), modulus)) % (1<<17-1)).ljust(2, b'\x00')def encrypt_block(block, key, modulus, rounds=8, shortcut=False):sub_block_1 = block[:2].ljust(2, b'\x00')sub_block_2 = block[2:4].ljust(2, b'\x00')sub_block_3 = block[4:].ljust(2, b'\x00')for i in range(0, rounds):round_key = key[i*2:i*2+2]new_sub_block_1 = xor_bytes(sub_block_1, sub_block_2) new_sub_block_2 = f(sub_block_3, round_key, modulus)new_sub_block_3 = xor_bytes(sub_block_2, round_key)sub_block_1 = new_sub_block_1sub_block_2 = new_sub_block_2sub_block_3 = new_sub_block_3print(sub_block_1 + sub_block_2 + sub_block_3)if shortcut and sub_block_1 == b"\xff\xff":breakreturn sub_block_1 + sub_block_2 + sub_block_3def encrypt(plaintext, key, modulus):iv = os.urandom(6)padded = pad(plaintext.encode(), 6)blocks = [padded[i:i+6] for i in range(0, len(padded), 6)] res = []for i in range(len(blocks)):if i == 0: block = xor_bytes(blocks[i], iv)else: block = xor_bytes(blocks[i], bytes.fromhex(res[-1]))res.append(encrypt_block(block, key, modulus).hex())return iv.hex() + "".join(res)def handle():key = os.urandom(16)N = getPrime(1024)print("flag =", encrypt(FLAG, key, N))print("N =", N)encrypted = []while True:print("[1] Encrypt")print("[2] Exit")opt = input("> ")if opt == "1":plaintext = input("Enter your fantastic plaintext (in hex): ")if len(plaintext) % 2 != 0 or len(plaintext) < 2 or len(plaintext) > 12:print("It doesn't look fine to me :/")elif plaintext in encrypted:print("Nah, you've already encrypted it!")else:encrypted.append(plaintext)ciphertext = encrypt_block(bytes.fromhex(plaintext).rjust(6, b"\x00"), key, N, shortcut=True)print("Here it is: " + ciphertext.hex())elif opt == "2":print("Bye (^-^)")exit(0)else:print("Nope :/")if __name__ == "__main__":signal.alarm(300)handle()

16字节密钥分成8段轮密钥，每段2字节。加密将密文分成6字节块块加密，块加密将明文分成3块：b1,b2,b3，然后得到b1^b2, b3+e^key_round, b2^key_round。

但在最后给了后门：当c1==FFFF里会退出并不都需要经过8轮。

这样就有了爆破的方法，只要让运行指定轮里使c1==FFFF即可。第一轮直接FFFF00000000则可根据第3段密文得到第1个轮密钥。第2轮是上一轮的c2和b1,b2如此类推。

先从远程得到key和密文。

#-------------远程获取密文,key,N
'''
i    b1^b2^c(i-1)   x    c(i-1)^ki
i+1  b1^b2^c(i-1)^c(i)   c(i)^k(i+1)
'''
from pwn import *def getenc(tmp):p.sendlineafter(b"> ", b'1')p.sendlineafter(b"Enter your fantastic plaintext (in hex): ", tmp.hex().encode())p.recvuntil(b"Here it is: ")return bytes.fromhex(p.recvline().strip().decode())p = remote('chall.ctf.k1nd4sus.it', 31013)print(p.recvline())
print(p.recvline())c2 = b'\x00\x00'
lc2 = b'\x00\x00'
tk = b''
for i in range(8):tmp = xor(b'\xff\xff', c2)+b'\x00'*4#enc = encrypt_block(tmp, key, N, shortcut=True)enc = getenc(tmp)c2 = xor(c2,enc[2:4])tk+=xor(enc[4:],lc2)lc2 = enc[2:4]print(tk.hex())p.close()

然后弄个解密函数解一下。这东西居然不是每次都成功，会出乱字符，不清楚怎么来的。

def decrypt_block(block, key):c1,c2,c3 = block[:2],block[2:4],block[4:]for i in range(7,-1,-1):round_key = key[i*2:i*2+2]b2 = xor(c3, round_key)b1 = xor(c1, b2)b3 = long_to_bytes((bytes_to_long(c2) - pow(65537,bytes_to_long(round_key), N))&0xffff)c1,c2,c3 = b1,b2,b3#print(c1,c2,c3)return c1+c2+c3def decrypt(ciphertext, key, modulus):iv = ciphertext[:6]padded = ciphertext[6:]blocks = [padded[i:i+6] for i in range(0, len(padded), 6)] res = b''for i in range(len(blocks)):tmp = decrypt_block(blocks[i], key)if i == 0:r = xor(tmp, iv)else: r = xor(tmp,blocks[i-1])res += r#print(res)return reskey = bytes.fromhex('35e7c26a66bc651827cac73bc99c6667')
N = 175914002278057050406831961452237183138299948079975109116384718227058692202299804814271876290451098159041914033459568540766514412008363701006284852804260357617529486527991021342873932212136053758342488462611451121664507695932811146083705960145782839959600560090211913120599024239421171256321562939861953258223
flag = bytes.fromhex('9f3d4928ba479f1e53a7f287efe0dba974745b5fb4a472e24ecdcefb3a70824f9ec87aba16cf7ab4551324af56035c387cb9bf390888')
decrypt(flag,key,N)
#b'KSUS{N3veR_Ev3r_5hOr7cuT_F3ist3l_Ne7w0rks}\x06\x06\x06\x06\x06\x06'

key in the haystack

后边这两个是同一问题，一个小一个大，放一起

from Crypto.Util import number
from base64 import b64encodeprime = lambda: number.getPrime(512)
def b64enc(x):h = hex(x)[2:]if len(h) % 2:h = '0' + hreturn b64encode(bytes.fromhex(h)).decode()p = prime()
q = prime()
with open("flag.txt") as f:flag = f.readline().strip()n = p * q
m = int(flag.encode().hex(), 16)
c = pow(m, 65537, n)print("ciphertext:", hex(c)[2:])bale = [p, q]
bale.extend(prime() for _ in range(1<<6))def add_hay(stack, straw):x = stack[0]for i in range(1, len(stack)):y = stack[i]stack[i] = y + (straw * x)x = ystack.append(straw * x)stack = [1]
add_hay(stack, p) #[1,p]
add_hay(stack, q) #[1,p+q,p*q]
for straw in bale:add_hay(stack, straw)print("size:", len(stack))
for x in stack:print(b64enc(x))

生成包含p,q的66个素数。然后经过add_hay生成stack。

这里是我自己的想法，这个方法不适用加强后的第2题，但也是个思路记录一下。

先设一个变量，从后向前导一下：Kn = S(n) + v*S(n-1) => Sn = Kn - v*S(n-1)

最后得到等于f = ss[-1]*v - stack[-1] 这是一个66次1元方程，不算太大sage可以直接解。由于这里的66个素数都是对称的，直接可以解出66个根，这里边就包含p,q

from base64 import *
from Crypto.Util.number import *outs = open('output.txt').readlines()
st = [bytes_to_long(b64decode(outs[2+i])) for i in range(69)]#Kn = S(n) + v*S(n-1) => Sn = Kn - v*S(n-1) 
var('v')
ss = [1]
for i in range(1,68):ss.append(st[i]-v*ss[-1])#K68 = v*S68
f = ss[-1]*v - st[-1]
ps = f.roots()
#v有66个解,对应66个素数
ps = [int(i[0]) for i in ps]c = 0x7434d263623892ca660f4139c54ab02a8a14d87cd5c658fca9105f88f7ed5c888a744e949b716094c1d73fd8084eeaf72b23e97325829a69ca57a34e5e0b5272ddaf039bcc0aed2055968c8dfa7cd0373cca072c31123e6259659af03ce87b224bb7fdf13fb89b4ceb580d2d11524025ccb4f86560f3b006d99d86a63ab3aa5a#猜flag小于512位
for p in ps:m = pow(c,invert(65537,p-1),p)print(long_to_bytes(int(m)))#b'KSUS{6465726976617469766573206172652061206e69636520747269636b}'

key in the big haystack

这个升级版想了一天也没结果，然后问小鸡块给秒了。(数据有44M，就不贴了，也贴不上)

bale = [p, q]
bale.extend(prime() for _ in range(1<<9))stack = [1]
add_hay(stack, p)
add_hay(stack, q)
for straw in bale:add_hay(stack, straw)
for straw in bale[2:]:add_hay(stack, straw + 2)

这题与上边只有这些变化，素数由64改为512，并且用了两次，所以结果是1029项。

这些给定的值实际上是一个1029项多项式的系数。可以先用3个变量试下。

(x+p)*(x+q)*(x+r) = x^3 + (p+q+r)*x^2 + (pq+qr+rp)*x + pqr

然后把这些数据代入含x的方程

$f = \sum (x^{1028-i}*stack_{i}) _{i=0}^{1028}$

而这个式子里除了p,q是2次外其它都是1次（包含512和素数和512个素数+2，素数+2后跟原来不形成平方关系）所以对f求导后与原来的f作gcd就能得到对于p,q的多项式。然后直接求解可得p,q

from base64 import *
from Crypto.Util.number import *
from gmpy2 import irootouts = open('big_output.txt').readlines()
enc = bytes.fromhex('5894f38180b9f41fb816c7428b64b63cf207e349832aeb256977526ec750239c5b75e846f2c7db19fc84d44e57c1a6181562487cd4a7e58bab9903feead90d884b574dcc9d35b0d6ae7d491d399dcdf6aacc74efff2135c673178e08b50ac1a09f5334cd0d4b48355b28219dbc31b45a2c7687114b69c4f8a0ae20740e9ce1fe')
c = bytes_to_long(enc)
stack = [bytes_to_long(b64decode(outs[2+i])) for i in range(1029)]PR.<x> = PolynomialRing(ZZ)
f = sum([stack[i] * x^(1028-i) for i in range(len(stack))])
g = gcd(f.derivative(), f)
print(g)
#x^2 + 20450065261452182016584260876047399525896704233984001074890163119931284325571387726435254377483741593577102784943815777723994032502151858215013739509078298*x + 101344562563413148702503209034490415272295393794389109823061195011331285068194700252292458323839836319978741203645201395179109429423054143994480684843212974225776158987058221755014377991550489320194566899710227109943050130147641582913932721996451645082208066936338974731735770555839605141969367848387625804201
#系数分别是p+q,p*q 
v = g.roots()
p = abs(v[0][0])
#8434298218257235619456993018380042120260367010962473119979826477888279532268658434816651817828253000282579391409905630356600119281235242527375263115386349
long_to_bytes(int(pow(c,inverse_mod(65537,p-1),p)))
#KSUS{43525420697320612076657279206e69636520747269636b}