MATH/CSCI 4116 Cryptography Assignment 1
Before you begin: Please read the Assignment Instructions posted under “Content → Assignments” on Brightspace, and write the sentence:
“I have read and understood the posted assignment instructions”, at the beginning of your assignment, and sign this statement.
—————
1. Julius Caesar wants to arrange a secret meeting with Mark Antony, and he sends the ciphertext EVIRE. However, Antony does not know the key, so he tries all possiblities. Where will he meet Caesar? (At the ???).
(Note: Consider the Caesar cipher in the wider sense, that is, a shift cipher with m = 26. Also note that in an exhaustive search, there may be more than one solution. In fact, there are two possible solutions here).
2. The Playfair Cipher, or Wheatstone-Playfair Cipher, explained in the attachment to this assignment, or in many books or other resources, is one of the most famous classical ciphers. Although a fairly weak system by modern standards, it was still used in World War I, and took real effort to break at the time.
Use this cipher, with the key as given by the square in the attach- ment, to decipher the message
BHPCHAGYHMDGCFDSDCHMUGFAPT
JFLEMJJGFDPGCDEIOD
(A message from Queen Victoria (1819–1901) during the Boer War).
3. Use the definition of congruence modulo m to prove that it is an equivalence relation.
4. Prove parts (b) and (c) of Proposition 2.1.
5. (Optional) Solve the following “Crypticquote” that was published years ago in the no longer existing Halifax Daily News. Describe the main steps that led you to its deciphering.
Hint: See any frequence table, e.g., the one given in the introductory presentation.
AGDLKRKEMW EN RW EUIG RWU PMNK SRING EPDMNEKEMW;
MSK QMK TEKJMLK PGAEK, RWU IMNK TEKJMLK UGNGACEWQ.
– NJRFGNDGRAG
Note: The difficulty of breaking such ciphers depends on how well one knows the language in question. Therefore:
1 bonus point for native speakers of English,
3 bonus points for nonnative speakers of English (please indicate if this applies to you).
Due: Tuesday, January 19, 2021, by midnight Halifax time
CSCI/MATH 4116 – Assignment 1 – Solutions
1. [4 pts.] This question does not have a unique solution, and was intended to be somewhat open-ended. First, observe that Caesar did not use the “Caesar cipher”, since a shift by 3 places in the alphabet does not produce a sensible word. Then, if you go through all 25 shifts, you will come across the meaningful words arena and river. So, Marc Antony still does not know with certainty where to meet Caesar.
This ambiguity does not, however, contradict the definition of a cryptosystem since Antony did not have Caesar’s key. He therefore tried to cryptanalyze the ciphertext; cryptanalysis may or may not be suc- cessful.
Of course one could argue that in Caesar’s time the English language did not exist, so that arena is in fact the unique meaningful plaintext. This will certainly be acceptable as a valid solution, but only if all shifts have been checked.
2. [5 pts.] Follow the instructions and/or examples, but note that the operations in points (1) and (2) need to be reversed. Queen Victoria’s message was:
we are not interested in the possibilities of defeat
3. [6 pts.] (a) [2] Reflexivity: a ≡ a(mod m) is, by definition, the same as m | a − a, i.e., m | 0, which is always true.
(b) [2] Symmetry: a ≡ b(mod m) means m | a − b. But then also m | b − a, so b ≡ a(mod m).
(c) [2] Transitivity: a ≡ b(mod m) and b ≡ c(mod m) means m | a−b, respectively m | b−c. But then also m | (a−b)+(b−c), i.e., m | a − c, which means a ≡ c(mod m).
In summary: congruence modulo m is an equivalence relation.
4. [5 pts.] This is quite similar to Question 3.
(b) [2] Rewrite the two given congruences as m | a−b and m | c−d,
respectively. Now note that m | (a − b) + (c − d), which is the same as m|(a+c)−(b+d),andthisisequivalenttoa+c≡b+d (modm).
1
(c) [3] In this case it is easier to use Lemma 2.1: The given congru- ences can be written as a = b + k1m and c = d + k2m, respectively, for appropriate integers k1,k2. Now multiply these two equations together:
ac=(b+k1m)(d+k2m)=bd+(bk2 +dk1 +k1k2m)m;
this, again with Lemma 2.1, means that ac ≡ bd (mod m).
5. [1 or 3 bonus points] Many different clues are helpful here, including frequency of the letters, the fact that “and” is one of the most common 3-letter words, or the fact that there is only a limited number of 2-letter words (in contrast to 4-letter words). Thus, RW and RWU would almost certainly be an and and. Some “cultural knowledge” is also useful; here it helps to know that Shakespeare is responsible for numerous quotations, and that he is often referred to without his first name. The decrypted quotation is:
“Reputation is an idle and most false imposition; oft got without merit, and lost without deserving. – Shakespeare.”
2
MATH/CSCI 4116 Cryptography Assignment 2
1. A string over a finite set Σ is a finite sequence of elements from Σ. Show that the following procedure defines a cryptosystem.
Let w be a string over {A, B, . . . , Z}. Choose two shift cipher keys k1 and k2. Encrypt the elements of w in odd-numbered positions with k1 and those in even-numbered positions with k2. Then reverse the order of the encrypted string.
Determine the plaintext space, the ciphertext space, and the key space.
(Hint: This question is not difficult, but can be a bit tricky. Read the description very carefully; it may also help if you do an example for yourself. To show that it is indeed a cryptosystem is best done in words, rather than equations.)
2. Which of the following schemes is a cryptosystem? What is the plaintext space, the ciphertext space, and the key space?
(a) Each letter x ∈ Z26 is replaced by kx (mod 26), k ∈ {1,2,…,26}. (b) Each letter x ∈ Z26 is replaced by kx (mod 26), k ∈ {1,2,…,26},
gcd(k, 26) = 1.
3. (a) Find all the invertible residue classes mod 15 and their inverses.
(b) Determine the group of units and the zero divisors of Z/16Z.
4. (a)Listallintegersxintherange−50≤x≤50thatsatisfyx≡7
(mod 17).
(b) Exhibit a set of representatives modulo 17 composed entirely of mul- tiples of 3.
(c) Write a single congruence that is equivalent to the pair of congruences x≡2 (mod7),x≡3 (mod10).
5. Find φ(2020), φ(2021), and φ(b), where b is the integer obtained from the four digits after B00 of your student number.
Due: Tuesday, January 26, 2021, by 11:30 pm AST.
Assignment 2 – Solutions
1. [3] Let Σ = {A, B, . . . , Z}. Because of the reversal operation, the encryption depends on the length of the plaintext string. Therefore the plaintext space P and the ciphertext space C are both the set of all strings of Σ (and not just Σ itself).
Next, to show that the given scheme is a cryptosystem, we have to define a decryption function Dd and show that Dd(Ee(p)) = p for any p ∈ P, where Ee is the encryption function that was given.
This is best done in words. First, reverse the order of the ciphertext string. Then apply a shift cipher with key −k1 to the odd-numbered positions, and key −k2 to the even-numbered positions. This clearly gets us back to the original string p, so Dd(Ee(p)) = p.
Since two independent shift keys k1,k2 were used, the key space is the set of all pairs (k1,k2) with k1,k2 ∈ Z26 or, in other words, K = Z26 × Z26 = Z26.
2. (a) [2] This is not a cryptosystem because the encryption function is not injective. (Example: k = 2; then A corresponds to 0 (“zero”), which is mapped to 0 (that is, A). N corresponds to 13, which is mapped to 2·13≡0 (mod26)(thatis,toAagain).
(b) [2] This is a cryptosystem. Plaintext and ciphertext space are Z26 (or equivalently {A, B, . . . , Z}. The key space is the set {k = 1,2,… ,26 | gcd(k,26) = 1}.
3. (a) [2] We have to find those elements in Z15 that satisfy gcd(a, 15) = 1; these are a = 1, 2, 4, 7, 8, 11, 13, 14. At this stage, the inverses are best found by “trial and error” (we will learn a systematic method later). For instance, 2 · 8 ≡ 1 (mod 15), which means that the inverse of 2 is 8, and the inverse of 8 is 2. Similarly, since 4·4 ≡ 1 (mod15), 4 is its own inverse, etc. Altogether the inverses are, (in this order): 1, 8, 4, 13, 2, 11, 7, 14.
(b) [2] The group of units consists of all invertible elements modulo 16, that is, the residue classes belonging to a ∈ Z16 with gcd(a, 16) = 1; these are a = 1, 3, 5, 7, 9, 11, 13, 15. The zero divisors are all the others,
1
namely a = 2, 4, 6, 8, 10, 12, 14, except for 0 which, by definition, is not a zero divisor.
4. (a) [1] −44, −27, −10, 7, 24, 41.
(b) [2] There are numerous possibilities, for instance, 0, 3, 6, 9, 12,
15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48.
(c) [2] Some will know the “Chinese Remainder Theorem” which
can be used here. However, this was not covered in class, and it is not necessary here. Just do it by “trial and error”: The resulting congru- ence has to be modulo 70. Now, the second congruence means that x ≡ 3,13,23,33,43,53, or 73 (mod 70). Of these, only 23 is also ≡ 2 (mod 7), so that the desired single congruence is x ≡ 23 (mod 70).
5. [4] You can use either of the two formulas provided in the notes. It is essential that the integers be completely factored.
2020=22·5·101, soφ(2020)=2020(1−1)(1−1)(1− 1 )=800. 2 5 101
2021=43·47, soφ(2021)=(43−1)(47−1)=1932.
2
MATH/CSCI 4116 Cryptography Assignment 3
1. Using the fact that 10 ≡ 1 (mod 9), resp. 10 ≡ −1 (mod 11), prove the following divisibility rules for integers in decimal notation:
(a) “Casting out nines”, i.e., an integer is divisible by 9 if and only if the sum of its digits is divisible by 9.
(b) Less well-known, but just as easy: An integer is divisible by 11 if and only if the alternating sum of its digits is divisible by 11. (Example: 11 | 1353 because 3 − 5 + 3 − 1 = 0, which is divisible by 11.)
(Hint: Use the decimal representation of the integer in question.)
2. Fix a modulus m and use the affine cipher with key k1 = (a,b) to encrypt an element x; then encrypt the result with a key k2 = (c,d). What is the resulting cipher? Given your answer, is security of the affine cipher with a given modulus m increased if one encryption is followed by a second encryption with a different key?
3. Suppose we work modulo 29 instead of modulo 26 for affine ciphers. How many keys are possible? What if we work modulo 30?
4. (a) Determine the number of bit permutations of the set {0,1}n, n ∈ N.
(b) Determine the number of circular right shifts of {0,1}n.
(c) Find a permutation of {0, 1}n that is not a bit permutation.
5. Let Σ be an alphabet. Show that the set Σ∗ together with concate- nation is a monoid. Is this monoid a group?
6. Give an example to show that the group of permutations S5 is not commutative.
Due: Tuesday, February 2, 2021, by 11:30 pm AST
Assignment 3 – Solutions
1. [4 pts.] Write a positive integer n in its decimal expansion:
n=ak10k +ak−110k−1 +…+a110+a0,
where0≤aj ≤9forj=0,1,…,k.
(a) Since 10 ≡ 1 (mod 9), we have by the rules for congruences that
10j ≡1j =1 (mod9)forallj=1,2,…,andthus
n ≡ ak · 1 + ak−1 · 1 + . . . + a1 · 1 + a0 (mod 9),
which means that n ≡ 0 (mod 9), i.e., it is divisible by 9, if and only if the sum of digits is.
(b) Similarly, since 10 ≡ −1 (mod 11), we have by the same rules that 10j ≡ (−1)j = 1 (mod 11) for all j = 1,2,…, and thus
n ≡ ak(−1)k + ak−1(−1)k−1 + . . . − a1 + a0 (mod 11),
which means that n ≡ 0 (mod 11), i.e., it is divisible by 11, if and only
if the digit sum, with alternating signs, is divisible by 11.
2. [3 pts.] Note that the two keys k1 = (a,b) and k2 = (c,d) have to
satisfy gcd(a, m) = gcd(c, m) = 1. The double encryption results in Ek2 (Ek1 (x)) = Ek2 (ax + b) = c(ax + b) + d = (ca)x + (cb + d).
So this is just another affine cipher with key (ca, cb + d) and gcd(ac, m) = 1. Hence security is not increased.
3. [3 pts.] The number of keys of the affine cipher modulo 29 is the product of φ(29) = 28 (for the number of possible a) and 29 (for the number of possible b), so it is 812.
Similarly, modulo 30 we have φ(30)·30 = 301 +1 +1·30 =
8 · 30 = 240 different keys.
1
235
4. (a) [2 pts.] Since a bit permutation of the set {0, 1}n is given by b1b2…bn →bπ(1)bπ(2)…bπ(n),
where π is a permutation of the permutation group Sn, the desired num- ber of bit permutations is |Sn| = n!.
(b) [1 pt.] The number of circular right shifts is clearly n (here the zero-shift should also be counted).
(c) [1 pt.] There are many possibilities. Consider, for instance, the map on {0,1}n that sends 0 to 1 and 1 to 0. This is clearly a permutation on {0,1}n. But, for instance, the string 00…0 gets mapped to 11…1, which is not a bit permutation.
5. [3 pts.] It is clear that concatenation is an associative operation, so (Σ∗,◦) is a semigroup. The empty string ε is the neutral element, and this makes (Σ∗,◦) a monoid. It is not a group since no element except for ε has an inverse.
6. [3 pts.] All we need are two permutations in S5 that do not commute. For example,
1234512345 12345 24315◦43125=13245
1234512345 12345 43125◦24315=32145
The resulting permutations are different.
2
MATH/CSCI 4116 Cryptography Assignment 4
123 1.(a) Determine det A, where A = 2 3 1 .
312
(b) Determine the inverse of the matrix A =
2. Do the following “by hand” or use a computer algebra system:
124 LetM=1525 .
1 14 196
(a) Find the inverse of M (mod 101).
(b) For which primes p does M not have an inverse (mod p)?
3. Find an injective affine linear map (Z/2Z)3 → (Z/2Z)3 that sends (1, 1, 1) to (0, 0, 0).
4. Find a key for the affine linear cipher with alphabet {A, B, C, . . . , Z} and block length 3 that encrypts red as TWO.
(To make it a bit more interesting, choose a matrix other than the identity, and a vector b different from the zero vector. Note that there are many different possibilities; use an easy one.)
5. Suppose that Oscar has learned that the plaintext displayedequation
is encrypted to give the ciphertext
SRMSIOPLXLJAZULLM
and Oscar also knows that it’s an affine linear cipher with block length n = 3. Compute the key, showing all computations.
(Suggestion: Use the first four blocks of each of the given strings.)
Due: Thursday, February 11, 2021, 11:30 pm AST.
111 1 1 0 100
modulo 2.
Assignment 4 – Solutions
1.(a) [2 pts.] There are different ways of doing this. One is by expansion
along the first row:
123 31 21 23 det 231 =det 12 −2det 32 +3det 31
312
= 5 − 2 · 1 + 3 · (−7) = −18.
(b) [2 pts.] This can be done in different ways (see your linear algebra
book or notes). The formula from class can also be used. The result is
001 011 .
110
2.(a) [2 pts.] Once again, various methods can be used, including com- puter algebra. The inverse of M (mod 101) is
30 85 88 64 38 100 . 87 86 29
(b) [2 pts.] Since the determinant of M is 324 = 2234, the only primes p for which M does not have an inverse (mod p), that is, with which detM is not relatively prime, are p = 2 and p = 3.
3. [2 pts.] There are many possible solutions. We have to find a map f(v) = Av + b, for v ∈ (Z/2Z)3. The easiest choice is A = I3; then clearly det A = 1, so by Proposition 2.10 of the class notes the map is bijective. Now the choice b = (1, 1, 1) is such that f ((1, 1, 1)) = (0, 0, 0).
4. [4 pts.] Again, many possible solutions. The identity matrix was not admissible, but you may as well choose a very similar one, say
100
A= 001 with detA=−1≡25 (mod26),
010
1
and thus the condition gcd(det A, 26) = 1 is satisfied. Now, the vector (r,e,d) ↔ (17,4,3) = w is to be mapped to (T,W,O) ↔ (19,22,14) = c according to
c = f(w) = Aw + b.
Solving for b, we get
19 1 0 017 19 17 2
b= 22 − 001 4 = 22 − 3 ≡ 19 (mod26),
14 010 3 14 4 10
and so the pair (A, b) is a possible key.
5. [6 pts.] Proceed as in subsection 2.8.3 of the class notes. Since the block length is 3, we need n + 1 = 4 pairs of plaintext-ciphertext blocks. Recall the suggestion that the first four blocks of each of the given strings be used. They translate into the blocks
w0 = (3,8,18), w1 = (15,11,0), w2 = (24,4,3), w3 = (4,16,20), andthematrixW whichhaswi−w0 (i=1,2,3)ascolumns,is
12 21 1 W= 3228 .
8 11 2
Similarly, the ciphertext blocks are
c0 = (18,17,12), c1 = (18,8,14), c2 = (15,11,23), c3 = (11,9,0),
and the corresponding matrix which has ci − c0 (i = 1, 2, 3) as columns,
is
0 2319 C= 172018 .
2 11 14
Now detW ≡ 1 (mod 26), so gcd(detW,26) = 1, and thus W is in- vertible in Z26 . Once again, there are different ways of finding W −1 , including computer algebra systems:
W
−1 8 2116
≡ 6 16 11 (mod 26),
13 10 19
2
and consequently
A≡CW ≡ 2225 2 (mod26).
−1 21 12 16 4 20 3
It is now important to check that the matrix A is allowable; indeed, we find that det A ≡ 19 (mod 26), and thus gcd(det A, 26) = 1.
Finally, the vector b is found by solving the congruence c0 ≡ Aw0 + b for b; we get b ≡ (13, 1, 20) (mod 26). Now the pair (A, b) is the desired key.
3
MATH/CSCI 4116 Cryptography Assignment 5
1. We know that φ(ab) = φ(a)φ(b) whenever gcd(a,b) = 1. Give an example that shows that this identity is, in general, not true when gcd(a, b) ̸= 1.
2. Use the stream cipher discused in class (Section 2.6), with n = 7 andc0 =c1 =1,c2 =c3 =0,c4 =c5 =c6 =1. Encryptw= 1110011 1110001 1010001 using the key k = 1010011.
3. Find the sample space and probability distribution that model flip- ping two coins. Describe the event “at least one coin comes up heads” formally and compute its probability.
4. We throw two dice. Determine the probability that they both show different numbers under the condition that the sum of both numbers is even.
5. (a) Determine the integer n such that the probability for two of n people having the same birthday is at least 9/10.
(b) Suppose the 4-digit PINs are randomly distributed. How many peo- ple must be in a room such that the probability that two of them have the same PIN is at least 1/2? (Here “4 digits” means that the PIN cannot start with a 0.)
Note: Pay special attention to the direction of the inequality in the formula(s) used for this question.
Due: Thursday, February 25, 2021, 11:30 pm
Assignment 5 – Solutions
1.[2 pts.] There are many possible examples. Take, for instance, a = 2 andb=6. Thenφ(a)=1andφ(b)=2,whileφ(ab)=φ(12)=4. So we have φ(a)φ(b) ̸= φ(ab).
2. [See after Q. 4]
3.[3 pts.] Let H denote “heads”, and T “tails”. The sample space is
S = {HH,HT,TH,TT}.
The probability of each elementary event is 1/4. The event “at least one
coin comes up heads”is the subset {HH,HT,TH}. The probability of
this event is 3 · 1 = 3 . 44
4.[4 pts.] The sample space is {11, 12, . . . , 65, 66}. The event “both dice come up differently”is A = {12, 13, 14, 15, 16, 21, 23, . . . , 65}. Its probability is p(A) = 5/6. The event “the sum of the results in even”is B = {11,13,15,22,24,26,… ,66}; its probability is p(B) = 1/2. The intersection of both events is A ∩ B = {13,15,24,26,… ,64}; it has p(A ∩ B) = 1/3. Finally, by definition,
p(A|B)= p(A∩B) = 1/3 = 2. p(B) 2/3 3
2.[5 pts.] The given sequence of coefficients gives rise to the recurrence relation
zi+7 =zi ⊕zi+1 ⊕zi+4 ⊕zi+5 ⊕zi+6
With the key 1010011 as initial values, this gives the keystring shown in the “zi ”column of the table. From the plaintext w1 w2 . . . w21 we then obtain the ciphertext string by ci = zi ⊕ wi.
1
i
zi
wi
ci
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1
0
1
0
0
1
1
1
0
1
0
0
1
1
1
0
1
0
0
1
1
1
1
1
0
0
1
1
1
1
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
5.(a)[3 pts.] By Proposition 3.2 (course notes) we need to find a k ∈ N such that q ≤ 1/10, which is satisfied when
exp(−k(k − 1)) ≤ 1/10. 2·365
Now “trial and error”is the easiest method: We find
exp(− 41 · 40 ) ≃ 0.10576, exp(− 42 · 41 ) ≃ 0.09452.
2·365 2·365 2
So k = 42 is the desired result.
(b)[3 pts.] Here we could use the same method as in (a), or use the formula given in the examples after Proposition 3.2 (course notes). The allowable PINs range from 1000 to 9999, so we have n = 9000. Then the formula mentioned tells us that
k≥ 11+1+8·9000·log2≃112.20004 2
suffices. So the solution is: 113 people must be in the room.
3