🚀 go-pugleaf

In article <1992Nov11.173642.29608@ee.eng.ohio-state.edu> butzerd@columbia.eng.ohio-state.edu (Dane C. Butzer) writes:
>  "Random number generators" are
>  frequently dreamed up by newcomers as a "pseudo one time pad",
>  but they are notoriously vulnerable to analysis, all
>               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>  independent of whether the pseudo-random stream satisfies
>  randomness tests or not.
>
	[example of DES as a PRNG]

>This is pseudo one time pad that I don't think would be "easy" to break.
>Now, how about substituting some other type of PRNG for DES?  If its
>non-predictive (can't determine numbers in the stream from other numbers)
>and statistically random, whouldn't it work?  Is the real problem coming up
>with a "good" enough PRNG?

Of course, if you use a cryptographically strong PRNG, it's as good as a
1-time-pad.  That's the definition of cryptographic strength -- that the
PRNG is indistinguishable by any polynomial time&space test from true
random numbers.

The FAQ was warning against use of standard, canned PRNGs (e.g.,

	x' = a*x+b mod N

) as the generator.

BTW, Ron Rivest published a secure PRNG method in an early Cryptologia.  As
I remember it, he used

	x' = x^2 mod N

taking one bit from each iteration.  If you know x at any time, you can go
forward trivially -- but because sqrt() is multi-valued, you can't go
backwards.  So, he then used TWO such bit streams -- one forward through
the message and one backward.  He XORed the message text with both streams.

[I assume you have to use large numbers N and x0 -- to avoid finally getting
to the value x=1 and having the generator be no good any more.]

-- 
-- <<Disclaimer: All opinions expressed are my own, of course.>>
-- Carl Ellison						cme@sw.stratus.com
-- Stratus Computer Inc.	M3-2-BKW		TEL: (508)460-2783
-- 55 Fairbanks Boulevard ; Marlborough MA 01752-1298	FAX: (508)624-7488