# RSA

* [The original paper.](http://people.csail.mit.edu/rivest/Rsapaper.pdf)
* <https://en.wikipedia.org/wiki/RSA_(cryptosystem)>

### Method

* Choose random semi-prime n = p \* q
* Choose random e: gcd(e, (p-1)(q-1)) = 1
* d: ed = 1 mod (p-1)(q-1)

Public key: (e, n)

Private key: (d, n)

Encrypt: E(M) = M^e mod n

Decrypt: D(C) = C^d mod n

### Math

D(E(M)) = M is proved based on Fermat's little theorem or Euler's theorem.

(p-1)(q-1) is the Euler's totient number for n (number of integers less than n co-prime with it).

Knowing p and q, it's trivial to compute d from e. Not knowing: supposedly hard.

### Attacks and Stuff

* There are many ways to choose weak keys.
  * <https://github.com/Ganapati/RsaCtfTool>
  * <https://www.sjoerdlangkemper.nl/2019/06/19/attacking-rsa/>
* Needs strong random number generator, otherwise can be factorized.
* Needs good padding.
  * <https://en.wikipedia.org/wiki/Semantic_security>
  * <https://en.wikipedia.org/wiki/Padding_(cryptography)>

### RSA Problem

* ["If we consider the problem of finding the private exponent 𝑑 then it is proven by Miller to be computationally equivalent to factoring 𝑛;"](https://crypto.stackexchange.com/questions/89883/is-it-proven-that-breaking-rsa-is-equivalent-to-factoring-as-of-2021)
  * [Breaking RSA Generically is Equivalent to Factoring.](https://eprint.iacr.org/2008/260.pdf)
* Decrypting a single cyphertext: not necessarily as difficult as factoring. It probably isn't.

### Format

DER: binary format; modulo concatenated with exponent.

PEM: base64-encoded DER.

<https://tls.mbed.org/kb/cryptography/asn1-key-structures-in-der-and-pem>