RSA

RSA, which is an abbreviation of the author's names (Rivest–Shamir–Adleman), is a cryptosystem which allows for asymmetric encryption. Asymmetric cryptosystems are alos commonly referred to as Public Key Cryptography where a public key is used to encrypt data and only a secret, private key can be used to decrypt the data.

Definitions

What makes RSA viable?

If public n, public e, private d are all very large numbers and a message m holds true for 0 < m < n, then we can say:

(me)dm (mod n)

Note

The triple equals sign in this case refers to modular congruence which in this case means that there exists an integer k such that (me)d = kn + m

RSA is viable because it is incredibly hard to find d even with m, n, and e because factoring large numbers is an arduous process.

Implementation

RSA follows 4 steps to be implemented: 1. Key Generation 2. Encryption 3. Decryption

Key Generation

We are going to follow along Wikipedia's small numbers example in order to make this idea a bit easier to understand.

Note

In This example we are using Carmichael's totient function where λ(n) = lcm(λ(p), λ(q)), but Euler's totient function is perfectly valid to use with RSA. Euler's totient is φ(n) = (p − 1)(q − 1)

  1. Choose two prime numbers such as:
    • p = 61 and q = 53
  2. Find n:
    • n = pq = 3233
  3. Calculate λ(n) = lcm(p-1, q-1)

    • λ(3233) = lcm(60, 52) = 780
  4. Choose a public exponent such that 1 < e < λ(n) and is coprime (not a factor of) λ(n). The standard is most cases is 65537, but we will be using:

    • e = 17
  5. Calculate d as the modular multiplicative inverse or in english find d such that: d x e mod λ(n) = 1
    • d x 17 mod 780 = 1
    • d = 413

Now we have a public key of (3233, 17) and a private key of (3233, 413)

Encryption

With the public key, m can be encrypted trivially

The ciphertext is equal to me mod n or:

c = m17 mod 3233

Decryption

With the private key, m can be decrypted trivially as well

The plaintext is equal to cd mod n or:

m = c413 mod 3233

Exploitation

From the RsaCtfTool README

Attacks:

  • Weak public key factorization
  • Wiener's attack
  • Hastad's attack (Small public exponent attack)
  • Small q (q < 100,000)
  • Common factor between ciphertext and modulus attack
  • Fermat's factorisation for close p and q
  • Gimmicky Primes method
  • Past CTF Primes method
  • Self-Initializing Quadratic Sieve (SIQS) using Yafu
  • Common factor attacks across multiple keys
  • Small fractions method when p/q is close to a small fraction
  • Boneh Durfee Method when the private exponent d is too small compared to the modulus (i.e d < n0.292)
  • Elliptic Curve Method
  • Pollards p-1 for relatively smooth numbers
  • Mersenne primes factorization