Page 330 - Discrete Mathematics and Its Applications

Computer Projects 309

the congruence 3(d 1 + d 4 + d 7 ) + 7(d 2 + d 5 + d 8 ) + (d 3 + keystream, after the first, is the previous letter of the plaintext.
d 6 + d 9 ) ≡ 0 (mod 10) must hold. When the ciphertext is used, each subsequent character of the
keystream, after the first, is the previous letter of the ciphertext
45. Show that if d 1 d 2 ...d 9 is a valid RTN, then d 9 = 7(d 1 +
d 4 + d 7 ) + 3(d 2 + d 5 + d 8 ) + 9(d 3 + d 6 ) mod 10. Fur- computed so far. In both cases, plaintext letters are encrypted
thermore, use this formula to find the check digit that by shifting each character by the numerical equivalent of the
follows the eight digits 11100002 in a valid RTN. corresponding keystream letter.
46. Show that the check digit of an RTN can detect all single 48. Use the autokey cipher to encrypt the message NOW IS
errors and determine which transposition errors an RTN THE TIME TO DECIDE (ignoring spaces) using
check digit can catch and which ones it cannot catch. a) the keystream with seed X followed by letters of the
47. The encrypted version of a message is LJMKG MG- plaintext.
MXF QEXMW. If it was encrypted using the affine ci- b) the keystream with seed X followed by letters of the
pher f(p) = (7p + 10) mod 26, what was the original ciphertext.
message? 49. Use the autokey cipher to encrypt the message THE
Autokey ciphers are ciphers where the nth letter of the plain- DREAM OF REASON (ignoring spaces) using
text is shifted by the numerical equivalent of the nth letter of a) the keystream with seed X followed by letters of the
a keystream. The keystream begins with a seed letter; its sub- plaintext.
sequent letters are constructed using either the plaintext or the b) the keystream with seed X followed by letters of the
ciphertext. When the plaintext is used, each character of the ciphertext.

Computer Projects

Write programs with these inputs and outputs.

1. Given integers n and b, each greater than 1, find the base 14. Given a message and a positive integer k less than 26,
b expansion of this integer. encrypt this message using the shift cipher with key k;
2. Given the positive integers a, b, and m with m> 1, find and given a message encrypted using a shift cipher with
b
a mod m. key k, decrypt this message.
3. Given a positive integer, find the Cantor expansion of this 15. Given a message and positive integers a and b less than
integer (see the preamble to Exercise 48 of Section 4.2). 26 with gcd(a, 26), encrypt this message using an affine
4. Given a positive integer, determine whether it is prime cipher with key (a, b); and given a message encrypted us-
using trial division. ing the affine cipher with key (a, b), decrypt this message,
by first finding the decryption key and then applying the
5. Given a positive integer, find the prime factorization of
appropriate decryption transformation.
this integer.
16. Find the original plaintext message from the ciphertext
6. Given two positive integers, find their greatest common
message produced by encrypting the plaintext message
divisor using the Euclidean algorithm.
using a shift cipher. Do this using a frequency count of
7. Given two positive integers, find their least common mul-
letters in the ciphertext.
tiple.
∗ 17. Construct a valid RSA encryption key by finding two
8. Given positive integers a and b, find Bézout coefficients
primes p and q with 200 digits each and an integer e> 1
s and t of a and b.
relatively prime to (p − 1)(q − 1).
9. Given relatively prime positive integers a and b, find an
inverse of a modulo b. 18. Given a message and an integer n = pq where p and
q are odd primes and an integer e> 1 relatively prime
10. Given n linear congruences modulo pairwise relatively to (p − 1)(q − 1), encrypt the message using the RSA
prime moduli, find the simultaneous solution of these con- cryptosystem with key (n, e).
gruences modulo the product of these moduli.
19. Given a valid RSA key (n, e), and the primes p and q
11. Given a positive integer N, a modulus m, a multiplier a,an with n = pq, find the associated decryption key d.
increment c, and a seed x 0 , where 0 ≤ a< m,0 ≤ c< m,
and 0 ≤ x 0 <m, generate the sequence of N pseudo- 20. Given a message encrypted using the RSA cryptosystem
random numbers using the linear congruential generator with key (n, e) and the associated decryption key d, de-
x n+1 = (ax n + c) mod m. crypt this message.
12. Given a set of identification numbers, use a hash func- 21. Generate a shared key using the Diffie-Hellman key ex-
tion to assign them to memory locations where there are change protocol.
k memory locations. 22. Given the RSA public and private keys of two parties,
13. Compute the check digit when given the first nine digits send a signed secret message from one of the parties to
of an ISBN-10. the other.