RSA has been around a long time and is relatively easy to understand and implement. But for new deployments we’re supposed to use ECC instead. The comment earlier about P vs NP is unfortunately confused. Factoring is not known to be NP-hard and it probably isn’t.
I’ve always had a bit of a queasy feeling about ECC, particularly secp256k1 and ECDSA due to the Bitcoin value attracting attackers, but the whole family as well. The massive BTC processing farms are also, essentially, ECC brute forcing tools-for-hire if you know the right people to ask.
The relative simplicity / ease of understanding RSA and the longevity of it in the field, being attacked by so many academics over the decades, is what puts me at ease about its security. Shor’s algorithm may take it down some day, if the issues around scaling up quantum computers are ever solved, but those issues may be rooted in the things that keep RSA secure - kind of a “conservation of effort” effect. Or not, the future is notoriously difficult to predict.
Fwiw, bitcoin mining amounts to brute forcing SHA256 rather than ECC. Tendency these days for ECC (like in TLS) is to use Curve25519 rather than secp256k1. PQ (post quantum) is an entirely different topic and is in the direction of much more complicated schemes. RSA (or rather, integer factoring) has a long history of falling to better and better attacks, with a (now expired) 512 bit CA certificate recently having been factored on a single workstation. The first fielded deployment was at a nuclear lab and it used 336 bit keys! The big crypto nerds all seem to prefer ECC to RSA now. I tend to defer to them.
I’ve moved to ECC because the software packages fight me less in using it (except Microsoft DevOps ssh keys which insist on using RSA - making them the biggest pain in the process lately.)
RSA is eroding slowly - as all cryptographic algorithms have done historically. The 3072 bit RSA keys I put into practice 10 years ago are still “secure enough” - but I expect after a century they’ll look pretty quaint and easily broken as well.
On the other hand: ECC seems great from all kinds of metrics, easy to implement, small keys, etc. - it just feels like the kind of thing that a clever insight is going to demolish all at once some day, unlike RSA that’s sort of gracefully degrading with time.
I would say, there are known sub-exponential algorithms for factoring, while nothing better than (exponential) brute force is known for ECC. So, slightly better algorithms that erode RSA further are incremental improvements, while anything sub-exponential at all for ECC would be a breakthrough. Of course as someone once said, predictions are hard to make, especially about the future.
Just looking at the keys in authorized_keys, that short ECC key feels like any algorithmic breakthrough is going to turn it trivial… RSA already has those easier algorithms, but it also has the brute force bits to make the easier algorithms harder.
We can actually make stronger claims about factoring. We know for certain do that it is not in NP hard, so you are correct there
And I’m not exactly a security expert, but moving away from RSA at this point makes sense. Early assumptions about the difficulty of factoring large semi-primes certainly hasn’t panned out (in particular in light of the growing risk of quantum computers.)
Factoring is at most NP-complete because we have a polynomial time verification for it.
That means it’s in NP. These terms mean very precise things and it’s easy to get confused, but at the end of the day the new paper didn’t find a faster way to factor.
Four decades ago, the professor who taught me P vs NP absolutely stuffed his explanation of the polynomial refactoring example, drawing sum of products on the board as his example - bugged the crap out of me because I could visualize code for an algorithm to refactor sum of products relatively easily - certainly in polynomial time. I brought that to him after the next lecture and he clarified: product of sums is the hard problem, well, yeah, obviously when you look at that nightmare. I assume he had been teaching it for about a decade as well, he certainly had been in the department that long and longer.
You wrote “we know for certain do that it [factoring] is not in NP hard”. That sentence is 1) borderline ungrammatical (we usually use NP-hard as an adjective, though it also denotes a set); and 2) in error. We suspect factoring is not NP-hard but we don’t know for certain (consider what happens if P=NP). The error suggests confusion about what these terms mean. If you’re really teaching this subject, can I ask what textbook you are using?
No, we don’t use it as an adjective. It is a set. That’s literally all it is.
And predicating anything on the assumption that P equals NP is rather absurd. Of course, we can’t rule it out as a possibility. But virtually nobody in the discipline believes that to be the case. And honestly, why would it be? If there were polynomial time solutions to that many problems of that degree of importance, surely we would have discovered something by now.
Exactly, we don’t know for certain. Of course it’s very unlikely, but in math when we say we know something for certain, it means there’s a theorem to that effect. There reason to think that factoring is not NP-hard but we don’t know for certain. If you still claim otherwise, can you cite a theorem?
Anyway, yes, you’re confused, and at this point you’re spouting misinformation. You might consider reading a book or taking a class.
If there were polynomial time solutions to that many problems of that degree of importance, surely we would have discovered something by now.
It’s still an open problem, there’s a $1 million Clay prize waiting for you to claim it if you have a proof either way.
Factoring is not NP-complete because it is not a member of NP-hard.
You are correct that verifiability is in there, but you have to also be able to do the reduction.
There are plenty of problems out there where we lack polynomial time solutions, while the problem also lacks the expressiveness required to reduce back and forth.
Factoring is not in any category because we don’t have a proof for it. As it stands, the algorithms we have require exponential time in the worst case, but solutions can be verified in polynomial time, which is NP-complete. I said “at most” for a reason.
Also, every algorithm is verifiable. If there’s no better way to do it then re-running the algorithm and that algorithm is exponential, then it’s NP-Hard.
Factoring is in a category. Everything computable exists somewhere. We know factoring to be in NP.
What I was disagreeing with was the “at least” and “at most” characterization of NP completeness. It is a set, not a boundary. The actual diagram of the complexity zoo is much more complicated than concentric circles.
And for verifiability, I was not referring to it as an existential sort of thing. I was simply saying that I agreed with you in that particular facet, but it isn’t sufficient to describe NP completeness. You also need NP-hardness.
RSA is secure because it relies on P vs NP. Very basically, RSA multiplies 2 very large prime numbers together to encrypt things. We rely on something similar for secure Internet connections
That is incorrect. It relies on perceived difficulty of factoring large semi-prime. P equals NP is related, of course, if it happens to be an NP-intermediate problem, but the difficulty of factoring is not because it’s NP-complete.
There are already classical algorithms that are sub-exponential to solve the problem. If it were the case that the problem was NP-complete, then we would have had a big advance in our theory and practice based on it.
I’m not about to get into the weeds about P vs NP to explain a concept to someone that doesn’t know much about encryption in the first place. I’m aware that factoring isn’t really NP complete, but P vs NP is about solving vs verifying solutions for something in Polynomial time, which can’t be done via brute force for RSA keys.
If you want to be pedantic, fine. Integer factoring is not in P. Therefore the math used to encrypt RSA is not in P. The usage of integer factoring to encrypt therefore means it can’t be decrypted in P using brute force. That’s the point I’m making.
There are tradeoffs with encryption. RSA is so secure, that the US government has tried to insert a mathematic backdoor into the key selection because that’s the easiest method to attack the encryption. RSA uses thousands of bits for their encryption, making it inefficient for most attacks. The attack detailed in this article is on one of the weaker RSA algorithms, with only 1024 bits. The high end RSA uses 4096 bits or more, I believe the algorithm has increased the bit length to officially support 8192.
On the other side of RSA is another secure algorithm called AES. It can go up to 512 bits, but it hashes the key to meet the key length instead of relying on generating huge prime numbers. It makes it more resilient to certain types of attacks, but the bit limitation makes it easier to brute force or use rainbow tables.
Thanks for this answer. The article makes it sound as though even the 4096-bit versions are now more or less trivial to defeat given a bit of money for a capable machine and this new method:
Even for 2048- and 4096-bit keys, the method reduces the security of RSA to unacceptable levels. The National Security Agency, National Institute of Standards and Technology, and European Union Agency for Network and Information Security require that any cryptosystem should provide a level of no less than 128 or more bits, meaning the operations required must exceed 2^128.
The forgery attack drops these levels to 2^65, 2^90, and 2^119 for 1024-, 2048-, and 4096-bit keys respectively. These levels may further drop because Heninger’s team did all the coding by hand and used no AI or GPUs in performing the forgeries. The researcher said these tools will “almost certainly” drop the security levels further.
Just to put a bit of context on those, OpenAI said they used 180,000 GPUs for training their GPT-5 model. As I understand it, each GPU has ~16,000 cores, and each of those cores does a couple billion operations per second. With that cluster, 2^65 operations takes a couple seconds, 2^90 takes many years, and 2^119 is off in “the sun has grown to surround the Earth” territory. The NSA is concerned with protecting their stuff against organizations with hundreds of billions of dollars, and a hundred of years of time to dedicate dozens or hundreds of people to breaking it. “Not good enough” in that context is a very different bar than what most people have to worry about.
You also need to provide them 2^43 unsalted responses, which is more than a casual few.
Elliptical curve for RSA was immediately phased out
what? when did RSA want to use elliptical curves? its a completely different technology. and ECC itself was not phased out of anywhere. certain curves were, not ECC as a whole.
Tl;dr - Choosing parameters for ECC is very important but also very difficult. Also, ECC is more resistant to quantum algorithms than RSA.
I didn’t know about the PQC readiness of ECC so thank you!
To my understanding, picking the right ECC parameters is critical to ensuring large enough entropy that it can’t be brute forced. There are a lot of weak and easy to compromise parameters, and a lot of trust has to be put in the standards organizations declaring which ones are “safe” like the NIST curves. Or you can choose your own, with a lot of risk associated.
There’s also the fact that I believe there’s more potential to leak info/expose side channels on the embedded devices running these protocols (I’ve personally had to worry at work!)
interesting about the security, it looks like ECC is arguably more secure against quantum algorithms? I first learned about all of this stuff about 10 years ago, and I only vaguely remember reading about the pqc resistance. Thanks for the update on that!
Edit: But I want to be clear I’m not a security expert, just some lady whose had to deal with embedded cryptography from time to time.
tell me again why people still use RSA?
Modern crypto systems don’t. They’re still available for legacy interoperation, but modern stuff uses ed25519 and the like.
RSA has been around a long time and is relatively easy to understand and implement. But for new deployments we’re supposed to use ECC instead. The comment earlier about P vs NP is unfortunately confused. Factoring is not known to be NP-hard and it probably isn’t.
I’ve always had a bit of a queasy feeling about ECC, particularly secp256k1 and ECDSA due to the Bitcoin value attracting attackers, but the whole family as well. The massive BTC processing farms are also, essentially, ECC brute forcing tools-for-hire if you know the right people to ask.
The relative simplicity / ease of understanding RSA and the longevity of it in the field, being attacked by so many academics over the decades, is what puts me at ease about its security. Shor’s algorithm may take it down some day, if the issues around scaling up quantum computers are ever solved, but those issues may be rooted in the things that keep RSA secure - kind of a “conservation of effort” effect. Or not, the future is notoriously difficult to predict.
Fwiw, bitcoin mining amounts to brute forcing SHA256 rather than ECC. Tendency these days for ECC (like in TLS) is to use Curve25519 rather than secp256k1. PQ (post quantum) is an entirely different topic and is in the direction of much more complicated schemes. RSA (or rather, integer factoring) has a long history of falling to better and better attacks, with a (now expired) 512 bit CA certificate recently having been factored on a single workstation. The first fielded deployment was at a nuclear lab and it used 336 bit keys! The big crypto nerds all seem to prefer ECC to RSA now. I tend to defer to them.
I’ve moved to ECC because the software packages fight me less in using it (except Microsoft DevOps ssh keys which insist on using RSA - making them the biggest pain in the process lately.)
RSA is eroding slowly - as all cryptographic algorithms have done historically. The 3072 bit RSA keys I put into practice 10 years ago are still “secure enough” - but I expect after a century they’ll look pretty quaint and easily broken as well.
On the other hand: ECC seems great from all kinds of metrics, easy to implement, small keys, etc. - it just feels like the kind of thing that a clever insight is going to demolish all at once some day, unlike RSA that’s sort of gracefully degrading with time.
I would say, there are known sub-exponential algorithms for factoring, while nothing better than (exponential) brute force is known for ECC. So, slightly better algorithms that erode RSA further are incremental improvements, while anything sub-exponential at all for ECC would be a breakthrough. Of course as someone once said, predictions are hard to make, especially about the future.
Just looking at the keys in authorized_keys, that short ECC key feels like any algorithmic breakthrough is going to turn it trivial… RSA already has those easier algorithms, but it also has the brute force bits to make the easier algorithms harder.
Difficult to see, always moving the future is.
You could say the same things about AES keys being short.
And I do…
Academically, I trust the more modern algorithms with the shorter keys - not least because all the guidance says to trust them.
Viscerally, looking at the keys, the short ones just feel more vulnerable.
We can actually make stronger claims about factoring. We know for certain do that it is not in NP hard, so you are correct there
And I’m not exactly a security expert, but moving away from RSA at this point makes sense. Early assumptions about the difficulty of factoring large semi-primes certainly hasn’t panned out (in particular in light of the growing risk of quantum computers.)
It’s likely to be NP-intermediate (outside of P, but not NP-hard), but it is not known.
(@Kairos@lemmy.today)
That means it’s in NP. These terms mean very precise things and it’s easy to get confused, but at the end of the day the new paper didn’t find a faster way to factor.
I’m not confused. I’ve been teaching this subject for over a decade.
I’m not certain are you arguing with me?
I was largely agreeing with you.
Four decades ago, the professor who taught me P vs NP absolutely stuffed his explanation of the polynomial refactoring example, drawing sum of products on the board as his example - bugged the crap out of me because I could visualize code for an algorithm to refactor sum of products relatively easily - certainly in polynomial time. I brought that to him after the next lecture and he clarified: product of sums is the hard problem, well, yeah, obviously when you look at that nightmare. I assume he had been teaching it for about a decade as well, he certainly had been in the department that long and longer.
You wrote “we know for certain do that it [factoring] is not in NP hard”. That sentence is 1) borderline ungrammatical (we usually use NP-hard as an adjective, though it also denotes a set); and 2) in error. We suspect factoring is not NP-hard but we don’t know for certain (consider what happens if P=NP). The error suggests confusion about what these terms mean. If you’re really teaching this subject, can I ask what textbook you are using?
No, we don’t use it as an adjective. It is a set. That’s literally all it is.
And predicating anything on the assumption that P equals NP is rather absurd. Of course, we can’t rule it out as a possibility. But virtually nobody in the discipline believes that to be the case. And honestly, why would it be? If there were polynomial time solutions to that many problems of that degree of importance, surely we would have discovered something by now.
While I agree that NP is likely not within P, that “No True Scotsman” argument is exceptionally weak for such a well disciplined field.
From the first sentence of https://en.wikipedia.org/wiki/NP-hardness : “In computational complexity theory, a computational problem H is called NP-hard if…”.
Exactly, we don’t know for certain. Of course it’s very unlikely, but in math when we say we know something for certain, it means there’s a theorem to that effect. There reason to think that factoring is not NP-hard but we don’t know for certain. If you still claim otherwise, can you cite a theorem?
Anyway, yes, you’re confused, and at this point you’re spouting misinformation. You might consider reading a book or taking a class.
It’s still an open problem, there’s a $1 million Clay prize waiting for you to claim it if you have a proof either way.
deleted by creator
Factoring is at most NP-complete because we have a polynomial time verification for it.
Factoring is not NP-complete because it is not a member of NP-hard.
You are correct that verifiability is in there, but you have to also be able to do the reduction.
There are plenty of problems out there where we lack polynomial time solutions, while the problem also lacks the expressiveness required to reduce back and forth.
Factoring is not in any category because we don’t have a proof for it. As it stands, the algorithms we have require exponential time in the worst case, but solutions can be verified in polynomial time, which is NP-complete. I said “at most” for a reason.
Also, every algorithm is verifiable. If there’s no better way to do it then re-running the algorithm and that algorithm is exponential, then it’s NP-Hard.
Factoring is in a category. Everything computable exists somewhere. We know factoring to be in NP.
What I was disagreeing with was the “at least” and “at most” characterization of NP completeness. It is a set, not a boundary. The actual diagram of the complexity zoo is much more complicated than concentric circles.
And for verifiability, I was not referring to it as an existential sort of thing. I was simply saying that I agreed with you in that particular facet, but it isn’t sufficient to describe NP completeness. You also need NP-hardness.
RSA is secure because it relies on P vs NP. Very basically, RSA multiplies 2 very large prime numbers together to encrypt things. We rely on something similar for secure Internet connections
That is incorrect. It relies on perceived difficulty of factoring large semi-prime. P equals NP is related, of course, if it happens to be an NP-intermediate problem, but the difficulty of factoring is not because it’s NP-complete.
There are already classical algorithms that are sub-exponential to solve the problem. If it were the case that the problem was NP-complete, then we would have had a big advance in our theory and practice based on it.
I’m not about to get into the weeds about P vs NP to explain a concept to someone that doesn’t know much about encryption in the first place. I’m aware that factoring isn’t really NP complete, but P vs NP is about solving vs verifying solutions for something in Polynomial time, which can’t be done via brute force for RSA keys.
I don’t care who you want to get in the weeds with or what you wish to spar about, you’re just not correct.
There is no almost NP complete. There are strong and weak variants, sure, and those have particular implications.
But you’re drawing conclusions that don’t exist from definitions that you clearly don’t understand.
Signed: Somebody who has taught theory of computation for over a decade.
If you want to be pedantic, fine. Integer factoring is not in P. Therefore the math used to encrypt RSA is not in P. The usage of integer factoring to encrypt therefore means it can’t be decrypted in P using brute force. That’s the point I’m making.
We actually don’t know if integer factorization is not in P, though.
Right now, I think most of us would guess that it is a prime candidate for NP Intermediate. Hence why I mentioned it earlier.
And you absolutely can solve it in polynomial time just not with classical architectures.
but do we not have other, much more secure encryption that is just as easy to employ?
There are tradeoffs with encryption. RSA is so secure, that the US government has tried to insert a mathematic backdoor into the key selection because that’s the easiest method to attack the encryption. RSA uses thousands of bits for their encryption, making it inefficient for most attacks. The attack detailed in this article is on one of the weaker RSA algorithms, with only 1024 bits. The high end RSA uses 4096 bits or more, I believe the algorithm has increased the bit length to officially support 8192.
On the other side of RSA is another secure algorithm called AES. It can go up to 512 bits, but it hashes the key to meet the key length instead of relying on generating huge prime numbers. It makes it more resilient to certain types of attacks, but the bit limitation makes it easier to brute force or use rainbow tables.
AES is asymmetric encryption and cannot be used for the same things as RSA. EdDSA would be more comparable to RSA.
I know that AES is symmetrical. I was using it to illustrate that symmetrical and asymmetrical encryption have tradeoffs that cannot be worked around.
Thanks for this answer. The article makes it sound as though even the 4096-bit versions are now more or less trivial to defeat given a bit of money for a capable machine and this new method:
Just to put a bit of context on those, OpenAI said they used 180,000 GPUs for training their GPT-5 model. As I understand it, each GPU has ~16,000 cores, and each of those cores does a couple billion operations per second. With that cluster, 2^65 operations takes a couple seconds, 2^90 takes many years, and 2^119 is off in “the sun has grown to surround the Earth” territory. The NSA is concerned with protecting their stuff against organizations with hundreds of billions of dollars, and a hundred of years of time to dedicate dozens or hundreds of people to breaking it. “Not good enough” in that context is a very different bar than what most people have to worry about.
You also need to provide them 2^43 unsalted responses, which is more than a casual few.
Yes it’s becoming more common to have Elliptic Curve keys. But many still use RSA.
Elliptical curve for RSA was immediately phased out as soon as it was proven that the NIST was influenced by the NSA to implement it
what? when did RSA want to use elliptical curves? its a completely different technology. and ECC itself was not phased out of anywhere. certain curves were, not ECC as a whole.
And if I remember correctly, I believe it has more weaknesses (especially potential unknown ones) than RSA.
But it’s definitely more efficient on embedded hardware, and for sure still gets used in that space. Not that I’d know cough cough
what are those weaknesses? so far I have only read for users that ECC is more secure than RSA
not only on embedded hardware, but everywhere and also in network transfer because of the smaller keys
Tl;dr - Choosing parameters for ECC is very important but also very difficult. Also, ECC is more resistant to quantum algorithms than RSA.
I didn’t know about the PQC readiness of ECC so thank you!
To my understanding, picking the right ECC parameters is critical to ensuring large enough entropy that it can’t be brute forced. There are a lot of weak and easy to compromise parameters, and a lot of trust has to be put in the standards organizations declaring which ones are “safe” like the NIST curves. Or you can choose your own, with a lot of risk associated.
There’s also the fact that I believe there’s more potential to leak info/expose side channels on the embedded devices running these protocols (I’ve personally had to worry at work!)
interesting about the security, it looks like ECC is arguably more secure against quantum algorithms? I first learned about all of this stuff about 10 years ago, and I only vaguely remember reading about the pqc resistance. Thanks for the update on that!
Edit: But I want to be clear I’m not a security expert, just some lady whose had to deal with embedded cryptography from time to time.
Well, as they say the S in IoT is for security
Ohhh so that’s what they meant by putting IoT nodes on the Edge!
Yes we’re supposed to use ECC instead of RSA now. The major crypto libraries support it so you just configure your program to use it.
deleted by creator