Lecture 4: RSA Encryption
RSA Cryptography
A useful and basically unbreakable method for
encoding messages
Needed for implementing RSA:
Prime Factorization
Fast Exponentiation
Modular inverses
FLT (Fermat’s Little Theorem)
Euler’s Phi Function
L4 1
L4 2
L4 3
Prime Factorization
To factor a number n is to write it as a product of
other numbers.
n=a*b*c
Or, 100 = 5 * 5 * 2 * 2
Prime factorization of a number n is writing it as a
product of prime numbers.
143 = 11 * 13
Relatively Prime Numbers
Two numbers are relatively prime if they have no
common divisors other than 1.
10 and 21 are relatively prime, in respect to each
other, as 10 has factors of 1, 2, 5, 10 and 21 has
factors of 1, 3, 7, 21.
The Greatest Common Divisor (GCD) of two relatively
prime numbers can be determined by comparing
their prime factorizations and selecting the least
powers.
Relatively Prime Numbers Cont.
For example, 125 = 53 and 200 = 23 * 52
GCD(125, 200) = 20 * 52 = 25
If the two numbers are relatively prime the GCD will
be 1.
Consider the following: 10(1, 2, 5, 10) and 21(1, 3,
7, 21)
GCD(10, 21) = 1
It then follows, that a prime number is also relatively
prime to any other number other than itself and 1.
L4 7
L4 8
L4 9
L4 10
L4 11
Euler’s phi function
is defined by the rule that, for each positive integer n,
(n) = #{ k : 1 ≤ k < n and k is relatively prime to n }.
For example,
(2) = #{1} = 1,
(3) = #{1, 2} = 2,
(4) = #{1, 3} = 2,
(6) = #{1, 5} = 2,
and (12) = #{1, 5, 7, 11} = 4.
L4 12
L4 13
L4 14
L4 15
L4 16
L4 17
L4 18
L4 19
L4 20
Fast Exponentiation
L4 21
Fast Modular Exponentiation
A: By taking the mod after each multiplication.
For example:
233 mod 30 -73 (mod 30)
(-7)2 ·(-7) (mod 30)
49 · (-7) (mod 30)
19·(-7) (mod 30)
-133 (mod 30)
17 (mod 30)
Therefore, 233 mod 30 = 17.
L4 22
Fast Modular Exponentiation
Q: What if had to figure out 2316 mod 30.
A: Better way. Notice that 16 = 2·2·2·2 so that 2316 =
232·2·2·2 = (((232)2)2)2
Therefore:
2316 mod 30 (((-72)2)2)2 (mod 30)
(((49)2)2)2 (mod 30) (((-11)2)2)2 (mod 30)
((121)2)2 (mod 30) ((1)2 )2 (mod 30)
(1)2 (mod 30) 1(mod 30)
Which implies that 2316 mod 30 = 1.
L4 23
Fast Modular Exponentiation
Q: How ‘bout 2325 mod 30 ?
A: The previous method of repeated squaring works
for any exponent that’s a power of 2. 25 isn’t.
However, we can break 25 down as a sum of such
powers: 25 = 16 + 8 + 1.
Apply repeated squaring to each part, and multiply the
results together.
Previous calculation:
238 mod 30 = 2316 mod 30 = 1
Thus: 2325 mod 30 2316+8+1 (mod 30) 2316·238·231
(mod 30) 1·1·23 (mod 30)
Final answer: 2325 mod 30 = 23
L4 24
Example 1: of Modular Exponentiation
L4 25
Example 2: of Modular Exponentiation
L4 26
Example 3: of Modular Exponentiation
L4 27
L4 28
L4 29
L4 30
L4 31
L4 32
L4 33
L4 34
L4 35
L4 36
L4 37
L13 38
L4 39
L4 40
L13 41
L4 42
L4 43
L4 44
L4 45
RSA Cryptography
The key to security of RSA cryptosystem:
The public key (N,e) must be such that
it is very difficult for Snoop to figure out
what d is.
L4 46