# What are the security issues for generating a RSA private key that is 3 bits in size? [closed]

And is it possible for me to be able to perform these attacks or would I need to have very powerful hardware?

• Are you sure you mean one bit? That's not a very useful key - it'd either be 0 or 1. – Boycott SE for Monica Cellio Feb 16 '17 at 22:34
• As in when you generate a SSH public key pair it says what size you want the key? – 99Con Feb 16 '17 at 22:42
• You can't have a 1-bit key. The key consists of an exponent and a modulus integer pair. – Arminius Feb 16 '17 at 22:49
• As @Arminius said, the smallest key possible is 6 bits, and you can break it by hand in seconds... – ThoriumBR Feb 16 '17 at 23:02
• How would you do that? – 99Con Feb 16 '17 at 23:32

(Original question)

What are the security issues for generating a RSA private key that is 1 bits in size?

You can't have a 1-bit key.

The key size of an RSA key denotes the size of the RSA modulus. This modulus is a product of two distinct prime numbers. So the smallest possible value would be `6 = 2 * 3` which fits into 3 bits (`6 = 0b110`).

It is similarly ridiculous to choose the public key exponent to be 1, because then the private key exponent must also be 1 (the only possible multiplicative inverse). This means that the ciphertext looks exactly like the plaintext. Consequently, this also violates the RSA specification.

What are the security issues for generating a RSA private key that is 3 bits in size?

For your private key to be secure, the distinct primes that build the RSA modulus have to be much larger since RSA relies on the assumption that there is no efficient algorithm for integer factorization (the task of retrieving the primes from the modulus). For small values however, you don't need an efficient algorithm as it's trivial to obtain the prime factors by brute force. And once you got the primes `p` and `q` for modulus `m`, you can calculate `φ(m) = (p-1)*(q-1)` (Euler's totient function) and then proceed the same way as in the initial key creation process. You simply calculate the private key exponent `d` for the known public exponent `e` by solving `e*d ≡ 1 (mod φ(m))`. See the key generation algorithm for details.

The issue is that: a 3-bit key is dreadfully easy to crack since it's remarkably easy to factor.

Notice in this article on RSA the comment "... this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem."

The largest integer in base-10 that can be represented in a 3-bit word (111) is 7

With no difficulty factoring the number 7, there is no strength to the 3-bit key. The lack of verification of key-strength in RSA is exactly RSA's problem. Nothing stops you from using a 3-bit key.

• But then nothing stops you generating a 1-megabit RSA key using an atrocious or nobbled RNG with only say 10 or 20 bits of entropy, and that's much harder to catch by a simple script or even auditor-type human looking at the pubkey string. – dave_thompson_085 Feb 18 '17 at 9:23
• The question is about a 3-bit key not a 1M key - but yes a 1M key would be much harder to crack. – user34445 Feb 18 '17 at 10:52
• No, my example of a badly generated 1Mbit key would NOT be hard to crack, even though superfically it looks strong. 'Stop[ping] you from using a [small] key' would be good but it would NOT 'verif[y] key-strength' and only verifying actual strength (not size) would actually solve the 'problem'. – dave_thompson_085 Feb 19 '17 at 0:08