Public Key System for Encryption and Digital Signatures

Copyright (c) Lloyd Miller, 1985
Calgary, Alberta



Public Key Encryption is a system of encrypting messages where the
encryption and decryption keys are different. The, so called, public
encryption key, used to encrypt messages is related to the private decryption
key but it is very difficult to figure out the decyrption key if you only know
the encryption key. (If you think this is confusing, you're right.)

To send a secret message to someone you need to know only their public
key. For anyone to send you a secret message, you need to let them know your
public key. I have included my public key with these files so that anyone who
gets this system can send me a secret message (I don't know why they might
want to but they can). If someone wants me to reply (secretly) then they would
have to send me their public key.

Messages can also be encrypted with the private key. This is called a
signature. Anyone who knows the public key can decrypt the message but only
the person who knows the corresponding private key could have created the
message. I have included a message signed by me in this archive that can only
be decoded with my public key and thus could only have been encrypted by my
private key. Since I havn't given my private key to anyone and I don't think
anyone could have figured it out, you should be able to safely assume that I
wrote the orginal message. Signatures are not quite as useful as the normal
encryption operation but they do have some very interesting capabilities.

Messages can be encrypted more than once. One use for this feature is to
sign a secret message. To do this you encrypt the message with both the your
private key and the recipient's public key. The combination is a message which
only the recipient can read and only you could have created. In order to read

the message it must be decrypted twice using the recipeint's private key and
your public key in the reverse order that it was encrypted.

The difficulty of "breaking" the key is dependant on the length of the
keys used. Keys of 8 digits or smaller are actually quite easy to break. In
fact you my find a simple (hee hee) basic program included with these files
for "cracking" keys of 5 to 8 digits (called cracker.bas). I haven't really
tried it but a key of even 50 digits is estimated that it could be cracked in
about 4 hours using a super computer and the fastest factoring algoritm known.
A key of 75 digits would take 104 days and a key of 200 digits would take
3,800,000,000 years. For more on this see the ACM article. If anyone cracks my
75 digit key I would like to hear about it. I suspect you would need a Cray-2
or equivalent to do it this year.

The disadvantage of longer keys is that it takes longer to find and create
the key and the encryption/decryption processes are slower as well. A 8 digit
key will only take about 1/2 minute to generate with this software on a
standard IBM-PC. A 20 digit key takes about 90 sec. A 50 digit key, about 10
min. A 200 digit key will take about 6 to 12 hours. These times may be longer
or shorter depending on your luck on the random number generator.












PKSCrypt is a program to perform the three basic functions reqired for a
complete public key encryption system. The first question it asks is what
function you want to perform, Genkeys, Encrypt, Decrypt, or Quit.

GENKEYS is the function to generate encryption and decryption keys for the
RSA (Rivest, Shamir, Adleman) system of public key encryption. See
Communications of the ACM, February, 1978.

GENKEYS takes, as the first input parameter, a single number from 5 to 200
designating the number of digits desired in the key. This number determines
the level of security of the resulting cypher. It also determins the amount of
time needed to generate a key.

Also input is a name for the key to be generated. This is an 8 character
filename without extension.

Output of the function is two files (besides all the stuff displayed on
the screen to keep you from thinking the software has crashed). The first is
the public key file called keyname.KEY. It contains two numbers, each of which
contains, at most, the number of digits requested. The first number is called
"n" and is the product of two large prime numbers (p and q). The second number
is called "e" and is a number which is relativly prime to (p-1)*(q-1). These
numbers are the, so called, public key. This file is the one to be given out
and/or published for people who want to send you secret messages.

The second file produced is called keyname.KDY. It also has two numbers in
it. The first is "n" and is the same as the "n" in the public key. The second
number in this file is called "d" and is the secret decryption key. "d" is
constructed such that (d * e) MOD ((p - 1) * (q - 1)) = 1. This file is your
private key for decrypting messages encrypted with your public key and must be
kept secure and private. Perhaps keep it on a floppy disk and locked up when
not in use, perhaps with extra copies in separate places.

The key files are only significant up to the end of the second number in
each file so comments may be added at the end of the file. This is
particularily usefull for the public key files where the name and/or address
can be added to the key to indicate the owner of the key. For an example of
this, see the file LLOYD.KEY included in this archive. That file is my public
key and can be used to send me secret messages. When you edit these files make
sure your editor does not break any long lines into shorter lines. For
instance a 200 digit key would have over 200 characters in each of the first
two lines. These lines must not be broken up into shorter lines.

The other two functions, ENCRYPT and DECRYPT, use the key files created by
GENKEYS to encrypt and decrypt other files. The time required for these
functions to do their job depends on the length of the key used and the size
of the file. Any file can be encrypted with any key. They can only be
decrypted with the opposite key of the pair.

ENCRYPT, when selected, will ask for the name of the file to be encrypted
and the full name of the key file to be used for encryption (ie "LLOYD.KEY").
Third and last it will ask for a file name to store the encrypted file under.
ENCRYPT saves the name of the key file used to encrypt in the output file in
plain text so that the decrypt system can easily figure out which key is











needed. It does not store any keys in the encrypted file, just the key file
name. Encrypt also saves the input file name and size in the encrypted file.
This is so the decryption can reproduce the origninal file. The input file
name and size are encrypted so no extra information is obtainable from the
encrypted file without the decryption key.

DECRYPT first asks for the name of the encrypted file. It reads the header
and offers you the default name for the decryption key. (I.E. if the file was
encrypted with a key called "test.key" it will ask if you want to decrypt with
"test.kdy".) Normally you would anser "yes" to this question. If you have
renamed the key file you want to use then answer no and type in the name you
want to use. If you tell the program the wrong key to use then nothing will
work right after that. DECRYPT then decodes the first part of the file to
obtain the original file name and size. Once it has decoded this information
it will ask you if you want to use the original name for the decoded file or
you can enter a new filename. DECRYPT will then procede to decrypt the rest of
the file.


PKSCrypt can be operated from the command line if you know in advance the
answers to ALL the questions which will be asked. Just type them following the
command to start up the program. ie:

pkscrypt genkeys 10 temp quit
pkscrypt e temp.key temp.dt1 temp.dt2 q
pkscrypt decrypt temp.dt2 yes yes quit


Anyone can make as many copies of this software as they want and give them
away so long as the programs and this documentation are included in any copies
and all files are in their original unmodified form. In fact you are
encouraged to distribute this software as much as possible by whatever means
you can find, electronic, magnetic, optical or via any future technologies
which may be developed. If you find this system usefull then you can encourage
me to write and distribute more of my software by sending $30 to:

Lloyd Miller
2420 Capitol Hill Crescent, N.W.
Calgary, Alberta T2M-4C2

If you are a corporate or governmental user then the $30 is not optional.
If you need an invoice in order to pay for this please feel free to make one
out. If you send me a SSAE I will send you a real invoice.

This software and documentaion is protected by copyright and if you don't
think that means much then ask a lawyer.

If you have comments, complaints (heaven forbid) or questions then you can
either send a SASE to the above address or send a message to me (Lloyd Miller)
via Fidonet(TM of Tom Jennings) node 134/1, "The Calgary Fido". If you want to
send encrypted messages via Fidonet then you will need your sysop's co-
operation to send "attached files". Your sysop will not be able to read your
secret messages. If you want to send encrypted messages via traditional mail
then you would have to send floppy disks.












This software is designed to run on an IBM-PC using MS-DOS version 2.00 or
later. I have tried to avoid using any features of the IBM-PC which are
machine dependant so I believe it should work on any system which uses MS-DOS
or PC-DOS but it has not been tested on many other types of systems. I would
like to hear from you if you have tried it on any other systems and if you
have had any probelms or not. I have tested the system on a Sanyo MBC 555
(with a V-20 CPU chip) and it works fine.

These programs are written in Modula-2 using the Logitech Modula-2/86
compiler system. I would be willing to consider converting these programs for
use with other Modula-2 systems if anyone wants to pay me to do the
convertion. I would not consider converting the programs to another language.
The nature of these programs would probably eliminate from consideration any
M-CODE or P-CODE interpreter style compiler systems since they would become
prohibitivly slow.


Version History

Version 0.0 Distributed as three programs, GENKEYS, ENCRYPT, and
DECRYPT. Worked fine

Version 0.01 Combined the three programs into one executable,
PKSCRYPT, to save space on my disk. The same key files and encrypted files are
used.

Version 0.01a Update to Version 2.0 of the compiler. Some spelling
corrections.

Version 0.01b Eliminated last few remaining REALS. Added a few
"Please Wait" messages. Documented the command line operation which has
allways been available.

Version 0.01c Converted a few selected routines to mahine code. Not
much speed difference resulted. Hardly worth the effort.

Version 0.01d Allows smaller keys (5 digits) and includes
cracker.bas for breaking keys of 8 digits and smaller.

Version 0.02 Changed the long arithmetic from byte at a time to
word at a time. Very nice speed improvement. Generated a 200 digit key in 4
hours 40 min. Minimum key size increased back up to 7 digits because of
occational hangs on smaller keys.
Sample decrypt times for 10 byte message on regular 8088 at 4.77mhz.

Key digits V0.01d V0.02

10 0:12 0:12
20 0:20 0:15
30 0:31 0:15
40 1:02 0:26
50 1:42 0:38
200 36:57 10:29

Version 0.02a Found another bug in the long arithmetic. V0.02 would
occasionally dump with a divide by zero. Some more speed-up implememted,
relativly minor.

Lloyd Miller
1986 March 29