Cryptography and Network Security B.

Tech(CSE) III Year II Sem

UNIT III
Asymmetric Encryption
Mathematics of Asymmetric Key Cryptography, Asymmetric Key Cryptography

Primes and Related Congruence Equations

PRIMES
Asymmetric-key cryptography uses prime numbers extensively.
A prime is divisible only by itself and 1.

Figure Three groups of positive integers

Example 1:
What is the smallest prime?
The smallest prime is 2, which is divisible by 2 (itself) and 1.
Example 2:
List the primes smaller than 10.
There are four primes less than 10: 2, 3, 5, and 7. It is interesting to note that the percentage of primes
in the range 1 to 10 is 40%. The percentage decreases as the range increases.
Cardinality of Primes
We can use infinite Number of Primes.
Number of Primes
is the number of primes less than or equal to x. is not similar to mathematics
The primes under 25 are 2, 3, 5, 7, 11, 13, 17, 19 and 23 so = 2, = 4 and = 9.

A Table of values of x)

Example 1
Find the number of primes less than 1,000,000.
The approximation gives the range 72,383 to 78,543.

77
 Cryptography and Network Security B.Tech(CSE) III Year II Sem
The actual number of primes is 78,498.
Checking for Primeness
Given a number n, how can we determine if n is a prime? The answer is that we need to see if the number is
divisible by all primes less than

We know that this method is inefficient, but it is a good start.

Example 1:
Is 97 a prime?
The floor of 97) = 9. The primes less than 9 are 2, 3, 5, and 7. We need to see if 97 is divisible by any of
these numbers. It is not, so 97 is a prime.
Example 2:
Is 301 a prime?
The floor of 301) = 17. We need to check 2, 3, 5, 7, 11, 13, and 17. The numbers 2, 3, and 5 do not divide
301, but 7 does. Therefore 301 is not a prime.

Little Theorem
First Version: if p is prime and a is positive integer, then
ap 1 p
Second Version:
ap p
This means that if we divide ap by p then the remainder should be

Example 1:
Find the result of 610 mod 11.
We have 610 mod 11 = 1. This is the first version of little theorem where p = 11.
Example 2
Find the result of 312 mod 11.
Here the exponent (12) and the modulus (11) are not the same. With substitution this can be solved using
little theorem.

Multiplicative Inverses
a mod p = a p 2
mod p
Example
The answers to multiplicative inverses modulo a prime can be found without using the extended Euclidean
algorithm:

78
 Cryptography and Network Security B.Tech(CSE) III Year II Sem

Example:
How to calculate multiplicative inverse of 5 modulo 23 that is 5-1 mod 23?
Solution:
1. 5-1 mod 23 = 523-2 mod 23 (Ref: a-1 mod p= ap-2 mod p)
23-2 21
2. 5 mod 23 = 5 mod 23
3. Calculate following to solve 521 mod 23:
51 mod 23 = 5
52 mod 23=25 mod 23=2
54 mod 23= (52)2 mod 23= (2)2 mod 23=4
58 mod 23= (54)2 mod 23 (4)2 mod 23=16
516 mod 23= (58)2 mod 23 (16)2 mod23=256 mod 23=3
Now binary equivalence of 21 is 10101, so multiply 51 , 54 and 516 values, leave 52 and 58 because these are
in binary form.
521 mod 23 = (516 x 54 x 51 ) mod 23=(3x4x5) mod 23=60 mod 23= 14 mod 23.
Finally 5-1 mod 23 = 521 mod 23 = 14 mod 23

Euler's totient function

Euler's totient function, also known as phi-function (n), this function counts the number of integers that are
both smaller than n and relatively prime to n (coprime). Two numbers are coprime if their greatest
common divisor equals 1.
Here are values of (n) for the first few positive integers:

Example: Find co-primes of 9?

If we check gcd(9,1), gcd(9,2), gcd(9,4), gcd(9,5), gcd(9,7), gcd(9,8) =1,
So, coprimes to 9 are 1,2,4,5,7,8 and their count
Properties
(1)=0
If p is a prime number, (p)=p
If a and b are relatively prime, then: (ab)= (a) (b).
e
If p is a prime, )=pe - pe-1
Examples:
1) Find (7)?
(7)=7-1=6
2) Find (21)?
(21)= (3x7) = (3)x (7)=2x6=12
3) Find (77)?
(77)= (7x11) = (7)x (11)=6x10=60

79
 Cryptography and Network Security B.Tech(CSE) III Year II Sem
4) Find (32)?
(32)= (32)- (32-1) = 9-3=6
5) What is the value of (13)?
Because 13 is a prime, (13) = (13 = 12.
6) What is the value of (10)?
We can use the third rule: (10) = (2) × (5) = 1 × 4 = 4, because 2 and 5 are primes.
7) What is the value of (240)?
We can write 240 = 24 × 31 × 51. Then
(240) = (24 3) × (31 30) × (51 50) = 64
8) Can we say that (49) = (7) × (7) = 6 × 6 = 36?
No. The third rule applies when m and n are relatively prime. Here 49 = 72. We need to use the fourth rule:
(49) = 72 1
= 42.
9) What is the number of elements in Z14*?
The answer is (14) = (7) × (2) = 6 × 1 = 6. The members are 1, 3, 5, 9, 11, and 13.

Note: Interesting point: If n > 2, the value of f(n) is even.

Theorem
First Version:For every a and n, they are relatively prime then
a (n) (mod n)
Second Version
a k × f(n) + 1 a (mod n)
Note: The second version of theorem is used in the RSA cryptosystem.

Example 2:
Find the result of 624 mod 35.
Solution
We have 624 mod 35 = 6 (35) mod 35 = 1.
Example :
Find 34 mod 10 ?
Solution

Example 3:
Find the result of 2062 mod 77.
Solution
If we let k = 1 on the second version,
we have f(77)= f(7)x f(11)=6x10=60
2062 mod 77 = (20 mod 77) (2060+1 mod 77) mod 77=
(20 mod 77) (20f(77) + 1 mod 77) mod 77
= (20)(20) mod 77 = 15.
Multiplicative Inverses
theorem can be used to find multiplicative inverses modulo a composite.

80
 Cryptography and Network Security B.Tech(CSE) III Year II Sem

Example:
The answers to multiplicative inverses modulo a composite can be found without using the extended
Euclidean algorithm if we know the factorization of the composite:

Primitive Root and Multiplicative Orders

Multiplicative Order:
If 'a' and are relatively prime, then
The multiplicative order of modulo n is smallest positive integer 'k' with
ak (mod n)
n(a) or On(a)
Example 1: Define multiplicative order of 4 mod 7
41=4 3 (mod 7)
42=16 2 (mod 7)
43=64 1 (mod 7)
Ord7(4)=3 because 43 is congruent to 1 modulo 7.
Example 2: Define multiplicative order of 2 mod 7
21=2 2 (mod 7)
22=4 4 (mod 7)
23=8 1 (mod 7)
Ord7(2)=3 because 23 is congruent to 1 modulo 7.

Primitive Root :

81
 Cryptography and Network Security B.Tech(CSE) III Year II Sem

If the Group G=<Zn*,x> has any primitive root, the number of primitive roots is
(n))
Example: Find the Number of primitive roots of 25
(25)=20
Find the primitive root of 761
( (761))= (760)
= (23x5x19) = (23)x (5)x (19)
=(23 - 22)x 4x18=4x4x18
=288

CHINESE REMAINDER THEOREM

The Chinese remainder theorem (CRT) is used to solve a set of congruent equations with one variable but
different moduli, which are relatively prime, as shown below:

Solution To Chinese Remainder Theorem

1. Find M = m1 × m2 × × mk. This is the common modulus.
2. Find M1 = M/m1, M2 = M/m2, Mk = M/mk.
3. Find the multiplicative inverse of M1, M2, k using the
corresponding moduli (m1, m2 k). Call the inverses
M1 , M2 k .
4. The solution to the simultaneous equations is

82
 Cryptography and Network Security B.Tech(CSE) III Year II Sem

Example:
Find the solution to the simultaneous equations:

Solution:
We follow the four steps.
1. M = 3 × 5 × 7 = 105
2. M1 = 105 / 3 = 35, M2 = 105 / 5 = 21, M3 = 105 / 7 = 15
3. The inverses are M 1 = 2, M 2 = 1, M 3= 1
4. x = (2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1) mod 105 = 23 mod 105
Example 2:
Find an integer that has a remainder of 3 when divided by 7 and 13, but is divisible by 12.
Solution
This is a CRT problem. We can form three equations and solve them to find the value of x.

If we follow the four steps, we find x = 276. We can check that

276 = 3 mod 7, 276 = 3 mod 13 and 276 is divisible by 12 (the quotient is 23 and the remainder is zero).

Example 3
Assume we need to calculate z = x + y where x = 123 and y = 334, but our system accepts only numbers less
than 100.

Adding each congruence in x with the corresponding congruence in y gives

Now three equations can be solved using the Chinese remainder theorem to find z. One of the acceptable
answers is z = 457.

QUADRATIC CONGRUENCE
Quadratic Congruence is a congruence of the equation of the form a2x2 + a1x + a0 0 (mod n).
We limit our discussion to quadratic equations in which
a2 = 1 and a1 = 0, that is equation of the form.
x2 a (mod n)

83
 Cryptography and Network Security B.Tech(CSE) III Year II Sem
There are two ways:
1. Quadratic Congruence Modulo a Prime
2. Quadratic Congruence Modulo a Composite
Quadratic Congruence Modulo a Prime
In this, we consider the modulus is a prime number. That is the form. x2 a (mod p)
Where p is a prime and is an integer.
Example 1: Solve the x2 3 (mod 11)
Solution: 3 congruent to modulo 11 are 3,14,25 (25 is 5x5 or (-5)x(-5))
The given equation has two solutions:
x2 25 (mod 11)
x 5 (mod 11) and x -5 (mod 11),
But -
So, the solutions are 5 and 6
Check the result: substitute x=5
52 25 =3 (mod 11)
substitute x=6
62 36 =3 (mod 11)
Example 2: Solve the y2 10 (mod 13)
Solution: The number 10 congruent to 13 are 10,23,36 (36 is 6x6 or (-6)x(-6))
The given equation has two solutions:
x (mod 13) and x -6 (mod 13),
But - (mod 13)
So, the solutions are 6 and 7
Check the result: substitute x=6
62 36 10 (mod 13)
substitute x=7
7 49 10 (mod 13)
Quadratic Congruence Modulo a Composite
Quadratic Congruence Modulo a Composite can be solved by set of Quadratic Congruence Modulo a Prime.
Decomposition of congruence modulo a composite:

Example: Assume that x2 36 (mod 77).

We know that 77 = 7 × 11. We can write

The answers are x +1 (mod 7), x 1 (mod 7),

x + 5 (mod 11), and x 5 (mod 11). Now we can make four sets of equations out of these:

84
 Cryptography and Network Security B.Tech(CSE) III Year II Sem

The answers are x = ± 6 and ± 27.

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

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 where as 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
1 Plaintext This is the readable message or data that is fed into the algorithm as input.

2 Encryption The encryption algorithm performs various transformations on the plaintext.

algorithm
3 Public key This is a pair of keys that have been selected so that if one is used for

85
 Cryptography and Network Security B.Tech(CSE) III Year II Sem

4 Private key 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
This is the scrambled message produced as output. It depends on the
5 Ciphertext plaintext and the key. For a given message, two different keys will produce
two different
ciphertexts.
6 Decryption This algorithm accepts the ciphertext and the matching key and produces the
algorithm original plaintext.

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
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 private key.

86
 Cryptography and Network Security B.Tech(CSE) III Year II Sem

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:

87
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

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

transmitting it. B can decrypt the message using public key. Because the message was

entire encrypted message serves as a digital signature.

It is impossible to alter the message without access to 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

Prepared by Ch Assoc.Professor, CSED,KHIT, Guntur 88

Samsonu,
https://www.freshersnow.com/
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

the public-key scheme (above figure):

In this case, we begin as before by encrypting a message, using the private key. This provides

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
private key or the 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 public key.
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/Decryption Digital Signature Key Exchange
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

Prepared by Ch Samsonu, Assoc.Professor, 89

https://www.freshersnow.com/
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

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 (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 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.

Prepared by Ch Samsonu, Assoc.Professor, 90

https://www.freshersnow.com/
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

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 to compute
without some special knowledge k. Given k, then it is easy to compute
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 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.

Prepared by Ch Samsonu, Assoc.Professor, 91

https://www.freshersnow.com/
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

For any integer b and a, here a is a primitive root of prime number P, then
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.

Prepared by Ch Samsonu, Assoc.Professor, 92

https://www.freshersnow.com/
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

The Diffie- Hellman key exchange is insecure against a in the middle

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 and 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

Prepared by Ch Samsonu, Assoc.Professor, 93

https://www.freshersnow.com/
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

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)

Prepared by Ch Samsonu, Assoc.Professor, 94

https://www.freshersnow.com/
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

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

Alice generates a key pair as follows:

Prepared by Ch Samsonu, Assoc.Professor, 95

https://www.freshersnow.com/
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

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.

Prepared by Ch Samsonu, Assoc.Professor, 96

https://www.freshersnow.com/
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

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 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)
4. 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

Prepared by Ch Samsonu, Assoc.Professor, 97

https://www.freshersnow.com/
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

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 -11 +a2xM2xM -12) mod M
=( 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 -11 +a2xM2xM -12) mod M
=( 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 M1xM -11 +a2xM2xM -12) mod M
=( 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
-1 -1 23-2 21
M1 =7 mod 23 = 7 mod 23 = 7 mod 23=10
M2-1=23-1 mod 7 = 237-2 mod 7 = 235 mod 7=4
X= (a1 x M1xM -11 +a2xM2xM -12) mod M
=( 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

Prepared by Ch Samsonu, Assoc.Professor, 98

https://www.freshersnow.com/