RSA: Recall the definition of RSA: n = pq where p, q are large primes and encryp
ID: 3662795 • Letter: R
Question
RSA: Recall the definition of RSA: n = pq where p, q are large primes and encryption is M^e (mod n), decryption, (M^e)^d (mod n) where ed = 1 (mod pi(n)). Now pi(2) = 1; pi(3) = 2, pi(4) = 2, pi(5) = 4. Do some more calulations of pi, and then answer the following questions. What is 0(n) if n is a prime? Prove your answer (a one-line proof will suffice). What is pi(n) if n is the product of two primes? What is the difficulty, in big O notation, of calculating the decryption exponent d if you know the factorization of n? Explain your answer in terms of the size of the input (that is, the length of n). What is the difficulty of calculating the decryption exponent d if you don't know the factorization of n?Explanation / Answer
You can "break" RSA by knowing how to factor "n" into its "p" and "q" prime factors:
n = p * q
The easiest way is probably to check all odd numbers starting just below the square root of n:
Product of two primes
In addition to needing p and q to be coprime’s, we also want
p and q to be individually primes. It is only when p and q are individually prime that we can decompose the totient of n into the product of the totients of p and q. That is
(n) = (p) × (q) = (p 1) × (q 1)
if you know factorization then we can write
That is if you know the factors p and q, you can calculate (n) by multiplying p 1 with
q 1. And if you know (n) and n, you can calculate the factors p and q readily.
So if you dont know factorization is (not then) we can write and we face some difficulties like
Integer Factorization problem:
Input : An odd composite number n.
Output: A prime p that satisfies p|N
N can be factored if we calculate the private key e successfully.
That means we successfully solve the factorization problem. But here broke the application RSA Algorithm.
For example we take the product of 2 complex prime numbers.
The prime numbers randomly choosen about the same size.
using exp((64/9b)1/3(logb)2/3.
We can solve above problem using above exp.
So that the cipher cannot be broken by an exhaustive search for the prime factors of the modulus n, it is important that both p and q be very large primes.
what is big o notation ,of calculating decryption exponent d if you know the factorization of n
It gets a bit more interesting when we look at algorithms with a varying input size. For the asymmetric algorithm RSA, we have the public (and private) key modulus nn, and its size k=[log2n]k=[log2n] in bits can be considered a security parameter.
The message size is then limited by O(k)O(k), too.
Encryption and decryption are both modular exponentiations of plaintext or ciphertext modulo nn, with the respective exponents.
With the square-and-multiply algorithm, encryption needs O(1)O(1), decryption O(k)O(k) multiplications and a similar number of modular reductions, each of kk-bit or 2k2k-bit numbers .
Decryption can be sped up by storing the factors of nn, but this still gives only a constant factor, I think (i.e. it reduces the kk in the formulas)..RSA also uses one of various padding schemes, but this should be in O(k) and thus not contribute to the complexity.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.