Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Probably duplicate of Why are very large prime numbers important in cryptography?

But my question is,what if we start with two small prime numbers say $p = 3$, $q = 5$ and $n = pq = 15$, $\phi(n) = 8$, and $1 < e < 8$.

Should we able to calculate RSA for this? How secure it will be ?

share|improve this question
By simple trial and error, one might try the first 10000 primes for an easy attack. In this case, the first three primes would have sufficed, seconds using a computer. Not secure at all. In fact, always remember a saying and it will serve you well - "Security is hard"! The bad guys are looking for any weak link and there are many places to look for those. –  Amzoti May 30 '13 at 4:06
Thanks @Amzoti. –  swapnil May 30 '13 at 4:08
You are very welcome. It is also worth noting that security is about people, technology and operations. Look up NSA Suite B for the cryptographic algorithms and how they are really implemented and you will see how difficult things get. Add protocols, random number generation, system level security, ... and it is hard! –  Amzoti May 30 '13 at 4:11
To make this clear. If $n$ is relatively small, say $n<10^9$, you can easily build a table of all the pairs $(x,x^e)$ for all $x, 0\le x<n$ on a small laptop, sort it according to the value of $x^e$, and just read off the plaintext. A few gigabytes of memory is all you need. If $n$ is a bit larger, building a look up table is no longer feasible, but factoring still is feasible with school level math of trial division. When $n$ is larger still, you need more sophisticated factoring algorithms. The demands on the size of $n$ depend on the range of foreseeable attacks (and their projected cost). –  Jyrki Lahtonen May 30 '13 at 7:20

Your Answer


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

Browse other questions tagged or ask your own question.