Transcript 4 Public Key Cryptography

Internet Security 1 (IntSi1)
4 Public Key
Cryptography
Prof. Dr. Andreas Steffen
Institute for Internet Technologies and Applications (ITA)
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 1
Cryptographical Building Blocks
Secure Network Protocols
Confidentiality
Data
Integrity
Encryption
MACs
MICs
Symmetric Key
Cryptography
Block
Ciphers
Stream
Ciphers
Message
Digests
Hash
Functions
NonRepudiation
Authentication
Challenge
Response
IVs
Nonces
Pseudo
Random
Smart
Cards
Digital
Signatures
Secret
Keys
Public Key
Cryptography
Random
Sources
Elliptic
Curves
DH
RSA
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 2
The Secure Key Distribution Problem
KAB, KAC, KAD, KAE, KAF
Alice
KAF, KBF, KCF,
Fred
Bob
KDF, KEF
KAB, KBC, KBD,
KBE, KBF
KAE, KBE, KCE,
KAC, KBC, KCD,
KDE, KEF
KCE, KCF
Edna
secure distribution
of n2/2 keys
Carol
Dave
KAD, KBD, KCD, KDE, KDF
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 3
Public Key Distribution System
Public
Directory
Alice :
Bob :
Carol :
Dave :
Edna :
Fred :
KA
KB
KC
KD
KE
KF
KA
Alice
Fred
Bob
KE
KB
KE
KC
Edna
public distribution
of n keys
Carol
KD
Dave
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 4
Public Key Cryptography
•
The Inventors
• Whitfield Diffie and Martin Hellman 1976
• Ralph Merkle 1978
Trap Door
Alice
Bob
C = fKB(P)
Encryption with
one-way function
One-way functions
are often based on wellknown hard problems
P = f-1KB(C,TB)
Computation of inverse
function is extremely
expensive
KB
Joe
P = f-1KB(C)
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 5
Internet Security 1 (IntSi1)
4.1 RSA Public Key
Cryptosystem
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 6
RSA Public Key Cryptosystem
•
The Inventors
•
The One-Way Function
• R - Ron Rivest
• S - Adi Shamir
• A - Leonard Adleman
• The exponentiation function y = f(x) = xe mod n
•
•
can be computed with reasonable effort.
Its inverse x = f -1(y) is extremely difficult to compute.
The Hard Problem Securing the Trap Door
• The RSA public key algorithm is based on the well-known hard
problem of factoring a large number into its prime factors that has
been studied over many centuries.
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 7
RSA Public Key Cryptosystem
Key Generation Algorithm
•
Step 1: Choose two random large prime numbers p and q
• For maximum security, choose p and q of about equal length,
e.g. 1024 … 1536 bits each.
•
Step 2: Compute the product
•
Step 3: Choose a random integer e < (p-1)(q-1)
n = p·q
• The numbers e and (p-1)(q-1) must be relatively prime, i.e.
they should not share common prime factors.
•
Step 4: Compute the unique inverse
d = e-1 mod (p-1)(q-1)
• The equation d·e mod (p-1)(q-1) = 1
can be solved using the Euclidian algorithm.
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 8
RSA Public Key Cryptosystem
How to find large random prime numbers
•
•
•
There are 10305 primes 1024 bits in length or less.
•
To prove that a randomly chosen number is really prime you
would have to factor it. Try small factors (3, 5, 7, 11, ...)
•
Probabilistic Primality Tests (e.g. Miller–Rabin)
There are only 1077 atoms in the universe.
The chance that two people choose the same prime factors for
key generation is therefore near to nil !
Result
of
Primality
Test
•
not prime
is prime
100 %
0.1 %
0%
99.9 %
random number is a
composite number
prime number
After passing 5 tests, assume a random number to be prime
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 9
RSA Public Key Cryptosystem
Key Generation Example
•
p = 3, q = 11:
•
•
(p-1)·(q-1) = 2 · 10 = 2 · 2 · 5 = 20
n = p·q = 33
the public exponent e must be relatively prime to (p-1)·(q-1) ,
i.e. it cannot contain any factors of 2 and 5
e
d
e·d
3
7
9
11
13
17
19
7
3
9
11
17
13
19
21
21
81
121
221
221
361
e·d mod 20
1
1
1
1
1
1
1
all possible choices for
the exponents e and d
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 10
RSA Public Key Cryptosystem
Public and Private Keys
•
Public Key: modulus n and public exponent e
• Publish n and e in a public directory, so that anybody wanting to send
you a confidential message can retrieve it.
•
Private Key: modulus n and private exponent d
• The private exponent d is your secret. It should be protected either
•
by storing it in a tamper-proof smart card or when stored on a disk
by encrypting it with a symmetric cipher secured by a secret
passphrase of your choice.
The primes p and q that were used for key generation are often kept
as part of the private key, because their smaller size (i.e. half the
length of the modulus n) allow an efficient implementation of the
private key operations (Montgomery multiplication).
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 11
RSA Public Key Cryptosystem
Encryption and Decryption
•
Encryption of a plaintext block x:
y = xe mod n
• The sender uses the public key
of the recipient to encrypt x < n.
•
Decryption of a ciphertext block y:
x = yd mod n
• The recipient uses her private key
to recover the plaintext block x
•
Without proof:
yd = (xe)d = xe·d = xm·(p-1)·(q-1) + 1 = x1 = x (mod n)
•
Encryption and Decryption are symmetric operations
• The order of the exponentiation with the public exponent e and
the private exponent d can be exchanged.
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 12
RSA Public Key Cryptosystem
Fast Exponentiation Example
•
Encryption with Public Key





•
e =
e =
y =
y =
x2 =
1·23 + 1·22 + 0·21 + 1·20
1·8 + 1·4 + 0·2 + 1·1
xe =(x8)1 ·(x4)1·(x2)0·(x)1 mod n
x8·x4·x mod n
x·x mod n, x4 = x2·x2 mod n, x8 = x4·x4 mod n
Decryption with Private Key





n = 33, e = 13
n = 33, d = 17
d = 1·24 + 0·23 + 0·22 + 0·21 + 1·20
d = 1·16 + 0·8 + 0·4 + 0·2 + 1·1
x = yd =(y16)1 ·(y8)0 ·(y4)0·(y2)0·(y)1 mod n
x = y16·y mod n
y2 = y·y mod n, y4 = y2·y2 mod n, y8 = y4·y4 mod n,
y16 = y8·y8 mod n
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 13
RSA Public Key Cryptosystem
Plaintext to Ciphertext Mapping
•
y = xe mod n
n = 33, e = 13, d = 17
x
y
x
y
x
y
x
y
x
y
0
1
2
3
4
5
6
7
0
1
8
27
31
26
18
13
8
9
10
11
12
13
14
15
17
3
10
11
12
19
5
9
16
17
18
19
20
21
22
23
4
29
24
28
14
21
22
23
24
25
26
27
28
29
30
31
30
16
20
15
7
2
6
25
32
32
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 14
The RSA–768 Challenge
•
The Effort
• 768 bit number (232 digits) factored in December 2009
• Sieving step took 2 years on a cluster of several hundred computers.
• Sieving on a single core 2.2 GHz Opteron processor with 2 GB of RAM
•
would have taken 1500 years.
1024 modulus is about 1000 times harder to factor.
1230186684530117755130494958384962720772853569595334792197
3224521517264005072636575187452021997864693899564749427740
6384592519255732630345373154826850791702612214291346167042
9214311602221240479274737794080665351419597459856902143413
= ?
3347807169895689878604416984821269081770479498371376856891
2431388982883793878002287614711652531743087737814467999489
*
3674604366679959042824463379962795263227915816434308764267
6032283815739666511279233373417143396810270092798736308917
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 15
Cryptographics Strength of RSA Keys
•
Assumed effort:
40 million dollardays = 40M x 1 day = 100k x 400 days
•
•
•
•
•
•
•
•
•
•
•
56 bits in 1982
64 bits in 1994
72 bits in 2006
76 bits in 2012
80 bits in 2018
88 bits in 2030
96 bits in 2042
104 bits in 2054
112 bits in 2066
120 bits in 2078
128 bits in 2090
RSA:
RSA:
RSA:
RSA:
RSA:
RSA:
RSA:
RSA:
RSA:
RSA:
RSA:
366 … 527 bits
639 … 746 bits
1007 … 1012 bits
1164 … 1229 bits
1329 … 1478 bits
1698 … 2063 bits
2124 … 2770 bits
2608 … 3607 bits
3154 … 4582 bits
3764 … 5701 bits
4440 … 6974 bits
www.keylength.com
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 16
Internet Security 1 (IntSi1)
4.2 Diffie Hellman
Key Exchange Algorithm
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 17
The Diffie–Hellman Key-Exchange Algorithm
Generating a Common Secret Key
•
•
•
•
•
•
•
•
Alice and Bob agree on a large prime modulus n, a primitive
element g and the one-way function y = f(x) = gx mod n.
The integers n and g are not secret and can be published.
Alice chooses a large random integer a and sends Bob
A = ga mod n
Bob chooses a large random integer b and sends Alice
B = gb mod n
Alice computes
s = Ba mod n = gba mod n
Bob computes
s = Ab mod n = gab mod n
Alice and Bob share now the secret key s = gab mod n
Since computing the inverse x = f-1(y) is extremely difficult, no
one listening to the key-exchange can compute the secret key s
from the values A, B, n and g.
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 18
The Diffie–Hellman Key-Exchange Algorithm
Practical Example
y=
gx
Prime modulus:
n = 31
Primitive element: g = 3
mod n
x
0
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15
y
1
3
9 27 19 26 16 17 20 29 25 13
8 24 10 30
x
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
y
28 22
4 12
5 15 14 11
2
6 18 23
7 21
1
A: a = 8
 A = 38 mod 31 = 20
s = 168 mod 31 = 4
B: b = 6
 B = 36 mod 31 = 16
s = 206 mod 31 = 4
Andreas Steffen, 17.10.2011, 4-PublicKey.pptx 19