RAGHU ENGINEERING COLLEGE

(Autonomous)
Dakamarri, Visakhapatnam – 531162

Approved by AICTE
Accredited by NBA
Accredited by NAAC with 'A' Grade
Affiliated to JNTU-Kakinada

COMPUTER SCIENCE & ENGINEERING

IV B.Tech - I Semester
CRYPTOGRAPHY AND NETWORK SECURITY
 1

UNIT III: Number Theory & Asymmetric Key Cryptography

Asymmetric Encryption Mathematics of Asymmetric Key Cryptography,
Asymmetric Key Cryptography

Topics to be covered: Prime and relatively prime numbers, modular

arithmetic, Fermat’s theorems

Q1. What are prime numbers?

Prime numbers: To design a strong encryption algorithm, prime number plays a
very important role. A positive number which is greater than 1 and has no
factors other than 1 and that number itself is called a prime number. In other
words, the number which is divisible by 1 and the number itself is called a
prime number. Prime numbers are always positive integers. For example, 2,
3,5,7,11,13. These numbers have the factors as 1 and itself only. If we consider
number 14, the factors are 1, 2, 7, and 14. So 14 is not a prime number.
Positive integer numbers greater than 2 and not a prime numbers are called
composite numbers. The smallest prime numbers less than 50 are
2,3,5,7,11,13,17,19,23,29,31,37,41,43, and 47. The integer 1 is neither prime
nor composite. There is infinite number of prime numbers.

Q2. What are relative prime numbers and explain with suitable examples?
Relatively Prime Numbers: Two numbers are called relatively prime if the
greatest common divisor (GCD) of these numbers is 1. The numbers 8 and 15
are relatively prime number in respect to each other. The factors of 8 are
1,2,4,8 and the factors of 15 are 1, 3, 5, and 15.Examples of relative prime
numbers are (10, 21), (14, 15), (45, 91).
The greatest common divisor (GCD) of two numbers can be determined by
comparing their prime factors and selecting the least powers of the factor. For
example, two numbers are 81 and 99.
The factors of these numbers are
81= 1*9*9 = 1*3*3*3*3 = 1*34
99= 1*3*33 = 1*3*3*11 – 1* 32 *11
The GCD is the least power of a number in the factors,

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 2

So GCD (81, 99) = 32 = 9.

Example: GCD (300, 18) = 6
300= 22 x 31 x 52 and 18 = 21 x 32 and GCD (300,
18) = 21 x 31 x 50
Example: GCD (50, 24) = 2
50= 21 x 52 and 24 = 23 x 31 and 21 x 30 x 50 = 2
If the GCD of two numbers is 1, then those numbers are relatively prime
numbers. Therefore 81 and 99 are not relatively prime numbers.
For example, two relative prime numbers are 45 and 91.
45= 1 * 3 * 3 * 5 = 1 * 32 * 5
91 = 1 * 7 * 13
So GCD (45, 91) = 1.
Therefore, 45 and 91 are relatively prime numbers. It is not necessary that
both the numbers should be prime numbers. A prime number is also relatively
prime number to any other number other than itself and 1. Large prime
number provides more security in cryptography.
Q3. Discuss in detail about modular arithmetic?
Modular Arithmetic: We are familiar to find out the mod of any number with
some base. Suppose we have to find out the mod of a number m with base n as
m mod n
The mod with respect to n is (0,1,2,…..,,n-1).
Suppose m = 23 and n = 9, then
23 mod 9 = 5
For any value of m, the value of m mod 9 is from (0,1,2,….8).
If m is negative, suppose m= -15, then
-15 mod 9 = -6 mod 9
= (9-6) mod 9
= 3 mod 9

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 3

Properties:
1. Addition of modular numbers
The addition of two numbers p and q with same modular base n is
(p mod n + q mod n) mod n = ( p + q ) mod n
For example,
(15 mod 9) + (17 mod 9) = (15 mod 9 + 17 mod 9) mod 9
= ( 6 + 8 ) mod 9
= 14 mod 9 = 5
OR
15 mod 9 + 17 mod 9 = ( 15 + 17 ) mod 9
= (32) mod 9 = 5
2. Subtraction of modular number
The subtraction of two numbers p and q with same modular base n is
( p mod n – q mod n) mod n = (p – q) mod n
For example
17 mod 9 – 15 mod 9 = ( 17 mod 9 – 15 mod 9) mod 9
= ( 8 – 6) mod 9
= 2 mod 9 = 2
OR
15 mod 9 – 15 mod 9 = (17 – 15) mod 9
= 2 mod 9 = 2
3. Multiplication of modular number
The multiplication of two numbers p and q with same modular base n is
( p mod n * q mod n ) mod n = ( p * q ) mod n
For example
17 mod 9 * 15 mod 9 = (17 mod 9 * 15 mod 9) mod 9
= (8 * 6) mod 9
= 48 mod 9 = 3
OR
17 mod 9 * 15 mod 9 = (7 * 15) mod 9
= 255 mod 9 = 3
a pq
4. m mod n = m mod n where a = p*q
= (mp mod n)q mod n

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 4

Example: Find the value of 77 mod 9.

Soln: 77 mod 9 = (72)3 * 7 mod 9
= (72 mod 9)3 mod 9 * 7 mod 9
= ( 49 mod 9 )3 mod 9 * 7 mod 9
= ( 4 ) 3 mod 9 * 7 mod 9
= 64 mod 9 * 7 mod 9
= 1 * 7 mod 9 = 7 mod 9 = 7

Q4. Explain about Fermat’s theorem with suitable examples?

FERMAT’S THEOREM: Fermat’s theorem is one of the most important
theorems in cryptography. It is also known as Fermat’s Little theorem. It is
useful in public key encryption techniques and primality testing.
Fermat’s theorem states that if p is a prime number and n is a
positive integer number which is not divisible by p, then
np = n mod p
Therefore,
n p-1 = 1 mod p
n p-1 = 1 mod p
n p-1 mod p = 1
where p is prime and GCD (n,p) = 1
Fermat’s theorem np-1 = 1 mod p
The result is on factoring natural numbers into product of prime powers.
Example: n=7, p=19
72 49 (mod 19) = 11
74112 (mod 19) =121(mod 19) = 7 78 72
(mod 19) = 11
716112 (mod 19) =121(mod 19) = 7 71811 x 7(mod 19) =
77(mod 19) = 1
Example: n= 3 and p=5
329 (mod 5) = 4,
3442 (mod 5) = 16(mod 5) = 1
Another form of Fermat's theorem:
If n is any integer and p a prime number then,

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 5

np n (mod p).

Note that n and p need not be relatively prime.
Example: n= 3 and p=5
329 mod 5 = 4,
3442 mod 5 = 16 mod 5 = 1 and 351 x 3 mod 5 = 3 mod 5.
In this example n and p are relatively prime.
Example: n = 10 and p=5 (a and p are not relatively prime) 105 = 100000 mod 5
= 0 and
n mod p = 10 mod 5 = 0
Example: n= 6 and p=3 (a and p are not relatively prime)
63=216 mod 3 =0 and 6 mod 3=0
Class work:
1. What is the significance of prime numbers in cryptography?
Home work:
1. State and prove Fermat’s theorem.
Important and previous JNTUK examination questions:
1. What are the applications of prime numbers in cryptography? [8M][Set-3,
NOV - 2014]
2. Explain various logarithms used for modular arithmetic operations with
example. [8M][Set-2, Mar-2015]
3. Use Fermats theorem to find a number a between 0 and 72 with a congruent
to 9794 modulo 73 [8M][Set-3, Mar-2015]
4. Discuss the following with respect to prime numbers
i) Relatively prime numbers ii) Test for primality. [8M][Set-3, Mar-2015]

Topics to be covered: Euler Totient theorem, The Chinese Remainder

theorem

Q1. What is Euler Totient Function and give examples?

If consider arithmetic modulo n, then a reduced set of residues is a subset of

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 6

the complete set of residues modulo n which are relatively prime to n

 e.g. for n=10,
 the complete set of residues is {0,1,2,3,4,5,6,7,8,9}
 the reduced set of residues is {1,3,7,9}
The number of elements in the reduced set of residues is called the Euler
Totient function (n).
Example: n=37 (prime number). As n is prime all numbers less than n (36 in
number) are prime to n thus  (37) = 36. For any prime p,  (p) = p-1
Example: 35) = 24. The numbers less than 35 and prime to 35 are 1, 2, 3, 4,
6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34 and there
are 24 numbers in this list.
If n= p × q (p, q are primes) then  (n) =  (p) ×  (q) = (p-1) × (q-1)
Example:  (21) = 12 [numbers less than 21 and prime to 21 are 1, 2,
4, 5, 8, 10, 11, 13, 16, 17, 19, 20
Alternatively, 21 = 3 × 7 and 3) = 2,  (7) = 6. Thus  (21) =  (3) × (7) = 2 x 6
=12.

Q2. Explain about Euler's Theorem with suitable examples?

Let gcd(a,n)=1 then
o a (n) mod n = 1
o Proof: consider all reduced residues xi
o Then axi also form reduced residues set
o Using  axi =  xi mod n and  xi has inverse
Compute  (n)
o If factoring of n is known
  (n)=n  (1-1/pi) where pi is its prime factor
o Otherwise
 It is expensive!
Euler’s theorem for every a and n that are relatively prime, a (n)1 mod n.
Example : Let a=3, n=10; (10) = 4, 34 =81 1 mod 10
Example: Let a=2, n=11; 11) = 10, a (n) = 210 = 1024 1 mod 11
Alternative form of this theorem is as follows: For any two integers a,

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 7

n we have a (n)+1≡a mod n. ( a and n need not be relatively prime)

Example: Let a=3, n=10;  (10) = 4, a (n)+1= 35 = 243 3 mod 10 = a mod n
In this example a and n are relatively prime.
Example: a=3, n=6; (6)=2, an)+1= 33 = 27 3 mod 6 = a mod n
In this example a and n are not relatively prime.
Example Find the last digit of 555.
We first note that finding the last digit of 555 can be obtained by reducing 555
(mod 10), that is evaluating 555(mod10). We note that (10, 55) = 5, and hence
this pair is not relatively prime, however, we know that 55 has a prime power
decomposition of 55 = 5 x 11. (11, 10) = 1, hence it follows that
11ϕ(10)≡1(mod10). We note that ϕ(10)=4. Hence 114≡1(mod10), and more
appropriately:
555=55⋅115=55⋅114⋅11≡512⋅(11)4⋅11≡34375≡5(mod10)
Hence the last digit of 555 is 5.

Q3. What is Linear Congruence Theorem?

An integer a is invertible modulo n if and only if gcd(a,n)=1 ("invertible" means
there's some a−1 such that aa−1≡1modn). This is the Linear Congruence
Theorem.

Q4. State and prove Chinese Reminder Theorem?

The Chinese Reminder Theorem is an ancient but important calculation
algorithm in modular arithmetic. The Chinese Remainder Theorem enables one
to solve simultaneous equations with respect to different moduli in
considerable generality.
Theorem (Chinese Remainder Theorem). Let m1; : : : ; mk be pairwise relatively
prime positive integers (gcd(mi; mj ) = 1) whenever i not equal to j. Let m be the
product m = m1m2 mk. Let a1; : : : ; ak be integers. Consider the system of
congruences:
x a1 (mod m1)
x a2 (mod m2)
:::

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 8

x ak (mod mk):
Then there exists exactly one x  Zm satisfying this system.

Proof that a solution exists: To keep the notation simpler, we will assume k =
4. Note the proof is constructive, i.e., it shows us how to actually construct a
solution.
Our simultaneous congruences are
x ≡a1 (mod m1), x ≡a2 (mod m2), x≡a3 (mod m3), x≡a4 (mod m4). Our goal is
to find integers w1, w2, w3, w4 such that:

Once we have found w1, w2, w3, w4, it is easy to construct x: x = a1w1
+ a2w2 + a3w3 + a4w4.
Moreover, as long as the moduli (m1, m2, m3, m 4) remain the same, we can use
the same w1, w2, w3, w4 with any a1, a2, a3, a4.
First define: z1 = m / m1 = m2m3m4 z2 = m / m2 = m1m3m4, z3 = m / m3 =
m1m2m4 z4 = m / m4 = m1m2m3
Note that
i) z1≡0 (mod mj) for j = 2, 3, 4.
ii) gcd( z1, m1) = 1. (If a prime p dividing m1 also divides
and likewise for z2, z3, z4. z1= m2m3m4, then p divides m2, m3, or m4.)
Next define: y1 ≡z1–1 (mod m1)
y2 ≡z2–1 (mod m2) y3≡z3–1 (mod m3) y4≡z4–1 (modm4)
The inverses exist by (ii) above, and we can find them by Euclid’s extended
algorithm. Note that
iii) y1z1≡ 0 (mod mj) for j = 2, 3, 4. (Recall z1 ≡0 (mod mj) ) iv) y1z1≡1 (mod m1)
and likewise for y2z2, y3z3, y4z4.
Lastly define: w1 ≡y1z1 (mod m) w2≡y2z2 (mod m)

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 9

w3≡y3z3 (mod m) w4 ≡y4z4 (mod m)

Then w1, w2, w 3, and w4 have the properties in the table.
Example: There are certain things whose number is unknown. Repeatedly
divided by 3, the remainder is 2; by 5 the remainder is 3, and b7 7 the
remainder is 2. What will be the number?
x = 70(2) + 21(3) + 15(2) (mod 105)
= 140 + 63 + 30 (mod 105)
= 233 (mod 105)
= 23 (mod 105)
Example:
x= 1 (mod 2) m1 = 105 (mod 210) = 1 (mod 2) y1 = 1
x= 2 (mod 3) m2 = 70 (mod 210) = 1 (mod 3) y2 = 1
x= 3 (mod 5) m3 = 42 (mod 210) = 2 (mod 5) y3 = 1
x= 4 (mod 7) m4 = 30 (mod 210) = 2 (mod 7) y4 = 4
x = (1)(105)(1) + (2)(70)(1) + (3)(42)(3) + (4)(30)(4) (mod 210)
= 53 (mod 210)

Q5. Solve the simultaneous congruence for the following:

x ≡6 (mod 11), x ≡13 (mod 16), x ≡9 (mod 21), x ≡19 (mod 25).
Solution: Since 11,16,21, and 25 are pair wise relatively prime, the Chinese
Remainder Theorem tells us that there is a unique solution modulo m, where m
= 11*16*21*25-92400.

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 10

Q5. What is a Primitive Root?

Order of integer: The order of modulo n is the smallest positive k such that
ak ≡ 1 mod n
 Integer a is a primitive root of n if the order of a modulo n is (n)
 Not all integers have primitive root
 Example n = pq for primes p and q
 Prime p has (p -1) primitive roots
Class work:
1. Give any one example for Chinese remainder theorem?
Home work:
1.What is importance Chinese Remainder Theorem in cryptography? Explain.
Important and previous JNTUK examination questions:
1. State and prove Euler’s theorem? [8M][Set-3, NOV - 2014]
2. Define Euler Totient functions Determine (27) and (35)? [8M][Set-1, Dec-
2014]
3. State and prove Chinese remainder theorem. [8M][Set-2, Dec-2014]

Topic to be covered: Discrete Logarithms, Principles, public key cryptography

algorithms

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 11

Q 1. How to represent discrete logarithms with suitable example?

The Discrete logarithm is fundamental to many public key encoding systems
including Diffei-Hellman key exchange algorithms and digital signatures.
The inverse problem to exponentiation is to find the discrete logarithm of a
number modulo p
 That is to find I such that b = a i (mod p)
 This is written as i = dlog a b (mod p)
 If a is a primitive root then it always exists, otherwise it may not
 For example. x = log 3 4 mod 13 has no answer
x = log 2 3 mod 13 = 4 by trying successive powers
 Whilst exponentiation is relatively easy, finding discrete logarithms is
generally a hard
problem
 The least positive integer m which satisfies the equation am = 1 mod n is
called (i)
order of a mod n (ii) exponent to which a belongs to mod n (iii) length of the
period
generated by a
Example:

Q2. How do you Calculate discrete logarithms?

Consider the equation y=gx mod p. Given g, x and p it is straight
forward to calculate y. We can multiply g with itself x times or find
modulo at in between steps and find y. However given y, g, p it is
difficult to find x (dlog). This is as difficult as factoring a large

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 12

number into product of primes.

Q3. Explain about Public Key Cryptography?

Asymmetric algorithms rely on one key for encryption and a different but
related key for decryption. These algorithms have the following important
characteristics.
1. It is computationally infeasible to determine the decryption key given only
knowledge of the cryptographic algorithm and the encryption key. In
addition, some algorithms, such as RSA, also exhibit the following
characteristic.
2. Either of the two related keys can be used for encryption, with the other
used for decryption.

Q4. What are the Principles of Public key Cryptosystem?

The principles of the public key cryptography are:
 Public-key cryptography is also known as asymmetric-key cryptography.
 The concept was proposed in 1976 by diffie and Hellman
 In a Public-key cryptography each end system in a network generates a pair of
keys to be used one for encryption another one for decryption. The two keys
in such a key pair are referred to as the public key and the private key.
 In a Public-key cryptography in the two keys each system publishes one key,
called public key and another key kept secret for decryption that key is called
private key.
 Public key algorithms are used for message authentication, confidentiality,
digital signature and key distribution
 Public key algorithms are based on mathematical functions
 In a public key cryptography both key are different and any key could not
derived from other.
 Asymmetric algorithms rely on one key for encryption and a different but
related
 key for decryption.
 These algorithms have the following important characteristic.

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 13

 It is computationally infeasible to determine the decryption key given only

knowledge of the
cryptographic algorithm and the encryption key.
 In addition, some algorithms, such as RSA, also exhibit the following
characteristic.
Either of the two related keys can be used for encryption, with the other
used for decryption.

Q5. Explain about public key encryption and decryption algorithms?

A public-key encryption as shown in figure 1.

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. This encrypts plain text using public key of
receiver (as in figure 1) or using private key of the sender (as in figure 2)
3. Public and private keys: This is a pair of keys that have been selected so

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 14

that if one is used for encryption, the other is used for decryption. The
exact transformations performed by the algorithm depend on the public or
private key that is provided as input. In figure 1, encryption is done using
public key and decryption using private key, whereas in figure 2, encryption
is done using private key and decryption using public key.
4. Cipher text: 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 cipher texts.
5. Decryption algorithm: This algorithm accepts the cipher text and the
matching key and produces the original plaintext. In figure 1, decryption
algorithm uses private key, whereas in figure 2, decryption is done using
public key.
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 figures 1 and 2 suggest, 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 (figure.1).Or Bob uses his
private key to encrypt the plain text (figure 2).
4. When Alice receives the message, she decrypts it using her private key (figure
1). No other recipient can decrypt the message because only Alice knows
Alice’s private key. Or Alice uses public key of Bob (figure 2). With this
approach, all participants have access to public keys, and private keys are
generated locally by each participant and therefore they never be distributed.
As long as a user’s private key remains protected and secret, incoming
communication is secure. At any time, a system can change its private key and
publish the companion public key to replace its old public key.

Q.6 Differentiate the characteristics between conventional and public key

systems.

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 15

Table summarizes the important characteristics of symmetric and asymmetric

cryptosystems. To discriminate between the two, we refer to the key used in
symmetric encryption as a secret key. The two keys used for asymmetric
encryption are referred to as the public key and the private key. Invariably, the

Private Key is kept secret, but it is referred to as a private key rather

than a secret key to avoid confusion with symmetric encryption.

Class work:
1. Explain about public key encryption and decryption algorithms.
Home work:
1. Differentiate Conventional encryption and public key encryption

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 16

Important and previous JNTUK examination questions:

1. Compare symmetric encryption algorithms with public key algorithms. [8M]
[Set-1, Nov - 2014]
2. What is importance of discrete logarithms in cryptography? [8M][Set-1, Dec-
2015]
3. Discuss various principles of public key crypto Systems. [8M][Set-2,
Mar-2015]

Topics to be covered: Public key forms of encryption and

applications

Q1. Write an essay on different forms of public key encryption?

Public key encryption can offer confidentiality or sender
authentication or both, depending on keys used for
encryption/decryption. Figures 3, 4 and 5 show all the three forms of
encryption.
With the message X and the encryption key PUb as input, A forms the
cipher text Y = E(PUb, X). The intended receiver, in possession of the matching
private key, is able to invert the transformation as X = D(PRb, Y). An adversary,
observing Y and having access to PUb, but not having access to PRb or X, must
attempt to recover X and/or PRb. It is assumed that the adversary does have
knowledge of the encryption (E) and decryption (D) algorithms. If the adversary
is interested only in this particular message, then the focus of effort is to
recover X by generating a plaintext estimate X ˆ.Often, however, the adversary
is interested in being able to read future messages as well, in which case an
attempt is made to recover PRb by generating an estimate PRb ˆ.

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 17

The scheme illustrated in Figure 3 provides confidentiality, Figures 2 and 4

show the use of public-key encryption to provide authentication. Here cipher text
is generated using Y = E(PRa, X) and plain is recovered using X = D(PUa, Y).
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.
In addition, 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.
In the preceding scheme, the entire message is encrypted, which, although
validating both author and contents, requires a great deal of storage. Each
document must be kept in plaintext to be used for practical purposes. A copy also
must be stored in cipher text so that the origin and contents can be verified in
case of a dispute. A more efficient way of achieving the same results is to encrypt
a small block of bits that is a function of the document. Such a block, called an
authenticator, must have the property that it is infeasible to change the
document without changing the authenticator. If the authenticator is encrypted
with the sender’s private key, it serves as a signature that verifies origin, content,
and sequencing.

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 18

It is, however, possible to provide both the authentication function and

confidentiality by a double use of the public-key scheme as in figure 5. The cipher
text is produced by double encryption as Z = E(PUb, E(PRa, X)) and plain text is
recovered using double decryption in the reverse order of encryption as X =
D(PUa, D(PRb, Z)).

In this case, we begin as before by encrypting a message, using the sender’s

private key. This provides the digital signature, next, we encrypt again, using the
receiver’s public key. The final cipher text can be decrypted only by the intended
receiver, who alone has the matching private key. Thus, confidentiality is
provided. The disadvantage of this approach is that the public-key algorithm,
which is complex, must be exercised four times rather than two in each
communication.

Q2. Write the applications for Public Key Cryptosystems?

The applications of the public key cryptosystems are:
i. Encryption/Decryption
ii. Authentication/ Digital signature

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 19

iii. Key exchange

iv. Time stamping
v. Electronic money
The public key system is characterized by the use of a cryptographic type of
algorithm with two keys, one is public key and other is private key. Depending
on the application, sender uses either the sender’s private key or the receiver’s
public key, or both, to perform some type of cryptographic function.
i. Encryption/Decryption
The sender encrypts a message with the recipient’s public key. For example in
disk encryption programs encrypt your entire hard disk so that you don't have
to worry about unencrypted data on your disk.
Pretty Good Privacy is a software package originally developed by Phil
Zimmerman. This software package provides encryption and authentication for
e-mail and file storage applications. Zimmerman developed his freeware
program using existing encryption techniques. It runs on multiple platforms. It
provides message encryption, digital signatures, data compression, and e-mail
compatibility. PGP uses the user's private key and user-supplied password to
encrypt the file using IDEA. The receiver use same password and key to unlock
the file.
ii. Authentication/Digital signature
Authentication and digital signatures are a very important application of public-
key cryptography in which sender “signs” a message with its private key. For
example, if you receive a message from me that I have encrypted with my
private key and you decrypt it using my public key, you should feel that the
message did come from me. If I think that it necessary to keep the message
secret, I may encrypt the message with my private key and then with your
public key, that way only you can read the message, and you will know that the
message came from me. The only requirement is that public keys are
associated with their users by a trusted manner, for example a trusted
directory. Due to this weakness, the standards community has used an object
called a certificate. It contains, the certificate issuer's name, the subject name
for which the certificate is being issued, the public key of the subject, and some
time stamps. The public key is good, because the certificate issuer has a

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 20

certificate too.
iii. Key exchange
We can use Asymmetric Key Cryptography for Key exchange. I.e. the session
key can be transmitted using Asymmetric Key Cryptography.
iv. Time Stamping
Time stamping is a technique that can certify that a certain electronic
document was delivered at a certain time. Time stamping uses the blind
signature scheme encryption model. Blind signature schemes allow the sender
to get a message receipted by another party without revealing any information
about the message to the other party.
Time stamping is working alike to sending a registered letter through the
ordinary mail, but with additional level of proof etc recipient received a specific
document. Following applications include patent applications, copyright
archives, and contracts.
v. Electronic Money
Electronic money is also called electronic cash or digital cash. It is still evolving.
The transaction carried out electronically with a net transfer of funds from one
party to another. It may be either debit or credit and can be either anonymous
or identified. Anonymous applications work on blind signature schemes.
Anonymous schemes are the electronic analog of cash, while identified
schemes are the electronic analog of a debit or credit card.
Encryption is used for conventional transaction data in electronic money
schemes like account numbers and transaction amounts. Digital signatures can
replace handwritten signatures and public-key encryption can provide
confidentiality. There are several systems of this range of applications, from
transactions mimicking conventional paper transactions with values of several
dollars and up. The various micropayment schemes that consignment
extremely low cost transactions into amounts that will bear the overhead of
encryption and clearing the bank.

Q3. What are the requirements of Public Key Cryptosystem?

The requirements of the public key cryptosystem are:
1. It is computationally easy for a party B to generate a pair (public key PUb,

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 21

private key PRb).

2. It is computationally easy for a sender A, knowing the public key and the
message to be encrypted, M, to generate the corresponding cipher text: C =
E(PUb, M)
3. It is computationally easy for the receiver B to decrypt the resulting cipher
text using the private key to recover the original message: M = D(PRb, C) =
D[PRb, E(PUb, M)]
4. It is computationally infeasible for an adversary, knowing the public key,
PUb, to determine the private key, PRb.
5. It is computationally infeasible for an adversary, knowing the public key,
PUb, and a cipher text, C, to recover the original message, M.
6. The two keys can be applied in either order: M = D[PUb, E(PRb,M)] = D[PRb,
E(PUb, M)]. This condition is not for all public key applications.
These are formidable requirements, as evidenced by the fact that only a few
algorithms (RSA, elliptic curve cryptography, Diffie-Hellman, DSS) have received
widespread acceptance in the several decades since the concept of public-key
cryptography was proposed.
Class work:
1. What are the applications of Asymmetric key cryptography?
Home work:
1. What are the requirements of Public Key Cryptosystem?
Important and previous JNTUK examination questions:
1. Discuss various principles of public key crypto Systems. [8M][Set-2, Mar -
2015]

Topic to be covered: The RSA algorithm

Q1. What is RSA?

RSA is a cryptosystem or means of transporting information in a secure and
encrypted way.
It is based on the principles of public key cryptography. I.e. it uses two keys:

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 22

Public Key and Private Key. Everyone which is involved in communication

generates two keys. One key (Public Key) is sent to other parties involved in
communication public and the other key is kept secret. If someone wants to
send you an encrypted message, he must know your public key. He/She takes
your public key, encrypts the message with it and then sends it to you. Unless
someone is able to factor 128-bit numbers in less than 100 years, your message
is relatively safe. After receiving the message, you decrypt the message using
your private key. Someone else holding your public key will not be able to
decrypt your message

Q2. Discuss about RSA Algorithm?

The RSA Algorithm was invented by Rivest, Shamir & Adleman of MIT in
1977. It is the best known & widely used public-key scheme. The details of the
algorithm are as follows:
Key Generation
The first step of RSA Algorithm is key generation. Each user that wishes to
communicate must generate a public-private key pair. The following are the
steps used for key generation.

1. Choose two large prime numbers p and q such that p!=q

2. Find the product of p and q is assign to n and m<n (m is a plain text). Where n
is the modulus that is made public. The length of n is considered as the RSA key
length.
n=p*q (and m<n )
3. Compute the ᵩ(n) value is the product of (p-1) and (q-1)
ᵩ(n)=(p-1) * (q-1)
4. Choose a random number ‘e’ in as a public key in the range 0<e <ᵩ(n) and
relatively prime to ᵩ(n) (two numbers are said to be relative prime numbers if
there have no common factor except1)
gcd ( e, ᵩ(n))= 1 and 0<e<ᵩ(n) The letter e is public key is the value is used
in encryption
5. Find private key d such that d*e mod ᵩ(n)=1 is exactly divisible by ᵩ(n).

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 23

The letter d is private key , this value will be used in decryption.

6. Finally return the public key and key length {e , n } to the sender and the
private key and key length {d , n} for own purpose.
Figure shows Encryption, decryption, and key generation in RSA

Encryption algorithm:
 Consider the device A that needs to send a message to B securely.
 A can be use algorithm to encrypt the plaintext (m) message into ciphertext
(C) message
In encryption the size of the plaintext (m) message must be less than n, which
means that if the size of the plaintext is longer than n, it should be dived into
blocks.
Let e be B’s public key. Since e is public, A has access to e for encrypt the
message.
Calculate the ciphertext C
Cipher text C = me mod n, where n is the moduls. Where m is a
plaintext and e is public key .Return the ciphertext C.

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 24

Decryption algorithm:
 B can be use algorithm to decrypt the ciphertext (C ) message into plainyext
(m).
 The size of the ciphertext is always less than then n
 Let C be the cipher text received from A.
 Calculate plaintext Message m = Cd mod n, where d is B’s private key and n
is the modulus.
 Return the plaintext m.

Q3. Give any one numerical example of RSA?

Here is an example of RSA Algorithm.
perform Encryption and decryption using RSA when p=3,q=11,e=7,m=5
Where p=3,q=11
n=p*q=3*11=33
ᵩ(n)=(p-1)*(q-1)=(3-1)*(11-1)=2*10=20
e=7
d*e mod ᵩ(n)=1 d*7 mod 20=1 3*7 mod 20=1 so d=3
public key(e,n)=(7,33) private key(d,n)=(3,33)
Encryption alg:
c=me mod n
=57 mod 33
=78125 mod 33=14
Decryption alg:
M=cd mod n
=143 mod 33
=2744 mod 33= 5

Q4. Explain different attacks of RSA algorithm?

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 25

Three possible attacks of the RSA algorithm are:

i. Brute force attack
ii. Mathematical attacks
iii. Timing attacks
i. Brute force attack
A brute force attack involves of trying every possible code, combination, or
password until you find the right one. Brute force attack is not an easy method.
Following factors determining the difficulty of a Brute force attack:
1. How long can the key be?
2. How many possible values can each component of the key have?
3. How long will it take to attempt each key?
4. Is there a mechanism which will lock the attacker out after a number of
failed attempts?
We explain it with example if a system which only allows 4 digits PIN codes.
This means there are a maximum of 1000 possible PIN combinations. PIN
security could be increased by increasing the length of the PIN, allowing the PIN
to contain characters other than numbers, such as * or #, imposing a 30 second
delay between failed authentication attempts and locking the account after 5
failed authentication attempts. A brute force attack will always succeed,
eventually but brute force attacks against systems with sufficiently long key
sizes may require billions of years to complete.
ii. Mathematical attacks
There are several approaches, all equivalent in effect to factoring the product
of two primes. The security of RSA depends of factoring being difficult. There
are several methods to try factoring, but as long as the keys are long enough
there is small risk of having your RSA encoded message broken. 256 bits can be
broken relatively easily, 512 bits is probably insecure and breakable by major
governments, 1024 bits should be secure for decades according to today's
information. 2048 bits will most probably remain safe for a long time.
iii. Timing attacks
These depend on the running time of the decryption algorithm. The way to
break RSA is to find a technique to compute e th roots mod n. Since c = m^e, the
eth root of c is the message m. This attack would allow someone to recover

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 26

encrypted messages and forge signatures even without knowing the private
key. This attack is not known to be equivalent to factoring. No methods are
currently known that attempt to break RSA in this way.
Public Key Cryptography solves the problem of Key Distribution and verification
of Messages from the sender which exists in Symmetric Key Ciphers. But the
most of the algorithms (e.g. RSA) are slow as compared to DES and other
Symmetric Ciphers. Thus Public Key Cryptography is most suitable for
transmission of smaller messages (e.g. exchange of Session Keys).
Class work:
1. Explain the RSA algorithm. Compute cipher text for M=88, p=17 and q=11.
Home work:
1. Explain RSA algorithm with an example.
Important and previous JNTUK examination questions:
1. Explain RSA algorithm [8M][Set-1, NOV - 2014]
2. In public key system using RSA, you intercept the cipher text C=10 sent to user
whose public key is e=5, n=35. What is the plaintext M? [8M][Set-3, Dec-2014]
3. In detail explain different possible approaches for attacking RSA algorithm [8M]
[Set-3, Mar-2015]

Topic to be covered: Diffie Hellman Key Exchange

Q1. Explain about Diffie Hellman Key Exchange with suitable example?
 Diffie-Hellman Key Exchange is the first Public Key Algorithm published by
Whitefield diffie and martin Hellman in 1976.
 It is a first published public key agreement algorithm, it is used in many
commercial products
 Diffie-Hellman is a key agreement algorithm that helps two devices to agree
on a shared secret between them with out the need to exchange any
secret/private information.

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 27

 It is a Public Key Algorithm Only for Key Exchange, it Does NOT Encrypt or
Decrypt
 The DH standard is specified RFC 2631.
 In this Diffie-Hellman is a key agreement algorithm the two parties create a
symmetric session key with out need of KDC. Thus allows two parties that
have prior knowledge of each other to jointly establish a shared secret key
over an insecure communication channel.
 Diffie-Hellman key agreement is widely used in Security Protocols (used in
the IKE component of theIPSec protocol suite), for securing internet
protocol communications.

Key agreement:
 For establishing shared secret between two devices A and B, both devices
(parties) agree on large public constants p and g. Where p is a prime
number and g is the generator less than p. these two do not need to be
confidential they can be sent through the internet, they can be public.
1) A chooses a large random X, such that 0<= X <= p-1 and calculates R1 = gx
mod p
2) Next the A sends R1 to B. note that A does not send the value of X, it sends
only the R1.
3) B choose another large random number Y, such that 0<= Y <= p-1 and
calculates
R2 = gy mod p.
4) Now the B sends R2 to A. note that B does not send the value of Y, it sends
only the R2.
5) next The end A computes the K value.

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 28

where K= (R2 )x mod P = (gy mod p)x mod P that is equal to gyx mod p.
6) next The end B computes the K value.where K= (R1 )y mod P = (gx mod p)y mod
p that is equal to gxy mod p. Now the A and B have shared same key values
( K ),because
gxy mod p= gyx mod p.( note that the x and y are kept secret). Means
now the key k is created and distributed in to both ends.

Example
A and B agree to use a prime number p=23 and base g=5.
1) A chooses a secret integer x=6 and calculated R1 = gx mod p = 56 mod 23
= 15625 mod 23=8.
2) next A sends R1 = 8 to B. note that A does not send the value of X, it sends
only the R1.
3) B chooses a secret integer y=15, then calculated R2 = gy mod p = 515 mod 23
= 30517578125mod 23 = 19.
4) next B sends R2 = 19 to A. note that B does not send the value of Y, it sends
only the R2.
5) A calculate key K value where K= (R2 )x mod P.
K= 196 mod 23 = 47045881 mod23 =2
6) B calculate key K value where K= (R1 )y mod P.
K= 815 mod 23 =35184372088832 mod 23=2
Now the A and B have shared same key values ( K ),
because gxy mod p= gyx mod p.( note that the x and y are kept secret). Means
now the key k is created and distributed in to both ends
Man-in-middle-attack:
 The above method has another weakness. The unauthorized entity does
not have to find the vale of X and Y to attack the protocol. Unauthorized
entity can fool A and B be creating two keys:
One between herself and A, and another between herself and B
1) A choose X, calculate R1 = gx mod p and sends R1 to B.
2) An unauthorized entity, intercepts R1, she choose z, calculates R3 = g z mod p,
and sends R3 to A .
R1 is intercepted by unauthorized entity and never reach to B.

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 29

3) A and unauthorized entity calculate K1= (g ) xy mod P. K1 become a shared key

between A and unauthorized entity
4) However an unauthorized entity creates a bogus key K2 between herself and
B.
Finally an unauthorized entity disturbs key distribution between A and B.

Class work:
1. Give any one example for Diffie-Hellman Key exchange?
Home work:
1. Discuss Diffie –Hellman Key exchange protocols in detail
Important and previous JNTUK examination questions:
1. Explain Diffie- Hellman key exchange algorithm. [8M][Set-3, NOV - 2014]

Topics to be covered: Elgamal encryption & decryption, Elliptic Curve

Cryptography

Q1. Explain about Elgamal encryption & decryption with suitable examples?
In 1984, T. Elgamal announced a public-key scheme based on discrete logarithms,
closely related to the Diffie-Hellman technique. The ElGamal cryptosystem is
used in some form in a number of standards including the digital signature
standard (DSS).
 El_Gamal is a public-key cryptosystem technique was designed by Dr.
Taher Elgamal.
 El_Gamal depends on the one way function, means that the encryption
and decryption are done in separate functions.
The encryption process requires two modular exponentiations (extra time).
A disadvantage of El_Gamal encryption is that there is message expansion
by a factor of 2. That is, the ciphertext is twice as long as the corresponding
plaintext.
 Receiver A must do the following:

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 30

1- Generate a large random prime number (p)

2- Choose a generator number (a) {show in slide 7 }
3- Choose an integer (x) less than (p-2) , as secret number.
4-Compute (d) where d= ax mod p
5- Determine the public key (p, a, d) and the private key (x)
 Example : let p = 11 and a = 2 and x = 5
calculate d = 25 mod 11 = 10
public key = (11 ,2 ,10)
private key = (5)
 How to test (a) generator or not :
1- (a) must be between 1 and p-1
2- Find Ø = p-1
3- Find the all factors of Ø {f1,f2,….,fn} – { 1 }
4- Find {q1,q2,…..,qn} where
qi = fi
for the redundant factors
qi = fifreq
5- (a) generator number if and only if
wi= a Ø/qi mode p <> 1 , for all qi
 Example 1 : let p= 11 , a=2 ,test a is generator number or not ?
sol:
Ø= p-1 = 10 , factors of 10 = {2 , 5}
q1 = 2 ,q2 = 5
w1 = 210/2 mod 11 = 10 <> 1
w2 = 210/5 mod 11 = 4 <> 1
i.e a generator number .
 Example 2 : let p= 11 , a=3 ,test a is generator number or not ?
sol: Ø= p-1 = 10 , factors of 10 = {2 , 5}
q1 = 2 ,q2 = 5
w1 = 310/2 mod 11 = 1== 1
w2 = 310/5 mod 11 = 9 <> 1
i.e a not generator number .
 Example 3 : let p= 41 , a=2 ,test a is generator number or not ?

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 31

sol:
Ø= p-1 = 40 , factors of 40 = {2 , 2 , 2, 5}
q1 = 21 = 2 ,q2 = 22 = 4,q3 = 23 = 8
q4 = 5
w1 = 240/2 mod 41 = 0.98 <> 1
w2 = 240/4 mod 41 = 40 <> 1
w2 = 240/8 mod 41 = 32 <> 1
w2 = 240/5 mod 41 = 10 <> 1
i.e a generator number
Encryption:
 Sender B must do the following :
1- Obtain the public key (p , a , d ) from
the receiver A.
2- Choose an integer k such that :
1 < k < p-2
3- Represent the plaintext as an integer m where 0 < m < p-1
4- compute (y) as follows :
y = ak mod p
5- compute (z) as follows :
z = (dk * m ) mod p
6- Find the ciphertext (C) as follows :
C= ( y , z )
7- The sender B send C to The receiver A .
Decryption:
 Receiver A must do the following :
1- Obtain the ciphertext (C) from B .
2- compute (r) as follows :
r = yp-1-x mod p
3- Recover the plaintext as follows:
m = ( r * z ) mod p
Example:
Let p = 11 and a generator number = 2
and select integer number x = 5

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 32

calculate d = 25 mod 11 = 10
Then
public key = ( 11 , 2 , 10)
private key = (5)
Plaintext = Age
Represent the plaintext as integer value as follows:
The new plaintext = ( 1 7 5 )
Encryption (sender):
y = ak mod p , z = (dk * m ) mod p
Choose an random integer value k = 6
yA = 26 mod 11 = 9
zA = (106*1) mod 11 = 1
Choose an random integer value k = 4
yg = 24 mod 11 = 5
zg = (104*7) mod 11 = 7
Choose an random integer value k = 7
ye = 27 mod 11 = 7
ze = (107*5) mod 11 = 6
Ciphertext = (9,1) (5,7) (7,6)
The sender B send the ciphertext to the receiver A.
The receiver decrypt the ciphertext as follows :
Compute (r) and (m) where
r = yp-1-x mod p , m = ( r * z ) mod p

r1= 911-1-5 mod 11 = 1

m1= (1*1) mod 11= 1
r1= 511-1-5 mod 11 = 1
m2 = ( 1 * 7 ) mod 11 = 7
r1= 711-1-5 mod 11 = 10
m3 = ( 10 * 6 ) mod 11 = 5
The receiver find the plaintext ( 1 7 5 )
Convert the plaintext to letters = Age

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 33

Q2. Explain about Elliptic Curve Cryptography?

 Elliptic curves are rich mathematical structures that have shown usefulness
in many different types of applications. An Elliptic Curve Cryptosystem
(ECC) provides much of the same functionality that RSA provides: digital
signatures, secure key distribution, and encryption. One differing factor is
ECC’s efficiency. Some devices have limited processing capacity, storage,
power supply, and bandwidth like the newer wireless devices and cellular
telephones. With these types of devices, efficiency of resource use is very
important.
 ECC provides encryption functionality requiring a smaller percentage of the
resources required by RSA and other algorithms, so it is used in these types
of devices. In most cases, the longer the key length, the more protection
that is provided, but ECC can provide the same level of protection with a
key size that is smaller than what RSA requires.
 Because longer keys require more resources to perform mathematical
tasks, the smaller keys used in ECC require fewer resources of the device.
ECC cryptosystems use the properties of elliptic curves in their public key
systems. The elliptic curves provide ways of constructing groups of
elements and specific rules of how the elements within these groups
combine. The properties between the groups are used to build
cryptographic algorithms.
 The principal attraction of ECC, compared to RSA, is that it appears to offer
equal security for a far smaller key size, thereby reducing processing
overhead. On the other hand, although the theory of ECC has been around
for some time.
 it is only recently that products have begun to appear and that there has
been sustained cryptanalytic interest in probing for weaknesses.
Accordingly, the confidence level in ECC is not yet as high as that in RSA.
 ECC is fundamentally more difficult to explain than either RSA or Diffie-
Hellman, and a full mathematical description is beyond the scope of this
book. This section and the next give some background on elliptic curves and
ECC.

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III
 34

Q3. Explain about Elliptic Curve Encryption/Decryption?

 Several approaches to encryption/decryption using elliptic curves have
been analyzed in the literature. In this subsection, we look at perhaps the
simplest.
 The first task in this system is to encode the plaintext message to be sent as
an – point. It is the point that will be encrypted as a ciphertext and
subsequently decrypted.
 Note that we cannot simply encode the message as the or coordinate of a
point.
 As with the key exchange system, an encryption/decryption system requires
a point and an elliptic group as parameters.
 Each user A selects a private key nA and generates a public key PA = nA * G.
 To encrypt and send a message to B, A chooses a random positive integer
and produces the ciphertext consisting of the pair of points.
 Note that A has used B’s public key . To decrypt the ciphertext, B multiplies
the first point in the pair by B’s secret key and subtracts the result from the
second point.
Class work:
1. Give any one example for Elgamal encryption & decryption?
Home work:
1. Explain about Elgamal encryption & decryption with suitable examples?
Important and previous JNTUK examination questions:
1. Discuss the following related to Elliptic Curve Cryptography (ECC) [8M][Set-2,
Mar - 2015]
a) ECC Encryption / Decryption and Security of ECC
b) ECC Diffie Hellman Key Exchange

Raghu Engineering College Dept. of CSE Cryptography and Network Security Unit III