Transcript Still Image Compression

Lecture 3: Public Key Cryptography
CS 392/6813: Computer Security
Fall 2008
Nitesh Saxena
*Adopted from Previous Lectures by Nasir Memon
Course Admin

Good/Bad News

HW#1 will not be graded!



Not a trick – just for the benefit of this course
HW#2 due coming Monday (09/22)
HW#3 will be posted soon after
7/7/2015
Lecture 3: Pubic Key
Cryptography
2
Outline of Today’s Lecture



Public Key Crypto Overview
Number Theory Background
Public Key Encryption



RSA
ElGamal
Public Key Signatures (digital signatures)


7/7/2015
RSA
DSS
Lecture 3: Pubic Key
Cryptography
3
Recall: Private Key/Public Key
Cryptography

Private Key: Sender and receiver share a
common (private) key



Encryption and Decryption is done using the
private key
Also called conventional/shared-key/single-key/
symmetric-key cryptography
Public Key: Every user has a private key and
a public key


7/7/2015
Encryption is done using the public key and
Decryption using private key
Also called two-key/asymmetric-key cryptography
Lecture 3: Pubic Key
Cryptography
4
Private key cryptography revisited.


Good: Quite efficient (as you’ll see from the HW#2
exercise on AES)
Bad: Key distribution and management is a serious
problem – for N users O(N2) keys are needed
7/7/2015
Lecture 3: Pubic Key
Cryptography
5
Public key cryptography model


Good: Key management problem potentially simpler
Bad: Much slower than private key crypto (we’ll see
later!)
7/7/2015
Lecture 3: Pubic Key
Cryptography
6
Public Key Encryption

Two keys:







public encryption key e
private decryption key d
Encryption easy when e is known
Decryption easy when d is known
Decryption hard when d is not known
We’ll study such public key encryption
schemes; first we need some number theory.
Security notions/attacks very similar to what
we studied for private key encryption
7/7/2015
Lecture 3: Pubic Key
Cryptography
7
Group: Definition
(G,.) (where G is a set and . : GxGG) is said to be a
group if following properties are satisfied:
1.
Closure : for any a, b  G, a.b  G
2.
Associativity : for any a, b, c  G, a.(b.c)=(a.b).c
3.
Identity : there is an identity element such that
a.e = e.a = a, for any a  G
4.
Inverse : there exists an element a-1 for every a
in G, such that a.a-1 = a-1.a = e
Abelian Group: Group which also satisfies
commutativity , i.e., a.b=b.a
Examples: (Z,+) ; (Z,*)?; (Zm, “modular addition”)
7/7/2015
Lecture 3: Pubic Key
Cryptography
8
Definitions related to a group

An element g in G is said to be a generator of
a group if a = gi for every a in G, for a certain
integer i




A group which has a generator is called a cyclic
group
The number of elements in a group is called
the order of the group
Order of an element a is the lowest i such
that ai = e
A subgroup is a subset of a group that itself
is a group
7/7/2015
Lecture 3: Pubic Key
Cryptography
9
Divisors

x divides y (written x | y) if the remainder is 0
when y is divided by x


1|8, 2|8, 4|8, 8|8
The divisors of y are the numbers that divide
y


divisors of 8: {1,2,4,8}
For every number y


7/7/2015
1|y
y|y
Lecture 3: Pubic Key
Cryptography
10
Prime numbers

A number is prime if its only divisors are 1
and itself:


2,3,5,7,11,13,17,19, …
Fundamental theorem of arithmetic:

For every number x, there is a unique set of
primes {p1, … ,pn} and a unique set of positive
exponents {e1, … ,en} such that
x  p1
e1
7/7/2015
* ... *
pn
Lecture 3: Pubic Key
Cryptography
en
11
Common divisors

The common divisors of two numbers x,y are
the numbers z such that z|x and z|y

common divisors of 8 and 12:



intersection of {1,2,4,8} and {1,2,3,4,6,12}
= {1,2,4}
greatest common divisor: gcd(x,y) is the
number z such that


z is a common divisor of x and y
no common divisor of x and y is larger than z

7/7/2015
gcd(8,12) = 4
Lecture 3: Pubic Key
Cryptography
12
Euclidean Algorithm: gcd(r0,r1)
Main idea: If y = ax + b then gcd(x,y) = gcd(x,b)
r0  q1r1  r2
r1  q2 r2  r3
...
rm  2  qm 1rm 1  rm
rm 1  qm rm  0
gcd( r0 , r1 )  gcd(r1 , r2 )  ...  gcd(rm 1 , rm )  rm
7/7/2015
Lecture 3: Pubic Key
Cryptography
13
Example – gcd(15,37)




37 = 2 * 15 + 7
15 = 2 * 7 + 1
7=7*1+0
gcd(15,37) = 1
7/7/2015
Lecture 3: Pubic Key
Cryptography
14
Relative primes


x and y are relatively prime if they have no
common divisors, other than 1
Equivalently, x and y are relatively prime if
gcd(x,y) = 1


7/7/2015
9 and 14 are relatively prime
9 and 15 are not relatively prime
Lecture 3: Pubic Key
Cryptography
15
Modular Arithmetic

Definition: x is congruent to y mod m, if m
divides (x-y). Equivalently, x and y have the
same remainder when divided by m.
Notation: x  y(modm)
Example: 14  5(mod 9)



We work in Zm = {0, 1, 2, …, m-1}, the group
of integers modulo m
Example: Z9 ={0,1,2,3,4,5,6,7,8}
We abuse notation and often write = instead

of
7/7/2015
Lecture 3: Pubic Key
Cryptography
16
Addition in Zm :

Addition is well-defined:
if
x  x' (modm)
y  y ' (modm)
then
x  y  x' y ' (modm)


7/7/2015
3 + 4 = 7 mod 9.
3 + 8 = 2 mod 9.
Lecture 3: Pubic Key
Cryptography
17
Additive inverses in Zm

0 is the additive identity in Zm
x  0  x(modm)  0  x(modm)

Additive inverse of a is -a mod m = (m-a)



7/7/2015
Every element has unique additive inverse.
4 + 5= 0 mod 9.
4 is additive inverse of 5.
Lecture 3: Pubic Key
Cryptography
18
Multiplication in Zm :

Multiplication is well-defined:
if
x  x' (modm)
y  y ' (modm)
then
x  y  x' y ' (modm)



7/7/2015
3 * 4 = 3 mod 9.
3 * 8 = 6 mod 9.
3 * 3 = 0 mod 9.
Lecture 3: Pubic Key
Cryptography
19
Multiplicative inverses in Zm


1 is the multiplicative identity in Zm
x 1  x(modm)  1 x(modm)
Multiplicative inverse (x*x-1=1 mod m)



7/7/2015
SOME, but not ALL elements have unique
multiplicative inverse.
In Z9 : 3*0=0, 3*1=3, 3*2=6, 3*3=0, 3*4=3,
3*5=6, …, so 3 does not have a multiplicative
inverse (mod 9)
On the other hand, 4*2=8, 4*3=3, 4*4=7,
4*5=2, 4*6=6, 4*7=1, so 4-1=7, (mod 9)
Lecture 3: Pubic Key
Cryptography
20
Which numbers have inverses?

In Zm, x has a multiplicative inverse if and
only if x and m are relatively prime or
gcd(x,m)=1

7/7/2015
E.g., 4 in Z9
Lecture 3: Pubic Key
Cryptography
21
Extended Euclidian: a-1 mod n


Main Idea: Looking for inverse of a mod n means
looking for x such that x*a – y*n = 1.
To compute inverse of a mod n, do the following:





7/7/2015
Compute gcd(a, n) using Euclidean algorithm.
Since a is relatively prime to m (else there will be no
inverse) gcd(a, n) = 1.
So you can obtain linear combination of rm and rm-1 that
yields 1.
Work backwards getting linear combination of ri and ri-1 that
yields 1.
When you get to linear combination of r0 and r1 you are
done as r0=n and r1= a.
Lecture 3: Pubic Key
Cryptography
22
Example – 15-1 mod 37
37 = 2 * 15 + 7
 15 = 2 * 7 + 1
 7 = 7 * 1 + 0
Now,
 15 – 2 * 7 = 1
 15 – 2 (37 – 2 * 15) = 1
 5 * 15 – 2 * 37 = 1
So, 15-1 mod 37 is 5.

7/7/2015
Lecture 3: Pubic Key
Cryptography
23
Modular Exponentiation:
Square and Multiply method


Usual approach to computing xc mod n is
inefficient when c is large.
Instead, represent c as bit string bk-1 … b0
and use the following algorithm:
z = 1
For i = k-1 downto 0 do
z = z2 mod n
if bi = 1 then z = z* x mod n
7/7/2015
Lecture 3: Pubic Key
Cryptography
24
Example: 3037 mod 77
z = z2 mod n
if bi = 1 then z = z* x mod n
i
b
z
5
1
30
=1*1*30 mod 77
4
0
53
=30*30 mod 77
3
0
37
=53*53 mod 77
2
1
29
=37*37*30 mod 77
1
0
71
=29*29 mod 77
0
1
2
7/7/2015
=71*71*30 mod 77
Lecture 3: Pubic Key
Cryptography
25
Lagrange’s Theorem

Order of an element in a group divides the
order of the group
7/7/2015
Lecture 3: Pubic Key
Cryptography
26
Euler’s totient function


Given positive integer n, Euler’s totient
function  (n) is the number of positive
numbers less than n that are relatively prime
to n
Fact: If p is prime then ( p)  p  1

7/7/2015
{1,2,3,…,p-1} are relatively prime to p.
Lecture 3: Pubic Key
Cryptography
27
Euler’s totient function

Fact: If p and q are prime and n=pq then
(n)  ( p  1)(q  1)

Each number that is not divisible by p or by q
is relatively prime to pq.


7/7/2015
E.g. p=5, q=7: {1,2,3,4,-,6,-,8,9,-,11,12,13,-,,16,17,18,19,-,-,22,23,24,-,26,27,-,29,,31,32,33,34,-}
pq-p-(q-1) = (p-1)(q-1)
Lecture 3: Pubic Key
Cryptography
28
Euler’s Theorem and Fermat’s Theorem

If a is relatively prime to n then
a

( n)
 1modn
If a is relatively prime to n then
ap-1 = 1 mod p
Proof : follows from Lagrange’s Theorem
7/7/2015
Lecture 3: Pubic Key
Cryptography
29
RSA Cryptosystem
7/7/2015
Lecture 3: Pubic Key
Cryptography
30
“Textbook” RSA: KeyGen





Alice wants people to be able to send her encrypted
messages.
She chooses two (large) prime numbers, p and q and
computes n=pq and  (n) . [“large” =512 bits +]
She chooses a number e such that e is relatively
prime to  (n) and computes d, the inverse of
e in Z  (n )
(i.e., ed =1 mod \phi(n))
She publicizes the pair (e,n) as her public key.(e is
called RSA exponent, n is called RSA modulus)She
keeps d secret and destroys p, q, and  (n)
Plaintext and ciphertext messages are elements of Zn
and e is the encryption key.
7/7/2015
Lecture 3: Pubic Key
Cryptography
31
RSA: Encryption



Bob wants to send a message x (an element
of Zn*) to Alice.
He looks up her encryption key, (e,n), in a
directory.
The encrypted message is
y  E( x)  xe modn

Bob sends y to Alice.
7/7/2015
Lecture 3: Pubic Key
Cryptography
32
RSA: Decryption

To decrypt the message
y  E( x)  x modn
e
she’s received from Bob, Alice computes
D( y)  y modn
d
Claim: D(y) = x
7/7/2015
Lecture 3: Pubic Key
Cryptography
33
RSA: why does it all work

Need to show
 D[E[x]] = x



E[x] and D[y] can be computed efficiently if keys
are known
E-1[y] cannot be computed efficiently without
knowledge of the (private) decryption key d.
Also, it should be possible to select keys
reasonably efficiently

7/7/2015
This does not have to be done too often, so
efficiency requirements are less stringent.
Lecture 3: Pubic Key
Cryptography
34
E and D are inverses:
Case 1: gcd(x,n)=1
D( y )  y modn
d
 ( x e modn) d
 ( x ) modn
e d
 x modn
ed
x
t ( n ) 1
 (x
Because ed  1 mod(n)
modn
(n) t
) x modn
 1t x modn  x modn
7/7/2015
From Euler’s Theorem
Lecture 3: Pubic Key
Cryptography
35
Alternative Proof that E and D are
inverses
ed  t (n)  1  t ( p  1)(q  1)  1
x
p 1
(x
x
x
 1 mod p
p 1 t ( q 1)
)
t ( n )
 1 mod p
 1 mod p
t ( n ) 1
 x mod p
x ed  x mod p
p | ( x ed  x)
7/7/2015
Lecture 3: Pubic Key
Cryptography
36


By analogous argument q | ( xed  x)
So
ed
n | ( x  x)
x ed  x modn
7/7/2015
Lecture 3: Pubic Key
Cryptography
37
Tiny RSA example.





Let p = 7, q = 11. Then n = 77 and
(n)  60
Choose e = 13. Then d = 13-1 mod 60 = 37.
Let message = 2.
E(2) = 213 mod 77 = 30.
D(30) = 3037 mod 77=2
7/7/2015
Lecture 3: Pubic Key
Cryptography
38
Slightly Larger RSA example.

Let p = 47, q = 71. Then n = 3337 and
( pq)  46* 70  3220




Choose e = 79. Then d = 79-1 mod 3220 =
1019.
Let message = 688232… Break it into 3 digit
blocks to encrypt.
E(688) = 68879 mod 3337 = 1570.
E(232) = 23279 mod 3337 = 2756
D(1570) = 15701019 mod 3337 = 688.
D(2756) = 27561019 mod 3337 = 232.
7/7/2015
Lecture 3: Pubic Key
Cryptography
39
Security of RSA: RSA assumption




Suppose Oscar intercepts the encrypted
message y that Bob has sent to Alice.
Oscar can look up (e,n) in the public directory
(just as Bob did when he encrypted the
message)
If Oscar can compute d = e-1 mod  (n) then
d
D
(
y
)

y
modn  x to
he can use
recover the plaintext x.
If Oscar can compute  (n) , he can compute
d (the same way Alice did).
7/7/2015
Lecture 3: Pubic Key
Cryptography
40
Security of RSA: factoring



Oscar knows that n is the product of two
primes
If he can factor n, he can compute  (n)
But factoring large numbers is very difficult:




7/7/2015
Grade school method takes O( n ) divisions.
Prohibitive for large n, such as 160 bits
Better factorization algorithms exist, but they are
still too slow for large n
Lower bound for factorization is an open problem
Lecture 3: Pubic Key
Cryptography
41
How big should n be?

Today we need n to be at least 1024-bits


This is equivalent to security provided by 80-bit
long keys in private-key crypto
No other attack on RSA known

7/7/2015
Except some side channel attacks, based on
timing, power analysis, etc. But, these exploit
certain physical charactesistics, not a theoretical
weakness in the cryptosystem!
Lecture 3: Pubic Key
Cryptography
42
Key selection

To select keys we need efficient algorithms to

Select large primes



Compute multiplicative inverses

7/7/2015
Primes are dense so choose randomly.
Probabilistic primality testing methods known. Work in
logarithmic time.
Extended Euclidean algorithm
Lecture 3: Pubic Key
Cryptography
43
RSA Key Generation

To select keys we need efficient algorithms to

Select large primes


Primes are dense so choose randomly.
Probabilistic primality testing methods known. Work in
logarithmic time.
 See references
 Compute multiplicative inverses
 Extended Euclidean algorithm
7/7/2015
Lecture 3: Pubic Key
Cryptography
44
RSA in Practice

Textbook RSA is insecure


Why?
In practice, we use a “randomized” version of
RSA, called RSA-OAEP

Interested in details: refer to (section 3.1 of)
http://isis.poly.edu/courses/cs6903/Lectures/lecture13.pdf
7/7/2015
Lecture 3: Pubic Key
Cryptography
45
Discrete Logarithm Assumption




p, q primes such that q|p-1
g is an element of order q and generates a
group of order q
x in Zq, y = gx mod p
Given (p, q, g, y), it is computationally hard
to compute x



No polynomial time algorithm known
p should be 1024-bits and q be 160-bits
x becomes the private key and y becomes the
public key
7/7/2015
Lecture 3: Pubic Key
Cryptography
46
ElGamal Encryption

Encryption (of m in Zp):





Decryption of (k,c)


Choose random r in Zq
k = gr mod p
c = myr mod p
Output (k,c)
M = ck-x mod p
Secure under discrete logarithm assumption
7/7/2015
Lecture 3: Pubic Key
Cryptography
47
ElGamal Example: dummy


Let’s construct an example
KeyGen:





Enc(3):



p = 11, q = 2 or 5; let’s say q = 5
2 is a generator of Z11*
g = 22 = 4
x = 7; y = 47 mod 11 = 5
r = 9  k = 49 mod 11 = 3
c = 3*59 mod 11 = 5
Dec(3,5):

7/7/2015
m = 5*3-7 mod 11 = 3
Lecture 3: Pubic Key
Cryptography
48
Digital Signatures

Message Integrity


Source/Sender Authentication


Detect if message is tampered with while in the
transit
No forgery possible
Non-repudiation


7/7/2015
If I sign something, I can not deny later
A trusted third party (court) can resolve dispute
Lecture 3: Pubic Key
Cryptography
49
Public Key Signatures



Signer has public key, private key pair
Signer signs using its private key
Verifier verifies using public key of the signer
7/7/2015
Lecture 3: Pubic Key
Cryptography
50
Security Notion/Model for signatures

Existential Forgery under (adaptively) chosen
message attack



7/7/2015
Adversary (adaptively) chooses messages mi of its
choice
Obtains the signature si on each mi
Outputs any message m (≠ mi) and a signature s
on m
Lecture 3: Pubic Key
Cryptography
51
RSA Signatures





Key Generation: same as in encryption
Sign(m): s = md mod N
Verify(m,s): (se == m mod N)
The above text-book version is insecure
In practice, we use a randomized version of
RSA

7/7/2015
Hash the message and then sign the hash
Lecture 3: Pubic Key
Cryptography
52
Digital Signature Standard (DSS)


Adopted as standard in 1994
Security based on hardness of the discrete
logarithm problem
7/7/2015
Lecture 3: Pubic Key
Cryptography
53
DSS Signing/Verification
7/7/2015
Lecture 3: Pubic Key
Cryptography
54
DSA Example:

Refer to 11.57 of HAC
7/7/2015
Lecture 3: Pubic Key
Cryptography
55
Some questions


2-1 mod 4 =?
What is the complexity of





(a+b) mod m
(a*b) mod m
a-1 mod (m)
xc mod (n)
c1 = RSA_Enc(m1), c2 = RSA_Enc(m2).

What is RSA_Enc(m1m2)?


What is RSA_Enc(2m1)?


Homomorphic property
Malleability (not a good property!)
Is it possible to find inverses mod n (RSA modulus)?
7/7/2015
Lecture 3: Pubic Key
Cryptography
56



Order of a group is 5. What can be the order of an
element in this group?
RSA stands for Robust Security Algorithm, right?
If e is small (such as 3)



Encryption is faster than decryption or the other way round?
What about signing and verification?
Private key crypto has key distribution problem and
Public key crypto is slow


7/7/2015
How about a hybrid approach?
Do you know how ssl/ssh works?
Lecture 3: Pubic Key
Cryptography
57


Key generation in RSA is -------- than in DLbased schemes (El Gamal/DSS)
I encrypt m with Alice’s RSA PK, I get c



I encrypt m with Alice’s ElGamal PK, I get c



I encryt m again, I get --?
What does this mean?
I encryt m again, I get --?
What does this mean?
What if I do the above with DES?
7/7/2015
Lecture 3: Pubic Key
Cryptography
58

Find x such that




x = 4 mod 5
x = 7 (mod 8)
x = 3 (mod 9)
Chinese Remainder Theorem


7/7/2015
Can be applied to speed up RSA
decryption/signing
At home reading assignment!!!
Lecture 3: Pubic Key
Cryptography
59
Further Reading









Cryptography: Theory and Practice – D. Stinson. CRC Press.
Cryptography and Network Security – William Stallings.
Applied Cryptography – B. Schneier. John Wiley.
North American Crypto archive http://cryptography.org/
Crypto Resource page http://world.std.com/~franl/crypto.html
Ron Rivest’s crypto page
http://theory.lcs.mit.edu/~rivest/crypto-security.html
Cryptography Research Inc. Resource page
http://www.cryptography.com/resources/index.html
Cryptography archive: http://www.austinlinks.com/Crypto/
AES home page http://csrc.nist.gov/encryption/aes/
7/7/2015
Lecture 3: Pubic Key
Cryptography
60