zer0pts CTF 2023 writeup

easy_factoring (crypto)

The word "decomposition" has multiple meanings.

Can you decompose?

nc crypto.2023.zer0pts.com 10333

平方和問題。サーバーで動作するプログラムが配布されるので確認する。

import os
import signal
from Crypto.Util.number import *

flag = os.environb.get(b"FLAG", b"dummmmy{test_test_test}")

def main():
    p = getPrime(128)
    q = getPrime(128)
    n = p * q

    N = pow(p, 2) + pow(q, 2)

    print("Let's factoring !")
    print("N:", N)

    p = int(input("p: "))
    q = int(input("q: "))

    if isPrime(p) and isPrime(q) and n == p * q:
        print("yey!")
        print("Here you are")
        print(flag)
    else:
        print("omg")

def timeout(signum, frame):
    print("Timed out...")
    signal.alarm(0)
    exit(0)

if __name__ == "__main__":
    signal.signal(signal.SIGALRM, timeout)
    signal.alarm(30)
    main()
    signal.alarm(0)

素数p,qを作成して、N=p²+q²を出力する。ここからpとqを求めることができればflagが表示される。Nを平方和に分解する問題となる。

Fermat's theorem on sums of two squares(en.wikipedia.org)

フェルマーの二平方定理によれば、奇素数pがp≡1(mod 4)であれば、p=X²+Y²を満たす整数XとYが存在する。

方針としては、Nを素因数分解してp₁,p₂,...p_nを作り、各p_iをp_i=X_i²+Y_i²で表現する。

すると、(X_i²+Y_i²)(X_j²+Y_j²) = (X_iX_j+Y_iY_j)² + (X_iY_j-X_jY_i)²、の計算を繰り返して、最終的なN=p²+q²を得ることができる。

p_iの分解には、x²≡-1(mod p)となるxを見つける必要がある。xの存在有無はオイラーの規準を用いることで、平方剰余の存在を判定することができる。

平方剰余とルジャンドル記号とヤコビ記号 | 晴耕雨読(github.io)

xが存在することがわかれば、具体的にxを求める方法としてTonelli-Shanksのアルゴリズムがあり、次のページのコードを参照した。

Tonelli-Shanksのアルゴリズムについて - Project Euphoria(hatenablog.com)

xが求まればp=X²+Y²を計算できる。次のページのコードを参照した。

2017を二つの平方数の和で表す方法 (1) - tsujimotterのノートブック(hatenablog.com)

手順をまとめると以下のようになる。

Nを素因数分解して素因数p₁,p₂,...p_nを得る
すべての素因数p_iがp_i≡1(mod 4)を満たすことを確認する
各p_iについて
1. x²≡-1(mod p_i)となるxが存在することを確認する
2. x²≡-1(mod p_i)となるxを求める
3. xとp_iからp_i=X_i²+Y_i²を求める
得られたX_i²+Y_i²の組を計算してN=p²+q²を求める。

tonelli_shanks.py#https://xornet.hatenablog.com/entry/2020/05/11/112508
from Crypto.Util.number import isPrime

def neg(x, n):
    return -x % n

def is_quadratic_residue(a, p):
    if a % p == 0:
        return True
    return legendre_symbol(a, p) == 1

def legendre_symbol(a, p):
    if not isPrime(p) or p == 2:
        raise ValueError("p must be a odd prime number")
    return pow(a, (p-1) // 2, p)

def get_q_s(p):
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    return (q, s)

def get_nonresidue(p):
    ret = 2
    while is_quadratic_residue(ret, p):
        ret += 1
    return ret

def main(a, p):
    if not is_quadratic_residue(a, p):
        return ()
    if a == 0:
        return 0
    q, s = get_q_s(p)
    z = get_nonresidue(p)
    m, c, t, r = s, pow(z, q, p), pow(a, q, p), pow(a, (q+1) // 2, p)
    while True:
        if t == 1:
            return (r, neg(r, p))
        i = m
        for j in range(1, m):
            if pow(t, pow(2, j), p) == 1:
                i = j
                break
        b = pow(c, pow(2, m - i - 1), p)
        b_pow = pow(b, 2, p)
        m, c, t, r = i, b_pow, t * b_pow % p, r * b % p

solve.pyfrom sympy.ntheory import factorint
import tonelli_shanks

#https://tsujimotter.hatenablog.com/entry/fermat-descent
def descent(x, y, k, p):
        if k == 1:
                return [x, y, 1, p]
        
        x_mod_k = x % k
        if x_mod_k > abs(x_mod_k - k):
                x_mod_k = x_mod_k - k
        y_mod_k = y % k
        if y_mod_k > abs(y_mod_k - k):
                y_mod_k = y_mod_k - k
        next_k = (x_mod_k**2 + y_mod_k**2) // k
        next_x = (x * x_mod_k + y * y_mod_k) // k
        next_y = (x * y_mod_k - y * x_mod_k) // k
        return descent(next_x, next_y, next_k, p)

#https://tex2e.github.io/blog/crypto/legendre-and-jacobi-symbls
def QR(a,p):
        return pow(a, (p - 1) // 2, p) == 1

def calc(p):
        Xs = tonelli_shanks.main(p-1,p)
        x = Xs[0]
        y = 1
        k = (x*x+1)//p
        x,y,k,p = descent(x,1,k,p)
        return (abs(x),abs(y))


N = int(input("N= "))
factors = factorint(N)
print(factors)
MLTs = []
XYs = []

for p in factors:
        if factors[p]==2:
                MLTs.append(p)
        elif p==2 :
                XYs.append([1,1])
        elif p%4 != 1:
                print("false...")
                break
        elif not QR(p-1,p):
                print("false...")
                break
        else:
                x,y = calc(p)
                XYs.append([x,y])
                print(str(p)+"="+str(x)+"^2+"+str(y)+"^2")

# (a1^2+b1^2)(a2^2+b2^2) = (a1a2+b1*b2)^2 + (a1*b2-b1*a2)^2
def proofm(a1,b1,a2,b2):
        return a1*a2+b1*b2,a1*b2-a2*b1

X = 0
Y = 0
for xy in XYs:
        if X==0 and Y==0:
                X = abs(xy[0])
                Y = abs(xy[1])
        else:
                X,Y = proofm(X,Y,xy[0],xy[1])
                X = abs(X)
                Y = abs(Y)
for m in MLTs:
        X *= m
        Y *= m

print("p= " + str(X))
print("q= " + str(Y))
print(X*X+Y*Y == N)

solve.pyを実行、サーバーから与えられたNを入力するとp,qを出力する。時間がかかってtime outになることもあるが数回以内には成功する。同じ素因数は2個までを想定しており、p_iが2個ある時は分解する必要はない。

ローカル側：

$ python3 solve.py 
N= 226331076098488940388205693533921106326905753746168177126656766414479243947810
{2: 1, 5: 1, 22633107609848894038820569353392110632690575374616817712665676641447924394781: 1}
5=2^2+1^2
22633107609848894038820569353392110632690575374616817712665676641447924394781=65871231347943334317349051483801057334^2+135255641252239906040866650072552760085^2
p= 332869335296069908992913804523955932087
q= 339895692408776383805250898733857222921

サーバー側：

$ nc crypto.2023.zer0pts.com 10333
Let's factoring !
N: 226331076098488940388205693533921106326905753746168177126656766414479243947810
p: 332869335296069908992913804523955932087
q: 339895692408776383805250898733857222921
yey!
Here you are
b"zer0pts{piyopiyo_Fermat's_Sum_of_Square_meow!!}"

zer0pts{piyopiyo_Fermat's_Sum_of_Square_meow!!}

SquareRNG (crypto:warmup)

I wrote a pseudorandom number generator. You can't guess the next bit without knowing each other's secret.

nc crypto.2023.zer0pts.com 10666

平方剰余問題。途中まで進んだので、そこまでのwriteupと復習を兼ねてflagを出すまで記載する。

サーバーで動作するプログラムが配布されるので確認する。

#!/usr/bin/env python3
import os
from Crypto.Util.number import getPrime, getRandomRange

def isSquare(a, p):
    return pow(a, (p-1)//2, p) != p-1

class SquareRNG(object):
    def __init__(self, p, sa, sb):
        assert sa != 0 and sb != 0
        (self.p, self.sa, self.sb) = (p, sa, sb)
        self.x = 0

    def int(self, nbits):
        v, s = 0, 1
        for _ in range(nbits):
            self.x = (self.x + 1) % p
            s += pow(self.sa, self.x, self.p) * pow(self.sb, self.x, self.p)
            s %= self.p
            v = (v << 1) | int(isSquare(s, self.p))
        return v

    def bool(self):
        self.x = (self.x + 1) % self.p
        t = (pow(self.sa, self.x, self.p) + pow(self.sb, self.x, self.p))
        t %= self.p
        return isSquare(t, self.p)

p = getPrime(256)

sb1 = int(input("Bob's seed 1: ")) % p
sb2 = int(input("Bob's seed 2: ")) % p
for _ in range(77):
    sa = getRandomRange(1, p)
    r1 = SquareRNG(p, sa, sb1)
    print("Random 1:", hex(r1.int(32)))
    r2 = SquareRNG(p, sa, sb2)
    print("Random 2:", hex(r2.int(32)))

    guess = int(input("Guess next bool [0 or 1]: "))
    if guess == int(r1.bool()):
        print("OK!")
    else:
        print("NG...")
        break
else:
    print("Congratz!")
    print(os.getenv("FLAG", "nek0pts{*** REDACTED ***}"))

プログラムは起動すると素数pを生成して、好きなsb1とsb2を入力することができる。続いて乱数saを生成して、SquareRNGクラスで定義されたint関数を(p,sa,sb1)と(p,sa,sb2)の2つについて実行、この2つの結果から(p,sa,sb1)のbool関数の出力を推測する問題。乱数saを変えて77回連続で成功すればflagが表示される。

int関数とbool関数はともに平方剰余の有無を判定するisSquare関数の結果(True/False)を出力する。

int(sb,N) : isSquare( ∑[x=0,N](sa^x × sb^x) mod p )
bool(sb,N): isSquare( (sa³³ + sb³³) mod p )

ここでint関数は同一のsbに対してN=1～32までの32個分を出力する。

入力可能なsb1とsb2に1と-1を入れると式を次のように整理できる。

sb=1
- int(1,N) : isSquare( ∑[x=0,N]sa^x mod p )
- bool(1): isSquare( (sa³³ + 1) mod p )
sb=-1
- int(-1,N) : isSquare( ∑[x=0,N](-sa)^x mod p )
- bool(-1): isSquare( (sa³³ - 1) mod p )

競技中はここまで書いて時間切れとなったが、sb=1とsb=-1のint関数及びbool関数の式を利用すると、次のように書ける。

(sa³³ + 1) mod p = (∑[x=0,32](-sa)^x)×(1+sa) mod p

すなわち

bool(1) = int(-1,32)×int(1,1)

よって、sb1=1、sb2=-1を入力したとき、回答すべきbool(1)はsb1のint関数出力の最初のビットとsb2のint関数出力の最後のビットから得ることができる。

平方剰余の相互法則(ja.wikipedia.org)より、平方剰余同士の積が計算できる。ここではisSquareの出力はTrue/Falseだが、これを1/-1に読み替えればよい。

以下のsolverを書いた。

from pwn import *

io = remote('crypto.2023.zer0pts.com',10666)

io.recvuntil("Bob's seed 1: ")
io.sendline(b'1')
io.recvuntil("Bob's seed 2: ")
io.sendline(b'-1')
for _ in range(77):
        int1 = 1 if int(io.recvline().decode()[10:],16) >> 31 == 0 else -1
        int2 = 1 if int(io.recvline().decode()[10:],16) & 0x1 else -1
        bool1 = 1 if int1*int2==-1 else 0
        io.recvuntil("Guess next bool [0 or 1]: ")
        io.sendline(str(bool1).encode())
        res = io.recvline().decode()
        print(str(int1) + "*" + str(int2) + " > " + str(bool1) + " : " + res[:-1])
        if not "OK!" in res:
                break
io.interactive()

実行させるとflagに到達する。

$ python3 solve.py 
[+] Opening connection to crypto.2023.zer0pts.com on port 10666: Done
-1+-1 > 0 : OK!
-1+1 > 1 : OK!
1+1 > 0 : OK!
-1+-1 > 0 : OK!
-1+-1 > 0 : OK!
-1+-1 > 0 : OK!
1+-1 > 1 : OK!
-1+1 > 1 : OK!
1+1 > 0 : OK!
1+-1 > 1 : OK!
-1+1 > 1 : OK!
-1+1 > 1 : OK!
-1+1 > 1 : OK!
1+1 > 0 : OK!
-1+-1 > 0 : OK!
-1+-1 > 0 : OK!
1+-1 > 1 : OK!
-1+1 > 1 : OK!
1+1 > 0 : OK!
-1+1 > 1 : OK!
1+1 > 0 : OK!
1+1 > 0 : OK!
-1+-1 > 0 : OK!
-1+1 > 1 : OK!
1+1 > 0 : OK!
1+1 > 0 : OK!
-1+-1 > 0 : OK!
-1+-1 > 0 : OK!
1+-1 > 1 : OK!
1+-1 > 1 : OK!
-1+-1 > 0 : OK!
-1+1 > 1 : OK!
1+1 > 0 : OK!
-1+-1 > 0 : OK!
1+-1 > 1 : OK!
1+-1 > 1 : OK!
1+1 > 0 : OK!
1+-1 > 1 : OK!
-1+-1 > 0 : OK!
-1+1 > 1 : OK!
1+-1 > 1 : OK!
-1+1 > 1 : OK!
1+1 > 0 : OK!
-1+1 > 1 : OK!
1+1 > 0 : OK!
-1+-1 > 0 : OK!
-1+1 > 1 : OK!
-1+1 > 1 : OK!
1+-1 > 1 : OK!
1+1 > 0 : OK!
-1+-1 > 0 : OK!
-1+1 > 1 : OK!
1+-1 > 1 : OK!
-1+1 > 1 : OK!
1+1 > 0 : OK!
-1+1 > 1 : OK!
1+-1 > 1 : OK!
1+-1 > 1 : OK!
1+-1 > 1 : OK!
-1+-1 > 0 : OK!
1+-1 > 1 : OK!
-1+-1 > 0 : OK!
-1+-1 > 0 : OK!
1+-1 > 1 : OK!
-1+1 > 1 : OK!
-1+1 > 1 : OK!
1+1 > 0 : OK!
1+1 > 0 : OK!
-1+-1 > 0 : OK!
1+1 > 0 : OK!
-1+-1 > 0 : OK!
1+-1 > 1 : OK!
-1+1 > 1 : OK!
-1+-1 > 0 : OK!
1+-1 > 1 : OK!
-1+-1 > 0 : OK!
1+-1 > 1 : OK!
[*] Switching to interactive mode
Congratz!
zer0pts{L(a)L(b)=L(ab)}

zer0pts{L(a)L(b)=L(ab)}

zer0pts CTF 2023 writeup

概要

目次

easy_factoring (crypto)

SquareRNG (crypto:warmup)