Chapter-2
Public Key Cryptography
Public-Key Encryption:
Public-key algorithms are based on mathematical functions rather than on simple
operations on bit patterns, such as are used in symmetric encryption algorithms.
Public-key cryptography is asymmetric, involving the use of two separate keys—in
contrast to the symmetric conventional encryption, which uses only one key.
Public-Key Encryption Structure:
1
A public-key encryption scheme has six ingredients
1) Plaintext: This is the readable message or data that is fed into the algorithm as input.
2) Encryption algorithm: The encryption algorithm performs various transformations on the
plaintext.
3) &4) Public and private key: This is a pair of keys that have been selected so that if one is
used for encryption, the other is used for decryption. The exact transformations performed by the
encryption algorithm depend on the public or private key that is provided as input.
5) Ciphertext: This is the scrambled message produced as output. It depends on the plaintext
and the key. For a given message, two different keys will produce two different ciphertexts.
6) Decryption algorithm: This algorithm accepts the ciphertext and the matching key and
produces the original plaintext.
As the names suggest, the public key of the pair is made public for others to use, while the
private key is known only to its owner. A general-purpose public-key cryptographic algorithm
relies on one key for encryption and a different but related key for decryption.
Public Key Cryptography:Secrecy
2
• We have a source A that produces plaintext X destined for B .
• B generates a pair of keys KUb (a public key) and KRb (a privatekey).
• With X and KUb as inputs, A forms the ciphertext Y :
• Y = EKUb(X)
• The intended receiver B is able to invert the transformation with his private key:
• X = DKRb(Y )
Public Key Cryptography: Authentication:
• A prepares a message to B using his private key to encrypt and B can decrypt it using A’s
public key .
• Y = EKRa(X)
• X = DKUa(Y )
• As the message was prepared using A’s private key it could only have come from A
therefore the entire message serves as a digital signature.
3
Public Key Cryptography: Confidentiality& Authentication
Encryption:
• We have a source A that produces plaintext X destined for B.
• B generates a pair of keys KUb (a public key) and KRb (a privatekey).
• A prepares a message to B using his private key to encrypt and B can decrypt it using
A’s public key
Y = EKRa(X)
• With Y and KUb as inputs, A forms the ciphertext Z
Z = EKUb(Y)= EKUb(EKRa(X))
• The intended receiver B is able to invert the transformation with his private key:
Y = DKRb(Z )
• A prepares a message to B using his private key to encrypt and B can decrypt it using A’s
public key .
X = DKUa(Y ) = DKUa(DKRb(Z ) )
4
One-Way function:
A function which is easy to compute in one direction, but hard to compute in the other, is
known as a one-way function.
o Hashing, modular arithmetic.
A one-way function that can be easily inverted with an additional piece of knowledge is
called a trapdoor one-way function.
Password systems also use one-way functions.
The RSA Public-Key Encryption Algorithm:
One of the first public-key schemes was developed by Ron Rivest, Adi Shamir, and Len
Adleman.
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 period 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 KU= {e, n} and a private
key of KR ={d, n}.
The following requirements must be met for RSA Algorithm
ed
1. It is possible to find values of e, d, n such that M mod n= M for all M < n.
e d
2. It is relatively easy to calculate M and C for all values of M< n.
3. It is infeasible to determine d given e and n.
Key generation Algorithm for RSA:
1. Select two prime numbers, p= 17 and q= 11.
2. Calculate n = pq = 17 × 11 = 187.
5
3. Calculate f(n) =(p 1)(q 1) =16 * 10 =160.
4. Select e such that e is relatively prime to f(n) =160 and less than f(n); we choose e=7.
5. Determine d such that de mod 160= 1 and d < [Link] correct value is d 23, because 23 * 7
=161 =(1 *160)+ 1
6
There are two possible approaches to defeating the RSA algorithm.
The first is the brute-force approach: Try all possible private keys. Thus, the larger the
numbers of bits in e and d, the more secure the algorithm.
Most discussions of the cryptanalysis of RSA have focused on the task of factoring n into
its two prime factors. For a large n with large prime factors, factoring is a hard problem.
Disadvantage of RSA:
Calculations involved (both in key generation and in encryption/decryption) are complex,
the larger the size of the key, the slower the system will run.
Diffie-Hellman Key Exchange:
The purpose of the algorithm is to enable two users to exchange a secret key securely that
then can be used for subsequent encryption of messages.
The algorithm itself is limited to the exchange of the keys.
There are two publicly known numbers: a prime number q and an integer α that is a primitive
root of q. Suppose the users A and B wish to exchange a key.
User A selects a random integer XA < q and computes YA = α XA mod q.
Similarly, user B independently selects a random integer XB < q and computes
YB = α XB. mod q
7
Each side keeps the X value private and makes the Y value available publicly to the other
side.
User A computes the key as K = (YB)XA mod q
User B computes the key as K = (YA)XB mod q
8
9
Key Management:
• public-key encryption helps address key distribution problems
• have two aspects of this:
– distribution of public keys
– use of public-key encryption to distribute secret keys
Distribution of Public Keys:
Distribution of public key can be done in following ways
– Public announcement
– Publicly available directory
– Public-key authority
– Public-key certificates
Public Announcement:
users distribute public keys to recipients or broadcast to community at large.
major weakness is forgery
o anyone can create a key claiming to be someone else and broadcast it
o until forgery is discovered can masquerade as claimed user
Publicly Available Directory:
• can obtain greater security by registering keys with a public directory
• directory must be trusted with properties:
– contains {name,public-key} entries
– participants register securely with directory
– participants can replace key at any time
– directory is periodically published
– directory can be accessed electronically
• still vulnerable to tampering or forgery
10
Public-Key Authority:
Improve security by tightening control over distribution of keys from directory.
It has properties of directory and requires users to know public key for the directory.
Users interact with directory to obtain any desired public key securely.
Suppose consider user A wants to know public key of user B, the following procedure to
be followed for obtaining keys.
1) User A request Public key authority for the public key of user B
Request║Time1
Where time1 is the time of the request send by user A
2) Public key authority check whether user A is registered user or not .If user A is a
registered user it responds user A request and send the public key of user B (KUb) &
request message by encrypting the same by using public key authority private key
(KRauth)
E [KRauth [KUb║ Request║Time1]
3) Once user A obtain the public key of user B, user A encrypt the message by using the
public key of B with user A’s identity along with message number N1
11
E [KUb [IDA║ N1]
4) Since user B also not aware of the public key of user A,it will request public key
authority for the public key for user A.
Request║Time2
Where time2 is the time of the request send by user B
5) Public key authority check whether user B is registered user or not .If user B is a
registered user it responds user B request and send the public key of user A (KUa) &
request message by encrypting the same by using public key authority private key
(KRauth)
E [KRauth [KUa║ Request║Time1]
6)Once user B obtain the public key of user A, user B encrypt the message N2 by using
the public key of B along with message number N1
E [KUa [N1║ N2]
7) User A will acknowledge the message number N2 from user B.
E [KUa [N2]
Public-Key Certificates:
certificates allow key exchange without real-time access to public-key authority
a certificate binds identity to public key
o usually with other info such as period of validity, rights of use etc
with all contents signed by a trusted Public-Key or Certificate Authority (CA)
can be verified by anyone who knows the public-key authorities public-key .
12
1) User A send its public key KUa to Certificate Authority to issue a certificate for user A
that is CA .
2) If user A is a registered user in the directory, Certificate Authority responds to user A
request by creating a certificate for user A which contains identity of user A (IDA),public
key of user A (KUa) and time information about when A has send request encrypted by
using the private key of certificate authority.
CA=E [KRauth [KUa║ IDA ║Time1]
3) Once the user A receives the certificate it send the same to User B.
4) User B send its public key KUb to Certificate Authority to issue a certificate for user B
that is CB .
5) If user B is a registered user in the directory, Certificate Authority responds to user B
request by creating a certificate for user B which contains identity of user B (IDB),public
key of user A (KUb) and time information about when B has send request encrypted by
using the private key of certificate authority.
CB=E [KRauth [KUb║ IDB ║Time2]
6) Once the user b receives the certificate it send the same to User A.
13