CakeCTF 2021 Writeup [Crypto]

[Crypto] discrete_log

from Crypto.Util.number import getPrime, isPrime, getRandomRange

def getSafePrime(bits):
    while True:
        p = getPrime(bits - 1)
        q = 2*p + 1
        if isPrime(q):
            return q

with open("flag.txt", "rb") as f:
    flag = f.read().strip()

p = getSafePrime(512)
g = getRandomRange(2, p)
r = getRandomRange(2, p)

cs = []
for m in flag:
    cs.append(pow(g, r*m, p))

print(p)
print(g)
print(cs)

512bitの素数 $p$ と乱数 $g, r (2≤g, r ≤p)$ を定義し、フラグ $m$ の各バイト列に対して $cipher=g^{rm} \mod p$ で暗号化を行っている。

暗号化の式は

$\displaystyle{ cipher=(g^r \mod p)^m \mod p }$

となり、またフラグの頭CakeCTF{であることから、Common Modules Attackと同じ要領でいい感じに $g^{r} \mod p$ を計算できる。

あとはフラグの各文字に対して0x20~0x7eの総当たりで一位に定まる $g^{r} \mod p$ を計算すればいい。

と思ったけど、毎回Common Modules Attack回さなくてもいいじゃん。

import gmpy2, binascii
from output import *

# CakeCTF{*****}
def culc(v1, v2): # https://gist.github.com/AkashiSN/81df83a26fd7c38efd55c5a2515ea9ff#file-common_modulus_attack-py
    n = p
    e1 = 101
    e2 = v2
    c1 = ciphers[3]
    c2 = v1
    val = gmpy2.gcdext(e1,e2)
    if val[1] < 0:
        a = -val[1]
        b = val[2]
        c1_inv = gmpy2.invert(c1,n)
        c1a = pow(c1_inv, a, n)
        c2b = pow(c2, b, n)
    else:
        a = val[1]
        b = -val[2]
        c2_inv = gmpy2.invert(c2,n)
        c1a = pow(c1, a, n)
        c2b = pow(c2_inv, b, n)
    m = (c1a * c2b)%n
    m,result = gmpy2.iroot(m,val[0])
    return m

ans = culc(ciphers[0], 67)
for cipher in ciphers:
    for i in range(200):
        if culc(cipher, i) == ans:
            print(chr(i), end="")
            break
    else:
        print("e", end="")

print("")

# CakeCTF{4h4_p14in73x7_5p4c3_i5_7000000_5m411}

[Crypto] together_as_one

from Crypto.Util.number import getStrongPrime, bytes_to_long

p = getStrongPrime(512)
q = getStrongPrime(512)
r = getStrongPrime(512)

n = p*q*r

x = pow(p + q, r, n)
y = pow(p + q*r, r, n)

m = bytes_to_long(open("./flag.txt", "rb").read())
assert m.bit_length() > 512
c = pow(m, 0x10001, n)

print(f"{n = :#x}")
print(f"{c = :#x}")
print(f"{x = :#x}")
print(f"{y = :#x}")

素数1つ求めた以降が分からなかった。平文だけでなく、因数 $p, q, r$ も一緒に暗号化してるタイプの問題。

$\displaystyle{ x=(p+q)^r \mod n \\ y=(p+qr)^r \mod n }$

$x, y$ の式は二項定理より、

$\displaystyle{ x= \binom{r}{0}p^r+ \binom{r}{1}p^{r-1}q+ \dots+ \binom{r}{r-1}pq^{r-1}+ \binom{r}{r}q^r \mod n \\ y= \binom{r}{0}p^r+ \binom{r}{1}p^{r-1}qr+ \dots+ \binom{r}{r-1}p(qr)^{r-1}+ \binom{r}{r}(qr)^r \mod n }$

となる。ここで $x$ の式の $p^{r}, q^{r}$ 以外の二項係数は $r$ の倍数になり $p, q$ を因数に含むことから法 $n(=pqr)$ に引っかかり0になる。また $y$ の式の $p^{r}, (qr)^{r}$ 以外の項は $p, q, r$ を因数に含むので、0になる。

$\displaystyle{ x=p^r+q^r \mod n \\ y=p^r+(qr)^r \mod n }$

ここで $x-y$ について考えてみると、

$\displaystyle{ x-y ≡ q^r(1-r^r) \mod n }$

となるので、 $x-y$ は $q$ の倍数であることがわかる（⇔ $q=gcd(x-y, n)$ となる）。また、

$\displaystyle{ \frac{x-y}{q}-1≡r^r \mod n }$

となり、 $r=gcd((x-y)/q+1, n)$ と求めることができる。

これで $n$ が素因数分解できたので、あとはしゅっとやって終わり。

from Crypto.Util.number import *
from output import x, y, n, c

q = GCD(x-y, n)
r = GCD((x-y) // q - 1, n)
p = n // q // r

assert p*q*r == n

phi = (p - 1) * (q - 1) * (r - 1)
e = 65537

d = inverse(e, phi)
m = pow(c, d, n)

print(long_to_bytes(m))

[Crypto] improvisation

import random

def LFSR():
    r = random.randrange(1 << 64)
    while True:
        yield r & 1
        b = (r & 1) ^\
            ((r & 2) >> 1) ^\
            ((r & 8) >> 3) ^\
            ((r & 16) >> 4)
        r = (r >> 1) | (b << 63)

if __name__ == '__main__':
    with open("flag.txt", "rb") as f:
        flag = f.read()
        assert flag.startswith(b'CakeCTF{')
        m = int.from_bytes(flag, 'little')

    lfsr = LFSR()
    c = 0
    while m:
        c = (c << 1) | ((m & 1) ^ next(lfsr))
        m >>= 1

    print(hex(c))

LFSR（線形帰還シフトレジスタ）で乱数を生成し、XORしている。先入観でcipherはビッグエンディアンだと勘違いしてしまい、開催期間中に解くことができなかった…

LFSRの状態を復元して終わり。

from Crypto.Util.number import *


def LFSR(r):
    while True:
        yield r & 1
        b = (r & 1) ^\
            ((r & 2) >> 1) ^\
            ((r & 8) >> 3) ^\
            ((r & 16) >> 4)
        r = (r >> 1) | (b << 63)


cipher = 0x58566f59979e98e5f2f3ecea26cfb0319bc9186e206d6b33e933f3508e39e41bb771e4af053
cipher = int(bin(cipher)[2:][::-1], 2) << 1
prefix = bytes_to_long("CakeCTF{"[::-1].encode())
lfsr = LFSR((cipher & (2**64 - 1)) ^ prefix)
length = cipher.bit_length()

key = 0
for i in range(length):
    key += next(lfsr) * 2**i

m = key ^ cipher
print(long_to_bytes(m).decode()[::-1])