Exploring RSA Encryption

By convenient accident, the program does not echo the values of p and q. That is just as well, because those two numbers must never be revealed. After you have your key numbers, you no longer need p and q, so all traces of those two numbers can and probably should be erased.

Alice can copy her keydata text file into two new files with the commands

        cp keydata mykey
        cp keydata publickey

for example, and then call her favorite text editor with the command able mykey to delete everything except her private key. The file mykey then would look like:

Use private key d:
11996408748608023536238408391172572664696533934155555472164565632938\
50181603

The other file, publickey, can be edited with the command able publickey. Everything can be deleted except the following text containing the public key:

 Publish e:
75380476290958131791641748048971859813983920749766736465799243190805\
53565403
 and n:
22614142887287439537492524414691557944195176224930020939739772957241\
398345067

Alice can publish this file on her web site or send it to Bob as clear text in an e-mail.

Once Alice has published her public keys, anyone can of course encrypt a message and send it to her; perhaps pretending to be Bob. While our premise has been that only Alice needs to set up RSA encryption, in practice, both Alice and Bob will probably want to set up RSA encryption. By doing so, Bob can use his own private key to authenticate his messages.

Recall that the program rsatest1.bc does not care whether you are encrypting or decrypting. Indeed, the program does not even know which of these two things you are doing. Any message encrypted with e and n can be, in turn, decrypted with d and n. Likewise, any message encrypted with d and n can be decrypted with e and n.

When Bob encrypts a message with his own private key, anyone can decrypt that message with Bob's public key. Putting it the other way round, if you can decrypt a message with Bob's public key, then Bob must have been the one who encrypted the message. In effect, the message is Bob's signature.

Practical implementations of RSA encryption are available both in Phil Zimmerman's Pretty Good Privacy and in the Free Software Foundation's GNU Privacy Guard, the GNU equivalent of PGP. The latter one is published with all the sources.

Sources for the programs rsakeys.bc and rsatest1.bc, as well as rsakeys1.bc, are in the compressed file crypto.tgz that can be downloaded from www.seasurf.com/~jdennon. All the author's code is GPLed.

On that site you can also check out my pretty good editor for GNU/Linux, described in the book Build your own Linux C Toolbox.

GNU Privacy Guard, a free replacement for PGP, can be downloaded from www.gnupg.org.

Also available from the Free Software Foundation is the GNU Bc compiler written by Philip A. Nelson. The entire Bc package including sources can be downloaded from www.gnu.org/directory/bc.html.

An introduction to Pretty Good Privacy, including a blow-by-blow account of Phil Zimmerman's many battles on our behalf, can be found in the book PGP: Pretty Good Privacy, by Simson Garfinkel, published in 1995 by O'Reilly. ISBN 1-56592-098-8.

For additional background on PGP, see Phil Zimmerman's own book, The Official PGP User's Guide published in 1995 by The MIT Press.

For background on cryptography in practice, written by a professional in the field, with details on RSA and many other algorithms, find a copy of Bruce Schneier's Applied Cryptography, published in 1994 by Wiley, ISBN 0-471-59756-2. Although the first edition is out of print, the second edition is available at Amazon.

Jack Dennon is owner of Micromethods, where he writes control code for sawmill machines, studies Linux and helps his wife homeschool their four children.