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.RSA EncryptionNamed 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.The GNU Bc CompilerOur 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.Setting Up RSATo 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).Example Key SearchUsing 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

Example ApplicationAlice 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.Bigger Is BetterIn 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.Big NumbersTo 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)

Discard p and qBy 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.Extract the KeysAlice 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.SpoofingOnce 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.SignaturesRecall 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.RSA in PracticePractical 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.ResourcesSources 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