MODULE 2

CHAPTER 1 PUBLIC-KEY CRYPTOGRAPHY AND RSA

 The development of public-key cryptography is the greatest and perhaps the only true
revolution in the entire history of cryptography.
 Earlier all cryptographic systems have been based on the elementary tools of substitution
and permutation.
 Public key algorithms are based on mathematical functions rather than on substitution
and permutation.
 More important, public-key cryptography is asymmetric, involving the use of two separate
keys, in contrast to symmetric encryption, which uses only one key.
 The use of two keys has profound consequences in the areas of confidentiality, key distribution,
and authentication, as we shall see.

Common misconceptions concerning public-key encryption:

1. Public-key encryption is more secure from cryptanalysis than is symmetric encryption. In fact,
the security of any encryption scheme depends on the length of the key and the
computational work involved in breaking a cipher.
2. A second misconception is that public-key encryption is a general-purpose technique that has
made symmetric encryption obsolete.
3. Finally, there is a feeling that key distribution is important when using public-key encryption,
compared to the rather handshaking involved with key distribution centers for symmetric
encryption.

Terminology Related to Asymmetric Encryption

Asymmetric Keys

Two related keys, a public key and a private key, that are used to perform
complementary operations, such as encryption and decryption or signature generation and
signature verification.
Public Key Certificate

A digital document issued and digitally signed by the private key of a Certification
Authority that binds the name of a subscriber to a public key. The certificate indicates that the
subscriber identified in the certificate has sole control and access to the corresponding private
key.

Public Key (Asymmetric) Cryptographic Algorithm

A cryptographic algorithm that uses two related keys, a public key and a private key. The
two keys have the property that deriving the private key from the public key is computationally
infeasible.

Public Key Infrastructure (PKI)

A set of policies, processes, server platforms, software and workstations used for the
purpose of administering certificates and public-private key pairs, including the ability to issue,
maintain, and revoke public key certificates.

Principles of Public-Key Cryptosystems

The concept of public-key cryptography evolved from an attempt to attack two of the
most difficult problems associated with symmetric encryption. The first problem is that of key
distribution.

As we have seen, key distribution under symmetric encryption requires either

1. Two communicants already share a key, which somehow has been distributed to them or
2. The use of a key distribution center.

Whitfield Diffie, one of the discoverers of public-key encryption reasoned that this
second requirement negated the very essence of cryptography: the ability to maintain total
secrecy over your own communication.
The second problem is digital signatures. The electronic messages and documents would
need the equivalent of signatures used in paper documents. That isdigital message had been sent
by a particular person? This is a somewhat broader requirement than that of authentication,
Diffie and Hellman achieved breakthrough by coming up with a method that addressed
both problems and was radically different from all previous approaches to cryptography.
Public-Key Cryptosystems
Asymmetric algorithms rely on one key for encryption and a different but related key for
decryption. 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.

 Either of the two related keys can be used for encryption, with the other used
for decryption.

Anyone knowing the public key can encrypt messages or verify signatures, but cannot
decrypt messages or create signatures, thanks to some clever use of number theory.

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.
 Ciphertext: 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
ciphertexts.
 Decryption algorithm: This algorithm accepts the ciphertext and the matching key and
produces the original plaintext.
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. Thisis the
public key. The companion key is kept private. 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 messageusing
Alice's public key.

4. When Alice receives the message, she decrypts it using her private key. No otherrecipient
can decrypt the message because only Alice knows Alice's private key.

To discriminate between symmetric and public-key encryption, 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.
Conventional Encryption Public-Key Encryption
Needed to Work: Needed to Work:
1. The same algorithm with the same key 1. One algorithm is used for encryption and
is used for encryption and decryption. decryption with a pair of keys, one for
2. The sender and receiver must share the encryption and one for decryption.
algorithm and the key. 2. The sender and receiver must each have one of
the matched pair of keys (not the same one).

Needed for Security: Needed for Security:

1. The key must be kept secret. 1. One of the two keys must be kept secret.
2. It must be impossible or at least 2. It must be impossible or at least impractical to
impractical to decipher a message if no decipher a message if no other information is
other information is available. available.
3. Knowledge of the algorithm plus 3. Knowledge of the algorithm plus one of the
samples of ciphertext must be keys plus samples of ciphertext must be
insufficient to determine the key. insufficient to determine the other key.

Public-Key Cryptosystems: Secrecy and Authentication

 Public-key schemes can be used for either secrecy or authentication, or both (as shown
here). There is some source A that produces a message in plaintext X. The message is
intended for destination B.

 B generates a related pair of keys: a public key, PUb, and a private key, PRb. PRbis
known only to B, whereas PUb is publicly available and therefore accessible byA.

 With the message X and the encryption key PUb as input, A forms the
 ciphertext Y = E(PUb, X)

 The intended receiver, in possession of the matching private key, is able to invert the
transformation: 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. This provides confidentiality.

 Public-key encryption can also provide authentication:

Y = E(PRa, X); X = D(PUa, Y)

 To provide both the authentication function and confidentiality have a double use of the
public- key scheme (as shown here):

Z = E(PUb, E(PRa, X))

X = D(PUa, D(PRb, Z))

Applications for Public-Key Cryptosystems

We can classify the use of public-key cryptosystems into three categories:

 Encryption/decryption: The sender encrypts a message with the recipient's public key.
 Digital signature: The sender "signs" a message with its private key. Signing is achieved
by a cryptographic algorithm applied to the message or to a small block of data that is a
function of the message.
 Key exchange: Two sides cooperate to exchange a session key. Several different
approaches are possible, involving the private key(s) of one or both parties.

Requirements for Public-Key Cryptography

1. It is computationally easy for a party B to generate a pair (public key PUb, privatekey 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(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
ciphertext, C, to recover the original message, M.

We can add a sixth requirement that, although useful, is not necessary for allpublic-
key applications:

6. The two keys can be applied in either order:

M = D[PUb, E(PRb, M)] = D[PRb, E(PUb, M)]

A one-way function is one that maps a domain into a range such that every function value has a
unique inverse, with the condition that the calculation of the function is easy whereas the
calculation of the inverse is infeasible:

Y = f(X) easy

X = f–1(Y) infeasible

Trap-door one-way function

It is easy to calculate in one direction and infeasible to calculate in the other direction unless certain
additional information is known.

Y = fk(X) easy, if k and X are

knownk X = f –1(Y) easy, if k and Y

are known

X = f k–1(Y) infeasible, if Y known but k not known

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.
 The key size must be large enough to make brute-force attack impractical but result in
encryption/decryption speeds that are too slow for general-purpose use.
 Another form of attack is to find some way to compute the private key given the public key.
To date, it has not been mathematically proven that this form of attack is infeasible for a
particular public-key algorithm.
 Finally, there is a form of attack that is peculiar to public-key systems. This is, in
 essence, a
probable-message attack.
 Suppose, for example, that a message were to be sent that consisted solely of a 56-bitDES
key. An adversary could encrypt all possible 56-bit DES keys using the public key and could
discover the encrypted key by matching the transmitted ciphertext.
 Thus, no matter how large the key size of the public-key scheme, the attack is reduced to a
brute- force attack on a 56-bit key. This attack can be thwarted by appending some random
bits to such simple messages.

The RSA Algorithm

RSA Algorithm was developed in 1977 by Ron Rivest, Adi Shamir, and Len Adleman at MIT.

The Rivest-Shamir-Adleman (RSA) scheme has since that time reigned supremeas the
most widely accepted and implemented general-purpose approach to public-key encryption.

The RSA scheme is a block cipher in which the plaintext and 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 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 blocksize must be
less than or equal to log2(n) + 1. Encryption and decryption are of the following form, for
some plaintext block M and ciphertext block C.

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

For this algorithm to be satisfactory for public-key encryption, the following requirements must
be met.

1. It is possible to find values of e, d, 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.

For now, we focus on the first requirement and consider the other questions later. We need to
find a relationship of the form. The preceding relationship holds if e and d are multiplicative
inverses modulo φ(n), where φ(n) is the Euler totient function. The relationship between e and d
can be expressed as ed mod ɸ(𝑛) = 1 e-1
This is equivalent to saying

That is, e and 𝑑 are multiplicative inverses mod (ɸ𝑛 ) . Note that, according to the rules of
modular arithmetic, this is true only if 𝑑 (and therefore e) is relatively prime to
ɸ(𝑛).Equivalently, gcd(ɸ(𝑛),
𝑑) = 1.

We are now ready to state the RSA scheme. The ingredients are the following:

𝑝 , 𝑞 t,wo prime numbers (private, chosen)

n = pq (public, calculated)

e, with gcd(ɸ(𝑛), e) = 1; 1 < e < (n) (public, chosen)

𝑑 ≡ e− 1𝑚 o 𝑑 (ɸ𝑛 ) (private, calculated)

The private key consists of {d, n} and the public key consists of {e, n}. Supposethat user
A has published its public key and that user B wishes to send the message M to A. Then B
calculates 𝐶= 𝑀e 𝑚o𝑑 𝑛 and transmits C. On receipt of this ciphertext, user A decrypts by
calculating 𝑀= 𝐶𝑑 𝑚o𝑑 𝑛.

Example:

Alice generates a public/private key pair; Bob encrypts using Alice’s public key; and Alice
decrypts using her private key. For this example, the keys were generated as follows.
1. Select two prime numbers, p = 17 and q = 11.
 2. Calculate n = pq = 17 * 11 = 187.
3. Calculate f(n) = (p - 1)(q - 1) = 16 * 10 = 160.
4. Select e such that e is relatively prime to f(n) = 160 and less than f(n); we choose e = 7.
5. Determine d such that de K 1 (mod 160) and d 6 160. The correct value is d = 23, because
23
* 7 = 161 = (1 * 160) + 1; d can be calculated using the extended Euclid’s algorithm
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 = 887mod 187. Exploiting the properties of modular arithmetic, we can do this as
follows.

887 mod 187 = [(884mod 187) × (882mod 187) × (881mod 187)] mod 187

881mod 187 = 88

882mod 187 = 7744 mod 187 = 77

884mod 187 = 59,969,536 mod 187 = 132

887mod 187 = (88 × 77 × 132) mod 187 = 894,432 mod 187 = 11

For decryption, we calculate M = 1123 mod 187:
1123mod 187 = [(111mod 187) × (112mod 187) × (114mod 187) × (118mod 187) × (118 mod 187)]
mod 187
111mod 187 = 11

112mod 187 = 121

114mod 187 = 14,641 mod 187 = 55

118mod 187 = 214,358,881 mod 187 = 33

1123mod 187 = (11 × 121 × 55 × 33 × 33) mod 187 = 79,720,245 mod 187 = 88

Computational Aspects

We now turn to the issue of the complexity of the computation required to use RSA. There
are actually two issues to consider: encryption/decryption and key generation.

To perform the modular exponentiations, you can use the “Square and Multiply
Algorithm”, a fast, efficient algorithm for doing exponentiation.

The idea is to repeatedly square the base, and multiply in the ones that are needed to
compute the result, as found by examining the binary representation of the exponent.

 Eg. 7 5= 7 4.7 1= 3.7 = 10 mod 11

 eg. 3129 = 3128.31 = 5.3 = 4 mod 11

The RSA algorithm requires that during key generation, the user selects a value of e that
is relatively prime to ø (n). Thus, if a value if e is selected first, and the primes p and q are
generated, it may turn out that gcd(ø(n), e) ≠ 1. In that case, the user must reject the p, q values
and generate a new p, q pair.

RSA Key Generation

 Before the application of the public-key cryptosystem, each participant must generate a pair
of keys, which requires finding primes and computing inverses.
 Both the prime generation and the derivation of a suitable pair of inverse exponents may
involve trying a number of alternatives.
 Typically make random guesses for a possible p or q, and check using a probabilistic
primarily test whether the guessed number is indeed prime. If not, try again.
 Note that the prime number theorem shows that the average number of guesses needed is
not too large.
 Then compute decryption exponent d using Euclid’s Inverse Algorithm, which is
quite efficient.

The Security of RSA

Four possible approaches to attacking the RSA algorithm are as follows:

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

Brute force:

The defense against the brute-force approach is the same for RSA as for other
cryptosystems, namely, use a large key space. Thus, the larger the number of bits in d, the
better. However, because the calculations involved, both in key generation and in
encryption/decryption, are complex, the larger the size of the key, the slower the system will
run.

The Factoring Problem:

We can identify three approaches to attacking RSA mathematically:

 Factor n into its two prime factors. This enables calculation of ɸ(𝑛)=(p -1)*( q-
1),which, in turn, enables determination of 𝑑= e− 1𝑚 o 𝑑 (ɸ𝑛 ) .
 Determine ɸ(𝑛) directly, without first determining p and q. Again, this
enables determination of 𝑑 = e− 1𝑚 o 𝑑 (ɸ𝑛 ) .
 Determine d directly, without first determining ɸ(𝑛).

Determining ɸ(𝑛) given n is equivalent to factoring n. With presently known

algorithms, determining d given e and n appears to be at least as time-consuming as the

factoring problem. Hence, we can use factoring performance as a benchmark against

 which to evaluate the security of RSA.

To avoid values of n that may be factored more easily, the algorithm's inventors suggest
the following constraints on p and q:

1. p and q should differ in length by only a few digits. Thus, for a 1024-bit key
(309decimal digits), both p and q should be on order of 1075 to 10100.
2. Both (p – 1) and (q – 1) should contain a large prime factor
3. gcd(p–1, q–1) should be small.

Timing Attacks:

 Timing Attacks demonstrated that a snooper can determine a private key by keeping
track of how long a computer takes to decipher messages.
 Timing Attacks are based on observing how long it takes to compute the cryptographic
operations. Timing attacks are applicable not just to RSA, but to other public-key
cryptography systems.
 This attack is alarming for two reasons: It comes from a completely unexpected
direction and it is a ciphertext-only attack.

The timing attack is a serious threat; there are simple countermeasures that can be
used, including using constant exponentiation time algorithms, adding random delays, or using
blind values in calculations.

 Constant exponentiation time: Ensure that all exponentiations take the same amount of
time before returning a result. This is a simple fix but does degrade performance.
 Random delay: Better performance could be achieved by adding a random delay to the
exponentiation algorithm to confuse the timing attack. Kocher points out that if defenders
don't add enough noise, attackers could still succeed by collecting additional
measurements to compensate for the random delays.
 Blinding: Multiply the ciphertext by a random number before performing exponentiation.
This process prevents the attacker from knowing what ciphertext bits are being processed
inside the computer and therefore prevents the bit-by-bit analysis essential to the timing
attack.
Chosen Ciphertext Attacks:
 The RSA algorithm is vulnerable to a chosen ciphertext attack (CCA).
 CCA is defined as an attack in which adversary chooses a number of ciphertexts and is
then given the corresponding plaintexts, decrypted with the target’s privatekey.
 The adversary exploits properties of RSA and selects blocks of data that, when processed
using the target’s private key, yield information needed for cryptanalysis.
 More sophisticated variants need to modify the plaintext using a procedure known as
optimal asymmetric encryption padding (OAEP).

To counter such attacks RSA Security, a leading RSA vendor and former holder of the
RSA patent, recommends modifying the plaintext using a procedure known as optimal
asymmetric encryption padding (OAEP).

 As a first step the message M to be encrypted is padded. A set of optional parameters P is

passed through a hash function H.
 The output is then padded with zeros to get the desired length in the overall data
block(DB). Next, a random seed is generated and passed through another hash function,
called the mask generating function (MGF).
 The resulting hash value is bit-by-bit XORed with DB to produce a maskedDB.
 The maskedDB is in turn passed through the MGF to form a hash that is XORed withthe
seed to produce the masked seed.
 The concatenation of the maskedseed and the maskedDB forms the encoded messageEM.
 Note that the EM includes the padded message, masked by the seed, and the seed,masked
by the maskedDB. The EM is then encrypted using RSA.
 CHAPTER 2. OTHER PUBLIC KEY CRYPTOSYSTEMS

Diffie-Hellman Key Exchange

The purpose of the algorithm is to enable two users to securely exchange a keythat can
then be used for subsequent encryption of messages.

If a is “a” primitive root of the prime number p, then the numbers

a mod p, a2 mod p,..., ap1 mod p

are distinct and consist of the integers from 1 through p -1 in some permutation.

Example:

3 is primitive root of 7.

The number 3 is a primitive root modulo 7, because

31 = 3 = 30 × 3 ≡ 3 ≡ 3 (𝑚o𝑑 )7

32 = 9 = 32 × 3 ≡ 9 ≡ 2 (𝑚o𝑑 7)

33 = 27 = 33 × 3 ≡ 6 ≡ 6 (𝑚o𝑑 7)

34 = 81 = 34 × 3 ≡ 18 ≡ 4 (𝑚od 7)

35 = 243 = 35 × 3 ≡ 12 ≡ 5 (𝑚o𝑑 7)

36 = 729 = 36 × 3 ≡ 15 ≡ 1 (𝑚o 7)

Here we see that the period of 3k modulo 7 is 6. The remainders in the period,which are
3, 2, 6, 4, 5, 1, form a rearrangement of all nonzero remainders modulo 7, implying that 3 is
indeed a primitive root modulo 7.
The Algorithm:
There are two publicly known numbers: a prime number q and an integer that is
aprimitive root of q.
Suppose the users A and B wish to exchange a key. User A selects a random integer XA
< q and computes YA = XA mod q. Similarly, user B independently selects arandom integer XA
< q and computes YB = XB mod q.
Each side keeps the X value private and makes the Y value available publicly to the otherside.
User A computes the key as K = (YB)X mAod q and user B computes the key as K =(YA)XB mod
q. These two calculations produce identical results:
K = (YB)XA mod q
= (XB mod q)XA mod q
= (XB)XA mod q by the rules of modular arithmetic
XB XA
= ( mod q
XA XB
= ( ) mod q
= (XA mod q)
= (XA mod q)XB mod q
= (YA)XB mod q

Example:

Prime number q = 353 and a primitive root of 353, in this case α = 3.

A and B select secret keys XA = 97 and XB = 233, respectively. Each computes its publickey:

A computes YA = 397 mod 353 = 40.

B computes YB = 3233 mod 353 = 248.

After they exchange public keys, each can compute the common secret key:

A computes K = (YB)XA mod 353 = 24897 mod 353 = 160

B computes K = (YA)XB mod 353 = 40233 mod 353

Key Exchange Protocols:

Suppose that user A wishes to set up a connection with user B and use a secret key to
encrypt messages on that connection. User A can generate a one-time private key
XA,calculate YA, and send that to user B.
User B responds by generating a private value XB calculating YB, and sending YB to user A.
Both users can now calculate the key.
The necessary public values q and would need to be known ahead of time.
Alternatively, user A could pick values for q and and include those in the first message.
Man-in-the-Middle Attack:

Suppose Alice and Bob wish to exchange keys, and Darth is the adversary.
Theattack proceeds as follows.

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
digitalsignatures and public-key certificates;

ELGAMAL CRYPTOGRAPHIC SYSTEM

As with Diffie-Hellman, the global elements of ElGamal are a prime number and ,whichis a
primitive root of .User A generates a private/public key pair as follows:
1. Generate a random integer XA , such that 1<XA < Q-1
2. Compute 𝑌A = 𝛼𝑋𝐴 𝑚o𝑑 𝑞
3. A’s private key is XA; A’s pubic key is {𝑞 , 𝛼 ,𝑌A}
Any user B that has access to A’s public key can encrypt a message as follows:
User A recovers the plaintext as follows:

User A generates a public/private key pair; user B encrypts using A’s public key; and
user A decrypts using her private key.

First, how 𝐾 is recovered by the decryption process:

Next, using𝐾 , we recover the plaintext as

Example:
Thus, 𝐾 functions as a one-time key, used to encrypt and decrypt the message. For example, let us
start with the prime field GF (19); that is, q 19. It has primitive roots {2, 3, 10, 13, 14, and 15}, as
shown in Table 8.3.We choose 𝛼 = 10.

Encryption:
Alice generates a key pair as follows:

Suppose Bob wants to send the message with the value M =17.Then,
Decryption:

If a message must be broken up into blocks and sent as a sequence of encrypted blocks, a unique
value of “k” should be used for each block. If is used for more than oneblock, knowledge of one block
m1of the message enables the user to compute other blocks as follows. Let

The security of Elgamal is based on the difficulty of computing discrete logarithms. To recover A’s
private key, an adversary would have to compute XA = dlog α,q(YA).