Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:57
Marcus Watts (mdw@umich.edu)
Mon, 10 Aug 98 06:28:25 -0400
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.
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.
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.
-Marcus Watts
UM ITD PD&D Umich Systems Group
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:57