Quantum computing (Robert J. Hansen)

vedaal at hush.com vedaal at hush.com
Thu Apr 19 16:06:23 CEST 2007

>Message: 4
>Date: Wed, 18 Apr 2007 19:56:48 -0500
>From: "Robert J. Hansen" <rjh at sixdemonbag.org>
>Subject: Re: Quantum computing

>Brute-forcing a 128-bit cipher using a traditional  
>computer is a ridiculous proposition, but using Grover's, it 
>as hard as brute-forcing a 64-bit cipher... hard, but possible.
>So the best way to defend against exhaustive key search in a 
>world is to either (a) trust that quantum computing is going to  
>remain "in just a couple of years" for the next few decades (which 
>may very well be true), or (b) multiply your key sizes by a factor 
>of 2.
>The principal reason why AES supports a 256-bit key is because of 
>possibility of quantum computing and Grover's algorithm.  Brute- 
>forcing a 256-bit cipher with Grover's is as hard as brute-forcing 
>128-bit cipher with a conventional computer... absolutely  
>ridiculous.  :)

am not familiar with quantum physics,
but do have some math background

please confirm if i have understood your post correctly to imply
that if someone uses a straight diceware passphrase
(choosing words as they appear in the diceware list without 
so that a brute force dictionary attack using a diceware word list 
is possible) to protect a message encrypted symmetrically with a 
256 bit algorithm,
then quantum computing could crack the passphrase even if it 
of 10 diceware words,
and that in order to achieve passphrase security at the 128 bit 
a 20 word diceware passphrase would be necessary ?

=====[begin background calculations]===== 

a diceware word list has 7776 possiblities,
7776 = 6^5  (5 dicethrows, 6 possibilities each)

7776 = [(2)(3)]^5

2^(1.58) < 3 < 2^(1.59)

(2)(3) = (2)(2^[1.58]) = 2^[2.58]

(7776) = [(2)(3)]^5 = [2^(2.58)]^5 = 2^(12.9)

to find the number of diceware words that would provide equivalent 
security to a 128 or 256 bit symmetrical algorithm,
we do
(7776)^x = 2^128   and  (7776)^y = 2^256

which becomes
2^[(12.9)x] = 2^128  and  2^[(12.9)y] = 2^256

so the closest integral values for x and y are 10 and 20 
(whether the 1.58 or 1.59 exponents are used)

=====[end background calculations]=====

back to the quantum issue,

does this mean that if quantum computing ever becomes functional
to where a 128 bit symmetrical cipher is feasibly attackable,
then symmetrically encrypted messages, sda's, etc. using 10 
diceware words or less,
are similarly attackable?



Click to find great rates on medical insurance, save big, shop here

More information about the Gnupg-users mailing list