3 ms·

"Seriously, stop using RSA" https://news.ycombinator.com/item?id=30879442 https://news.ycombinator.com/item?id=30879442

bvrmn 2y ago
It's hilarious foil-hat level shit here: https://blog.trailofbits.com/2019/07/08/fuck-rsa/#comment-91809 https://blog.trailofbits.com/2019/07/08/fuck-rsa/#comment-91...
- ivlad 2y ago
  He is not wrong on the main claim, which is “All ECC (X25519-P521) will be broken by private sector quantum chips before RSA-2048 due to the physical limitations of stabilizing qubits.” Shor’s algorithm is polynomial, however the number of qubits required is in order of O(log(n)^2), where n is the length of the key. Because ECC keys are much shorter (e.g., 256 to 521 bits) than RSA (2048 to 4096 bits), a smaller quantum computer would be needed to attack ECC.
  - genewitch 2y ago
    This is the first time in nearly 30 years I've ever heard the claim that you only need 18-20 qubits for something like a 256 bit key. I've only ever seen the claims of 1:1 key bit to qubits. Aren't there existing claimed quantum computers with 20 qubits? Isn't Canada's machine an order of magnitude more qubits?
    - red_admiral 2y ago
      I think it matters not only how many qubits you have, but how they are "connected". As far as I know, it's a far easier problem to put N qubits in a chain with O(N) connections, than it is to have N qubits with O(N^2) connections to form a complete graph. And I believe the second example is what you need to do Shor's algorithm.
    - ivlad 2y ago
      I am sorry, I should’ve read it twice before posting. I meant, QC to attack longer keys should be bigger proportionally. Number of operations is logarithmic. Silly me.
  - red_admiral 2y ago
    RSA needs 4k (or 16k) keys because, with index calculus, these sizes reduce to a subproblem where you effectively need only 2^128 (or 2^256) time rather than the 2^{4k} for brute-force. I think, but I may be misremembering, that you could apply Shor's algorithm to speed up index calculus by going for the subproblem directly? In this case RSA would fall too. I note that the NSA recommendations are "move to post-quantum crypto", not "go back to RSA" so I infer that they think RSA-4096 might still be vulnerable.
    - ivlad 2y ago
      I am not NSA, but I think their idea is something along the “once Shor’s algorithm is practical for key sizes of hundreds of bits, it’s only a matter of a few years of engineering effort to make it feasible for thousands bits long keys”. In other words, there is no sufficient safety margin for larger keys.
  - tptacek 2y ago
    This is deeply silly.
    - ivlad 2y ago
      … because? Edit: yes, I read it and it is.
  - less_less 2y ago
    I'm not sure this is true anymore. There are recent improvements in quantum factoring algorithms, which significantly reduce the number of qubits required. See eg https://eprint.iacr.org/2024/222 https://eprint.iacr.org/2024/222
upofadown 2y ago
My comments on that article: https://articles.59.ca/doku.php?id=pgpfan:rsabad https://articles.59.ca/doku.php?id=pgpfan:rsabad

It's hilarious foil-hat level shit here: https://blog.trailofbits.com/2019/07/08/fuck-rsa/#comment-91809 https://blog.trailofbits.com/2019/07/08/fuck-rsa/#comment-91...

ivlad 2y ago
He is not wrong on the main claim, which is “All ECC (X25519-P521) will be broken by private sector quantum chips before RSA-2048 due to the physical limitations of stabilizing qubits.” Shor’s algorithm is polynomial, however the number of qubits required is in order of O(log(n)^2), where n is the length of the key. Because ECC keys are much shorter (e.g., 256 to 521 bits) than RSA (2048 to 4096 bits), a smaller quantum computer would be needed to attack ECC.
- genewitch 2y ago
  This is the first time in nearly 30 years I've ever heard the claim that you only need 18-20 qubits for something like a 256 bit key. I've only ever seen the claims of 1:1 key bit to qubits. Aren't there existing claimed quantum computers with 20 qubits? Isn't Canada's machine an order of magnitude more qubits?
  - red_admiral 2y ago
    I think it matters not only how many qubits you have, but how they are "connected". As far as I know, it's a far easier problem to put N qubits in a chain with O(N) connections, than it is to have N qubits with O(N^2) connections to form a complete graph. And I believe the second example is what you need to do Shor's algorithm.
  - ivlad 2y ago
    I am sorry, I should’ve read it twice before posting. I meant, QC to attack longer keys should be bigger proportionally. Number of operations is logarithmic. Silly me.
- red_admiral 2y ago
  RSA needs 4k (or 16k) keys because, with index calculus, these sizes reduce to a subproblem where you effectively need only 2^128 (or 2^256) time rather than the 2^{4k} for brute-force. I think, but I may be misremembering, that you could apply Shor's algorithm to speed up index calculus by going for the subproblem directly? In this case RSA would fall too. I note that the NSA recommendations are "move to post-quantum crypto", not "go back to RSA" so I infer that they think RSA-4096 might still be vulnerable.
  - ivlad 2y ago
    I am not NSA, but I think their idea is something along the “once Shor’s algorithm is practical for key sizes of hundreds of bits, it’s only a matter of a few years of engineering effort to make it feasible for thousands bits long keys”. In other words, there is no sufficient safety margin for larger keys.
- tptacek 2y ago
  This is deeply silly.
  - ivlad 2y ago
    … because? Edit: yes, I read it and it is.
- less_less 2y ago
  I'm not sure this is true anymore. There are recent improvements in quantum factoring algorithms, which significantly reduce the number of qubits required. See eg https://eprint.iacr.org/2024/222 https://eprint.iacr.org/2024/222

upofadown 2y ago

My comments on that article: https://articles.59.ca/doku.php?id=pgpfan:rsabad https://articles.59.ca/doku.php?id=pgpfan:rsabad