assignment -1

ASSIGNMENT ON DEFFIE-HELLMAN KEY EXCHANGE AND

ELGAMAL PKC

DUE: EMAIL BY 26 FEB 2021

(1) Alice and Bob agree to use the prime p = 1373 and the base g = 2 for a Diffie- Hellman key exchange. Alice sends Bob A = 974. Bob asks your assistance, so you ask him to use the secret exponent b = 871. What value B should Bob send Alice, and what is the secret shared value? What was Alice’s secret key a? You can use Sage to create a table of powers of 2 modulo 1373 and see which power matches 974. >: R=IntegerModRing(1373) >: table(rows=[(x,R(2^x)) for x in [500..600]])

(2) Alice and Bob agree to use the prime p = 1373 and the base g = 2 for communica- tions using the ElGamal public key cryptosystem. (a) Alice choses a = 947 as her private key. What is the value of her public key

A? (b) Bob choses b = 716 as his private key, so his public key is 2716 computed modulo

1373. It is 469. Alice encrypts the message m = 583 using the ephemeral key k = 877. What is the ciphertext (c1, c2) that Alice sends to Bob?

(c) Alice decides to choose a new private key a = 299 with the associated public key 2299 = 34 mod 1373. Bob encrypts a message using Alice’s public key and sends her the ciphertext (c1, c2) = (661, 1325). Decrypt the message.

(3) This exercise describes a public key cryptosystem that requires Bob and Alice to exchange several messages. It is illustrated by 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 = ma mod p = 15950 to Bob. Bob chooses a random exponent b = 4037 and sends v = ub mod p = 15422 back to Alice. Alice then computesw = v15619 = 27257 mod 32611 and sends w = 27257 to Bob. Finally, Bob computes w31883 mod 32611 and recovers the value 11111 of Alice’s message. (a) Explain why this algorithm works. In particular, Alice uses the numbers a =

3589 and 15619 as exponents. How are they related? Similarly, how are Bob’s exponents b = 4037 and 31883 are related? Remember that exponents (the logs) are computed modulo p − 1.

(b) Formulate a general version of this cryptosystem, i.e., using variables, and show that it works in general.

ASSIGNMENT ON DEFFIE-HELLMAN KEY EXCHANGE AND ELGAMAL PKC 2

(c) What is the disadvantage of this cryptosystem over ElGamal? (Hint. How many times must Alice and Bob exchange data?)