ASYMMETRIC KEY /PUBLIC KEY CRYPTOGRAPHY

Asymmetric key cryptosystems / public-key cryptosystems use a pair of keys:

public key (encryption key) and private key (decryption key).
Public Key Cryptography ?

 Public key cryptography also called as asymmetric cryptography.

 It was invented by whitfield Diffie and Martin Hellman in 1976. Sometimes this
cryptography also called as Diffie-Helman Encryption.
 Public key algorithms are based on mathematical problems which admit no
efficient solution that are inherent in certain integer factorization, discrete
logarithm and Elliptic curve relations.
Public key Cryptosystem Principles:
 The concept of public key cryptography is invented for two most difficult problems
of Symmetric key 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
These two key systems very useful in the areas of confidentiality (secure) and
authentication.

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 Encryptio The encryption algorithm performs various transformations on
n the plaintext.
algorithm
3 Public key This is a pair of keys that have been selected so that if one is
used for
 4 Private encryption, the other is used for decryption. The exact
key transformations performed by the
algorithm depend on the public or private key that is provided
as input
This is the scrambled message produced as output. It
5 Ciphertex depends on the plaintext and the key. For a given message, two
t different keys will produce two different
ciphertexts.
6 Decryptio This algorithm accepts the ciphertext and the matching key and
n produces the original plaintext.
algorithm

Public key cryptography for providing confidentiality (secrecy)

The essential steps are the following.

1. Each user generates a pair of keys to be used for the encryption and decryption
of messages.
2. 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 the above Figure
suggests, each user maintains a collection of public keys obtained from others.
3. If Bob wishes to send a confidential message to Alice, Bob encrypts the message using
Alice‟s
public key.
4. 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.
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 PUb is publicly available and therefore accessible
by A.
With the message X and the encryption key PUb as input, A forms the ciphertext 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:
 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
message is authenticated both in terms of source and in terms of data integrity.

Public key cryptography for both authentication and confidentiality

(Secrecy)
 It is, however, possible to provide both the authentication function and
confidentiality by a double use of

the public-key scheme (above figure):

In this case, we begin as before by encrypting a message, using the senders private
key. This provides the digital signature. Next, we encrypt again, using the receivers
public key. The final ciphertext can be decrypted only by the intended receiver, who
alone has the matching private key. Thus, confidentiality is provided.

Applications for Public-Key Cryptosystems

Public-key systems are characterized by the use of a cryptographic algorithm with
two keys, one held private and one available publicly. Depending on the
application, the sender uses either the senders private key or the receivers public
key, or both, to perform some type of cryptographic function. the use of public-
key cryptosystems into three categories
• Encryption /decryption: The sender encrypts a message with the recipients 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.
Applications for Public-Key Cryptosystems
Algorithm Encryption/Decryp Digital Signature Key Exchange
tion
RSA Yes Yes Yes
Elliptic Curve Yes Yes Yes
Diffie-Hellman No No Yes
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. However, there
is a tradeoff to be considered. Public- key systems depend on the use of some sort
of invertible mathematical function. The complexity of calculating these functions
may not scale linearly with the number of bits in the key but grow more rapidly
than that. 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 the most common public key algorithm.

 This RSA name is get from its inventors first letter (Rivest (R), Shamir (S) and
Adleman (A)) in the year 1977.
 The RSA scheme is a block cipher in which the plaintext & ciphertext 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 PlainText M and
CipherText block C

M=Cd mod = (Me mod n) d mod 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 receiver 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}
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., e with
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
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,
because 23 * 7
= 161
= (1 × 160) + 1;
d can be calculated using the extended Euclids algorithm
 6. 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, we can do this as follows.

The Security of RSA

Four possible approaches to attacking the RSA algorithm are
• 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.
Trapdoor one-way function
 A trapdoor function is a function that is easy to perform one way, but has a secret
that is required to perform the inverse calculation efficiently.
 That is, if f is a trapdoor function, then y=f(x) is easy to compute, but x=f−1(y) is hard
to compute without some special knowledge k. Given k, then it is easy to compute
y=f−1(x,k).
 The analogy to a "trapdoor" is something like this: It's easy to fall through a trapdoor,
but it's very hard to climb back out and get to where you started unless you have
a ladder.
 An example of such trapdoor one-way functions may be finding the prime factors of
large numbers. Nowadays, this task is practically infeasible.
 On the other hand, knowing one of the factors, it is easy to compute the
other ones. For example: RSA is a one-way trapdoor function
 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 from 1 to P-1 that is if ‘a’ is a primitive root of the
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≡ aimod P 0 ≤ i ≤ (P-1)
The exponent i is refer as discrete logarithm or index of b for the base a, mod P.
The value denoted as ind a,p(b)

Algorithm for Diffie-Hellman Key Exchange:

Step 1 Select global public numbers q, α

q Prime number
α primitive root of q and α< q.
Step 2 if A & B users wish to exchange a key
a) User A select a random integer XA<q and computes
b) User B independently select a random integer XB <q and computes
c) Each side keeps the X value private and Makes the Y value available publicly to
the outer side.
Step 3 User A Computes the key as User B Computes
the key as

Step 4 two calculation produce identical results

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

Example:
 MAN-in the Middle Attack (MITM)

Definition: A man in the middle attack is a form of eavesdropping where

communication between two users is monitored and modified by an unauthorized
party.
Generally the attacker actively eavesdrops by intercepting (stoping) a public key
message exchange.

The Diffie- Hellman key exchange is insecure against a “Man in the middle
attack”.
Suppose user A & B wish to exchange keys, and D is the adversary (opponent). The
attack proceeds as follows.
1. D prepares for the attack by generating two random private keys XD1 & XD2 and
then computing the corresponding public keys YD1 and YD2.
2. A transmits YA to B
3. D intercepts YA and transmits YD1 to B. and D also calculates
4. B receives YD1 & calculate
5. B transmits YB to A
6. Dintercepts YB and transmits YD2 to „A‟ and „D‟ calculate K1
7. A receives YD2 and calculates
At this point, Bob and Alice think that they share a secret key, but instead Bob and
Darth share secret key K1 and Alice and Darth share secret key K2. All future
communication between Bob and Alice is compromised in the following way.

The key exchange protocol is vulnerable to such an attack because it does not
authenticate the participants. This vulnerability can be overcome with the use of
digital signatures and public-key certificates.
Elliptic Curve Cryptography
 Elliptical curve cryptography (ECC) is a public key encryption technique based on
 elliptic curve theory that can be used to create faster, smaller, and more efficient
cryptographic keys. ECC generates keys through the properties of the elliptic
curve equation instead of the traditional method of generation as the product of
very large prime numbers
 An elliptic curve is defined by an equation in two variables with coefficients. For
cryptography, the variables and coefficients are restricted to elements in a finite
field, which results in the definition of a finite abelian group.

Elliptic Curves over Real Numbers

ECC-Key Exchange:
Take two Global public Elements
Eq(a,b) : Elliptic curve with parameters a,b, & q
G : Point on elliptic curve whose order is large value n
Alice Key Generation:
Select private key nA : nA < n Calculate public key PA: PA = nAxG
Bob Key Generation:
Select private key nB : nB < n Calculate public key PB: PB = nBxG
Secrete Key calculation by Alice
K=nAxPB
Secrete Key calculation by Bob
K=nBxPA
ECC- Encryption
 Let the message be M
 First encode the message M into a point on the elliptic curve
 Let this point be Pm
 Now this point is encrypted
 For encryption choose a random positive integer k
 Then Cm={ kG,Pm+kPB } where G is the base point
ECC-Decryption
 Multiply first point in the pair with receivers secrete key i.e, kG x nB
 Then subtract it from second point in the pair i.e, Pm + kPB- (kGx nB)
 ELGAMAL CRYPTOGRAPHIC SYSTEM
 In 1984, T. Elgamal announced a public-key scheme based on discrete
logarithms, closely related to the Diffie-Hellman technique.
 EIGamal Algorithms are used for both digital signatures as well as
encryption.

EIGamal Algorithm:-

Thus, functions as a one-time key, used to encrypt and decrypt the

message. For example, let us start with the prime field GF(19); that is, q =
19. It has primitive roots {2, 3, 10, 13, 14, 15 }. We choose α = 10.
Alice generates a key pair as follows:
RABIN CRYPTOSYSTEM
Rabin Cryptosystem is an public-key cryptosystem invented by Michael Rabin, is a
variation of the RSA. RSA is based on the exponentiation congruence; Robin is based
on quadratic congruence.
The public key in the Rabin is n, private key is the tuple(p,q). Everyone can encrypt
a message using n, only Bob can decrypt the message using p and q.
Decryption of the message is infeasible It uses asymmetric key encryption for
communicating between two parties and encrypting the message.
The security of Rabin cryptosystem is related to the difficulty of factorization. It has
the advantage over the others that the problem on which it banks has proved to be
hard as integer factorization.
It has the disadvantage also, that each output of the Rabin function can be generated
by any of four possible inputs. if each output is a cipher text, extra complexity is
required on decryption to identify which of the four possible inputs was the true
plaintext.

Steps in Rabin cryptosystem Key generation

1. Generate two very large prime numbers, p and q, which satisfies the condition
p ≠ q → p ≡ q ≡ 3 (mod 4)
For example:
p=139 and q=191
2. n = p.q
3. Public_key=n
4. Private_key=(p,q)
5. Return public_key, Private_keys
Encryption
1. Get the public key n.
2. Convert the message to ASCII value. Then convert it to binary and extend
the binary value with itself, and change the binary value back to decimal M.
3. Encrypt with the formula: C = M2 mod n
4. Send C to recipient.

Decryption
1. Accept C from sender.
2. Compute:
a1 = C (p+1)/4 mod p a2= - C(p+1)/4 mod p b1= C(q+1)/4 mod q b2= - C(q+1)/4 mod q
3. Calculate four Plain text by using Chinese Remainder
4. Algorithm:
M1=Chainese_Remainder(a1,b1,p,q)
M2=Chainese_Remainder(a1,b2,p,q)
M3=Chainese_Remainder(a2,b1,p,q)
M4=Chainese_Remainder(a2,b2,p,q)
5. Choose one of the above (M1,M2,M3 and M4) is the appropriate plaintext.

The Rabin cryptosystem is not deterministic: Decryption creates four equally

probable plain texts

Example:
1. Bob selects p=23 and q=7, note both are congruent to 3 mod 4
2. Bob calculates n=pxq=161
3. Bob announces n publickly; he keeps p and q private
4. Allice want to send plain text P=24. Note that 161and 24 are relatively prime; 24
is in Z161* She calculates C=242 mod 161 =93 mod 161, and sends the ciphertext 93
 to Bob
5. Bob receives 93 and calculates four values:
a. a1=+(93(23+1)/4 mod 23=1 mod 23
b. a2=-(93(23+1)/4 mod 23=22 mod 23
c. b1=+(93(7+1)/4 mod 7=4 mod 7
d. b2=-(93(7+1)/4 mod 7=3 mod 7
6. Bob takes four possible answers, (a1,b1), (a1,b2), (a2,b1),(a2,b2) and uses
Chinese Remainder Theorem to find 4 possible plain texts: 116,24,137 and 45.

Case 1:
By using (a1=1,b1=4) combinations with modulo (p=23,q=7), Let X is plain text: X = 1
mod 23
X= 4 mod 7
By using Chinese Remainder Theorem:
M=23x7=161, M1=M/23=161/23=7, M2=M/7=161/7=23 M1-1=7-1 mod 23 =
723-2 mod 23 = 721 mod 23=10
M2-1=23-1 mod 7 = 237-2 mod 7 = 235 mod 7=4
X= (a1 x M1xM 1
-1+a2xM2xM -1) mod M
2
=( 1 x 7 x 10 + 4 x 23 x 4) mod 161 = 438 mod 161=116

Case 2:
By using (a1=1,b2=3) combinations with modulo (p=23,q=7), Let X is plain text: X = 1
mod 23
X= 3 mod 7
By using Chinese Remainder Theorem:
M=23x7=161, M1=M/23=161/23=7, M2=M/7=161/7=23 M1-1=7-1 mod 23 =
723-2 mod 23 = 721 mod 23=10
M2-1=23-1 mod 7 = 237-2 mod 7 = 235 mod 7=4
X= (a1 x M1xM 1
-1+a2xM2xM -1) mod M
2
=( 1 x 7 x 10 + 3 x 23 x 4) mod 161 = 346 mod 161=24
Case 3:
By using (a2=22,b1=4) combinations with modulo (p=23,q=7), Let X is plain text: X =
22 mod 23
X= 4 mod 7
By using Chinese Remainder Theorem:
M=23x7=161, M1=M/23=161/23=7, M2=M/7=161/7=23 M1-1=7-1 mod 23 =
723-2 mod 23 = 721 mod 23=10
M2-1=23-1 mod 7 = 237-2 mod 7 = 235 mod 7=4
X= (a1 x M1xM1
-1+a2xM2xM -1) mod M
2
=( 22 x 7 x 10 + 4 x 23 x 4) mod 161 = (1540+368) mod 161=137

Case 4:
By using (a2=22,b2=3) combinations with modulo (p=23,q=7), Let X is plain text: X =
22 mod 23
X= 4 mod 7
By using Chinese Remainder Theorem:
M=23x7=161, M1=M/23=161/23=7, M2=M/7=161/7=23 M1-1=7-1 mod 23 =
723-2 mod 23 = 721 mod 23=10
M2-1=23-1 mod 7 = 237-2 mod 7 = 235 mod 7=4
X= (a1 x M1xM1
-1+a2xM2xM -1) mod M
2
=( 22 x 7 x 10 + 3 x 23 x 4) mod 161 = (1540+276) mod 161=45
So, Finally from four cases: we got four plain text messages
Case 1: 116
Case 2: 24
Case 3: 137
Case 4: 45.
Only second answer(24) is Alice plain text, Bob needs to make a decision based on the
situation

Secure of the Rabin System:

The Rabin System is secure as long as p and q are large numbers