2.4 RSA Encryption

The feasibility and security of the RSA public-key encryption system using keys based on 300-digit primes \(p, q\) depends on the fact that certain computations listed below are "easy" and certain others are "hard."

1. Which of the following computations have to be "easy" in order for RSA to be feasible using keys based on 300 digit primes \(p,q\)?
   Note that there are some easy computations in this list that are not relevant to RSA.

   Exercise 1

    testing if a 300-digit number is prime 

    finding \(q\) given \(p\) and the product \(n ::= pq\) 

    finding \(n ::= pq\) given \(p,q\) 

    finding 300-digit primes \(p,q\) given \(n ::= pq\) 

    finding \(\Phi(pq)\) given \(p,q\) 

    generating 300 random digits 

    finding a 300-digit prime number 

    factoring a 600-digit number 

    testing whether a 300-digit number is relatively prime to a given 600-digit number 

    finding a 300-digit number that is relatively prime to a given 300-digit number 

    finding an inverse (if there is one) modulo a 600-digit number of a 300-digit number 

    raising a 600-digit number to a 600-digit power 

    finding the remainder on division by a 600 digit number \(n\) of a 600 digit number raised to a 600 digit power 

   2: EASY but IRRELEVANT
   4,8: HARD
   12: 36000-digit arithmetic is feasible, say using Mathematica, but IRRELEVANT
2. Which of the following computations have to be "hard" in order for RSA to be secure using keys based on 300-digit primes \(p,q\)?
   Note that there are some hard computations in this list that are not relevant to RSA.
   Exercise 2

    testing if a 300-digit number is prime 

    finding \(q\) given \(p\) and the product \(n ::= pq\) 

    finding \(n ::= pq\) given \(p,q\) 

    finding 300-digit primes \(p,q\) given \(n ::= pq\) 

    finding \(\Phi(pq)\) given \(p,q\) 

    generating 300 random digits 

    finding a 300-digit prime number 

    factoring a 600-digit number 

    testing whether a 300-digit number is relatively prime to a given 600-digit number 

    finding a 300-digit number that is relatively prime to a given 300-digit number 

    finding an inverse (if there is one) modulo a 600-digit number of a 300-digit number 

    raising a 600-digit number to a 600-digit power 

    finding the remainder on division by a 600-digit number \(n\) of a 600-digit number raised to a 600-digit power 

   See above explanation.
   CheckShow Answer