The RSA Algorithm

The Rivest–Shamir–Adleman Algorithm

UCI 403: Information Assurance and Security

Summary

• Overview
• Key Creation
• Operation
- Simple Example
- Why RSA Works?
• Computational Aspects
- Efficient Encryption
- Efficient Decryption
- Key Generation
• Security
- Mathematical Attack
- Timing Attack
- Chosen Ciphertext Attack

1
 RSA Overview

• Developed by Ronald Rivest, Adi Shamir, and Leonard

Adleman of MIT in 1977.
• Best known and widely used public-key scheme.
- Primarily used to encrypt the session key used for secret key
encryption (key exchange), the message's hash value
(message integrity and digital signatures) or encryption of
small blocks of data.
- Used in hundreds of software products.
• Its mathematical hardness comes from the ease in
calculating the product of two large prime numbers and
the difficulty in finding the prime factors of those large
numbers.

RSA Overview

• The math behind RSA is relatively

straightforward.
• RSA uses a variable size encryption block and a
variable size key.
• The key-pair is derived from a very large number, n,
that is the product of two prime numbers chosen
according to special rules;
- These primes may be 100 or more digits in length each,
yielding an n with roughly twice as many digits as the prime
factors.

2
 RSA Overview

• The public key information includes n and a

derivative of one of the factors of n;
- An attacker cannot determine the prime factors of n
(and, therefore, the private key) from this information
alone and that is what makes the RSA algorithm so
secure.
• RSA key lengths of 512 and 768 bits are
considered to be pretty weak.
- The minimum suggested RSA key is 1024 bits.
- Key lengths of 2048 and 3072 bits are even better.

RSA Key Creation

To create an RSA public/private key pair, these are the

basic steps:
1. Choose two prime numbers at random, p and q.
• From these numbers you can calculate the system modulus:
n = pq.
2. Select a third number at random, e, that is relatively
prime to the product: ø(n)=(p-1)(q-1).
• i.e.: 1 < e < ø(n), gcd(e,ø(n))=1
• The number e is the public exponent.

3
RSA Key Creation

3. Calculate an integer d so that:

• ed mod[ø(n)] = 1, and: 0 ≤ d ≤n
• i.e.: the quotient (ed-1)/ø(n) should be an integer.
• The number d is the private exponent.
4. Publish public encryption key: PU = {e, n}
5. Keep secret private decryption key: PR = {d, n}

Note: It is computationally infeasible to determine d from

PU (n and e) if p and q are large enough.

RSA Operation

• Sender: encrypts a message, M, with public key

PU={e,n}, to create the ciphertext, C, using
the equation:
e
- C = M mod n, where 0≤ M <n
• Receiver: decrypts the ciphertext with the private
key PR={d,n} using the equation:
d
- M = C mod n
• Note: the message M must be smaller than the
modulus n (block if needed).

4
RSA Example - Key Setup

1. Select primes: p=3 & q=5

2. Compute modulus: n = pq = 15
3. Compute: ø(n)=(p-1)(q-1)= 2x4 =8
4. Select e:
1. Must be relatively prime to ø(n)(or gcd(e,8)=1)
2. Choose e=11
5. Determine d: ed mod 8 = 1 and d < 8. Thus
(ed-1)/ø(n)=11d-1/8 must be an integer.
6. Value is d=3 since 3x11=33= 4x8+1
7. Publish public key: PU={11,15}
8. Keep secret private key: PR={3,15}

RSA Example - Operation

• Let's assume we wish to send the string: SECRET.

• We will convert the string to the decimal
representation of the ASCII values of the characters:
0x 83 69 67 82 69 84
• The sender encrypts each digit one at a time (we have
to because the modulus is so small) using the public
key value (e, n) = (11, 15).
- Each ciphertext character is computed:
Ci = Mi11 mod 15.
- The input digit string will be transmitted as:
0x 2c 69 6d 28 69 24

5
RSA Example - Operation

• The receiver decrypts each digit using the private key

value (d, n) = (3, 15).
- Each plaintext character Mi = Ci3 mod 15.
- The input digit string will be converted to 0x 83 69 67 82
69 84
- Then reassembled as the plaintext string SECRET.
• For simplicity, the example above uses small values
and, in fact, shows the weakness of small values; note
that 4, 6, and 9 do not change when encrypted, and
that the values 2 and 8 encrypt to 8 and 2,
respectively.

Why RSA Works

• Euler’s Theorem:
- aø(n) mod n = 1 where gcd(a,n)=1
• In RSA have:
- N = pq
- ø(n)=(p-1)(q-1)
- Carefully chose e & d to be inverses mod ø(n):
• ed mod[ø(n)] = 1
- Hence: ed = 1 + kø(n) for some k
• Thus: ed 1+kø(n) 1 ø(n) k
Cd = M = M = M (M )
= M1.(1)k = M1 = M mod n

6
RSA Computational Aspects

• We will briefly analyse the computational

complexity required to use RSA.
• There are two issues to consider:
- Encryption/Decryption
• This involves raising an integer to an integer power, mod n. -
Key Generation
• This involves determining two large primes at random, and
computing either e or d after selecting the other.

Exponentiation

• Property of modular arithmetic.

- [(a mod n)(b mod n)] mod n = ab mod n
• You can use the Square and Multiply Algorithm.
- Fast, efficient algorithm for exponentiation. -
Based on repeatedly squaring base.
- Then multiplying in the ones that are needed to compute the
result.
• Look at binary representation of exponent
- It only takes O(log2 n) multiples for number n.
- E.g.: 75 = 74.71 = 3.7 = 10 mod 11
- E.g.: 3129 = 3128.31 = 5.3 = 4 mod 11

7
Exponentiation

• Algorithm to compute: ab mod n

c = 0; f = 1
for i = k down to 0
do c = 2 x c
f = (f x f) mod n
if bi == 1 then
c = c + 1
f = (f x a) mod n
return f

RSA Efficient Encryption

• Encryption uses exponentiation to power e.

• Hence if e small, this will be faster.
- Most common choice: e=65537 (216-1). -
Other popular choices: e=3 or e=17.
• But if e too small (e.g. e=3) RSA becomes vulnerable:
- Using Chinese Remainder Theorem and same message M sent to
three different users with different modulii (n1, n2, n3).
- Problem reduced to finding a cubic root as: M3 < n1n2n3.
• If e fixed must ensure gcd(e,ø(n))=1.
- i.e. Reject any p or q not relatively prime to e.

8
RSA Efficient Decryption

• Decryption uses exponentiation to power d.

- Likely to be large, insecure if not.
• Can use the Chinese Remainder Theorem (CRT) to
compute mod p and q separately, then combine to get
desired answer.
- Approx 4 times faster than doing directly.
• Only the owner of the private key can use this
technique as only s/he who knows values of p and
q.

RSA Key Generation

• Users of RSA must:

- Determine two primes at random: p,q.
- Select either e or d and compute the other.
• Primes p,q must not be easily derived from modulus
n=pq.
- Must be sufficiently large.
• Pick at random a large odd number, test if prime. If not,
pick successive random numbers until found.
- Use a probabilistic primarily test such as the Miller-Rabin test. -
Tedious procedure but not done often.
• Exponents e, d are inverses, so use Inverse algorithm to
compute the other.

9
RSA Security

• Attacker knows the public key (e, n) and needs to find d.

• The attacker will need to find the pair p, q so that pq = n.
- This is quite difficult because p and q are large prime numbers.
• Since d depends on p, q and e, the attacker cannot
easily proceed.
• Possible approaches to attacking RSA are:
- Brute force key search (infeasible given size of numbers).
- Mathematical attacks (based on difficulty of computing ø(n), by
factoring modulus n).
- Timing attacks (on the running of decryption).
- Chosen Ciphertext attacks (given properties of RSA).

Mathematical Attack (Factoring)

• Mathematical approach takes three forms:

- Factor n=pq, hence compute ø(n) and then d. -
Determine ø(n) directly and compute d.
- Find d directly.
• Currently believed all equivalent to factoring:
- It has seen slow improvements over the years.
• May-05 RSA 200 Challenge public key length of 200 decimal
digits (663 bits) with Lattice Sieve algorithm.
- Biggest improvement comes from improved algorithm.
• Quadratic Sieve Generalised Number Field Sieve, Lattice Sieve.
- Currently it is assumed that 1024-2048 bit RSA is secure.
• Counter-measures: Choose p, q so that they fulfil some properties
that make the above attacks more complex.

10
Timing Attack

• Developed by Paul Kocher in mid-1990’s.

- A snooper can determine a private key by keeping track of how
long a computer takes to decipher messages.
• Exploit timing variations in operations.
- E.g. multiplying by small vs. large number. -
Or IF's varying which instructions executed.
• Infer operand size based on time taken.
• RSA exploits time taken in exponentiation.
• Possible counter-measures:
- Use constant exponentiation time. -
Add random delays.
- Blinding: multiply the ciphertext by a random number before
performing the exponentiation.

Chosen Ciphertext Attack

• RSA is vulnerable to a Chosen Ciphertext Attack

(CCA).
• Attacker chooses ciphertexts and gets decrypted
plaintext back.
• Choose ciphertext to exploit properties of RSA to
provide info to help cryptanalysis.
• Possible counter-measures:
• Add random pad of plaintext.
• Use Optimal Asymmetric Encryption Padding (OASP).

11
RSA vs. DES

• Hardware implementations:
- DES is 1,000 faster than RSA.
• Software implementations:
- DES is 100 faster than RSA.

Other Resources

• Most of the material in the previous slides was

taken from:
• Gary C. Kessler May 1998 (Last updated: 25 May
2022) on:
- https://www.garykessler.net/library/crypto.html
• Stallings, W. Cryptography and Network Security. 4
Ed. Prentice Hall.

12