% $RCSfile: rsa.tex,v $
%
% $Log: rsa.tex,v $
% Revision 1.1  1995/07/28 21:19:57  slm
% Initial revision
%
% Revision 1.6.1.1  1994/10/21  00:00:17  hkaram
% New branch
%
% Revision 1.6  1994/08/02  23:55:43  davidm
% Sectioning commands now use \protspec and \topic so latex2html has
% an easier time.
%
% Revision 1.5  1994/07/05  00:42:34  ho
% Indexed.
%
% Revision 1.4  1994/01/14  19:29:44  menze
% Fixed KEYS subsection to not make TOC entry
%
% Revision 1.3  1994/01/12  01:31:42  menze
% Fixed an exponentiation
%

\protspec{RSA}{RSA (Rivest-Shamir-Adleman Encryption Algorithm)}
\index{rsa}
\index{RSA encryption}
\index{cryptography, public key}
\label{RSA}

\input cryptDist

\topic{SPECIFICATION}

\noindent
The RSA protocol encrypts all bytes of all packets sent using the
RSA encryption algorithm in ECB (electronic code book) mode.
RSA uses the key manager protocol (KM, page~\pageref{KM}) to map from the 
destination address passed in at open time to an RSA key.  Each message is 
encrypted independently.  RSA is designed to be composed over any
datagram protocol, and it accepts arbitrary address types at 
open time.  RSA lengthens each packet by as much as a few hundred bytes.
When packets are received, decryption reverses the encryption, and the original
packet lengths are restored.

The important cryptographic feature of RSA is that the encryption and decryption
keys contain different information, so that the encryption key may
be published, without compromising the decryption key.


\topic{SYNOPSIS}

\noindent 
When an RSA session is opened, it opens the protocol configured below 
it with the addresses passed to it during open.  It then performs a 
GETPARTICPANTS operation on the newly opened session 
to acquire the fully resolved addresses of the participants.  The
first two participants are then used as arguments to open two key manager (KM)
sessions. 

When a message is pushed to an RSA session a KM\_RESOLVE operation is
done on the destination key manager session to get the current remote encryption key.
This will be a series of two or three large numbers, expressed in decimal
as a string, several hundred characters long.
A special parsing routine converts the numbers to the binary values
required for the RSA algorithm.  The character string key, and converted binary key
are cached; on subsequent messages, the key returned from the key manager
is compared to the cached value, and if it hasn't changed,
the conversion step is skipped.

The message length is prepended to the message as an unsigned four byte number.

The message is divided into blocks of size (binary-key-size - 1) bytes.
The last block is padded with 0s if needed.

Each block is encrypted with the RSA algorithm, producing an output
block one byte larger than the input block.  These blocks are concatenated
to make the output message.  A typical RSA key size is 64 bytes:  In this case,
input messages of size 0 - 59 bytes will expand upon encryption to one
block of 64 bytes; a message of size 1000 bytes will expand to 1024 bytes.

Decryption is straightforward, using essentially the same algorithm.
(The KM\_RESOLVE is done with the local host address.)
Some partial checking is done that the decrypted input makes sense.
Of course, received packets shrink some when they are decrypted.

RSA has not been tested on little-endian machines, or between
machines of differing endianness.

RSA discards the attributes attached to any outgoing message.
This is done to minimize out-of-band information transmittal.
RSA does not touch any attributes attached to incoming 
messages, and forwards them along with the decrypted data up to the next 
protocol.  Exception: If the IP psuedoheader length fixup flag
is turned on, the length field is adjusted in upgoing pseudoheaders.

For packets going in either direction, if the KM\_RESOLVE fails, the message is dropped.
The present code assumes that the decimal-to-binary conversion operation
on the key will succeed; bad format keys will probably cause a memory fault.


\topic{REALM}

RSA is in the ASYNC realm.


\topic{PARTICIPANTS}

RSA passes participants to the lower protocols without manipulating them.
It uses the first two participants to lookup the keys for encryption and decryption.

\topic{CONTROL OPERATIONS}

RSA recognizes the following control operations; all others are passed
unchanged to the lower protocol or session.  To prevent an outbound
channel, the data buffer is zeroed in the downward direction.

GETMAXPACKET and GETOPTPACKET:  The packet size returned by the lower
protocol/session is passed on unchanged.  This isn't exactly the right
thing to do.

IP\_PSEUDOHDR:  This control operation turns on the IP pseudoheader
length-fixup flag, either for a session or the entire protocol.
The control operation is also passed to the lower session or protocol.
See IP (page~\pageref{IP}) for an explanation of this kludge.

ETH\_REGISTER\_ARP is recognized by rsaControlProtl, and is passed
down without zeroing the data buffer.

RSA does not support the CRYPT series of control operations for communicating
with the key manager.


\topic{CONFIGURATION}

RSA expects to be configured on top of a transport protocol and a
key manager.  The transport protocol must
preserve packet boundaries (i.e. RSA will not work on top of TCP).

Example of a graph.comp file:
\begin{verbatim}
---------------------------------
@;
name=simeth/0;
name=eth protocols=simeth/0;
name=arp protocols=eth;
name=vnet protocols=eth,arp;
name=ip protocols=vnet;
name=km;
name=rsa protocols=ip,km;
name=udp protocols=rsa;
name=udpcrypttest protocols=udp;
@;
prottbl = ../../../etc/prottbl.nonstd;
---------------------------------
\end{verbatim}

\topic{KEYS}

An RSA key is a set of three numbers, separated by any nonnumeric characters.
The three numbers are the Modulus, the Encryption exponent, and the
Decryption exponent, in decimal.  The decryption exponent may be 0 if absent.
A bad format key can cause a core dump in the key parser.
No consistency checking is done on the numbers.
No cryptographic care is taken by the key parser to erase intermediate results.
The modulus M is the product of two large primes P and Q, each typically around 75 digits.
P and Q don't appear explicitly in the key.  They must be kept secret.
There is various magic for selecting ``good'' primes, but random primes of the
right size are usually ok.
In the example below, I have standardized on the value $2^{511}+3$ as the
encryption exponent E.  Any large number about the size of the modulus may be
used for E, but it must be relatively prime to (P-1)*(Q-1).
The modulus and the encryption exponent are published.
The decryption exponent D is the solution to D*E = 1 (mod (P-1)*(Q-1)).
It must be kept secret.

Example of a keys file:
\begin{verbatim}
---------------------------------
4 10-1000 10
0xc00c4574  #leibniz
            # P = 314159*10^70 + 143; Q = largest prime < 2^512/P
            # Mod = P*Q;  EncExp = 2^511+3
            "1340780792994259709957402499820584612747936582059239337\
             7723561443721764030073217999499518551191939614890369525\
             058823497765371118769307671100370276265584333
             6703903964971298549787012499102923063739682910296196688\
             8617807218608820150367734884009371490834517138450159290\
             93243025426876941405973284973216824503042051
             2210719290388045346905339355787434075468743397471703259\
             9002057100400698735281575781871972803870117115603534718\
             25220112394617831579775760441554445681825271"
0xc00c4554  #cottonwood
            # P = 271828*10^70 + 183; Q = largest prime < 2^512/P
            # Mod = P*Q;  EncExp = 2^511+3
            "1340780792994259709957402499820584612747936582059239337\
             7723561443721764030073529800297232392991909065538380829\
             542476840196156388644073364112998961600082697
             6703903964971298549787012499102923063739682910296196688\
             8617807218608820150367734884009371490834517138450159290\
             93243025426876941405973284973216824503042051
             5907169959764554352962919640402328589843757838494447294\
             1156728779748701667813048426221184319210061087236538029\
             59044237615679489623343998139399365759904515"
---------------------------------
\end{verbatim}

For testing, I have all my machines sharing one keys file, and the
decryption exponent is included with each key.  In normal use,
each host will have its own keys file, and the third number in
each key will be 0 except for the host's own key.


\topic{RESTRICTIONS}

\noindent Most of the restrictions mentioned in CRYPT also apply to RSA.
One additional weakness of RSA is that it operates in ECB
(electronic code book) mode, so, in a message that contains a repeated
block of plaintext, the plaintext will be enciphered to the same value
each time.  A block of 0s enciphers to a block of 0s, and a block with
all zeros except the low bit will encipher to the same thing.
RSA is quite slow.

\topic{ACKNOWLEDGMENT}

\noindent RSA uses the GNU multiprecision package to do its bignum arithmetic.


\topic{AUTHOR}

\noindent Richard Schroeppel

