UNIT-III

PUBLIC KEY CRYPTOGRAPHY

Public Key Cryptography: Asymmetric Encryption: Mathematics of Asymmetric Key Cryptography,
Asymmetric Key Cryptography

PUBLIC KEY CRYPTOSYSTEM PRINCIPLES

Public key cryptography also Known as asymmetric cryptography. Public-key systems depend on the
use of mathematical functions.
The concept of public key cryptography evolved from an attempt to attack two of the most difficult
problems associated with symmetric encryption.
The Key Exchange Problem The Trust Problem
The Key Exchange Problem: The key exchange problem arises from the fact that communicating parties must
somehow share a secret key before any secure communication can be initiated, and both parties must then
ensure that the key remains secret. Of course, direct key exchange is not always feasible due to risk,
inconvenience, and cost factors.
The Trust Problem: Ensuring the integrity of received data and verifying the identity of the source of that data
can be very important. Means in the symmetric key cryptography system, receiver doesn’t know whether the
message is coming for particular sender.
This public key cryptosystem uses two keys as pair for encryption of plain text and Decryption of
cipher text.
These two keys are names as “Public key” and “Private key”. The private key is kept secret whereas
public key is distributed widely.
A message or text data which is encrypted with the public key can be decrypted only with the
corresponding private-key
This two key system very useful in the areas of confidentiality (secure) and authentication

A public-key encryption scheme has six ingredients

Plaintext This is the readable message or data that is fed into the algorithm as
1
input.
Encryption The encryption algorithm performs various transformations on the plaintext.
2
algorithm
Public key This is a pair of keys that have been selected so that if one is used for
3
encryption, the other is used for decryption. The exact transformations

P.SOLMON CSE DEPT, NIT. Page 1

 Private performed by the algorithm depend on the public or private key that is
4
key provided as input
This is the scrambled message produced as output. It depends on
the plaintext and the key. For a given message, two different keys will
Cipher
5 produce two different cipher texts.
text
Decryption This algorithm accepts the cipher text and the matching key and
6
algorithm produces the original plaintext.

Public key cryptography for providing confidentiality (secrecy)

Figure 9.1
The essential steps are the following.
Each user generates a pair of keys to be used for the encryption and decryption of messages.
Each user places one of the two keys in a public register or other accessible file. This is the public key.
The companion key is kept private. As Figure 9.1a suggests, each user maintains a collection of public
keys obtained from others.
If Bob wishes to send a confidential message to Alice, Bob encrypts the message using Alice‟s public
key.
When Alice receives the message, she decrypts it using her private key. No other recipient can decrypt
the message because only Alice knows Alice‟s private key.

P.SOLMON CSE DEPT, NIT. Page 2

 There is some source A that produces a message in plaintext X = [X1, X2, . . . ,XM].

The M elements of X are letters in some finite alphabet. The message is intended for destination B. B generates
a related pair of keys: a public key, PUb, and a private key, PRb.

PRb is known only to B, whereas PUbis publicly available and therefore accessible by A.
With the message X and the encryption key PUbas input, A forms the cipher text Y = [Y1, Y2, .. ,YN]:

The intended receiver, in possession of the matching private key, is able to invert the transformation:

Public key cryptography for proving Authentication:

P.SOLMON CSE DEPT, NIT. Page 3

 The above diagrams show the use of public-key encryption to provide authentication:

In this case, A prepares a message to B and encrypts it using A‟s private key before transmitting it. B
can decrypt the message using A‟s public key. Because the message was encrypted using A‟s private
key, only A could have prepared the message. Therefore, the entire encrypted message serves as a
digital signature.

It is impossible to alter the message without access to A‟s private key, so the messageis authenticated
both in terms of source and in terms of data integrity.

Applications for Public-Key Cryptosystems

Public-key systems are characterized bythe use of a cryptographic algorithm with two keys, one held private and
one available publicly. Depending on the application, the sender uses either the sender‟s private key or the
receiver‟s public key, or both, to perform some type of cryptographic function.
We can classify the use of public-key cryptosystems into three categories
Encryption /decryption: The sender encrypts a message with the recipient‟s public key.
Digital signature: The sender “signs” a message with its private key. Signing is achieved by a

cryptographic algorithm applied to the message or to a small block of data that is a function of the
message.
Key exchange: Two sides cooperate to exchange a session key. Several different approaches are
possible, involving the private key(s) of one or both parties.

P.SOLMON CSE DEPT, NIT. Page 4

 Applications for Public-Key Cryptosystems

Algorithm Encryption/Decryptio Digital Key Exchange

n Signature
RSA Yes Yes Yes
Elliptic Yes Yes Yes
Curve
Diffie- No No Yes
Hellman
DSS No Yes No

Public-Key Cryptanalysis
 As with symmetric encryption, a public-key encryption scheme is vulnerable to a brute-force attack.
 The countermeasure is the same: Use large keys
 Public-key systems depend on the use of some sort of invertible mathematical function.
 Thus, the key size must be large enough to make brute-force attack impractical but small enough for practical
encryption and decryption. In practice, the key sizes that have been proposed do make brute- force attack
impractical but result in encryption/decryption speeds that are too slow for general-purpose use.
 Instead, as was mentioned earlier, public-key encryption is currently confined to key management and
signature applications.

RSA ALGORITHM

 It is one of the most common public key algorithm.

 It was first published by Rivest (R), Shamir (S) and Adleman (A) in the year 1977.
 The RSA scheme is a block cipher in which the plaintext & cipher text are integers
between 0 and n-1 for some „n‟.
 A typical size for „n‟ is 1024 bits or 309 decimal digits. That is, n is less than 21024

Description of the Algorithm:

RSA algorithm uses an expression with exponentials.
In RSA plaintext is encrypted in blocks, with each block having a binary value less than some
number n. that is, the block size must be less than or equal to log2(n)
RSA uses two exponents „e‟ and„d‟ where e public and d private.
Encryption and decryption are of following form, for some Plain Text „M‟ and Cipher text block „C‟

P.SOLMON CSE DEPT, NIT. Page 5

 M=Cd mod = (Me mod n) d mon n =(Me)d mod n= Med mod n

Both sender and receiver must know the value of n.

The sender knows the value of „e‟ & only the reviver knows the value of „d‟ thus this is a public key
encryption algorithm with a
Public key PU={e, n} Private key PR={d, n}

REQUIREMENTS:

The RSA algorithm to be satisfactory for public key encryption, the following requirements must be met:
It is possible to find values of e, d n such that “ Med mod n =M ” for all M<n It is relatively easy to
calculate “ Me mod n “ and “ Cd mod n “for M<n
It is infeasible to determine “d” given „e‟ & „n‟. The “ Med mod n =M ”

Then the relation between „e‟ & „d‟ can be expressed as this is equivalent to saying

That is „e‟ and „d‟ are multiplicative inverses mod Ø(n).

Steps of RSA algorithm:

Step 1: Select 2 prime numbers p & q Step 2: Calculate n=pq
Step 3: Calculate Ø(n)=(p-1)(q-1)
Step 4: Select or find integer e (public key) which is relatively prime to Ø(n).ie., gcd (Ø(n), e)=1 where 1<e<
Ø(n).
Step 5: Calculate “d” (private key) by using following condition.d<Ø(n).

Step 6: Perform encryption by using

Step 7: Perform Decryption by using

P.SOLMON CSE DEPT, NIT. Page 6

 Figure 9.5 summarizes the RSA algorithm. If Bob wants to send a message to Alice,Alice generates a
public/private key pair; Bob encrypts using Alice‟s public key; and Alice decrypts using her private key.

P.SOLMON CSE DEPT, NIT. Page 7

 Example:
1. Select two prime numbers, p = 17 and q = 11.
2. Calculate n = pq= 17 × 11 = 187.
3. Calculate Ø(n) = (p - 1)(q - 1) = 16 × 10 = 160.
4. Select e such that e is relatively prime to Ø(n) = 160 and less than Ø (n); we choose e = 7.
5. Determine d such that de ≡1 (mod 160) and d < 160.The correct value is d = 23, because23 * 7 =
161 = (1 × 160) + 1; d can be calculated using the extended Euclid‟s algorithm

The resulting keys are public key PU = {7, 187} and private key PR = {23, 187}.

The example shows the use of these keys for a plaintext input of M= 88. For encryption,
we need to calculate C = 887 mod 187. Exploiting the properties of modular arithmetic, wecan do this as
follows.

P.SOLMON CSE DEPT, NIT. Page 8

 Example 2:
 Choose p = 3 and q = 11
 Compute n = p * q = 3 * 11 = 33
 Compute φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20
 Choose e such that 1 < e <φ(n) and e and n are coprime. Let e = 7
 Compute a value for d. One solution is d = 3 [(3 * 7) % 20 = 1]
 Public key is (e, n) => (7, 33)
 Private key is (d, n) => (3, 33)
 Consider the plain text m=2
 The encryption of m = 2 is c = 27 mod33= 29
 The decryption of c = 29 is m = 293mod33 = 2

The Security of RSA

There are three main approaches of attacking RSA algorithm.

Brute force: This involves trying all possible private keys.

Mathematical attacks: There are several approaches, all equivalent in effort to factoring the
product of two primes.
Timing attacks: These depend on the running time of the decryption algorithm.
Chosen ciphertext attacks: This type of attack exploits properties of the RSA algorithm.

Taxonomy of potential attacks on RSA:

P.SOLMON CSE DEPT, NIT. Page 9

 DIFFIE-HELLMAN KEY EXCHANGE:

 Diffie-Hellman key exchange is the first published public key algorithm

 This Diffie-Hellman key exchange protocol is also known as exponential key agreement. And it is
based on mathematical principles.
 The purpose of the algorithm is to enable two users to exchange a key securely that can then be used
for subsequent encryption of messages.
 This algorithm itself is limited to exchange of the keys.

This algorithm depends for its effectiveness on the difficulty of computing discrete logarithms.
The discrete logarithms are defined in this algorithm in the way of define a primitive root of a prime
number.
Primitive root: we define a primitive root of a prime number P as one whose power generate all the
integers form 1 to P-1 that is if „a‟ is a primitive root ofthe prime number P, then the numbers
are distinct and consist of the integers form 1 through P-1 in some permutation. For any integer „b‟ and „a‟, here
„a‟ is a primitive root of prime number P, then b≡ ai mod P 0 ≤ i ≤ (P-1)

The exponent refer as discrete logarithm or index of b for the base a, mod P. The value denoted as
i inda,p(b)

Algorithm for Diffie-Hellman Key Exchange:

Step 1: Consider two publicly known numbers q, α

Q is Prime number and α is primitive root of q and α<q. Step 2: if A & B users wish to exchange a key
User A select a random integer XA<q and computes

User B independently select a random integer XB<q and computes

Each side keeps the X value private and Makes the Y value available publicly tothe outer side.
Step 3: UserA Computes the key as

P.SOLMON CSE DEPT, NIT. Page 10

 User B Computes the key as

Step 4: Two calculation produce identical results

(We know that )

(We know that )

The result is that the two sides have exchanged a secret key.

P.SOLMON CSE DEPT, NIT. Page 11

 Example:

P.SOLMON CSE DEPT, NIT. Page 12

 ELLIPTIC CURVE CRYPTOGRAPHY

Definition: Elliptic curve cryptography (ECC) is an approach to public-key cryptography based

on the algebraic structure of elliptic curves over finite fields. These are analogy of existing public
key cryptosystem in which modular arithmetic is replaced by operations defined over elliptic
curve.

ECC DIFFIE-HELLMAN KEY EXCHANGE:

ECC can do key exchange, that is analogous to Diffie Hellman.

Key exchange using elliptic curves can be done in the following manner.
First pick alarge integer q , which is either a prime number P or an integer of the form 2m andelliptic
curve parameters a & b for equation or
.
This define elliptic group of point Eq(a,b).

Pick a base point G=(x1,y1) in Ep(a,b) whose order is a very large value n.

P.SOLMON CSE DEPT, NIT. Page 13

 nG=0.Eq(a,b)

The order n of a point G on an elliptic curve is the smallest +ve integer n such that

Elliptic Curve Encryption/Decryption:

P.SOLMON CSE DEPT, NIT. Page 14

P.SOLMON CSE DEPT, NIT. Page 15