--------- MIDTERM --------------

CSC609. 
Out: Oct 15
Due: Oct 25


(1)
In this problem you are asked to factor the number 2993 whic
is the product of two primes p and q, using a guess at phi(2993) 
and solving for p and q using the quadratic formula.

The guess at phi(2993) is given by the fact that you are
told that the RSA
encryption exponent is 11 and the decryption exponent is 1571.

Hint:
Since 11*1571 is 1 modulo phi(n), then we can try small
values of k and suppose that k * phi(n) = (11*1571-1).



(2)
In this problem you are asked to factor the number
83659 by finding x such that x*x = 1 modulo 83659.

It is given that x to the power 581560 always gives
1 modulo 83659 (we know this because we know both the RSA
encryption and decrption exponents). 

Select 10 numbers at random, and raise
them to the 581560 power according to the method 
in class. If this reveals a non-trivial square root of 
one, use this information to factor 83659. 

How many of the random numbers worked to factor n? 
Categorize the non-working random numbers by the reason
that they did not find a non-trivial square root of one.



(3)
The modulus is 19207163. The encryption exponent is 4783.
The message is:

0 7157254 7746594 6915190 3571767 
12170796 7746594 3571767 12057260 10801492 
5377196 0 10801492 5377196 3571767 
0 47694 3571767 7746594 13204635 
5377196 0 939850 7157254 10801492 
219273 11236489 6915190 3571767 0 
10801492 5377196 3571767 0 13204635 
12017414 12057260 219273 219273 12170796 
939850 939850 18993027 0 

Decrypt this message. First find the decryption exponent
then decrypt the message using RSA.
Then, for extra credit, turn the resulting numbers into
the cleartext message.

Note that you don't actually need to
RSA decrypt to get the real cleartext message, 
you can break the message working directly with
the ciphertext.


-----END------------