RSA

RSA Encryption Algorithm

Back

Restart

This work is licensed with a Creative Commons Attribution 4.0 International LicenseEndFragment

RSA Encryption Algorithm

1/13

5/13

Now you try:

What are the factors of ? Submit and show next question

Factoring Quiz

Let's try different modulus using our clock example. Create a new modulus clock by entering a modulus number less than 20. This sets the number of clock positions. Now enter a number. When calculating the modulo, just find the remainder or last position, not how many times around.

Number: Modulus: Animate

7/13

Modulus Operation

Element with Audio HTML

N = 14

click to continue

Look at the steps that RSA uses to generate a key pair—we are using small numbers compared to the very large numbers actually used by the algorithm.

1 2 3 4 5

T = ( 2 - 1 ) x ( 7 - 1 ) = 6

1 is a factor of all numbers

Choose two prime numbers

Calculate (e * d) mod Te: d: T: CalculateResult:

4 is not co-prime

= e

2 is a factor of 6 and 14

Multiply the prime numbers together to get the product, N

• Must be co-prime with T and N

Generating a Key Pair

3 is a factor of the Totient

Calculate the Totient, T = (p - 1) x (q - 1)

• Must not be a factor of the Totient

11/13

Select the Public Key (e)

Select the Private Key (d)

• Must be less than the Totient

(e x d) mod T = 1

Use the calculator to test possible values for d given e = 5 and T = 6 so that the Result = 1

p = 2 q = 7

6/13

The RSA algorithm is dependent on modulus mathematics. A modulus is like a clock. A standard clock has 12 positions or a modulus of 12. If it's 10 o'clock now and you wait for 3 hours, what time will it be? Simple, it will be 1 o'clock. Why 1 o'clock and not 13 o'clock? Because when the hour hand completes a full rotation (i.e., 12 hours), it starts over from the beginning, which is analogous to taking the modulus with respect to 12. Imagine the clock only had 9 positions. It would be a modulus of 9. If it had 15 positions, the modulus would be 15.

If it is 7 o’clock and you wait for 8 hours, what time will it be? 7 + 8 = 15 hours 15 mod 12 = 3 hours So, the time will be 3 o'clock

<<-click here to continue->>

To understand prime numbers and the RSA algorithm, it is important to also understand factors. Factoring a number is to express it as a product of (other) whole numbers, called factors. For example, we can factor 12 as 1 x 12, 2 x 6, or 3 × 4. So 1, 2, 3, 4, 6 and 12 are all factors of 12.

Calculate Factors Factors:

Factoring

Enter a number between 2 and 100:

4/13

Factor Calculator

2/13

Alice’s Public Key

Alice’s Private Key

Ciphertext

Decryption

Original Plaintext

Encryption

RSA is an algorithm used for asymmetric encryption. It’s named after its inventors: Rivest, Shamir, and Adleman. Asymmetric encryption uses two different mathematically related keys to encrypt and decrypt messages. A user’s public key is available to anyone while the user’s private key remains protected. The security of RSA comes from the fact that, even if you know the public key and the encrypted message, it’s extremely hard (and would take years) to figure out the private key or the original message. To look at how RSA works (in simple terms, of course), there are a few important mathematical concepts we need to review.

Prime Numbers

3/13

click the button to generate a list of prime numbers from 1 to 10,000

The RSA algorithm is dependent on using two large prime numbers. A prime number is a whole number greater than 1 whose only factors are 1 and itself. Examples of prime numbers are 3, 5, 7,11. There is an infinite list of prime numbers.

Generate Prime Numbers

We kept our examples simple by using small numbers. Generate some larger prime numbers (1,000-1,999) to use as inputs for RSA keys.

13/13

RSA Key GenerationPrime Number 1 (p):Prime Number 2 (q): Generate RSA KeysResults: Prime Number 1: Prime Number 2: N: Euler Totient: Encryption (E): Decryption (D):

Generate Prime Numbers

Key Generation Calculator

8/13

Co-prime numbers are NOT necessarily prime numbers.

Co-prime Numbers

Co-prime numbers are used in the RSA algorithm. Also known as relatively prime or mutually prime numbers, are two numbers that have no common positive integer factors other than 1. Keep in mind the following:

Two numbers can be co-prime even if one or both of them are composite (non-prime).

Two consecutive integers will always be co-prime because one of them will always be even and the other odd, ensuring they have no common divisors apart from 1.

Click to continue

Any two prime numbers are always co-prime to each other since they don’t share any divisor other than 1.

101

Decryption algorithm:

12/13

25 mod 14 = 4

messagee mod N

411 mod 14 = 2

click to encrypt

click to decrypt

Secret message:

Original secret message:

Encryption calculation:

the number 2

Ciphertext

Decryption calculation:

The public key = (e, N) and the private key = (d, N). In the previous scene, we determined that N = 14, e = 5, and one of the possible vales for d is 11. We will use the key pair to step through RSA encryption and decryption.

Ciphertext:

The Algorithm

Encryption algorithm:

Ciphertextd mod N

Quiz

10/13

Co-prime numbers play a significant role in number theory and are widely used in topics related to modular arithmetic, encryption algorithms, and the Euler Totient Function.

9/13

Integer A: Integer B: Are these numbers co-prime?Co-Prime NOT Co-prime Next