Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!mips!decwrl!deccrl!bloom-beacon!eru!hagbard!sunic!mcsun!ukc!axion!cam-cl!news
From: nbvs@cl.cam.ac.uk (Nicko van Someren)
Newsgroups: comp.compression
Subject: Re: public key encryption
Message-ID: <1991Apr2.093400.27382@cl.cam.ac.uk>
Date: 2 Apr 91 09:34:00 GMT
References: <SCHULTZ.91Mar28145545@halley.est.3m.com> <5119@ns-mx.uiowa.edu>
Reply-To: nbvs@cl.cam.ac.uk (Nicko van Someren)
Organization: U of Cambridge Comp Lab, UK
Lines: 43
X-and-bacon: yum yum

One method of digital signatures using a PKC system I have used runs along
these lines:

In most PKC systems you have a public key K and a private key P (and usually
some modulo number M).  You encrypt the plain text D with some function

f(D, K, M) -> D'

and you get the plain text back from the coded text by either the same of
a very similar function

f(D', P, M) -> D

The idea is that everyone should know all the K values for every one but only
know their own P.  So consider

f( f(D, P1, M1), K2, M2) -> D''

the inverse is

f( f(D'', P2, M2), K1, M1) -> D

If I the sender know P1 (my private key) K1 and K2, and you know P2 (your
private key), K1 and K2 then clearly I can encrypt the data and you can
decrypt it, but if I am the only one who knows P1, which I must be if the
system is at all secure, then I am the only person who could have sent the
data as I an the only person who has the inverse to K1.

In the system I used, based on an artical in Scientific American from Aug. 78
M is the product of two primes X and Y, K is more or less random and P is the
modulo inverse of K wrt (X-1)(Y-1) (K is not true random since it must not
have any factors in common with X-1 or Y-1).  The function f is

f(D, K, M) = (D^K) mod M

I hope this is of some use.

By the way, why is this in comp.compression?  Just asking...

Nicko
+-----------------------------------------------------------------------------+
| Nicko van Someren, nbvs@cl.cam.ac.uk, (44) 223 358707 or (44) 860 498903    |
+-----------------------------------------------------------------------------+