(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.

/in /by

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 divisors.
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
0
1
· (c − k2) mod p
where k
0
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
−1
1
· (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
−1
1
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 g
A 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 = a
2 mod N and set A = A/2.
iii) If A > 0, continue with loop at Step 2.
3. Return the number b, which equals g
A 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 Eve’s 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 Alice’s private key