Page 326 - Discrete Mathematics and Its Applications

4.6 Cryptography 305

20. Express the Vigenère cipher as a cryptosystem. 29. Describe the steps that Alice and Bob follow when they use

To break aVigenère cipher by recovering a plaintext message from the Diffie-Hellman key exchange protocol to generate a shared
the ciphertext message without having the key, the first step is to key. Assume that they use the prime p = 23 and take a = 5,
figure out the length of the key string. The second step is to figure which is a primitive root of 23, and that Alice selects k 1 = 8
out each character of the key string by determining the correspond- and Bob selects k 2 = 5. (You may want to use some compu-
ing shift. Exercises 21 and 22 deal with these two aspects. tational aid.)
21. Suppose that when a long string of text is encrypted using 30. Describe the steps that Alice and Bob follow when they use
a Vigenère cipher, the same string is found in the ciphertext the Diffie-Hellman key exchange protocol to generate a shared
starting at several different positions. Explain how this infor- key. Assume that they use the prime p = 101 and take a = 2,
mation can be used to help determine the length of the key. which is a primitive root of 101, and that Alice selects k 1 = 7
and Bob selects k 2 = 9. (You may want to use some compu-
22. OncethelengthofthekeystringofaVigènerecipherisknown, tational aid.)
explain how to determine each of its characters. Assume that
the plaintext is long enough so that the frequency of its let- In Exercises 31–32 suppose that Alice and Bob have these
ters is reasonably close to the frequency of letters in typical public keys and corresponding private keys: (n Alice ,e Alice ) =
English text. (2867, 7) = (61 · 47, 7), d Alice = 1183 and (n Bob ,e Bob ) =
(3127, 21) = (59 · 53, 21), d Bob = 1149. First express your an-
∗ 23. Show that we can easily factor n when we know that n is the swers without carrying out the calculations. Then, using a com-
product of two primes, p and q, and we know the value of putational aid, if available, perform the calculation to get the
(p − 1)(q − 1).
numerical answers.
In Exercises 24–27 first express your answers without computing
modular exponentiations. Then use a computational aid to com- 31. Alice wants to send to all her friends, including Bob, the mes-
plete these computations. sage “SELL EVERYTHING” so that he knows that she sent
it. What should she send to her friends, assuming she signs
24. Encrypt the message ATTACK using the RSA system with the message using the RSA cryptosystem.
n = 43 · 59 and e = 13, translating each letter into integers
and grouping together pairs of integers, as done in Example 32. Alice wants to send to Bob the message “BUY NOW” so that
8.
he knows that she sent it and so that only Bob can read it.What
25. Encrypt the message UPLOAD using the RSA system with should she send to Bob, assuming she signs the message and
n = 53 · 61 and e = 17, translating each letter into integers then encrypts it using Bob’s public key?
and grouping together pairs of integers, as done in Example
8. 33. We describe a basic key exchange protocol using private key
cryptography upon which more sophisticated protocols for
26. What is the original message encrypted using the RSA sys- key exchange are based. Encryption within the protocol is
tem with n = 53 · 61 and e = 17 if the encrypted message is done using a private key cryptosystem (such as AES) that is
3185 2038 2460 2550? (To decrypt, first find the decryption considered secure. The protocol involves three parties, Alice
exponent d, which is the inverse of e = 17 modulo 52 · 60.) and Bob, who wish to exchange a key, and a trusted third party
Cathy. Assume that Alice has a secret key k Alice that only she
27. What is the original message encrypted using the RSA system
and Cathy know, and Bob has a secret key k Bob which only he
with n = 43 · 59 and e = 13 if the encrypted message is 0667
and Cathy know. The protocol has three steps:
1947 0671? (To decrypt, first find the decryption exponent d
which is the inverse of e = 13 modulo 42 · 58.) (i) Alice sends the trusted third party Cathy the message “re-
quest a shared key with Bob” encrypted using Alice’s key
∗ 28. Suppose that (n, e) is an RSA encryption key, k Alice .
with n = pq where p and q are large primes and
(ii) Cathy sends back to Alice a key k Alice,Bob , which she gen-
gcd(e, (p − 1)(q − 1)) = 1. Furthermore, suppose that d
erates, encrypted using the key k Alice , followed by this same
is an inverse of e modulo (p − 1)(q − 1). Suppose that
e
C ≡ M (mod pq). In the text we showed that RSA de- key k Alice,Bob , encrypted using Bob’s key, k Bob .
d
cryption, that is, the congruence C ≡ M(mod pq) holds
(iii)Alice sends to Bob the key k Alice,Bob encrypted using k Bob ,
when gcd(M, pq) = 1. Show that this decryption congruence
known only to Bob and to Cathy.
also holds when gcd(M, pq) > 1. [Hint: Use congruences
modulo p and modulo q and apply the Chinese remainder Explain why this protocol allows Alice and Bob to share
theorem.] the secret key k Alice,Bob , known only to them and to Cathy.