Asymmetric Encryption
Uses publicprivate key pair 
Each user generates a pair of public and private keys 
Public Key is known to everyone and is used to encrypt data 
Private Key is only known to the key owner and used for decryption 
Used in 3 categories
–Encryption/Decryption (provide secrecy) 
–Digital signatures (provide authentication) 
–Key exchange (of session keys) 
DiffieHellman key exchange
First publickey type scheme 
Proposed by Diffie & Hellman in 1976 
A practical method for public exchange of a secret key 
Cannot be used to exchange an arbitrary message 
Security relies on the difficulty of computing discrete logarithms 
DiffieHellman algorithm
q 
prime number 
α 
α<q ,α primitive root of q 
User A 
Select PR=Xa 
Xa<q 
Calculate PU=Ya 
Ya=α^Xa mod q 
User B 
Select PR=Xb 
Xb<q 
Calculate PU=Yb 
Yb=α^Xb mod q 
Secret key calculation 
User A 
K=(Yb)^Xa mod q 
User B 
K=(Ya)^Xb mod q 
Disadvantages
Cannot be used for asymmetric key exchanges 
ManintheAttack 
ElGammalCryptosystem
Presented in 1984 by Tather Elgammal 
Used for encrypting messages 
Based on discrete lagarithmic problem 
Disadvantages 
Decryption is slow 
Duplicates message length by factor of two during encryption 
ElGammal algorithm
Select large prime 
q 
Select 
p , p is primitive root of q 
User A 
Choose private key 
Xa , 1 < Xa < q1 
Compute public key 
Ya=p^Xa mod q 
Similarly User B calculates Xb and Yb 
Encryption from A 
Message M 
0<=M<=q1 
Choose k 
1<=k<=q1 
Compute 
K=Ya^k mod q 
Compute 
C1=p^k mod q 
Compute 
C2=KM mod q 
Ciphertext(C1,C2) 
Decryption from B 
Recover key 
K=C1^Xa mod q 
Compute message 
M=C2*K1 mod q 
RSA
Uses large integers (eg.1024 bits) 


RSA key generation
Select two large primes p and q 
p not equal to q 
Calculate 
n<p*q 
Calculate 
O(n)<(p1)*(q1) 
Select e 
1<e<O(n) and e is coprime to O(n) 
Calculate 
d<e^1mod O(n) 
Public key 
PU={e,n} 
Private key 
PR={d,n} 
Encryption 
Plaintext 
M<n 
Ciphertext 
C=M^e(mod n) 
Decryption 
Plaintext 
C 
Ciphertext 
M=C^d(mod n) 
Key Distribution Techniques
Means of delivering key to two parties who wish to communicate 
For symmetric encryption to work,two parties must exchange the same key 
Publickey cryptosystems are mostly used to encrypt secret keys 
Frequent key exchanges are desirable to limit the amount of data compromised 
The strength of any cryptographic system relys on key distribution technique 
Advantages and Disadvantages
Hard to crack since it involves factorization of prime numbers 
Can be very slow in cases where large data needs to be encrypted 
ManintheMiddle attack 
Key Distribution Models
Model 1 
A>B 
PUaIDa 
B>A 
E(PUa,ks) 
Ensures confidentiality but not authentication 
Vulnerable to maninthemiddle attack 
Model 2 
A>B 
E(PUb,[N1IDa]) 
B>A 
E(PUa,[N1N2]) 
A>B 
E(PUa,N2) 
A>B 
E(PUb,E(PRa,Ks)) 
ensures both confidentiality and authentication 
Distribution of public keys:
Public announcement 
Feeding in a Publicly available directory 
Both vulnerable to forgery(anyone can claim to be someone) 
Public Key Authority 
A trusted third party(KDC) 
Provides session keys to users who wish to communicate 
Requires users to be registered 
Just like a directory composed of users public key 
User interacts with the directory to obtain any desired public key securely 
Interaction Model: 
A>auth 
RequestT1 
auth>A 
Epr_auth[KPU_bRequestT1] 
A>B 
Epu_b[IDAN1] 
B>auth 
RequestT2 
auth>B 
Epr_auth[KPU_aRequestT2] 
B>A 
Epu_a[N1N2] 
A>B 
Epu_b[N2] 


PublicKey Certificates:
Certificates allow key exchange without realtime access to PublicKey Authority 
A certificate binds user identity to public key 
Certificate contains all necessary details appended by its hash 
Helps user claim accountability for a Key 
X_509 Certificates: 
Issued by a Certification Authority (CA) 
Part of CCITT X.500 directory service standards 
Defines the framework for authentication 
Uses publickey crypto & digital signatures 
X.509 certificates are widely used and has 3 versions 
Each version with information extended 
Certificate contains information such as Public Key, Digital Signature , Issuer, Version, Serial Number, Time Stamp. 
X.509 Version 3: 
Has been recognised that additional information is needed in a certificate 
email/URL, policy details, constraints 
Rather than explicitly naming new fields defined a general extension model 
Identifier, Criticality Indicator, Value 
Hash Functions
Accepts variable length input M and produces fixedsize hash h 
h = H(M) 
Principal object is data integrity 
It is infeasible to find object 
 With prespecified hash(OneWay Property) 
Two objects mapping to same hash(Collision Free Property) 
Message Authentication Code(MAC):
Also known as a keyed hash function 
Concerned with integrity and authentication 
Calculates hash from the message and encrypts with the secret key>Cryptographic Checksum or MAC or Tag 
Then is appended to the message 
The reciever calcutates the hash of message and compares 
Same hash value confirms that the message came from the stated sender (its authenticity) and has not been changed. 
Digital Signatures :
Concerned with integrity , authentication, Nonrepudiation 
Operation is similar to that of the MAC 
Model1: 
Instead the hash value of a message is encrypted with a user’s private key 
Anyone who knows the user’s public key can verify the integrity of the message 
An attacker who wishes to alter the message would need to know the user’s private key 
This provides authentication. 
Model 2 : 
Once the encrypted hash of the message is calulated and appended to original message 
Once again it is encrypted with the symmetric secret key 
Reciever decrypts it with the symmetric key then public key 
Then calculates hash of message and compares 
This ensures confidentiality as well as authentication 
