What is RSA? #
RSA is an asymmetric encryption algorithm, meaning that we have two keys with distinct roles: a public key to encrypt data and a private key to decrypt encrypted data. It is normally impossible to retrieve the private key from the public key.
RSA Formulas #
The formulas needed to create keys, encrypt, decrypt, create a signature, and verify a signature are listed here.
Key Generation #
- Choose distinct prime numbers \(p\) and \(q\)
- Compute the encryption modulus \(n\) with \(n = p*q\)
- Compute \(\varphi(n) = (p-1)(q-1)\)
- Choose a natural number \(e\) coprime with \(\varphi(n)\) and \(1 < e < \varphi(n),\) called the encryption exponent
- Compute \(d\) with \(d = e^{-1} \pmod {\varphi(n)} \) and \(d < \varphi(n),\) called the decryption exponent
With this, we obtain the public key \(n\) and \(e,\) as well as the private key \(n\) and \(d.\)
Encryption #
If \(M \in \mathbb{N}\) and \(M < n\) represents a message, then the encrypted message will be represented by:
\[C = M^e \pmod n\]
Decryption #
To decrypt \(C\), we use \(d = e^{-1} \pmod {\varphi(n)} ,\) and retrieve the plaintext message \(M\) by:
\[M = C^d \pmod n\]
Generating a Signature #
To create a signature, we encrypt \(hash(M)\) with the private key \(d\):
\[S = h^d \pmod n\]
Verifying a Signature #
To verify a signature, we decrypt \(S\) with \(e\):
\[h’ = S^e \pmod n\]
Then we check that \(h’ = h.\)
Some Simple Attacks #
Simple attacks that do not require extensive mathematical knowledge will be listed here. Since I am very bad at math and crypto, there will only be a few simple attacks.
Factorizable \(n\) #
It is sometimes possible to factorize \(n\) to retrieve \(p\) and \(q.\) To do this, you can use the site factordb. Once \(p\) and \(q\) are obtained, you can retrieve \(d\) and get \(Privkey(n, d).\)
Common Factor Attack #
If you have two public keys and \(n_1\) and \(n_2\) share a common factor, it is possible to retrieve \(p,\) \(q_1\), and \(q_2:\)
- \(p = gcd(n_1, n_2)\)
- \(q_1 = \frac{n_1}{p}\)
- \(q_2 = \frac{n_2}{p}\)
Then you just need to compute \(d_1\) and \(d_2.\)
Example Python script:
from math import gcd
def common_factor_attack(n1, n2, c1, c2, e):
p = gcd(n1, n2)
q1 = n1 // p
q2 = n2 // p
phi1 = (p - 1) * (q1 - 1)
d1 = pow(e, -1, phi1)
m1 = pow(c1, d1, n1)
phi2 = (p - 1) * (q2 - 1)
d2 = pow(e, -1, phi2)
m2 = pow(c2, d2, n2)
return (m1, m2)
Low Exponent Attack #
If \(e\) is so small that \(M^e < n,\) then \(M\) can be retrieved from \(C\) with:
\[M = \sqrt[e]{C}\]
Decryption Oracle #
RSA has Homomorphic properties, meaning that:
\[M(x * y) = M(x) * M(y)\] \[C(x * y) = C(x) * C(y)\]
This means that \(M\) can be retrieved with \(C_1 = \frac{C}{x}\) and \(C_2 = x,\) where \(C_1 \in \mathbb{N}\) and \(C_2 \in \mathbb{N}.\) Then, send \(C_1\) and \(C_2\) to the decryption oracle to get \(M_1\) and \(M_2\). Finally, \(M\) can be retrieved because \(M = (M_1 * M_2) \pmod n.\)