Final 609.051

Out: Mon, Dec 6, 2004
Due:

Problems 1 through 4: from chapter 4 of the textbook,

Problem 5
Problem 6
Problem 7
Problem 11

Problem 5: About Proof of Knowledge.
We have the interactive proof of knowledge of x such that y = g^x mod p, where g generates the subgroup of order q, q|(p-1), p and q are primes. The proof is a triple (a,c,b) where

Prover chooses a random element r for the integer mod q, calculates a=g^r mod p, and sends a to the Verifier.
After receiving a, Verifier chooses a challenge c, a random element of integer mod q, and sends it to the Prover.
Prover responds with b, calculated as b = r-cx mod q.
Verifier checks that a = g^by^c and if so, accepts. Else it rejects.

If there are found to be two transcripts where the commitment a is repeated, but the challenges differ, (a,b,c) and (a,b'c'), b ≠ b', c ≠ c', it is possible to discover the prover's secret x,

Here are several transcripts of this protocol, including the parameters p, g, and the public value y. But two of the transcripts begin with the same a. Find the secret x.

You might be interested in the program which produced these transcripts. Man bn (the BIGNUM package of openssl) for more information, if you are on a free unix, linux, freebsd or Mac OS X.

Problem 6: About Quadratic Residues in Integers mod n=pq.
If p and q are distinct primes, then y has a square root mod n=pq only if y has a square root individually mod p and mod q. If y has a square root mod n, then it has four, corresponding to the mixing of the two square roots of y mod p and mod q. Using chinese remainder, or the alternative method described below, the square roots of y mod p and mod q can be lifted to a square root mod n.

A cryptosystem can be defined:

To send a zero, send a quadratic residue. That is, a number y which is the square of some other number, mod n.
To send a one, send a non residue. That is, a number y which is not equal to the square of any other number, mod n.

In addition, we require that the non residue be a non residue both mod p and mod q. Without this, we can detect some non residues without factoring n. Else it is believed that we need to factor n.

Here are your assignments:

Look at the transcript of the program quad_res.c
Determine the eight bits encoded by the program
To break the system, try to factor n. You can try Pollard's Rho method.
The bits are the password to the secret page, username solution. Example, if the bits are 0 1 0 1 0 1 0 1, then the password would be 01010101.

Good luck all!

I hope you find the course useful to your future endeavors.

Burton Rosenberg
Last update: Wed Dec 8 13:16:12 EST 2004