This file is README from rpem.tar.Z
Available from dcssparc.cl.msu.edu  (35.8.1.6).

See also:
  INSTALL for installation details.
  THEORY  for cryptographic discussion of the algorithm used here.


WHAT WE HAVE HERE

This distribution makes available a (nearly) public-domain public key
encryption system.  Included are functions implementing the algorithm,
functions implementing related capabilities (including a DES
implementation for recipients in the USA), and a program, rpem, that
implements a simple Privacy Enhanced Mail system.

The principal applications provided are:

  rpem -- program to encrypt a file into an encapsulated, printable
    form suitable for inclusion into a mail message.  The program
    is somewhat compatible with RFC 1113.  (I couldn't make it
    completely compatible because I am not using RSA or RSA-style
    certificates.)

  makerkey -- program to create public keys (both public and private
    components) for use with rpem.

There are also some miscellaneous applications thrown in for your
interest.

The main point behind all the work done here is to provide a free
alternative to the RSA (Rivest/Shamir/Adleman) public key
cryptosystem.  The public key algorithm used is due to Michael Rabin.
In Rabin's system, ciphertext = plaintext^2 mod pq  (p, q prime).
RSA has some technical advantages over Rabin's system; amoung other
things, it lends itself better to authentication.  However, the RSA
algorithm is (essentially) patented, whereas Rabin's technique is in
the public domain.  On the other hand, Rabin's technique, as implemented
here, is rather slow.

The "rpem" application was somewhat of an afterthought and was
originally intended only as a demo of how the basic encryption 
technology might be used.  However, rpem or some enhanced version
of it might be useful in its own right.

For those wanting to make their own public key system from the code
here, see the routines in the file "cippkg.c".  The functions
RabinEncipherBuf and RabinDecipherBuf do much of the work for you.
Amoung other things, these routines take care of the details of
converting the messages from ordinary byte format to large integer
format and back again.  (The Rabin algorithm, like most public key
systems, is typically expressed in terms of arithmetic operations on
large integers.  Of course, most messages consist of bytes, not large
integers, so someone has to do the conversion.  Also, long messages
must be broken into multiple large integers prior to encryption.)

The package as put on FTP servers does not include the DES code
because it might be subject to export restrictions.  See me to get
the code, or plug in your own DES.


CREDITS, AND TERMS OF DISTRIBUTION

This package reflects the work of many people, though most were not
involved in the "rpem" project.  I include their names here to
recognize their contributions; don't hold them responsible for any
shortcomings in the final product.  Since they're all pretty busy, you
probably should think twice before sending them email.

Arjen Lenstra   lenstra@flash.bellcore.com
   Wrote the multiple-precision integer package in zbigint.c.

Bennet Yee      bsy+@cs.cmu.edu
   Wrote the essential decryption routines found in mberleka.c,
   egcd.c, and mcrt.c.

Marc Ringuette  mnr+@cs.cmu.edu
   Wrote miscellaneous large integer routines, provided ideas.

Phil Karn       karn@thumper.bellcore.edu
   Wrote (most of) the DES implementation used here.

Michael Rabin   rabin@endor.harvard.edu
   Designed the public key algorithm used here.

I (Mark Riordan) did all the rest.

Michael Rabin's public key algorithm is in the public domain.  All
code by Arjen Lenstra, Marc Ringuette, Phil Karn, and Mark Riordan 
is in the public domain.  Bennet Yee's code is bound by GNU-like
restrictions; see his comments in the above-mentioned files.
For more information on what's in the files (which include a
few minor applications other than rpem and makerkey), see
the file INSTALL.  So far, the package has been ported
(from OS/2 1.1) to MS-DOS and a few flavors of Unix.


KEY REGISTRATION

How do you communicate your public key to others?  That's a good 
question, and I have no answer that matches the capabilities provided,
for a fee, by RSA Data Security and possibly other companies.
The "makerkey" program creates public key output that is meant
to be appended to a communal file that will be searched by rpem
when it is run in enciphering mode.

I have provided a crude way of collecting public keys on an
Internet-wide basis.  There is a key server on dcssparc.cl.msu.edu,
35.8.1.6.  Send your public key output (stdout) output from makerkey
via electronic mail to:

   rkey@dcssparc.cl.msu.edu

The key server collects its mail messages every hour and appends them
to a key named "rkeys", which is available as pub/rkeys/rkeys via
anonymous FTP from dcssparc.cl.msu.edu.  Although I've tried to 
make the key server semi-intelligent, it might be confused by some
.signature files, so turn off signatures if possible.

[Disclaimer follows.]
Naturally, this service is not being provided on an official basis
and might be terminated or moved to another machine without notice.
Furthermore, this method of key distribution does not provide for
authentication.  Sorry.


FILE FORMATS

======== Start of sample output from rpem ================================

-----PRIVACY-ENHANCED MESSAGE BOUNDARY-----
Proc-Type: 2000,ENCRYPTED
DEK-Info: DES-CBC,BC8FAD3F2E1CF923
File-Mode: ASCII
Sender-ID: me
Sender-Public-Key:
 EZH1YLtibf1rJyRkZhGPtGfmb60vRrVXwDJ=
Recipient-ID: mrr@mynode
Key-Info: Rabin,
 FND4Cw1e0Wg0Fw6Q/reCQalmftUhHAlvbgg=

q6cWPpcyR56noyopXOPVFbdJIP8dA9K5spLqUkGhMzPbFw9LIjoQvA==
-----PRIVACY-ENHANCED MESSAGE BOUNDARY-----
======== End of sample output from rpem ==================================

======== Sample private key file =========================================
p
 zkRn8p2nDP9Q6pRgQm690Q==
q
 zUQMYumwa+ToMaz2Cwyx3Q==
Rabin-Modulus:
 EZH1YLtibf1rJyRkZhGPtGfmb60vRrVXwDI=
======== End of Sample private key file ==================================

======== Sample public key file ==========================================
User: mrr@tardis.cl.msu.edu
Rabin-Modulus:
 EZH1YLtibf1rJyRkZhGPtGfmb60vRrVXwDI=

User: jls@cl-next1.cl.msu.edu
User: john_smith
Rabin-Modulus:
 5XyCX/OJFpHXapSwHvSf9oUHlbARdh1WorwP

======== End of Sample public key file ===================================

Note the manually-added synonym "john_smith".


The output files from rpem encryption have the following pieces:

-----PRIVACY-ENHANCED MESSAGE BOUNDARY-----
   This line appears at the beginning and end of the output from rpem.

Proc-Type: 2000,<enc>
   This line indicates the encryption system and is always present.
      2000 indicates the rpem system.
   <enc> is ENCRYPTED or PLAIN.  (PLAIN means encryption algorithm
      "none" has been selected.)

DEK-Info: <alg>[,<initvec>]
   This line gives information on the message key and is present only
   if the message has been encrypted.
   <alg> is DES, DES-ECB, DES-CBC, NEWDES, NEWDES-ECB, or NEWDES-CBC.
      DES  specifies the Data Encryption Standard.
      NEWDES specifies the obscure but fast algorithm invented
           by Robert Scott (unrelated to DES, really).
      -ECB specifies Electronic Code Book (i.e., unmodified) block
           encipherment and is the default if neither -ECB nor -CBC
           is specified.
      -CBC specifies Cipher Block Chaining.
   <initvec> is the initialization vector in hexadecimal and is
      specified only in CBC mode.

File-Mode: {ASCII | Binary}
   This line specifies the mode of the original plaintext file.
   If not specified, the default is ASCII.  Means nothing to Unix.

Sender-ID: <useraddress>
   This line specifies the identity of the sender.
      In the current implementation it is ignored.

Sender-Public-Key:
   This line has no fields but is followed by the unencrypted
      public key component of the sender, in RFC 1113 encoded format.
      This encoded public key contains white space in the first
      column of each line.  In the best of worlds,
      one would hope that the recipient would obtain the sender's
      public key (for purposes of a reply) in some more sophisticated
      way, but for our little system here this will have to do for now.
      This line is ignored in the current implementation.

Recipient-ID: <useraddress>
   This line specifies the recipient.  There can be multiple recipients,
      each of whom gets his own copy of the message key.  There's only
      one message key per message, but it's encrypted differently
      for each recipient.

Key-Info: Rabin,
   This line preceeds the RFC 1113-encoded, Rabin-encrypted message key
      for this (the preceeding) recipient.
      It appears only in ENCRYPTED mode.  The key contains white
      space in the first column of each line.
      "Rabin" specifies the algorithm used to encrypt the message key.

These fields are followed by an empty line, and then the message
itself (encrypted or unencrypted) in RFC 1113 coded form.  The
lines of the message do not start with white space.


FUTURE WORK FOR AMBITIOUS INDIVIDUALS

-- Add Digital Signature capability.  Must be done carefully to
avoid making it easier for an assailant to determine p and q.

Here are some ideas from Marc Ringuette:

"I would impose the following strict guideline:  the requester gets to
specify most of the bits (in order to be sure that the signer was
authentic), and the signer gets to specify at least 64 random bits
(in order to be secure against attacks on his public key).

So if we assume a 384 bit modulus, I would do the following:

To sign a block sent by person X:
   - accept blocks of length up to 320 bits.  Pad with 32 random bits at the 
     beginning, and 32 random bits at the end.  Take the square root; and
     return the block you used (including the random bits) and the root.
   - to check a signature, check that your bits are contained in the
     middle of the signed block, square the signature, and see if the signer
     gave the correct square root.

To sign a message you're sending:
   - run a message digest algorithm on the message (e.g. repeated
     DES-CBC on message "000000" with keys equal to blocks of the message,
     or another recognized message digest that would be hard to fake, but
     that someone checking on you can verify).  [I would use MD2 or MD4
     to avoid export restrictions on DES.  /mrr]
   - replicate the message digest up to 320 bits, pad with 32 random
     bits at beginning and end, and sign that block.  Provide the random
     bits along with the signature.
   - to check a signature, perform the message digest, append the signer's
     random bits, and check that the signature is the correct square root."


-- Add Message Integrity Check (MIC) (aka Checksum).  Should be much
easier--use, for instance, the MD4 algorithm kindly placed in the
public domain by Ronald Rivest.  (FTP to rsa.com.)

-- Implement message key caching (for both sender and receiver) for a
series of messages to the same individual.  This prevents the
recipient from having to do the slow public key decryption for each
message.  I.e., this is strictly for performance gain.  Idea due to
Bennet Yee.

-- Consider issues related to attempts to decrypt with the wrong
private component of the public key.  Consider whether the file
containing the private component should be labelled as to whether the
key is encrypted.  This could be a security problem for users who
choose to not encrypt their keys; the fact that the key is not
encrypted would be more obvious to a system cracker pawing through
user files.

--  Speed up the zbigint.c multiple precision integer package.  Convert
it to Lenstra's new package (which I just received) or possibly benchmark
some of the other multiple precision packages.  [I have collected some
of these on cl-next1.cl.msu.edu (35.8.4.21).]  For MS-DOS and/or OS/2,
code some of Lenstra's basic routines in 386 assembler.  The refusal
of MS C 6.0 and Turbo C to generate 386 instructions (esp. for
32-bit multiplys) probably really slows things down.  It appears that
the 386 implementation is disproportionately slower than 32-bit Unix
implementations for this reason.

--  Implement additional symmetric systems.

--  Improve the method by which "makerkey" chooses primes.
I understand that there are other criteria besides size which
primes p and q should meet in order to make pq hard to factor.

--  Integrate into a Mail User Agent for ease of use and to take
advantage of fields like Sender-Public-Key.


I will probably continue to fiddle with this program myself; in
particular, I'd like to implement signatures and MIC's.  Before doing
so, though, I thought I'd release this to the net in its current form.
This project has dragged on long enough as it is.

Please mail your comments and criticisms to me at:
  riordanmr@clvax1.cl.msu.edu

Mark Riordan  Michigan State University (but not representing MSU here)
              24 April 1991
