mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Tales From the Crypt(o)

Reply
 
Thread Tools
Old 2017-06-22, 16:15   #23
chris2be8
 
chris2be8's Avatar
 
Sep 2009

7×311 Posts
Default

From the latest cryptogram (at https://www.schneier.com/crypto-gram...2017/0615.html ).
Quote:
Interesting research on a version of RSA that is secure against a quantum computer:
https://eprint.iacr.org/2017/351.pdf
The mind boggles at the key sizes proposed.

Chris
chris2be8 is offline   Reply With Quote
Old 2017-11-02, 21:35   #24
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2×3×29×67 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
From the latest cryptogram (at https://www.schneier.com/crypto-gram...2017/0615.html ).

The mind boggles at the key sizes proposed.

Chris
But note the apparently highly supralinear scaling between key length and #qubits needed, as detailed here:

Google Plans to Demonstrate the Supremacy of Quantum Computing - IEEE Spectrum

The nut quote for me:
Quote:
A system size of 49 superconducting qubits is still far away from what physicists think will be needed to perform the sorts of computations that have long motivated quantum computing research. One of those is Shor’s algorithm, a computational scheme that would enable a quantum computer to quickly factor very large numbers and thus crack one of the foundational components of modern cryptography. In a recent commentary in Nature, Martinis and colleagues estimated that a 100-million-qubit system would be needed to factor a 2,000-bit number—a not-uncommon public key length—in one day. Most of those qubits would be used to create the special quantum states that would be needed to perform the computation and to correct errors, creating a mere thousand or so stable “logical qubits” from thousands of less stable physical components, Martinis says.
The prospects of using a QC to factor the double-Mersenne MM127 were already bad enough with just one H-atom-sized element needed per bit of MM127, due to the size of a solid blob of M127 H-atom-sized computing elements ... now we need apparently exponentially-scaling additional qubits for error correction? Ouch.

But one can see how the more modest goal of cracking RSA-style crypto fits into Google's we-must-know-everything-you-do paradigm, as epitomized by Gmail scanning the content of every user e-mail so that - the word "smart" here being the classic Silicon Valley bullshit tell - "its smart-reply feature can figure out what responses to suggest". Users using encryption on their mail are clearly an unacceptable batch of Luddites willfully defeating The Smartness which the GOOG is trying to bless them with, so being able to on-the-fly decrypt such content so as to restore The Smartness is a big deal.
ewmayer is offline   Reply With Quote
Old 2017-11-03, 07:29   #25
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

22×3×11×83 Posts
Default

Quote:
Originally Posted by ewmayer View Post
But one can see how the more modest goal of cracking RSA-style crypto fits into Google's we-must-know-everything-you-do paradigm, as epitomized by Gmail scanning the content of every user e-mail so that - the word "smart" here being the classic Silicon Valley bullshit tell - "its smart-reply feature can figure out what responses to suggest". Users using encryption on their mail are clearly an unacceptable batch of Luddites willfully defeating The Smartness which the GOOG is trying to bless them with, so being able to on-the-fly decrypt such content so as to restore The Smartness is a big deal.
I recognize rhetorical bullshit hyperbole when I see it.

For a start RSA is not the only public key cryptosystem. Some of the alternatives, ECC for instance, have no known sub-exponential attacks either on QCs. The quantum advantage to the attacker is nullified by a mere doubling of the key size.

Secondly, o-t-f encryption never uses RSA in practice, rather a symmetric algorithm such as AES. Again, and as far as is known, a QC doubles the key space which can be searched. Admittedly the key-exchange protocol still need to be hardened but that is very far from impossible.
xilman is offline   Reply With Quote
Old 2017-11-05, 03:17   #26
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·3·29·67 Posts
Default

Quote:
Originally Posted by xilman View Post
I recognize rhetorical bullshit hyperbole when I see it.
And here I was trying to be elliptical with my snark.

Quote:
For a start RSA is not the only public key cryptosystem. Some of the alternatives, ECC for instance, have no known sub-exponential attacks either on QCs. The quantum advantage to the attacker is nullified by a mere doubling of the key size.

Secondly, o-t-f encryption never uses RSA in practice, rather a symmetric algorithm such as AES. Again, and as far as is known, a QC doubles the key space which can be searched. Admittedly the key-exchange protocol still need to be hardened but that is very far from impossible.
And of course with AES-style schemes side-channel attacks (e,g. via DPA) are a much bigger worry than quantum crackage, but lack the futuristic sci-fi-sounding sexiness of "the quantum".

I am still somewhat agog at the estimate re. the huge number-of-qubits needed to perform a 2 kilobit RSA-modulus factorization. One wonders to what extent that that number may be slashed as the technology matures, perhaps via as-yet-unkown decoherence-countering schemes.

Last fiddled with by ewmayer on 2017-11-05 at 03:19
ewmayer is offline   Reply With Quote
Old 2017-11-05, 04:16   #27
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by ewmayer View Post
I am still somewhat agog at the estimate re. the huge number-of-qubits needed to perform a 2 kilobit RSA-modulus factorization. One wonders to what extent that that number may be slashed as the technology matures, perhaps via as-yet-unkown decoherence-countering schemes.
I believe 2001 qubits can be achieved, at least in principle, via Kitaev recycling, see arXiv:1507.08852. But this would require exceptionally high fidelity, at least 99.9999% (even then, you'd have to re-run the calculations until the QFT worked). But Paul would probably know more.

Last fiddled with by CRGreathouse on 2017-11-05 at 04:16
CRGreathouse is offline   Reply With Quote
Old 2017-11-05, 18:32   #28
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·29·43 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
The mind boggles at the key sizes proposed.
Hmm. If the modulus n is 2^40 bytes big, and the exponent is 3, then for any plaintext P of 2^13 bytes or less, there's no need to do modular arithmetic to encrypt, since the ciphertext P3 will be less than n. OTOH, you'd be able to decrypt simply by extracting the integer cube root
;-D
Dr Sardonicus is offline   Reply With Quote
Old 2017-11-05, 19:29   #29
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

22·3·11·83 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
Hmm. If the modulus n is 2^40 bytes big, and the exponent is 3, then for any plaintext P of 2^13 bytes or less, there's no need to do modular arithmetic to encrypt, since the ciphertext P3 will be less than n. OTOH, you'd be able to decrypt simply by extracting the integer cube root
;-D
True but, and I'm sure that you are aware of this, ensuring that P is large enough is entirely trivial. 213 bytes is only 8kB and {app,pre}pending a text of 8193 copies of "WTF " to the plaintext is easy enough.

Last fiddled with by xilman on 2017-11-05 at 19:31 Reason: fix tag
xilman is offline   Reply With Quote
Old 2017-11-05, 23:16   #30
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

142148 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
Hmm. If the modulus n is 2^40 bytes big, and the exponent is 3, then for any plaintext P of 2^13 bytes or less, there's no need to do modular arithmetic to encrypt, since the ciphertext P3 will be less than n. OTOH, you'd be able to decrypt simply by extracting the integer cube root
;-D
Padding schemes have existed for a long time to cover this case (and others). Don't simply use RSA without a bit of back reading.

But a modulus of 2^43 bits requires two primes of ~2^21.5 bits, those are not so easy to find. But that isn't really the bad part. The associated D value will be of the order of 2^43 bits also, so that stage of the cypher is going to take an extremely long time to compute.
retina is online now   Reply With Quote
Old 2017-11-06, 03:15   #31
axn
 
axn's Avatar
 
Jun 2003

19·271 Posts
Default

Quote:
Originally Posted by retina View Post
But a modulus of 2^43 bits requires two primes of ~2^21.5 bits, those are not so easy to find.
sqrt(2^43) = 2^21.5

sqrt(2^43 bits) = sqrt(2^2^43) = 2^2^42 = 2^42 bits
axn is offline   Reply With Quote
Old 2017-11-06, 04:42   #32
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

11000100011002 Posts
Default

Quote:
Originally Posted by axn View Post
sqrt(2^43) = 2^21.5

sqrt(2^43 bits) = sqrt(2^2^43) = 2^2^42 = 2^42 bits
Thanks for the correction.

Just makes it even more difficult. Primes of 2^42 bits. I'm pretty sure we don't know any yet.
retina is online now   Reply With Quote
Old 2017-11-06, 05:31   #33
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by retina View Post
Just makes it even more difficult. Primes of 2^42 bits. I'm pretty sure we don't know any yet.
You don't need to make it that difficult, though. As the paper's authors suggest, you can generate lots of smaller primes rather than the standard two primes. If you were hardening against classical algorithms -- ECM and GNFS -- you'd want to choose as many primes as you could, until they became small enough that you could find one of them via ECM with about as much effort as splitting them via NFS.

Using very rough estimates -- the (assumed) asymptotics of ECM and GNFS -- you'd want ~2355 primes of ~3.7 billion bits each. OK, that's still out of reach, but not as crazy.

Of course you're not worried about classical attacks, but quantum attacks. That's why the paper suggests, rather than trading off GNFS and ECM, that you trade off their quantum equivalents: Shor's algorithm, which would factor the number in a go, and GEECM, a quantum-accelerated version of ECM. Because Shor's algorithm improves on GNFS much more than GEECM does on (E)ECM, the tradeoff goes much more sharply in the latter direction, favoring lots of primes that can be generated quickly. Their 1 TB key is composed of 2^31 4096-bit primes; you could probably use 2^32 2048-bit primes, which I think would be more in line with their asymptotics, but they preferred the greater security margin since the extra compute time was affordable.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ElGamal crypto without prime ElChapo Math 9 2017-06-10 03:26
SHA-1 Crypto Hash weakened plandon Lounge 0 2009-06-16 13:55
The news giveth, the news taketh away... NBtarheel_33 Hardware 17 2009-05-04 15:52
Crypto 2007 R.D. Silverman Lounge 2 2007-08-08 20:24
crypto game MrHappy Lounge 0 2005-01-19 16:27

All times are UTC. The time now is 11:55.


Fri Oct 22 11:55:39 UTC 2021 up 91 days, 6:24, 1 user, load averages: 1.59, 1.52, 1.36

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.