from fastecdsa.curve import P521 as Curve from fastecdsa.point import Point from Crypto.Util.number import bytes_to_long, isPrime from os import urandom from random import getrandbits def gen_rsa_primes(G): urand = bytes_to_long(urandom(521//8)) while True: s = getrandbits(521) ^ urand Q = s*G if isPrime(Q.x) and isPrime(Q.y): print("ECC Private key:", hex(s)) print("RSA primes:", hex(Q.x), hex(Q.y)) print("Modulo:", hex(Q.x * Q.y)) return (Q.x, Q.y) flag = int.from_bytes(input(), byteorder="big") ecc_p = Curve.p a = Curve.a b = Curve.b Gx = Curve.gx Gy = Curve.gy G = Point(Gx, Gy, curve=Curve) e = 0x10001 p, q = gen_rsa_primes(G) n = p*q print((q**5 - a*q**3 + b*q**2 - n**2) / ecc_p) file_out = open("downloads/ecc-rsa.txt", "w") file_out.write("ECC Curve Prime: " + hex(ecc_p) + "\n") file_out.write("Curve a: " + hex(a) + "\n") file_out.write("Curve b: " + hex(b) + "\n") file_out.write("Gx: " + hex(Gx) + "\n") file_out.write("Gy: " + hex(Gy) + "\n") file_out.write("e: " + hex(e) + "\n") file_out.write("p * q: " + hex(n) + "\n") c = pow(flag, e, n) file_out.write("ciphertext: " + hex(c) + "\n")
楕円曲線上の点 Qのx y座標をそれぞれ p , q として使ったRSA。つまり という関係がある。 を代入すると未定変数は 1つになる。
ので、 剰余方程式を解くテク をやるだけ
from sage.all import * from Crypto.Util.number import * n = 0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f a = -0x3 b = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00 PRIME = 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PR, x = PolynomialRing(FiniteField(PRIME), name="x").objgen() f = (n**2) - (x**5) - a * (x**3) - b * (x**2) polys = f.roots() for ans in polys: if isPrime(int(ans[0])): p = int(ans[0]) break q = n // p c = 0x3862c872480bdd067c0c68cfee4527a063166620c97cca4c99baff6eb0cf5d42421b8f8d8300df5f8c7663adb5d21b47c8cb4ca5aab892006d7d44a1c5b5f5242d88c6e325064adf9b969c7dfc52a034495fe67b5424e1678ca4332d59225855b7a9cb42db2b1db95a90ab6834395397e305078c5baff78c4b7252d7966365afed9e phi = (p-1)*(q-1) e = 65537 d = inverse_mod(e, phi) m = pow(c, d, n) print(bytes.fromhex(hex(m)[2:]))