Transcript CIS 4362

Lecture 9
Public Key Cryptography
Public Key Algorithms
CIS 4362 - CIS 5357
Network Security
1
Euler’s Totient function (n) - again
• (n) is the number of positive integers less than n and
relatively prime to n.
Let p be a prime. Then (p) = p – 1
Let n = pq for p and q prime. Then (n) = (pq) = (p)(q)
Proof outline: look at numbers relatively prime to pq. Must
take all the numbers less than pq but eliminate multiples of p
and multiples of q.
(pq – 1)–(q – 1)–(p – 1) = (p – 1)(q – 1)
Example: let n = 15,
Then (15) = (5) (3) = 8 Z15* = {1,2,4,7,8,11,13,14}
2
Euler’s Theorem - extension
• Euler’s theorem: for every a and n that are relatively
prime, a(n) ≡ 1 mod n
• Corollary: for every a and n that are relatively prime,
ak(n)+1 ≡ a mod n
• For n a product of two primes p and q, then for all a
and k non-negative, ak(n)+1 ≡ a mod n
Proof outline: consider case where a is a multiple of p, a
= cp. Then gcd(a,q) = 1.
3
Discrete Logarithms
• Let y = gx mod p
• x is said to be the (discrete) logarithm of y,
with base g.
• It is easy to compute y, given g,x, and p.
• It is hard to find x, given g,p, and y.
• It is believed to be as hard as factoring large
primes.
4
xy
0
1
2
3
4
5
6
7
8
9
0 1 2 3 4 5 6 7 8 9 10 11 12
1
1
1
1
1
1
1
1
1
0
1
2
3
4
5
6
7
8
9
0
1
4
9
6
5
6
9
4
1
0
1
8
7
4
5
6
3
2
9
0
1
6
1
6
5
6
1
6
1
0
1
2
3
4
5
6
7
8
9
0
1
4
9
6
5
6
9
4
1
0
1
8
7
4
5
6
3
2
9
0
1
6
1
6
5
6
1
6
1
0
1
2
3
4
5
6
7
8
9
0
1
4
9
6
5
6
9
4
1
Table for exponentiation mod 10
0
1
8
7
4
5
6
3
2
9
0
1
6
1
6
5
6
1
6
1
Looking at the mod 10 table
• Note that (10) = 4. Also, 10 is the product of distinct
primes so Euler’s theorem applies (for any x)
– that is x1 + k(n) = x mod n where n = 10, for all x
– thus (10) = 4 means that every 4th column will be the
same (except starting at x0)
• Note however that although exponentiating by 1, 3, and 4,
are a permutation of the set 1-9, exponentiating by 2 does not
result in a permutation.
– this is because 2 is not a coprime of 4 = (10)
– for all coprimes of 4, for example e = 3 we can find a d
such that ed = 1 mod 4.
– Thus, using mod 10 arithmetic, xed = x1+ (10) = x and
thus x3 has an exponentiative inverse in the sense that for
all x, (x3)d = x, for some d.
6
RSA
• Rivest, Shamir, Adleman, 1978, MIT
• Variable key size, common to use 1024 bits
• Generating RSA keys is based on finding multiplicative
inverses of large numbers (modulo), which is not hard
• Generating RSA ciphertext is based on modulo
exponentiation, which is not hard
• RSA's strength is based on difficulty of factoring large
numbers and computing discrete logarithms, which is
believed to be hard.
• There may be other trap doors in RSA, but none have
been found yet.
7
The RSA Algorithm
Choosing public and private keys
• Let k be the key length then choose two large
prime numbers p and q of bit lengths k/2, for
example 512 bits each. Let n = pq.
• Choose e < n with e relatively prime to (n).
The public key is <e,n>
• Find multiplicative inverse d of e mod (n).
The private key is <d,n>
8
RSA operations
encryption / decryption
• Encryption – for a message m < n,
c = me mod n (c is the ciphertext)
• Decryption – given the ciphertext c,
compute cd mod n
• Note that cd mod n = med mod n = m since d
was chosen so that ed = 1 + k (n) and we
are simply using Euler’s (extension)
theorem
9
RSA operations
signature / verification
• Signature – for a message m < n,
s = md mod n (s is the signature)
• Signature verification – given the signature s,
compute se mod n
• Note that se mod n = med mod n = m. Also anyone
can verify the signature using the public key.
10
RSA Example
1. Select two large primes, 2357 and 2551.
2. Multiply them to get n = 6012707
3. Select e = 3674911, relatively prime to (n)= 600780
4. d = 422191 is the multiplicative inverse of e mod (n)
5. Encrypt m = 5234673 < n as
c = me mod n
= 52346733674911 mod 6012707
= 3650502
6. Decrypt c as, m = cd mod n
= 3650502 422191 mod 6012707
= 5234673
11
Back to one way functions:
an example of encryption / decryption
• Let n be a large number
• Let the plaintext be viewed as M < n
• To get the ciphertext, we do the following:
C = Me mod n
• Example
Let (e,n) be (7, 187) and M be 88
Then C = 887 mod 187 = 11
• (d,n)=(23,187)and 187 = 17  11
• Then M = 1123 mod 187 = 88
12
An Attack on RSA
1. An intruder, X intercepts a message (m) intended
for Alice encrypted under Alice's public key(e):
(m)e mod n
2. The intruder generates a value x, computes:
xeme mod n = (xm)e mod n
and sends it to Alice
3. Alice decrypts the message to attain the value:
xm mod n, which appears to be garbage
4. If Alice disposes of the "garbage" carelessly, the
intruder can recover it and compute:
(xmx-1) mod n = m
13
Some aspects of RSA
1. It's strength is based on the difficulty of factoring
large numbers and the difficulty of computing
discrete logarithms
2. It is much more computationally intensive than DES,
IDEA, AES, etc.
3. It has avoidable weaknesses
•
•
•
•
If there are a limited number of plaintext messages used in
practice, can compute all the corresponding ciphertext
messages and compare
Encrypting small messages (say the value of e used is 3. Then
can recover using cube root
Smooth number threat – product of small primes
Need to pad properly
14
Diffie Hellman
• Oldest public key system in use
• Allows Alice and Bob to agree on a shared key
even though all messages are exchanged in the
open
• Limited functionality – the shared secret can
subsequently be used for encrypting / decrypting
using other systems
• Weakness – no authentication as a basic element
of DH
15
Diffie Hellman Key Exchange
•
Choose a large prime p and g < p. These are
publicly known to all. (some restrictions on g and p
for additional security)
1.
2.
3.
4.
5.
Alice and Bob “randomly” choose a and b respectively these are their individual private keys.
Alice computes TA = ga mod p, Bob computes
TB = gb mod p
Alice and Bob exchange the values TA and TB
Alice computes TBa mod p and Bob computes TAb mod p
They have both computed the same number, the shared
secret key
16
Intro to El Gamal
1. Alice and Bob agree on a large (512 bits) prime p
and a generator g < p with some restrictions on g.
(Operations are all mod p)
2. Alice chooses a random number a (her private
key) and computes and publishes her public key
TA = ga
3. To transmit a message M, Bob selects a random
number r (private), and computes and sends to
Alice: C =(gr,Mgar)
4. Alice computes gar , then g-ar, and finally
M = M(gar)(g-ar)
17
El Gamal Example
g=
5
ga mod p =
3
p=
11
gr mod p =
3
a=
2
gar mod p =
9
r=
7
Mgar mod p =
M=
6
g-ar mod p =
10
5
Mgar * g-ar mod p = 6
18