Daily AlpacaHack: ECRSA Writeup

ECRSA

Elliptic Curve x RSA = ECRSA

import os

# secp521r1 patemeter
p = 0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
K = GF(p)
a = K(0x01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc)
b = K(0x0051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00)
EC = EllipticCurve(K, (a, b))

while True:
    Q = EC.random_point()
    q = int(Q.xy()[0])
    R = 2*Q
    r = int(R.xy()[0])
    if is_prime(q) and is_prime(r):
        break

n = q*r
e = 65537
m = int.from_bytes(os.environ.get("FLAG", "Alpaca{dummy}").encode(), "big")
assert m < n
c = pow(m, e, n)

print("n = {}".format(n))
print("e = {}".format(e))
print("c = {}".format(c))

今回の楕円曲線のパラメータはsecp521r1(別名: NIST P-521)を使用しています。
secp521r1はSECG の SEC 2 で定義された素数体$\mathbb{F}_p$上の推奨曲線です。
secpはStandards for Efficient Cryptography(SEC)とprime field(p)を表します。
521は$p$のビット長を表しており、この曲線では、$p = 2^{\scriptstyle 521} - 1$が使われています。
r1は、rがverifiably at random(検証可能なランダム方式)を、1はその系列内でのバリエーション番号を表しています。これは、曲線パラメータの選定に恣意性が入りうるため、seed を公開し、その seed から SHA-1 を用いて係数$b$ を導出する手順も公開することで、第三者が同じ seed から同じ $b$ を再現・検証できるようにしたものです。
余談ですが、sepc256k1のkはKoblitzを表します。
https://www.secg.org/sec2-v2.pdf

解法

今回の問題において、$q = x(Q), r = x(2Q)$をそれぞれ整数とし、$q, r \in \mathbb{P}$となるように設定しています。
ここで重要なのは、$r$は$q$の$x$座標を2倍した位置にあるということです。これは、楕円曲線の2倍公式を使えば、$q, r$を示すことができます。

今回の曲線$y^2 \equiv x^3 + ax + b \pmod p$上の点$(x_1, y_1)$の2倍点$(x_2, y_2)$は以下の式で求められます。

\begin{align}
x_2 &\equiv \lambda^2 - 2x_1 \pmod p\\
y_2 &\equiv \lambda(x_2 - x_1) + y_1 \pmod p
\end{align}

ただし、$\lambda \equiv \frac{3x_1^2+a}{2y_1} \pmod p$とします。

$q = (q_x, q_y), r = (r_x, r_y)$とすると、

\begin{align}
r_x &\equiv \lambda^2 - 2q_x \pmod p\\
r_y &\equiv \lambda(r_x - q_x) + q_y \pmod p
\end{align}

となります。
ここで、

\begin{align}
r_x &\equiv \lambda^2 - 2q_x \\
&\equiv \left(\frac{3q_x^2+a}{2q_y} \right)^2 - 2q_x\\
&\equiv \frac{9q_x^4 + 6aq_x + a^2}{4q_y^2} - 2q_x \pmod p
\end{align}

となり、$y^2 \equiv x^3 + ax + b \pmod p $から$q_y^2 \equiv q_x^3 + aq_x + b \pmod p$と表すことができるので、

\begin{align}
r_x &\equiv \frac{9q_x^4 + 6aq_x + a^2}{4(q_x^3 + aq_x + b)} - 2q_x\\
&\equiv\frac{(9q_x^4 + 6aq_x^2 + a^2) - 8q_x(q_x^3 + aq_x + b)}{4(q_x^3 + aq_x + b)}\\
&\equiv \frac{q_x^4 - 2aq_x^2 - 8bq_x + a^2}{4(q_x^3 + aq_x + b)} \pmod p
\end{align}

と変形することができます。
今回の問題では、$q, r$ともに$x$座標のみを使用しています。
つまり、$n = qr$は以下のようになります。

$$
n \equiv qr \equiv q\cdot\frac{q_x^4 - 2aq_x^2 - 8bq_x + a^2}{4(q_x^3 + aq_x + b)} \pmod p
$$
となり、$n$を$q$のみで表すことができました。

最後に、方程式として解くために少し変形しましょう。

$$
4n(q_x^3 + aq_x + b) - q(q_x^4 - 2aq_x^2 - 8bq_x + a^2) \equiv 0 \pmod p
$$
よって、未知の変数$q_x$を使って根を求め、$n = qr$を満たす$q$を見つけられたらそれを用いて復号すればフラグを得られます。

from Crypto.Util.number import long_to_bytes
from sage.all import *

n = 24489807923160829853331858278295353076882496748356437425136070159565438013983472411573830861255379509744527059864107405391335396070661875605498494586447825822788450364814932266675738776136998383491576779465083731669643596152181500936763824489148317369367655622357267302603914593581625372679508643581386912033877057
e = 65537
c = 2878521000528279319502304373550176174118970956553760958198895851295578685557304197481600194317208136193632870619822554981703968844914526643614371981441816886658546070361109613762488893788055957762778868012759138069722552457665235326670564609161988943959614368453819936924812599400584406309008222724731151234689436

p = 0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
K = GF(p)
a = K(0x01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc)
b = K(0x0051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00)
EC = EllipticCurve(K, (a, b))

R = PolynomialRing(K, "q")
q = R.gen()

poly = 4*K(n)*(q**3 + a * q + b) - q*(q**4 - 2*a*q**2 - 8*b*q + a**2)
poly = poly.monic()

roots = poly.roots(multiplicities=False)
if not roots:
    raise ValueError("No roots found")
for root in roots:
    r = n // int(root)
    if r * int(root) == n:
        q = int(root)
        break

phi = (q-1)*(r-1)
d = pow(e, -1, phi)
flag = pow(c, d, n)
print(long_to_bytes(flag).decode())

Flag: Alpaca{easier_cracked_ruined_suboptimal_algorithm}