ECE4802/CS4801 Assignment #2 Solution

1- DES

Input:
bit # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
bit 1 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1 0 0 1 1 0

Round Key:
bit # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
bit 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 0 0 1 1 0 0 0 1 0

bit # 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
bit 1 1 0 1 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 1 1 1 1

Permutation table DES Expansion Table

P
16 7 20 21 29 12 28 17
1 15 23 26 5 18 31 10
2 8 24 14 32 27 3 9
19 13 30 6 22 11 4 25

E
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1


a- Extend the input to 48 bits using DES expansion function b- Add (XOR) the given round key to the expanded input bits.
c- Using 8 DES S-boxes, find the 32-bit output of substitution step. DES S-boxes are presented in the DES paper, appendix 1 (pages 17-18).
d- Permute the S-box output using the given permutation table.

2- AES

Compute the given steps below. You can use AES specification for more explanation. Show your work and present the results in a table to make it easy to follow.

a- Convert the given 128-bit input to Hexadecimal form.
b- Write the input in a state diagram (4 by 4 matrix).
c- Apply SubBytes Step: use AES S-box to substitute the input.
d- Apply ShiftRows Step.
e- Apply Mixcolumns Step: use Irreducible polynomial 𝑃(𝑥) = 𝑥8 + 𝑥4 + 𝑥3 + 𝑥 + 1.
f- Apply AddRoundKey Step: use the given round key.


128-bit input
bit # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
bit 0 1 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 0

bit # 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
bit 0 1 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 0 1 1 0 1 1 0 1 0 0 0 0 1 1

bit # 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
bit 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0

bit # 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
bit 1 0 0 1 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 1 1 1


AES S-box Table


Round Key

bit # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
bit 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 1 0 1 0 1 1 0

bit # 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
bit 0 1 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1

bit # 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
bit 1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 1 0 1

bit # 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
bit 1 1 1 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 0







3- Modular Arithmetic is the basis of many cryptosystems. As a consequence, we will address this topic with several problems in this and upcoming chapters.

a- Compute the results:
i. 37 ⋅ 3 𝑚𝑜𝑑 23
ii. 19 ⋅ 13 𝑚𝑜𝑑 23 iii. 18 ⋅ 15 𝑚𝑜𝑑 12
iv. 15 ⋅ 29 + 11 ⋅ 15 𝑚𝑜𝑑 23

b- Find the inverses in the given modular spaces:
v. 8−1 𝑚𝑜𝑑 17 vi. 5−1 𝑚𝑜𝑑 17 vii. 5−1 𝑚𝑜𝑑 37 viii. 10−1 𝑚𝑜𝑑 15


c- List all elements of modulo 216 with no multiplicative inverse.