RSA

• The original paper.

• 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 𝑛;"

  • Breaking RSA Generically is Equivalent to Factoring.
• 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