ECC-RSA - watevrCTF 2019

Crypto
, , ,

Challenge Description

1
ECC + RSA = Double security!

Attachment

- ecc-rsa.py
- ecc-rsa.txt

ecc-rsa.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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")

ecc-rsa.txt

1
2
3
4
5
6
7
8
ECC Curve Prime: 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Curve a: -0x3
Curve b: 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00
Gx: 0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66
Gy: 0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650
e: 0x10001
p * q: 0x1d61da34917e872315d41403c6a59911be97ba4673b0ff1e40201a7c7381845716d1e2f3906f226f649d663af7d9f68e0029629ff9bb07991db2bdff13adad242e9c4c06c6b5cf1ca5fa20eae64f1cdc2376651a4a7f7610e71257ce5da3cc8389c80797a2a9952bcd8c165d0dd5eef523ceb96748eb5aa66d0b4959dcef6a53dac5
ciphertext: 0x12fc466fa277837af8f20c59144d22e80fe4f9ab7371668487cdea44ff1677655d8628aacb688747c2bca111c3b34fa034b9915736fc614c3233bf6445d5ee90eac16a218770f296885bd997989f64a2e70324bba4171ad39759435b4f6d598952e6600eb663d5d9a210baa7134b1aa556aa56a092e7414127a1c35a3bbb1cbb455c

Observation

We can notice that the primes are generated using a custom function named gen_rsa_primes,
and that function gets a random point of the given elliptic curve and checks if both
co-ordinates are primes and thus maintain a relationship between the primes, and that relation is
the equation of the curve.

means: y^2 = x^3 + a*x + b =>=> q^2 = p^3 + a*p + b

Exploit Idea

- Recover primes using the relation
- Decrypt the Ciphertext to get the Flag

Recovering Primes using the curve equation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# ECC params
lines = open("downloads/ecc-rsa.txt", "r").read().split("\n")
p = ZZ(lines[0].split(" ")[-1])
a = ZZ(lines[1].split(" ")[-1])
b = ZZ(lines[2].split(" ")[-1])

# RSA params
e = ZZ(lines[5].split(" ")[-1])
n = ZZ(lines[6].split(" ")[-1])
c = ZZ(lines[7].split(" ")[-1])

# Definitions
P = GF(p)
E = EllipticCurve(P, [a, b])
G = E(Gx, Gy)

# Equation
F. < x > = PolynomialRing(P)
f = x ^ 5 + a*x ^ 3 + b*x ^ 2 - n ^ 2

# Finding Primes
p = [int(i[0]) for i in f.roots() if int(n) % int(i[0]) == 0][0]
q = n//q

Decryption

1
2
3
4
5
6
phi = (p-1)*(q-1)
d = invert(e, phi)

m = pow(c, d, n)

flag = b'watevr{' + long_to_bytes(m) + b'}'

Exploit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# ECC params
lines = open("downloads/ecc-rsa.txt", "r").read().split("\n")
p = ZZ(lines[0].split(" ")[-1])
a = ZZ(lines[1].split(" ")[-1])
b = ZZ(lines[2].split(" ")[-1])

# RSA params
e = ZZ(lines[5].split(" ")[-1])
n = ZZ(lines[6].split(" ")[-1])
c = ZZ(lines[7].split(" ")[-1])

# Definitions
P = GF(p)
E = EllipticCurve(P, [a, b])
G = E(Gx, Gy)

# Equation
F. < x > = PolynomialRing(P)
f = x ^ 5 + a*x ^ 3 + b*x ^ 2 - n ^ 2

# Finding Primes
p = [int(i[0]) for i in f.roots() if int(n) % int(i[0]) == 0][0]
q = n//q

# Decryption
phi = (p-1)*(q-1)
d = invert(e, phi)

m = pow(c, d, n)

flag = b'watevr{' + long_to_bytes(m) + b'}'

assert flag == b'watevr{lol}'

Flag

b’watevr{lol}’