Transcript Document

Problems with symmetric (private key) encryption
1) secure distribution of keys
2) large number of keys
number of communicators 2
3
4
5
6
n
number of private keys
3
6
10
15
n(n-1)
2
1
Solution to both problems: Public Key (asymmetric) encryption
keypub
keypriv
plaintext
plaintext
ciphertext
encryption algorithm
decryption algorithm
DkeyPriv( EkeyPub(message)) = message
Data transmission via public key encryption
sue
bob
Every user maintains a unique pair of keys: one private and one public.
Public keys are available for anyone to use.
For Sue to send a message to Bob, she first encrypts using Bob’s public key. This ensures
that only Bob will be able to read the message.
Note that this preserves data confidentiality, but does not ensure authenticity.
Public key encryption first proposed in 1976 - Diffie & Hellman
• Rivest-Shamir-Adelman (1978) is the best known of current public key encryption methods.
• RSA poperties:
DkeyPriv(EkeyPub(message)) = message
DkeyPub(EkeyPriv(message)) = message
sue
bob
Secure transmission:
1) Sue encrypts the message (or part of it) using her private key.
2) Sue uses Bob’s public key to encrypt the result of (1).
3) The message is transmitted.
4) Bob decrypts the message with his private key.
5) Bob decrypts the result of (5) (or appropriate part) with Sue’s public key.
The above mechanism preserves both confidentiality and authenticity.
• Begin with two large primes (p and q).
• n = p*q
(Note that n should be about 200 digits - roughly 512 bits.)
• Select e relatively prime to (p-1)*(q-1).
• Select d so that (e*d) mod ((p-1)*(q-1)) = 1.
• public key: (e, n)
private key: (d, n)
Encryption Algorithm (apply to each part of the transmission)
Ee(message) = (messagee) mod n
Decryption Algorithm (apply to each part of the transmission)
Dd(message) = (messaged) mod n
Side note: (p-1)*(q-1) comes from Euler’s definition of totient
(n) = number of positive integers less than n that are relatively prime to n.
Example
(note that numbers are artificially small.)
p = 2 q = 17
Therefore, n = p*q = 34
Select e = 3
Note that (p-1)*(q-1) = 16. (3 and 16 are relatively prime.)
d = 11 because e*d = 3*11 = 33 and 33 mod 16 = 1
Treat alphabet as integers from zero, and include blank:
K
B
C
D
E
F
G
H
I
J
0
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 23 25 26
to encipher H
H 7
7e mod n = 73 mod 34 = 3
to encipher I
I 8
8e mod n = 83 mod 34 = 2
HI MOM SEND
3 2 32 28 24 28 32 18 30 21 27
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z

A
to decipher 3
3d mod n = 311 mod 34 = 7
7H
to decipher 2
2d mod n = 211 mod 34 = 8
8I
3 2 32 28 24 28 32 18 30 21 27
7 8 26 12 14 12 26 18 4 13 3
Cryptanalysis Issues
1) The values of p, q, and (n) are not divulged.
2) Cryptanalysis of RSA accomplished by finding the prime factors of a 200-digit number.
3) Factoring is not known to be an NP problem, but the best known
algorithms are exponential.
4) To date no serious security flaws have been discovered.
Finding p and q
• Verifying that p and q are prime requires testing about 1050 potential factors.
• A practical alternative (Solovay & Strassen algorithm) tests a number
to any desired probability of being prime.
Encryption & Decryption
• RSA can be as much as 10,00 times slower than symmetric algorithms
(Multiplication used in place of bit manipulation and table lookup/indexing).
• to improve computation: (a * b) mod n = [(a mod n) * (b mod n)] mod n