Exercise III

Remarks:Always explain (or prove if necessary) the correctness of your analysis or claims.

Question 1:Say that the cyphertext obtained from te RSA is 5859. Say that n= 11413 and note that n= 11413 = 101 113. Let e= 7467. Find the plaintext.

Question 2:Why the epublished in the RSA can not be 1 and can not be 14?

Question 3:Say that two users use n₁,n₂in the RSA and gcd(n₁,n₂) 6= 1. How can we break their system?

Question 4:In this question we show that we can use (n)/2. Let n= pq. Let xbe a number so that gcd(x,n) = 1.

1. show that x^(n)/2 = 1 mod pand x^(n)/2= 1 mod q
2. Show that this implies that and x^(n)/2= 1 mod n3. Show that if e d= 1 mod (n)/2 then x^ed= 1 mod n.

4. How can we use (n)/2 in the RSA?

Question 5:Say that x² = y²mod n, but x6= y mod nand x6= y mod n.

1. Let d= gcd(x y,n), Show that d6= n.
2. Show that 1 = gcd(x y,n) implies that ndivides x+ y, and that this is not possible.
3. Show that we found a non trivial factor of n