Computer Security: Principles and Practice, 1/e
Asymmetric/Public key cryptography
Lecture 5a
1
Overview
Revisiting: intro to asymmetric crypto and key change issue
Applications of asymmetric cryptography
Key maths concept in asymmetric cryptography
RSA cipher
1) General process
2) Examples: example01 and example02
3) Security issues with RSA
4) Timing attacks
Diffie Hellman Exchange
1) Intro
2) General process
3) Examples
4) Security issues: Man-in-the-middle attack
Public-Key Encryption Structure
3
Publicly proposed by Diffie and Hellman in 1976
Based on mathematical functions
Asymmetric
Uses two separate keys
Public key and private key
Public key is made public for others to use
Some form of protocol is needed for distribution
**
Plaintext
Readable message or data that is fed into the algorithm as input
Encryption algorithm
Performs transformations on the plaintext
Public and private key
Pair of keys, one for encryption, one for decryption
Ciphertext
Scrambled message produced as output
Decryption key
Produces the original plaintext
4
User encrypts data using his or her own private key
Anyone who knows the corresponding public key will be able to decrypt the message
5
Requirements for Public-Key Cryptosystems
6
Computationally easy to create key pairs
Computationally easy for sender knowing public key to encrypt messages
Computationally easy for receiver knowing private key to decrypt ciphertext
Computationally infeasible for opponent to otherwise recover original message
Useful if either key can be used for each role
Computationally infeasible for opponent to determine private key from public key
Public key methods
Applications for Public-Key Cryptosystems
8
RSA Public-Key Encryption
By Rivest, Shamir & Adleman of MIT in 1977
Best known and widely used public-key algorithm
Uses exponentiation of integers modulo a prime
Encrypt: C = Me mod n
Decrypt: M = Cd mod n = (Me)d mod n = M
Both sender and receiver know values of n and e
Only receiver knows value of d
Public-key encryption algorithm with public key PU = {e, n} and private key PR = {d, n}
10
Perhaps the most widely used public-key algorithms are RSA and Diffie-Hellman.
One of the first public-key schemes was developed in 1977 by Ron Rivest, Adi Shamir, and Len Adleman at MIT and first published in 1978. The RSA scheme has since that time reigned supreme as the most widely accepted and implemented approach to public-key encryption. RSA is a block cipher in which the plaintext and ciphertext are integers between 0 and n – 1 for some n.
Encryption and decryption are of the following form, for some plaintext block M and ciphertext block C:
C = Me mod n
M = Cd mod n = (Me)d mod n = Med mod n
Both sender and receiver must know the values of n and e, and only the receiver knows the value of d. This is a public-key encryption algorithm with a public key of PU = {e, n} and a private key of PR = {d, n}.
P and q numbers in real
12
RSA – example01
Encryption
Decryption
Public key: (5,14)
Plaintext: B 2 index
( mod ) 14
= 32 (mod 14)
= 4 (mod) 14
= D = 4 index
Private key (11, 14)
Note: 14 is the same
Ciphertext: D 4
(mod)14
= 4194304 (mod 14)
= 2 (mod 14)
= B = 2 index
C= mod N
M= mod N
How does it work?
1st step: two primes number p and q
p=2 and q=7
2nd step: product of p and q = p x q = 14 = N
which is mod in public and private key, it is publicise
3rd step: (pronounced as PHI(N) = (p-1)(q-1)
=(2-1)(7-1)
= 6 = total number of co-prime
4th step: Choose e 1< e < (N) = 2,3,4,5
{ co-prime with N, (N) = 2,3,4,5
N=14, (N)=6;
public key = 5, 14
5th step: choose d: de (mod (N)) = 1
5d (mod 6) = 1
d should be such a number that when it multiplies with 5 and find mod by 6, it should give you 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
d 1 2 3 4 5 …..
5d 5 10 15 20 25 ……
mod 6 5 4 3 2 1 0
This pattern repeat, pick any number that give you mod 1
How many coprime below 14?
14=2x7 2=2x1
4=2x2
6=3x2
8=2x2x2
12=2x2x3
14=2x7 1=1x1
3=3x1
5=5x1
7=7x1
9=3x3
11=11x1
13=13x1
Coprime
1=1x1
3=3x1
5=5x1
9=3x3
11=11x1
13=13x1
Example02
Encryption Decryption
two primes p x q ; p=3, p=11
N = p x q = 3 x 11 = 33
(N) = (p-1)(q-1) = (3-1) (11-1) = 2 x 10 = 20 [this will be our mod] = Both parties will have this value
Selecting e
1< e < (N) = 1