6.7 Suppose that n = pq is an RSA modulus (i.e., p and q are distinct...

 

Transcribed Image Text:

6.7 Suppose that n = pq is an RSA modulus (i.e., p and q are distinct odd primes), and let a Zn*. For a positive integer m and for any a Zm*, define ordm (a) to be the order of a in the group Zam". (a) Prove that ordn (a) = lcm(ordp(a), ord(a)). (b) Suppose that gcd(p 1, q 1) : - - = d. Show that there exists an element a Zn such that ord (a) = = o (n). d ) Suppose that gcd (p-1, q- 1) =2, and we have an oracle that solves the Discrete Logarithm problem in the subgroup (a), where a Zn* has order (n)/2. That is, given any E (a), the oracle will find the discrete logarithm a = log , where 0 < a < (n)/2 - 1. (The value o(n)/2 is secret however.) Suppose we compute the value = a" mod n and then we use the oracle to find a = log B. Assuming that p > 3 and q > 3, prove that n a= = O(n). (d) Describe how n can easily be factored, given the discrete logarithm a = log from (c). 6.7 Suppose that n = pq is an RSA modulus (i.e., p and q are distinct odd primes), and let a Zn*. For a positive integer m and for any a Zm*, define ordm (a) to be the order of a in the group Zam". (a) Prove that ordn (a) = lcm(ordp(a), ord(a)). (b) Suppose that gcd(p 1, q 1) : - - = d. Show that there exists an element a Zn such that ord (a) = = o (n). d ) Suppose that gcd (p-1, q- 1) =2, and we have an oracle that solves the Discrete Logarithm problem in the subgroup (a), where a Zn* has order (n)/2. That is, given any E (a), the oracle will find the discrete logarithm a = log , where 0 < a < (n)/2 - 1. (The value o(n)/2 is secret however.) Suppose we compute the value = a" mod n and then we use the oracle to find a = log B. Assuming that p > 3 and q > 3, prove that n a= = O(n). (d) Describe how n can easily be factored, given the discrete logarithm a = log from (c).