Internet.Security

162 INTERNET SECURITY

Calculation of Y from X is comparatively easy, using repeated squaring, but computation of X from Y is typically far more difficult.

Suppose the user i chooses a random integer Xi and the user j a random integer Xj . Then the user i picks a random number Xi from the integer set {1, 2, . . . , q − 1}. The user i keeps Xi secret, but sends

Yi ≡ αXi (mod q)

to the user j . Similarly, the user j chooses a random integer Xj and sends

Yj ≡ αXj (mod q)

to the user i.

Both users i and j can now compute:

Kij ≡ αXiXj (mod q)

and use Kij as their common key.

The user i computes Kij by raising Yj to the power Xi :

Kij ≡ YjXi (mod q)

≡(αXj )Xi (mod q)

≡αXjXi ≡ αXiXj (mod q)

and the user j computes Kij in a similar fashion:

Kij ≡ YiXj (mod q)

≡ (αXi )Xj ≡ αXiXj (mod q)

Thus, both users i and j have exchanged a secret key. Since Xi and Xj are private, the only available factors are the public values q, α, Yi and Yj . Therefore the opponent is forced to compute a discrete logarithm which is considered to be unrealistic, particularly for large primes. Figure 5.1 illustrates the Diffie – Hellman key exchange scheme.

When utilising finite field GF(q), where q is either a prime or q = 2k , it is necessary to ensure the q − 1 factor has a large prime, otherwise it is easy to find discrete logarithms in GF(q).

Example 5.1 Consider a prime field Zq where q is a prime modulus. If α is a primitive root of the modulus q, then α generates the set of nonzero integer modulo q such that α, α2, . . . , αq−1. These powers of α are all distinct and are all relatively prime to q. Given α, 1 α q − 1, and q = 11, all the primitive elements of q are computed as shown in Table 5.1.

For the modulus q = 11, the primitive elements are α = 2, 6, 7 and 8 whose order is 10, respectively.

Example 5.2 Consider a finite field GF(q) of a prime q. Choose a primitive element α = 2 of the modulus q = 11.

164 INTERNET SECURITY

Compute:

Yi ≡ αXi (mod q)

≡ 25 (mod 11) ≡ 10

to the user j . Similarly, the user j chooses a random number Xj = 7 and sends

Yj ≡ αXj (mod q)

≡ 27 (mod 11) ≡ 7

to the user i.

Finally, compute their common key Kij as follows:

Kij ≡ YjXi (mod q)

≡ 75 (mod 11) ≡ 10

and

Kji ≡ YiXj (mod q)

≡ 107 (mod 11) ≡ 10

Thus, each user computes the common key.

which is the product of two primes:

n = pq

Choose the encryption key e such that e and φ(n) are coprime, i.e. gcd (e, φ(n)) = 1, in which φ(n) = (p − 1)(q − 1) is called Euler’s totient function.

Using euclidean algorithm, the private key d for decryption can be computed by taking the multiplicative inverse of e such that

d ≡ e−1 (mod φ(n))

or ed ≡ 1 (mod φ(n))

The decryption key d and the modulus n are also relatively prime. The numbers e and n are called the public keys, while the number d is called the private key.

To encrypt a message m, the ciphertext c corresponding to the message block can be found using the following encryption formula:

c ≡ me (mod n)

To decrypt the ciphertext c, c is raised to the power d in order to recover the message m as follows:

m ≡ cd (mod n)

It is proved that

cd ≡ (me)d ≡ med ≡ m (mod n)

due to the fact that ed ≡ 1 (mod φ(n)).

Because Euler’s formula is mφ(n) ≡ 1 (mod n), the message m is relatively prime to n such that gcd (m, n) = 1. Since mλ φ(n) ≡ 1 (mod n) for some integer λ, it can be written mλ φ(n)+1 ≡ m (mod n), because mλ φ(n)+1 ≡ mmλ φ(n) ≡ m (mod n). Thus, the message m can be restored.

Figure 5.2 and Table 5.3 illustrate the RSA algorithm for encryption and decryption. Using Table 5.3, the following examples are demonstrated.

Example 5.4 If p = 17 and q = 31 are chosen, then n = pq = 17 × 31 = 527

φ(n) = (p − 1)(q − 1) = 16 × 30 = 480

If e = 7 is chosen, then compute: d ≡ e−1 (mod φ(n)) ≡ 7−1

This decryption key d is calculated using the extended euclidean algorithm.

ed ≡ 7 × 343 (mod 480) ≡ 2401 (mod 480) ≡ 1

Figure 5.2 RSA public-key cryptosystem for encryption/decryption.

Table 5.3 RSA encryption algorithm

Public key e:

n (product of two primes p and q (secret integers))

e (encryption key, relatively prime to φ(n) = (p − 1) (q − 1)) Private key d:

d (decryption key, d = e−1 (mod φ(n)) ed ≡ 1 (mod φ(n))

Encryption:

c ≡ me (mod n), where m is a plaintext. Decryption:

m ≡ cd (mod n), where c is a ciphertext.

The public key (e, n) is required for encryption of m. If m = 2, then the message m is encrypted as:

c ≡ me (mod n)

≡ 27 (mod 527) ≡ 128

To decipher, the private key d is needed to compute the message as follows:

m ≡ cd (mod n)

≡ 128343 (mod 527) ≡ 2

Example 5.5 If p = 47 and q = 71, then compute

n = pq = 47 × 71 = 3337

φ(n) = (p − 1)(q − 1) = 46 × 70 = 3220

Choose the encryption key e = 79 randomly such that gcd (e, φ(n)) = gcd (79, 3220) = 1, i.e. e and φ(n) are relatively prime. Using the extended euclidean algorithm (i.e. gcd (e, φ(n)) = 1 = ed + φ(n)s), compute the decryption key d such that:

ed ≡ 1 (mod φ(n))

79d ≡ 1 (mod 3220)

3220 = 79 × 40 + 60

79 = 60 + 19

60 = 19 × 3 + 3

19 = 3 × 6 + 1 → gcd(79, 3220) = 1 (coprime)

1 = 19 − 3 × 6 = 19 − (60 − 19 × 3) × 6

=19 × 19 − 60 × 6 1 = (79 − 60) × 19 − 60 × 6

=79 × 19 − 60 × 25

1 = 79 × 19 − (3220 − 79 × 40) × 25

= 79 × 1019 − 3220 × 25

(79)(1019) ≡ 1 (mod 3220)

d = 1019 (privatekey)

To encrypt a message m = 688 with e = 79, compute: c ≡ me (mod n) ≡ 68879 (mod 3337)

6882 (mod 3337) ≡ 2827, 6884 (mod 3337) ≡ 3151 6888 (mod 3337) ≡ 1226, 68816 (mod 3337) ≡ 1426 68832 (mod 3337) ≡ 1243, 68864 (mod 3337) ≡ 18

c≡ 68879 (mod 3337) ≡ 68864+8+4+2+1

≡18 × 1426 × 3151 × 2827 × 688 (mod 3337)

≡1570 (mod 3337)

To decrypt a message, perform the same exponentiation process using the decryption key d = 1019 such that:

m ≡ cd (mod n) ≡ 15701019 (mod 3337)

m = (1570)512 × (1570)256 × (1570)128 × (1570)64 × (1570)32

×(1570)16 × (1570)8 × (1570)2 × (1570)

=3925000 (mod 3337) ≡ 688

Thus, the message is recovered.

To encrypt the message m, break it into a series of mi -digit blocks, 1 i n − 1. Suppose each character in the message is represented by a two-digit number as shown in Table 5.4.

Example 5.6 Encode the message ‘INFORMATION SECURITY’ using Table 5.4.

m = (0914061518130120091514001905032118092025)

Choose p = 47 and q = 71. Then

n = pq = 47 × 71 = 3337

φ(n) = (p − 1)(q − 1) = 46 × 70 = 3220

Break the message m into blocks of four digits each:

Choose the encryption key e = 79. Then the decryption key d becomes: d ≡ e−1 (mod φ(n)) ≡ 79−1 (mod 3220) ≡ 1019

The first block, m1 = 914, is encrypted by raising it to the power e = 79 and dividing by n = 3337 and taking the remainder c1 = 3223 as the first block of ciphertext:

c1 ≡ me1 (mod n)

≡91479 (mod 3337)

≡3223

Table 5.4 Two-digit number representing each character