[tommiegannert]

I think this is where the move to elliptic curve comes in, and that seems well on its way. Both in signatures and handshakes (Diffie-Hellman).

Perhaps it's not a one minute operation to DR, but I doubt everything would be open if RSA/DH was rendered insecure overnight. I know my SSH keys are a mixed bag right now.

[TheCondor]

Arguably, we know a lot more about elliptical curves than prime number theory too. There have definitely been a lot more folks working on it.

There are other algorithms, NIST has a post-quantum project. There are options, but it’s a lot more than having some algorithms, we need protocols and they are still a bit off. Prime factorization isn’t going to get easier or faster though. There might be another attack or approach to attacking, some other numerical break through that leads to faster rsa cracking might be found but it’s hard to imagine it being that practical.

[exe34]

does the move to elliptic crypto suggest that the people in the know expect prime factorisation to be broken soon?

[bjoli]

If anything, ECC is probably easier to break with qc. Shor's algorithm works "better" for discrete logarithms than for prime factorisation. "Better" as in requiring a smaller quantum computer. Still way beyond what is available today.

The reason for switching to ECC is speed and key size. The NSA recommends 3096bit rsa keys for 128 aes, but only 256 bit ecc keys for the same security against traditional attacks.

They also went ahead and recommended 348bit keys for ecc, but I don't know if something like that is widely used anywhere. Curve448 is nice but slow. Curve41417 is fast but largely unused.

[Jach]

Since no one mentioned, a major reason to prefer elliptic curves is that you can get equivalent security for much smaller key sizes.

[kevin_thibedeau]

I had to implement key generation on an embedded device @ 180MHz. RSA2048 would take upwards of five minutes if you didn't get lucky finding primes early on. Stronger ECC would be done within a second.

[tommiegannert]

And the key consituents don't have to be prime. That use of heuristics has always scared me a bit.

[dspillett]

Nit-pic: the key constituents only need to be co-prime rather than absolutely prime, though in practise this makes little or no difference.

[bluGill]

So far as we know. It scares some people that maybe co-primes working might be a sign of some future attack. Nobody has been able to figure out how such an attack works, but considering RSA is defined for primes, that some non-prime numbers also work is scary.

[tzs]

> Nobody has been able to figure out how such an attack works, but considering RSA is defined for primes, that some non-prime numbers also work is scary.

What do you mean by some non-prime numbers working? Do you mean that instead of picking two primes, p and q, and then e and d such that ed = 1 mod ϕ(pq) one can sometimes pick a prime p and composite q or even composite p and composite q, compute e and d such that ed = 1 mod ϕ(pq), and still get a working RSA system?

If so, that shouldn't actually be scary. Consider a composite positive integer N. The positive integers that are less than N and relatively prime to it form a finite group under multiplication mod N with ϕ(N) elements. For each element a in that group, a^ϕ(N) = 1 mod N. We can raise that to any positive integer power k giving a^(k ϕ(N)) = 1 mod N. Multiply by a giving a^(k ϕ(N) + 1) = a mod N.

If we pick e and d such that ed = k ϕ(N) + 1 for some k, then we will have (a^e)^d = a mod N for all a in the group, i.e., for all a in [1, N) that are relatively prime to N.

That almost gives us RSA E(m) = m^e mod N for encryption and D(m) = m^d mod N for encryption. Given our initial N, e and d are easy to compute because ed = k ϕ(N) + 1 for some k is true for any e, d where ed = 1 mod ϕ(N). So as long as we pick N so that we can easily compute ϕ(N) but someone just given N and e cannot, we are all set--except for one thing.

That one thing is that the above reasoning only shows that it works when m is relatively prime to N. We would like it to work for all messages in [1, N), not just the ones relatively prime to N.

If we pick N = p q where p and q are primes then the messages m that we have to worry about are: p, 2p, ..., (q-1)p and q, 2q, ..., (p-1)q. All the other possible messages will be relatively prime to pq and so are covered by the earlier arguments.

Because (ab)^e = a^e b^e, if our system works for a and b, it will work for ab, so we only need to show it works for p and that will also cover 2p, 3p, ..., (q-1)p, and similarly for q.

To show it works for p, we can consider powers of p mod q. In particular p and q are relatively prime, and p^ϕ(q) = 1 mod q.

Recall that N=pq. ϕ is multiplicative, and so ϕ(q) divides ϕ(N), and so p^ϕ(N) = 1 mod q, or p^(ϕ(N)+1) = p mod q. Note that also p^(ϕ(N)+1) = p mod p (because both sides are 0 mod p). And since p and q are relatively prime, p^(ϕ(N)+1) = p mod pq, or p^(ϕ(N)+1) = p mod N. So our almost RSA does work for p. Similar argument shows it works for N, and or almost RSA turns out to be actual RSA.

What if we try it where N is a product of 3 distinct primes instead of 2? The messages that are not relatively prime to N then will fall into 6 classes: messages where gcd(m,N) = one of the prime factors of N, and messages were gcd(m,N) = the product of two of the prime factors of N.

The above argument to show that a message equal to p is fine when N=pq extends fairly straightforwardly to show that those 6 classes of non-relatively prime messages an N that is a product of 3 distinct primes works.

So as long as your composite N is square free it should be suitable for an RSA system.

[eddd-ddde]

I remember when I generated my first EC key and added it to an SSH client. I was so surprised by the size of the key I spent some time researching if I had made a mistake.

Honestly impressive.

[exe34]

nice thank you!

[staunton]

It's to do with "if we ever have big/good quantum computers, prime factorization is doable" and with "let's use the new shiny things".

On a related note, someone might discover some elliptic curve math tomorrow and your CPU can break all that stuff just as well...

[exe34]

so with my cynic hat on, maybe a bunch of people already have that and that's why we're being moved off the hard stuff.

[staunton]

The NSA had the option to do something like that when they (via NIST) standardized DES.

They chose to standardize a version that's secure against attacks that only they knew at the time, shorten the key length so they can still brute-force it if they really need to, and successfully kept the attack secret until researchers at a foreign university independently discovered it decades later.

[alphager]

Yup, that was the older generation. The newer generation used NIST to propagate a backdoored RNG and to weaken several ECC-curves.

[temporary_name]

https://en.wikipedia.org/wiki/Shor%27s_algorithm

As soon as quantum computers have enough qbits prime factorisation can be done very quickly. Not sure the timeline on that as there are a lot of challenges in the technology and it is hideously expensive, but a lot of the move away from RSA to elliptic curves is driven by readiness for quantum computing.

https://en.wikipedia.org/wiki/Post-quantum_cryptography

[kamov]

Elliptic curve cryptography can be broken by Shor's algorithm as well

https://arxiv.org/pdf/1706.06752

[upofadown]

... and easier than with RSA. Not that it would make a significant difference.

[fragmede]

sgt101 posted a good comment about this a couple months back: https://news.ycombinator.com/item?id=40187560

tl;dr: not in our lifetime.

[shakow]

Smaller key sizes and faster at a given level of security, PQ-safe (at least as far as we publically know).