yoshikingのがんばる日記

あたまよくないけどがんばります

Harekaze mini CTF 2020 Writeup

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

Disaster Level Hackerのwriteupはこちら

ptr-yudai.hatenablog.com

[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}