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.

I am currently attempting to learn RSA. Most of the literature I am using is at least a few years old, if not older. Given the advancements in computing and improvements in attacking RSA, I am wanting more current information. I've tried searching the internet (including stackexchange) for more up-to-date information, but I am having a hard time finding a consensus for how large the primes (and, consequently, the modulus) need to be these days to ensure security. In other words, as of today in March of 2014, how many digits do I need?

I realize the number of digits is not necessarily the point. For example, I know that if $n=pq$, where $p$ and $q$ are my primes, then choosing $p$ and $q$ close to each other introduces a serious vulnerability to my system. Namely, even if $p$ and $q$ were astronomical, a hacker could just search in the neighborhood of $\sqrt{n}$ to find my prime factors. Thus, picking $p$ and $q$ to be as large as possible at the same time would translate to making them close to each other, which would introduce the aforementioned vulnerability. I assume one must consider lots of similar pitfalls when attempting to encrypt plaintext using RSA.

I am aware this question does not lend itself well to an exact answer, so I put "guarantee" in quotation marks for that reason. In other words, assuming no major breakthrough in attacking RSA, yet preparing for the continued advancement in computing power, what is the typical size of numbers to work with today? A ballpark answer is okay. I just want to know generally what size of numbers I need to work with to be relevant these days.

share|improve this question

3 Answers 3

up vote 1 down vote accepted

RSA-768 has been factored and currently most systems are using at least 1024 bits. For example, Microsoft has an update for minimum certificate key length in 2012, requiring keys be at least 1024 bits.

As of now, 1024 bits is still considered secure. How secure? An old estimate for the cost of factoring 1024 bits is about US50 million for just one of the steps (The sieving step, if you know what it is). There are goals to push this towards 2048 bits, where the recommendation is to use it till 2030. Here is a quick reference.. Search for "Asymmetric algorithm key lengths".

For standard RSA, $n=pq$, we always choose $p,q$ to be the same size. There are also other special requirements for $p$ and $q$. A common one is to require that $p\pm 1$ and $q\pm 1$ cannot be factored into small primes, because there are specialized attack for these type of primes. More generally, there are many many other possible weaknesses, but I am not sure if there is a good article providing a comprehensive study. A general philosophy might be that the hamming weight cannot be small: if we represent $p$ and $q$ in some base-$r$, there should not be many zeroes in the representation. (Small hamming weight would mean most values are zeroes.)

Edit_1: For the part on "guarantee", you may find a good interpretation in terms of the estimated time to factor a given RSA number. The current best algorithm is the General Number Field Sieve and there is an estimated (heuristic) complexity of factoring $n$ by using this formula: $$\exp\left(\left(\sqrt[3]{\frac{64}{9}}+o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right)$$ Just put in the size of $n$. This will give you a rough measure of the number of operations required, if I am not mistaken. For example if you take $o(1)=0$ and $n=2^{1024}$ then $$\exp\left(\sqrt[3]{64/9} (1024 \ln(2))^{1/3} (\ln(1024 \ln(2)))^{2/3}\right)\approx 1.3 \times 10^{26}\approx 2^{87}$$ Edit_2: To better relate to this, notice that RSA security claims that RSA-1024 is equivalent to 80-bit symmetric key.

For reference, your typical PC can solve problems of about $2^{30+}$ in 1 week. What people might do then is to convert these number into CPU years. i.e. RSA-1024 requires xx CPU-years, RSA-2048 requires yy CPU-years. If you want better information, look out for these measures when you search for security of RSA numbers.

(Please note that I am not trained in Theoretical Computer Science and some part of my answer may be too loose.)

share|improve this answer

Based on Moore's Law, RSA predicts that 1024 bit keys will be broken in the near future and 2048 bit keys are sufficient until 2030. A 3072 bit key is about equivalent to a 128 bit symmetric key, which should not be broken for a very long time (current technology would take $10^{18}$ years to crack).

share|improve this answer
    
What's the math you do in order to figure out current technology will take $10^{18}$ years to crack? –  GaMbiT Mar 12 at 22:06
1  
@GaMbiT from eetimes.com/document.asp?doc_id=1279619 –  qwr Mar 12 at 22:24

617 decimal digits or 2048 bits should be more than good.

http://en.wikipedia.org/wiki/RSA_numbers#RSA-2048

share|improve this answer

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.