CPSC 418 / MATH 318 — Introduction to Cryptography W21
MIDTERM EXAMINATION — SOLUTION KEY
Problem 1 — Affine cipher (7 marks)
Feel free to use a calculator for this problem, but be sure to show all your work.
Consider an alphabet consisting of the digits 0-9 and the 26 English letters. Analogous to the
shift cipher, each symbol is converted to a number modulo 36, where we assign each digit its own
numerical value and the numerical equivalents of the letters A-Z are the numbers 10-35.
The affine cipher is a generalization of the shift cipher, where the plaintext space and ciphertext
space are Z36 and the key space is the cartesian product Z∗36 × Z36. That is, keys are pairs (a, b)
where a ∈ Z∗36 and b ∈ Z36.
Encryption of a plaintext M ∈ Z36 with a key (a, b) ∈ Z∗36 × Z36 is the ciphertext
C ≡ aM + b (mod 36)
in Z36. Note that for a = 1, this is just the shift cipher with shift b.
a. (3 marks) What is the size of the key space? Your answer should be an explicit number, along
with an explanation of how you got it.
Solution. The size of the key space is |Z∗36||Z36| = φ(36) · 36 where φ denotes Euler’s phi
function. Since 36 = 2232, we have
φ(36) = φ(22)φ(32) = (22 − 2)(32 − 3) = 2 · 6 = 12.
Hence the number of keys is 12 · 36 = 432.
Note: φ(36) 6= 35. The formula φ(p) = p− 1 only applies to primes.
b. Which if any of the following pairs are valid affine cipher keys? Explain.
(i) (1 mark) (10, 25)
Solution. Not a valid key as gcd(10, 36) > 1 (common factor 2), so 10 /∈ Z∗36.
(ii) (1 mark) (25, 10)
Solution. Valid key as gcd(25, 36) = 1, so 25 ∈ Z∗36 and 10 ∈ Z36.
c. (2 marks) Encrypt the string “W21” using the key (13, 17). Convert this string into a sequence
of plaintext characters in Z36, encrypt it, and convert the resulting ciphertext back to a string.
Solution. The numerical encoding of “W” is 32 ∈ Z36. The encryptions of the numerical values
of the three characters are
13 · 32 + 17 = 433 ≡ 1 (mod 36) ,
13 · 2 + 17 = 43 ≡ 7 (mod 36) ,
13 · 1 + 17 = 30 ≡ 30 (mod 36) .
Converting these numbers back to alphabet symbols yields the ciphertext 17U.
1
Problem 2 — Entropy and perfect secrecy (10 marks)
Consider a cryptosytem with plaintext space M = {a, b}, ciphertext space C = {1, 2, 3, 4, 5} and
key space K = {K1,K2,K3,K4,K5}, where encryptions are given by the following table:
a b
K1 1 2
K2 2 3
K3 3 1
K4 4 5
K5 5 4
Assume the following probability distribution on K:
p(K1) = p(K2) = p(K3) =
1
6
, p(K4) = p(K5) =
1
4
.
a. (3 marks) What is the entropy of the key space? Your answer should be a numerical value that
is accurate to two decimal places (feel free to use a calculator).
Solution.
H(K) =
5∑
i=1
p(Ki) log2
(
1
p(Ki)
)
= 3 · 1
6
log2(6) + 2 ·
1
4
log2(4) ≈
1
2
· 2.58 + 1
2
· 2 = 2.29 bits .
Note: The directive was to provide hte value to two decimal places. In real-world jobs, it is
imperative to follow specifications; failing to adhere to specs, policies and standard can have
very dire consequences.
b. (5 marks) Use the characterization
A cryptosystem provides perfect secrecy if and only if p(C|M) = p(C) for all M ∈
M, C ∈ C with p(M) > 0 and p(C) > 0
to prove that this system provides perfect secrecy. For your convenience, here are the relevant
formulas:
p(C|M) =
∑
K∈K with
EK(M)=C
p(K) , p(C) =
∑
K∈K with
C∈EK(M)
p(DK(C))p(K) .
Note: You do not need to know the plaintext space probability distribution here; you can prove
this result for any plaintext probabilities p(a), p(b) where p(a) + p(b) = 1.
Solution. Since for each (M,C) with M ∈M and C ∈ C, there is exactly one key that encrypts
M to C, each sum p(C|M) consists of one term only, and we obtain
p(1|a) = p(K1) = 1
6
, p(2|a) = p(K2) = 1
6
, p(3|a) = p(K3) = 1
6
,
p(1|b) = p(K3) = 1
6
, p(2|b) = p(K1) = 1
6
, p(3|b) = p(K2) = 1
6
,
2
p(4|a) = p(K4) = 1
4
, p(5|a) = p(K5) = 1
4
,
p(4|b) = p(K5) = 1
4
, p(5|b) = p(K4) = 1
4
.
When computing the 5 ciphertext probabilities, we need to use the fact that p(a) + p(b) = 1 to
obtain
p(1) = p(a)p(K1) + p(b)p(K3) = p(a) · 1
6
+ p(b) · 1
6
= (p(a) + p(b)) · 1
6
=
1
6
,
p(2) = p(a)p(K2) + p(b)p(K1) = p(a) · 1
6
+ p(b) · 1
6
=
1
6
,
p(3) = p(a)p(K3) + p(b)p(K2) = p(a) · 1
6
+ p(b) · 1
6
=
1
6
,
p(4) = p(a)p(K4) + p(b)p(K5) = p(a) · 1
4
+ p(b) · 1
4
=
1
4
,
p(5) = p(a)p(K5) + p(b)p(K4) = p(a) · 1
4
+ p(b) · 1
4
=
1
4
.
Comparing values shows that p(C|M) = p(C) for all M ∈ M (note that p(C) > 0 for all
ciphertexts C, but these identifies hold for all values p(a) and p(b), even when p(a) = 0 or
p(b) = 0). Hence the system provides perfect secrecy.
c. (2 marks) If, instead of the probability distribution on the key space given above, keys are
chosen with equal likelihood, i.e. p(Ki) = 1/5 for i = 1, 2, 3, 4, 5, does the system still provide
perfect secrecy? Give a yes/no answer and a very brief explanation of how the values you
calculated for part (b) change when you use equal key probabilities.
Solution. Yes it does. All the quantities 1/6 and 1/4 of part (b) change to 1/5.
3
Problem 3 — Blind quiz marking via the one-time-pad (20 marks)
For each part of this question, provide a yes/no answer (where requested) and a brief, rigorous,
formal explanation.
Professor Proton wishes to give an on-line quiz to a class of 100 students. The quiz consists of 20
true/false questions and is to be marked by Proton’s mysterious teaching assistant Q (who could
be a human, computer, AI or anything else you care to imagine). Proton does not wish to entrust
Q with the solutions to the quiz, nor does Proton want Q to see the answers submitted by any of
the students. But how is Q supposed to grade the quiz under these conditions?
To solve this conundrum, Proton devises the following procedure:
1) Each student is assigned a unique ID number which is an integer between 1 and 100. All the
ID numbers are distinct, i.e. no two students have the same ID number. For simplicity, we refer
to a student whose ID number is i as student i.
2) Prior to the quiz, Proton establishes a shared cryptographic key with each of the students.
Keys are bit strings of length 20, and each student has their own key shared with Proton. Each
key is chosen equally likely, i.e. the probability that any 20-bit string occurs as a key is 2−20.
We assume that all keys are distinct, so no two students share the same key with Proton.1
3) After writing the quiz, each student encodes their answers as a 20-bit string, where the j-th bit
corresponds to the answer given on the j-th question, with 1 representing an answer of ‘true’
and 0 an answer of ‘false’. We refer to this string as the student’s answer string.
4) Similarly, Professor Proton converts the correct answers for the quiz to a 20-bit string using
the same encoding procedure, with 1 representing a ‘true’ answer and 0 a ‘false’ answer’. We
refer to this string as the solution string.
5) Every student now uses the one-time pad to encrypt their answer string with their key shared
with Professor Proton and sends the result toQ. That is, for each ID number i with 1 ≤ i ≤ 100,
student i sends Ci = Mi ⊕Ki to Q, where Mi is the student’s answer string and Ki is the key
shared between the student and Proton.
6) Professor Proton uses the one-time pad to encrypt the solution string with each of the shared
keys and sends all these encryptions to Q. That is, Proton sends the strings C ′i = M ⊕ Ki,
1 ≤ i ≤ 100, to Q, where M is the solution string and Ki is the key shared between student i
and Proton.
Q is now in possession of 100 pairs of 20-bit strings (Ci, C ′i) (let’s assume for simplicity that all 100
students wrote the quiz and submitted answers). However, Q does not know the solution string
M , any of the student answer strings Mi or any of the keys Ki.
1In practice, this is reasonable because by the birthday paradox (Problem 4 on Assignment 1), approximately
1.177
√
220 > 1200 keys need to be generated for a 50% chance of a collision, but there are only 100 students. In any
case, on the off-chance of a match, Proton can always ask one of the students to throw away that key and share a
new one.
4
a. (4 marks) Show that Q is able to grade the quiz. Specifically, explain how Q can determine for
each student precisely which of the questions the student answered correctly and which ones
the student got wrong.
Solution. For each i, we have Ci = Mi ⊕Ki and C ′i = M ⊕Ki. The x-or of these two strings
yields Ci⊕C ′i = Mi⊕M , and Q can compute this string from Ci and C ′i. Every 0 bit in Mi⊕M
corresponds to identical bits in Mi and M , which means that student i’s answer is identical
to the answer encoded in the solution string. Similarly, every 1 bit in Mi ⊕M corresponds to
different bits in Mi and M , so student i’s answer is different from the answer encoded in the
solution string. In other words, student i’s answers are are correct on questions corresponding
to 0 bits in Ci ⊕ C ′i and wrong on questions corresponding to 1 bits in Ci ⊕ C ′i.
b. (6 marks) Is Q able to discover any of the following:
(i) The solution string M?
Solution. No. Since the one-time pad provides perfect secrecy when keys are chosen
equally likely, we have p(M |C) = p(M) for every ciphertext C, where M is the answer
string. So knowledge of the ciphertexts Ci, C
′
i, 1 ≤ i ≤ 100 (or in fact of any ciphertext)
reveals nothing about M .
(ii) Any answer string Mi?
Solution. No. Again, we have p(Mi) = p(Mi|C) for every ciphertext C and every i with
1 ≤ i ≤ 100. So knowledge of the encryption Ci of any Mi or of any other ciphertext
reveals nothing about Mi.
(iii) Any key Ki?
Solution. No. Knowledge of any key Ki immediately produces an answer string Mi =
Ci ⊕Ki or the solution string M = C ′i ⊕Ki. Since Q is unable to find M or any Mi by
parts (i) and (ii), Q cannot discover any keys.
c. (6 marks) Suppose a key is leaked to Q, but Q does not know its owner. That is, Q knows a
string K ′ such that K ′ = Ki for some i, but Q does not know the corresponding student ID i.
What if anything can Q deduce about any of the following:
(i) The solution string M?
Solution. A priori there are 220 possibilities for the solution string M . But now Q knows
that M = C ′i ⊕K ′ for some i. So Q can narrow down the number of possibilities for M
from 220 = 1,048,576 to 100. However, Q still cannot know which of these 100 strings is
M .
(ii) Any key Ki?
Solution. Since there are 100 possibilities for M by part (i), Q can narrow down the
number of possibilities for each key Ki from 2
20 to 100 by computing the 100 strings
C ′i ⊕M ′ where M ′ is one of the 100 possibilities for M . However, for any i, Q cannot
find out which of these 100 candidate strings is the correct key Ki.
(iii) Any answer string Mi?
Solution. Since there are 100 possibilities for each key Ki, there are 100 possibilities for
each answer string Mi, namely Ci ⊕K ′′ where K ′′ is one of the 100 possibilities for the
key Ki. So Q can narrow down the number of possibilities for each answer string Mi from
220 to 100. But Q is again unable to identify for each i which of the 100 choices is Mi.
5
d. (4 marks) Suppose now thatQ finds out that the key K ′ of part (c) belongs to student number 5.
Does this knowledge help Q in discovering any of the following:
(i) The solution string M?
Solution. Yes because M = C ′5⊕K5 = C ′5+K ′. So Q can discover the solution string M .
(ii) Any key Ki?
Solution. Yes because Ki = M ⊕ C ′i for each i. Since Q can find M by part (i), every
key is now revealed.
(iii) Any answer string Mi?
Solution. Yes because Mi = Ci ⊕Ki for all i. Since Q can obtain every key Ki by part
(ii), Q can now decrypt every Ci to obtain Mi.
6
Problem 4 — Key streams via binary recurrences (10 marks)
Stream ciphers such as the one-time pad require a secret key stream of random bits which is bitwise
x-or’ed with a plaintext to produce a ciphertext. In this problem, you will cryptanalyze one possible
approach for generating such a key stream.
Letm be a positive integer and c0, c1, . . . , cm−1 ∈ {0, 1} a sequence ofm fixed bits. Let z0, z1, . . . , zm−1
be any sequence of m bits and define zm, zm+1, zm+1, . . . via the linear recurrence
zn+m ≡ cm−1zn+m−1 + cm−2zn+m−2 + · · ·+ c1zn+1 + c0zn (mod 2) , (1)
with the usual arithmetic modulo 2. The fixed bits c0, c1, . . . cm−1 are the coefficients of the linear
recurrence (1) and the initial values z0, z1, . . . , zm−1 are its seed. If the seed and the coefficients are
appropriately chosen, then (1) generates a sequence of 2m pseudorandom bits2 (zi)i≥0 from a seed
of length m. This type of construction is popular since it can be implemented very efficiently in
hardware using a linear feedback shift register.
a. (2 marks) Let m = 4 and consider the recurrence
zn+4 ≡ zn+3 + zn (mod 2).
This is the special case of (1) with m = 4 and coefficients c3 = 1, c2 = 0, c1 = 0 and c0 = 1.
Write down the first 19 bits z0, z1, . . . , z18 generated by this recurrence when starting with the
seed (z0, z1, z2, z3) = (0, 0, 0, 1).
Solution. 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1 .
Note the repetition after 15 = 24 − 1 bits.
b. (4 marks) Suppose you are given the 8-bit sequence
(z3, z4, z5, z6, z7, z8, z9, z10) = (1, 0, 1, 0, 1, 1, 0, 1)
which was generated using an unknown linear recurrence of the form (1) with m = 4, i.e.
zn+4 ≡ c3zn+3 + c2zn+2 + c1zn+1 + c0zn (mod 2) .
Find the unknown coefficients c0, c1, c2, c3 of this recurrence. Show your work and be smart
about this; solutions that use brute force/guessing will receive no credit.
Suggestion: check your answer, i.e. ensure that the coefficients you obtain define a recurrence
that produces the second four given bits (z7, z8, z9, z10) = (1, 1, 0, 1) from the first four given
bits (z3, z4, z5, z6) = (1, 0, 1, 0).
Solution. Substituting the subscripts n = 3, 4, 5, 6 into the recurrence yields
z7 ≡ c3z6 + c2z5 + c1z4 + c0z3 (mod 2) ,
z8 ≡ c3z7 + c2z6 + c1z5 + c0z4 (mod 2) ,
z9 ≡ c3z8 + c2z7 + c1z6 + c0z5 (mod 2) ,
z10 ≡ c3z9 + c2z8 + c1z7 + c0z6 (mod 2) .
2Since there are only 2m − 1 distinct non-zero bit patterns of length m, there must be repetition after at most
2m − 1 bits. So in practice, m must be large.
7
Substituting these values for z3, . . . , z10 into the congruences yields
1 ≡ c2 + c0 (mod 2)
1 ≡ c3 + c1 (mod 2)
0 ≡ c3 + c2 + c0 (mod 2)
1 ≡ c2 + c1 (mod 2)
Adding the first three congruences modulo 2 yields 0 ≡ c1 (mod 2), so c1 = 0. The second
congruence now yields c3 = 1, the last congruence yields c2 = 1, and first congruence yields
c0 = 0. In summary, (c0, c1, c2, c3) = (0, 0, 1, 1) and the recurrence is
zn+4 ≡ zn+3 + zn+2 (mod 2) .
Note: The appropriate approach here is to systematically solve the system of equations. Con-
sidering many cases and partially or completely brute forcing one’s way through the 24 = 16
possibilities of the quadruple (c0, c1, c2, c3) may work for a small example as given here. But
it becomes utterly infeasible for cryptanalyzing a real-life key stream generated by a sequence
with a value m of cryptographic size. Hence the directive of not applying guessing/brute force.
c. (4 marks) Suppose you intercept the 8-bit ciphertext fragment C = 10011010 that was encrypted
with the one-time pad using as key an 8-bit sequence (z0, z1, . . . , z7), where (z0, z1, z2, z3) is a
seed and the 4-tuple (z4, z5, z6, z7) is obtained from this seed using the recurrence of part (b).
Suppose also that you discover that the last two bits of the seed (i.e. z2 and z3) are 1 and 0,
respectively. Decrypt as many bits of C as possible.
Solution. The corresponding 8-bit plaintext M is the bitwise x-or, or equivalently, the bitwise
addition modulo 2, of the ciphertext with the key, i.e.
M = (m0,m1, . . . ,m0) = (10011010)⊕ (z0, z1, . . . , z7) .
Using the recurrence zn+4 ≡ zn+3 + zn+2 and substituting the given values starting with n = 0,
we find
z2 = 1 ,
z3 = 0 ,
z4 ≡ z3 + z2 ≡ 1 + 0 ≡ 1 (mod 2) ,
z5 ≡ z4 + z3 ≡ 1 + 0 ≡ 1 (mod 2) ,
z6 ≡ z5 + z4 ≡ 1 + 1 ≡ 0 (mod 2) ,
z7 ≡ z6 + z5 ≡ 0 + 1 ≡ 1 (mod 2) .
Hence
(m0,m1, . . . ,m0) = (10011010)⊕ (z0, z1, 1, 0, 1, 1, 0, 1) ≡ (1 + z0, z1, 1, 1, 0, 1, 1, 1) .
So the last 6 bits of M are 110111. The first two bits of M cannot be determmined; depending
on the specific values of z0 and z1, they can take on any values.
8
Problem 5 — Primitive roots (5 marks)
Verify that 2 is a primitive root of 37 using as few modular exponentiations as possible. For each
modular exponentiation, you must use the binary exponentiation algorithm covered in class and
show all your intermediate steps. Feel free to use a calculator, but be sure to show all your work.
Answers that don’t use this algorithm or provide no explanation will receive no credit.
(Suggestion: check your answers using a calculator.)
Solution. We use the primitive root test that asserts that an element g ∈ Z∗p is a primitive root
of p if and only if g(p−1)/q 6≡ 1 (mod p) for all prime factors of p− 1.
In our example, we have 37 − 1 = 36 = 22 · 32, so the prime factors of 36 are 2 and 3 and the
exponents we need to check are 36/2 = 18 and 36/3 = 12. We use the binary exponentiation
algorithm to compute 218 (mod 37) and 212 (mod 37).
Exponent 18 : Since 18 = 16+2, the binary representation of 18 is (10010)2 and the exponentiation
by 18 will require 4 steps (not counting the initialization r0 = 2). Using the notation from class,
we compute
r0 = 2 ,
r1 = r
2
0 = 4 ,
r2 = r
2
1 = 16 ,
r3 ≡ r22 · 2 ≡ 162 · 2 ≡ 31 (mod 37) ,
r4 ≡ r23 ≡ 312 ≡ 36 (mod 37) .
So 218 ≡ 36 6≡ 1 (mod 37).
Exponent 12 : Since 12 = 8 + 4, the binary representation of 123 is (1100)2 and the exponentiation
by 12 will require 3 steps. We obtain
r0 = 2 ,
r1 = r
2
0 · 2 = 8 ,
r2 = r
2
1 = 64 ≡ 27 (mod 37) ,
r3 ≡ r22 ≡ 272 ≡ 26 (mod 37) .
So 212 ≡ 26 6≡ 1 (mod 37).
9
Problem 6 — A modified variant of the Diffie-Hellman protocol (6 marks)
Consider the following modification of the Diffie-Hellman protocol.
Set-up:
ˆ All participants agree on a public prime p and a primitive root of p.
ˆ Each participant generates their own random exponent ui with 1 < ui < p− 1 and computes
Ui ≡ gui (mod p).
The public parameters g, p as well as the numbers Ui are stored in a public database. Each
participant keeps their exponent ui secret.
Suppose Alice and Bob wish to establish on a shared cryptographic key. Denote Alice’s database
entry by X ≡ gx (mod p) and Bob’s database entry by Y ≡ gy (mod p). They now execute the
following modified Diffie-Hellman protocol:
1. Alice generates a secret exponent a with 1 < a < p − 1, computes A ≡ ga (mod p) and sends
A to Bob.
Bob generates a secret exponent b with 1 < b < p− 1, computes B ≡ gb (mod p) and sends B
to Alice.
2. Alice looks up Bob’s public database entry Y and computes K ≡ BxY a (mod p)
Bob looks up Alice’s public database entry X and computes K ≡ AyXb (mod p).
The key shared between Alice and Bob is K. The man-in-the-middle attack on ordinary Diffie-
Hellman no longer works here as long as the database is tamper-proof (of course any attacker with
the ability to hack into the database can simply replace Bob’s database entry by her own and
impersonate Bob).
a. (2 marks) Formally prove that Alice and Bob compute the same quantity K in step 2.
Solution.
BxY a ≡ (gb)x(gy)a ≡ gbx+ya ≡ gay+xb ≡ (ga)y(gx)b ≡ AyXb (mod p) .
The left most expression is the result of Alice’s computation and the right most expression is
the result of Bob’s computation. So both computations produce the same result.
b. (4 marks) Recall the Diffie-Hellman problem whose solution breaks the original Diffie-Hellman
protocol:
Given A ≡ ga (mod p) and B ≡ gb (mod p), compute gab (mod p).
Suppose Eve is able to solve the Diffie-Hellman problem efficiently for any inputs A and B.
Explain how she can use this capability when eavesdropping on Alice and Bob to find any key
generated by Alice and Bob using the modified Diffie-Hellman protocol described above.
10
Solution. Eve intercepts A and B via eavesdropping on Alice and Bob. She can also look up
Alice’s ad Bob’s respective public database entries X and Y . She solves the Diffie-Hellman
problem for inputs A ≡ ga (mod p) and Y ≡ gy (mod p) to obtain gay (mod p). Similarly, she
solves the Diffie-Hellman problem for inputs X ≡ gx (mod p) and B ≡ gb (mod p) to obtain
gxb (mod p). Finally, she multiplies the results of her two Diffie-Hellman problem solution
together to obtain
gaygxb ≡ gay+xb ≡ K (mod p) .
Note: We cannot assume here that Eve has the capability of extracting discrete logarithms;
this is a stronger assumption that renders this problem trivial. Remember that an algorithm
for computing discrete logs solves the Diffie-Hellman problem, and it is easy to see that it also
makes finding keys for this variant very simple. But the reverse direction is unknown; that is,
it is unknown whether anyone with the capability of discovering Diffie-Hellman keys or keys for
this modified variant can use this ability to extract discrete logarithms.
11
Problem 7 — Hash functions (15 marks)
In class, we encountered three properties for hash functions in the context of cryptography: pre-
image resistance, weak collision resistance and strong collision resistance. We saw that strong
collision resistance implies weak collision resistance (because every weak collision is also a strong
collision). This problem establishes that there are no further implications amongst these three
properties. As always, “‖” denotes concatenation of strings, and n denotes a positive integer.
a. This part proves that pre-image resistance does not imply strong collision resistance and hence
also not weak collision resistance.
Let h : {0, 1}∗ → {0, 1}n be a pre-image resistant hash function. Define a new hash function
H : {0, 1}∗ → {0, 1}n via
H(M) = h(M ′) ,
where M ′ is obtained by replacing the last bit of M by 0; if the last bit of M is already 0, it is
left unchanged, so H(M) = h(M) in this case.
(i) (4 marks) Formally prove that H is pre-image resistant. Specifically, prove that a pre-
image of a string x ∈ {0, 1}n under H produces a pre-image of x under h.
(Suggestion: Proof by contradiction works nicely here. Specifically, you can find a pre-
image under h from a pre-image under H.)
Solution. Assume to the contrary that H is not pre-image resistant. Then there exists
x ∈ {0, 1}n for which it is feasible to find a pre-image under H, i.e. a bit string M ∈ {0, 1}∗
with H(M) = x. Let M ′ be obtained from M by setting the last bit of M to 0. Then
h(M ′) = H(M) = x, so a pre-image M ′ of x under h was efficiently found, contradicting
the pre-image resistance of h. Hence H is pre-image resistant.
(ii) (3 marks) Prove that H is not strongly collision resistant by exhibiting an explicit example
of a strong collision for H. Explain your example.
Solution. Put M = 1 and M ′ = 0. Then M 6= M ′. Replacing the last (in fact, the only)
bit in M by 0 yields M ′, so H(M) = H(1) = h(0) = H(0) = H(M ′). Hence {M,M ′} is
a strong collision. (In fact, we have H(S‖0) = H(S‖1) for all bit strings S.)
b. This part proves that weak collision resistance does not imply pre-image resistance; hence strong
collision resistance also does not imply pre-image resistance.
Let h : {0, 1}∗ → {0, 1}n be a weakly collision resistant hash function. Define a new hash
function H : {0, 1}∗ → {0, 1}n+1 via
H(M) =
{
1‖0n if M = 0,
0‖h(M) otherwise, ,
where 1‖0n is the string of length n+ 1 that begins with a 1, followed by n 0’s.
(i) (5 marks) Formally prove that H is weakly collision resistant. Specifically, prove that for
an input M ∈ {0, 1}∗, a weak collision with M for H produces a weak collision with M
for h. You might want to handle the case M = 0 separately.
(Suggestion: Analogous to part (a) (i).)
12
Solution. Assume to the contrary that H is not weakly collision resistant. Then there
exists an input M ∈ {0, 1}∗ for which it is feasible to find a weak collision under H, i.e.
there exists a string M ′ ∈ {0, 1}∗ with M ′ 6= M and H(M ′) = H(M).
We first note that no weak collision for H with the string 1‖0n exists because there is
only one input that maps to 1‖0n under H, namely the input 0. So neither M nor M ′
can be the string 0.
It follows that H(M) = 0‖h(M) and H(M ′) = 0‖h(M ′), so 0‖h(M) = H(M) = H(M ′) =
0‖h(M ′), which implies h(M) = h(M ′). But now we found a weak collision M ′ with M for
h, contradicting the weak collision resistance of h. Thus, H is weakly collision resistant.
(ii) (3 marks) Prove that H is not pre-image resistant by exhibiting an example of a string
x ∈ {0, 1}n+1 for which it is easy to find a pre-image under H. Explain your example.
Solution. The string x = 1‖0n is an example of a hash value of H for which it is feasible
to find a pre-image M , namely M = 0.
13
Problem 8 — Polynomial arithmetic in Keccak’s function ι (7 marks)
Assume Keccak is used with a width of b = 1600, so the Keccak state A is a 5× 5× 64 bit array.
Recall that in Keccak’s function ι, the bits A[0, 0, 2j − 1] with 0 ≤ j ≤ 6 are x-or’ed with round
constants r[j + 7i] where i is the round index and r[t] is the constant coefficient of the polynomial
xt (mod x8 + x6 + x5 + x4 + 1)
for any t ≥ 0.
a. (4 marks) Compute x11 (mod x8 + x6 + x5 + x4 + 1). Your answer should be a polynomial of
degree ≤ 7 with binary coefficients. Note that this question does not require long division.
Solution. In polynomial arithmetic modulo x8 + x6 + x5 + x4 + 1 with binary coefficients, we
have
x8 = x6 + x5 + x4 + 1 ,
x9 = x · x8 = x(x6 + x5 + x4 + 1) = x7 + x6 + x5 + x ,
x10 = x · x9 = x(x7 + x6 + x5 + x) = x8 + x7 + x6 + x2
= (x6 + x5 + x4 + 1) + x7 + x6 + x2 = x7 + x5 + x4 + x2 + 1
x11 = x · x10 = x8 + x6 + x5 + x3 + x
= (x6 + x5 + x4 + 1) + x6 + x5 + x3 + x = x4 + x3 + x+ 1 .
So x11 ≡ x4 + x3 + x+ 1 (mod x8 + x6 + x5 + x4 + 1).
b. (3 marks) In the Keccak round with round index 1, does ι flip the bit A[0, 0, 15] or leave it
unchanged? Explain your answer; guesses without explanation will receive no credit.
Solution. Since 15 = 24−1, we have j = 4 and i = 1, so we need to compute the round constant
r[4+7·1] = r[11]. Thus, we must compute the constant coefficient of x11 (mod x8 + x6 + x5 + x4 + 1);
that is, the coefficient of x0 = 1. From part (a), we see that this constantcoefficient is 1. So ι
changes the bit A[0, 0, 15] to A[0, 0, 15]⊕ 1. Since 0⊕ 1 = 1 and 1⊕ 1 = 0, ι flips this bit.
14

欢迎咨询51作业君