MODULE - 2

Public key cryptography and RSA

 Message Authentication

Why Message Authentication Require?

Message authentication is necessary because the following are the identified

attackers:
1) Disclosure – The message content released to a person. This is a breach of
confidentiality. It can be possible either from an insider or outsider.
2) Traffic analysis – The attacker can identify the message by analyzing the traffic
pattern like signal frequency and length of the message between sender and
receiver.
3) Masquerade – He can change the message content. He can read the message
as if he is an authorized user. He can send the message acks on behalf of true
receiver.
 Why Message Authentication Require? (contd….)

4) Content modification - Changes to the contents of a message, including

insertion, Deletion and modification.
5) Source repudiation- Denial of transmission of message by source (refuse for
connection establishment).
6) Destination repudiation- Denial of receipt of message by destination.

To overcome these attacks/problems, message authentication is necessary.

 Message Authentication Functions

The message authentication functions are of three types.

1) Hash function
2) Message encryption
3) Message authentication code (MAC)
 Message Authentication Functions

(1) Hash function

It transform message of any length into a fixed length, which
provide message authentication.
(2) Hash functions are known for faster execution.
(3) Hash functions are computationally efficient.
(4) Hash function generate random numbers. The combination of
random number with cryptographic key can provide both
authenticity and Integrity.
 (1)Hash function (contd….)

(4) The digital signature system uses Hash function (hashing/

hashing algorithm).
(5) A hash function is a mathematical function that converts an
input value into a compressed numerical value called
hash value or message digest or cryptographic hash.
(7) The hashing process unit takes message of arbitrary length and
gives you the output of a fixed length called hash value.
Example
 (2) Message Encryption
This is another method of message authentication.
There are two methods of message encryption –
(1) Symmetric-key encryption methods &
(2) Asymmetric-key (Public-key) encryption method.
 Generally, the public & private keys are not generated using
the same algorithm, but the key combination is used for
encryption and decryption because the algorithm use
mathematically related logic.
 Normally, public keys are generated by random number
generating algorithms.
 (2) Message Encryption (cotnd…)

(1) Symmetric-key encryption methods

A is the source and B is the destination. A & B use the same key. A encrypt the
message (M) by using the key (K). The encrypted message, X=E(K,M) is
transmitted from A to B. B decrypt the received cipher text by using the same
secret key (K) and recover the plaintext, Y=D(K,X).
 If no third party knows the key, then confidentiality and authenticity has been
provided for the message.
 B believes that none of the bits of M have been altered, because an opponent
that does not know the key, K.
 No third party can read the message.
 (2) Symmetric-key encryption methods (contd….)
 Suppose that there is a possibility of eavesdropping, then to protect the
message, append by a frame check sequence (FCS) or checksum function to
each message before encryption, as illustrated in Figure.
 Source A, prepares a plaintext M, provides this M as an input to a function F,
which produce FCS. FCS is appended with M and the entire block is encrypted.
 At the destination, B decrypt the block using Key, gets M & FCS, apply the same
function F to M to get the FCS. The calculated FCS is equal to the incoming FCS,
then the message is considered authentic. This process is also called as internal
error control.
 (3) Symmetric-key encryption methods (contd….)
 Source A, encrypt the message by using the key, apply F to
ciphertext to get FCS code. Append FCS code with ciphertext.
 At B, ciphertext is decrypted using key to get plaintext Message.
The ciphertext is fed to F to get FCS. The calculated FCS is
compared with received FCS, found correct authenticate the
message. This is called external error control.
 This provide both confidentiality and authenticity.
 (2) Public-Key Encryption

Public-key encryption is also known as Asymmetric Encryption, Public-Key

Cryptography, two-key encryption.
 Here one key is used for data encryption while the other key is used
for decryption.
 (i) Public-Key Encryption: Confidentiality
 Here, A is the source and B is the destination.
 The source A uses the public key Pub to encrypt the message M. The

destination B use corresponding private key PRb for decrypt the message.
 This scheme provides confidentiality but not the authentication, because,
(a) any opponent could use public key to encrypt some message and claim to
be A,
(b) Eaves Dropper can intercept the message.
 (ii) Public-Key Encryption: Confidentiality & Integrity (authentication)
 To provide authentication, A uses his private key to encrypt the message, and

B uses A’s public key to decrypt .

 The mechanism provide confidentiality because the message is encrypted by

using private-key.
 The scheme also provide authentication as the message must have come

from A, because A is the only person that possesses Pra. Therefore, he is the

only person who can construct the ciphertext. It is decrypted by using PU a.

 (iii) Public-Key Encryption: Confidentiality ,Integrity & Signature(security)
 To provide both confidentiality and authentication, A can encrypt the message
M first using private key, which provides the digital signature (authentication),
and then using B’s public key encrypt again , which provides confidentiality as
shown in the figure.
 (3) Message Authentication Code (MAC)

 A secret key is used to encrypt and decrypt message.

 Using MAC, we can provide both confidentiality and Integrity.

 It is symmetric key algorithm.
 The technique use a secret key & MAC function to generate a small fixed-size
block of data, known as a cryptographic checksum or MAC. This MAC is
appended to the message.
 Operation of MAC function is to confirm that the message came from true
sender (authenticity) and has not been changed.
 Message Authentication Code (MAC) - authentication
Type-1:
 Two communicating parties, say A and B, share a common secret key K.
 When A has a message to send to B, it calculates the MAC as a function of the
message and the key,
 MAC = C(K, M) where M = input message; C = MAC function; K = shared
secret key; MAC = message authentication code.
 A minor change in the message or in the key results to totally different MAC
value.
Type-2:
Message Authentication Code (MAC) - authentication & Confidentiality

Two separate secret keys are used.

Type-3:
Message Authentication Code (MAC) - authentication & Confidentiality
 Key Management and Distribution
Symmetric key distribution using symmetric encryption
 In symmetric encryption, the two parties must share the same key so, the key
must be protected from access by others during the process of exchange.
 Therefore, the strength of any cryptographic system depends upon the key
distribution technique.
Possible key distribution types between two parties A and B are as follows:
1. A can select a key and physically deliver it to B (manual delivery).
2. A third party can physically deliver the key to A and B (manual delivery).
3. If A and B have previously and recently used a key, one can transmit the
new key to the other by encrypting using the old key (link encryption).
4. If A and B each has an encrypted connection to a third party C, the third party
C can deliver a key in an encrypted way to A and B (end-to-end encryption).
 Use of key hierarchy
 A key distribution center (KDC) is part of a cryptosystem takes care of
exchanging the keys.
 The key distribution center (KDC)works based on a hierarchical key system
called Session key and Master key.
 To establish the logical connection between two end points, the crypto system
use a temporary key called Session key.
 Session keys are transmitted in an encrypted form using Master key.
 Master keys can be distributed to the intermediate nodes in some non-
cryptographic way, such as physical delivery.
 RSA (Rivest, Shamir, Adleman) Algorithm
 Developed in 1977 by Rivest, Shamir, and Adleman.
 Famous and most popular public key algorithm.
 It has simple procedure but very hard to break the cipher.
 It is extensively used in data transfer over the Internet.
 It use a pair of keys called Public key & Private key.
 Key Generation
1) Choose large prime numbers p & q.
2) n = p x q
3) Euler's Totient function, φ(n) = (p-1)x (q-1)
4) Choose Kpub = e ϵ{1,2,3,4,….. (φ(n) -1)} such that GCD (e, φ(n)) =1 (relatively
prime).
5) Compute Kpr = d such that e x d = 1 mod φ(n)
6) Encryption, C = Me mod n
7) Decryption, M = Cd mod n.

Note: p , q ≥ 2 512 24 862048 digit long prime number

Example-1: Let p =3, q =11
Solution
1) n = 3 x 11 = 33
2) Euler’s totient function, φ(n) = (p-1) x (q-1) = 2 x 10 = 20
3) Choose Kpub = e ϵ {1,2,3,4,….. (φ(n) -1)} = e ϵ {1,2,3,4, 5,6,7….19} such that

GCD (e, φ(n)) =1 (relatively prime).

4) Assume e = 3 such that GCD (3, 20) = 1 (relatively prime). Therefore, Kpub = e = 3.

5) Compute Kpr = d such that e x d = 1 mod φ(n). 3 x d = 1 mod 20,

Therefore, Kpr = d = 7
6) Encryption: Let, M = 4 < n.
(i) C = Me mod n ⇒ c = 43 mod 33 ⇒ c = 64 mod 33 = 31. ⇒ C =31.
7) Decryption:
(i) M = Cd mod n ⇒ M = 317 mod 33 ⇒ M = 4.
Example-2: Let p =3, q =5
Solution
1) n = 3 x 5 =15
2) Euler’s Totient function, φ(n) = (p-1)x (q-1) = 2 x 4 = 8
3) Choose Kpub = e ϵ {1,2,3,4,….. (φ(n) -1)} = e ϵ {1,2,3,4, 5,6,7} such that
GCD (e, φ(n)) =1 (relatively prime).
4) Assume e = 3 such that GCD (3, 8) = 1 (relatively prime). Therefore, Kpub = e = 3.

5) Compute Kpr = d such that e x d = 1 mod φ(n). 3 x d = 1 mod 8, impels, Kpr = d = 3

6) Encryption: Let, M = 4 < n.
(i) C = Me mod n ⇒ c = 43 mod 15 ⇒ c = 64 mod 15 = 4. Therefore, C =4.
7) Decryption:
(i) M = Cd mod n ⇒ M = 43 mod 15 ⇒ M = 64 mod 15 ⇒ M =-4
Example-3: Let p =17, q =11
Solution
1) n = 17 x 11 = 187
2) Euler’s totient function, φ(n) = (p-1)x (q-1) = 16 x 10 = 160
3) Choose Kpub = e ϵ {1,2,3,4,….. (φ(n) -1)} = e ϵ {1,2,3,4, 5,6,7….159} such that

GCD (e, φ(n)) =1 (relatively prime).

4) Assume e = 7 such that GCD (7, 160) = 1 (relatively prime). Therefore, Kpub = e = 7.

5) Compute Kpr = d such that e x d = 1 mod φ(n) ⇒ 7 x d = 1 mod 160,

Therefore, Kpr = d = 23
6) Encryption: Let, M = 88 < n.
(i) C = Me mod n ⇒ c = 887 mod 187 ⇒ c = 894432 mod 187 = 11. ⇒ C =11.
7) Decryption:
(i) M = Cd mod n ⇒ M = 1123 mod 187 ⇒ M = 88.
 The Security of RSA

Five 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.
 Hardware fault-based attack: This involves inducing hardware
faults in the processor that is generating digital signatures.
 Chosen ciphertext attacks: This type of attack exploits properties
of the RSA algorithm.
 Diffie – Hellman key Exchange Algorithm

 The public-key algorithm was developed by Diffie and Hellman

and is generally referred to as Diffie-Hellman key exchange.

 A number of commercial products employ this key exchange

technique.

 The purpose of the algorithm is to enable two users to securely

exchange a key that can then be used for subsequent symmetric
encryption of messages.
 Diffie – Hellman key Exchange Algorithm

i) User A selects a random integer XA < q where q is a prime

number and computes YA = a XA mod q. Similarly, user B
independently selects a random integer XB < q and computes YB
= a XB mod q.

ii) Each side keeps the X value private and makes the Y value
available publicly to the other side. Thus, XA is A’s private key
and YA is A’s corresponding public key, and similarly , XB is B’s
private key and YB is B’s corresponding public key.

iii) User A computes the key as K = (YB)XA mod q and user B

computes the key as K = (YA)XB mod q. These two calculations
produce identical results:
Diffie-Hellman key exchange Protocol
To show that these two calculations produce identical keys
Example
Man-in-the-Middle Attack
 The Man-in-the Middle attack proceeds as follows:

1. Darth prepares for the attack by generating two random private keys XD1 and
XD2 and then computing the corresponding public keys YD1 and YD2.
2. Alice transmits YA to Bob.
3. Darth intercepts YA and transmits YD1 to Bob. Darth also calculates

K2 = (YA)XD2 mod q.
4. Bob receives YD1 and calculates K1 = (YD1)XB mod q.
5. Bob transmits YB to Alice.
6. Darth intercepts YB and transmits YD2 to Alice. Darth calculates
K1 = (YB)XD1 mod q.
7. Alice receives YD2 and calculates K2 = (YD2)
XA mod q
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.

1. Alice sends an encrypted message M: E(K2, M).

2. Darth intercepts the encrypted message and decrypts it to recover M.
3. Darth sends Bob E(K1, M) or E(K1, M′), where M′ is any message. In the
first case, Darth simply wants to eavesdrop on the communication without
altering it. In the second case, Darth wants to modify the message going to
Bob.
 The Elgamal cryptographic system (ECS)

In 1984, T. Elgamal announced a public-key scheme based on discrete logarithms,

closely related to the Diffie-Hellman technique .

ECS use a prime number q and α, which is a primitive root of q. User A generates
a private/public key pair as follows:
Any user B that has access to A’s public key can encrypt a message as follows:
User A recovers the plaintext as follows:
The Elgamal Cryptosystem
We can restate the Elgamal process as follows,

END OF MODULE-2