Ferhat Abbas – Sétif-1 University L3 Computer Science

Department of Computer Science 2025 - 2026

Computer Security
Tutorial-4 : Asymmetric Cryptography

Exercise 1 : RSA

I. Alice wants to construct an RSA cryptosystem using the two numbers p = 13 and q = 29.
1. What conditions must p and q satisfy ?
2. Which exponent e should be chosen among these values : 341, 9, 11 ?
3. Find the private key of Alice.
4. Among the values p, q, n, φ(n), e, and d, what values must remain secret?
II. Bob wants to construct an RSA cryptosystem using the numbers p = 11, q = 23, and e = 7.
1. Find the private key of Bob.
III. Bob wants to send the message M = 6 to Alice, what is the ciphertext?
IV. Alice wants to send the message M = 10 to Bob, what is the ciphertext?
V. Bob receives the ciphertext C = 5, what is the plaintext?
Correction
I.
1. p and q are two large (1024 bits) prime numbers, and p ≠ q.
2. Choose e, such as GCD (φ(n), e) = 1, and 1 < e < φ(n).
n = 13 * 29 = 377. φ(n) = (p-1) * (q-1) = 12 * 28 = 336.
• GCD (336, 341) = 1, but 341 > φ(n) : e ≠ 341.
• GCD (336, 9) ≠ 1 : e ≠ 9.
• GCD (336, 11) = 1, and 1 < 11 < 336, So e = 11.
The public key of Alice is (11, 377)
3. We find d, such as (e*d) mod φ(n) = 1, using the extended Euclide method,
e*u + φ(n)*v = 1, with u=d.
336 = 11 * 30 + 6 …… (1)
11 = 6 * 1 + 5 ………. (2)
6 = 5 * 1 + 1 ……... (3)
We stop when the reminder = 1.
From equation (3), we find :
1=6–5*1
We replace 5 by its equivalent from equation (2): 5 = 11 – 6 * 1 :
1 = 6 – (11 – 6 * 1) * 1
1 = 6 – 11 * 1 + 6 * 1
1 = 6 * 2 - 11 * 1.
We replace 6 by its equivalent from equation (1): 6 = 336 – 11 * 30 :
1 = (336 – 11 * 30) * 2 – 11 * 1
1 = 336 * 2 – 11 * 60 – 11 * 1
1 = 336 * 2 – 11 * 61
u = -61 mod 336 = 275
So d = 275.
The private key of Alice is (275, 377)
4. Alice can publish her public key (11, 377), but the values of p, q, φ(n), and d must be
kept secret.
1
II.
1. n = 11 * 23 = 253. φ(n) = (p-1) * (q-1) = 10 * 22 = 220.
The public key of Bob is (7, 253).
We find d, such as (e*d) mod φ(n) = 1, using the extended Euclide method,
e*u + φ(n)*v = 1, with u=d.
220 = 7 * 31 + 3 …… (1)
7 = 3 * 2 + 1 ……. (2)
We stop when the reminder = 1.
From equation (3), we find :
1=7–3*2
We replace 3 by its equivalent from equation (2): 3 = 220 – 7 * 31 :
1 = 7 – (220 – 7 * 31) * 2
1 = 7 – 220 * 2 + 7 * 62
1 = -220 * 2 + 7 * 63
d = 63.
The private key of Bob is : (63, 253)
III. Bob wants to send the message M = 6 to Alice, he uses the public key of Alice (11,377)
to encrypt the message. The encryption function is C = Me mod n.
C = 611 mod 377 = 154
C = 154
IV. Alice wants to send the message M = 10 to Bob, she uses the public key of Bob (7,253)
to encrypt the message. The encryption function is C = Me mod n.
C = 107 mod 253 = 175
C = 175
V. Whan Bob receives the ciphertext C = 5 from Alice, he uses his private key (Bob’s)
(63, 253) to decrypt the ciphertext. The decryption function is M = Cd mod n.
M = 563 mod 253
M = 53+6*2*5 mod 253
M = 53 mod 253 * (56 mod 253)2*5 mod 253
M = 125 * 1922*5 mod 253
M = 125 * (1922 mod 253)5 mod 253
M = 125 * 1795 mod 253
M = 125 * 1792+3 mod 253
M = 125 * (1792 mod 253) * (1793 mod 253) mod 253
M = 125 * 163 * 82 mod 253
M = 191.

2
Exercise 2: ElGamal

In this exercise, we focus on the ElGamal cryptographic algorithm.

I. Alice chose the values p = 17 and g = 3, and the private key x = 6.
• What is the public key of Alice?
II. Bob chose the values p = 23 et g = 7, and the private key x = 10.
• What is the public key of Bob?
III. Bob wants to send the message M = 12 to Alice, what is the ciphertext? (Let k = 5).
IV. Bob received the ciphertext (16, 22), what is the plaintext?
Correction
I.
• Alice’s public key: y = gx mod p = 36 mod 17 = 15,
Public key: (𝑝𝑝, 𝑔𝑔, 𝑦𝑦) = (17, 3, 15).
II.
• Bob’s public key: y = gx mod p = 710 mod 23 = 13,
Public key: (𝑝𝑝, 𝑔𝑔, 𝑦𝑦) = (23, 7, 13).
III. Bob wants to send the message M = 12 to Alice (with k = 5), he uses the public key of
Alice.
𝑐𝑐1=𝑔𝑔𝑘𝑘 mod 𝑝𝑝 = 35 mod 17 = 5,
𝑐𝑐2=𝑚𝑚 * 𝑦𝑦𝑘𝑘 mod 𝑝𝑝 = 12 * 155 mod 17 = 7
The ciphertext is: (𝑐𝑐1, 𝑐𝑐2) = (5, 7)
IV. Bob receives the ciphertext (16, 22), he uses his private key to decrypt.
𝑠𝑠 = 𝑐𝑐1x mod 𝑝𝑝 = 1610 mod 23 = 13
The modular inverse of 13 is 𝑠𝑠−1 mod 𝑝𝑝 = 13−1 mod 23 = 16
The plaintext : M = 𝑐𝑐2 * 𝑠𝑠−1 mod 𝑝𝑝 = 22 * 16 mod 23 = 7

Exercise 3: Diffie-Hellman
1. What is the purpose of the Diffie–Hellman algorithm?
2. Let p = 37 and g = 5 two integers shared between Alice and Bob. Alice chooses a = 6,
and Bob chooses b = 11.
3. Complete the Diffie–Hellman protocol to find the secret key K.
Correction
1. The Diffie–Hellman algorithm allows two people to agree on a shared secret key.
2. Alice side: A = ga mod p A = 56 mod 37 = 11
Bob side: B = gb mod p B = 511 mod 37 = 2
Alice sends A to Bob, and Bob sends B to Alice.
Bob calculates: K = Ab mod p:
K = 1111 mod 37 = 27

Alice calculates: K = Ba mod p

K = 26 mod 37 = 27

The shared secret key is K = 27.

3
Exercise 4: Hash functions

I. Mid-square hashing method

To compute the hash value of the message M (an integer) using the middle-square
hashing method consists of two steps:
• Compute the square of M.
• Extract the r middle digits as the hash value.
1. Find the digest of M = 695, with r = 2.
2. Which properties of a cryptographic hash function are satisfied or not satisfied by
this function?
II. Multiplication hashing method

This hashing method works in two steps:

• First, the message M is multiplied by a constant A (0 < A < 1), and the fractional
part of this product is extracted.
• Then, this value is multiplied by m, and the integer part of the result is taken.
This final value is the hash value.
In short, the hash function is: H(M) = floor (m ((M * A) mod 1))), where “(M*A) mod 1”
denotes the fractional part of M * A.
1. Find the digest of M = 33261, with A = 0.578 and m = 100.
2. Which properties of a cryptographic hash function are satisfied or not satisfied by
this function?

Correction

I.
1. 6952 = 483025
H(695) = 30.
2. The function H is a one-way function, it’s preimage resistant, but it does not
respect the collision and second preimage property.
H(32) = H(322) = H(1024) = 02 and H(45) = H(452) = H(2025) = 02 --- Collision.
H(48) = 482 = 2304 = H(695) --- Second preimage.
II.
1. H(33261) = floor (100 * ((33261 * 0.578) mod 1))
H(33261) = floor (100 * ((19 224,858) mod 1))
H(33261) = floor (100 * (0,858))
H(33261) = floor (85.8)
H(33261) = 85
2. The function H is a one-way function, it’s preimage resistant, but it does not
respect the collision and second preimage property
H(12) = 93 and H(512) = 93 --- Collision.
H(34261) = 85 = H(33261) --- Second preimage.

4
Exercise 5: RSA Signature

Bob uses an RSA system to sign messages, with p = 17, q = 7, and d = 5.

1. To authenticate his messages, he must publish his verification key.
• What is the public key of Bob.
2. Bob wants to send the signed message M = 4 to Alice.
• What is the signature of this message?
3. Alice receives the message M = 58 and the signature S = 11.
• Explain how she can verify the integrity of the message.

Correction

1. Finding the public key :

n = p × q = 17 × 7 = 119, ϕ(n) = (p−1)*(q−1) = 16 × 6 = 96,
e × d ≡ 1 mod ϕ(n)
96 = 5 * 19 + 1 …(1)
1 = 96 – 5 * 19
u = -19 mod 96 = 77.
The public key is: (77, 119)
2. Bob uses his private key to sign the message:
S = Md mod n = 45 mod 119 = 72.
3. Alice uses the public key of Bob (77, 119) to verify the signature, then she compares the
result with the received message M:
M′ = Se mod n = 1177 mod 119 = 58 = M.
Exercise 6: ElGamal Signature

Alice uses the ElGamal signature scheme with the following parameters: p=23, g=5, and x=6.
1. To authenticate his messages, Alice must publish her verification key.
• Compute Alice’s public key y.
2. Alice wants to sign the message M = 13, she chooses k=7.
• Verify that k is valid and compute the signature (s1, s2).
3. Bob receives M = 13, s1 = 17, s2 = 3. Verify whether the signature is valid.

Correction
1. y = gx mod p = 56 mod 23 = 8. The public key is (p, g, y) = (23, 5, 8).
2. k is a random number that verify: 𝑘𝑘 ∈ {1, …, 𝑝𝑝−2}, and GCD (k, p-1) = 1.
To sign, we compute s = 𝑔𝑔 mod 𝑝𝑝, and s = k *(M – x * s ) mod 𝑝𝑝-1.
𝑘𝑘 -1
1 2 1
(k * k-1 mod (p - 1) = 1)
s2 = 19 *(13 – 6 * 17) mod 22 = 3
7
s1 = 5 mod 23 = 17 and
The signature is : (s1, s2) = (17, 3).
3. To verify, we compute v1 = gM mod 𝑝𝑝 and v2 = ys1 * s1s2 mod 𝑝𝑝
v1 = 513 mod 23 = 21 and v2 = 817 * 173 mod 23
Since v1 = v2, the signature is verified.