[3182] in cryptography@c2.net mail archive
Re: Strong PRNG with AES or 3-DES
daemon@ATHENA.MIT.EDU (Mok-Kong Shen)
Mon Aug 10 15:15:18 1998
Date: Mon, 10 Aug 1998 14:57:21 +0100
From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de>
To: Marcus Watts <mdw@umich.edu>
CC: aes@suburbia.net, coderpunks@toad.com, cryptography@c2.net
Marcus Watts wrote:
>
> Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> writes:
> >
> > I wonder whether a method that I employed in another situation of
> > pseudo-random number generation could be of some use to you. It is
> > addition of two pseudo-random real numbers streams (in my case in [0,1))
> > mod 1. Since one can't determine from the result of this addition
> > the two participating addends, it appears barely possible for
> > the analyst to determine the two input streams, thus providing
> > security. I think that if you have two bit streams you can analogously
> > take 32 bit blocks and do addition mod 2^32 (which on PC is just
> > the ordinary integer addition, the carry-over beyond the leftmost
> > bit being simply ignored). For an concrete implementation using the
> > said method and literature reference of it see
> >
> > http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper9
> >
> > I should appreciate very much to know whether my above argument
> > concerning the security provided by addtion mod 1 is o.k.
> >
> > M. K. Shen
> >
>
> Addition mod 1 is not normally considered useful. Any integer
> modulo 1 is 0, and hence has zero information content.
>
> Probably M.K.Shen meant to say "addition modulo 2", which is
> indeed a popular means of combining data in cryptography.
> Usually, it's called "xor" instead of "addition modulo 2".
> A fancier term is a Galois field -- GF(2^n), where n is
> the bit string length. Galois fields have many strange
> and wondrous properties, which makes them well suited
> for cryptography.
If you read carefully my text posted, addition mod 1 is meant only in
my case where I have real psuedo-random numbers in range [0,1).
Hopefully this dispells your surprise and makes my point clear to you
now.
>
> Addition modulo 2^32 is also a popular technique. It's
> often used because it's a somewhat more efficient bit
> mixer than xor and increases linear complexity somewhat
> faster. In effect, it's "almost" like getting a 1-bit shift
> in at the same time. SHA-1 (for instance) uses addition
> to good effect, along with some shifts.
>
> Multiplication is an even more efficient bit mixer, and several
> modern algorithms (idea, rc6) use multiplication to good effect.
> Multiplication is at its best on software implementations on modern
> high speed processors; in hardware or very old processors (Z80's)
> multiplication is not so advantageous.
Multiplication may be better but takes in general more time. Addition
mod 2^32 is in my opinion already much better than XOR. As far as
I know, this technique has not been applied before to combine
outputs from two PRNGs. I should appreciate literature to the
opposite.
>
> Incidently, on a PC (intel based, I presume), it's not quite safe to
> say that addition modulo 2^32 is the "natural" way. The original
> PC was based on the 8086, which was pretty definitely a 16-bit
> architecture. It's only with the 386 that the chip acquired
> 32-bit registers, and even after the 386 was introduced,
> it was still quite common for people to build code using 16-bit
> code models. Indeed, it wasn't until windows 95 that people
> really started moving to 32-bit programming, which makes it
> a very recent PC development.
The basic idea is independent of the length of words. If you have
64 bit (or in some future 128 bit) words, then you use 2^64 (or
2^128).
M. K. Shen
