Question on RSA trapdoor permutation

Question

You plan to use a public-key cryptosystem based on the RSA trapdoor permutation in three different real-life applications, in which the attacker has, respectively, only one of the following resources:

1. a single computer,
2. a collection of computers distributed across the Internet, and
3. a quantum computer.

When choosing the length of the modulus n for the RSA trapdoor permutation, you plan to choose a different length for each of the above three attacker resource scenarios. Which of the following length settings is closer to your choice?

A. (a): 1024; (b): 2048; (c): 4096  
B. (a): 512; (b): 1024; (c): I would not use RSA    
C. (a) 2048; (b): 4096; (c): I would not use RSA    
D. (a) 512; (b): 1024; (c): 2048

Not sure how to do this. Can anyone help me with this and explain why?

Answer 1

My own answer would be: 2048, 2048, and still 2048 bits.

Why ? Because:

• 2048-bit is the current "standard recommendation"; it has been so for quite some time, and is likely to remain so for quite some time (decades). See this site for pointers.
• There are plans for removing support for keys shorter than 2048 bits in some widespread software, e.g. Firefox. Using shorter keys invites future interoperability trouble and maintenance headaches.
• There are widespread systems (in particular hardware, such as smart cards and HSM) which have trouble with keys larger than 2048 bits. Even when longer keys are supported, the computational cost rises quite sharply with the key size, so you don't want to overdo it (if your algorithm is super-secure but too heavy, then people will look for ways not to use it, and so goes security down the drain).
• If your enemy has access to a quantum computer, then he has resources which are way beyond your wildest dreams. Remember that hiring a few thugs to break your kneecaps is cheap; an attacker with a budget of more than 10k$ will just do that, instead of trying to unravel your public key with computers. Then an attacker who can afford a machine that does not seem to exist at all... Contrary to a quantum computer, a tiny camera concealed in your own glasses is doable with existing technology, and will reveal all your secrets. Worrying about quantum computers is therefore misdirected paranoia.

Your examiner would probably dislike this answer, though. He probably expects that you answer "don't use RSA" when the attacker has a quantum computer, so that you show that you have understood that a quantum computer will make short work of RSA keys of any size.

Answer 2

Consider Shor's algorithm, which solves RSA in polynomial time on a quantum computer and the fact that there is publicly available software that could factor a 512 bit modulus on a modern PC in a few days' time.

Answer 3

The closest to my choice is: C. (a) 2048; (b): 4096; (c): I would not use RSA

My answer takes in account not only details mentioned in question, but currently widely deployed security practices. I try to point out useful resources to study. Things are not as simple as pick one of A-D. I recommend to study resources I've included and draw your own conclusions.

---

US government has recommendations for security levels used in asymmetric cryptography. The systems used by US government agencies are validated according to these recommendations and only approved systems are allowed to be used.

Even if you do not intent the application for use by the US government, it is a good idea to at least meet (and occasionally exceed) their recommendations.

The modules lengths for RSA are defined in document FIPS 186-4 (Digital Signature Standard, version 4). The document defines these three levels:

1. 1024 bit modulus (approx. equivalent in strength to 80 bit symmetric key cryptography)
2. 2048 bit modulus (approx. equivalent in strength to 112 bit symmetric key cryptography)
3. 3072 bit modulus (approx. equivalent in strength to 128 bit symmetric key cryptography)

The lowest of these levels (1024 bit modulus) has been deprecated. US government agencies are no longer allowed to use 1024 bit RSA, except for certain legacy uses. (For more detail read NIST SP 800-131A.)

In interest of interoperability, it is not recommended to go below 2048 bit modulus (minimum for US government, and actually, some other organizations as well) even if assumed attackers have only single computer.

If the attacker has large number of PCs (for instance all computers in internet), 2048-bit RSA should resist attack for quite long time (maybe indefinitely). 768 bit modulus is largest that has been publicly broken, and it is expected that governments may be able to break 1024-bit RSA modulus. However, in interest of stronger security and preparing for future, I recommend stronger (such as 3072 bit) modulus against attackers, who have large computational capabilities.

Quantum computer

The part of question quantum computer is unclear. Assuming it means device which can run Shor's algorithm, then you may want to refer this question: RSA key length vs. Shor's algorithm. Then again, it is possible to purchase a quantum computer. But the ones available for purchase (such as D-Wave) are not useful in breaking RSA.