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¶
 The Public Key is made up of (n, e)
 The Private Key is made up of (n, d)
 The message is represented as m and is converted into a number
 The encrypted message or ciphertext is represented by c
 p and q are prime numbers which make up n
 e is the public exponent
 n is the modulus and its length in bits is the bit length (i.e. 1024 bit RSA)
 d is the private exponent
 The totient λ(n) is used to compute d and is equal to the lcm(p1, q1), another definition for λ(n) is that λ(pq) = lcm(λ(p), λ(q))
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:
(m^{e})^{d} ≡ m (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 (m^{e})^{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)
 Choose two prime numbers such as:
 p = 61 and q = 53
 Find n:
 n = pq = 3233

Calculate λ(n) = lcm(p1, q1)
 λ(3233) = lcm(60, 52) = 780

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
 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 m^{e} mod n or:
c = m^{17} mod 3233
Decryption¶
With the private key, m can be decrypted trivially as well
The plaintext is equal to c^{d} mod n or:
m = c^{413} 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
 SelfInitializing 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 < n^{0.292})
 Elliptic Curve Method
 Pollards p1 for relatively smooth numbers
 Mersenne primes factorization