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