you are viewing a single comment's thread
view the rest of the comments
[–] 8 points 1 month ago (23 children)

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.

  • source
  • parent
  • hideshow 23 child comments
  • [–] 1 point 1 month ago (10 children)

    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.

  • source
  • parent
  • hideshow 10 child comments
  • [–] 1 point 1 month ago (9 children)

    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.

  • source
  • parent
  • hideshow 9 child comments
  • [–] 1 point 1 month ago (8 children)

    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.

  • source
  • parent
  • hideshow 8 child comments
  • [–] 3 points 1 month ago (7 children)

    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.

  • source
  • parent
  • hideshow 7 child comments
  • [–] 1 point 1 month ago (6 children)

    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.

  • source
  • parent
  • hideshow 6 child comments
  • [–] 1 point 1 month ago (5 children)

    You could say the same things about AES keys being short.

  • source
  • parent
  • hideshow 5 child comments
  • [–] 1 point 1 month ago* (4 children)

    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.

  • source
  • parent
  • hideshow 4 child comments
  • [–] 1 point 1 month ago (3 children)

    Most of us don't have control over the public keys we use. We connect to a web site with a browser, and the server supplies the public key.

    If you want public keys for your own purposes, I guess nothing stops you from generating 4096 bit (or whatever) ECC keys. Of course the arithmetic will be slow.

    If you're really paranoid about potential math advances affecting ECC and/or RSA, then you may be best off avoiding public key schemes altogether. Just use secret keys, and maybe Merkle tree signatures.

  • source
  • parent
  • hideshow 3 child comments
  • [–] 1 point 1 month ago (2 children)

    Just use secret keys

    You mean symmetric keys? They're great, but they aren't terribly practical in MANY application scenarios.

  • source
  • parent
  • hideshow 2 child comments
  • [–] 1 point 1 month ago (1 child)

    They can be less convenient, yes, but a situation where you need truly public keys is probably not that secure to begin with. If you're just trying to talk to your friends from your tree house, symmetric encryption is completely practical, including using something like DUKPT for forward secrecy.

  • source
  • parent
  • hideshow 1 child comment
  • [–] 1 point 1 month ago (7 children)

    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.)

  • source
  • parent
  • hideshow 7 child comments
  • [–] 3 points 1 month ago (6 children)

    We know for certain do that it is not in NP hard

    It's likely to be NP-intermediate (outside of P, but not NP-hard), but it is not known.

    (@Kairos@lemmy.today)

    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.

  • source
  • parent
  • hideshow 6 child comments
  • [–] 1 point 1 month ago* (5 children)

    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.

  • source
  • parent
  • hideshow 5 child comments
  • [–] 2 points 1 month ago*

    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.

  • source
  • parent
  • [–] 0 points 1 month ago* (last edited 1 month ago) (3 children)

    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?

  • source
  • parent
  • hideshow 3 child comments
  • [–] 1 point 1 month ago (2 children)

    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.

  • source
  • parent
  • hideshow 2 child comments
  • [–] 1 point 1 month ago

    virtually nobody in the discipline believes that to be the case.

    While I agree that NP is likely not within P, that "No True Scotsman" argument is exceptionally weak for such a well disciplined field.

  • source
  • parent
  • [–] 0 points 1 month ago*

    No, we don’t use it as an adjective.

    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...".

    Of course, we can’t rule it out as a possibility.

    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.

  • source
  • parent
  • [–] 1 point 1 month ago (3 children)

    Factoring is at most NP-complete because we have a polynomial time verification for it.

  • source
  • parent
  • hideshow 3 child comments
  • [–] 0 points 1 month ago (2 children)

    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.

  • source
  • parent
  • hideshow 2 child comments
  • [–] 1 point 1 month ago* (1 child)

    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.

  • source
  • parent
  • hideshow 1 child comment
  • 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.

  • source
  • parent