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
>becomes
>as hard as brute-forcing a 64-bit cipher... hard, but possible.
>
>So the best way to defend against exhaustive key search in a
>quantum
>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
>the
>possibility of quantum computing and Grover's algorithm. Brute-
>forcing a 256-bit cipher with Grover's is as hard as brute-forcing
>a
>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
alteration,
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
consisted
of 10 diceware words,
and that in order to achieve passphrase security at the 128 bit
level
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)
so,
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
respectively
(whether the 1.58 or 1.59 exponents are used)
=====[end background calculations]=====
so,
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?
tia,
vedaal
--
Click to find great rates on medical insurance, save big, shop here
http://tagline.hushmail.com/fc/CAaCXv1QS4cgSbayabBZZAAdxaOeMea0/
More information about the Gnupg-users
mailing list