Lab Assignment 5


1. El Gamal, p = 37, secret message x = 7
	a). Find generator alphi
	b). Find public key
	c). Compute the encrypted message
	d). Perform the decryption

2. Determine gcd(24140,16762)

3. What is the multiplicative inverse of 550 in the field of integers mod 1769?

4. Using Fermat's theorem, find 3^201 mod 13. 

5. Conside a Diffie-Hellman scheme with a common prime q=11 and a primitive root alphi = 2.
	a). if user A has public key Y_a = 9, what's A's private key X_a ?
	b). if user B has public key Y_b = 3, what's B's private key X_b ?   

6. You have just received an offer to join a startup that is in the network security business. They have a patent on an authentication mechanism that works as follows.

Two people (Alice and Bob) want to verify that each has a key X of length b bits.  Alice selects  a random binary string S of length b, computes S' = (S xor X), and sends S' to Bob.  Bob, who has key X', now computes S'' = (S' xor X') and sends S'' to Alice.

To verify if Bob's key X' is the same as her key X, Alice can now simply check if S'' is identical to S.  Neither Alice nor Bob have sent their key over the connection, and the method is very fast.

Would you take up the offer?  Explain in as much detail as possible.