Life is probably full of bugs
#

問題
#

多分人生はバグだらけ

import os
import secrets
from Crypto.Util.number import isPrime, getPrime, bytes_to_long

e = 65537
D = 3
bits = 1024
FLAG = os.environ.get("FLAG", "Alpaca{REDACTED}")

while True:
    V = secrets.randbelow(max(1 << (bits - 1), (1 << bits) - 1))
    if V % 2 == 0:
        V += 1
    p = (D * V**2 + 1) // 4
    if isPrime(p):
        break

q = getPrime(bits)
if q == p:
    q = getPrime(bits)
N = p * q

m = bytes_to_long(FLAG.encode())
assert m < N
c = pow(m, e, N)

print("N =", N)
print("e =", e)
print("c =", c)

素数$p$が

$$ p=\frac{3V^2+1}{4} $$

という特殊な形のRSA問題。以降の説明は[1]を引用しながら説明を実施する。

前提知識
#

一般の体上の楕円曲線
#

体 $K$ 上の楕円曲線を

$$ E/\mathbb{K}:y^2=x^3+Ax+B,\quad A,B\in K,\quad 4A^3+27B^2\ne 0 $$

と書く。ここで点集合$E(\mathbb{K})$は

$$ E(\mathbb{K})={(x,y)\in \mathbb{K}\times\mathbb{K}:y^2=x^3+Ax+B}\cup{\mathcal{O}} $$

と定義される。$\mathcal{O}$ は無限遠点で、加法の単位元である。

ここで、任意の点$P\in E(\mathbb{K})$に対して、スカラー倍算$mP(m\in \mathbb{N})$は加法を繰り返すことで定義される。すなわち、 $$ mP = P + P + \cdots + P(m個)\in E(\mathbb{K}) $$ となる。アフィン座標系では、$mP$は $$ mP=\left(\frac{a_m}{d_m^2},\frac{b_m}{d_m^3}\right) $$

のように表せる。また、次が成立する。

$$ mP=O\Longleftrightarrow d_m=0 $$

j-不変量と twist
#

楕円曲線

$$ E:y^2=x^3+Ax+B $$

の $j$-不変量は

$$ j=\frac{4\cdot 1728A^3}{4A^3+27B^2} $$

で定義される。

後述するが、今回の問題は$j=0$なので、$j=0$に絞って説明を行う。 $j=0$を持つ曲線は

条件	曲線
$j_0=0$	$y^2=x^3+R$

となる。

有限体上の楕円曲線
#

有限体 $\mathbb{F}_p$ 上の楕円曲線について、点の数を

$$ \#E(\mathbb{F}_p)=p+1-t $$

と書く。この $t$ が traceもしくはFrobeniusと呼ぶ。特に

$$ \#E(\mathbb{F}_p)=p $$

となるような曲線、すなわちEがtrace 1のとき、 anomalous curve と呼ぶ。

なお、[2]より、次が知られている。

$$ \#\mathrm{Twist}(E)= \begin{cases} 2 & \text{E の j-不変量が 0,1728 でない場合},\\ 4 & \text{E の j-不変量が 1728 の場合},\\ 6 & \text{E の j-不変量が 0 の場合}. \end{cases} $$

また、$E/\mathbb{F}_p$を有限体$\mathbb{F}_p$上の楕円曲線とし、 $$ n = \#E(\mathbb{F}_p) $$ とする。このとき、任意の点 $P\in E(\mathbb{F}_p)$ に対して

$$ nP=\mathcal{O} $$

が成立する。

CM法とクラス多項式
#

平方数でない整数 $D\in\mathbb{Z}$ と素数 $p$ が $$ 4p-t^2 = DV^2 $$ を満たすとする。ただし、$t\neq 0$, $V\in\mathbb{Z}$ である。また、$H_D(j)$ を判別式 $D$ のクラス多項式とする。

このとき、$H_D(j)$ の根である $j_0$ を $j$-不変量にもつ $\mathbb{F}_p$ 上の楕円曲線 $E$、または $E$ の twist $E’$ は、 trace $t$ を持つ。

もし $E$ が $j_0$ を用いて構成されているならば、 $E$ が trace $t$ を持つ確率は $$ \begin{cases} 1/6 & \text{if } D=3,\\ 1/4 & \text{if } D=1,\\ 1/2 & \text{otherwise}. \end{cases} $$ である。

今回の脆弱性
#

基本的な考え方
#

$N$ の素因数 $p$ が

$$ p=\frac{DV^2+1}{4} $$

という形なら、

$$ 4p-1=DV^2 $$

である($D, V\in \mathbb{Z}$)。ここで $t=1$ と見ると、先ほどの確率に従って$E_p$はanomalousになる。また、Lagrangeの定理より、trace $1$ なら

$$ \#E(\mathbb{F}_p)=p $$

である。よって

$$ pP_p=\mathcal{O}_p $$

となる。$N=pq$ なので、

$$ NP_p=(pq)P_p=q(pP_p)=\mathcal{O}_p $$

である。

ここで、重要なのが、$N$が合成数であるため、$\mathbb{Z}_N$ が体ではないことにある。点加算の途中で割り算 $\alpha/\beta$ が出てきたとき、これらが計算可能である場合、すなわち

$$ \gcd(N,\beta)=1 $$

なら普通に逆元を取れる。一方で

$$ 1<\gcd(N,\beta)<N $$

なら、その $\gcd$ が非自明な因数である。

もう少し詳しく説明を行う。 $kP$ を

$$ kP=\left(\frac{a_k}{d_k^2},\frac{b_k}{d_k^3}\right) $$

とし、 $$ d_{k, p} := d_k \pmod p $$ とする。もし、 $$ kP_p=\mathcal{O}_p $$

なら

$$ d_{k, p}= 0 $$

となり、これは、$d_k$が$p$の倍数であることと同値である。つまり、

$$ g=\gcd(N,d_k) $$

を計算をし、もし、 $g \ne 0$ ならば$g$は$N$の非自明な約数、つまり$p$の倍数となる。

今回のような素数を解くうえでの問題設定
#

今回は$D=3$なので、

$$ p=\frac{3V^2+1}{4} $$

であるため、必要なクラス多項式は $D=3$ のものだけである。

$D$	$H_D(j)$
$3$	$j$

つまり

$$ H_3(j)=j $$

であり、根は

$$ j_0=0 $$

である。したがって使う曲線は

$$ E:y^2=x^3+B $$

でよい。

ランダムに $x,y\in\mathbb{Z}_N$ を選び、

$$ B=y^2-x^3 $$

と置く。すると定義から

$$ y^2=x^3+B $$

なので、

$$ P=(x,y)\in E(\mathbb{Z}_N) $$

である。

なお、先ほどの確率から今回の攻撃は$\frac{1}{6}$で成功する。

アルゴリズム
#

ランダムに $x_0,y_0\in\mathbb{Z}_N$ を選ぶ。
$B=y_0^2-x_0^3$ とする。
$E/\mathbb{Z}_N:y^2=x^3+B$ を作る。
$P=(x_0,y_0)$ とする。
$NP$ を計算する。
分母 $d_N$ に対して $g=\gcd(N,d_N)$ を計算する。
$1<g<N$ なら $g$ が素因数である。
失敗したら別の $x_0,y_0$ でやり直す。

SageMathのVersionが9の場合では、$\mathbb{Z}_N$ 上で逆元を持たない値に遭遇すると ZeroDivisionError が発生する。このエラーに含まれる値が分母に相当するため、その値と $N$ の gcd を取る。一方、SageMathのVersionが10の場合では、その値は射影座標の $Z$ 成分に現れるため、この $Z$ 成分と $N$ の gcd を取る。

import secrets
import re
from Crypto.Util.number import long_to_bytes

from sage.all import *

N = 331870752672014044147181737213412265816523398759615097525139943745771796210285641753397448357034246227758902399979980100515869028774495881259087973250414629281616256673215740614627279222216892287315839494738673533606415338614910770016326702863476621524055282218717990186070218733351509983642415795104346431996804760168955771990411604175165533190602779739268458359854567217134178322927674138876033790911485253556339367464609524645236034199126092787214934713729184221556626485050407422356315907375366959491219626930689355708106915958318935132543131885987076770142681617098974942011563094271188148568855545969095659093800528446912366013535883549657435233957417498281715562124870001144941819675972314842967923288388867960885311992990946028062381240832830506983130996065984416598586021861754119890976275431390726334265905113682082124286691261365801512029848055541389244928274789072868460518572844418477155878801582341572611988431
e = 65537
c = 236295471689740812505534297929776166772230487944897586528275996313476392922101434917708323182972259085517756077698022562556571344836160008877823086658496427525484541816350490066191094376031331588390626750932068822765849532151875048171239488285236932022406536346403199170597031855615328952119177480297569446206867883697875282481420825400971358757678940609305080869495307401953703856417400143035353334696098250915694539028811098974225685730119420661858730616172801478853113561819100764185654102779314050492399799517374934236308687335707876729350908255980585753593111532330811793257046754572488996805570304364492607639321260941111295044137670658741360932069744523665920425619909456645036449386828578036925231188180317472027040431729571764670280822879125187612385724885122670480018785566324155865816458829915767109906969883185680233265251055818532204763281485948242327516716072755766969026316961727158396694728526179105023703302

R = Zmod(N)


def denom_from_zerodiv(ex):
    m = re.search(r"Inverse of\s+(.*?)\s+does not exist", str(ex), flags=re.S)
    if not m:
        return None
    digits = re.findall(r"\d+", m.group(1))
    if not digits:
        return None
    return int("".join(digits))


p = None
for _ in range(50):
    x = secrets.randbelow(N)
    y = secrets.randbelow(N)

    B = (pow(y, 2, N) - pow(x, 3, N)) % N
    E = EllipticCurve(R, [0, B])
    P = E(R(x), R(y))

    try:
        Q = N * P
        g = gcd(int(Q[2]), N)
        if 1 < g < N:
            p = int(g)
            break
    except ZeroDivisionError as err:
        dnm = denom_from_zerodiv(err)
        if dnm is None:
            continue
        g = gcd(dnm, N)
        if 1 < g < N:
            p = int(g)
            break

if p is None:
    raise RuntimeError("factor failed")

q = N // p
d = inverse_mod(e, (p - 1) * (q - 1))
m = power_mod(c, d, N)
print(long_to_bytes(int(m)).decode())

フラグは以下となります。

Alpaca{mirai_tte_kakikake_no_note_jan!!!_82ed9780f16b85f27e69eadbdba4b6625537183b8aebe574678bcb1d46168d43}

おまけ
#

問題文とフラグはあおぎり高校が出している「たぶん人生はバグだらけ」から引用しています。特に未来ってかきかけのノートじゃんという歌詞は好きです。良ければ聞いてね。

https://www.youtube.com/watch?v=WhtLblWwoXU

参考文献
#

[1] Masaaki Shirase, “Condition on composite numbers easily factored with elliptic curve method,” Cryptology ePrint Archive, Paper 2017/403, 2017. Available: https://eprint.iacr.org/2017/403

Life is probably full of bugs#

問題#

前提知識#

一般の体上の楕円曲線#

j-不変量と twist#

有限体上の楕円曲線#

CM法とクラス多項式#

今回の脆弱性#

基本的な考え方#

今回のような素数を解くうえでの問題設定#

アルゴリズム#

おまけ#

参考文献#