Re: We can do it! Efficient secret communications! (Another paper)

[Michael McClary <michael>]

> I'll let Michael describe his alternative to XOR, and why we need it.

Looks GREAT so far!  (One caveat:  Compromising the private key
at EITHER end makes recorded traffic readable, as with the other
non-transitive-authentication systems, such as DES.  With RSA it
only compromises traffic bound toward the compromised side.)

I agree we should research Snefru's children.  Especially if he had
a recognized child with someone outside the pharonic line.  B-)

(I'm always itchy about pseudo-random generators, because if they ever
figure out where you are in the sequence, you're screwed.  On the other
hand, if that ever becomes a concern, we could use some function of
(a^(X*Y))%M, rather than 1, for the increment, and even if they achieve
sync they're back to figuring out (a^(X*Y))%M on the next block.)

(Yes, they used one-time-pad in wars.  Real pads of paper.  Shannon
 invented information theory for the military crypto effort in WWII,
 and proved one-time-pad is really unbreakable, so the pads are as
 strong as the random generator and the key distribution path, and
 perfect if true random noise used once and destroyed.)

Why straight XOR one-time-pad isn't enough:  If the bad guy can intercept
and modify your transmission, and he knows what your are about to send,
he can solve for your chunk of one-time-pad, and use that to replace
the message with his bogus message.

The GLOPS variant of one-time-pad:

(I don't have the paper handy, so I'll just sketch it... and
undobutedly use different letters than I used on the paper.)

GLOPS is a small-block cypher.  In this description, I'll use
bytes (8-bit blocks), but the blocks can be any size, with the
probabilities scaling accordingly.

Rather than using one byte of one-time-pad to encrypt one byte
of plaintext (via add or XOR), you use two bytes, and combine
them with the plaintext using a system of arithmetic called a
"gallois field".  (Pronounced gah-WAH)

A gallois field is any of a set of finite fields constructed
from polynomial arithmetic as follows:

	- Numbers are sets of integer coefficients for a
	  polynomial of degree N-1.

	- The coefficients range from zero to one less than
	  some prime P.

	- Addition is polynomial addition, with the coefficients
	  taken modulus P.

	- Multiplication is polynomial multiplication, with the
	  coefficients taken modulus P and the entire polynomial
	  taken modulus an irreducable polynomial I, which is of
	  order N.

It can be shown that, for any combination of P and N>0, there exists
at least one irreducable polynomial I on which a gallois field can
be constructed.  Since the numbers in a gallois field are ordered
N-tuples of integers from zero to P-1, and 2 is prime, at least one
gallois field exists which exactly represents a binary word of any
given number of bits.

In a gallois field with P=2, addition and subtraction are XOR.  Polynomial
multiplication and division with coefficients modulus 2 are accomplished
by XOR-and-shift operations analogous to the add/subtract-and-shift
operations used for integer multiply and divide (think of it as binary
arithmetic with the carry bits lost), and the two can be combined in a
single loop.  Thus the gallois P=2 multiply is roughly:

	MASK = 1<<N;	/* In this case, N=8 */
	k = multiplier;

	m = multiplicand;
	a = 0;
	for (j = N; --j > 0; {
		if ((a <<= 1) & MASK) {
			a ^= I;
		}
	}) {
		if ((m <<= 1) & MASK) {
			a ^= k;
		}
	}
	/* Result in a */

This is quite fast.  (For 8 bits, though, you might just want to use
a table, which would only be 64K long.)

Divide is most easily accomplished by multiplying by an entry from
a pre-computed table of multiplicative inverses.  Similarly, since
you only need one I for all time, you can find it in a few sec of
brute-force search.

Because gallois fields are FIELDS, all the interesting field properties
(additive inverses, a zero, multiplicative inverses {except for the zero},
a one, commutativity, distributivity) apply.  (Note that boolean logic is
just the gallois field with P=2, N=1.)

Now, to encrypt:

	+ = gallois(P=2,N=8) addition       (i.e. bitwise XOR)
	- = gallois(P=2,N=8) subtraction    (i.e. bitwise XOR)
	* = gallois(P=2,N=8) multiplication (see above)
	/ = gallois(P=2,N=8) division       (from precomputed inverse table)

	Let T0 = First byte of your plaintext.

	Let K0 = the first byte from your one-time pad.  (If it is zero,
		 discard it and take the next byte, etc., until you get
		 a byte that is not zero).

	Let K1 = the next byte from your one-time pad.  (Zero is OK.)

	Calculate C0 = (T0 * K0) + K1.  This is your cyphertext.

Discard the "used" one-time-pad bytes and repeat as necessary.

To decrypt:

	Calculate T0 = (C0 - K1) * inverse(K0).

Because gallois arithmetic is a field, for any Tb != T0 Cb != C0,
there exists exactly one combination of K0 { = (C0 - Cb) / (T0 - Tb)}
and K1 { = (Cb*T0 - C0*Tb) / (T0 - Tb)} such that:

	C0 = (T0 * K0) + K1 and  Cb = (Tb * K0) + K1.

This means that the bad guy has the following choice:  He can leave
the byte unmodified, or he can substitute a bogus cyphertext byte (Cb)
that corresponds to a random selection (Mb) among the other possible
values for the message byte.  He is thus reduced to a malicious noise
generator.  (The best he can do is chose the worst spot to inject his
noise.)  His knowlege that K0 != 0 corresponds exactly to his knowlege
that he can leave the message unmodified.

Using 8-bit blocks, you can encrypt single keystrokes.  The bad guy's
chance of making a desired change in one of them is 1/255, in two of
them is 1/(255**2), and so on.

	michael
s