CS772

Assignment #4

Due Midnight, Thursday Nov. 15, 2012

 

Q1:

 

1.  Choose two-digits  distinct primes p and q 
2.  Compute n = p.q & Ø(n) = (p-1)(q-1).
3.  Choose a number e that is relatively prime to Ø(n).

4.  Find a number d that is the exponentiative inverse of e
     i.e., e.d = 1 mod Ø(n).

5.  Choose a three-digits number m < n and use the public key  <e,n>  &  the private key  <d,n> to

ü   encrypt/decrypt  m

ü   sign/verify m

 

 


v Dr. Wahab’s Solution:   You must choose different values for p, q, e and m

 

 

p = 83, q=73

n = 6059

 Ø(n) = 82 * 72 = 5904

e = 5

 

 

e=5,   Ø(n) = 5904

 

i

qi

ri

 ui

vi

-2

 

5

1

0

-1

 

5904

0

1

0

0

5

1

0

1

1180

4

-1180

1

2

1

1

1181

-1

 

 

Since    r2   is  1 then e-1 is 1181

Thus d=1181.

e.d mod Ø(n) = 5 x 1181 mod 5904 = 1

 

m = 222

encrypt/decrypt:

c =  enc (m) = me mod n =  222 5  mod 6059 = 1046

m = dec (c) = c d mod n = 1046 1181 mod 6059 = 222

 

sign/verify:

s = dec (m) = md mod n =  222 1181  mod 6059 = 4185

v = enc (s) = se mod n =  4185 5  mod 6059 = 222

 

 


Q2: 

Assume that Alice and Bob, and Cidney are using Diffie-Hellman with  p=83 and g = 73.

Let  SA = 11 and SB = 22, and SC = 33. 

In order to avoid the man-in-the-middle attack, they deposit their public values

PA , PB  and PC with a trusted authority.

·       Compute the public values:

·       PA

·       PB 

·       PC 

·       Compute the shared secret between each pair of these three individuals:

·       AB , BA

·       AC , CA

·       BC , CB

 


Q3: 

  The Graph isomorphism problem is an example of Zero Knowledge Proof Systems.

  The following is Alice’s  public key graphs. 

  Find Alice’s private key (the mapping between the two graphs).

 

 

1

1

 

1

 

 1

 

 

 

1

1

1

 

 

1

 

1

 

 

1

 

1

 

1

1

 

1

 

1

 

1

1

 

1

 

 

 

 

 

 

1

1

 

 

1

 

1

1

 

1

 

1

 

1

 

 

1

 

1

1

1

1

 

1

 

 

1

1

1

1

 

 

 

Q4: 

Show the multiplication table of Z15*