ECC-RSA[watevrCTF 2019]

椭圆曲线ECC与RSA

学习出处：https://www.anquanke.com/post/id/196010?display=mobile

题目

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


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")

分析

RSA中（p,q）是以G为基点，P,a,b为参量的椭圆曲线上一点

已知Q，G，在素数域中推断出私钥s十分困难

通过椭圆曲线方程构造只有一个未知量的基于有限域的多项式

对多项式进行分解，度为1且与n有公因数即可分解p,q

知识点

椭圆曲线方程

定义在Fp(p是大于3的素数上的椭圆曲线方程为

y^2^ =x^3^+ax+b a,b∈Fp

构造多项式

q^2^=p^3^+ap+b(mod P)

两边同乘p^2^

n^2^=p^5^+ap^3^+bp^2^(mod P)

则多项式 f ≡ p^5^+ap^3^+bp^2^-n^2^(mod P)

分解多项式求p

R.<p>=PolynomialRing(GF(P))
f=p^5+a*p^3+b*p^2-n^2
factor=f.factor()
for i in factor:
    if i[0].degree()==1:
        p=Integer(mod(-i[0][0],P))
        if gcd(p,n)!=1:
            q=n//p
            break

注意：①因为p求出来是负数，需要对P求模取正

②mod(-i[0][0],P)的数据类型与n(Integer类型)不同，这里踩了坑，gcd(mod(-i[0][0],P),n)一直等于一，应该进行Integer()类型转换

解题

P= 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
a= -0x3
b= 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00
x= 0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66
y= 0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650
e= 0x10001
n= 0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f
c= 0x3862c872480bdd067c0c68cfee4527a063166620c97cca4c99baff6eb0cf5d42421b8f8d8300df5f8c7663adb5d21b47c8cb4ca5aab892006d7d44a1c5b5f5242d88c6e325064adf9b969c7dfc52a034495fe67b5424e1678ca4332d59225855b7a9cb42db2b1db95a90ab6834395397e305078c5baff78c4b7252d7966365afed9e
R.<p>=PolynomialRing(GF(P))
f=p^5+a*p^3+b*p^2-n^2
factor=f.factor()
for i in factor:
    if i[0].degree()==1:
        p=Integer(mod(-i[0][0],P))
        if gcd(p,n)!=1:
            q=n//p
            break
d=inverse_mod(e,(p-1)*(q-1))
m=pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))

椭圆曲线学习出处

https://www.cnblogs.com/Kalafinaian/p/7392505.html

https://www.freebuf.com/articles/database/155912.html

https://www.freebuf.com/articles/database/165851.html