Mylene Cover

CS 472 - Fall 2005
Dr. Wahab

Assignment # 4
===========

Q1
---
Assume a cipher message C = 198273465 is the result of encrypting a message M with K = 3, assuming each digit was encrypted individually.  What is the value of the message M if the message was encrypted using:

A.  Mod 11 Addition

C = 198273465
K = 3
M = ?

The additive inverse of the key K = 3 is 8.  8 + 3 = 11.  11 mod 11 = 0.
We then add the inverse to each digit of the cipher to get the original message M.

(1+8)mod 11 = 9, (9+8)mod 11 = 6, (8+8)mod 11 = 5, (2+8)mod 11 = 10, (7+8)mod 11 = 4, (3+8)mod 11 = 0, (4+8)mod 11 = 1, (6+8)mod 11 = 3, (5+8)mod 11 = 2

-----------------------------
| M = 9 6 5 10 4 0 1 3 2 |
-----------------------------

B.  Mod 11 Multiplication

C = 198273465
K = 3
M = ?

The multiplicative inverse of key K = 3 is 4.  4 * 3 = 12.  12 mod 11 = 1.
We then multiply every digit of the cipher by 4 to get M.

(1*4)mod 11 = 4, (9*4)mod 11 = 3, (8*4)mod 11 = 10, (2*4)mod 11 = 8, (7*4)mod 11 = 6, (3*4)mod 11 = 1, (4*4)mod 11 = 5, (6*4)mod 11 = 2, (5*4)mod 11 = 9

-----------------------------
| M = 4 3 10 8 6 1 5 2 9 |
-----------------------------

C. Mod 11 Exponentiation

C = 198273465
K = 3
M = ?

Phi(n) = n -1 since n is prime.  So Phi(11) = 10
The exponentiative inverse is 7.  (3*7)mod phi = 21 mod 10 = 1.

We do modular exponentiation mod 11 on each of the digits of the cipher C to get M.

(1^7)mod 11 = 1, (9^7)mod 11 = 4, (8^7)mod 11 = 2, (2^7)mod 11 =7, (7^7)mod 11 = 6, (3^7)mo
----------------------------
| M = 1 4 2 7 6 9 5 8 3 |
----------------------------

Q2
----
Assume a cipher message C = 123 is the result of encrypting a message M using the public key e = <5, 133>.

A.  Verify that d = <65, 133> is the corresponding private key of e.

We know:
e = 5
n = 133
p = ?
q = ?
p and q are prime numbers that are factors of 133, by guessing and checking, I got:
p = 19
q = 7
Phi(133) = (p-1)(q-1) = (19-1)(7-1) = 18*6 = 108

If we know a public key e and need to find d, we find the number that is the multiplicative inverse of e mod phi(n).

So we find the number d such that:
5*d = 1 mod 108

5* 65 = 325.  325 mod 108 = 1. 

Therefore d = <65,133> is the corresponding private key of e.  


B.  Use the efficient exponentiation scheme described in RSA to compute M.  

M = (123)^65 mod 133 = (123)^1000001 mod 133 =  (((((((123^2)^2)^2)^2)^2)123)^2 mod 133 = 100
---------
| M = 100 |
---------

Q3
----
Assume that A and B, and C are using Diffie-Hellman with p = 19 and g = 7.  
Let Sa = 16 and Sb = 14 and Sc = 11.

In order to avoid the man-in-the-middle attach, they deposit their public values Pa, Pb, and Pc with a trusted authority (TA).  

1.  Compute the public values Pa, Pb, and Pc.

Pa = (g^Sa) mod p
Pa = (7^16) mod 19 = 7

Pb = (g^Sb) mod p 
Pb = (7^14) mod 19 = 11

Pc = (g^Sc) mod p
Pc = (7^11) mod 19 = 11

2.  Compute the shared secret between based on the values deposited with the TA.

- A and B

X = Ta^Sb mod p
X = 7^14 mod 19 = 11

Y = Tb^Sa mod p
Y = 11^16 mod 19 = 11

-------------------
| X = 11, Y = 11, X=Y |
-------------------

- B and C

X = Tb^Sc mod p
X = 11^11 mod 19 = 7

Y = Tc^Sb mod p
Y = 11^14 mod 19 = 7

------------------
| X = 7, Y = 7, X=Y |
------------------

- C and A

X = Tc^Sa mod p
X = 11^16mod 19 = 11

Y = Ta^Sc mod p
Y = 7^11 mod 19 = 11

--------------------
| X = 11, Y = 11, X = Y |
--------------------

- end of assignment 4 :)