l4p1n
ff3bfb1876

3 weeks ago  

src  3 weeks ago  
.gitignore  3 weeks ago  
Cargo.lock  3 weeks ago  
Cargo.toml  3 weeks ago  
README.md  3 weeks ago 
README.md
Breaking RSA
The exercise assignment was:
The folder
x509
contains 1000 root certificates. Each public key consists of
 a 4096bit RSA modulus and
 a public exponent set to 65537.
Can you factorize one (or more) modulus and get the private exponent?
This little program is one solution to the problem, written in Rust.
Requirements
 Rust compiler version 1.51.0 or greater. May work in previous versions, but no guarantee.
Executing the program
 Put your certificates into
certificates
 Compile and launch the program with
cargo run release
. The compiled executable lives intarget/release/RSAbreak
.
Principle
Given:
e
= the exponent (constantPUBLIC_EXPONENT
in the code)n
=p * q
= modulus
We need to find:
p
= 1st factor in the key generationq
= 2nd factor in the key generation
Knowing that n = p * q
, I can say that p = n / q
, which doesn't help much does it ?
Factorizing a 4096 bit number (n) is not practical and, as such, is not an option. If we had only one key, looking at it, you could have said "We can't factorize that".
But we have multiple public keys. Computing the greatest common divisor (GCD) of an integer is efficient.
Since RSA relies on two random huge numbers to be secure (they don't fit in the largest integer type of Rust, u128
 Unsigned integer of 128 bits), what if, by pure luck or with poor random number generation, two keys shared one factor ?
In other words, what if one public key shared one random number q
with another public key ? With symbols, what if n
from one key is a * q
and n
from another key is b * q
. If we happen to find one common divisor, the system falls apart.
With one known factor q
, we can very easily divide n
by q
and get p
. With p
, q
, n
and e
, we can compute the private part of the key d
.
Method from one video of LiveOverflow, summarized above:
Recover RSA private key from public keys  rhme2 Key Server (crypto 200)