1. Try out the smoothness bounds

L = 2.3 = 6, L^2 = 36 and so on...

Let a = 2.

gcd(a^L-1, N) = gcd(2^6-1, 1739) = gcd(63, 1739) = 1.

gcd(a^{L^2}-1,N) = gcd(2^36-1, 1739) = gcd(2^36-1 mod 1739, 1739) = gcd(1517, 1739) = gcd(222, 1739) = 37.

Thus, 37 divides N, and N can be written as N = 37 * 47 (which is its prime factorization.)

[10 points for the idea + correct execution ]


2. a. x = 1, 3, 9.

[3 marks]

2. b. Let x = g^k. Then, we want solutions to g^3k = 1 mod p. 
It must be that 3k is a multiple of p-1 since g is a generator of the group. 
Thus, the three distinct solutions are 1, g^{(p-1)/3} and g^{2(p-1)/3}.

[ 7 marks]

2. c. The equations x^3 = 1 mod p and x^3 = 1 mod q have three solutions each. 
By Chinese remaindering each pair of solutions to the mod p and mod q equations gives 
us a distinct solution to x^3 = 1 mod N.

Thus, we have 9 solutions.

[3 marks]

2. d. Let x^3 = 1 mod N, and thus x^3 - 1 = 0 mod N.

Factoring the left hand side, we get (x-1)(x^2 + x + 1) = 0 mod N.
Thus, N | (x-1)(x^2 + x + 1).
From (a), we know that N does not divide x - 1.
From (b), we know that N does not divide x^2 + x + 1.

It must be that p divides x-1 and q divides x^2+x+1, or the other way round. 
In either case compute gcd(x - 1, N) which gives us the answer.

[7 marks]

3. I'll give the solution for Schnorr signatures. The idea for El Gamal signatures is essentially identical.

Suppose Samantha releases two signatures with \sigma_1 = \sigma_1' = g^a, \sigma_2 = a + cx mod p-1 
and \sigma_2' = a + c'x mod p-1 where c = H(M) and c' = H(M').

Given these two signatures, an adversary can now compute the secret key x as

x = (\sigma_2' - \sigma_2) * (c'-c)^{-1}  mod p-1 if the inverse of c-c' exists.

[20 marks for the key idea]