Hacker News Reader

Comment by simias | Hacker News Reader

Can someone comment on how broken it was to use 1 as exponent? Is it just a theoretical concern or does it mean the crypto could have been easily broken (as we saw with cryptocat yesterday)?

I'm asking because they seem to treat it like a minor issue:

It's of course questionable whether 1 (not a prime) was a good choice for the exponent to begin with, but it's hardly necessary to lose faith over this.

View on HN

In the RSA cryptosystem there are three really important numbers N (which is the product of two large primes N=pq), e (the public exponent) and d (the private exponent). The public key in an RSA scheme is <N,e> and the private key is <N,d>. The only bit of the private key that's private is d.

A large part of the security of RSA relies on you not being able to figure out d from N and e. Now the key element of RSA is that

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

So what happens if e = 1? You get

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

So you know the value of d. So you know the private key. So you can decrypt everything.

But you don't actually need to do that because what is RSA encryption? It's computing the following (c is the cipher text you'll transmit, m is the message being sent which is to be encrypted with the public key <N,e>)

  c = m^e (mod N)

If e = 1 then that's

  c = m (mod N)

but, oh wait, m is always < N so m (mod N) is just m, i.e.

  c = m

i.e. the encryption does nothing.

Looking on the bright side an exponent of 1 does make RSA quite fast :-)

PS Test code for those interested showing the same N with exponents 1 and 65537 and effect of encryption: https://gist.github.com/jgrahamc/5933984

.. to guarantee m < N, m in real world actually is not a message itself, but a key for symmetric encryption of the message

So the key is getting transferred in plaintext, if their implementation is what I think it is.

Funny, I though the private key had p and q, but then I reread the algo description

The 1 mod (p-1)(q-1) comes from Euler's theorem and (p-1)(q-1) is how you calculate the totient for numbers that are the product of 2 primes p and q

On a scale of 1-10, it was about a 15 on the broken scale. As explained in the comments on the patch, a public exponent of 1 means a private exponent of 1 (it's the inverse). This makes it completely, trivially broken.

So why don't the crypto libs at least throw a warning that "what you're doing is nonsensical" if not just reject an exponent of 1 outright? We hammer on people not to invent their own crypto, yet here someone is, using the RSA lib, and still doing it wrong.

They're not using a crypto library, they implemented RSA from scratch.

They're using a library (M2Crypto) to generate the an RSA key at least, so ams6110's point stands.

Oh. Sorry about that. I should have looked at the diff more carefully.

Because crypto libs can't see the future. I'm struggling to think of a case where using cryptographic primitives should be bubblewrapped. Don't use the primitives if you don't know what you're doing.

Also note that that quote from user madduck appears to be from a user of Salt in the issue tracker, not one of the project maintainers. It seems like they added a comment below and an edit to the first comment to clarify that.

Reply on news.ycombinator.com