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]