Cracking an RSA key
This was created for the Bitsight finding that says a 1024-bit long RSA key is too short.
Basics
The public key has two parts, the modulus and the public exponent. The modulus is generated by multiplying two large numbers; finding these numbers is called the factorization problem. Once found, the private key can be generated.
How RSA works: here.
Notes for CTF
CTF may require you to crack keys. Typically these keys are generated in a way so it is easier to bruteforce the primes. CTF-specific tool.
For example, if the two prime numbers are close to each other, the fastest algo is Fermat.
Find a key
Look up any DKIM key:
https://mxtoolbox.com/SuperTool.aspx?action=dkim%3amail.eftours.com%3aneolane&run=toolpageParse the key to get the modulus
Using an online tool
FYIcenter Public/Private Key Decoder and Viewer
Using openssl
openssl rsa -in test.key -text -nooutDecode private key using openssl
Finding the factors
Classical computing
Multiple factorization algorithms. Finding factors for numbers that are longer than 1024 bits is not feasible.
- GNFS (the general number field sieve).
yafu
This CLI tool uses multiple algorithms and claims to be the fastest to find the prime factors.
b4den
docker pull b4den/rsacrackdocker run b4den/rsacrack 80336855234907714168477675917972994189398342031083238074132216291031761724679Distributed computation
Cado
Quantum computing
Shor's algorithm is the most efficient. It is not fault tolerant; there are not enough qubits in publicly available quantum computers to work on real keys.
Current record holder is China: in December 2022, the 48-bit factorisation 261980999226229 = 15538213 × 16860433.
Practical test
https://mxtoolbox.com/SuperTool.aspx?action=dkim%3amail.eftours.com%3aneolane&run=toolpageDecimal value of modulus (512 bits):
11727072126368842823241799238001370926495779394333067486602074378877544296380125130127358294020854876980544613061262402088368482995636801387448982841270869Finding the factors locally, started Monday 6:02 PM. Probably not practical.