UIUCTF 2020 | nook crypt - crypto-writeup-public

EllipticCurve

option 1では $flag * G$ と $hello\_world * G$ の結果を得ることができる。ただし時折 $p$ が壊れた値になるらしい

option 2では任意の平文 $m$ に対して $m*G$ を計算してもらえる

まずは楕円曲線上の点を集めて楕円曲線のパラメータを当てるところからやる。

$y^2 \equiv x^3 + Ax + B \mod p$

$x_1^3 - y_1^2 = k_1p - Ax_1 - B$

$x_2^3 - y_2^2 = k_2p - Ax_2 - B$

に対して $(x_1^3 - y_1^2) - (x_2^3 - y_2^2) = (k_1 - k_2)p - (x_1 - x_2)A$ $\triangle$

同様に　 $(x_2^3 - y_2^2) - (x_3^3 - y_3^2) = (k_2 - k_3)p - (x_2 - x_3)A$ $\square$

この2式に対して次の計算をして、 $A, B$ の影響を消すことができる

$\triangle*(x_2 - x_3) - \square*(x_1 - x_2)$

$= \left((k_1 - k_2)p - (x_1 - x_2)A\right)(x_2 - x_3) - \left((k_2 - k_3)p - (x_2 - x_3)A\right)(x_1 - x_2)$

$= (k_1 - k_2)(x_2 - x_3)p - (x_1 - x_2)(x_2 - x_3)A - (k_2 - k_3)(x_1 - x_2)p + (x_2 - x_3)(x_1 - x_2)A$

$= p(k_1x_2 - k_1x_3 - k_2x_2 + k_2x_3 - k_2x_1 + k_2x_2 + k_3x_1 - k_3x_2)$

$= p(k_1x_2 - k_1x_3 + k_2x_3 - k_2x_1 + k_3x_1 - k_3x_2)$

同様に計算していって 6個の点から4つの $p(...)$ を計算する（ここでそれぞれの式は高々2回しか使っていないことに注意する。こうしないと $p(...)$ の $(...)$ の部分に共通の項が現れてGCDで消えなくなる）

ここまでの話をまとめたものを楕円曲線/6点からパラメータを復元するに書いた。

これの結果、 p = 0xfffffffdffffffffffffffffffffffff がわかる

これと2点があれば、次のように $A, B$ がわかる

$y_1^2 - y_2^2 \equiv x_1^3 - x_2^3 + A(x_1 - x_2) \pmod p$

$A \equiv \left((y_1^2 - y_2^2) - (x_1^3 - x_2^3)\right) {(x_1 - x_2)}^{-1} \pmod p$

$B \equiv y_1^2 - x_1^3 - Ax_1 \pmod p$

ということでこれをやると次のパラメータが求まる。

p = 0xfffffffdffffffffffffffffffffffff
a = 0xd6031998d1b3bbfebf59cc9bbff9aee1
b = 0x5eeefca380d02919dc2c6558bb6d8a5d

これはsecp128r1という有名なパラメータで、こんなのの上ではまず離散対数問題は解けない。

というわけで壊れた $p$ とそれの $flag*G$ $hello\_world*G$ を攻略していく。その前に $G$ をとっておく。これは\x01を暗号化してもいいし、適当に暗号化したやつに対して楕円曲線：逆数をかけるをやっても良い

さてこのような暗号化が成功するには正しい $p$ 、と壊れた $p\prime$ の楕円曲線について、 $G$ がそれぞれの上に無いといけないわけだが、実はこのとき、 $p$ だけでなく $B$ も異なっている。とにかく異なっている。

$flag*G, hello\_world*G, G$ の3点から、 $p\prime$ と $B\prime$ を求める

楕円曲線：A既知のとき3点からpを求める

このとき、 $p\prime$ は素数でない可能性が高い。素数でない $p\prime$ とPohlig HellmanみたいなことをしてもCRTでの復元ができない（＝実質離散対数が存在しない）ので、いくつかのパラメータをとってきて、 $p\prime, p\prime\prime, \dots$ の小さい約数に関して離散対数問題を求めて、CRTで復元する

def recover_p(points):
    """
    NOTICE: points must be int or Integer not on ModRing
    """
    xs = []
    for i in range(len(points)):
        xs.append(points[i][0])

    xy = []
    for i in range(len(points)):
        xy.append(points[i][0]**3  - points[i][1]**2 )


    diffs = []
    for i in range(len(xy)-1):
        diffs.append(xy[i] - xy[i+1])

    pk = []
    for i in range(len(diffs)-1):
        pk.append(diffs[i] * (xs[i+1] - xs[i+2]) - diffs[i+1] * (xs[i] - xs[i+1]))

    return gcd(pk) # p or p * small

p = random_prime(1 << 150)
a = randint(2, p - 1)
b = randint(2, p - 1)

EC = EllipticCurve(GF(p), [a, b])

points = [EC.random_point() for _ in range(6)]
for i in range(len(points)):
    points[i] = [Integer(xy) for xy in points[i].xy()]

p_ = recover_p(points)
print(p_)
print(p)

a_ = (points[0][1] ** 2 - points[1][1] ** 2 - points[0][0] ** 3 + points[1][0] ** 3) * inverse_mod(points[0][0] - points[1][0], p) % p
print(a_)
print(a)

b_ = (points[0][1] ** 2 - points[0][0] ** 3 - points[0][0] * a_) % p
print(b_)
print(b)