Union CTF | Mordell Primes

#UnionCTF

from Crypto.Util.number import bytes_to_long
from secrets import k, FLAG

assert k < 2^128
assert FLAG.startswith(b'union{')

E = EllipticCurve(QQ,[0,1,0,78,-16])
P = E(1,8)
Q = k*P
R = (k+1)*P

p = Q[0].numerator()
q = R[0].numerator()

assert is_prime(p)
assert is_prime(q)

e = 0x10001
N = p*q
m = bytes_to_long(FLAG)
c = pow(m,e,N)

print(f'N = {N}')
print(f'c = {c}')

有理数体上のEllipticCurveで秘密鍵を生成しているRSA

有理数体では点の座標が無限に大きくなれるので、それっぽい大きさのところを2分探索してもいいし、bruteforceしてもとける

E = EllipticCurve(QQ,[0,1,0,78,-16])
P = E(1,8)

N = ...
c = ...

for k in range(2, 1000):
    Q = k*P
    R = (k+1)*P

    M = Q[0].numerator() * R[0].numerator()
    if N == M:
        p, q = (Q[0].numerator(), R[0].numerator())
        break
else:
    quit()

e = 0x10001
N = p*q
phi = (p-1)*(q-1)
d = inverse_mod(e, phi)

m = pow(c, d, N)
print(bytes.fromhex(hex(m)[2:]))