Homework 2: Understanding Symmetric Ciphers
Purpose
This homework is designed to do several things:
The proficiency problems may become part of your portfolio that demonstrates meeting the content objectives of the course.
Doing challenge problems and submitting them (and their revised version(s)) demonstrates some of our overall objectives.
Submitting your check in memo and homework problems are an opportunity to get feedback from Dr. Bolkema.
Instructions
Do as many of the proficiency problems as you feel necessary to meet the objectives. The challenge problems are optional but encouraged. Recall that you can submit up to three problems per week for direct feedback from Dr. Bolkema.
Submit a check-in memo by Friday at noon (under the check in memos tab on Blackboard) by Friday at noon that describes your progress on these problems (and some other things). There are specific questions to answer there. This goes privately to Dr. B who will then give you feedback.
Content Objectives – Module 2
By doing this homework you will demonstrate that you are able to
1. Apply modular arithmetic algorithms for fast-powering, division, and finding greatest common divi- sors.
2. Implement symmetric ciphers involving modular arithmetic.
3. Discuss plaintext attacks on symmetric ciphers.
Proficiency Problems
1. (Objective 1)
(a) Use the Euclidean algorithm to compute gcd(291, 252).
(b) Use the square-and-mulitply algorithm to compute 17183 mod 256.
(c) Use the division algorithm to compute the quotient and remainder of 34787 divided by 353.
2. (Objective 1) Let a and b be positive integers.
(a) Suppose that there are integers u and v satisfying au + bv = 1. Prove that gcd(a, b) = 1.
(b) Suppose that there are integers u and v satisfying au + bv = 6. Is it necessarily true that gcd(a, b) = 6? If not, give a specific counterexample, and describe in general all of the possible values of gcd(a, b).
(c) Suppose that (u1, v1) and (u2, v2) are two solutions in integers to the equation au + bv = 1. Prove that a divides v2 ?v1 and that b divides u2 ?u1.
3. (Objective 2) Let N be a large integer and let K = M = C = /N. For each of the functions
e : K×M?C
listed below, answer the following questions.
Is e an encryption function?
If e is an encryption function, what is its associated decryption function d?
If e is not an encryption function, could you modify the given function into an encryption function by using some smaller set of keys?
(a) ek(m) ? k ?m mod N (b) ek(m) ? k ·m mod N (c) ek(m) ? (k + m)2 mod N
4. (Objective 2 & 3) Consider the affine cipher with key k = (k1, k2) whose encryption and decryption functions are given by
ek(m) ? k1 ·m + k2 mod p dk(c) ? k?1 · (c?k2) mod p
where k?1 is the inverse of k1 modulo p.
(a) Let p = 541 and let the key be k = (34, 71). Encrypt the message m = 204. Decrypt the ciphertext c = 431.
(b) Assuming that p is public knowledge, explain why the affine cipher is vulnerable to a known plaintext attack. How many plaintext/ciphertext pairs are likely to be needed in order to recover the private key?
(c) Alice and Bob decide to use the prime p = 601 for their affine cipher. The value of p is public knowledge, and Eve intercepts the ciphertexts c1 = 324 and c2 = 381 and also manages to find out that the corresponding plaintexts are m1 = 387 and m2 = 491. Determine the private key and then use it to encrypt the message m3 = 173.
(d) Suppose now that p is not public knowledge. Is the affine cipher still vulnerable to a known plaintext attack? If so, how many plaintext/ciphertext pairs are likely to be needed in order to recover the private key?
5. (Objective 2 & 3) Consider the Hill cipher defined by
ek(m) ? k1 ·m + k2 mod p dk(c) ? k?11 · (c?k2) mod p
where m, c, and k2 are column vectors of length n, and k1 is an n×n matrix.
(a) We use the vector Hill cipher with p = 7 and the key k1 =
( 1 3 2 2
) and k2 =
( 5 4
) .
(i) Encrypt the message m =
( 2 1
) (ii) What is the matrix k?11 used for decryption?
(iii) Decrypt the message c =
( 3 5
) .
(b) Explain why the Hill cipher is vulnerable to a known plaintext attack.
(c) The following plaintext/ciphertext pairs were generated using a Hill cipher with the prime p = 11. Find the keys k1 and k2.
m1 =
( 5 4
) , c1 =
( 1 8
) , m2 =
( 8 10
) , c2 =
( 8 5
) , m3 =
( 7 1
) , c3 =
( 8 7
) (d) Explain how any simple substitution cipher that involves a permutation of the alphabet can be
thought of as a special case of a Hill cipher.
6. (Objective 3) Explain why the cipher
ek(m) = k ?m and dk(c) = k ? c
defined by of bit strings is not secure against a known plaintext attack. Demonstrate your attack by finding the private key used to encrypt the 16-bit ciphertext c = 1001010001010111 if you know that the corresponding plaintext is m = 0010010000101100.
Challenge Problems
Justify your answers with complete sentences explaining your reasoning.
7. Let N, g, and A be positive integers. Prove that the following algorithm returns the value gA mod N.
Input: positive integers N, g, and A.
1. Set a = g and b = 1.
2. While A > 0
i) If A ? 1 mod 2, set b = b ·a mod N. ii) Set a = a2 mod N and set A = A/2.
iii) If A > 0, continue with loop at Step 2.
3. Return the number b, which equals gA mod N.
8. Alice and Bob choose a key space K containing 256 keys. Eve builds a special-purpose computer that can check 10, 000, 000, 000 keys per second.
(a) How many days does it take Eve to check half of the keys in K? (b) Alice and Bob replace their key space with a larger set containing 2B different keys. How large
should Alice and Bob choose B in order to force Eves computer to spend 100 years checking half the keys? (Use the approximation that there are 365.25 days in a year.)
9. Bob and Alice use a cryptosystem in which their private key is a (large) prime k and their plaintexts and ciphertexts are integers. Bob encrypts a message m by computing the product c = km. Eve intercepts the following two ciphertexts:
c1 = 12849217045006222, c2 = 6485880443666222.
Use greatest common divisors to find Bob and Alices private key.
