Harekaze mini CTF 2020 Writeup - yoshikingのがんばる日記

zer0ptsで参加していました。 Crypto 2問だけ解いたので、Writeupを書いておきます。

Disaster Level Hackerのwriteupはこちら

ptr-yudai.hatenablog.com

[Crypto] rsa
[Crypto] Wilhelmina says

[Crypto] rsa

from Crypto.Util.number import getStrongPrime, getRandomRange

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

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
phi = (p-1)*(q-1)
e = 65537
c1 = pow(flag, e, n)
c2 = pow(p + q, e, n)
c3 = pow(p - q, e, n)

print(f"{n=}")
print(f"{e=}")
print(f"{c1=}")
print(f"{c2=}")
print(f"{c3=}")

$c2, c3$ はそれぞれ展開すると、 $pq$ となる項はmod n で0になるので、

$c2 \equiv p^e + q^e \pmod{n}\\ c3 \equiv p^e - q^e \pmod{n}$

となります。あとは、

$c2 + c3 \equiv 2p^e \pmod{n}$

となり、 $p$ を入手できますが、せっかくなのでもう少し丁寧に式を追うと、

$\begin{align} c2 + c3 &= 2p^e - k_1n\\ &\equiv 0 \pmod{p}\\ &= k_2 p \end{align}$

となるので、 $c2 + c3$ と $n$ でGCDを取れば $p$ を求めることができ、フラグを入手できます。

solver:

from Crypto.Util.number import *

exec(open("./output.txt").read())

p = GCD(c2 + c3, n)
print(isPrime(p))

q = n // p

d = inverse(e, n - p - q + 1)
m = pow(c1, d, n)
print(long_to_bytes(m))

HarekazeCTF{RSA_m34n5_Rin_Shiretoko_Ango}

[Crypto] Wilhelmina says

from Crypto.Util.number import getStrongPrime
import random

p = getStrongPrime(512)

with open("flag", "rb") as f:
  flag = int.from_bytes(f.read().strip(), "big")
  assert flag < p

t = flag.bit_length()
n = 5
k = 350

xs = [random.randint(2, p-1) for _ in range(n)]
ys = [x * flag % p for x in xs]
zs = [(y >> k) << k for y in ys]

print(f"{t=}")
print(f"{p=}")
print(f"{xs=}")
print(f"{zs=}")

flagを $m$ とすると、

$X_0m + k_0P - a_0= Z_0\\ X_1m + k_1P - a_1= Z_1\\ X_2m + k_2P - a_2= Z_2\\ X_3m + k_3P - a_3= Z_3\\ X_4m + k_4P - a_4= Z_4$

と表せられます。ここで、 $a_i$ は下位ビットを切り落としている処理を表しています。また、大文字の変数( $X_i, P, Z_i$ )は知っている値としています。

これは、CVPで解けそうな匂いがプンプンするので、解きます（雑）。 CVPに関する記事は、以下のwriteupが最初に読むものとしてはとても簡潔に、わかりやすく書かれていると思います。（詳しく書かれた難しいのは知らん）

colab.research.google.com

もう少しわかりやすく書くと、

$m \begin{bmatrix} X_0 \\ X_1 \\ X_2 \\ X_3 \\ X_4 \\ 1 \end{bmatrix} \; + \; k_0 \begin{bmatrix} P \\ 0 \\ 0 \\ 0 \\ 0 \\0 \end{bmatrix} \; + \; k_1 \begin{bmatrix} 0 \\ P \\ 0 \\ 0 \\ 0 \\0 \end{bmatrix} \; + \; k_2 \begin{bmatrix} 0 \\ 0 \\ P \\ 0 \\ 0 \\0 \end{bmatrix} \; + \; k_3 \begin{bmatrix} 0 \\ 0 \\ 0 \\ P \\ 0 \\0 \end{bmatrix} \; + \; k_4 \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ P \\ 0 \end{bmatrix} \text{ } = \text{ } \begin{bmatrix} Z_0 \\ Z_1 \\ Z_2 \\ Z_3 \\ Z_4 \\ 0 \end{bmatrix} \; + \; \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \\ a_4 \\ m \end {bmatrix}$

となり、以下のような格子を考えることでうまく行きます。

$\Lambda = \begin{array}{c c} \begin{array}{c} m \\ k_0 \\ k_1 \\ k_2 \\ k_3 \\ k_4 \end{array}\hspace{-1em} & \left( \begin{array}{@{} c c c c c c @{}} X_0 & X_1 & X_2 & X_3 & X_4 & 1\\ P & 0 & 0 & 0 & 0 & 0\\ 0 & P & 0 & 0 & 0 & 0\\ 0 & 0 & P & 0 & 0 & 0\\ 0 & 0 & 0 & P & 0 & 0\\ 0 & 0 & 0 & 0 & P & 0\\ \end{array} \right) \end{array}.$

solver:

def solve_cvp(B, t, verbose=False):
    t_ = t - B.stack(t).gram_schmidt()[0].row(-1)
    if verbose:
        print("Target vector projection:")
        print(numerical_approx(t_, digits=4))

    B_ = B.LLL()
    if verbose:
        print("\nLLL-reduced basis:")
        print(numerical_approx(B_, digits=4))

    c = B_.solve_left(t_)

    c_ = vector(map(round, c))
    if verbose:
        print("\nRound-off errors:")
        print(numerical_approx(vector(map(abs, c - c_)), digits=4))

    return c_ * B_

exec(open("./output.txt").read().strip())
B = matrix([
    [xs[0], xs[1], xs[2], xs[3], xs[4], 1],
    [p, 0, 0, 0, 0, 0],
    [0, p, 0, 0, 0, 0],
    [0, 0, p, 0, 0, 0],
    [0, 0, 0, p, 0, 0],
    [0, 0, 0, 0, p, 0],
])
t = vector([zs[0], zs[1], zs[2], zs[3], zs[4], 0])

ans = solve_cvp(B, t, verbose=True)
print("[+] ans:", ans)

m = ans[-1]
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(m))

HarekazeCTF{H0chmu7_k0mm7_v0r_d3m_F411}