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 $\lambda (n)$ is used to compute $d$ and is equal to the $lcm(p-1,q-1)$, another definition for $\lambda (n)$ is that

$$\lambda (pq)=lcm(\lambda (p),\lambda (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\equiv m(modn)$$

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 is implemented in 3 steps:

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

$$\lambda (n)=lcm(\lambda (p),\lambda (q))$$

but Euler's totient function is perfectly valid to use with RSA. Euler's totient is

$$\varphi (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 $\lambda (n)=lcm(p-1,q-1)$

   • $\lambda (3233)=lcm(60,52)=780$

4. Choose a public exponent such that $1<e<\lambda (n)$ and is coprime (not a factor of) $\lambda (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\ast e(mod\lambda (n))=1$
   • $d\ast 17(mod780)=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(modn)$ or:

$$c=m^{17}(mod3233)$$

Decryption

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

The plaintext is equal to $c^d(modn)$ or:

$$m=c^{413}(mod3233)$$

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<n^0.292$)
• Elliptic Curve Method
• Pollards $p-1$ for relatively smooth numbers
• Mersenne primes factorization