Cryptography and Network Security

Subject Code: BCG703

Module 2: Public key cryptography and RSA

These algorithms have the following important characteristic:

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. A public-key encryption scheme has six ingredients

2
Public-Key Cryptosystems
A public-key encryption scheme has six ingredients

• Plaintext: This is the readable message or data that is fed into the algorithm as input.
• Encryption algorithm: The encryption algorithm performs various transformations on
the plaintext.
• Public and private keys: This is a pair of keys that have been selected so that if one is
used for encryption, the other is used for decryption. The exact transformations
performed by the algorithm depend on the public or private key that is provided as
input.
• 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.
• Decryption algorithm: This algorithm accepts the cipher text and the matching key and
produces the original plaintext.
3
Figure 9.1 Public-Key Cryptography

4
Figure 9.1 Public-Key Cryptography

5
Public-Key Cryptosystems
• Decryption algorithm:
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 Figure 9.1a 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.

6
Public-Key Cryptosystems

With the message X and the encryption key PUb as input, A forms the
ciphertext Y = [Y1, Y2 ,………,YN ]:

Y = E(P Ub, X)
The intended receiver, in possession of the matching private key, is able to
invert the transformation:
X = D(PRb, Y)

7
8
9
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. 10
It is, however, possible to provide both the authentication function and confidentialityby
a double use of the public-key scheme (Figure 9.4):

11
Requirements for Public-Key Cryptography
The cryptosystem illustrated in Figures 9.2 through 9.4 depends on a cryptographic algorithm
based on two related keys. Diffie and Hellman postulated this system without demonstrating
that such algorithms exist
1. It is computationally easy for a party B to generate a key pair (public key PUb, 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 ciphertext C = E(PUb, M)
3. It is computationally easy for the receiver B to decrypt the resulting ciphertext using
the private key to recover the original message: M = D(PR b, C) = D[PR b, E(PU b, M)]

12
Requirements for Public-Key Cryptography Contd..
4. It is computationally infeasible for an adversary, knowing the public key, PU b, to determine the private
key, PR b.
5. It is computationally infeasible for an adversary, knowing the public key, PU b, and a
ciphertext, C, to recover the original message, M.

We can add a sixth requirement that, although useful, is not necessary for all public-key applications:
6. The two keys can be applied in either order:
M = D[PU b, E(PR b, M)] = D[PR b, E(PU b, M)]

13
Public-Key Cryptography

14
THE RSA ALGORITHM
The pioneering paper by Diffie and Hellman [DIFF76b] introduced a new approach to
cryptography and, in effect, challenged cryptologists to come up with a cryptographic
algorithm that met the requirements for public-key systems. A number of algorithms have
been proposed for public-key cryptography.

Some of these, though initially promising, turned out to be breakable. One of the first
successful responses to the challenge was developed in 1977 by Ron Rivest, Adi Shamir,
and Len Adleman at MIT and first published in 1978 [RIVE78]. The Rivest-Shamir-
Adleman (RSA) scheme has since that time reigned supreme as the most widely accepted
and implemented general-purpose approach to public-key encryption.

15
The RSA Algorithm: Description
RSA makes use of an expression with exponentials. 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) + 1; in practice, the block size is i bits, where 2i < n <= 2i+1.

Encryption and decryption are of the following form, for some plaintext block M and
cipher-text block C.
C = Me mod n
M = Cd 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,
and only the receiver knows the value of d. Thus, this is a public-key encryption
algorithm with a public key of PU = {e, n} and a private key of PR = {d, n}.

16
The RSA Algorithm: Description Contd..

For this algorithm to be satisfactory for public-key encryption, the following

1. It is possible to find values of e, d, and n such that Med mod n = M for all M < n.
2. It is relatively easy to calculate Me mod n and Cd mod n for all values of M < n.
3. It is infeasible to determine d given e and n.

17
The RSA Algorithm: Description Contd..

That is, e and d are multiplicative inverses mod ϕ(n). Note that, according to the rules
of modular arithmetic, this is true only if d (and therefore e) is relatively prime to f(n).
Equivalently, gcd(ϕ(n), d) = 1.
18
19
THE RSA ALGORITHM

20
THE RSA ALGORITHM

21
THE RSA ALGORITHM

22
Diffie-Hellman algorithm

23