5 ms·

i suppose a handheld gaming device could be considered low consequence on the spectra of encryption use, which may simply answer my own question.. but being so

i suppose a handheld gaming device could be considered low consequence on the spectra of encryption use, which may simply answer my own question.. but being someone interested in factorisation i am baffled as to why anyone has or is using rsa my intended inference is that factoring numbers is deterministically achievable in sub polynomial time, and having your crypto rely on 'it's hard for me it must be impossible for you' reads so sophomoric

eximius 11y ago
That is what all cryptography is based on? And I don't know what subpolynomial time nonsense you're talking about.
- 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
- deleted 11y ago
  [deleted]
tptacek 11y ago
The 3DS is higher stakes than virtually any other cryptosystem. Nintendo spends billions bringing it to market. Game consoles live or die based on third party developer support, and one of the important promises console developers make to entice developers to their platforms is that they will carefully steward those developers IP. What's more interesting to me is that the 3DS system is nonrenewable. As the author of this post correctly points out, all DRM systems inevitably fall, but they accomplish their commercial purpose as long as that fall happens far enough into the future that the developers make their money. Smart systems trying to employ DRM this way build, from the beginning, mechanisms to refresh and re-complicate their DRM systems on a title-by-title basis. I actually agree with you "in the large" about RSA (factoring doesn't seem like a hard enough problem anymore), but in the particulars, nobody is breaking RSA-2048 any time soon. Unlike strong curves, though, it seems plausible that RSA-2048 (and beyond) could fall before quantum computing.
yifanlu 11y ago
First, the 3DS mostly uses RSA for code signing, something I didn't really touch on since there's no serious mistakes there. Second, while RSA does not fair well against quantum attacks, as of today, there is still no way of factoring a 2048 bit key that won't take you at least (being generous) hundreds of years (provided no quantum computers). So if you have proof that it's (today) achievable in polynomial time, please email me ;) But turning the question around, what do you think we should do to achieve asymmetric encryption? If you don't want it to break with Shor, then RSA and ECDSA are off the table. If you want small message size, you can't use Lamport.
- justifier 11y ago
  if i had that proof an email would be unnecessary, you'd already know :p to address your question i'll say this, crypto is only interesting to me in securing my own work and because my interests are in number theory that, due to rsa popularity, would incidentally affect crypto i lack an intimate familiarity with the optimisation requirements of rolling production crypto, meaning i can comfortably ignore any message size restraints for my personal uses instead of implying i know how crypto should be enacted.. with my current knowledge and interest i would be wholly unable to deduce as you did in your article.. i was simply stating that i am interested in factoring large integers and i wonder why anyone thinks open problems in number theory are a sound means of crypto superb write up by the way
  - yifanlu 11y ago
    > i wonder why anyone thinks open problems in number theory are a sound means of crypto The short answer is that the numbers are so large that with current state of the art means (which I'm sure you know a lot about), factoring a 2048 bit number takes around 1000 years and 4096 bit keys takes about 2^32 times more years. Even if computers get faster every 10 years, you can see that it won't improve much. That's why we use number factoring for crypto; because it takes so long to break. However, as you've pointed out, since the problems are open, the calculations are meaningless. And of course all this analysis goes out the window with quantum computers. But the unfortunate truth (the "biggest embarrassment of computer science" as Dan Boneh calls it) is that we don't actually have any proof that security exists. All crypto is built on open problems. So better choose open problems that's been open for a long time.

eximius 11y ago

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

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
deleted 11y ago
[deleted]

tptacek 11y ago

The 3DS is higher stakes than virtually any other cryptosystem. Nintendo spends billions bringing it to market. Game consoles live or die based on third party developer support, and one of the important promises console developers make to entice developers to their platforms is that they will carefully steward those developers IP. What's more interesting to me is that the 3DS system is nonrenewable. As the author of this post correctly points out, all DRM systems inevitably fall, but they accomplish their commercial purpose as long as that fall happens far enough into the future that the developers make their money. Smart systems trying to employ DRM this way build, from the beginning, mechanisms to refresh and re-complicate their DRM systems on a title-by-title basis. I actually agree with you "in the large" about RSA (factoring doesn't seem like a hard enough problem anymore), but in the particulars, nobody is breaking RSA-2048 any time soon. Unlike strong curves, though, it seems plausible that RSA-2048 (and beyond) could fall before quantum computing.

yifanlu 11y ago

First, the 3DS mostly uses RSA for code signing, something I didn't really touch on since there's no serious mistakes there. Second, while RSA does not fair well against quantum attacks, as of today, there is still no way of factoring a 2048 bit key that won't take you at least (being generous) hundreds of years (provided no quantum computers). So if you have proof that it's (today) achievable in polynomial time, please email me ;) But turning the question around, what do you think we should do to achieve asymmetric encryption? If you don't want it to break with Shor, then RSA and ECDSA are off the table. If you want small message size, you can't use Lamport.

justifier 11y ago
if i had that proof an email would be unnecessary, you'd already know :p to address your question i'll say this, crypto is only interesting to me in securing my own work and because my interests are in number theory that, due to rsa popularity, would incidentally affect crypto i lack an intimate familiarity with the optimisation requirements of rolling production crypto, meaning i can comfortably ignore any message size restraints for my personal uses instead of implying i know how crypto should be enacted.. with my current knowledge and interest i would be wholly unable to deduce as you did in your article.. i was simply stating that i am interested in factoring large integers and i wonder why anyone thinks open problems in number theory are a sound means of crypto superb write up by the way
- yifanlu 11y ago
  > i wonder why anyone thinks open problems in number theory are a sound means of crypto The short answer is that the numbers are so large that with current state of the art means (which I'm sure you know a lot about), factoring a 2048 bit number takes around 1000 years and 4096 bit keys takes about 2^32 times more years. Even if computers get faster every 10 years, you can see that it won't improve much. That's why we use number factoring for crypto; because it takes so long to break. However, as you've pointed out, since the problems are open, the calculations are meaningless. And of course all this analysis goes out the window with quantum computers. But the unfortunate truth (the "biggest embarrassment of computer science" as Dan Boneh calls it) is that we don't actually have any proof that security exists. All crypto is built on open problems. So better choose open problems that's been open for a long time.