# Exploring RSA Encryption

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.

email: jdennon@seasurf.com