foobarCTF 2022 | sigma bg

#foobarCTF_2022

#!/usr/bin/env python3

from Crypto.Util.number import *
import math

flag = b'***************REDACTED******************'

def keygen(bits):
    while True:
        p,q = getPrime(bits),getPrime(bits)
        if (p % 4 == 3) and (q % 4 == 3 ) and (p != q):
            n = p * q
            break
    return n

def keygen2():
    X = [2]
    x = 2
    for i in range(len((C))):
        x = 2 * x + 1
        X.append(x)
    return X

def encrypt1(m,h,n):
    while len(m)%h!=0:
        m = '0'+ m
    l = len(m) // h
    r = 89657896589
    x=pow(r,2,n)
    C = ''
    for i in range(l):
        x = pow(x,2,n)
        p_i = (bin(x)[2:])[-h:]
        c_i = int(p_i,2)^int(m[i*h:(i+1)*h],2)
        cx = bin(c_i)[2:].zfill(h)
        C+=cx
    return C


def encrypt2(C, M):
    S = 0
    for x, m in zip(C, M):
        S += int(x) * m
    return S

n = keygen(512)
h = int(math.log(int(math.log(n,2)),2))
m = ''.join(bin(ord(i))[2:].zfill(8) for i in str(flag))
C = encrypt1(m,h,n)
X = keygen2()
S = encrypt2(C,X)

print("n =  {}".format(n))
print("S =  {}".format(S))

encrypt1 と encrypt2でそれぞれ暗号化を行ってる。どちらも暗号に用いられている鍵は既知なので、順番に復号すればよい。

keygen2 で生成される配列は超増加列になっていて、encrypt2は ナップザック暗号でいうところの秘密鍵で暗号化をしている状態。鍵を後ろからみていって単に のときは必ず が和に含まれている（その後 と更新する

encrypt1 はなんか見覚えあるなと思ったらBlum-goldwasser cryptosystemっぽい感じ。本来ランダムで有るべきが固定かつ既知なので、単純にを求めてそこからを求める、というパートが省略できる

import math

with open("output.txt") as f:
    n = int(f.readline().strip().split(" =  ")[1])
    S = int(f.readline().strip().split(" =  ")[1])

# -- encrypt2
key = [2]
x = 2
while x < S:
    x = 2 * x + 1
    key.append(x)

C = ""
for k in key[::-1]:
    if k < S:
        C += "1"
        S -= k
    elif len(C) > 0:
        C += "0"


# -- encrypt1
h = int(math.log(int(math.log(n,2)),2))
assert len(C) % h == 0

r = 89657896589
x = pow(r,2,n)
m = 0
for i in range(len(C) // h):
    x = pow(x,2,n)
    p_i = (bin(x)[2:])[-h:]
    m_i = int(p_i,2)^int(C[::-1][i*h:(i+1)*h],2)

    m = (m << h) + m_i
print(m.to_bytes(100, "big"))