CNS Tut 6 Solution

Tutorial-VII (Symmetric Ciphers & Revision)

(i) Use an affine cipher to encrypt the message “hello” with the key pair (7, 2).
(ii) Use the affine cipher to decrypt the message “ZEBBW” with the key pair (7, 2) in modulus 26. (i) Encrypt “hello” (h=7, e=4, l=11, o=14) with key (a=7, b=2) mod 26. Encryption: $E (x) = (a x + b) (mod m) = (7 x + 2) (mod 26)$ .
- $E (7) = (7 \cdot 7 + 2) (mod 26) = 51 (mod 26) = 25 \to Z$
- $E (4) = (7 \cdot 4 + 2) (mod 26) = 30 (mod 26) = 4 \to E$
- $E (11) = (7 \cdot 11 + 2) (mod 26) = 79 (mod 26) = 1 \to B$
- $E (11) = 1 \to B$
- $E (14) = (7 \cdot 14 + 2) (mod 26) = 100 (mod 26) = 22 \to W$ Ciphertext: ZEBBW
(ii) Decrypt “ZEBBW” (Z=25, E=4, B=1, W=22) with key (a=7, b=2) mod 26. Find $a^{- 1} = 7^{- 1} (mod 26)$ . $7 \times 15 = 105 = 4 \times 26 + 1$ , so $a^{- 1} = 15$ . Decryption: $D (y) = a^{- 1} (y - b) (mod m) = 15 (y - 2) (mod 26)$ .
- $D (25) = 15 (25 - 2) (mod 26) = 15 \times 23 (mod 26) = 345 (mod 26) = 7 \to h$
- $D (4) = 15 (4 - 2) (mod 26) = 15 \times 2 (mod 26) = 30 (mod 26) = 4 \to e$
- $D (1) = 15 (1 - 2) (mod 26) = 15 \times (- 1) (mod 26) = - 15 (mod 26) = 11 \to l$
- $D (1) = 11 \to l$
- $D (22) = 15 (22 - 2) (mod 26) = 15 \times 20 (mod 26) = 300 (mod 26) = 14 \to o$ Plaintext: hello

2. Using the Rabin cryptosystem with $p = 47$ and $q = 11$ :

(i) Encrypt $P = 17$ to find the ciphertext.
(ii) Use the Chinese remainder theorem to find four possible plaintexts. Given: $p = 47$ , $q = 11$ , $P = 17$ . Public key $n = p \times q = 47 \times 11 = 517$ .

(i) Encryption: Ciphertext $C = P^{2} (mod n)$ . $C = 1 7^{2} (mod 517)$ $C = 289 (mod 517)$ Ciphertext $C = 289$ .

(ii) Decryption: We need to find the square roots of $C = 289$ modulo $n = 517$ . This involves solving $P^{2} \equiv 289$ modulo $p = 47$ and modulo $q = 11$ .

Solve $P^{2} \equiv 289 (mod 47)$ : $289 = 6 \times 47 + 7$ . So $P^{2} \equiv 7 (mod 47)$ . We know $1 7^{2} = 289 \equiv 7 (mod 47)$ , so $P \equiv 17 (mod 47)$ is a solution. The other solution is $P \equiv - 17 (mod 47) \equiv 30 (mod 47)$ . Solutions mod 47: $P \equiv \pm 17 \equiv {17, 30} (mod 47)$ .
Solve $P^{2} \equiv 289 (mod 11)$ : $289 = 26 \times 11 + 3$ . So $P^{2} \equiv 3 (mod 11)$ . We know $17 \equiv 6 (mod 11)$ , and $6^{2} = 36 \equiv 3 (mod 11)$ . So $P \equiv 6 (mod 11)$ is a solution. The other solution is $P \equiv - 6 (mod 11) \equiv 5 (mod 11)$ . Solutions mod 11: $P \equiv \pm 6 \equiv {6, 5} (mod 11)$ .
Combine using Chinese Remainder Theorem (CRT): We need to solve four systems of congruences:
- $P \equiv 17 (mod 47)$ , $P \equiv 6 (mod 11)$
- $P \equiv 17 (mod 47)$ , $P \equiv 5 (mod 11)$
- $P \equiv 30 (mod 47)$ , $P \equiv 6 (mod 11)$
- $P \equiv 30 (mod 47)$ , $P \equiv 5 (mod 11)$
Using CRT: $n_{1} = 47, n_{2} = 11, N_{1} = 11, N_{2} = 47$ . Find inverses: $N_{1}^{- 1} (mod n_{1}) = 1 1^{- 1} (mod 47) \equiv 30 (mod 47)$ (since $11 \times 30 = 330 = 7 \times 47 + 1$ ). $N_{2}^{- 1} (mod n_{2}) = 4 7^{- 1} (mod 11) \equiv 3^{- 1} (mod 11) \equiv 4 (mod 11)$ (since $3 \times 4 = 12 \equiv 1 (mod 11)$ ).

Solutions $P = (a_{1} N_{1} N_{1}^{- 1} + a_{2} N_{2} N_{2}^{- 1}) (mod n)$ : $P \equiv (a_{1} \cdot 11 \cdot 30 + a_{2} \cdot 47 \cdot 4) (mod 517)$ $P \equiv (330 a_{1} + 188 a_{2}) (mod 517)$
- Case 1: $a_{1} = 17, a_{2} = 6 ⟹ P \equiv 330 (17) + 188 (6) = 5610 + 1128 = 6738 \equiv 17 (mod 517)$ .
- Case 2: $a_{1} = 17, a_{2} = 5 ⟹ P \equiv 330 (17) + 188 (5) = 5610 + 940 = 6550 \equiv 346 (mod 517)$ .
- Case 3: $a_{1} = 30, a_{2} = 6 ⟹ P \equiv 330 (30) + 188 (6) = 9900 + 1128 = 11028 \equiv 171 (mod 517)$ .
- Case 4: $a_{1} = 30, a_{2} = 5 ⟹ P \equiv 330 (30) + 188 (5) = 9900 + 940 = 10840 \equiv 500 (mod 517)$ .

The four possible plaintexts are $P \in {17, 171, 346, 500}$ .

3. In the elliptic curve $E (1, 2)$ over the $GF (11)$ field: (Revision Problem)

(i) Find all points on the curve and make a figure.
(ii) Generate public and private keys for Bob.
(iii) Choose a point on the curve as a plaintext for Alice.
(iv) Create ciphertext corresponding to the plaintext in part d for Alice. (Note: This likely refers to part (iii))
(v) Decrypt the ciphertext for Bob to find the plaintext sent by Alice.

Quartz 4

Explorer

CNS Tut 6 Solution

Graph View

Backlinks