Transcript No Slide Title

ECE-8843
http://www.csc.gatech.edu/copeland/jac/8843/
Prof. John A. Copeland
[email protected]
404 894-5177
fax 404 894-0035
Office: GCATT Bldg 579
email or call for office visit, or call Kathy Cheek, 404 894-5696
Chapter 3 - Public-Key Cryptography & Authentication
Authentication
Requirements - must be able to verify that:
1. Message came from apparent source or author,
2. Contents have not been altered,
3. Sometimes, it was sent at a certain time or sequence.
Sometimes we would like to provide authentication without
encryption (public statements do not need privacy). Still,
authentication requires that the sender know something that the forger
does not ( a secret key).
Conventional encryption can be used, but the sender must share the
secret key with the receiver.
2
3
(b) Using public-key
encryption
4
Secret Value is added by both parties to message before the “hash,”
function is used to get the Message Integrity Check (MIC). It is
removed before transmission.
MIC
MIC
It is critical that a forger can not compose a different message that
would produce the same MIC value.
5
6
SHA-1
Secure Hash Algorithm 1
7
8
HMAC Structure
9
Public-Key Cryptography
(Public-Private Key)
plaintext (data file or message)
encryption by key-1
decryption by key-1
ciphertext (stored or transmitted safely)
decryption by key-2
encryption by key-2
plaintext (original data or message)
10
Encryption using a
Public-Key System
11
Authentication using a
Public-Key System
12
RSA (Rivest, Shamir, and Adleman)
Key length is variable, 512 bits most common.
• The plaintext block ("m") must be less than the key
length.
Key Generation
•
•
•
•
•
Choose two large prime numbers, p and q (secret)
n = pq,
Ø(n) = (p-1)(q-1)
Find a number, e, that is relatively prime to Ø(n)
The public key is e and n (e,n)
Find d, the multiplicative inverse to e mod Ø(n)
(by “Number Theory”: d * e mod Ø(n) = 1)
The private key is d and n (d,n), public key is (e,n)
Encryption: c = m^e mod n
Decryption: m = c^d mod n
("m" is message)
("c" is ciphertext)
13
Is RSA Secure?
To factor a 512-bit number (to find p and q
from n) with the best known technique would
take 500,000 MIPs-years
•
In 500 years on a 1000 MIP/s CPU, an
eavesdropper can encrypt a list of all
possible messages (using the Public Key),
and compare the corresponding ciphertext to
the transmitted ciphertext.
• If the message is your password, make sure you
picked a good one (not in any dictionary).
•
A defense is to add random bits to the message.
MIPs - Millions of Instructions per second.
14
How Efficient are RSA Operations
Efficient techniques for doing exponentiation:
X * Y mod n = (X mod n) * (Y mod n)
•
Do a "mod n" operation whenever a multiplier is
bigger than n
To calculate x^10 1
1011101100001
2
mod n
x^10 2 = (x^1 2 )^2
x^100 2 = (x^10
2
)^2
x^(10 12 ) = (x^100
2
)*x
15
Does It Work?
(Does D(E(m))=m)
c = E(m) =(m ^ e) mod n
D(c) = (c ^ d) mod n
(the ciphertext)
(decryption of c)
= m^(e*d) mod n
= m^(e*d mod Ø(n)) mod n
(Number Theory)
= m^(1) mod n
=m
(the plaintext message)
To experiment use: www.csc.gatech.edu/copeland/jac/8843/tools/RSA.xls
16
17
Public-Key Systems
Digital
Signature
X
Key
Exchange
X
Diffie-Hellman
X
X
DSS
X
RSA
Elliptic Curve
Encrypt/
Decrypt
X
X
X
X
18
Diffie-Hellman Technique
Mutual Secret Keys or Public-Private Keys
Global Public Elements: q (large prime) and a (a < q)
User A‘s Keys:
Select secret Xa (Xa < q)
Public Key is Ya = a^Xa mod q
User B‘s Keys:
Select secret Xb (Xb < q)
Public Key is Yb = a^Xb mod q
Mutual Key is K =
Yb ^Xa (A’s calculation)
Ya ^ Xb (B’s calculation)
a^(Xa*Xb) mod q (in both cases)
No one else knows either Xa or Xb, so they can not find out K
19
Diffie-Hellman as used
for a Public-Private System
+ a and q
+ message encrypted
with “ K”
(Ya, a,q are A’s Public Key)
B has to send “ Yb” with
message so A can decrypt it.
“Trudie” does not know Xa: Can not read message.
20
Raw “Certificate” has user name, public key, expiration date, ...
Raw
Cert.
Generate hash code
of Raw Certificate
MIC
Hash
Signed
Cert.
Signed Certificate
Recipient can verify
signature using CA’s
public key.
Encrypt hash code
with CA’s private key
to form CA’s
signature
Certificate Authority generates the
“signature” that is added to raw
“Certificate”
21