||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|
The exercise assignment was:
x509contains 1000 root certificates. Each public key consists of
- a 4096-bit 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.
- Rust compiler version 1.51.0 or greater. May work in previous versions, but no guarantee.
Executing the program
- Put your certificates into
- Compile and launch the program with
cargo run --release. The compiled executable lives in
e= the exponent (constant
PUBLIC_EXPONENTin the code)
p * q= modulus
We need to find:
p= 1st factor in the key generation
q= 2nd factor in the key generation
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
q and get
e, we can compute the private part of the key
Method from one video of LiveOverflow, summarized above: