Protocols Assignment: Simplified Feige-Fiat-Shamir, Diffie-Hellman

This assignment solution addresses key concepts in Information Security Management, specifically focusing on protocols. It includes a detailed explanation of the Simplified Feige-Fiat-Shamir accreditation scheme, outlining the steps involved in the exchange of a secret between a Prover and a Verifier, including the use of RSA modulus. The solution also traces values with parameters n=15, illustrating the public and private keys and the verification process. Furthermore, the assignment covers the Diffie-Hellman protocol for three parties, explaining the steps of key exchange using discrete logarithms, from the initial agreement on prime numbers and generators to the final computation of the secret key. The solution covers the core concepts of protocols in information security, making it a useful resource for students.

information security
managEment

Table of Contents
3. Simplified Feige-Fiat-Shamir Accreditation Scheme..............................................................1
4. Tracing of values with parameters n = 15, r = 11....................................................................1
5. Diffie – Hellman protocol for three parties Alice, Bob and Carol..........................................2

3. Simplified Feige-Fiat-Shamir Accreditation Scheme
The accreditation scheme works for the exchange of the secret ‘s’, between Peggy and Victor
making them Prover and Verifier with an RSA modulus n=pq, where p and q are prime
numbers, and are kept hidden. The resultant n and a chosen parameter a, both belongs to the set
of natural numbers.
Now according to the accreditation scheme, following steps are executed –
- Peggy picks a random number r, less than n
- The computation of x takes place, such that x = r2 (mod n)
- Peggy sends x to Victor, the verifier
- Now, Victor send to Peggy a random bit b
- The answer sent by Peggy to Victor becomes
• r if the bit b is 0
• y, another parameter, as y= r * s (mod n) if the bit b is 1
- At the verification end, according to the bit value, Victor verifies
• x = r2 mod n if b is 0 -> Peggy knows √x
• x = y2 * v (mod n) -> Peggy knows √v-1
- The accreditation by Victor is accepted if the verification is successful
4. Tracing of values with parameters n = 15, r = 11
Given n = 15, the possible prime numbers p = 3 and q = 5 makes n = 15
Public and Private Keys
v (public key) equations square roots
1 x2 = 1 mod 15 1, 4, 11, 14
4 x2 = 4 mod 15 2, 7, 8, 13
v v-1 √v-1 (private key)
1 1 1
4 4 2
Now Peggy chooses r = 11 and sends x to Victor as
Page 1 of 6
Information Security Management

x = r2 (mod n)
x= (11)2 (mod 15)
x = 1 (mod 15)
x = 1
Victor sends Peggy, the bit b as either 0 or 1
Based on b, the answer becomes
Bit Value to be sent Answer
0 r 11
1 y = r × s mod n y = 11 * (2 (mod 15))
y = 22
At the verification end,
Bit Value to be verified Value
0 x = r2 mod n 1
1 x = y2 × v mod n y = 222 * (4 (mod 15))
y = 484 * 4 mod 15
y = 1936 mod 15
y = 1
Thus, Victor accepts the accreditation.
5. Diffie – Hellman protocol for three parties Alice, Bob and Carol
The protocol based on three parties Alice, Bob and Carol can be described using the discrete
logarithms as below –
Step 0: Alice, Bob and Carol agree on a large prime number n and an integer g, such that g is a
generator mod n.
Step 1: Alice, Bob and Carol choose their large random integers x, y and z respectively.
Step 2: The sharing (round 1)
- Alice send to Bob: X = gx mod n
- Bob sends to Carol: Y = gy mod n
- Carol sends to Alice: Z = gz mod n
Step 3: The sharing (round 2)
- Alice send to Bob: Y` = = gxy mod n
- Bob sends to Carol: Z` = Zy mod n = gyz mod n
- Carol sends to Alice: X` = Xz mod n = gzx mod n
Step 3: The computation
Page 2 of 6
Information Security Management

- Alice computes: kx = X`x mod n = gyzx mod n
- Bob computes: ky = Y`y mod n = gzxy mod n
- Carol computes: kz = Z`z mod n = gxyz mod n
Step 4: kx = ky = kz is used as the secret key
Page 3 of 6
Information Security Management