RSA.EXE Documentation - 1



Table of Contents


Overview.........................2
Command Line Arguments...........4

Program Options (No Frills)......7
Generate EKEY/DKEY Pair........8
Encode File....................9
Decode File...................11
Recover EKEY from DKEY....... 12
System Information............13
Change Key Descriptions.......14

Program Options (with Frills)...15
Enhancements over No Frills...16
Maintain KEYRACK..............17
Issue Command to DOS..........18

Digital Signatures..............19
The Algorithms..................20
Operation Times.................23
Miscellaneous...................24


The program RSA.EXE and accompanying documentation RSA.DOC may be
distributed and freely used for any non-commercial purpose,
provided that no modification is made to either and provided that
the program is not distributed without the documentation.


Disclaimer: The author makes no representations or warranties
with respect to the program or documentation, and specifically
disclaims any implied warranty of fitness for any particular
purpose for the program or documentation.


RSA.EXE (V. 88.08.15) now includes frills such as windows/color/
sound and on-line time estimates for long-running operations.
The display-related frills should work on most machines. A no
frills command line option is also supported. The option
essentially duplicates the previous version of the program
(except for keyrack support). The option produces a scrolled
display format that should work on any MS DOS machine.


Any questions, comments, bug reports, etc., may be addressed to
Craig Hessel on the CPCUG (Capital PC User Group) BBS,
Washington, DC, (301) 738-9060. I'll answer whatever I can. If
you find this program useful, and wish to send money, I'm not
interested. Instead, support your local user group or the
CPCUG. CPCUG annual membership, at $25, is one of the best
bargains around.


RSA.EXE Documentation - 2



Overview


The program RSA.EXE is an implementation for IBM-compatible
microcomputers of the Rivest-Shamir-Adleman public-key
cryptographic system.

The system was discovered in 1977 by the three MIT researchers
and was subsequently reported in the February, 1978, issue of
Communications of the ACM. The short paper there is entitled "A
Method for Obtaining Digital Signatures and Public-Key
Cryptosystems". Ten years later, the RSA system is still the
only known secure public-key cryptosystem.

At the time, publication of the paper stirred controversy. The
viability of the system was not the source of the controversy.
At issue was the potential conflict between the right to academic
freedom and the interest of national security. The point may
well be moot now. In any case, the RSA system has created
intense interest in the once-esoteric mathematical study of ways
to factor large numbers. Factoring large numbers is thought to
be the only way to "crack" the RSA system.

A public-key cryptosystem is a cryptographic system that requires
each user to create two distinct, but related, keys -- a decoding
key, which is kept secret, and an encoding key, which is
publically revealed. Making the encoding key public allows
anyone to encode data and then safely transmit it over insecure
channels to the holder of the corresponding secret decoding key,
without the need for a secret preliminary exchange of keys or
encryption procedures.

Before the discovery of the RSA system, the science (or art) of
cryptography traditionally required a single key for use in both
encoding and decoding. This key had to be secretly exchanged or
agreed upon beforehand by the interested parties.

The decoding key of each key pair in a public-key system must be
related to the encoding key. Otherwise decoding would be
impossible. But in order for the secret decoding key to be
secure, the relationship must be unusual enough so that knowledge
of the general relationship and the specific encoding key is
still insufficient to deduce the corresponding decoding key.

In the RSA system, the public encoding key of a key pair is the
product of two large prime numbers. Prime numbers (2, 3, 5, 7,
11, 13, 17, ...) are numbers which cannot be written as the
product of smaller numbers. The corresponding secret decoding
key is essentially the two prime factors known separately. The
qualifier 'large' is important here. The number 91 would not be
a secure encoding key, since it is easy to deduce that 91 is the
product of primes 13 and 7. However, factoring a large product
into its component primes becomes very difficult as the size of
the primes increases.

RSA.EXE Documentation - 3




With the use of fast computers, parallel processing, and
sophisticated mathematical algorithms, prime products approaching
80 decimal digits in length can now be factored. Because
factoring is an old mathematical problem that has been studied by
some of the best minds in that field over several centuries,
advances in the ability to factor large numbers are likely to
occur in at best small increments (an argument in the original
RSA paper). As a case in point, a recent heralded improvement
using parallel processing extended by only a dozen or so digits
the length of numbers that could be factored in a reasonable
amount of time.

On the other hand, it is relatively easy even on a microcomputer
to find a pair of large prime numbers (a decoding key).
Multiplying the primes together to create the corresponding
encoding key is also a simple matter. Users of the RSA system
need only choose sufficiently large primes to begin with to stay
well ahead of current technology and mathematical research.

Nothing is free. There is a cost in speed associated with using
the RSA system, but it is minor. Manipulating large numbers is
inherently time-consuming. However, by using the RSA system to
encode a key for a secure, and invariably faster, private-key
system, and then by using that key for encryption, anyone can
quickly encode a large volume of data without losing the benefit
of public-key cryptography. This is what RSA.EXE, in fact, does.
The private-key system used here is not particularly fast. But
it is very secure. And you may similarly use any other secure
private-key system as a third encryption level to gain additional
speed, if you wish.

RSA.EXE has a default key size of 64 bytes, which is equivalent
to an encoding key in excess of 150 decimal digits. The program
supports key sizes up to twice that length. Details on the use
of RSA.EXE, a description of the public-key and private-key
algorithms, and some typical running times are presented in later
sections of this documentation. Also described later is the
digital signature feature of the RSA cryptosystem.

One point needs to be emphasized before going on. RSA.EXE is not
meant to be, nor is it particularly useful as, a "hard disk
security" system. Rather, the use of RSA.EXE assumes that both
you and any party with whom you are exchanging data have secure
bases of operation to start with. There are other utilities or
physical mechanisms available for securing hard disk data, if
that is what you are looking for. What RSA.EXE does provide is a
way of safely encoding data for transmission over public (or
insecure) channels, e.g., phone lines, microwave transmissions,
or bulletin boards, WITHOUT requiring any prior secure meeting or
secure exchange of secret keys. If you are new to the idea of
public-key cryptography, that concept usually takes awhile to
sink in.


RSA.EXE Documentation - 4



Command Line Arguments


Unless you have included the command line option I=OFF, RSA.EXE
initially displays the following information:

----------------------------------------------------------------

RSA Public-Key Cryptography with Digital Signatures (V. 88.08.15)

Usage: RSA [[=] ... ]

default meaning
-------- ---------- ------- ------------------------
S 1 - 8 4 key size is 16 * S bytes
E drive:path current location for EKEY.RSA
D drive:path current location for DKEY.RSA
K drive:path current location for KEYRACK.RSA
I ON/OFF ON initial info display
F 1 - 8 7 frill level

No single argument may exceed 32 characters in length. Key sizes may not be
mixed during encoding/decoding or in keyrack. Use frill level 1 (no keyrack/
windows/color/sound) for incompatible adapters/monitors/machines.

RSA system developed by Rivest/Shamir/Adleman at MIT in 1977-78. This RSA
implementation plus private-key system by Craig Hessel. LIAL interpreter (V.
88.07.27) handles core routines. Frills written with Don Fordham's EZWINDOWs.

See file RSA.DOC for complete system documentation.

----------------------------------------------------------------

The option S=n, where n is 1 - 8, sets the security level for the
current session. The default is 4. The security level is 1/16
of the system key size in bytes. You should probably experiment
with the program using the smallest key size. This is not secure
(since 16 bytes is only about 38 decimal digits -- see Overview
discussion), but it is fastest for learning to use the program.

The E=drive:path, D=drive:path and K=drive:path options allow you
to specify locations for three files created/maintained by the
program: EKEY.RSA, DKEY.RSA, and KEYRACK.RSA. The default
drive:path is the current drive:path in each case. EKEY.RSA and
DKEY.RSA will each eventually hold a single key (an RSA encoding
key and RSA decoding key, respectively) preceded by a 40-
character descriptive tag. KEYRACK.RSA will hold RSA encoding
keys with their descriptive tags.

Option I=OFF turns off the above information display. I=ON is
the default.

Option F=n, where n is 1 - 8, sets the frill level for the
current session. The default frill level is 7. The frills

RSA.EXE Documentation - 5



supported at each level are summarized below:

8 - keyrack/windows/color/menu clicks/shadows/window sound
7 - keyrack/windows/color/menu clicks/shadows
6 - keyrack/windows/color/menu clicks
5 - keyrack/windows/color

4 - keyrack/windows/menu clicks/window sound
3 - keyrack/windows/menu clicks
2 - keyrack/windows

1 - no frills (scrolled display)

The frills above, aside from the keyrack, were written with Don
Fordham's EZWINDOW utility package and will work only with
hardware configurations supported by that package. This
excludes, for example, Hercules adapters and machines that are
not sufficiently IBM-compatible. For such equipment, use frill
level 1 (which duplicates the previous version of the program,
except that the keyrack is not supported). For monochrome
adapters, use frill levels 1 - 4. Even with compatible
equipment, you may still wish to use frill level 1, for example,
when redirecting keyboard input from a file. Frill level 1 does
not allow keyboard input to interrupt long-running operations and
is thus suitable for input redirection.

The keyrack is intended to hold the public encoding keys of
others with whom you wish to exchange RSA-encrypted data.
Ordinarily, DKEY.RSA will not change. It will be your personal,
secret RSA decoding key. EKEY.RSA will change each time you
choose to communicate with a different individual. You will
extract the individual's key from the keyrack (overwriting the
previous EKEY.RSA) before choosing the main encoding or decoding
option. Or else you might download the individual's encoding key
from a bulletin board to the file EKEY.RSA, and from there you
could add it to your keyrack. EKEY.RSA should be regarded as a
temporary file.

It is important to note that key sizes may not be mixed, either
in the encoding/decoding of files or within a keyrack. If you
choose to use different key sizes (different security levels),
you should maintain separate directories for each set of *.RSA
files, and then use command line options to specify their
locations. You might alternatively wish to maintain your
DKEY.RSA file on a floppy disk.

If you execute RSA.EXE with a security level different from the
one under which the specified *.RSA files were created, you will
typically get error messages from the program indicating that the
file encountered has an improper size with respect to the system
key size. To RSA.EXE, the *.RSA files contain no indication of
the system key size under which they were created other than
their DOS file size. The same holds true for encoded data files.
You may for your own benefit include this information in the

RSA.EXE Documentation - 6



descriptive tags for the keys or files.

The following example illustrates the use of the command line
options. Suppose you are in directory C:\DATA where there is a
small test file you want to encode. You've previously copied
RSA.EXE into some directory included in your DOS search path.
You could then start up RSA.EXE as follows:

RSA S=1 K=\RSA\LEVEL1 E=\RSA\LEVEL1 D=A: I=OFF F=4

This sets the system key size to 16 bytes. It also tells RSA.EXE
that files KEYRACK.RSA and EKEY.RSA both reside (or will be
created) in directory \RSA\LEVEL1 and that file DKEY.RSA exists
(or will be created) in the current directory on floppy drive A.
Directory C:\RSA\LEVEL1 should already exist, or else an error
message will appear. The initial information display is turned
off and the frill level is set to the highest that should be used
with a monochrome adapter.

To save keystrokes, you might wish to put a startup command like
this in a batch file.


RSA.EXE Documentation - 7



Program Options (No Frills)


There are six main program options (plus Quit) when the no
frills command line option (F=1) is used. This frill level is
also defaulted to automatically if there is insufficient memory
available for frills. Approximately 80 K is required for the
program with no frills -- an additional 32 K is required for the
frills. Pressing the asterisk (*) key at the prompt "Choose RSA
option (* = HELP):" will give you bullet descriptions of the
options. An option is chosen by pressing the letter key
associated with the option. These are the options:

(G) Generate EKEY/DKEY pair in files EKEY.RSA and DKEY.RSA
(E) Encode source file, creating separate target file
(D) Decode source file, creating separate target file
(R) Recover EKEY.RSA from DKEY.RSA
(S) System information display
(C) Change DKEY and/or EKEY description

With no frills, the program proceeds in a line-by-line scrolled
format.

The options are discussed in the following sections.


RSA.EXE Documentation - 8



Generate EKEY/DKEY Pair


This option (G) generates an RSA key pair and saves the keys
separately in files DKEY.RSA and EKEY.RSA. Before the process
begins, you are asked to supply random keystrokes as input and
also descriptive tags (up to 40 characters each) for the keys
that will be created. The number of random keystrokes required
is twice the system key size. The low order four bits of the
pressed key's ASCII code is extracted at each keystroke. Key
combinations or single keystrokes that translate to two-byte
codes are ignored (e.g., the function keys), with the exception
of the left cursor, which the program treats as a backspace.

For testing, you might hold down the same key for all the
"random" keystrokes. That way you can regenerate the same key
pair later to verify that the pair can indeed be recreated from
the same "random" keystrokes. For RSA keys that you really
intend to use, you should suitably scramble your input
keystrokes.

You may abort the operation by leaving either key tag blank.

The message "Generating keys..." appears next, followed by the
starting time. Whenever you see a time display during the
program, be ready to wait awhile. This indicates that a possibly
long-running operation is taking place. At frill level 1, these
operations may not be interrupted. When the operation is done,
the ending time will also be displayed.

RSA key generation is the most time-consuming option in the
program. Fortunately, it should not have to be executed often.
Once you have established your key pair, you should not have to
change it unless you lose your decoding key or unless its
physical security has been compromised.

For a key size of 64 bytes and on a Norton SI = 8.0 machine, this
operation typically takes seven to 14 minutes. The times vary
considerably since the operation searches for prime numbers,
which are not regularly spaced. For the maximum key size of 128
bytes and on the same machine, the operation typically takes one
to two hours. This is strictly internal processing, so you will
not see any disk activity during the wait. See the Operation
Times section for statistical data on key generation times.


RSA.EXE Documentation - 9



Encode File


This option (E) RSA-encodes a source file and produces the
encoded target file. You interactively supply four items of
information: some random keystrokes, a source file name, a
target file name, and a descriptive tag for the target file. In
addition, prior to calling the option, you should insure that
DKEY.RSA contains your secret decoding key and that EKEY.RSA
contains the public encoding key of the individual to whom you
will send the encoded file.

Initially, the descriptive tags contained in the current EKEY.RSA
and DKEY.RSA files are displayed. If these are not the keys you
intended to use, you may abort the operation by supplying a blank
source or target file name. The program also does a check to
insure that the two keys are not from the same key pair (i.e.,
the program makes sure you aren't accidentally using your own
encoding key). If the first four bits of the encoding key are
not clear or if the final bit is not set, you will be warned that
the key may not be a valid encoding key. If you choose to
continue, the five bits will be corrected for the operation. The
key in EKEY.RSA will remain unchanged, however.

The encoding operation requires you to supply your secret
decoding key for two reasons. As mentioned above, this allows a
check to insure that you are not accidentally using your own
encoding key. More importantly, though, the key is used for the
digital signature mechanism of the RSA cryptosystem. This is
discussed in the Digital Signature section.

The source and target file names may include drive and/or path
specifications. Up to 40 characters may be entered in each case.
If the target file already exists, you will be prompted for a new
target file name.

As with option G, the number of random keystrokes you supply is
twice the key size. The random data is used to generate a
private key for the encoding operation. The RSA keys are used to
encode the private key, which, in turn, is used to encode the
source file. See the Overview section for a discussion of this.

The target file descriptive tag, like any key tag, is limited to
40 characters. The tag is not encoded, and will show up at the
start of the target file if you use the DOS TYPE command to view
the file afterwards.

Encoding proceeds in three steps, each with start/stop times
displayed. The three messages successively displayed are
"Generating private key...", "Encoding private key...", and
"Encoding file...". You will only note disk activity during the
third step.

With a key size of 64 bytes and on a Norton SI = 8.0 machine, the

RSA.EXE Documentation - 10



first step typically takes 40 seconds to about a minute and the
second step consistently takes about 42 seconds. The third step
encodes the file at a rate of just under .9 K per second. With a
key size of 128 bytes on the same machine, the first step
typically takes three to six minutes and the second step takes
just over four minutes. File encoding then proceeds at a rate of
about 0.9 K per second. The times for generation of private
keys vary somewhat, since the operation includes a prime search.
See the Operation Times section for detailed timing data.

The size of the encoded target file will be slightly larger than
the source file. The 40-character descriptive tag and the
encoded private key (which is key-size bytes long) are included
at the start of the file. The file is encoded in key-size-byte
blocks. Any excess bytes found at the end of the file are still
encoded as a key-size-byte block. So there are up to an
additional key-size bytes, less one, at the end of the target
file. These extra bytes will all be stripped away during
decoding.

The limit on the source file size is 16 MB (half the DOS file
size limit).


RSA.EXE Documentation - 11



Decode File



This option (D) RSA-decodes a source file and produces the
decoded target file. The option is a little simpler than the
encoding option. You interactively supply the source and target
file names. In addition, prior to calling the option, you should
insure that DKEY.RSA contains your secret decoding key and that
EKEY.RSA contains the public encoding key of the individual from
whom you received the encoded file.

As with encoding, the descriptive tags contained in the current
EKEY.RSA and DKEY.RSA files are displayed initially. If these
are not the keys you intended to use, you may abort the operation
by supplying a blank source or target file name. The program
also does the same check performed during the encoding option to
insure that the two keys are not from the same key pair.

You are required to provide the sender's public encoding key here
for the purpose of signature verification. See the Digital
Signature section for more on this.

The source and target file names are subject to the same
constraints described under the encoding option. After you've
provided the source file name, the descriptive tag for the file
is displayed. If this isn't the file you intended to use as the
source file, you may abort the option by leaving the target file
name blank. If you get an error message indicating that the
source file is the wrong size, it may be that the file was
encoded under a different key size. This might happen if you are
using several different key sizes and have started up RSA.EXE
with the incorrect size. You may always view a file or key
descriptive tag with the DOS TYPE command.

Decoding proceeds in two steps, each with start/stop times
displayed. The messages displayed are "Decoding private key..."
and "Decoding file...". The times for these operations are
roughly the same as the corresponding encoding times. Note that
the extra "Generating private key..." step required by encoding
does not appear here.


RSA.EXE Documentation - 12



Recover EKEY from DKEY


This option (R) allows you to recover a lost RSA encoding key
from the corresponding decoding key. File DKEY.RSA is input to
the option and you are asked to provide a descriptive tag for the
EKEY.RSA file that will be created. You may abort the operation
by leaving the key tag blank. The option takes less than a
second, even at the maximum key size, on a Norton SI = 8.0
machine.

The reverse option -- recovering a lost DKEY from an EKEY --
cannot be done (for a large enough key size) with any likelihood
of success, since that is what the security of the system is all
about.

With a mainframe computer, you could extract the DKEY from a 16-
byte EKEY. With mainframes and parallel processing, and with
the best algorithm's available, you could probably extract the
DKEY from a 32-byte EKEY. Even with all of the resources
available to a large corporation or a government agency, the
possibility of extracting the DKEY from a 48-byte EKEY is remote.
And as the key size gets larger, the chance of successfully
extracting the DKEY from an EKEY shrinks dramatically.

The gist of this is that the problem of factoring appears to be
one for which every possible algorithm will have a running time
that grows at nearly an exponential rate with respect to the key
length. On the other hand, the running time for the creation of
RSA keys grows only a little faster than the cube of the key
length with the algorithms used by RSA.EXE.

It is suggested that a key size of 64 bytes (the default S=4) be
used for moderate security data transfers and that 128 bytes
(S=8) be used for high security operations.


RSA.EXE Documentation - 13



Change Key Descriptions


This option (C) allows you to change the key descriptions
contained in DKEY.RSA and/or EKEY.RSA.

The current description in each case is displayed (if the file
is present). You will be asked if you wish to overwrite the
description. Even if you answer yes, you may still leave the
description unchanged by just pressing the return key when you
are prompted to enter a new description.


RSA.EXE Documentation - 14



System Information


This option (S) shows the current system key size, the frill
level, the version date of the LIAL interpreter, and the current
EKEY.RSA and DKEY.RSA file specifications. For each of the two
files, an indication of whether or not the file exists yet is
also displayed. However, no check is made at this point of
either file's size.

If a file size is incompatible with the current system key size,
it will be detected under any menu option that attempts to use
the file.


RSA.EXE Documentation - 15



Program Options (with Frills)


After the main menu pops up, there is a pause of up to four
seconds accompanied by the message "One moment please". During
this pause, a rough speed check is made of the host machine. The
computed speed may vary up to about 5% from one program run to
the next. This check is made so that time estimates can be
supplied later for long-running operations. If a system clock
cannot be found, or if you "trick" the program into thinking your
machine is extremely slow by pressing Ctrl/NumLock during the
operation, the estimates will not be forthcoming or will be very
inaccurate. The estimates will also be inaccurate if you switch
your machine's speed subsequent to the check.

Menu options are selected by moving the highlight bar over the
desired choice with the up or down cursor arrows and then
pressing the return key. (Note: if you have a monochrome adapter
and have started up the program with a frill level higher than 4,
the highlight bar may not be visible.) The menu options are the
same as those for the no frills version of the program, with two
additional options:

Maintain KEYRACK
Issue Command to DOS

The six main menu options that are also included in the no frills
menu are discussed in the next section, with only the major
differences highlighted. So if you have skipped ahead to this
section, you might wish to backtrack and read the no frills
descriptions first. Generally the options are handled
similarly, aside from the obvious differences due to windows,
color, and sound.

The two additional options are discussed afterwards in separate
sections.


RSA.EXE Documentation - 16



Enhancements over No Frills


During any potentially long-running operation, i.e., EKEY/DKEY
generation, private key generation, encoding/decoding of a
private key, or encoding/decoding of a file, you may abort the
operation by pressing any key and then answering yes to the
"Abort?" prompt.

During the encoding/decoding of a file, the file size in
kilobytes is displayed along with the current number of
kilobytes encoded/decoded. The display is in whole numbers, with
any decimal portion truncated. E.g., 67.7 kilobytes is displayed
as 67 kilobytes.

When supplying random keystrokes prior to beginning either
EKEY/DKEY generation or private key generation, the four bits
extracted from each keystroke are displayed as a hexadecimal
digit (0-9 or A-F).

For EKEY/DKEY generation, private key generation, and
encoding/decoding of private keys, a time estimate for the
operation is displayed. In the case of EKEY/DKEY and private key
generation, the time estimate consists of a range of times. The
operation should fall within the indicated range about half the
time, and should fall below that range about as often as above.
For encoding/decoding of private keys, the time estimate is a
single time (not a range). Also included is a reminder that the
actual time may occasionally be a multiple of the displayed time.
Short time estimates (less than about four seconds) are reported
as "a few seconds".

The time estimates are based on the data found in the Operation
Times section, with a scaling adjustment for the speed of the
host machine.

A beep will signal the conclusion of long-running operations.
Error conditions will also be signaled with a beep.

When changing key descriptions, you are not asked if you wish to
overwrite the current description of the DKEY (or EKEY). If you
do not wish to change the displayed description, just press the
return key when prompted to enter a new description.

The display of system information includes the keyrack file
specification and an indication of whether or not the file is
present.

Whenever you are prompted for text or number entry in the frills
version of the program and you press just the return key, no
action is taken. When you are prompted for a 'yes' or 'no'
response (Y or N), just pressing the return key is the same as a
'no' response.


RSA.EXE Documentation - 17



Maintain KEYRACK


The keyrack is a frills option. When you select the keyrack
maintenance option from the main menu, another menu pops up with
options to do the following:

View the descriptive tags of keys in KEYRACK.RSA
Add EKEY.RSA to KEYRACK.RSA
Extract a key with its tag from KEYRACK.RSA to EKEY.RSA
Change the descriptive tag of a key in KEYRACK.RSA
Delete a key and its tag from KEYRACK.RSA

If KEYRACK.RSA does not exist at the start of maintenance, the
empty file is created and a message to that effect appears.

If you get an error message during maintenance which indicates
that KEYRACK.RSA is the wrong size with respect to the system key
size, this usually means you've started up RSA.EXE with the wrong
key size for that particular keyrack. Remember, key sizes may
not be mixed within a keyrack. The program will not always
detect these kinds of errors. E.g., a keyrack of thirteen 16-
byte keys (with 40-character tags) is the same size (728 bytes)
as a keyrack of seven 64-byte keys (with 40-character tags) and
these keyracks are not distinguishable by the program.

The keyrack is limited to 100 keys. This is an arbitrary limit.

The add option will prevent you from adding duplicates to the
keyrack. For the purpose of duplicate checks, the key tag is
ignored and only the key itself is inspected. In addition, the
first four bits and the final bit of the key are ignored during
the check, since these have fixed values for all RSA encoding
keys and will be corrected, if necessary (with a warning issued),
during any file encoding/decoding operation. Adding a key to the
keyrack is the functional equivalent of the DOS command COPY
KEYRACK.RSA/b+EKEY.RSA, but without duplicate checking or file
size checking.

The extract option does not also delete the key from the keyrack.

The program will prevent you from blanking out a key tag.


RSA.EXE Documentation - 18



Issue Command to DOS


This frills option allows you to enter a DOS-executable command.
The error message "Unable to execute command" will appear if the
program is unable (e.g., due to insufficient memory) to invoke
the command processor in order to execute the command. The
amount of additional memory required (besides the 112 K required
by the program with frills) depends on the version of DOS that is
running. Typically, this will about 30 K.

If sufficient memory is available, but you just mistype a command
(e.g., DUR instead of DIR), you will get the appropriate DOS
error message directly from DOS. You may normally shell to DOS
here by entering COMMAND and then later return to RSA.EXE from
the DOS prompt with the EXIT command.

The program does not leave any disk files open during this
option, so you are free to perform any reasonable disk-
maintenance activities, including deleting or renaming *.RSA
files. If you remove any directories that you have specified
explicitly in command line options, the program will later give
an error message when trying to create the corresponding files.

If you have started up RSA.EXE with command line options giving
complete file specifications for the *.RSA files, you may change
directories or drives without changing the *.RSA files the
program will subsequently use. If you started up RSA.EXE with
the default file specifications (current drive:path), the
program will later use the files it finds in the new location, or
it will create new ones there. If, however, you have specified
an incomplete file specification in any of the command line
options, make sure the path still exists after a drive or
directory change. Otherwise, the program will later give an
error message when trying to create any such files.

Reminder: the system information display will show the current
file specifications for the *.RSA files.

Do NOT do unreasonable things like installing terminate-and-stay-
resident programs while shelling out of RSA.EXE, or out of any
other program, for that matter.


RSA.EXE Documentation - 19



Digital Signatures


The RSA system provides a digital means for confirming that an
encoded message is from the person who claims to have sent it,
provided that the sender has not let his/her secret decoding key
be compromised. The method is based on the fact that the RSA-
decoding of data, followed by the RSA-encoding of the result,
using keys from the same key pair, restores the original data.
This also happens, of course, in the usual case when the data is
encoded first, then decoded.

The file encoding procedure described earlier requires that the
sender of a message provide both the public encoding key of the
intended receiver and the sender's own secret decoding key. The
sender's secret key is used initially to decode the data (which
is a one-time-use private system key). Next, the receiver's
public key is used to encode the result. Since the RSA keys used
in these two steps are from different RSA key pairs, the result
is still scrambled data. The one-time-use key (saved in
unscrambled form) is then used to encode the file to be
transmitted.

When this scrambled data reaches the receiver later, he/she
provides his/her own secret decoding key and the sender's public
encoding key to the file decoding procedure. The procedure
initially uses the receiver's secret key to decode the scrambled
one-time-use key. The result at this point is still scrambled
and must be encoded with the sender's public encoding key to
restore the original one-time-use private system key. If the
sender of the data had not, in fact, earlier used the secret
decoding key that corresponds to the public key used in this
step, the result would still be garbage, which the program will
detect. (And if by remote chance the garbage turns out to be a
valid private key, it will not be the correct one. The
subsequently decoded file will then be garbage.) Only the holder
of that secret key could have sent anything that ultimately
results in meaningful data.

This signature verification only guarantees that someone who knew
the sender's decoding key actually sent the data. The original
RSA paper suggested the possibility of using tamper-proof "black
boxes" for encoding/decoding, with something truly random and
non-reproducible (like cosmic rays) used internally to generate
random input for creation of its RSA key pair. The box could
never reveal its decoding key, and so could be the only source
for messages whose signatures were verified by its revealed
encoding key.

Whether or not this is practical, or even feasible, is debatable.
In any case, RSA.EXE is limited to the weaker form of signature
verification and leaves up to users the responsibility for safe-
guarding their secret decoding keys.


RSA.EXE Documentation - 20



The Algorithms


This section describes the key-generating and encoding/decoding
algorithms used by RSA.EXE. There are two sets of these
algorithms: one set for the RSA public-key system and one set
for the private-key system. Reading this section is optional.

Because the algorithms deal with large numbers, the core routines
were all written in LIAL -- a language specifically designed to
handle large numbers. The LIAL source code for the routines is
included in the public domain package LIAL2.ARC (and any later
versions) as sample source code. The LIAL interpreter is linked
into RSA.EXE to execute the routines.

Although interpreters are usually significantly slower than
compilers, they are ideal for applications that crunch large
numbers. In these, relatively few time-consuming multiplication
and division instructions tend to swamp the overhead introduced
by interpretation. While some of the RSA.EXE functions,
particularly the public-key functions, may seem slow, that is
basically the nature of number-crunching. Factoring a 150-digit
number is a much better example of "slow". However, the private-
key system included in RSA.EXE admittedly could benefit from
compilation.

Both the public-key and private-key algorithms include searches
for prime numbers. Both use a surprising algorithm, due to M.
Rabin, that finds primes "probabilistically". See LIAL2.ARC for
further details.


The RSA keys are created by first generating two prime numbers
from the user-supplied random input. Let N represent the system
key size in bytes and let P and Q represent the two primes, where
P is the larger of the two. Three bits of the random input
determine number MU in the range [0,7]. The primes P and Q are
generated from MU and from the rest of the random input subject
to the following constraints:

1. P is 13-MU bits larger than half the system key size.
2. Q is 11-MU bits smaller than half the system key size.
3. P and Q each begin 100000... (binary).
4. Neither P-1 nor Q-1 is divisible evenly by 3.
5. P-1 and Q-1 each have a large prime factor.

The N-byte DKEY is formed by stripping away the leading six bits
and the trailing odd bit from both P and Q, and then by packing
MU, followed by the two stripped primes, into N bytes in such a
way that P and Q can quickly be recovered. The N-byte EKEY is
formed by discarding the leading bit from the product P*Q. Note
that P*Q begins 10000... (binary) and is exactly N bytes plus one
bit long. See the package LIAL2.ARC for further details.


RSA.EXE Documentation - 21



An N-byte block of data X is RSA-encoded by performing the
transformation X <-- X**3 modulo P*Q. Note that P*Q is formed
from the EKEY by just restoring the discarded leading set bit.
If the result X does not fit into N bytes, the transformation is
repeated until it does fit. Repetitions are infrequent (at
worst one time in 16), since the product P*Q is barely larger
than N bytes. The encoding algorithm here is deceptively simple.
It basically consists of cubing the data and then finding the
remainder from a division by the publically known encoding key.

An N-byte block of data X is RSA-decoded as follows. First,
primes P and Q are extracted from the DKEY. This requires only
some bit-shifting based on the value of MU in the first three
bits of the key, and then the appending of the previously
discarded leading six bits and trailing odd bit to each
truncated prime. Next, number POWER is determined such that 1 =
3*POWER modulo (P-1)*(Q-1). Finally, the transformation X <--
X**POWER modulo P*Q is performed. As with encoding, the
transformation is repeated until the result fits into N bytes.
The number of repetitions is the same as the number required when
X was originally encoded. This is significantly slower than the
encoding algorithm. The final exponentiation determines the
speed, not the intermediate computation of POWER.


The size of the private system key is N bytes long. The key is
divided into four N/4-byte parts (with one part including a
leading implied set bit). Encoding/decoding actually takes place
in N/4-byte blocks. Let P, E, D, and R represent the four parts.

The key is determined from the N input random bytes (not quite
all of which are used) as follows. P is determined as a random
prime number that begins 100000000... (binary) and is exactly N/4
bytes plus one bit long. P is the system prime modulus and is
the part whose leading bit is implied when the four parts are
packed together to form the key. Next, E is set to N random
bytes, aside from the leading bit, which is set to 1. Part D is
then determined such that 1 = E*D modulo P. If D does not fit
into N/4 bytes, E is decremented by 1, and the value for D is
redetermined. This is repeated until D fits into N/4 bytes.
Repetitions will be infrequent, since P is barely larger than N/4
bytes. E is the system encoding multiplier; D is the system
decoding multiplier. Finally, part R is set to N/4 random bytes.
R is the initial seed value for a pseudo-random stream that is
part of the encoding/decoding process.

Data must be encoded and decoded in the same sequence with this
private-key system. The RSA system is not limited by this
constraint.

An N/4-byte block of data X is encoded as follows. First, the
current random seed R is set to the low order N/4 bytes of
(4*R+1)*(R+1), forming the next seed value. X is then
transformed by being exclusive-ored with the new R. Next, the

RSA.EXE Documentation - 22



transformation X <-- E*X modulo P is performed. If X does not
fit into N/4 bytes, the transformation is repeated until it does.
Repetitions are infrequent (at worst one time in 256), since
prime P barely exceeds N/4 bytes in length.

Decoding proceeds similarly, but with the operation order
reversed. First, the N/4-byte data block X is set to D*X modulo
P. As with encoding, the transformation is repeated until X fits
into N/4 bytes. The same number of repetitions will be required
as were performed when the data was originally encoded. Next,
the current seed value R is set to the low order N/4 bytes of
(4*R+1)*(R+1). X is then exclusive-ored with the new R.


Note that the private system key (after P, E, D, and R are packed
together) begins with a zero byte. This byte contains the eight
clear bits that follow the leading implied set bit in prime P.
When RSA.EXE encodes a file, the actual size of the last data
block in the file (a number less than or equal to the system key
size) is saved in this byte. When the file is later decoded,
the size of the last data block is recovered from this byte, and
its original zero value is restored.


RSA.EXE Documentation - 23



Operation Times


The following results were obtained using several Norton SI = 8.0
machines. For the key generation tests, a separate test program
automated the trials and accumulated the statistics. The program
called the same routines as used in RSA.EXE.


EKEY/DKEY generation times in seconds (100 random trials each):

Key Size Average Minimum 25% Median 75% Maximum
-------- ------- ------- ------- ------- ------- -------
16 | 19 12 15 18 20 40
32 | 90 55 72 82 99 178
48 | 276 120 224 266 329 518
64 | 664 293 456 642 808 1964
80 | 1236 608 931 1141 1457 2756
96 | 2165 834 1425 2007 2892 4155
112 | 3716 1158 2625 3398 4553 8034
128 | 5561 1943 3923 5318 7000 15075


Private key generation times in seconds (100 random trials each):

Key Size Average Minimum 25% Median 75% Maximum
-------- ------- ------- ------- ------- ------- -------
16 | 4 3 4 4 4 6
32 | 13 10 11 13 14 22
48 | 29 21 24 27 33 73
64 | 55 34 41 49 61 132
80 | 89 55 66 81 106 169
96 | 135 82 103 128 159 281
112 | 202 112 145 194 246 496
128 | 283 147 191 247 340 690

Seconds to encode/ Seconds to encode/
Key size decode private key decode 100 K file
-------- ----- -----
16 | 2 208
32 | 9 145
48 | 20 125
64 | 42 115
80 | 72 112
96 | 113 110
112 | 170 110
128 | 250 112

Note: Times for other machines are not quite proportional with
coefficient 1 to the Norton SI rating. Use the command line
argument T=ON to get a display of the speed rating (in System
Information) that scales the time estimates. The machines used
above have a rating of about 70 with the program's method.


RSA.EXE Documentation - 24



Miscellaneous


Version 88.08.15 of RSA.EXE is completely compatible with files
produced under version 88.04.04. The handling of random keyboard
input to produce EKEY/DKEY pairs or private system keys has been
changed, so the same sequence of keystrokes will produce
different keys under the two versions. But the resulting keys
may be used with either version of the program.

The current version of the program uses an updated version of the
LIAL interpreter. The only change to the interpreter is a
reduction in the frequency of checks for keyboard input when
keyboard breaks are allowed. The earlier version of RSA.EXE did
not allow the interpreter to be interrupted. This version allows
interruptions (except at frill level 1), and the change to the
interpreter reduced the overhead introduced by the checks. The
overhead for 16-byte keys is a few percent, but falls to a
negligible amount for key sizes of 64 bytes or more.

The actual LIAL routines (included in LIAL2.ARC) used by this
version of RSA.EXE are the same as those used previously.

The speed check used by the program consists of timing at least
one second's worth of repeated multiplication/division operations
(squaring, then dividing by, a fixed 128-byte number). The
number of repetitions is iteratively increased (1, 3, 7, 15,
..., 255) until at least a full second elapses. This speed
rating correlates well with the LIAL routines used by the
program. Seven repetitions on the Norton SI = 8.0 machines used
for testing took just under one second.

The program leaves all critical error handling up to DOS. This
means, for example, that the message "Abort, Retry, Ignore?" can
foul the screen display if a floppy disk is not in place when
expected. Fixing the problem and then retreating back to the
main menu will usually clear up the screen display. It also
means that you can abort the program at any time with Ctrl/C or
Ctrl/ScrollLock. This is not recommended. Besides the (small)
possibility of corrupting files in use, you will also lose your
cursor. To get the cursor back, restart the program then exit
normally.

This program uses Don Fordham's EZWINDOW shareware utility
package for the menu/window/color frills. The package appears to
work with CGA, EGA, and monochrome adapters (for the latter,
stick to frill levels 1 - 4). A few incompatibilities or
problems that you might encounter are listed below. If you are
having problems with your display other than these, try setting
the frill level lower. The program should work on any MS-DOS
machine at frill level 1.

1. EZWINDOWS does not support Hercules adapters and does not
seem to support marginally-IBM-compatible machines like

RSA.EXE Documentation - 25



WANGs. You will have to use frill level 1 in these cases.

2. Some RAM-resident programs may cause problems with the
display (e.g., the screen-blanking utility BURNOUT). Try
eliminating TSRs to see if one is the cause of the problem.

3. If your machine has a hardware-configured key combination
that switches processor speeds and, in doing so, changes the
cursor appearance, pressing that key combination may also
cause the system cursor to reappear on the screen during the
program. Returning to a program menu should blank out the
cursor again. Reminder: if you switch your processor speed
after program initialization, this will throw off the time
estimates.

Craig Hessel -- 15 AUG 88