1.   (a)

N = pq = 81789928785559159904680017620411554867681054256709142260101 e = 65537

m = 72059565158564519660691228300707183180614473561724520542850

Find the secret message (Hint:  A _→ 11, B _→ 12, C _→ 13, . . . , Z _→ 36) .

Please just write the secret message, there is no need to show any work. You can use any tool/website for the computations. The secret message should be an easy question.

(b) Encode the answer of the question found in the previous part using the same technique. Please just write the encoded message, there is no need to show any work again.

2. Alice wants to use RSA to receive secret messages from other people. She publishes her public modulus N = pq on her website together with two encryption keys e1  and e2  and she tells people that  “Please use only one of the encryption keys e1  and e2  to send your secret messages .  It is not very safe to use both of the keys to  encode the same message” .

Bob doesn’t pay too much attention to Alice’s warning and he thinks  “if a third party cannot recover x modulo N from  the  message  encoded  by e1  and from  the  message  encoded  by e2 ,  then  they still  cannot recover x from  the  two  messages  encoded  by e1   and e2” .  So, he computes xe1   and xe2   modulo N and

sends them to Alice.

Prove that Bob was wrong is his thinking if gcd(e1 , e2 ) = 1. In other words, please explain that a third party can recover x  (mod N)  “easily” if they capture both xe1   and xe2    (mod N) when gcd(e1 , e2 ) = 1.

3. An amateur cryptographer Charles thinks that he found a novel alternative to RSA to start receiving secure messages from other people. Here is how it works:

❼ Charles picks two very large distinct primes p and q, and compute the public modulus N = pq just like in RSA. He also picks random integers g, r1 , and r2  and computes g1  = gr1 (p一1)   (mod N) and g2 = gr2 (q 一1)   (mod N).  (Assume g and N are relatively prime) .

❼ Charles publishes N, g1 , and g2  on his website while the numbers p, q, g, r1 , r2  are not known to

anyone other than himself.

❼ Say David wants to send his secret message x to Charles securely. He picks two random integers s1 and s2  and computes m1 = x . g 1(s)1    (mod N) and m2 = x . g2(s)2    (mod N). David sends m1  and m2  to

Charles.

❼ To decode the received message, Charles uses Chinese Remainder Theorem and find and x\  (mod N)

such that x\ = m1   (mod p) and x\ = m2   (mod q). (Convince yourselves that this is computationally “easy”).

(a)  Prove that Charles decodes the message correctly.

(b) In a secure cryptosystem, it should be difficult for a third party to recover the secret message from the encoded messages. Show that this cryptosystem is unfortunately not secure Hint:  If we know p and q, then we can use  Charles’ technique for encoding.  Try attacking p and q instead of attacking the secret message first.

4.   (a) For an odd prime p, show that

,-1

╱ 、  =．-_1

(0

if p = 1, 7, 9, 11, 15, 17, 19, 25, 29, 31, 47, 49    (mod 52)  if p = 3, 5, 21, 23, 27, 33, 35, 37, 41, 43, 45, 51    (mod 52) if p = 13