MODULE 2

Pseudorandom number Generator: Linear Congruential Generators.

 Pseudorandom number generation is an algorithm first proposed by Lehmer,
which is known as the linear congruential method.
 The algorithm is parameterized with four numbers, as follows:


 The sequence of random numbers {Xn} is obtained via the following iterative
equation:
 Xn+1 = (aXn + c) mod m
 If m, a, c, and X0 are integers, then this technique will produce a sequence of
inte gers with each integer in the range 0 … Xn 6 m.
 The selection of values for a, c, and m is critical in developing a good ran dom
number generator.
 For example, consider a = c = 1. The sequence produced is obviously not
satisfactory.
 Now consider the values a = 7, c = 0, m = 32, and X0 = 1. This generates the
sequence {7, 17, 23, 1, 7, etc.}, which is also clearly unsatisfactory. Of the 32
possible values, only four are used; thus, the sequence is said to have a period
of 4.
 If, instead, we change the value of a to 5, then the sequence is {5, 25, 29, 17,
21, 9, 13, 1, 5, etc. }, which increases the period to 8.
 A common criterion is that m be nearly equal to the maximum representable
nonnegative integer for a given computer. Thus, a value of m near to or equal
to 231 is typically chosen.
 Park proposes three tests to be used in evaluating a random number generator:
T1: The function should be a full-period generating function. That is, the
function should generate all the numbers from 0 through m- 1 before repeating.
T2: The generated sequence should appear random.

T3: The function should implement efficiently with 32-bit arithmetic.

 With appropriate values of a, c, and m, these three tests can be passed. With
respect to T1, it can be shown that if m is prime and c = 0, then for certain
values of a the period of the generating function is m- 1, with only the value 0
missing. For 32-bit arithmetic, a convenient prime value of m is 231- 1. Thus,
the generating function becomes.

Xn+1 = (aXn) mod (231- 1)

 The strength of the linear congruential algorithm is that if the multiplier and
modulus are properly chosen, the resulting sequence of numbers will be

1
Dept. of CSE(Data Science)
 MODULE 2

statistically indistinguishable from a sequence drawn at random (but without

replacement) from the set 1, 2, c , m- 1.
 If an opponent knows that the linear congruential algorithm is being used and if
the parameters are known (e.g., a = 75, c = 0, m = 231- 1), then once a single
number is discovered, all subsequent numbers are known.
 Even if the opponent knows only that a linear congruential algorithm is being
used, knowledge of a small part of the sequence is sufficient to determine the
parameters of the algorithm.
 Suppose that the opponent is able to determine values for X0, X1, X2, and X3.
Then

o
 These equations can be solved for a, c, and m.
 Thus, although it is nice to be able to use a good PRNG, it is desirable to make
the actual sequence used nonreproducible, so that knowledge of part of the
sequence on the part of an opponent is insufficient to determine future elements
of the sequence.

Blum Blum Shub Generator

Fig: Blum Blum Shub Block Diagram

 A popular approach to generating secure pseudorandom numbers is known as the
Blum Blum Shub (BBS) generator.
 The procedure is as follows. First, choose two large prime numbers, p and q, that
both have a remainder of 3 when divided by 4. That is,

 This notation, explained more fully in Chapter 4, simply means that (p mod 4) = (q
mod 4) = 3.

2
Dept. of CSE(Data Science)
 MODULE 2

 For example, the prime numbers 7 and 11 satisfy 7 K 11 K 3(mod 4). Let n = p * q.
Next, choose a random number s, such that s is relatively prime to n; this is
equivalent to saying that neither p nor q is a factor of s.
 Then the BBS genera tor produces a sequence of bits Bi according to the following
algorithm:

 Thus, the least significant bit is taken at each iteration. Table 8.1 shows an example
of BBS operation.
 Here, n = 192649 = 383 * 503, and the seed s = 101355.
 The BBS is referred to as a cryptographically secure pseudorandom bit generator
(CSPRBG).
 A pseudorandom bit generator is said to pass the next-bit test if there is not a
polynomial-time algorithm1 that, on input of the first k bits of an output sequence,
can predict the (k + 1)st bit with probability significantly greater than 1/2. In other
words, given the first k bits of the sequence, there is not a practical algorithm that
can even allow you to state that the next bit will be 1 (or 0) with probability greater
than 1/2.

Table : Example Operation of BBS Generator

Public Key cryptography and RSA:

3
Dept. of CSE(Data Science)
 MODULE 2

Principles of public key cryptosystems- 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.
1. It is computationally infeasible to determine the decryption key given only
knowledge of the cryptographic algorithm and the encryption key.
2. Either of the two related keys can be used for encryption, with the other
used for decryption.
3. Plaintext: This is the readable message or data that is fed into the algorithm
as input.
4. Encryption algorithm: The encryption algorithm performs various
transformations on the plaintext.

Figure 1(a) & (b): Public-Key Cryptograph

 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

4
Dept. of CSE(Data Science)
 MODULE 2

performed by the algorithm depend on the public or private key that is provided as
input.
 Ciphertext: This is the encrypted 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 decryp tion 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 mes sage
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.

Table1: Summarizes some of the important aspects of symmetric and public key encryption.

Table 1: Conventional and Public-Key Encryption

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

5
Dept. of CSE(Data Science)
 MODULE 2

Using Figure 2,

Figure 2: Public-Key Cryptosystem: Confidentiality

 There is some source A that produces a message in plaintext, X = [X1, X2, c , 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 cipher text Y =
[Y1, Y2, c , YN]:

Y = E(PUb , X)
 The intended receiver, in possession of the matching private key, is able to invert the
transformation:

X = D(PRb,Y)
 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 Xn.
 an attempt is made to recover PR b by generating an estimate PR b.

Figure 1(b) and Figure 3, show the use of public-key encryption to provide authentication:

6
Dept. of CSE(Data Science)
 MODULE 2

Figure 3: Public-Key Cryptosystem: Authentication

Y = E(PRa,X)

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 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 ciphertext 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.
 It is, however, possible to provide both the authentication function and confi dentiality
by a double use of the public-key scheme (Figure 4)

Z = E(PUb, E(PRa,X))
X = D(PUa, D(PRb,Z))

7
Dept. of CSE(Data Science)
 MODULE 2

Figure 4: Public-Key Cryptosystem: Authentication and Secrecy

 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 ciphertext 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.

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 sender’s private key or the receiver’s
public key, or both, to perform some type of cryptographic function.

In broad terms, we can classify the use of public-key cryptosystems into three categories
1. Encryption/decryption: The sender encrypts a message with the recipient’s public key,
and the recipient decrypts the message with the recipient’s private key.
2. 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.
3. Key exchange: Two sides cooperate to exchange a session key, which is a secret key
for symmetric encryption generated for use for a particular transaction (or session) and
valid for a short period of time.

8
Dept. of CSE(Data Science)
 MODULE 2

4. Some algorithms are suitable for all three applications, whereas others can be used only
for one or two of these applications mentioned in Table 1.

Table 1: Applications for Public-Key Cryptosystems

Requirements for Public key cryptography.

 Diffie and Hellman postulated this system without demonstrating that such algorithms
exist.
 It is computationally easy for a party B to generate a key pair (public key PUb, private
key PRb).
 It is computationally easy for a sender A, knowing the public key and the mes sage to
be encrypted, M, to generate the corresponding ciphertext:
C = E(PUb, M)
 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)]

 It is computationally infeasible for an adversary, knowing the public key, PUb, to
determine the private key, PRb.
 It is computationally infeasible for an adversary, knowing the public key, PUb, and a
ciphertext, C, to recover the original message, M.
 The two keys can be applied in either order:

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

 The requirements boil down to the need for a trap-door one-way function. 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, wherea s
the calculation of the inverse is infeasible:

Y = f(X) easy

X = f-1(Y) infeasible

 easy is defined to mean a problem that can be solved in polynomial time as a function
of input length.
 Thus, if the length of the input is n bits, then the time to compute the function is
proportional to na, where a is a fixed constant.

9
Dept. of CSE(Data Science)
 MODULE 2

 Such algorithms are said to belong to the class P. The term infeasible is a much fuzzier
concept.
 For example, if the length of the input is n bits and the time to compute the function is
proportional to 2n, the problem is considered infeasible.
 These measures are inadequate for cryptography, which requires that it be infeasible to
invert a function for virtually all inputs, not for the worst case or even average case.
 definition of a trap-door one-way function, which is easy to calculate in one direction
and infeasible to calculate in the other direction un less certain additional information
is known.
 We can summarize as follows: A trap door one-way function is a family of invertible
functions fk, such that
Y = fk(X) easy, if k and X are known
X = fk-1(Y) easy, if k and Y are known
X = fk-1(Y) infeasible, if Y is known but k is not known

Public Key Cryptanalysis

 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.
 Another form of attack is to find some way to compute the private key given the public
key.
 Thus, any given algorithm, including the widely used RSA algorithm, is suspect.
 The history of cryptanalysis shows that a problem that seems insoluble from one
perspective can be found to have a solution if looked at in an entirely different way.
 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-bit
DES 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.

10
Dept. of CSE(Data Science)
 MODULE 2

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 supreme as 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 block size 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.

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

the following requirements must be met.

1. It is possible to find values of e, d, and n such that Med mod n = M for all M 6 n.

2. It is relatively easy to calculate Me mod n and Cd mod n for all values of M 6 n.

3. It is infeasible to determine d given e and n.

We need to find a relationship of the form

Med mod n = M

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 ∅ (n) = 1

This is equivalent to saying

11
Dept. of CSE(Data Science)
 MODULE 2

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 ∅ (n).

We are now ready to state the RSA [Link] ingredients are the following:

The private key consists of {d, n} and the public key consists of {e, n}. Suppose that user A
has published its public key and that user B wishes to send the message M to A. Then B
calculates C = Me mod n and transmits C. On receipt of this ci phertext, user A decrypts by
calculating M = Cd mod n.

Example:
Alice generates a public/private key pair; Bob encrypts using Alice’s public key; and Alice
decrypts using her private key. An example from [SING99] is shown in Figure 1. For this
example, the keys were generated as follows.

Figure 1: Example of RSA Algorithm

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 = 887 mod 187. we can do this as follows.

12
Dept. of CSE(Data Science)
 MODULE 2

In this simple example, the plaintext is an alpha numeric string. Each plaintext symbol is
assigned a unique code of two decimal digits (e.g., a = 00, A = 26).6 A plaintext block consists
of four decimal digits, or two alphanumeric characters.
Figure 2(a) illustrates the sequence of events for the encryption of multiple blocks, and Figure
2(b) gives a specific example. The circled numbers indicate the order in which operations are
performed.

13
Dept. of CSE(Data Science)
 MODULE 2

Figure 2(a) and 2(b) : RSA Processing of Multiple Blocks

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.

EXPONENTIATION IN MODULAR ARITHMETIC

 Both encryption and decryption in RSA involve raising an integer to an integer power,
mod n. If the exponentiation is done over the integers and then reduced modulo n, the
intermediate values would be gargantuan.
 we can make use of a property of modular arithmetic:

[(a mod n) * (b mod n)] mod n = (a * b) mod n

 Thus, we can reduce intermediate results modulo n. This makes the calculation
practical.
 To see how efficiency might be in creased, consider that we wish to compute x16. A
straightforward approach requires 15 multiplications:

x16 = x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x

 Example: suppose we wish to calculate x11 mod n for some integers x and n. Observe
that x11 = x1+2+8 = (x)(x2)(x8). In this case, we compute x mod n, x2 mod n, x4 mod n,
and x8 mod n and then calculate [(x mod n) * (x2 mod n) * (x8 mod n)] mod n.
 suppose we wish to find the value ab mod n with a, b, and m positive integers. If we
express b as a binary number bk bk-1………… b0, then we have

 Figure 1 & Table shows an example of the execution of this algorithm. Note that the
variable c is not needed; it is included for explanatory purposes. The final value of c is
the value of the exponent.

14
Dept. of CSE(Data Science)
 MODULE 2

Table: Result of the Fast Modular Exponentiation Algorithm for ab mod n, where a = 7, b =
560 = 1000110000, and n = 561

Figure1: Algorithm for Computing ab mod n

EFFICIENT OPERATION USING THE PUBLIC KEY

 To speed up the operation of the RSA algorithm using the public key, a specific choice
of e is usually made.
 The most common choice is 65537 (216 + 1); two other popular choices are 3 and 17.
Each of these choices has only two 1 bits, so the number of multiplications required to
perform exponentiation is minimized.
 However, with a very small public key, such as e = 3, RSA becomes vulner able to a
simple attack.
 Suppose we have three different RSA users who all use the value e = 3 but have unique
values of n, namely (n1, n2, n3). If user A sends the same encrypted message M to all
three users, then the three ciphertexts are C 1 = M3 mod n1, C2 = M3 mod n2 , and C3 =
M3 mod n3 . It is likely that n1, n2, and n3 are pairwise relatively prime.
 Therefore, one can use the Chinese remainder theorem (CRT) to compute M 3 mod
(n1 n2n3 ). By the rules of the RSA algorithm, M is less than each of the ni; therefore M 3
< n1 n2n3 .
 Accordingly, the attacker need only compute the cube root of M3. This attack can be
countered by adding a unique pseudorandom bit string as padding to each instance of
M to be encrypted.

EFFICIENT OPERATION USING THE PRIVATE KEY:

A small value of d is vulnerable to a brute-force attack and to other forms of cryptanalysis.
However, there is a way to speed up computation using the CRT. We wish to compute the value
M = Cd mod n. Let us define the following intermediate results:

15
Dept. of CSE(Data Science)
 MODULE 2

Following the CRT using Equation (8.8), define the quantities

The CRT then shows, using Equation (8.9), that

we can simplify the calculation of Vp and Vq using Fermat’s theorem, which states that ap-1 =1
(mod p) if p and a are relatively prime. Some thought should convince you that the following
are valid.

The quantities d mod (p- 1) and d mod (q- 1) can be precalculated. The end result is that the
calculation is approximately four times as fast as evaluating M = C d mod n directly.

KEY GENERATION
Before the application of the public-key cryptosystem, each par ticipant must generate a pair
of keys. This involves the following tasks.

1. Determining two prime numbers, p and q.

2. Selecting either e or d and calculating the other

First, consider the selection of p and q. Because the value of n = pq will be known to any
potential adversary, in order to prevent the discovery of p and q by exhaustive methods, these
primes must be chosen from a sufficiently large set (i.e., p and q must be large numbers).
At present, there are no useful techniques that yield arbitrarily large primes, so some other
means of tackling the problem is needed.
The procedure that is generally used is to pick at random an odd number of the desired order
of magnitude and test whether that number is prime.
the procedure for picking a prime number is as follows
1. Pick an odd integer n at random (e.g., using a pseudorandom number generator).
2. Pick an integer a 6 n at random.
3. Perform the probabilistic primality test, such as Miller–Rabin, with a as a parameter. If
n fails the test, reject the value n and go to step 1.
4. If n has passed a sufficient number of tests, accept n; otherwise, go to step 2.
However, remember that this process is per formed relatively infrequently: only when a new
pair (PU, PR) is needed.

16
Dept. of CSE(Data Science)
 MODULE 2

Example: For example, if a prime on the order of magnitude of 2200 were sought, then about
ln(2200)/2 = 70 trials would be needed to find a prime.

The Security for 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.

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

17
Dept. of CSE(Data Science)
 MODULE 2

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

18
Dept. of CSE(Data Science)
 MODULE 2

Figure: Encryption Using 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 with
the seed to produce the masked seed.
 The concatenation of the masked seed and the maskedDB forms the encoded message
EM.
 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.

19
Dept. of CSE(Data Science)
 MODULE 2

Diffie-Hellman Key Exchange:

The purpose of the algorithm is to enable two users to securely exchange a key that 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.

The Algorithm:

Figure 1: The Diffie–Hellman Key Exchange

The Diffie–Hellman key exchange algorithm.

For this scheme, there are two publicly known numbers: a prime number q and an integer a that
is a primitive root of q. Suppose the users A and B wish to create a shared key.
User A selects a random integer XA< 6 and computes YA = a XA mod q. Similarly, user B
independently selects a random integer X B < 6 and computes YB = a XB mod q.
Each side keeps the X value private and makes the Y value avail able publicly to the other side.
Thus, XA is A’s private key and YA is A’s correspond ing public key, and similarly for B.

User A computes the key as K = (Y B)XA mod q and user B computes the key as K = (Y A)XB
mod q. These two calculations produce identical results:

20
Dept. of CSE(Data Science)
 MODULE 2

Now consider an adversary who can observe the key exchange and wishes to determine the
secret key K.
Because XA and XB are private, an adversary only has the following ingredients to work with:
q, a, YA, and YB.
Thus, the adversary is forced to take a discrete logarithm to deter mine the key. For example,
to determine the private key of user B, an adversary must compute.

The adversary can then calculate the key K in the same manner as user B calculates it. That is,
the adversary can calculate K as

The security of the Diffie–Hellman key exchange lies in the fact that, while it is relatively easy
to calculate exponentials modulo a prime, it is very difficult to calculate discrete logarithms.
Example: Key exchange is based on the use of the prime number q = 353 and a primitive root
of 353, in this case a = 3. A and B select private keys XA = 97 and XB = 233, respectively. Each
computes its public key:

Key exchange Protocols:

 Figure Shows a simple protocol that makes use of the Diffie–Hellman calculation.
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 pri vate key XA, calculate YA, and send that to user B.
 User B responds by generating a private value X B, calculating YB, and sending Y B to
user A.

21
Dept. of CSE(Data Science)
 MODULE 2

 Both users can now calculate the key. The necessary public values q and a would need
to be known ahead of time. Alternatively, user A could pick values for q and a and
include those in the first message.
 As an example of another use of the Diffie–Hellman algorithm, suppose that a group of
users (e.g., all users on a LAN) each generate a long-lasting private value Xi (for user
i) and calculate a public value Yi.
 These public values, together with global public values for q and a, are stored in some
central directory. At any time, user j can access user i’s public value, calculate a secret
key, and use that to send an encrypted message to user A.
 Because only i and j can determine the key, no other user can read the message
(confidential ity). Recipient i knows that only user j could have created a message using
this key (authentication). However, the technique does not protect against replay
attacks.

Man in the middle attack:

Figure : Man-in-the-Middle Attack

1. Darth prepares for the attack by generating two random private keys XD1 and XD2 and then
computing the corresponding public keys Y D1 and YD2.

22
Dept. of CSE(Data Science)
 MODULE 2

2. Alice transmits YA to Bob.

3. Darth intercepts YA and transmits YD1 to Bob. Darth also calculates K2 = (Y A)XD2 mod q.
4. Bob receives YD1 and calculates K1 = (YD1) XB mod q.

5. Bob transmits YB to Alice.

6. Darth intercepts Y B and transmits YD2 to Alice. Darth calculates K1 = (Y B)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 key exchange protocol is vulnerable to such an attack because it does not authenticate the
participants.

ELLIPTIC CURVE CRYPTOGRAPHY

Consider the equation Q = kP where Q, P ∈ EP(a, b) and k 6 p. It is rela tively easy to calculate
Q given k and P, but it is hard to determine k given Q and P. This is called the discrete logarithm
problem for elliptic curves.
This is the group defined by the equation y2 mod 23 = (x3 + 9x + 17) mod 23. What is the
discrete logarithm k of Q = (4, 5) to the base P = (16, 5)? The brute-force method is to compute
multiples of P until Q is found. Thus,

Because 9P = (4, 5) = Q, the discrete logarithm Q = (4, 5) to the base P = (16, 5) is k = 9. In a

real application, k would be so large as to make the brute force approach infeasible.

ANALOG OF DIFFIE-HELLMAN KEY EXCHANGE:

Key exchange using elliptic curves can be done in the following manner.

23
Dept. of CSE(Data Science)
 MODULE 2

First pick a large integer q, which is either a prime number p or an integer of the form 2m, and
elliptic curve parameters a and b.
This defines the elliptic group of points Eq(a, b). Next, pick a base point G = (x1, y1) in Ep(a,
b) whose order is a very large value n.
The order n of a point G on an elliptic curve is the smallest positive integer n such that nG = 0
and G are parameters of the cryptosystem known to all participants.

A key exchange between users A and B can be accomplished as follows

Figure: ECC Diffie–Hellman Key Exchange

1. A selects an integer nA less than n. This is A’s private key. A then generates a public key PA
= nA * G; the public key is a point in Eq(a, b).

2. B similarly selects a private key nB and computes a public key P B.

3. A generates the secret key k = nA * PB. B generates the secret key k = nB * PA

The two calculations in step 3 produce the same result because

To break this scheme, an attacker would need to be able to compute k given G and kG, which
is assumed to be hard.

24
Dept. of CSE(Data Science)
 MODULE 2

Elliptic Curve Encryption/ Decryption

The first task in this system is to encode the plaintext message m to be sent as an (x, y) point
Pm.

It is the point Pm that will be encrypted as a ciphertext and subsequently decrypted.

Note that we cannot simply encode the message as the x or y coordinate of a point, because not
all such coordinates are in Eq(a, b); for example, see Table.

Table: Comparable Key Sizes in Terms of Computational Effort for Cryptanalysis

(NIST SP-800-57)
As with the key exchange system, an encryption/decryption system requires a point G and an
elliptic group Eq(a, b) as parameters. Each user A selects a private key nA and generates a
public key PA=nA *G.
To encrypt and send a message Pm to B, A chooses a random positive integer k and produces
the ciphertext Cm consisting of the pair of points:

Note that A has used B’s public key PB. To decrypt the ciphertext, B multiplies the first point
in the pair by B’s private key and subtracts the result from the second point:

Example:

25
Dept. of CSE(Data Science)
 MODULE 2

Security of Elliptic Curve Cryptography

 The security of ECC depends on how difficult it is to determine k given kP and P. This
is referred to as the elliptic curve logarithm problem.
 The fastest known technique for taking the elliptic curve logarithm is known as the
Pollard rho method.
 Based on this analysis, SP 800-57 recommends that at least through 2030, ac ceptable
key lengths are from 3072 to 14,360 bits for RSA and 256 to 512 bits for ECC.
 Similarly, the European Union Agency for Network and Information Security (ENISA)
recommends in their 2014 report (Algorithms, Key Size and Parameters report—2014,
November 2014) minimum key lengths for future system of 3072 bits and 256 bits for
RSA and ECC, respectively.
 Analysis indicates that for equal key lengths, the computational effort re quired for ECC
and RSA is comparable. Thus, there is a computational advantage to using ECC with a
shorter key length than a comparably secure RSA.

******************************* THANK YOU *******************************

26
Dept. of CSE(Data Science)