a) Using the formal assumptions from the lecture and the reduction technique, prove that factoring is at least as hard as breaking the RSA assumption. b) Consider the following (informal) assumption of hardness of computing the function.: It is hard to compute (N) for N being the product of two large primes. i. Formally define the above hardness assumption. ii. Prove that if N = pq where p and q are primes, then (N) = (p 1)(q 1). iii. Prove, using the reduction technique, that factoring is at least as hard as computing (i.e., breaking the assumption of hardness of computing the function).

Hardness Assumptions and the RSA a) Using the formal assumptions from the lecture and the reduction technique, prove that factoring is at least as hard as breaking the RSA assumption b) Consider the following (informal) assumption of hardness of computing the function It is hard to compute o(N) for N being the product of two large primes i. Formally define the above hardness assumption. ii. Prove that if N = pq where p and q are primes, then (N) = (p-1)(q-1). iii. Prove, using the reduction technique, that factoring is at least as hard as comput ing (i.e., breaking the assumption of hardness of computing the function)