aglew@ccvaxa.UUCP (01/28/86)
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.godman@uiucdcs.CS.UIUC.EDU (01/29/86)
This seems to me to be very similar to the RSA public-key cryptosystem proposed by Rivest, Shamir, and Adleman (thus, the name: RSA). I believe the paper was published in early 1978 in the J of the ACM.
aglew@ccvaxa.UUCP (01/29/86)
Similar to, but not the same as (if that was the paper passed out in my course and "Cryptography and Data Security"). Certainly not the same as the RSA scheme as described in Denning. 4 keys per user, not 2.
wiebren@botter.UUCP (02/03/86)
You seem to be a 'victim' of the fact that most people present the subject of secrecy and of authenticity (too much) intertwined. This is caused by the fact that RSA can be used for secrecy as well as for authenticity at the same time, since for RSA E.D=D.E=I. (E.g., note that the secret deciphering transformation for the 'secrecy application' is often denoted by D, but this bad identifier makes that the same D denotes the secret encyphering (!) transformation to be used for the 'authenticity application'.) Since the RSA algorithm is a (resp., the most) well-known, famous, secure, elegant, etc. public-key algorithm, it is (almost) always used to illustrate the possibility of achieving authenticity as well as secrecy. And thus in examples you will find only two keys. However, any cryptographer is (should be) aware of the fact that a public-key system not having the commutative property E.D=D.E (but giving the choice to keep either the E or the D transformation secret) still may be used for secrecy or authenticity, and that both properties then can be achieved by using four keys instead of two. In short, your idea of using four keys is OK, but contains no new elements.
aglew@ccvaxa.UUCP (02/06/86)
Thanks for reassuring me that I'm not totally at sea about this. If I was a victim of the mixup of security and authenticity about this, I'm certainly not the only one, as evidenced by the correspondence I received. Have you any references to where the proper distinction between authenticity and secrecy is made? I would have asked you by mail, except your return path did not get to me. Is there any possibility of truth to my suspicion that the less severe constraints on the "authenticity" transformations might make it easier to find reliable ones?