MATH/CSCI 4116: CRYPTOGRAPHY, WINTER 2020 Second Midterm, March 26, 2020
NAME: STUDENT ID:
This is an “open book” exam. Please read these instructions carefully, as they specify what you are allowed and not allowed to do.
Academic Integrity. All members of Dalhousie University community, which includes students, faculty, and staff, shall treat others with respect and fairness, be responsible and honest, and uphold the highest standards of academic integrity. By submitting this exam, I absolutely state that all work is entirely my own and does not violate Dalhousie University’s Academic Integrity policy.
What you are and aren’t allowed to do.
• You are not permitted to talk to any person other than the instructor, Peter Selinger, about any aspect
of this exam.
• You are permitted to consult your textbook, class notes, your own notes, and any handouts from this class including solutions to homework problems. You can also consult any other books, as well as online resources such as Wikipedia or Wolfram Math World. However, you are not permitted to consult any internet forum where people ask and answer questions, such as StackExchange. Also, you are not permitted to consult materials from this class from prior years.
• Youarepermittedtouseageneral-purposescientificcalculatorand,ifyouchoosetodoso,ageneral- purpose programming language. But you are not permitted to use a special-purpose internet calcu- lator (such as a Chinese Remainder Theorem solver).
• The rules of attribution apply to take-home exams: All sources must be cited. In particular, you must explicitly acknowledge any online resource that you consulted.
Policies.
• You affirm the statement: “I have had no conversation regarding this exam with any persons other than the instructor. Further, I certify that the attached work represents my own thinking. Any information, concepts or words that originate from other sources are cited in accordance with Dalhousie guidelines. I am aware of the serious consequences that result from improper discussions with others or from the improper citation of work that is not my own.”
• The instructor explicitly reserves the right to interview students whose grade deviates from the first midterm grade by more than 30%. The purpose of the interview is to ascertain that the student has mastered the course outcomes.
Submission instructions:
• Please start each problem on a fresh page. You can use your own paper, or write directly on the exam.
• Show your work. Your answers must include evidence for how you obtained them. For example, if you calculate a greatest common divisor, you must show the intermediate steps, such as the result of each division-with-remainder.
• If you suspect you found a typo in this exam, confirm this with your instructor, Peter Selinger, before submitting your exam.
• Submit your completed exam, as a single PDF file, via Brightspace before Saturday, March 28, at 8:30am.
1
Problem 1 (1 point). I have read and will abide by the instructions on academic integrity, what I am and am not allowed to do, and other policies on page 1 of this exam.
Yes No
Problem 2 (4 points). Use the Chinese remainder theorem and Euclid’s extended algorithm to solve the following system of equations:
x ≡ 15 (mod 3231) x ≡ 41 (mod 1234)
(Remember to show your work. Show the intermediate steps for Euclid’s extended algorithm. You may use a calculator to perform arithmetic operations including modulo operations; i.e., you do not need to show long divisions.)
2
Problem 3 (4 points). (a) Recall Euler’s φ-function, defined by φ(n) = |Z∗n|, the number of invertible elements in Zn. What is φ(9900)?
(b) Find 38436126602 (mod 13). Hint: use Fermat’s Little Theorem. and do almost no calculation. Explain your reasoning.
3
Problem 4 (4 points). Suppose Alice uses the RSA cryptosystem, with modulus n = 505741 and encryption exponent e = 5. Eve discovers that the prime factorization of n is 523·967. What is Alice’s secret decryption exponent d?
4
Problem 5 (4 points). In the ElGamal cryptosystem, Alice and Bob use p = 919 and α = 7. Bob chooses his secret to be a = 10, so that Bob’s public key is (p, α, β) = (919, 7, 381). Alice sends the ciphertext (r, t) = (4, 550). Determine the plaintext m.
5
Problem 6 (7 points). Consider the substitution permutation network that is shown in Figure 1 on the next page. It uses the S-box that is shown in Figure 2, with 4 input bits and 4 output bits. The linear approximation table for this S-box is shown in Figure 3.
Recall, for example, that the table entry “6” at position (7, 1) means that the linear equation X2 ⊕ X3 ⊕ X4 = Y4 holds with probability bias 6/16, where (X1, . . . , X4) is the input to the S-box, and (Y1, . . . , Y4) is the output.
(a) Find the encryption of the plaintext “11111111”, using the key
(K1, K2, K3, K4) = (00001111, 11110000, 00001111, 11110000).
Please also show the intermediate results (i.e., the rows A, B, D, E, F, G, H, and I from Figure 1). You can write directly on Figure 1, but remember to hand in this sheet.
(b) Find in the missing entries in row 10 of the linear approximation table of Figure 3.
(c) Find a linear approximation that relates the bit H7 to a suitable subset of the plaintext bits, with high probability bias. You can draw this directly on Figure 1, but remember to hand in this sheet.
(d) What is the total probability bias of the linear approximation you found in part (a)?
6
P1 …
plaintext
… P8
subkey K1 mixing
A1
…
…
…
…
…
…
S11
S12
B1
D1
… … … … …
… … … … …
…
…
subkey K2 mixing
E1
…
…
…
…
…
…
S21
F1
G1
… … … … …
… … … … …
S22
…
…
subkey K3 mixing
H1
…
…
…
…
…
…
S31
S32
I1
…
…
…
…
…
…
subkey K4 mixing
C1 …
ciphertext
Figure 1: An SPN network
A8
B8
D8
E8
F8
G8
H8
I8
… C8
Input: 0000 0001 0010 0011 0100 0101 0110 0111 Output: 1110 0011 0100 1000 0001 1100 1010 1111
Input: 1000 1001 1010 1011 1100 1101 1110 1111 Output: 0111 1101 1001 0110 1011 0010 0000 0101
Figure 2: The S-box for the SPN network
7
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 08000000000000000 1 0 0 0 0 2−2 2−2 0 0 4 4−2 2 2−2 2 0−2−2 0 0−2−2 0 0−2−2 0 4 2 2−4 3 0−2−2 0−2 0 4 2 0−2 2−4−2 0 0−2 4 0 0 0 0−2−2 2 2 0 0−4 4−2−2−2−2 5 0 0 0 0−4 0 0−4 0 0 0 0 0 4−4 0 6 0−2−2 0−2 4 0 2 0−2 2 4 2 0 0 2 7 0 6−2 0 0 2 2 0 0−2−2 0 0 2 2 0 8 0 2 0 2 0−2 0−2−2−4 2 0 2−4−2 0
9 0 2 0−6−2 10002−20
11 0 0 2−2 2
12 0 2 0 2 2
13 0 2 0 2−4−2 0 14 0 0−6−2 2−2 0 15 0 0 2−2 0 0−2
0 2 0 2 0 0−2 0−2 22−2002204 0−2 2 0 0 4 0−2−2 4 2 0 2 0 0 2−4−2 2−2 4 2 0 2 0 2 0 0−2 2 0 0 0 0−2 2 2−6−2 0 0−2 2 0 0
0−2 2 4
0−2
Figure 3: The linear approximation table for the S-box
8