Skip to main content

RSA - Key Generation Encryption

Introduction​

  • Introduced in 1977
  • Most popular public key algorithm in the world
  • Not used for encryption. Mainly for digital signatures
  • Keys are usually 2048
  • Security is built around the difficulty of factoring large numbers

Encryption​

  • Encryption performed by the public key can only be reversed using the private key

Key Transport​

  • Historically RSA was often used to encrypt session keys

Signatures​

  • The authenticity of signatures generated by the private key can be verified by the public key

Euler Totient Function​

  • Number of integers for in ZmZ_m for which gcd(a,m)=1gcd(a,m)=1

Integer Factorisation​

  • Any integer can be expressed as the multiplication of a list of prime numbers
  • The longer the value, the harder (and slower) this gets

Fermats Little Theorem​

  • States that for some prime p and any integer a: ap−1==1(modm)a^{p-1}== 1 (mod m)

Key Generation​

  1. Choose two large primes, pp and qq
  2. Calculate the modulus m=p×qm=p\times q
  3. Calculate ...
  4. Choose a value \ep∈2,...\ep \in {2,...} where gcd...=1
  5. Compute dd where d×e\eq1(mod...)d\times e \eq 1 (mod...)

65537

  • Largest known number of the from 22n+12^{2^n} +1
  • Primes of this form are known as Fermat Primes
  • Very useful public exponent for RSA