[21471] in cryptography@c2.net mail archive
Re: pipad, was Re: bounded storage model - why is R organized as
daemon@ATHENA.MIT.EDU (leichter_jerrold@emc.com)
Tue Mar 21 10:12:48 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: leichter_jerrold@emc.com
To: solinym@gmail.com
Cc: alex@alten.org, cryptography@metzdowd.com
Date: Tue, 21 Mar 2006 09:58:43 -0500
| Anyone see a reason why the digits of Pi wouldn't form an excellent
| public large (infinite, actually) string of "random" bits?
|
| There's even an efficient digit-extraction (a/k/a "random access to
| fractional bits") formula, conveniently base 16:
| http://mathworld.wolfram.com/BBPFormula.html
|
| I dub this "pi pad".
The issue would be: Are there any dependencies amoung the bits of
pi that would make it easier to predict where an XOR of n streams of
bits taken from different positions actually come from - or, more
weakly, to predict subsequent bits.
I doubt anyone knows. What would worry me is exactly the existence
of the algorithm that would make this approach workable: A way to
compute the i'th digit of pi without computing all the earlier ones.
As a starter problem, how about a simpler version: Take n=1! That
is, the key is simply a starting position in pi - taken from a
suitably large set, say the first 2^256 bits of pi - and we use
as our one-time pad the bits of pi starting from there. An
attackers problem now turns into: Given a sequence of k successive
bits of pi taken from among the first 2^256 bits, can you do better
than chance in predicting the k+1'st bit? The obvious approach of
searching through pi for matches doesn't look fruitful, but perhaps
we can do better. Note that if pi *isn't* normal to base 2 - and
we still don't know if it is - this starter problem is soluable.
BTW, Bailey and Crandall's work - which led to this discussion -
ties the question of normality to questions about chaotic
sequences. If the approach of using pi as a one-time pad
works, then all the systems based on chaotic generators
will suddenly deserve a closer look! (Many fail for much
simpler reasons than relying on such a generator, but some
are untrustworthy not because we don't know of an attack
but because we have no clue how to tell if there is one.)
| Is this idea transcendental or irrational?
Mathematician's insult: You're transcendental (dense and totally
irrational).
-- Jerry
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
