You”ve seen how the RSA encryption scheme works, but why is it hard to break? In this probl

You’ve seen how the RSA encryption scheme works, but why is it hard to break? In this problem, you will see that finding secret keys is as hard as finding the prime factorizations of integers. Since there is a general consensus in the crypto community (enough to persuade many large financial institutions, for example) that factoring numbers with a few hundred digits requires astronomical computing resources, we can therefore be sure it will take the same kind of overwhelming effort to find RSA secret keys of a few hundred digits. This means we can be confident the private RSA keys are not somehow revealed by the public keys 9 For this problem, assume that n D p _ q where p; q are both odd primes and that e is the public key and d the secret key of the RSA protocol.. Let x ::= e .d -1.

(a) Show that ∅(n)divides x.

(b) Conclude that 4 divides x.

(c) Show that if gcd.(r; n) = 1, then rx  ≡1 (.mod n): A square root of m modulo n is a nonnegative integer s < n such that s2 ≡m

(.mod n) Here is a nice fact to know: when n is a product of two odd primes, then every number m such that gcd(.m; n) = 1 has 4 square roots modulo n. In particular, the number 1 has four square roots modulo n. The two trivial ones are 1 and n – 1 (which is ≡ -1 (.mod n)). The other two are called the nontrivial square roots of 1.

(d) Since you know x, then for any integer, r, you can also compute the remainder, y, of rx=2 divided by n. So y2 ≡rx .(mod n) Now if r is relatively prime to n, then y will be a square root of 1 modulo n by part (c). Show that if y turns out to be a nontrivial root of 1 modulo n, then you can factor n. Hint: From the fact that y2 -1 = (y C+1) (y -1), show that y + 1 must be divisible by exactly one of q and p.

(e) It turns out that at least half the positive integers r < n that are relatively prime to n will yield y’s in part (d) that are nontrivial roots of 1. Conclude that if, in addition to n and the public key, e, you also knew the secret key d, then you can be sure of being able to factor n.

"Looking for a Similar Assignment? Get Expert Help at an Amazing Discount!"