An Extremely Simple Public Key Exchange

From: Jim Steuert (pjsteuert_at_rcn.com)
Date: 05/31/03 

Date: Fri, 30 May 2003 19:42:06 -0400

Has anyone seen the following algorithm?

Consider the following 6-bit operations:

Pa1: add 1.1.011.0
Pb1: add 1.0.101.1

Pa2: add 10.1111
Pb2: add 11.0010

Pa3: add 000110
Pb3: add 101111

Where the . separates bit fields and addition is modulo 2^k for
that bit field, with no carries between different bit fields.

Now consider the permutations Pai induced by adding
with those bit fields. Each addition's constant is a
separate hash of Alice's secret key Pai = hashi(A),
and Bob's is Pbi = hashi(B).

For example:

BShared = BInv(APub(x))
        = Pb1( Pb2( Pb3( Pa3( Pa2( Pa1( x ))))))

AShared = AInv(BPub(x))
        = Pa1( Pa2( Pa3( Pb3( Pb2( Pb1( x ))))))

To compute AShared:
first start with x = 100101
then do:
Pb1: add 1.0.101.1 => 0.0.111.0
Pb2: add 11.0010 ==> 11.0000
Pb3: add 101111 ==> 011111
Pa3: add 000110 ==> 100101
Pa2: add 10.1111 ==> 00.0100
Pa1: add 1.1.011.0 ==> 1.1.101.0
       = =========
            1.1.101.0

To compute BShared:
 first start with x = 100101
then do:
Pa1: add 1.1.011.0 ==> 0.1.101.1
Pa2: add 10.1111 ==> 11.1010
Pa3: add 000110 ==> 000000
Pb3: add 101111 ==> 101111
Pb2: add 11.0010 ==> 01.0001
Pb1: add 1.0.101.1 ==> 1.1.101.0
       = =========
            1.1.101.0
          Pb1 and Pa1 commute because there
are no included smaller bitfields between
those two additions:

These expressions cannot in general be simplified into the
addition of a single 6-bit constant.

Thus x is used at it's smallest bit-field division value.

It is difficult to "subtract out" the common value x,
because of the parity induced by the multiple
inner bit-field additions, which are dependent on other
of x's values. Inner addition carries are suppressed
by their bit-field boundaries, which affects other
subsequent stages. So the parities induced by x
are dependent on the multiple inner levels of
bit fields.

It is important the the finest level of bit fields
not be too fine, that is, there should be as many
say, 16-bit fields as possible, in order to create
dependencies among the input (x) bits as well.

In practice, this will require more (>>100)
stages of hash-parameter addition. And instead
of 6 bits, 1024 bits at least, with many bit fields
of width from 16 to 1024 bits at
various stages.

 -Jim Steuert