Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: Notesfiles $Revision: 1.7.0.10 $; site ccvaxa
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxn!ihnp4!inuxc!pur-ee!uiucdcs!ccvaxa!aglew
From: aglew@ccvaxa.UUCP
Newsgroups: net.crypt
Subject: Four key public cryptography?
Message-ID: <12900001@ccvaxa>
Date: Mon, 27-Jan-86 19:42:00 EST
Article-I.D.: ccvaxa.12900001
Posted: Mon Jan 27 19:42:00 1986
Date-Received: Thu, 30-Jan-86 00:38:18 EST
Lines: 82
Nf-ID: #N:ccvaxa:12900001:000:2768
Nf-From: ccvaxa.UUCP!aglew    Jan 27 18:42:00 1986






Can anybody tell me what is wrong with the following?  I came up with this
in a course on Cryptography and Data Security - the professor couldn't see
anything wrong with it, just said it wasn't done that way. It has the
advantage of making encryption functions a bit easier to find.

==========================================
Public Key Cryptography - The 4 Key System
==========================================

To send a message from A to B with no addressing info on the outside, and an
origin address on the inside:

A:  message m
    apply encoding EA
    label "from A"
    apply encoding EB
    
    coded message c on the public channel

    apply decoding DB
    determine sender
    apply decoding DA
B:  decoded message m

The decodes are the left inverses of the corresponding encode, ie.
DB(EB(m))=m, or DB.EB=I, or DB=EB**-L. Not that they are not necessarily the
right inverses.

If the decoding transformations can be applied in real-time B decodes
everything on the public channel and then applies another decode based on
valid addressing information on the front of the inner envelope.

This generalizes quite easily to two way communication, requiring each side
to have both a public and a private set of encodes and decodes:

From A to B:
A:  mAB
    apply EprA
    label "from A"
    apply EpuB

Channel:
    cAB

    apply DprB
    determine sender
    apply DpuA
B:  mAB

The reverse transmission from B to A is symmetric with Bs and As
interchanged.

Note that this has FOUR transformations for each user. A's public decoding
transformation is the inverse of A's private encoding transformation, and so
on:
    DpuA.EprA=I			    DprA.EpuA=I

Of course, parametrizing the transformations gives us FOUR keys,
    KEprA   KDpuA		    KEpuA   KDprA
Which, with the "public" coding transformations, have the properties
    D(KDpuA).E(KEprA)=I		    D(KDprA).E(KEpuA)=I

We have FOUR keys. Most public key algorithms only require TWO, a public and
a private key. These algorithms are a special case of the FOUR key sytem,
with identical encoding and decoding transforamtions, and KEprA=KDprA.

Why bother with FOUR keys? Well, it imposes much less stringent restrictions
on the well-known encoding/decoding algorithm: all you have to have is left
inverses, not left AND right inverses. Ie. for the TWO key system your
coding algorithm needs to satisfy
    T(KprA).T(KpuA)=I	    AND	    T(KpuA).T(KprA)=I
but for the FOUR key system you have weaker constraints.
    D(KDpuA).E(KEprA)=I		    D(KDprA).E(KEpuA)=I
The weaker constraints should make it (1) easier to find public key
encryption algorithms, (2) for which there is either a larger set of
possible keys, or for which it is easier to find public/private key pairs
==> increased security.