Challenge

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))

Solution

RSAの大きな素数q,rが楕円曲線上である点とその2倍点のx座標間の関係性を持つので特定可能。

倍算公式を用いて手計算で展開する解き方ではなく、sageに丸投げできる方法で解く。

• $\mathbb{F}_p$ 上の楕円曲線 $E/\mathbb{F}_p$ と倍算 $[2]$ を考える。

  Sage の x_rational_map() は有理関数 $f(x)\in\mathbb{F}_p(x)$を返し、

  $x([2]P)=f(x(P))$が成り立つ。

• ある点 $Q\in E(\mathbb{F}_p)$について $q=x(Q)∈\mathbb{F}_p$, $r=x([2]Q)∈\mathbb{F}_p$とし、

  問題から、$n=qr\in\mathbb{Z}$とする。

  なお、$n_p:=n\bmod p\in\mathbb{F}_p$

• 楕円曲線上の関係で $r=f(q)$

  RSAの式から $n_p=q\cdot r$ なので $r=n_p/q$

  よって

  $f(q)-n_p/q=0\quad(\mathbb{F}_p)$

• 左辺は $\mathbb{F}_p(x)$ の有理関数だから

  $f(x)-n_p/x=\frac{F(x)}{G(x)}\quad(F,G\in\mathbb{F}_p[x])$

  と書け、これは分子だけを見ればよく、$F(q)=0$

  つまり q は $F(x)$ の根

• 根（の代表）を列挙し、gcdを取れば、qが求まる。

Final Script

sage

# 体と曲線
Fp = GF(p)
E  = EllipticCurve(Fp, [Fp(a), Fp(b)])

# f(x) ∈ Fp(x):  x([2]P) = f(x(P))
f_x = E.scalar_multiplication(2).x_rational_map()

# Fp(x) の生成元
X = f_x.parent().gen()

# n を Fp に落としたもの（= n mod p）
n_mod_p = Fp(n)

# g(X) = f(X) - n_mod_p / X ∈ Fp(x)
# F_X は g(X) を通分したときの分子 ∈ Fp[X]
F_X = (f_x - n_mod_p / X).numerator()

# F_X(α)=0 の根 α ∈ Fp を候補として、整数 n と gcd を取って因数回収
p_factor = None
for alpha, mult in F_X.roots():
    g = gcd(Integer(n), Integer(alpha))
    if g != 1 and g != n:
        p_factor = Integer(g)   # = q (または r)
        break

q = p_factor
r = Integer(n) // q
print("[+] q =", hex(q))
print("[+] r =", hex(r))

# RSA 復号
phi_n = (q - 1) * (r - 1)
d = inverse_mod(Integer(e), phi_n)
m = power_mod(Integer(c), d, Integer(n))
msg = Integer(m).to_bytes((Integer(m).nbits() + 7)//8, "big")
print(msg)