CTF: RedPwn 2021
Description: Blecc! What are all these numbers? This doesn't look like RSA...
Solves: 146 out of 1418 teams
The challenge contains a file named blecc.txt with the following content:
p = 17459102747413984477
a = 2
b = 3
G = (15579091807671783999, 4313814846862507155)
Q = (8859996588597792495, 2628834476186361781)
d = ???
Can you help me find
Decode it as a string and wrap in flag format.
The description, the file contents and the challenge's name itself Blecc gives us a big hint "ECC" regarding Elliptic-Curve Cryptography. We are given:
p the prime modulus.
a, b, G and Q
Usually a capital letter contains the point on the elliptic curve and lowercase letters mean integer scalar.
Once we understand the information given, we are ready to compute
d. I am using SageMath to do the maths. The finite field can be defined as
F = GF(P), and we can define an Elliptic Curve
E in Sage using the
E = EllipticCurve(GF(p),[a, b]).
In this case
Q = k*G so
Q = d*G or
Q = GF(p)*G, and solve
d from the equation
d = G.discrete_log(Q).
We can use
pycryptodome or use
x.to_bytes((x.bit_length() + 7)//8, 'big') to convert
7868191182322623331 to a string format:
And the flag for this crypto challenge is