MODULE 2

PSEUDORANDOM NUMBER GENERATORS

Linear Congruential Generators

A widely used technique for pseudorandom number generation is an algorithm first proposed by
Lehmer [LEHM51], which is known as the linear congruential method. The algorithm is
parameterized with four numbers, as follows:
These equations can be solved for a, c, and m.

Blum Blum Shub Generator

A popular approach to generating secure pseudorandom numbers is known as the Blum Blum Shub
(BBS) generator (see Figure 8.3), named for its developers [BLUM86]. It has perhaps the strongest
public proof of its cryptographic strength of any purpose-built algorithm. 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,
 p = q = 3(mod 4)

This notation, explained more fully in Chapter 4, simply means that (p mod 4) = (q mod 4) = 3. 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 CSPRBG is defined as one that passes the next-bit test, which, in turn, is defined as follows:

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. For all practical purposes, the sequence is unpredictable. The security
of BBS is based on the difficulty of factoring n. That is, given n, we need to determine its two
prime factors p and q.
 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.
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.

Key distribution under symmetric encryption requires either

(1) That two communicants already share a key, which somehow has been distributed to them or

(2) The use of a key distribution centre.

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 is digital 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. 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.

Anyone knowing the public key can encrypt messages or verify signatures, but cannot decrypt
messages or create signatures.

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 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 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.
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.
Public-Key Cryptosystems: Confidentiality

Source A 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 PU b 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)

An adversary, observing Y and having access to PUb, but not having access to PRb, or X, must
attempt to recover X and/or PUb,. 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 ^X Often,
however, the adversary is interested in being able to read future messages as well, in which case an
attempt is made to recover PUb, by generating an estimate P^Rb..

Public-Key Cryptosystem: Authentication

Figure shows the use of public-key encryption to provide authentication:

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

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. It is impossible to alter the message without access to A’s private key, so the
message is authenticated both in terms of source and in terms of data integrity.
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 important to emphasize that the encryption process in Figures 9.3, does not provide
confidentiality. That is, the message being sent is safe from alteration but not from eavesdropping,
because any observer can decrypt the message by using the sender’s public key.

Public-Key Cryptosystem: Authentication and Secrecy

It is possible to provide both the authentication function and confidentiality by a double use of the
public-key scheme Figure 9.4:
Z = E (PUb, E (PRa,X))
X = D (PUa, D (PRb,Z))

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

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 keys of one or both the parties.

Requirements for Public-Key Cryptography

1. It is computationally easy for a party B to generate a 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 cipher text:
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 all public-key
applications:
6. The two keys can be applied in either order:
M = D[PUb, E(PRb, M)] = D[PRb, E(PUb, M)]
The requirements essentially focus on the necessity of a trap-door one-way function. A one-way
function3 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
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. Such algorithms are said to belong to the class P.
The term infeasible is a much fuzzier concept. In general, we can say a problem is infeasible if the
effort to solve it grows faster than polynomial time as a function of input size. 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.
A trap-door one-way function, which is easy to calculate in one direction and infeasible to
calculate in the other direction unless certain additional information is known. With the additional
information the inverse can be calculated in polynomial time. We can summarize as follows: A
trapdoor 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

Thus, the development of a practical public-key scheme depends on discovery of a suitable trap-
door one-way function.
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-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.

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 2 1024 .

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 log 2 (n) + 1. Encryption and decryption are of the following form, for some plaintext
block M and ciphertext block C.
e
C = M mod n
d d
M = C mod n = (Me) 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 publickey 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.

ed
1. It is possible to find values of e, d, and n such that M mod n = M for all M < n.
e
2. It is relatively easy to calculate M 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
ed
M mod n = M
The preceding relationship holds if e and d are multiplicative inverses modulo f(n), where f(n) is
the Euler totient function. It is shown in Chapter 2 that for p, q prime, f(pq) = (p - 1)(q - 1). The
relationship between e and d can be expressed as
ed mod f(n) =1
This is equivalent to saying
ed =1 mod f(n)
d = e-1 mod f(n)
That is, e and d are multiplicative inverses mod f(n).

We are now ready to state the RSA scheme. The ingredients are the following:
p, q, two prime numbers (private, chosen)
n = pq (public, calculated)
e, with gcd(Ф(n), e) = 1; 1 <e < Ф (n) (public, chosen)
d = e-1 (mod Ф (n)) (private, calculated)
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 ciphertext, 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. 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 Ф(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 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 = [(884 mod 187) * (882 mod 187) * (881 mod 187)] mod 187
881 mod 187 = 88
882 mod 187 = 7744 mod 187 = 77
884 mod 187 = 59,969,536 mod 187 = 132
887 mod 187 = (88 * 77 * 132) mod 187 = 894,432 mod 187 = 11
For decryption, we calculate M = 1123 mod 187:
1123 mod 187 = [(111 mod 187) * (112 mod 187) * (114 mod 187)* (118 mod 187) * (118 mod 187)]
mod 187
111 mod 187 = 11
112 mod 187 = 121
114 mod 187 = 14,641 mod 187 = 55
118 mod 187 = 214,358,881 mod 187 = 33
1123 mod 187 = (11 * 121 * 55 * 33 * 33) mod 187
= 79,720,245 mod 187 = 88
Figure 9.5 summarizes the RSA algorithm.
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.
Let us look first at the process of encryption and decryption and then consider 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. Fortunately, as the preceding example shows, 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.
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 vulnerable 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 C1 = 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 M3 mod (n1n2n3). By the rules of the RSA algorithm, M is less than each of the ni;
therefore M3 6 n1n2n3. 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
We cannot similarly choose a small constant value of d for efficient operation. 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:
Vp = Cd mod p Vq = Cd mod q
Following the CRT, define the quantities

Xp = q * (q-1 mod p) Xq = p * (p-1 mod q)

The CRT then shows, using Equation (8.9), that
M = (VpXp + VqXq) mod n

KEY GENERATION
 Before the application of 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 primality
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

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 defence against the brute approach is 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.
1. Factor n into its two prime factors. This enables calculation of Ф(n) = (p - 1) * (q - 1), which in
turn enables determination of d =e-1 (mod Ф(n)).
2. Determine Ф (n) directly, without first determining p and q. Again, this enables determination of
d =e-1 (mod Ф(n)).
3. Determine d directly, without first determining Ф(n).
Determining f(n) 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 the order of magnitude 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 ciphertex tonly attack.
The timing attack is a serious threat, there are simple countermeasures that can be used, including
the following.
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)
  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 masked DB.

 The masked DB 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 masked DB forms the encoded message EM.
 Note that the EM includes the padded message, masked by the seed, and the seed, masked
by the masked DB. The EM is then encrypted using RSA.
Diffie-Hellman key Exchange
Figure 10.1 summarizes 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.
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 through
p - 1 in some permutation.
Example:
3 is primitive root of 7.
The Algorithm
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 < q and
computes YA = αXA mod q. Similarly, user B independently selects a random integer XB < q and
computes YB = αXB mod q.
Each side keeps the X value private and makes the Y value available publicly to the other side.
Thus, XA is
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:
K = (YB)XA mod q
= (αXB mod q)XA mod q
= (αXB)XA mod q
= αXBXA mod q
= (αXA)XB mod q
= (αXA mod q)XB mod q
= (YA)XB mod q

Here is an 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:

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 = 160.
We assume an attacker would have available the following information:
q = 353; α = 3; YA = 40; YB = 248
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