11) Suppose you are using RSA (with modulus n = p q and encrypting exponent e),...

 

Transcribed Image Text:

11) Suppose you are using RSA (with modulus n = p q and encrypting exponent e), but you decide to restrict your message to number m satisfying m1000 = 1 mod n a. Show that if d satisfies de = 1 mod 1000, then d works as a decryption exponent for these messages b. Assume that both p and q are congruent to 1 mod 1000. Determine how many messages satisfy m1000 = 1 mod. You may assume and use the fact that 1000 = 1 mod r has 1000 solutions when r is a prime congruent to 1 mod 1000 with m 11) Suppose you are using RSA (with modulus n = p q and encrypting exponent e), but you decide to restrict your message to number m satisfying m1000 = 1 mod n a. Show that if d satisfies de = 1 mod 1000, then d works as a decryption exponent for these messages b. Assume that both p and q are congruent to 1 mod 1000. Determine how many messages satisfy m1000 = 1 mod. You may assume and use the fact that 1000 = 1 mod r has 1000 solutions when r is a prime congruent to 1 mod 1000 with m