Cryptography HW#1
[1] We describe a special case of a Permutation Cipher. Let m, n be positive integers. Write out the plaintext, by rows, in m×n rectangles. Then form the ciphertext by taking the columns of these rectangles. For example, if m=3, n=4, then we would encrypt the plaintext “cryptography is interesting …” by forming the following rectangle:
crypising…
togr tere
aphystin
The ciphertext would be “CTAROPYGHPRYITSSETIRINENG…” Decrypt the following ciphertext, which was obtained by using this method of encryptionand find your key (m, n).
CNROGATLTUAIOTANHTYUAOHVERKBOENHSTIMESGSAE (42 digits in total.) (12 points)
Sol:
[2] The Autokey Cipher is the simple type of non-synchronous stream cipher.
Autokey Cipher :
P = C = K = L = Z26
z1=K, zi=xi-1 for all i>1
For x, y, z Z26
ez(x)=(x+z) mod 26
dz(y)=(y-z) mod 26
Decrypt the following ciphertext, obtained from the Autokey Cipher and find key K
DHVDZVJABR (12 points)
(平心靜氣,從K=0猜起,發現不像就K+1, good luck!)
Sol:
[3] (a)Find the number of positive integers 3600 that have a factor greater than 1 in
common with 3600.(5 points)
Sol:
(b)Describe a finite field of 7 elements and indicate the multiplicative inverse of
each nonzero element. (5 points)
Sol:
(c)Describe a finite field of 8 elements and indicate the multiplicative inverse of
each nonzero element.(You may use h(x)=x3+x+1 as your irreducible polynomial.) (7 points)
Sol:
[4] (a)In DES, what is the round function gKi (Li-1, Ri-1) and what is the inverse g Ki -1(Li, Ri), where Ki is ith round key. (You may express gKi by using f, Li-1, Ri-1, Ki and express gKi-1 by using f, Li, Ri, Ki.) (6 points)
Sol:
(b) S3 below is the 3rd S-box of DES
What is the output of S3 if the input is 101001?
And what is the output of S3 if the input is 011011 (6 points)
Sol:
(c) In DES, you are given any pair (x, y), where x and y are of 64 bits.
What is the probability that there exists a key K such that DESK(x)=y?
(5 points)
Sol:
(d) In DES, you are given two plaintext-ciphertext pairs (x1, y1) and (x2, y2)
for some unknown real key K*. And if you find some key K in the exhaustive key search with DESK(x1)=y1 and DESK(x2)=y2, what is the probability that K=K*? (6 points)
Sol:
[5] Give a high-level description of AES to indicate how a plaintext x in AES is transformed to a ciphertext y. (Your answer should be limited in one page.)(12 points)
Sol:
[6] Suppose that the S-box is replaced by the following substitution .
x / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / A / B / C / D / E / F/ E / 1 / D / 4 / 2 / F / B / 8 / A / 3 / 6 / C / 9 / 5 / 0 / 7
The linear approximation table of values NL(a,b)-8 for this S-box is computed in the following table except A, B.
a\b / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / A / B / C / D / E / F0 / +8 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0
1 / 0 / +2 / -2 / -4 / +2 / 0 / 0 / +2 / -2 / +4 / 0 / +2 / 0 / +2 / +2 / 0
2 / 0 / -2 / -2 / -4 / +2 / 0 / 0 / -2 / 0 / -2 / +2 / 0 / +2 / 0 / -4 / +2
3 / 0 / +4 / 0 / 0 / 0 / 0 / 0 / -4 / -2 / -2 / -2 / +2 / -2 / +2 / -2 / -2
4 / 0 / +2 / 0 / -2 / -2 / -4 / -2 / 0 / 0 / -2 / 0 / +2 / +2 / -4 / +2 / 0
5 / 0 / 0 / -2 / -2 / -4 / +4 / +2 / +2 / -2 / -2 / 0 / 0 / -2 / -2 / 0 / 0
6 / 0 / 0 / -2 / +2 / +4 / 0 / +2 / +2 / 0 / -4 / +2 / +2 / 0 / 0 / +2 / -2
7 / 0 / +2 / 0 / +2 / -2 / 0 / -2 / 0 / -2 / 0 / A / 0 / 0 / +2 / 0 / +2
8 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / -2 / +2 / +2 / -2 / +2 / -2 / -2 / -6
9 / 0 / -2 / -2 / 0 / -2 / 0 / -4 / +2 / 0 / -2 / -2 / 0 / +2 / +4 / 0 / -2
A / 0 / +2 / -2 / 0 / -2 / 0 / +4 / -2 / +2 / 0 / 0 / -2 / +4 / +2 / +2 / 0
B / 0 / +4 / 0 / 0 / 0 / 0 / 0 / +4 / +4 / 0 / 0 / 0 / 0 / 0 / -4 / 0
C / 0 / -2 / +4 / -2 / B / 0 / +2 / 0 / +2 / 0 / +2 / +4 / 0 / +2 / 0 / -2
D / 0 / 0 / +2 / +2 / 0 / 0 / +2 / +2 / -4 / 0 / -2 / +2 / +4 / 0 / -2 / +2
E / 0 / 0 / +2 / -2 / 0 / -4 / +2 / +2 / -2 / -2 / 0 / -4 / -2 / +2 / 0 / 0
F / 0 / -2 / -4 / +2 / -2 / -4 / +2 / 0 / 0 / +2 / 0 / +2 / -2 / 0 / -2 / 0
(a)Calculate A and B by the corresponding truth tables (you may use the following presentation of ). (6 points)
Sol:
0 / 0 / 0 / 0 / 1 / 1 / 1 / 0
0 / 0 / 0 / 1 / 0 / 0 / 0 / 1
0 / 0 / 1 / 0 / 1 / 1 / 0 / 1
0 / 0 / 1 / 1 / 0 / 1 / 0 / 0
0 / 1 / 0 / 0 / 0 / 0 / 1 / 0
0 / 1 / 0 / 1 / 1 / 1 / 1 / 1
0 / 1 / 1 / 0 / 1 / 0 / 1 / 1
0 / 1 / 1 / 1 / 1 / 0 / 0 / 0
1 / 0 / 0 / 0 / 1 / 0 / 1 / 0
1 / 0 / 0 / 1 / 0 / 0 / 1 / 1
1 / 0 / 1 / 0 / 0 / 1 / 1 / 0
1 / 0 / 1 / 1 / 1 / 1 / 0 / 0
1 / 1 / 0 / 0 / 1 / 0 / 0 / 1
1 / 1 / 0 / 1 / 0 / 1 / 0 / 1
1 / 1 / 1 / 0 / 0 / 0 / 0 / 0
1 / 1 / 1 / 1 / 0 / 1 / 1 / 1
(b)The trail we choose in the linear attack is shown in the following figure.
What is the total bias of this trail? (Show your steps.) (10 points)
Sol:
(c) From the above figure, list all the random variables of plaintext bits, bits of U4 and key bits, which are involved in this attack. (8 points)
Sol:
1