Why is this commit that sets the RSA public exponent to 1 problematic?

Question

I saw this commit in SaltStack on Hacker News, but I don't understand exactly what it does or why the original version was a cryptography error. (I also don't know a lot about how the specifics of cryptography work, either.)

-    gen = RSA.gen_key(keysize, 1, callback=lambda x, y, z: None)
+    gen = RSA.gen_key(keysize, 65537, callback=lambda x, y, z: None)

Can someone elaborate why the choice of "1" was replaced? And why is "65537" better?

Answer 1

You've essentially asked three questions:

• What is this code doing?
• Why is 1 bad?
• Why was it replaced with 65537?

It sounds like you don't have a lot of cryptography background, so I'll try to fill in some of the gaps there as well.

What is this code doing?

To understand why the original value of 1 was a broken choice, you have to understand a little bit about how RSA works.

RSA is a cryptosystem -- a way of performing key generation, encryption, and decryption -- so that you can send messages securely to other people. RSA is a member of a class called public-key cryptosystems, because the key that you use to encrypt messages is public and can be freely known by everyone. The key you use to decrypt messages enciphered with your public key is secret and known only by you, so we call it a private key.

If you imagine padlocks and keys as the analog to public keys and private keys, you can see how this might work with real-world messages:

• Bob gives Alice a padlock (his public key) and keeps the key to the lock (his private key).
• Now, if Alice wants to send a Bob a message, she puts a message inside a box, puts his padlock on a box, and sends him the box.
• Only Bob has the key, so only Bob can unlock the padlock and get inside the box.

To actually generate the key, RSA needs three important numbers:

• "N", the product of two very large prime numbers p and q
• "e", the "public exponent"
• "d", the "private exponent"

A big part of the security of RSA comes from the fact that it should be very difficult to figure out what d is, given N and e. The public key in RSA consists of two numbers: <N,e>, while the private key is <N,d>.

In other words, if I know what Bob's padlock looks like, it should be very difficult to reverse-engineer a key that will open Bob's padlock.

Why is 1 bad?

1 is a bad choice because it makes very easy to reverse-engineer a key that will open Bob's padlock, which is the opposite of what we want.

The problematic section in full looks like this:

def gen_keys(keydir, keyname, keysize, user=None):
    # Generate a keypair for use with salt
    # ...
    gen = RSA.gen_key(keysize, 1, callback=lambda x, y, z: None)

This is a Python fragment which generates a RSA key with e = 1.

The relationship between N, e, and d is given by:

d*e = 1 mod (p-1)(q-1)

But wait: if you pick e = 1, as SaltStack did, then you have a problem:

d = 1 mod (p-1)(q-1)

Now you have the private key! The security is broken, since you can figure out what d is. So you can decrypt everyone's transmissions -- you've made it so that you can trivially get Bob's key given his padlock. Oops.

It actually gets worse than that. In RSA, encryption means that you have a message m to transmit that you want to encrypt with the public key <N,e>. The enciphered message c is computed as:

 c = m^e (mod N)

So, if e = 1, then m^e = m, and you have c = m mod N.

But if m < N, then m mod N is m. So you have:

 c = m

The enciphered text is the same the message text, so no encryption is happening at all! Double oops.

Hopefully it's clear why 1 is a bad choice!

Why is 65537 better?

65537 seems like an unusual, arbitrary choice. You may wonder why, for instance, we couldn't just pick e = 3. The lower e is, the faster encryption becomes, since to encrypt anything we have to execute:

 c = m^e (mod N)

and m^e can be a very large number when e is large.

It turns out that 65537 is mostly for compatibility reasons with existing hardware and software, and for a few other reasons. This Cryptography StackExchange answer explains it in good detail.

With a suitable random padding scheme, you can pick almost any odd integer higher other than 1 without affecting security, so e = 3 is otherwise a choice that maximizes performance.