Computer Security :: Lessons :: The RSA Algorithm
The RSA Algorithm
The Rivest-Samir-Adleman scheme, or RSA algorithm, was one of the first successful public-key cryptographic systems, and since the later 1970s has been the most widely-used public-key system. The plaintext and ciphertext of the RSA cipher are both integers between 0 and n - 1. Typically n is 1024 bits, or 309 decimal digits. The algorithm uses exponential expressions and modulus to encrypt and decrypt.
Key Generation
To use the RSA public-key cryptosystem, each participant has to generate a pair of keys. To do this, two prime numbers, p and q, must be selected. Then an encryption (e) or decryption (d) number must be selected so the other can be calculated. The procedure for picking a prime number is the following:
- Pick an odd integer n at random.
- Pick an integer a < n at random.
- Perform a probabilistic primality test with a as a parameter. If n fails, reject n and repeat step 1.
- If n has passed a sufficient number of tests, accept n, accept n; otherwise, go to step 2.
RSA Security
There are five potential approaches to attacking the RSA algorithm:
- Brute Force: Trying all possible private keys.
- Mathematical Attacks: Factoring the product of the two prime numbers.
- Timing Attacks: Using the runtime of the decryption algorithm to narrow down the space for a brute force attack.
- Hardware Fault-Based Attack: Inducing hardware faults in the processor that is generating digital signatures.
- Chosen Ciphertext Attacks: Exploit properties of the RSA algorithm.
The most likely attack on RSA would be factoring n into its two prime factors. This has been accomplished up to 232 decimal digits so currently RSA-1024 is safe. This table shows the progress made on RSA factoring.
