Yorkville High School Computer Science Department
Yorkville High School Computer Science Department on Facebook  Yorkville High School Computer Science Department Twitter Feed  Yorkville High School Computer Science Department on Instagram

Yorkville High School Computer Science

ASSIGNMENTS: Build a Computer - September 25, 2018 :: Network App - December 14, 2018

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:

  1. Pick an odd integer n at random.
  2. Pick an integer a < n at random.
  3. Perform a probabilistic primality test with a as a parameter. If n fails, reject n and repeat step 1.
  4. 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:

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.

Yorkville High School Computer Science Department on Facebook Yorkville High School Computer Science Department Twitter Feed Yorkville High School Computer Science Department on Instagram