Transcript Public key

Solve it with the Computer
Lecture 12
Rick Spillman
CSCE 115
Spring 2013
1
Outline

Review

Public Key Systems

RSA

Number Theory
2
Review
3
Our New Class Saying
Just because something is
complicated that does
not mean that I can’t understand it.
4
Public Key Ciphers
5
Public Key Systems

Public Key systems are also known as
asymmetric key ciphers

They are usually based on number theory
rather than substitution or permutation
operations

There are two different keys: one for
encryption and one for decryption

Knowing one key can not compromise the
other
6
Public Key Process

One problem with a single key system
involves the distribution of the key



Everyone who should have access to the
plaintext needs to have a copy of the key
All it takes is for one person to expose the key
and the security of all messages is lost
In a two key system, the encryption key
can be made public while the decryption
key remains secret
7
Public Key Transaction

Say Alice wants to send a message to Bob
using a public key algorithm
She looks up Bob’s
public key
plaintext
Alice
Public
key
PK
Cipher
Private
key
PK
Cipher
Bob uses his
private key
plaintext
Bob
8
Public Key Requirements





Easy to generate both public and private keys
Easy to encrypt and decrypt
Hard to compute the private key from the
public key
Hard to compute the plaintext from the
ciphertext and the public key
Useful if encryption and decryption can be
applied in any order
9
RSA
10
Exponentiation Ciphers

Class of ciphers which rely on multiplication to
generate the cipher text

GENERAL METHOD



Consider the plaintext to be a set of integers
Given a message block, M, which is an integer in
the range 0 to n-1 (8 bits would be 0 to 255, …)
Define the ciphertext to be the integer produced by
(e and n are the keys)
C = Me mod n
11
Decipher

To decode this kind of cipher, we
need one other key, an integer d
such that:
M = Cd mod n
We know that Mk mod n = 1 for some large integer k
so the value of d which allows us to decipher this code is
found by solving
ed = 1 mod k
12
RSA Cipher

Named after 3 researchers at MIT who
developed the cipher: Rivest-Shamir-Adleman
Cipher

PROCESS






Select two 100 digit (or more) prime numbers, p and q
Multiply them to obtain n = pq
publish n
select another number d which is relative prime to (p-1)(q-1) that means the largest number which divides both d and the
product is 1
calculate e so that it is the inverse of d when reduced mod
(p-1)(q-1) - that is ed mod (p-1)(q-1) is 1
publish e but keep p, q, and d secret
13
RSA Operation

The encryption process for RSA involves




divide the message into blocks such that the bit string can
be viewed as a 200 digit number - call this block m
compute and send c = me mod n
remember e and n are public keys (so anyone can do this)
The decryption process for RSA involves



compute cd mod n
this works because cd = (me)d = m1 mod n
remember d is private and remains private because to find
d you must discover p and q but the only way to do that is
to factor n
14
Aside: Characters to Numbers

Process: to translate a collection of
characters to a number


convert the characters to ASCII
treat the ASCII code like a binary number and
convert it to decimal
it
0110100101110100
214 x 213 x 211 x 28 x 26 x 25 x 24 x 22
26996
15
Aside: Numbers to Characters

Process: to translate a number to a
collection of characters


convert the number to binary
treat the binary number like an ASCII code
26995
0110100101110011
is
16
RSA Example

Select p and q to be two digit primes: p = 41, q = 53

Then n = pq = 2173 and (p-1)(q-1) = 40*52 = 2080

Select any d between 54 and 2079 which does not
share any factors with 2080, say d = 623

Now, compute e so that ed = 1 mod 2173

It turns out that e = 207 works since 207*623 =
128961 which when divided by 2080 leaves a
remainder of 1
17
Message

Now we need to divide the message into
blocks of bits




RULE: find the highest power of 2 less than n
In our case, n = 2173 and 211 = 2048 but 212 =
4096
So, divide the plaintext into blocks of 11 bits
Encrypt the message “JABBERWOCKY”
01011010
01010010
01011001
01000001
01010111
01000010
01001111
01000010
01000011
01000101
01001011
18
Blocks

The 11 bit blocks and their decimal
equivalent are:
binary
01011010010
00001010000
10010000100
10001010101
00100101011
10100111101
00001101001
01101011001
decimal
722
80
1156
1109
299
1341
105
857
This represents the 8 message blocks, m1 through m8 which
will be transformed into 8 ciphertext blocks c1 through c8
19
Ciphertext

The ciphertext is generated by:
722207
80207
1156207
1109207
299207
1342207
105207
857207
=
=
=
=
=
=
=
=
1794
1963
1150
702
145
593
2013
1861
=
=
=
=
=
=
=
=
c1
c2
c3
c4
c5
c6
c7
c8
mod
mod
mod
mod
mod
mod
mod
mod
2173
2173
2173
2173
2173
2173
2173
2173
So the transmitted message is
1794 1963 1150 702 145 593 2013 1861
20
Decipher

To decipher the message:
1794623
1963623
1150623
702623
145623
593623
2013623
1861623
= 722 = m1 mod 2173
=
80 = m2 mod 2173
= 1156 = m3 mod 2173
= 1109 = m4 mod 2173
= 299 = m5 mod 2173
= 1341 = m6 mod 2173
= 105 = m7 mod 2173
= 857 = m8 mod 2173
Convert these numbers back to binary, the binary back to
characters and the plaintext message reappears
21
RSA Performance

Key Generation is slow

Ciphertext generation is about 1000
times slower than DES

Often times, RSA is used to protect
session keys which are used with
DES
22
Using CAP

CAP implements RSA:
23
Breaking RSA

There are a several attacks that can be
made on RSA

The most obvious is to factor the public
key




To decrypt RSA you must know the private key d
d was selected so that ed mod (p-1)(q-1) = 1
where e is given as part of the public key
If p and q are known, then d can be calculated
p and q are known only if n can be factored
24
RSA Challenge

In December 1977, the challenge was given to
break RSA-129 where:
n (RSA-129) = 1 1438 1625 7578 8886 7669 2357 7997
6146 6120 1021 8296 7212 4236 2562 5618 4293 5706 9352
4573 3897 8305 9712 3563 9587 0505 8989 0751 4759 9290
0268 7954 3541
e = 9007
The best known algorithm at the time would have
required 40,000 trillion years if multiplications of
129 digit numbers could run as fast as 1 ns
25
Challenge Met

It only took 17 years
Derek Atkins (April 1994): We are happy to announce that
RSA-129 = 3490 5295 1084 7650 9491 4784 9619 9038 9813 3417 7646
3849 3387 8439 9082 0577 * 3 2769 1329 9326 6709 5499 6198 8190 8344
6141 3177 6429 6799 2942 5397 9828 8533
26
Process

When: August 1993 - 1 April 1994, 8
months

Who: D. Atkins, M. Graff, A. K. Lenstra, P.
Leyland


+ 600 volunteers from the entire world
How: 1600 computers

from Cray C90, through 16 MHz PC, to fax
machines
Now, RSA-155 has been broken as well, so the new
standard for keys is 231 digits
27
Number Theory
28
Why Number Theory?

There are three issues in number theory that
directly relate to the RSA cipher:


How do I find large prime numbers?
How do I find the required modular inverse?



i.e. given e and n find d such that ed = 1 mod n
How can I be sure that my primes are large
enough to avoid factoring?
Other Number Theory concepts will play a
role in alternative public key algorithms
29
Prime Numbers

The positive integers (1, 2, . . .) are made up
of:



composite numbers - a number which is the product
of several factors other than itself and 1
prime numbers - a number which has no factors
The FUNDAMENTAL THEOREM OF
ARITHMETIC

every positive integer n can be written as the
product of primes in only one way
30
Primes are Important

Most Public Key algorithms (like RSA) require
large prime numbers

The largest known prime changes every year
31
Finding Prime Numbers


Given a list of numbers (say from 1 to 30)
determine which in the list are prime
SOLUTION: Sieve of Eratosthenes




write all the numbers between a and b
cross out all the multiples of 2 except 2
cross out all the multiples of 3 except 3
continue until there is nothing left to cross out
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
PRIMES
32
Recognition of Primes

PROBLEM: Given a number N, determine if it is a
prime or composite

Fact: primes are not that rare! N/(ln N)



for 512-bit binary number, P(p-prime)=1/177
So, all we do is generate 1000 or so random integers…
and test them...
Two methods


Factor the number - if it has factors then it is composite (THIS IS
VERY HARD TO DO)
Primality Test - a test of the form, if a certain condition on N is true
then N is a prime otherwise N is a composite
33
Trial Division

Is 12553 prime or composite (not prime)?




One way to find out is to divide 12553 by every
number less than its square root.
If one of these numbers evenly divides 12553
then it is not prime otherwise it must be prime.
The square root of 12553 is 112.04, so this
approach requires only 112 division operations
(divide by 2, 3, 4, . . ., 113).
This method will quickly verify that 12553 is
prime, but what about 13952598148481?
34
Using CAP

CAP will perform trail division


Select integers on the main menu
Select Prime Test-Trial Division under the Special Functions menu
I gave up
35
Prime Test

A faster more efficient prime number detector is
required if RSA is to be used




It turns out that a variety of prime number detectors exist
that are based on an analysis of the properties of prime
numbers.
One method was developed by the 17th century French
mathematician Pierre Fermat.
He noticed that given two numbers, a base a and a prime p
where a is not divisible by p then ap-1 = 1 mod p.
For example, select 6 as the base number and 7 as the
prime number (6 is not divisible by 7) then
66 = 46656 = 1 (mod 7)

This result is known as Fermat’s Little Theorem.
36
Fermat’s Test

The test based on Fermat’s Little Theorem is:
A number p is prime if:
For some number a  ap-1 = 1 mod p
Examples:
1. Test p = 13 using base 2: 212 = 4096 = 1 mod 13
2. Test p = 341 using base 2: 2340 = 1 mod 341
BUT: 11 x 31 = 341
37
The Problem

Composite numbers like 341 which appear
on the basis of this test to be prime are
called pseudoprimes.


For example, 91 is a pseudoprime to base 3
since 390 = 1 (mod 91)
Perhaps choosing another base will work

In most cases it does but there are some
composite numbers that appear to be prime by
Fermat’s Test for every base – these are called
Carmichael numbers
38
Alternatives

A new test for primality was needed and several have
been discovered


Most are based on probabilities – that is if some number p
passes the test the probability that it is not prime is very small
One such test was proposed in 1982 by Lehmann
(called the Lehmann test):


To test the primality of p, select 100 random numbers ai (i = 1
to 100) in the range 1 to p-1
p is probably prime if:
ai(p-1)/2 = 1 or -1 mod p for all i
and it equals -1 for some i
39
Using CAP

CAP offers several primality test methods





Trial division
Fermat’s Method
Lehmann’s Method
Miller-Rabin test
All of these are found in the Large Integer
Routines window

Click on the Integers menu item to open this
window
40
The Real Problem

The real problem for RSA is not so much
testing an single number to determine if it
is prime – it is one of finding two large
prime numbers

CAP will do this as well by generating up
to 100 large random numbers stopping
only when one of them is determined to be
prime


One CAP method is based on the Lehmann
test
Another is based on the Miller-Rabin test
41
Using CAP

For example, CAP found a 15 digit prime
number in just over 6 minutes:
42
Guidelines for RSA

Not only do the primes selected for RSA
need to be large enough to prevent a
simple factor attack on n, the difference
between them must be large as well.



If p and q are close then (as will be seen) n
can be factored using Fermat’s algorithm.
One suggested guideline is that the size of the
smaller prime be 40 to 45% of the size of n.
That is if n is to have 100 digits, then p should
have about 45 digits and q should have about
55 digits.
43
Modular Inverse

Generating the keys for RSA requires
finding two large primes to create n = pq,
selecting a secret key, d and then finding
the public key e such that:
de mod (p-1)(q-1) = 1
e is the modular inverse of d (d-1)
PROBLEM: How do you find e (especially for large
integers)?
44
Solution

The solution is to use
the extended verson
of Euclid’s Algorithm


Euclid’s Algorithm is
used to find the
Greatest Common
Divisor, gcd, of two
numbers
CAP will do this for you
45
Factoring

RSA can be broken if the two primes that made n
can be found by factoring n

Given two numbers, say 1203 and 307, it is not
very difficult to find their product: 396321

In fact, given two very large numbers,
multiplication is still easy:
30761208
x 1063417
But it is a different story if we begin with a large number and are asked
32711991527736
to find two primes which multiply together to produce it:
7105593510097261
46
Factoring Algorithm

PROBLEM: Decompose a large integer into
its prime factors
7105593510097261

What would be the first step?

What would be a simple procedure?
47
Fermat’s Factoring Algorithm

Observation: The search for factors of an odd
integer n is equivalent to obtaining integral
solutions x and y to:
n = x 2 - y2

If n is the difference of two squares then n can be
factored as:
n = x2 - y2 = (x + y)(x – y)
So, when the factorization of n is n = ab with a >= b>= 1
2
2
a+b
a-b
n=
2
2
( ) ( )
48
Search Approach

Search for an x and y that satisfy
n = x2 – y2 which is the same as
using:
2
2
x -n=y
Start with the smallest integer k for k2 >= n
Look at numbers k2–n, (k+1)2–n, (k+2)2-n, . . . until some value
m >= sqrt(n) is found such that m2-n is a square
Then we know x and y so a = (x+y) and b = (x-y)
49
Using CAP

CAP implements Fermat’s Factoring Algorithm

Select Factor under the Public Key segment of the
Analysis menu
50
Using CAP

CAP also implements Pollard’s rho as well as two
other common factoring algorithms (Pollard’s p-1
and the Continued Fraction method)
51