CS547A Homework set #5

Due Tuesday December, 5 2000 in class at 14:30 SHARP

Exercises (from Stinson’s book)

• 7.4 •

Suppose n=pq, where p and q are two (secret) distinct large primes such that p=2p1+1 and q=2q1+1, where p1 and q1 are prime. Suppose that a is an element of order 2p1q1 in Zn* (this is the largest order of any element in Zn*). Define a hash function h : {1,2,…,n2} -> Zn* by the rule h(x) = ax mod n.

Now, suppose that n = 603241 and a = 11 are used to define a hash function h of this type. Suppose that we are given three collisions for h:

h(1294755) = h(80115359) = h(52738737).

Use this information to factor n.

• 7.5 •

Suppose h1 : {0,1}2m ->{0,1}m is a strongly collision-free hash function.

(a) Define h2 : {0,1}4m ->{0,1}m as in Figure 7.13. Prove that h2 is strongly collision-free.

(b) For an integer i>1, define a hash function hi : {0,1}^2im ->{0,1}m recursively from hi-1, as indicated in Figure 7.14. Prove that hi is strongly collision-free.

FIGURE 7.13 Hashing 4m bits to m bits

  1. write x in {0,1}4m as x = x1||x2, where x1,x2 in {0,1}2m
  2. define h2(x) = h1(h1(x1) || h1(x2)) .

 

FIGURE 7.14 Hashing 2im bits to m bits

  1. write x in {0,1}^2im as x = x1||x2, where x1,x2 in {0,1}^2i-1m
  2. define hi(x) = h1(hi-1(x1) || hi-1 (x2)) .

• 9.3 •

Suppose that Alice uses the Schnorr Scheme with p=122503, q=1201, t=10 and a=11538 (as in Exercise 9.2). Now suppose that v = 51131, and Olga has learned that

a 3v148 = a 158v1077 (mod p).

Show how Olga can compute Alice’s secret exponent a.

 

 

• 9.7 •

Suppose that Alice is using the Guillou-Quisquater Scheme with n = 199543, b=523 and v = 146152. Suppose that Olga has discovered that

v456101360b = v25736056 b (mod n).

Show how Olga can compute u.

 

Other Exercises

Goldwasser-Micali

Let n=p*q, the product of two primes, and let y be an element of QNRn[+1]. Remember that the Goldwasser-Micali cryptosystem with public parameters (n,y) encrypts a zero bit by [a random quadratic residue] modulo n and a one bit by [a random quadratic residue] x y modulo n.

Let GM(m1),GM(m2) be the Goldwasser-Micali encryption of messages m1 and m2 as computed and sent by Bob to Alice. Suppose Bob applied his personal signature to the encryption of each bit.

Imagine the government witnessed Bob's transmission of both messages to Alice and they wish to have some minor information about the messages as follows.

  1. Show how Bob can prove that both GM(m1),GM(m2) were encryptions of the same message m1=m2 without disclosing anything at all about it.

  2. Show how Bob can prove that GM(m1),GM(m2) were encryptions of messages m1 and m2 that differed in an even or odd number of positions, without disclosing anything else about them.

  3. Assume m1,m2 have even length, |m1|=|m2|=2k. Show how Bob can prove that GM(m1),GM(m2) were encryptions of different messages m1<>m2 by disclosing nothing except for the fact that they differed somewhere among all but one of the positions. (Bob can but aside one encrypted bit at a fixed position of GM(m1) and GM(m2), and then prove that the remaining truncated messages are different without disclosing anything about them except for the fact that they differ). Explain why we need messages of even length 2k.

  4. How much uncertainty is left about m1,m2 when only learning that they differ ? How much uncertainty is left about m1,m2 when learning that they differ by the method suggested in (c) ?

(in both cases assume that the a priori uncertainty was maximum.)