3 ms·

That is what all cryptography is based on? And I don't know what subpolynomial time nonsense you're talking about.

by eximius 11y ago

tptacek 11y ago
If you're going to be rude, at least be correct. All cryptography is not in fact based on factoring; in fact, most public-key crypto isn't.
- eximius 11y ago
  I wasn't referring to factoring. I quite like lattice based and ECC systems. I was referring to 'if it's hard for me it must be hard for you'. ALL cryptography is based off of that assumption. edit: I can't seem to reply to you again, so I'll edit. This is all a big miscommunication. I was more confused than hostile, though I recognize how it came off poorly. I genuinely thought he had some fundamental understandings due to the combination of things he said. I was mistaken and my response came off poorly.
  - tptacek 11y ago
    That's a reading of the original comment so uncharitable as to seem tendentious. The commenter was specific about factoring; they were not calling into question the entire idea of a trapdoor function.
justifier 11y ago
> subpolynomial time nonsense what exactly do you mean by this?
- tptacek 11y ago
  The original poster probably meant to write "sub-exponential". The commenter to whom you're responding may or may not have known what the correct term was; we'll never know, because they chose snarky incivility instead of correction.
  - justifier 11y ago
    i am the original poster :p and the 'sub' was misplaced, i actually asked instead of editing the original in case this was the reason i was called out so i could explain my typo for clarification the original should simply read 'polynomial time'
    - khedoros 11y ago
      > factoring numbers is deterministically achievable in sub polynomial time Am I missing something? I thought that the whole point of using the difficulty of integer factorization as the strength of things like RSA was that it's not known to be solvable in polynomial time. "P==NP" is one of the unsolved problems of computer science. I think that the state of the art is that we can factor in sub-exponential time.
      - tptacek 11y ago
        By "things like RSA", you pretty just much mean "RSA". A lot of progress was made on integer factorization over the last 35 years, so that key sizes we'd have thought totally reasonable in 1995 are totally inadequate today. That is not similarly true of non-factoring systems, and so it's legit to point out the relative weakness of IFP crypto compared to other approaches.
        khedoros 11y ago
        I take your point. ECC probably wouldn't cost Nintendo more to implement, but would provide a system that probably isn't being attacked as successfully, hopefully giving their system more time on the market before it's cracked.
        tptacek 11y ago
        It didn't make a huge difference here, I should be clear. I don't like RSA, and my dislike for it comes almost entirely from something orthogonal to key sizes --- public key systems provide one or more of three primitives: direct encryption, signature verification, and key exchange; RSA provides all three, and the direct encryption primitive is a giant foot cannon. If the original commenter's point was that RSA directly harmed the 3DS in some fundamental way, that would be a legit thing to push back on, I think.
deleted 11y ago
[deleted]

That is what all cryptography is based on? And I don't know what subpolynomial time nonsense you're talking about.

by eximius 11y ago

That is what all cryptography is based on? And I don't know what subpolynomial time nonsense you're talking about.

If you're going to be rude, at least be correct. All cryptography is not in fact based on factoring; in fact, most public-key crypto isn't.

eximius 11y ago
I wasn't referring to factoring. I quite like lattice based and ECC systems. I was referring to 'if it's hard for me it must be hard for you'. ALL cryptography is based off of that assumption. edit: I can't seem to reply to you again, so I'll edit. This is all a big miscommunication. I was more confused than hostile, though I recognize how it came off poorly. I genuinely thought he had some fundamental understandings due to the combination of things he said. I was mistaken and my response came off poorly.
- tptacek 11y ago
  That's a reading of the original comment so uncharitable as to seem tendentious. The commenter was specific about factoring; they were not calling into question the entire idea of a trapdoor function.

justifier 11y ago

> subpolynomial time nonsense what exactly do you mean by this?

tptacek 11y ago
The original poster probably meant to write "sub-exponential". The commenter to whom you're responding may or may not have known what the correct term was; we'll never know, because they chose snarky incivility instead of correction.
- justifier 11y ago
  i am the original poster :p and the 'sub' was misplaced, i actually asked instead of editing the original in case this was the reason i was called out so i could explain my typo for clarification the original should simply read 'polynomial time'
  - khedoros 11y ago
    > factoring numbers is deterministically achievable in sub polynomial time Am I missing something? I thought that the whole point of using the difficulty of integer factorization as the strength of things like RSA was that it's not known to be solvable in polynomial time. "P==NP" is one of the unsolved problems of computer science. I think that the state of the art is that we can factor in sub-exponential time.
    - tptacek 11y ago
      By "things like RSA", you pretty just much mean "RSA". A lot of progress was made on integer factorization over the last 35 years, so that key sizes we'd have thought totally reasonable in 1995 are totally inadequate today. That is not similarly true of non-factoring systems, and so it's legit to point out the relative weakness of IFP crypto compared to other approaches.
      - khedoros 11y ago
        I take your point. ECC probably wouldn't cost Nintendo more to implement, but would provide a system that probably isn't being attacked as successfully, hopefully giving their system more time on the market before it's cracked.
        tptacek 11y ago
        It didn't make a huge difference here, I should be clear. I don't like RSA, and my dislike for it comes almost entirely from something orthogonal to key sizes --- public key systems provide one or more of three primitives: direct encryption, signature verification, and key exchange; RSA provides all three, and the direct encryption primitive is a giant foot cannon. If the original commenter's point was that RSA directly harmed the 3DS in some fundamental way, that would be a legit thing to push back on, I think.

deleted 11y ago

[deleted]