4th-Year

CRYPTOGRAPY
University of Batna 2 Computer Networks Engineering
Department of Computer Science [Link] Karima

Solution of Tutorial Session No. 1

Exercise 1 :
Symmetric cryptography, also known as secret-key cryptography, is an encryption system in
which the same key is used for both encryption and decryption. Both the sender and the
receiver must share this secret key securely before communication begins.

Advantages :
 Speed : Symmetric algorithms are computationally faster and require less processing
power than asymmetric systems. (Examples : AES, DES, ChaCha20.)
 Eciency : Well-suited for encrypting large amounts of data such as les, audio, or video.
 Simplicity : The algorithms are generally simpler to implement and require fewer re-
sources.
Disadvantages :
 Key distribution problem : The secret key must be securely shared between parties
before communication. If the key is intercepted, the system is compromised.
 Scalability issue : In a network with
N users, each pair of users requires a unique key,
N (N −1)
resulting in keys in total.
2
 Lack of non-repudiation : Since both parties share the same key, it is impossible to
prove who created a specic message.
Comparison with Asymmetric Cryptography :
Symmetric cryptography uses the same key for both encryption and decryption, making it
fast but less secure for key distribution. In contrast, asymmetric cryptography uses a pair of
keys (a public key and a private key), which simplies key exchange and enhances security,
but the process is slower and computationally more expensive.

Exercise 2 :
1) Symmetric-key system
Each pair of nodes shares one unique secret key. For N =3 (nodes A, B , and C) :

KAB , KAC , KBC

Each node stores N −1 = 2 keys, but since each key is shared between two nodes, the total
number of unique keys in the system is :

N (N − 1) 3×2
= =3
2 2

Each node : 2 keys Total unique keys : 3

2) Asymmetric-key system
Each node has its own key pair (Kipub , Kipriv ). To communicate securely, each node must store
its private key and the public keys of the others.

Page 1
 4th-Year

CRYPTOGRAPY
University of Batna 2 Computer Networks Engineering
Department of Computer Science [Link] Karima

For N =3 :

A : (KApriv , KBpub , KCpub ) B : (KBpriv , KApub , KCpub ) C : (KCpriv , KApub , KBpub )

Thus, each node stores 1 + (N − 1) = 3 keys, and the system contains :

2N = 6 keys in total (3 private + 3 public).

Each node : 3 keys Total keys : 6

Exercise 3 :
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Plain Alphabet
Caesar Alphabet ( 3) D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
Encryption : The Caesar Cipher shifts each letter by a key k. Let k=3 (classical Caesar
shift).

Plaintext : the big bang theory

Ciphertext :
wkh elj edqj wkhrub
1. Key space : The Caesar cipher shifts each letter by a xed number k ∈ {1, 2, . . . , 25}.
Hence, the key space is of size 25.
2. Decryption of ciphertext : Ciphertext : edwqd xqlyhuvlwb
We test all possible shifts k = 1, . . . , 25. Because the key space is very small (25 possibili-
ties), it is easy to perform an exhaustive search. For k = 3, we get :

k=3
edwqd xqlyhuvlwb −−→ batna university

(example result depending on ciphertext).

Thus, the Caesar cipher is insecure due to its very limited key space.

Exercise 4 :
Keyword : BALLOON → remove duplicates ⇒ BALON.
Substitution alphabet :

Plain A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Cipher B A L O N C D E F G H I J K M P Q R S T U V W X Y Z
1. Encryption :  ATTACK AT DAWN

AB, TT, TT, AB, CL, KH ⇒ BTTBLH

ATBT, DAWNOBWK
Ciphertext : BTTBLH BT OBWK

Page 2
 4th-Year

CRYPTOGRAPY
University of Batna 2 Computer Networks Engineering
Department of Computer Science [Link] Karima

2. Key space :
26
X 26!
|K| =
k=1
(26 − k)!
This space is enormous compared to Caesar's 25 possible keys.

Comment : Larger key space= stronger against brute force, but still vulnerable to frequency
analysis since it's monoalphabetic.

Exercise 5 :
Consider the Ane cipher E(x) = (ax + b) mod 26 with a = 5 and b = 8, and the usual
encoding A = 0, . . . , Z = 25.
1. Encryption of CRYPTO.
Convert letters to numbers : C = 2, R = 17, Y = 24, P = 15, T = 19, O = 14.
Apply E(x) = (5x + 8) mod 26 :

x 2 17 24 15 19 14
E(x) 18 15 24 5 25 0

Mapping back to letters : 18 → S, 15 → P, 24 → Y, 5 → F, 25 → Z, 0 → A.

Ciphertext : SPYFZA
2. Key space.
a must be invertible modulo 26, so a must satisfy gcd(a, 26) = 1. There are φ(26) = 12
such values of a. b can be any of 26 values. Hence the number of valid key pairs (a, b) is

12 × 26 = 312.

3. Why not all values of a are valid.

Ifgcd(a, 26) ̸= 1, multiplication by a is not invertible mod 26, so the encryption map is not
bijective and decryption (unique recovery of plaintext) is impossible. Thus only a coprime
with 26 are allowed.

4. Decryption of ELBOHD with the same keys.

First compute a−1 mod 26. For a = 5 we have 5−1 ≡ 21 (mod 26) because 5 · 21 = 105 ≡ 1
(mod 26). Decryption formula :

P (x) = a−1 (C − b) mod 26.

Convert ELBOHD to numbers : E = 4, L = 11, B = 1, O = 14, H = 7, D = 3. Subtract

b=8 (mod 26) and multiply by 21 :

C 4 11 1 14 7 3
C −b 22 3 20 6 25 21
P = 21(C − b) mod 26 20 11 9 22 5 25

Map back to letters : 20 → U, 11 → L, 9 → J, 22 → W, 5 → F, 25 → Z .

Plaintext : ULJWFZ

Page 3
 4th-Year

CRYPTOGRAPY
University of Batna 2 Computer Networks Engineering
Department of Computer Science [Link] Karima

Exercise 6 : 
Total number of possible keys :

264 = 18 446 744 073 709 551 616

 Average number of keys to test (half the keyspace) :

263 ≈ 9.22 × 1018

 Speed of testing :
1 key per picosecond = 1 × 10−12 s/key

 Average time to nd the correct key :

T = 263 × 10−12 s ≈ 9.22 × 106 s

Conversions :

9.22 × 106
9.22 × 106 s ≈ days ≈ 106.8 days ≈ 0.29 years.
86400

Remark : Even with an attacker testing one key per picosecond, a 64-bit key can be found in
about 107 days on average, which is insucient for modern security ; using longer keys (e.g.
128 or 256 bits) is recommended.

Page 4