The University of Melbourne
School of Computing and Information Systems COMP90043 Cryptography and Security
Assignment 1, Semester 2 2022
Hints and Solutions
1. Security Properties [10 marks]
Describe one security threat in each of the following security properties, with regard
to the use of the COVIDSafe app1.
(a) Confidentiality (b) Integrity (c) Availability
2. Classical Ciphers [20 marks]
Consider the following version of a classical cipher where plaintext and ciphertext elements are the integers from 0 to 27. The encryption function, which maps any plaintext p to a ciphertext c, is given by
c = E(a,b)(p) = (ap + b) mod 28, where a and b are integers less than 28.
(a) Derive the decryption function for the scheme. Show your working.
(b) A key is considered to be trivial if c = p for all input p. How many non-trivial keys are possible for this scheme?
(c) Should this cipher be considered as mono-alphabetic cipher or poly-alphabetic cipher? Why?
1https://www.health.gov.au/resources/apps-and-tools/covidsafe-app 1
p = D(a,b)(c) = a−1(c − b) mod 28, where a−1 is the multiplicative inverse of a mod 28.
b could be any integer between 0 and 27 (both inclusive).
a has to be relatively prime to 28 (otherwise a−1 mod 28 does not exist).
i.e. a ∈ {1,3,5,9,11,13,15,17,19,23,25,27}
There are in total 28 × 12 = 336 possible keys. Out of which {a = 1,b = 0} is a trivial key as c = (ap + b) mod 28 = (1 × p + 0) mod 28 = p.
Thus the number of non-trivial key is 335.
It is a mono-alphabetic cipher. For any given key {a, b}, the encryption maps each letter in the plaintext into a fixed letter in the ciphertext.
(d) An oracle is available to you which can output the corresponding ciphertext for arbitrary plaintext you supply. Describe an efficient way to retrieve the key using this oracle.
We can use two plaintexts p1 and p2, to get their corresponding ciphertexts c1 and c2. We can then get (c1 −c2)mod28 = a(p1 −p2)mod28. In order to get a unique solution of a, (p1 − p2) must have a multiplicative inverse under modulo 28.
As an example, we can feed the oracle with p1 = 0, the encrypted result should bec1 =(ap1+b)mod28=(a×0+b)mod28=b. Thenforp2 =1,wewill get c2 = (ap2 +b) mod 28 = (a×1+b) mod 28 = (a+b) mod 28. The value of acouldberecoveredbya=c2 −bmod28.
3. Poly-alphabetic Cipher [25 marks]
For this question, we consider a cipher working on an alphabet A consisting of 26 English characters (A-Z), plus underscore (_), comma (,) and full stop (.), which corresponds to integers 0 to 28. The encryption is done by:
ciphertext = C2(C1(plaintext))
Here C1 is the encryption function used in Hill cipher. The plaintext is processed successively in blocks of size m. The encryption algorithm takes a block with m plain- text digits (p1, p2, · · · , pm) and transforms into a cipher block of size m (c1, c2, · · · , cm) using a key matrix of size m × m by the linear transformation, which is given by:
c1 = (k1,1p1 + k1,2p2 + ··· + k1,mpm) mod 29 c2 = (k2,1p1 + k2,2p2 + ··· + k2,mpm) mod 29 ···
cm = (km,1p1 + km,2p2 + ··· + km,mpm) mod 29
C2 is the encryption function used in Vernam cipher. It processes a block of plaintext at a time, and produces a same length ciphertext. In this task, our Vernan cipher uses the same block size m as used in Hill cipher. The encryption is performed by:
c1 =p1 +K1 mod29 c2 =p2 +K2 mod29 ···
cm =pm +Km mod29
Note: For this question, correspondence between plaintext and number modulo 27 are asfollows“A” ↔ 0,“B” ↔ 1,“C” ↔ 2, …, “Z” ↔ 25,“_”↔ 26,“,”↔ 27 and “.” ↔ 28. All following tasks use block size m = 6.
Code Help, Add WeChat: cstutorcs
(a) This cipher is easily broken with a known plaintext attack. Given the follow- ing combination of plaintext and ciphertext, your task here is to recover the encryption keys (for both Hill cipher and Vernam cipher). Please map the last five digits of your student number using the above correspondence, and use it as the “?????” in plaintext and ciphertext. For example, if your student number is 1234567, you should take the last five digits 34567 and use DEFGH to replace both “?????” below.
Plaintext PMZRTZYFQFTPIRBRXXKECAHRPMZRTZYZHHK?????HKVYNGQX Ciphertext XRDREZLE?????XOHHKVUPYONXRDREZHZHPRBJVGLHMSPNJBU
Make sure to show details of your working, including any tool/package/library used, and/or programs developed. Only showing the final result and/or a pro- gram may attract penalties.
We can rewrite the encryption function using matrix multiplication:
ck k ···kpK
c2 = k2,1 k2,2 ··· ··· ··· ··· ···
k2,m × p2 + K2 (mod 29)
··· ··· ··· ckk···kpK
m,m m pm ··· k1,m K1 1
further extended as:
ccc···c 1 m+1 2m+1 nm+1
c2 cm+2 c2m+2 · · · cnm+2 ··· ··· ··· ··· ···
··· ··· ··· pm
For multiple blocks of plaintext-ciphertext pairs, the above formula can be
m,1 m,2 k1,1 k1,2
···k Kp2
2,m 2×···(mod 29)
k k =2,1 2,2
km,1 km,2 ··· km,m Km 1
m m+m 2m+m nm+m
k ··· k K p1 pm+1 p2m+1 ··· pnm+1
· · · pnm+2
The above plaintext matrix has m + 1 rows. Once it has m + 1 columns, it becomes a square matrix and it may have a multiplicative inverse of mod 29.
1,1 1,m 1 p2 pm+2
=k2,1 ··· k2,m K2 × ···
··· (mod 29)
··· k···kKmm+m2m+m nm+m
··· ··· ··· ··· p p
m,1 m,m m 1 1 1 ··· 1
Code Help
(solution continued)
By multiplying the multiplicative inverse of the plaintext matrix to both sides of the equation, the key matrix can be calculated.
1,1 1,2 k2,1 k2,2
··· ··· km,1 km,2
The following solution is based on student number 1000000.
The given plaintext and ciphertext combination is (spaces added to separate blocks):
P = PMZRTZ YFQFTP IRBRXX KECAHR PMZRTZ YZHHKA AAAAHK VYNGQX C = XRDREZ LEAAAA AXOHHK VUPYON XRDREZ HZHPRB JVGLHM SPNJBU
Based on the above discussion, we require m + 1 = 7 blocks of plaintext- ciphertext pairs in order to calculate the key matrix. There are eight blocks presented here. However, the fifth block is identical to the first block thus should be removed (why? check task (c) answer).
··· k2,m K2
··· ··· ···
···km,mKm −1
··· pnm+2
··· c p1 pm+1 nm+1 p2 pm+2
··· cnm+2 × ···
m m+m nm+m 11
· · · · · · · · · · · · p p
··· ··· (mod29)
· · · p c c ··· c m m+m nm+m
Following the above
process, the key matrix can be calculated:
8 131924162315
··· k1,m K1 01528
··· k2,m K2= 15 20 25
··· ··· ··· 5 24 25
··· km,m Km 16 4 8 6 141520
k1,1 k2,1
2615421 1301112 27 21 7 26
k2,2 ··· ···
Hence, the encryption key used in Hill cipher is:
8 13 19 24 16 23 I N T Y Q X
0 15 28 26 15 4 A 15 20 25 13 0 11orP 5 24 25 27 21 7 F 16 4 8 6 14 15 Q
13 16 16 9 23 1 N The encryption key for Vernam cipher is [15
P . _ P E U Z N A L Y Z , V H E I G O P Q Q J X B
21 12 26 20 15] (PVM_UP).
13 16 16 9 23 1 15
(b) An adversary discovers the following ciphertext, which is encrypted using keys found in (a). There are 54 characters in total.
VQWBUQIDKILMWT_WJBBUDVKJWTOUTFOMVZZ,OFJRDMNK,.TZBZWUXU
Discuss how to recover the plaintext. Show the decryption key(s) used and the decrypted plaintext.
To recover the plaintext, we need to first apply the decryption function of Vernam cipher, then apply the decryption function of Hill cipher.
For Vernam cipher, the encryption key can be used in decryption, using the following decryption function:
pi = ci − Ki mod 29 , 1 ≤ i ≤ m
Observing that the encryption function of Hill cipher can be expressed using matrix multiplication, the decryption function can be derived using the multi- plicative inverse of the key matrix:
ckk···kp 1 1,1 1,2 1,m 1
c2 = k2,1 ··· ···
cm km,1 c k
k2,2 · · · k2,m × p2 (mod 29) ··· ··· ··· ···
1,1 1 1,1 1,1 1
k2,1 ··· × c2 = k2,1 ··· ··· ··· ···
km,1 ··· cm km,1
···−1 k ··· p
km,2 ··· km,m pm
··· ×k2,1 ···×p2(mod 29) ··· ··· ··· ···
··· km,1 ··· pm
··· × c2 = p2 (mod 29) ··· ··· ···
Using student number 1000000, the decryption key for Hill cipher is:
24 13 5 28 10 10 Y N F . K K 17 25 26 8 18 28 R Z _ I S . 1 20 15 9 7 28orB U P J H . 18 26 15 16 18 8 S _ P Q S I 18 4 2 7 21 25 S E C H V Z 13 3 26 16 14 10 N D _ Q O K
The decrypted message is:
THE_QUIETER_YOU_BECOME,_THE_MORE_YOU_ARE_ABLE_TO_HEAR.
···−1 c p 1,1 1 1
(c) How many different keys are possible in this system? Briefly justify your answer. 5
In Hill cipher, the number of valid keys is the number of invertible matrices of size m×m over Z29. Let’s consider each row of the key matrix one-by-one. The first row of the key matrix cannot have all-zeros, giving 29m−1 possibilities. The second row cannot be a multiple of the first row, giving 29m − 29 possibilities. The i-th row cannot be a linear combination of the first i − 1 rows, giving 29m − 29i−1 possibilities. The total valid keys can be calculated as:
∏mim m m2 mm−1
(29 −29 ) = (29 −1)×(29 −29)×(29 −29 )×…×(29 −29 In Vernam cipher, the number of possible keys is 29m.
For this task where m = 6, the total number of keys would be:
(296 −29i) ≈ 2.54×1061
4. Probability [20 marks]
Consider the following two experiments:
• Experiment 1: Alice flips a fair coin (0.5 probability of getting HEADS and 0.5 for TAILS), and shares the result with Bob.
• Experiment 2: Alice flips a fair coin, and always sends HEADS to Bob.
After each experiment, Bob needs to guess which experiment they were in. We can quantify the quality of Bob’s guess using the following formula:
Q = |P(W1) − P(W2)|
Here Wi refers to the event that Alice performed experiment i (i ∈ {1, 2}), while Bob guessed they were in experiment 1. We can see that Q = 0 indicates Bob cannot dis- tinguish the two experiments, while Q = 1 suggests Bob can always correctly identify which experiment they were in.
For the below tasks, apart from giving a numerical answer, please also show your working by providing formula used, and/or a short explanation.
(a) For each of the following strategies used by Bob, calculate the quality of Bob’s guess, Q.
i. Always guess experiment 2.
ii. Ignore the result reported by Alice, and randomly guess experiment 1 and experiment 2 with equal probability.
iii. Guessing experiment 1 if TAILS was shared from Alice, otherwise guess experiment 2.
iv. Guessing experiment 1 if HEADS was shared from Alice, otherwise guess experiment 2.
v. Guessing experiment 1 if TAILS was shared from Alice, otherwise randomly guess experiment 1 or 2 with equal probability.
In the formula, P(W1) stands for the conditional probability that Bob guessed correctly, under the condition where Alice chose experiment 1. P (W2) stands for the conditional probability that Bob’s guess was incorrect, under the condition where Alice performed experiment 2.
i. P(W1) = 0
ii. P(W1)=0.5
iii. P(W1) = 0.5
iv. P(W1) = 0.5
P(W2) = 0 P(W2)=0.5 P(W2) = 0 P(W2) = 1 P(W2) = 0.5
Q = 0.5 Q = 0.5 Q = 0.25
v. P(W1) = 0.75
A more systematic analysis is given in (b).
(b) What is the highest quality of Bob’s guess, Q? Briefly elaborate the strategy and justify your answer.
We could introduce two more variables to generalise this problem. Let x be the probability of Bob guessed experiment 1 under the condition that Alice shared HEADS, let y be the probability of Bob guessed experiment 1 under the condition that Alice shared TAILS. We can express P(W1) and P(W2) using x and y:
P ( W 1 ) = 21 ( x + y ) P(W2)=x
Hence we have Q = |P(W1) − P(W2)| = |1(x + y) − x| = |y−x| . 22
Noticing0≤x,y≤1,weget0≤Q≤0.5. Q=0.5canbeachievedusing either strategy iii or iv in the last question.
程序代写 CS代考 加QQ: 749389476