RSA is an #Asymmetric Cryptography scheme based on exponentiation in a Galois Field over integers modulo a prime which utilises integers as large as 1024 bits. The running time for exponentiation is \(o((\log n^3))\) operations, which is reasonable. However, to break the #algorithm, it needs \(o(e^{\log n \log \log n})\) factorisations, thus it is hard to crack#.
The security of RSA is guarantee by its Trapdoor One-Way Function# nature as primes \(p\) and \(q\) are only known to the key owner. It is impossible to do a Brute Force Attack on RSA due to the large key size. Other Cryptanalytic Attack such as mathematical attack based on difficulty of computing \(\phi(n)\), by factoring modulus \(n\) (can be overcome by having a larger \(n\)), timing attacks# on decryption algorithm, and chosen ciphertext attacks (CCA) can be done on RSA.
Note: Current \(n\) is of \(2^{1024}\) to \(2^{2048}\) bit size. It is currently assumed to be computational secure#.
The public and private key generation in RSA follows the below steps:
- Randomly select two large primes \(p\) and \(q\).
- Compute \(n = p \cdot q\) where \(n\) will be used use as the modulus for public and private key.
- Compute \(\phi (n) = (p - 1)(q - 1)\). (Euler Totient Function#)
- Select \(e\) such that \(1 < e < \phi (n)\) and \(GCD(e, \phi (n)) = 1\) according to Greatest Common Divisor (GCD)#.
- Find the decryption key \(d\) from \(de = 1 \mod \phi (n)\) and \(0 \le d \le n\).
Note: \(p\) and \(q\) must be kept secret as the attacker could easily compute \(n\) if known. They must be rather large to avoid easy guessing.
Note: \(e\) is usually relatively small or \(65537_{10}\) which is \(10000000000000001_2\) for easy computation by Square-and-Multiply Algorithm#. That being said, \(e\) can’t be either 1 or 2. The former means no encryption is done on \(M\) as \(M^e = M^1 = M\). The latter will not work due (\(d\) not exist) to the nature of Greatest Common Divisor (GCD)# since \(GCD(2, \phi(n))\) will always be 2 as \(\phi(n) = (p - 1) (q - 1)\) where \(p\) and \(q\) are primes results in even number. However, if \(e\) is too small, it is vulnerable to mathematical attack using Chinese Remainder Theorem (CRT)#.
From here, we could get the public key \(pu = \{e, n\}\) and private key \(pr = \{d, n\}\). Encryption could be done on message \(M\) using the formula \(C = M^e \mod n\) where \(0 \le M < n\) by using public key \(pu\) which is typically done by Square-and-Multiply Algorithm# for efficiency. Decryption could be done on ciphertext \(C\) using the formula \(M = C^d \mod n\) by using private key \(pr\) which is usually done by Chinese Remainder Theorem (CRT)#.
RSA works in both encryption and decryption due to the nature of the equation \(de = 1 \mod \phi(n)\) which can be reformed into the equation \(de = 1 + k \phi(n)\) (Modular Arithmetic#) and the fact that \(M^{\phi(n)} \mod n = 1\) (Euler’s Theorem#). From decryption equation \(C^d = M^{e \cdot d} = M^{1 + k \cdot \phi(n)} = M^1 \cdot (M^{\phi(n)})^k = M^1 \cdot 1^k = M^1 = M \mod n\), thus proved that RSA works.
However, using the above algorithm, primarily the decryption part, is exposed to possible Timing Attack# and CCA#. Several ways of Avoiding Timing Attack on RSA# could be done to the algorithm in order to avoid or decrease the efficiency from timing.