Question

Public-Key Encryption Scheme based on Discrete Log [16 Marks]

This question describes a public key cryptosystem that requires Bob and Alice to exchange several messages. We illustrate the system with an example.
Bob and Alice fix a publicly known prime p=32611 and all of the other numbers used are private. Alice takes her message m=11111 chooses a random exponent a=3589, and sends the number u=mᵃ mod p=15950 to Bob. Bob chooses a random exponent b=4037 and sends v=uᵇ mod p=15422 back to Alice. Alice then computes w=v¹⁵⁶¹⁹=27257mod32611 and sends w=27257 to Bob. Finally, Bob computes w³¹⁸⁸³ (mod32611) and recovers the value 11111 of Alice's message.
(a) Explain why this algorithm works. In particular, Alice uses the numbers 3589 and 15619 as exponents. How are they related with respect to the public prime p ? Similarly, how are Bob's exponents 4037 and 31883 related with respect to the public prime p ?
(b) Formulate a general version of this cryptosystem, i.e., using variables, and show that it works (satisfies correctness) in general.
(c) What is the disadvantage of this cryptosystem over the El Gamal encryption scheme?
(d) Are there any advantages of this cryptosystem over the El Gamal encryption scheme? In particular, can Eve break it if she can solve the Discrete Logarithm problem? Can Eve break it if she can solve the DiffieHellman problem?

Answer 1

This public-key encryption scheme is based on the discrete logarithm. Alice and Bob exchange messages to encrypt and decrypt a message using random exponents and a publicly known prime.

Step-by-step explanation:

In this public-key encryption scheme based on discrete log, Bob and Alice exchange messages to encrypt and decrypt a message.

Alice chooses a random exponent a and computes u = m^a mod p, where m is the message and p is the publicly known prime.

Bob chooses a random exponent b and computes v = u^b mod p.

Alice then computes w = v^a mod p and sends it to Bob.

Finally, Bob computes w^(p-1-b) mod p and recovers Alice's original message.

The exponents chosen by Alice and Bob are related to the public prime p: a and 15619 are congruent modulo (p-1), which means a is a solution to the congruence a ≡ 15619 (mod p-1). Similarly, b and 31883 are congruent modulo (p-1) as b ≡ 31883 (mod p-1).

The disadvantage of this cryptosystem over the El Gamal encryption scheme is that it is vulnerable to attacks such as the Baby-step Giant-step algorithm and the Pollard's rho algorithm, which can solve the discrete logarithm problem efficiently.

An advantage of this cryptosystem is that it provides a way to perform public-key encryption using the discrete logarithm problem and can be used for secure communication if the discrete logarithm problem is hard to solve.