NetNews Usenet Archive 1993 #1/NN_1993_1.iso/spool/sci/crypt/6505

Text File | 1993-01-07 | 4.0 KB | 102 lines

Newsgroups: sci.crypt
Path: sparky!uunet!walter!thumper!milton
From: milton@thumper..bellcore.com (Milton Anderson)
Subject: simple crypto algorithm descriptions
Message-ID: <[e-mail]>
Sender: [e-mail]
Nntp-Posting-Host: thumper.bellcore.com
Reply-To: [e-mail] (Milton Anderson)
Organization: Bellcore MRE
Date: Thu, 7 Jan 93 23:49:10 GMT
Lines: 89

To provoke some technical discussion, an interesting question
might be -- What is the simplest effective cryptological algorithm,
i.e. the one that can be described using the fewest high-level
programming language operators?

In order to make the algorithm simple to describe, we can
trade off some other characteristics, e.g.:
    - key length (anything under 10kB is OK, given current
      media densities),
    - executable size (up to a few MBs),
    - execution speed (up to about 10 k instructions per
      byte on a 100 MIPS processor is OK)

As an illustrative example, consider the following description
using C-language operators.

First define:
1    union { double f[63]   int i[127]   } x
2    int j, k
3    int m, mp, c, r

Then for each bit of the message:
4        x.i[k] = x.i[k] ^ (mp << 31)
5        x.i[k] = x.i[k] ^ (r  << 15)
6        x.f[j] = 4.0 * x.f[j] * ( 1.0 - x.f[j] )
7              c = m ^ ((x.i[k] >> 23) & 1)
8        mp = m
9         r = (x.i[k] >> 19) & 1
10        j = (x.i[k] >> 15) & 0x3f
11        k = j * 2 + 1

To decrypt each bit of the message replace (8) by:
8              m = c ^ ((x.i[k] >> 23 ) & 1)


The key is the 64 initial values of the floating point
variables x.f defined in (1).  Initially j, mp and r are
zero, and k is one, although they could be used as key bits.
For each bit encrypted, one of the ensemble of 64 chaotic systems is
iterated once in (6).  The 24th lsb of the mantissa is extracted
from the state variable and used in a Vernam cipher in (7)
where the crypto bit c is computed from the message bit m.
The message bit m is saved as mp in (8) and used in (4) for
message feedback in the next iteration to ensure that the
pseudorandom bits used in the Vernam cipher depend on the
message content.  A pseudorandom bit r is extracted in (9) and
then used in (5) to provide coupling between the chaotic
systems, which are iterated in a psuedorandom order according
to (10) and (11).

Beware the endianness of your machine; the above is for a Sun,
and you may need to make (11) k = j * 2 instead.  Also note
that different fpus give different results -- the limit cycle
of one system is about 5 M iterations on a Sun 4 and about 15
M on a PC with 287.  How your system initializes the fpu control word
for round-off may also matter.  Therefore this algorithm would
be mostly useful for keeping your private files private -- or
between machines with compatible hardware.

Note that a rather large family of algorithms can be
constructed by varying the bit position and functional form of
the message perturbation, the coupling perturbation and the
sequence calculation.  For more variety use:
6        x.f[j] = g[j] * x.f[j] * ( 1.0 - x.f[j] )
7        while (x.f[j] > 1.0)  x.f[j] -= 1.0
where g[] is an array of floating point numbers in the
interval (0.0, 8.0].  The number of chaotic systems may be
adjusted as well, and if the dimension of the arrays requires,
the x.f[] and g[] may be initialized by use of a function of
fewer variables.  E.g. the x.f could be calculated using a
sine function of a key consisting of amplitude, initial phase
and phase increment.

If anyone has a R4000 or Alpha, I'd appreciate knowing the
limit cycle and execution speed of the assembly language equivalent of:
    x = (x * (x ^ 0xffffffffffffffff)) >> 61
i.e. the radix-63 implementation of the chaotic system using
64-bit integers with a 128-bit product.  I'm assuming the
C-compiler won't handle this yet?  But when it does then
fixed-point implementations which are compatible between
differing machines would be simple as well.

The use of chaotic systems as PRNGs has been described in
Cryptologia.

Milton Anderson
[e-mail]