20170622, 16:15  #23  
Sep 2009
7×311 Posts 
From the latest cryptogram (at https://www.schneier.com/cryptogram...2017/0615.html ).
Quote:
Chris 

20171102, 21:35  #24  
∂^{2}ω=0
Sep 2002
República de California
2×3×29×67 Posts 
Quote:
Google Plans to Demonstrate the Supremacy of Quantum Computing  IEEE Spectrum The nut quote for me: Quote:
But one can see how the more modest goal of cracking RSAstyle crypto fits into Google's wemustknoweverythingyoudo paradigm, as epitomized by Gmail scanning the content of every user email so that  the word "smart" here being the classic Silicon Valley bullshit tell  "its smartreply 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 onthefly decrypt such content so as to restore The Smartness is a big deal. 

20171103, 07:29  #25  
Bamboozled!
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across
2^{2}×3×11×83 Posts 
Quote:
For a start RSA is not the only public key cryptosystem. Some of the alternatives, ECC for instance, have no known subexponential attacks either on QCs. The quantum advantage to the attacker is nullified by a mere doubling of the key size. Secondly, otf 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 keyexchange protocol still need to be hardened but that is very far from impossible. 

20171105, 03:17  #26  
∂^{2}ω=0
Sep 2002
República de California
2·3·29·67 Posts 
And here I was trying to be elliptical with my snark.
Quote:
I am still somewhat agog at the estimate re. the huge numberofqubits needed to perform a 2 kilobit RSAmodulus factorization. One wonders to what extent that that number may be slashed as the technology matures, perhaps via asyetunkown decoherencecountering schemes. Last fiddled with by ewmayer on 20171105 at 03:19 

20171105, 04:16  #27  
Aug 2006
3×1,993 Posts 
Quote:
Last fiddled with by CRGreathouse on 20171105 at 04:16 

20171105, 18:32  #28 
Feb 2017
Nowhere
2^{2}·29·43 Posts 
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 P^{3} will be less than n. OTOH, you'd be able to decrypt simply by extracting the integer cube root
;D 
20171105, 19:29  #29  
Bamboozled!
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across
2^{2}·3·11·83 Posts 
Quote:
Last fiddled with by xilman on 20171105 at 19:31 Reason: fix tag 

20171105, 23:16  #30  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
14214_{8} Posts 
Quote:
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. 

20171106, 03:15  #31 
Jun 2003
19·271 Posts 

20171106, 04:42  #32 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
1100010001100_{2} Posts 

20171106, 05:31  #33  
Aug 2006
3·1,993 Posts 
Quote:
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 quantumaccelerated 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 4096bit primes; you could probably use 2^32 2048bit 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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
ElGamal crypto without prime  ElChapo  Math  9  20170610 03:26 
SHA1 Crypto Hash weakened  plandon  Lounge  0  20090616 13:55 
The news giveth, the news taketh away...  NBtarheel_33  Hardware  17  20090504 15:52 
Crypto 2007  R.D. Silverman  Lounge  2  20070808 20:24 
crypto game  MrHappy  Lounge  0  20050119 16:27 