zer0ptsCTF 2022

参加したのでwriteupを書く。なおcrypto以外はノータッチ。miscはちょっと見たが難しそうでギブ。結局解けたのはAnti-Fermatのみでした。ctf出場２回目だけどこれが本場の難易度かとプルプル。まだまだ修行が必要ですな。

Anti-Fermat

from Crypto.Util.number import isPrime, getStrongPrime
from gmpy import next_prime
from secret import flag

# Anti-Fermat Key Generation
p = getStrongPrime(1024)
q = next_prime(p ^ ((1<<1024)-1))
n = p * q
e = 65537

# Encryption
m = int.from_bytes(flag, 'big')
assert m < n
c = pow(m, e, n)

print('n = {}'.format(hex(n)))
print('c = {}'.format(hex(c)))

要約

RSAで素数qが素数pに依存した形で定義されてる。n=p*qからpとqを求めよ。

解法

タイトルからフェルマー法を使えと言わんばかりの匂いがする。

しかし通常のフェルマー法はq=nextPrime(p)みたいになってる場合に有効なのでちょっと工夫が必要。

フェルマー法の核は「pとqが小さい数で結びついているので、その小さい数をbrute-forceで見つけ出す」点であるから、この「小さい数」を定式化しよう。

まずp ^ ((1<<1024)-1)とxorされているのが一見厄介だが、ここは(1<<1024)-p-1と等価である。そうすれば

pp = (1<<1024)-p - 1
q - pp = eps

となりqとpを小さい数epsで関連づけられた。あとはpとqを解に持つ２次方程式を解いてやればOK。具体的には

p + q = p + (pp + eps) = (1<<1024) + eps - 1
pq = n

よりp,qは

x^2 - ((1<<1024) + eps - 1)x + n = 0

の解であり、コレを解くと

x = [((1<<1024) + eps - 1) ± √{((1<<1024) + eps - 1)^2 - 4n}] / 2

コレが整数（特に素数）になるようなepsを小さい値から順番に探していく。

なお実際には判別式部分が平方数になるときで探していけばルート部分をいちいち考えなくて楽。

コード

from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes

M = 1 << 1024

for eps in range(1, 10000):
    D = (M + eps)**2 - 4 * n
    rootD, check = iroot(int(D), 2)
    if check:
        print(eps)
        break

p = ((eps + M) + rootD) // 2
q = ((eps + M) - rootD) // 2
phi = (p - 1) * (q - 1)

d = pow(e, -1, phi)
flag = pow(c, d, n)
long_to_bytes(flag)

出力

2030
b'Good job! Here is the flag:\n+-----------------------------------------------------------+\n| zer0pts{F3rm4t,y0ur_m3th0d_n0_l0ng3r_w0rks.y0u_4r3_f1r3d} |\n+-----------------------------------------------------------+'

CurveCrypto

import os
from random import randrange
from Crypto.Util.number import bytes_to_long, long_to_bytes, getStrongPrime
from Crypto.Util.Padding import pad
from fastecdsa.curve import Curve

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def gen():
    while True:
        p = getStrongPrime(512)
        if p % 4 == 3:
            break
    while True:
        q = getStrongPrime(512)
        if q % 4 == 3:
            break
    n = p * q
    a = randrange(n)
    b = randrange(n)

    while True:
        x = randrange(n)
        y2 = (x**3 + a*x + b) % n
        assert y2 % n == (x**3 + a*x + b) % n
        if pow(y2, (p-1)//2, p) == 1 and pow(y2, (q-1)//2, q) == 1:
            yp, yq = pow(y2, (p + 1) // 4, p), pow(y2, (q + 1) // 4, q)
            _, s, t = xgcd(p, q)
            y = (s*p*yq + t*q*yp) % n
            break
    return Curve(None, n, a, b, None, x, y) 

def encrypt(m, G):
    blocks = [m[16*i:16*(i+1)] for i in range(len(m) // 16)]
    c = []
    for i in range(len(blocks)//2):
        G = G + G
        c.append(G.x ^ bytes_to_long(blocks[2*i]))
        c.append(G.y ^ bytes_to_long(blocks[2*i+1]))
    return c

def decrypt(c, G):
    m = b''
    for i in range(len(c) // 2):
        G = G + G
        m += long_to_bytes(G.x ^ c[2*i])
        m += long_to_bytes(G.y ^ c[2*i+1])
    return m

flag = pad(os.environ.get("FLAG", "fakeflag{sumomomomomomomomonouchi_sumomo_mo_momo_mo_momo_no_uchi}").encode(), 32)
C = gen()
c = encrypt(flag, C.G)
assert decrypt(c, C.G) == flag

print("n = {}".format(C.p))  # 整数
print("a = {}".format(C.a))  # 整数
print("b = {}".format(C.b))  # 整数
print("c = {}".format(c))  # 長さ４の数列（fakeflag{sumomomo...}に対してだと長さ６）

要約

mod n上で定義された楕円曲線が与えられる。生成点Gは未知で、それを2G, 4G, 8Gと定数倍しながら、そのx座標およびy座標と平文をxorした結果を暗号文とする。平文を求めよ。

解法

生成点のx,y座標は1024ビットもあるのに平文は128ビットしかないことを利用する。単刀直入には平文部分を変数に置いて、Coppersmithをすれば良い。

肝心の関係式は、暗号文に平文をxorすれば楕円曲線上の点が出てくるので、この点がちゃんと楕円曲線上にあリますよと立式する。

コード（discordに上がってたものを転記）

# https://github.com/defund/coppersmith/blob/master/coppersmith.sage

import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()
    
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

################

R = Integers(n)
P.<x, y> = PolynomialRing(R)

def recover_flag(c):
    bounds = (floor(2^128), floor(2^128))
    mask = ~(int(2^128-1))
    c2 = [t & mask for t in (c[0], c[1])]
    f = (c2[0] + x)^3 + a*(c2[0] + x) + b - (y + c2[1])^2
    roots = small_roots(f, bounds)[0]
    c3 = [t + u for (t,u) in zip(c2, roots)]
    c4 = [int(t) ^^ int(u) for (t,u) in zip(c, c3)]
    return b''.join([bytearray.fromhex(hex(t)[2:]) for t in c4])

print((recover_flag(c[:2]) + recover_flag(c[2:4])).strip().decode('ascii'))

出力

zer0pts{th3_g00d_3ncrypti0n_c0m3s_fr0m_th3_g00d_curv3}

反省

めっちゃ簡単やん。。多変数CoppersmithはmodNだと使えないと思ってたが、その理解が間違ってるのか、今回は偶然modNを整数環にリフトしても影響がないのか、そこのところよく分かってない。識者求む。理解が進んだら記事を改めよう。

ちなみに多変数Coppersmith使うの初めて。１変数CoppersmithはRSAの文脈でなら使ったことあったが、楕円曲線の問題でもこんな使い方できるのか。

Karen

with open("flag.txt", "rb") as f:
    flag = int.from_bytes(f.read(), "big")

n = 70
m = flag.bit_length()
assert n < m
p = random_prime(2**512)


F = GF(p)
x = random_matrix(F, 1, n)
A = random_matrix(ZZ, n, m, x=0, y=2)
A[randint(0, n-1)] = vector(ZZ, Integer(flag).bits())
h = x*A

print(p)
print(list(h[0]))

要約

0,1のみを要素に持つ行列Aに巨大な要素を持つベクトルxをかけた結果が与えられる。コレだけからAとxを復元できるか？

解法

Aが0,1のみ要素にもつ行列なので、ナップサック問題の変種であろうことはすぐに想像がつく。難しいのはベクトルxが不明なのでナップサックに入れる荷物自体が分からない点。

実はこの問題設定はHidden Subset Sum Problemとしてよく調べられているらしく、A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problemにコレを解くSOTAアルゴリズムが書かれている。

（後で論文読もう、理解が進んだら追記予定）

コード（discordに上がってたものを転記）

import ast

with open("karen/output.txt") as f:
    p = ast.literal_eval(f.readline())
    h = ast.literal_eval(f.readline())


m = len(h)
n = 70

# orthogonal lattice
B = matrix(h).T.augment(matrix.identity(m)).stack(vector([p] + [0] * m))
nr = m - n
print("start BKZ", B.dimensions())
# ortho = B.LLL()[:nr, 1:]
ortho = B.BKZ()[:nr, 1:]
print(ortho)
# print(ortho * A.T)  # first nr rows are zeros
# exit()

R = ortho.T.augment(matrix.identity(m))

# print('after')
# print((A*R)[:,:nr])
# print('after nr')
# print((A*R)[:,nr:])
# exit()

R[:, :nr] *= 2 ^ 10
print("start LLL", R.dimensions())
# R = R.BKZ(algorithm="NTL")
R = R.LLL()

print("=" * 10)

goodvecs = []
for row in R:
    if any([x != 0 for x in row[:nr]]):
        continue
    if all(-1 <= x <= 1 for x in row):
        goodvecs.append(row[nr:])
        print(row[nr:])
print("gvecs", len(goodvecs))


def is_good(v):
    if all([x == 0 for x in v]):
        return None
    if all([0 <= x <= 1 for x in v]):
        return tuple(v)
    if all([-1 <= x <= 0 for x in v]):
        return tuple(-v)

print("find 01 basis")

from itertools import product
from tqdm import tqdm

avecs = set()
for v in goodvecs:
    if all(0 <= x <= 1 for x in v):
        avecs.add(tuple(v))
        bestvec = v
print(len(avecs))
for v1 in tqdm(goodvecs):
    for v2 in goodvecs:
        for coef in product([-1, 0, 1], repeat=3):
            vv = coef[0] * v1 + coef[1] * v2 + coef[2] * bestvec
            if any([x < 0 for x in vv]):
                vv = -vv
            if all([0 <= x <= 1 for x in vv]) and sum(vv) != 0:
                avecs.add(tuple(vv))
    if len(avecs) == n:
        break

print(len(avecs))
avecs = list(avecs)
AT = matrix(ZZ, avecs).T
x = AT.change_ring(Zmod(p)).solve_right(vector(h)).change_ring(ZZ)
print(x)

from Crypto.Util.number import *

for row in AT.T:
    bits = "".join(map(str, row))[::-1]
    m = int(bits, 2)
    f = long_to_bytes(m)
    if b"zer0pts" in f:
        print(f)

出力

start BKZ (352, 352)
......
start LLL (351, 632)
......
gvecs 70
find 01 basis
1
70
(58396395......00623572)
b'zer0pts{Karen_likes_orthogonal_as_you_like}\n'

反省

コレはむずい。トピック知らなかったしググって実装するにしても今の実力だと１、２日はかかるやつだ。

OK

from Crypto.Util.number import isPrime, getPrime, getRandomRange, inverse
import os
import signal

signal.alarm(300)

flag = os.environ.get("FLAG", "0nepoint{GOLDEN SMILE & SILVER TEARS}")
flag = int(flag.encode().hex(), 16)

P = 2 ** 1000 - 1
while not isPrime(P): P -= 2

p = getPrime(512)
q = getPrime(512)
e = 65537
phi = (p-1)*(q-1)
d = inverse(e, phi)
n = p*q

key = getRandomRange(0, n)
ciphertext = pow(flag, e, P) ^ key

x1 = getRandomRange(0, n)
x2 = getRandomRange(0, n)

print("P = {}".format(P))
print("n = {}".format(n))
print("e = {}".format(e))
print("x1 = {}".format(x1))
print("x2 = {}".format(x2))

# pick a random number k and compute v = k**e + (x1|x2)
# if you add x1, you can get key = c1 - k mod n
# elif you add x2, you can get ciphertext = c2 - k mod n
v = int(input("v: "))

k1 = pow(v - x1, d, n)
k2 = pow(v - x2, d, n)

print("c1 = {}".format((k1 + key) % n))
print("c2 = {}".format((k2 + ciphertext) % n))

要約

RSAの暗号文にさらに別の乱数keyをxorしている。クエリvを一回だけ与えることができ、それに応じてkeyと暗号文それぞれに(v+乱数)をd乗した値を足した結果が返ってくる。１回のクエリだけからkeyと暗号文を両方求められるか？

解法

結論としてはv = (x1 + x2) / 2とすれば良い。もしx1 + x2が奇数であればガチャ失敗ということで再度リベンジ。この時

c1 = (pow(v - x1, d, n) + key) 
c2 = (pow(v - x2, d, n) + ciphertext) 
=> c1 + c2 = key + ciphertext = key + (key ^ pow(flag, e, P))

となる。

見やすくするためC := (c1 + c2) % n, F := pow(flag, e, P)と置けば、

C = key + (key ^ F)

からFを割り出せば良いことになる。

一見こんなの不可能そうに見えるが、よく見るとFの偶奇とCの偶奇はkeyによらず一致する。これに気づけばFの他のビットも下から順番に割れそうな気がする。

（注意：上式はmod nでの等式なので上記議論は厳密には誤り。ただしC, key, Fは全てn未満であるから、実数上で見れば左辺と右辺のずれは0, nのどちらかでしかない。さらにFが奇数だと決め打ちしてしまえば左辺も奇数であるから、もしCが偶数ならnズレていたことが判明し、C += nとすれば上式は実数上で成り立つ。以降はこの前処理をしたものとして話を続ける。もしコレで解が見つからなければFが偶数の場合もチェックすれば良い）

ここからが妙技である。Fのiビット目をbit(F, i)と書くことにしよう（Cに対しても同様）。Fの0~i-1ビット目まで割れていて、今からbit(F, i)を求めるにはどうすれば良いかを考察する。

もしbit(F, i) = 1ならば、iビット目だけを見れば

bit(key, i) + bit(key ^ F, i) = bit(F, i) = 1

が成り立つ。ここでもしbit(C, i) = 0ならば、コレはi-1ビット目からの繰り上がりがあったことを意味し、同時にi+1ビット目への繰り上がりを引き起こす。i+1ビット目についても

bit(key, i + 1) + bit(key ^ F, i + 1) = bit(F, i+1) <= constant because F is always the same

が成り立つことから、繰り上がりの影響によりbit(C, i+1) = ~bit(F, i+1)で、特にコレは一定値であることが保証される。

以上の議論はbit(F, i) = 0, bit(C, i) = 0の場合には成り立たない。なぜならこの場合i+1ビット目への繰り上がりが生じるかはbit(key, i)に完全に依存し、bit(C, i+1)はkeyによってランダムな値を取るからである。

以上より次の作戦でbit(F, i)を割り出すことができる（下記コード参照）：

コード

from Crypto.Util.number import long_to_bytes

C_pool = [複数回クエリを投げて(c1+c2)%nたちを格納。偶数なら+nするのを忘れないこと。]

F_bits = [0] * 1000  # F_bits[i] = bit(F, i)
F_bits[0] = 1  # Fは奇数と仮定している

for i in range(1, 1000):
    # bit(F, i)を求める
    bit_C_i_plus_1_is_even = 0
    bit_C_i_plus_1_is_odd = 0

    for C in C_pool:
        C_bin = bin(C)[2:]

        # bit(C, i) = 0であるものだけ考える
        if C_bin[-i-1] == '0':
            if C_bin[-i-2] == '0':
                bit_C_i_plus_1_is_even += 1
            else:
                bit_C_i_plus_1_is_odd += 1
    
    # そもそも常にbit(C, i) = 1の場合があるが、この時はbit(F, i) = bit(C, i)
    # i-1ビット目から繰り上がりがきてる可能性はありうるが、
    # keyによらず常に繰り上がりが生じる事態は考えにくい。
    if bit_C_i_plus_1_is_even == 0 and bit_C_i_plus_1_is_odd == 0:
        F_bits[i] = 1
    # bit(C, i+1)が常に一定ならbit(F, i) = 1、そうでないならbit(F, i) = 0
    elif bit_C_i_plus_1_is_even == 0 or bit_C_i_plus_1_is_odd == 0:
        F_bits[i] = 1
    else:
        F_bits[i] = 0

# あとは復元するだけ
F = int('0b' + ''.join(map(str, F_bits))[::-1], 2)
d = pow(e, -1, P-1)
flag = pow(F, d, P)
print(long_to_bytes(flag))

反省

繰り上がりが起きるのが面倒臭いわけで、普通これを考慮するなら下位bitから順番に求めないといけない気がするが、この解法はbit(F, i)の導出にbit(F, 0),...,bit(F, i-1)を全く使っていない。それどころかbit(F, i+1)という上のビットを見ているわけで、よくこれで解けるなあと感嘆する。すごい。