[144601] in cryptography@c2.net mail archive
work factor calculation for brute-forcing crypto
daemon@ATHENA.MIT.EDU (travis+ml-cryptography@subspacefie)
Fri Jul 17 21:07:29 2009
Date: Fri, 17 Jul 2009 13:37:43 -0500
From: travis+ml-cryptography@subspacefield.org
To: cryptography@metzdowd.com
Mail-Followup-To: cryptography@metzdowd.com
--0Wg1ddIY7KV0vpwL
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
Hi folks,
Assume for a moment that we have a random number generator which is
non-uniform, and we are using it to generate a key.
What I'd like to do is characterize the work factor involved in
brute-force search of the key space, assuming that the adversary
has knowledge of the characteristics of the random number generator?
The algorithm for this is simple:
Let the array X represent the probabilities of the outcomes of the
random number generator, sorted by probability, with x[0] being the
probability of the most probable value.
Then, for a given fraction of the messages n (0 < n <=3D 1):
i =3D 0
m =3D 0
while (m + x[i]) < n:
m =3D m + x[i]
i =3D i + 1
return (i - 1) + (n - m) / (m + x[i])
This return value represents the average number of decryption attempts
required to guess the right key. If one wanted to round up, one could
just return i instead of the last expression above, because the second
term is always in (0, 1]
I'm curious if there's a way to express this calculation as a
mathematical formula, rather than an algorithm, but right now I'm just
blanking on how I could do it.
--=20
Obama Nation | My emails do not have attachments; it's a digital signature
that your mail program doesn't understand. | http://www.subspacefield.org/~=
travis/=20
If you are a spammer, please email john@subspacefield.org to get blackliste=
d.
--0Wg1ddIY7KV0vpwL
Content-Type: application/pgp-signature
Content-Disposition: inline
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (OpenBSD)
iQIcBAEBAgAGBQJKYMT3AAoJEGQVZZEDJt9HT/oQAIJjbHBBWj+tlyHsljoqEPet
iNd3FrQ6TZxpbEqQqUUfW3ejk4h5HqHNFau696FDYCu/V+hrsCLWuThYnYf/J3dQ
dzKPOmDUlDmRiq1Nawy7Ehs9DAt6kEE64gWXXYbIJe4UWOBt/+R/xsm0JRnuZu/D
vy9DPOXvNNSprNVYO3XbtwfQYmX7uHrZAjUeDwSGSzmhN0n1Fk1Odqa8RIRrl5Vc
TfkrLAdaDSk/6ja1+lMWZybGghBUIlkl22ER6vUOq64ilsYWP7HxbSbymgm1IljJ
DfUVwm0rX5bB687zT6Pr/iiynifDI35Zhx/TBInrmjczoQDqCL2u0koThquYhRGM
DdDZiQjJH2sGn33T+2N8NppS3gKeDSKHp1mMZNkOeqygH+DAyVEXMcdH9Gs/wAG9
BFEp8Rf7QfQ1ifD8Tp2mkNr0bxp2s/fGA4VeclB7OMdPJC1QDMsC+A9/+d4F+ORq
G5en9XD69FwLBeUIzFFN5nK824D4xaQuxx9aTS4WaR24lRxTsg19Bmhtq21Oq7mH
rOxovoxAZuEkbEv+l6uBEPRuIW54YMLPuQ9rmHtx4MQv3EFRdanWaGN3sHmF1+UP
nEdkLyS6J446+LU4qg8Zel48q8XPZT6ynljlNly0Ti+PKTYH2ebWBvHCPfKWOmnw
rVaHlExCRV8wWWHrbHrK
=7vsK
-----END PGP SIGNATURE-----
--0Wg1ddIY7KV0vpwL--
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
