Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

It is said that the RSA algorithm uses number theory. What parts of number theory does it use?
I know it uses modular arithmetic and Euler's totient theorem and function. Is that all?

share|improve this question
add comment

1 Answer 1

Other than Euler's phi function and modular arithmetic, RSA also make use of Fermat’s Little Theorem (number theory) and depends on the assumption that given the product of two large primes, one cannot factor the product in a reasonable time to solve the RSA problem.

i.e. even if we know e we cannot figure out d unless we know phi(n) which requires factoring n. While there is no proof that factorization is computationally difficult, no efficient solution has been found yet.

share|improve this answer
    
In fact, RSA as practiced (that is, PKCS#1) does not even use Euler's phi function for $d\equiv e^{-1}\pmod {\phi(N)}$; but rather uses the (less frightening) Least Common Multiple: $d\equiv e^{-1}\pmod {\operatorname{LCM}(p-1,q-1)}$, because that's the necessary and sufficient condition for a working $d$ (when all the factors of $N$ are distinct). –  fgrieu Dec 23 '13 at 12:24
1  
@fgrieu: Well, I don't know if the Carmichael function is really all that less-frightening! (At least, not if you approach the problem from a theory-heavy point of view instead of just ignoring the whole issue...) –  Reid Dec 23 '13 at 16:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.