Introduction to Cryptography Chapter 3

Exercise 3.16.1

#include <iostream>
using namespace std;

int main(){
    string input = "VHFUHW";
    for(int shift = 0; shift < 26; shift++){
        cout << "shift: " << shift << " ";
        for (char chr : input) cout << char('A' + (chr - 'A' + step) % 26);
        cout << endl;
    }
}

Results

shift: 0 VHFUHW
shift: 1 WIGVIX
...
shift: 22 RDBQDS
shift: 23 SECRET
shift: 24 TFDSFU
shift: 25 UGETGV

The Answer is SECRET.

Exercise 3.16.2

The plaintext space, cipher text space are $\Sigma = \lbrace A, B, ..., Z\rbrace$ . The key space is $\mathbb{Z}_{26} \times \mathbb{Z}_{26}$ .

Exercise 3.16.4

The number of palindromes having length $n$ over an alphabet $\Sigma$ is ${|\mathbb Z|}^{k}$ , where $k = \lceil n/2 \rceil$ .

Exercise 3.16.6

The number of possible blocks is $2^{n}$ . The key space is the set $S({\lbrace 0, 1\rbrace}^{n})$ of all permutations of ${\lbrace 0, 1\rbrace}^{n}$ and contains $(2^{n})!$ elements. so the answer is $(2^{n})!$ .

Exercise 3.16.7

The latter scheme is a cryptosystem. The encryption functions must be injective. The former scheme, however, the function isn't injective if ${\rm gcd}(k, 26) {\neq} 1$ . For example, if $k = 13$ , letters ${\sigma}_{1} = 0$ and ${\sigma}_{2} = 2$ lead the same cipher $0$ .

The plaintext space of the latter scheme is $\Sigma = \mathbb{Z}_{26}$ , the ciphertext space is also $\mathbb{Z}_{26}$ and the key space is $\lbrace1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25\rbrace$ .

Exercise 3.16.8

A tuple $(P, C, K, \Sigma , D)$ with the following properties:

$P = \mathbb{Z}_{2}$
$C = \mathbb{Z}_{4}$
$K = \lbrace2\rbrace$
$\Sigma = \lbrace E_0, E_1 \rbrace$ , where $p \in P, k \in K, E_0(p) = kp, E_1(p) = kp+1$
$D = \lbrace D_0, D_1 \rbrace$ , where $c \in C, k \in K, D_0(c) = \frac{c}{k}, D_1(c) = \frac{c-1}{k}$

Exercise 3.16.9

the number of bit permutations: $(n)!$

the number of circular right shifts: $n-1$ (or $n$ if 0 shift is included.)

Exercise 3.16.11

The answer can be represented below:

$\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$

For instance, a plaintext $p=11100$ will be transformed into $c=00011$

Exercise 3.16.12

$\begin{pmatrix} (0, 0, 0) & (1, 0, 0) & (0, 1, 0) & (0, 0, 1) & (1, 1, 0) & (1, 0, 1) & (0, 1, 1) & (1, 1, 1) \\ (0, 0, 0) & (1, 0, 0) & (0, 1, 0) & (0, 0, 1) & (0, 1, 1) & (1, 1, 0) & (1, 0, 1) & (1, 1, 1) \end{pmatrix}$

, where $n = 3$ .

$Proof$

Suppose the permutation above is affine linear. We can say there is a matrix $\mathbb{A} \in {\lbrace0, 1\rbrace}^{(3, 3)}$ , and a vector ${\bf b} \in {\lbrace0, 1\rbrace}^{3}$ such that:

f({\bf v}) = \mathbb{A}{\bf v} + {\bf b}{\quad}mod2

for all ${\bf v} \in {\lbrace0, 1\rbrace}^{3}$ .

Since $f( (0, 0, 0) ) = (0, 0, 0)$ ,

$(0, 0, 0) = (\mathbb{A}(0, 0, 0) + {\bf b}){\quad}mod 2 \\ (0, 0, 0) = {\bf b}{\quad}mod 2 \\ \therefore {\bf b} = (0, 0, 0)$

$f( (1, 0, 0) ) = (1, 0, 0)$ , $f( (0, 1, 0) ) = (0, 1, 0)$ , $f( (0, 0, 1) ) = (0, 0, 1)$

$\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} = (\mathbb{A} \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} ){\quad}mod 2 \\ \therefore \mathbb{A} = \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$

Therefore,

$f( (1, 1, 0) ) = ( \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} (1, 1, 0) ){\quad}mod 2 \\ \therefore f( (1, 1, 0) ) =(1, 1, 0)$

But we know that $f( (1, 1, 0) ) = (0, 1, 1)$ and $(1, 1, 0) \neq (0, 1, 1)$ . Hence, The permutation above is not affine linear.

Exercise 3.16.14

ciphertext: $m = 111111111111$ with length $u=12$ block length: $n=3$ key:

$k = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$

ECB mode

ciphertext blocks:

$m_{1} = 111, \quad m_{2} = 111, \quad m_{3} = 111, \quad m_{4} = 111$

ciphertext blocks:

$c_{1} = 111, \quad c_{2} = 111, \quad c_{3} = 111, \quad c_{4} = 111$

ciphertext: $c = 111111111111$

CFB mode

$r = 2$

plaintext blocks:

$m_{1} = 11, \quad m_{2} = 11, \quad m_{3} = 11, \\ m_{4} = 11, \quad m_{5} = 11, \quad m_{6} = 11$

initialization vector: $I_{1} = IV = 000$

$j$	$I_{j}$	$O_{j}$	$t_{j}$	$m_{j}$	$c_{j}$
1	000	000	00	11	11
2	011	110	11	11	00
3	100	001	00	11	11
4	011	110	11	11	00
5	100	001	00	11	11
6	011	110	11	11	00

ciphertext blocks:

$c_{1} = 11, \quad c_{2} = 00, \quad c_{3} = 11, \\ c_{4} = 00, \quad c_{5} = 11, \quad c_{6} = 00$

ciphertext: $c = 110011001100$

OFB mode

$r = 2$

plaintext blocks:

$m_{1} = 11, \quad m_{2} = 11, \quad m_{3} = 11, \\ m_{4} = 11, \quad m_{5} = 11, \quad m_{6} = 11$

initialization vector: $I_{1} = IV = 000$

$j$	$m_{j}$	$c_{j}$
1	11	11
2	11	11
3	11	11
4	11	11
5	11	11
6	11	11

ciphertext blocks:

$c_{1} = 11, \quad c_{2} = 11, \quad c_{3} = 11, \\ c_{4} = 11, \quad c_{5} = 11, \quad c_{6} = 11$

ciphertext: $c = 111111111111$

Exercise 3.16.15

ECB mode

cipertext: $c=011100011100$

CBC mode

cipertext: $c=011001010000$

CFB mode

$j$	$I_{j}$	$O_{j}$	$t_{j}$	$m_{j}$	$c_{j}$
1	000	000	00	10	10
2	010	100	10	10	00
3	000	000	00	10	10
4	010	100	10	10	00
5	000	000	00	10	10
6	010	100	10	10	00

ciphertext: $c=100010001000$

OFB mode

$j$	$m_{j}$	$c_{j}$
1	10	10
2	10	10
3	10	10
4	10	10
5	10	10
6	10	10

ciphertext: $c=101010101010$

Exercise 3.16.18

-18

Exercise 3.16.19

Sarrus' rule:

$\begin{vmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{vmatrix}\\ = a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} \\ \quad - a_{11}a_{23}a_{32} - a_{12}a_{21}a_{33} - a_{13}a_{22}a_{31}$

Exercise 3.16.20

${\bf v} \mapsto {\bf Iv} + (1, 1, 1) \quad {\rm mod} 2$

, where ${\bf I} \in \mathbb{Z}^{(3, 3)}$ is an identity matrix.

Exercise 3.16.21

$\begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \end{pmatrix}$

Note that each elements must be in $\lbrace 0, 1\rbrace$ .

Exercise 3.16.22

${\bf v} \mapsto {\bf Iv} + (14, 9, 1) \quad {\rm mod} 26$

The key is $(A, {\bf b}) = ({\bf I}, (14, 9, 1))$ , , where ${\bf I} \in \mathbb{Z}^{(3, 3)}$ is an identity matrix.

Note that we identify the alphabet $\lbrace A,B..., Z\rbrace$ according to Table 3.1 with the numbers $\lbrace 0, 1, ..., 25\rbrace$ .

$j$	$I_{j}$	$O_{j}$	$t_{j}$	$m_{j}$	$c_{j}$
1	000	000	00	11	11
2	011	110	11	11	00
3	100	001	00	11	11
4	011	110	11	11	00
5	100	001	00	11	11
6	011	110	11	11	00

$j$	$m_{j}$	$c_{j}$
1	11	11
2	11	11
3	11	11
4	11	11
5	11	11
6	11	11

$j$	$I_{j}$	$O_{j}$	$t_{j}$	$m_{j}$	$c_{j}$
1	000	000	00	10	10
2	010	100	10	10	00
3	000	000	00	10	10
4	010	100	10	10	00
5	000	000	00	10	10
6	010	100	10	10	00

$j$	$m_{j}$	$c_{j}$
1	10	10
2	10	10
3	10	10
4	10	10
5	10	10
6	10	10

$j$	$I_{j}$	$O_{j}$	$t_{j}$	$m_{j}$	$c_{j}$
1	000	000	00	11	11
2	011	110	11	11	00
3	100	001	00	11	11
4	011	110	11	11	00
5	100	001	00	11	11
6	011	110	11	11	00

$j$	$m_{j}$	$c_{j}$
1	11	11
2	11	11
3	11	11
4	11	11
5	11	11
6	11	11

$j$	$I_{j}$	$O_{j}$	$t_{j}$	$m_{j}$	$c_{j}$
1	000	000	00	10	10
2	010	100	10	10	00
3	000	000	00	10	10
4	010	100	10	10	00
5	000	000	00	10	10
6	010	100	10	10	00

$j$	$m_{j}$	$c_{j}$
1	10	10
2	10	10
3	10	10
4	10	10
5	10	10
6	10	10

$j$	$I_{j}$	$O_{j}$	$t_{j}$	$m_{j}$	$c_{j}$
1	000	000	00	11	11
2	011	110	11	11	00
3	100	001	00	11	11
4	011	110	11	11	00
5	100	001	00	11	11
6	011	110	11	11	00

$j$	$m_{j}$	$c_{j}$
1	11	11
2	11	11
3	11	11
4	11	11
5	11	11
6	11	11

$j$	$I_{j}$	$O_{j}$	$t_{j}$	$m_{j}$	$c_{j}$
1	000	000	00	10	10
2	010	100	10	10	00
3	000	000	00	10	10
4	010	100	10	10	00
5	000	000	00	10	10
6	010	100	10	10	00

$j$	$m_{j}$	$c_{j}$
1	10	10
2	10	10
3	10	10
4	10	10
5	10	10
6	10	10