BSides Ahmedabad CTF 2021 | ECC-RSA2

#bsidesahmedabadctf_2021

from Crypto.Util.number import getPrime
from hashlib import sha256
import random


def gen_parameters():
    p = getPrime(512)
    q = getPrime(512)
    N = p * q
    a = -3
    while True:
        b = random.randint(0, N)
        if (4*a**3 + 27*b**2) % N != 0:
            break
    x = random.randint(0, N)
    while True:
        y2 = (x**3 + a*x + b) % N
        if Zmod(p)(y2).is_square() and Zmod(q)(y2).is_square():
            break
        x = random.randint(0, N)
    y = CRT([int(Zmod(p)(y2).sqrt()), int(Zmod(q)(y2).sqrt())], [p, q])
    return (N, a, b, (x, y))

with open("flag.txt", "rb") as f:
    FLAG = f.read().strip()


N, a, b, (x, y) = gen_parameters()

EC = EllipticCurve(Zmod(N), (a, b))
P = EC(x, y)

T = P
ct = []
for byte in FLAG:
    r = int(T.xy()[0])
    ct.append(pow(byte*r, 65537, N))
    T += T

with open("backdoor.txt", "w") as f:
    f.write(str(P.xy()))

print(N)
print(a)
print(b)
print(ct)

概要

あるEllipticCurveのパラメータが与えられていて、暗号文は

• 

• 

という具合。

解法

がわかればを求めるのは容易い。まずはを求めたい。はフラグの先頭だろうから既知だと思うと、がを用いてかければ関係式を導き出せそうに見える。そしてこれは2倍公式で表せる

すなわちだが、除算は出来ないので両辺にを掛けて

という関係式になる。

上の同根の方程式が2つあるのでFranklin-Reiter Related Message Attackが可能。と大きいのでhalf-GCDを使うと良い

その他合成数modでのlift_xは重いのでx座標を自分で計算するなどの工夫が必要（中でrootsしているんだと思う）

• 自分で一回y座標計算してしまえばその後は軽いはずなのでそちらでもよい

def pdivmod(u, v):
    """
    polynomial version of divmod
    """
    q = u // v
    r = u - q*v
    return (q, r)

def hgcd(u, v, min_degree=10):
    """
    Calculate Half-GCD of (u, v)
    f and g are univariate polynomial
    http://web.cs.iastate.edu/~cs577/handouts/polydivide.pdf
    """
    x = u.parent().gen()

    if u.degree() < v.degree():
        u, v = v, u

    if 2*v.degree() < u.degree() or u.degree() < min_degree:
        q = u // v
        return matrix([[1, -q], [0, 1]])

    m = u.degree() // 2
    b0, c0 = pdivmod(u, x^m)
    b1, c1 = pdivmod(v, x^m)

    R = hgcd(b0, b1)
    DE = R * matrix([[u], [v]])
    d, e = DE[0,0], DE[1,0]
    q, f = pdivmod(d, e)

    g0 = e // x^(m//2)
    g1 = f // x^(m//2)

    S = hgcd(g0, g1)
    return S * matrix([[0, 1], [1, -q]]) * R

def pgcd(u, v):
    """
    fast implementation of polynomial GCD
    using hgcd
    """
    if u.degree() < v.degree():
        u, v = v, u

    if v == 0:
        return u

    if u % v == 0:
        return v

    if u.degree() < 10:
        while v != 0:
            u, v = v, u % v
        return u

    R = hgcd(u, v)
    B = R * matrix([[u], [v]])
    b0, b1 = B[0,0], B[1,0]
    r = b0 % b1
    if r == 0:
        return b1

    return pgcd(b1, r)

import ast

with open("./output.txt") as f:
    N = ast.literal_eval(f.readline())
    a = ast.literal_eval(f.readline())
    b = ast.literal_eval(f.readline())
    ct = ast.literal_eval(f.readline())

PR.<x> = PolynomialRing(Zmod(N))

e = 65537
m0 = ord("N")
m1 = ord("e")

f1 = (x*m0)^e - ct[0]
f2 = ((x^4 - 2*a*x^2 - 8*b*x + a^2)*m1)^e - (4*x^3 + 4*a*x + 4*b)^e*ct[1]

t1 = cputime()
f = pgcd(f1, f2)
t2 = cputime()

print("[+] time {}".format(t2 - t1))

x = Zmod(N)(-f.monic()[0])


m_table = {pow(m, e, N):m for m in range(256)}

flag = []
for i in range(len(ct)):
    flag.append(m_table[ ct[i] / (x^e) ])

    x = (x^4 - 2*a*x^2 - 8*b*x + a^2) / (4*x^3 + 4*a*x + 4*b)
    print(bytes(flag))