In contrast to the cooperative preparations required for setting up private key encryption, such as secret-sharing and close coordination between sender and receiver, you can act entirely on your own to create and publish two numbers that enable anyone, using the RSA encryption formula, to send a private message to you through a public channel. The message becomes "First Class" e-mail, so to speak, as if sealed in an envelope. Using the two numbers you have published, anyone can scramble a message and send it to you. You are the only one who can unscramble it--not even the sender of the message can decrypt the ciphertext.

Named after its inventors, Ron Rivest, Adi Shamir and Leonard Adleman, RSA encryption transforms the number "char" into the number "cipher" with the formula

        cipher = char^e (mod n)

The numbers e and n are the two numbers you create and publish. They are your "public key." The number char can be simply the digital value of a block of ASCII characters. The formula says: multiply the number char by itself e times, then divide the result by the number n and save only the remainder. The remainder that we have called cipher is the encrypted representation of char.

Our test program for calculating RSA keys, rsakeys.Bc, is written for Philip A. Nelson's threaded code compiler, named Bc. A program written for Bc is well suited to this experimental work, because it can handle numbers of arbitrary size.

To set up RSA encryption, the main thing you need is a table of prime numbers. Begin by selecting two prime numbers at random. When the rsakeys.bc program asks for p and q, give it the two primes you selected. Of course, any numbers can be used for practice. Primes, especially large primes, make it more difficult for an eavesdropper to decrypt your message.

Call the program with the command bc rsakeys.bc. After you enter the numbers p and q, the program asks for a random number to be used to start a search for keys. When the program finds a pair of keys, it prints out results and pauses for keyboard input. Enter a negative number to quit. Or, if you don't like the key pair offered, enter any positive number to continue the search for another pair of keys. The value that you enter, to continue or to stop, doesn't matter; only its sign is checked.

The search finds two numbers, e and d, such that their product, modulo the number (p-1)*(q-1), is 1. In other words, the numbers e and d are such that their product minus 1, e*d - 1, is an integer multiple of the number (p-1)*(q-1).

Using small numbers for clarity, here are results of an example run:

        enter prime p: 47
        enter prime q: 71
        n =  p*q   = 3337
        (p-1)*(q-1) = 3220
        Guess a large value for public key e 
        then we can work down from there.
        enter trial public key e: 79
        trying e = 79
         Use private key d:
        1019
         Publish e:
        79
         and n:
        3337
        cipher = char^e (mod n)  char = cipher^d (mod n)
        enter any positive value to continue search for next e 

The output above was created by the following Bc program.

   
# rsakeys.bc: generate RSA keys
# these Bc routines are transliterations of
# the  C  routines found in Bruce Schneier's
# "Applied Crytography" Wiley, New York. 1994.
# ISBN 0-471-59756-2
# modexp: from page 200
define modexp(a, x, n) { # return a ^ x mod n
        auto r
        
        r = 1
        while ( x > 0 ) {
                if ( (x % 2) == 1 ) {
                        r = (r * a) % n
                }
                
                a = ( a * a ) % n
                x /= 2
        }
        return(r)
}
# extended Euclidean algorithm
# adapted from  C  routine on page 202 
define exteuclid(u, v) {
        auto q, tn
        u1 = 1
        u3 = u
        v1 = 0
        v3 = v
        
        while ( v3 > 0 ) {
                q = u3 / v3
                
                tn = u1 - v1 * q
                u1 = v1
                v1 = tn
                
                tn = u3 - v3 * q
                u3 = v3
                v3 = tn
        }
        
        u1out = u1
        u2out = ( u3 - u1 * u ) / v
        return(u3)
}
print "enter prime p: "; p = read() 
print "enter prime q: "; q = read()
n = p * q
phi = (p-1) * (q-1)
print " n =  p*q   = ", n
print "\n(p-1)*(q-1) = ", phi
        print "\nGuess a large value for public key e "
        print "\n then we can work down from there."
        print "\nenter trial public key e: "; e = read()
        while ( e > 0 ) {
                
                print "\ntrying e = ",e
                gcd = exteuclid(e,phi)
                d = u1out
                if ( gcd == 1 ) {
                        nextgcd = exteuclid(u1out,phi)
                        # print "nextgcd = ",nextgcd
                        if ( u1out == e ) {
                                # print "\nthat one works  "
                                print "\n\nUse private key d:\n",d
                                print "\n\n Publish e:\n",e,"\n and n:\n",n
                                print "\ncipher = char^e (mod n)"
                                print "  char = cipher^d (mod n)"
                                print "\nenter any positive value"
                                print " to continue search for next e "
                                go = read()
                                if (go < 0) { break }
                        }
                }
        e = e - 2       
        }
        print "\n"
halt

Alice publishes the public key numbers e = 79 and n = 3337. Bob wants to send Alice the message Dr Dobbs. In decimal ASCII the message is 6882326879666683. Break this number string into smaller blocks like so

        688 232 687 966 668 3

To encrypt these blocks, apply the formula

        cipher = char^e (mod n)

to each block.

Let us create a Bc program to handle this calculation. Call your favorite text editor with a command such as able rsatest1.bc and type in the following text.

# rsatest1.bc:  RSA experiment 1
# encrypt or decrypt characters
define modexp(a, x, n) { # return a^x mod n
        auto r
        r = 1
        while ( x > 0 ) {
                if ( (x % 2) == 1 ) {
                        r = (r * a) % n
                }
                
                a = ( a * a ) % n
                x /= 2
        }
        return(r)
}
print "enter the base n (=p*q): "; n = read()
print "enter the key (e or d) : "; e = read()
print "\n"
while ( 1 ) {
        print "enter a character code (or -1 to quit): "
        char = read()
        if ( char < 0 )
                { break }
        cipher = modexp(char,e,n)
        print "cipher = ",cipher,"\n"
}
halt

Now Bob can encrypt his message with the command bc rsatest1.bc. The interactive session looks like this:

   
enter the base n (=p*q): 3337
enter the key (e or d) : 79
enter a character code (or -1 to quit): 688
 cipher = 1570
enter a character code (or -1 to quit): 232
 cipher = 2756
enter a character code (or -1 to quit): 687
 cipher = 2091
enter a character code (or -1 to quit): 966
 cipher = 2276
enter a character code (or -1 to quit): 668
 cipher = 2423
enter a character code (or -1 to quit): 3
 cipher = 158
enter a character code (or -1 to quit): -1

The encrypted message is 1570 2756 2091 2276 2423 158.

Bob can copy this number string into an e-mail and send it to Alice. When Alice receives this message, she decrypts it with her secret key, d = 1019, by calling the same program, with the command bc rsatest1.bc. Her interactive session looks like this:

   
enter the base n (=p*q): 3337
enter the key (e or d) : 1019
enter a character code (or -1 to quit): 1570
 cipher = 688
enter a character code (or -1 to quit): 2756
 cipher = 232
enter a character code (or -1 to quit): 2091
 cipher = 687
enter a character code (or -1 to quit): 2276
 cipher = 966
enter a character code (or -1 to quit): 2423
 cipher = 668
enter a character code (or -1 to quit): 158
 cipher = 3
enter a character code (or -1 to quit): -1

The decrypted string is 6882326879666683, which is the decimal ASCII representation of Dr Dobbs. Alice has received Bob's message.

The program should perhaps say char instead of cipher when it is being used to decrypt a message, but from the program's point of view the two operations are identical. The program doesn't need to know whether you are encrypting or decrypting; it does the same thing in either case.

In practice, large values for p and q should be used to create keys of about 100 digits, or even more. The larger the key strings are, the more difficult it is for an eavesdropper to decrypt successfully the message by brute force. For example, a brute force attack could set up the equation

        cipher = char^e (mod n)

with the known values of e, n and cipher. This implicit equation can, in theory, be solved for char by iterating through all possible values of char until one finds a value of char that generates the known value of cipher.

In our example we used small char blocks of three decimal digits each. To make the values of char large, making brute force decryption impractical, use big values for p and q, say 100 digits each. This way, the number n has about 200 digits. Instead of dividing your message into blocks of three digits each, you can then divide your message into blocks of just under 200 digits each. That should keep brute force cryptanalysts busy for a while.

To experiment with really big numbers, the compressed file crypto.tgz, which can be downloaded from www.seasurf.com/~jdennon, contains an alternative version of the key generator, called rsakeys1.bc. In this generator, the main program has been rearranged to keep things somewhat more orderly when reading input from stdin and writing results to stdout. The revised program uses the same subroutines modexp() and exteuclid(). Here is the revised main program:

print "enter prime p: "; p = read() 
print "enter prime q: "; q = read()
print "\n"
n = p * q
phi = (p-1) * (q-1)
print " n =  p*q   = ", n
print "\n(p-1)*(q-1) = ", phi
#       print "\nGuess a large value for public key e "
#       print "\n then we can work down from there."
#       print "\nenter trial public key e: "; e = read()
#       print "\nenter a random number: "; rn = read()
        e = n / 3
        rn = read()
        if ( e < n ) { e += rn + n }
        found_one = 0
        while ( e > 0 ) {
                while ( e > phi ) { e = e / 2 }
                if(found_one == 0) { e = e / 2 }
                
                print "\ntrying e = ",e
                gcd = exteuclid(e,phi)
                d = u1out
                if ( gcd == 1 ) {
                        nextgcd = exteuclid(u1out,phi)
                        # print "nextgcd = ",nextgcd
                        if ( u1out == e ) {
                                # print "\nthat one works  "
                                found_one = 1
                                print "\n\nUse private key d:\n",d
                                print "\n\n Publish e:\n",e,"\n and n:\n",n
                                print "\ncipher = char^e (mod n)"
                                print "  char = cipher^d (mod n)"
                                #print "\nenter any positive value"
                                #print " to continue search for next e "
                                #go = read()
                                #if (go < 0) { break }
                        }
                }
        if (found_one == 1) { break }
        e = e - 2       
        }
        print "\n"
halt

To create an input data file for this program, call your favorite text editor with a command such as able rsadata1 and type in three numbers:

        150386117655676543895037387253432987103
        150373872534329871035038611765567654389
        349801523

The first number is p, the second is q and the last number is the guess for the number e, which starts the search for the keys. If asked whether these first two big numbers are primes, be pleased, like Mark Twain, to answer immediately. Say, "I don't know."

Save the text file and then call the modified version of the key generator program with a command such as bc rsakeys1.bc < rsadata1 > keydata. For the example input file rsadata1, the contents of the example output file keydata should look like this:

enter prime p: enter prime q: 
 n =  p*q   = 226141428872874395374925244146915579441951762249300209\
39739772957241398345067
(p-1)*(q-1) = 226141428872874395374925244146915579438944162347400145\
24809696958222397703576
trying e = 753804762909581317916417480489718598139839207497667364657\ 
9924319080553565403
Use private key d:
11996408748608023536238408391172572664696533934155555472164565632938\
50181603
 Publish e:
75380476290958131791641748048971859813983920749766736465799243190805\
53565403
 and n:
22614142887287439537492524414691557944195176224930020939739772957241\
398345067
cipher = char^e (mod n)  char = cipher^d (mod n)

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.