You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long. l4p1n ff3bfb1876 3 weeks ago
3 weeks ago
3 weeks ago
3 weeks ago
3 weeks ago
3 weeks ago

# Breaking RSA

The exercise assignment was:

The folder `x509` contains 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.

## 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 in `target/release/RSA-break`.

## Principle

Given:

• `e` = the exponent (constant `PUBLIC_EXPONENT` in the code)
• `n` = `p * q` = modulus

We need to find:

• `p` = 1st factor in the key generation
• `q` = 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)