srdnlen CTF 2022 | give me a bag

#srdnlen_CTF_2022

from random import randint
from math import gcd
from secret import FLAG

BIN_LEN = 240

class MHK:

    def __init__(self):

        self.b = []
        self.w = []
        self.q = 0
        self.r = 0

        self.genKeys()


    def genKeys(self):

        k = 30

        self.w.append(randint(1,2**(k//2)))
        sum = self.w[0]

        for i in range(1, BIN_LEN):
            self.w.append(sum + randint(1, 2**k))
            sum += self.w[i]

        self.q = sum + randint(1, 2**k)

        while True:
            self.r = sum + randint(1, 2**k)
            if gcd(self.r,self.q) == 1:
                break

        for i in range(BIN_LEN):
            self.b.append((self.w[i]*self.r)%self.q)


    def encrypt(self, plaintext):

        msgBin = ''.join('{:08b}'.format(b) for b in plaintext.encode('utf8'))

        if len(msgBin) < BIN_LEN:
            msgBin = msgBin.zfill(BIN_LEN)

        ciphertext = 0
        for i in range(len(msgBin)):
            ciphertext += self.b[i]*int(msgBin[i],2)

        return str(ciphertext)


    def decrypt(self, ciphertext):

        plaintext = ''
        ciphertext = int(ciphertext)

        new_ciphertext = (ciphertext* pow(self.r,-1,self.q) )%self.q

        for i in range(len(self.w)-1,-1,-1):
            if self.w[i] <= new_ciphertext:
                new_ciphertext -= self.w[i]
                plaintext += '1'
            else:
                plaintext += '0'
        
        return int(plaintext[::-1], 2).to_bytes((len(plaintext) + 7) // 8, 'big').decode()


if __name__ == "__main__":

    crypto = MHK()
    encrypted = crypto.encrypt(FLAG)

    file=open('./output.txt','w+')
    file.writelines('b = '+ str(crypto.b))
    file.writelines('\nw = '+ str(crypto.w[:2]))
    file.writelines('\nc = '+ str(encrypted))
    file.close()

ナップザック暗号。densityが小さいが、なぜかCLOS法みたいなのはうまくいかない

秘密鍵の先頭が2つだけ与えられているので、 という関係から、を求めれば、からを復元できる

import ast
from Crypto.Util.number import inverse
from tqdm import tqdm


def decrypt(ciphertext, w, r, q):
    plaintext = ''
    ciphertext = int(ciphertext)
    new_ciphertext = (ciphertext * pow(r, -1, q)) % q
    for i in range(len(w)-1, -1, -1):
        if w[i] <= new_ciphertext:
            new_ciphertext -= w[i]
            plaintext += '1'
        else:
            plaintext += '0'

    return int(plaintext[::-1], 2).to_bytes((len(plaintext) + 7) // 8, 'big')


with open("output.txt") as f:
    b = ast.literal_eval(f.readline().strip().split(" = ")[1])
    w = ast.literal_eval(f.readline().strip().split(" = ")[1])
    c = ast.literal_eval(f.readline().strip().split(" = ")[1])


qx = w[1] * b[0] - w[0] * b[1]

fs = [2, 3, 3, 7, 5171, 23017, 37427849, 224958387154349926384350540467107171, 2258886974867359065776931126319410181]

for i in tqdm(range(2**len(fs))):
    q = qx
    for j in range(len(fs)):
        if i & (1 << j) != 0:
            q //= fs[j]

    r1 = b[0] * inverse(w[0], q) % q
    r2 = b[1] * inverse(w[1], q) % q

    if r1 == r2:
        r = r1
        print(r)
        w = [v * inverse(r, q) % q for v in b]

        print(decrypt(c, w, r, q))