RSA.EXE Documentation - 1
Table of Contents
Command Line Arguments...........4
Program Options (No Frills)......7
Generate EKEY/DKEY Pair........8
Recover EKEY from DKEY....... 12
Change Key Descriptions.......14
Program Options (with Frills)...15
Enhancements over No Frills...16
Issue Command to DOS..........18
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
RSA.EXE Documentation - 2
The program RSA.EXE is an implementation for IBM-compatible
microcomputers of the Rivest-Shamir-Adleman public-key
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
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
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