Problem Description

Here's a program that examines the RSA Public Key Exchange algorithm.  

Background & Techniques

A buddy of mine wrote a while ago asking me to clarify exactly how Alice and Bob used public key sharing to send encrypted messages.  I had read and thought I understood the concepts, but I couldn't  explain it to with out a refresher.  An excellent source is the book "In Code" by Sarah Flannery, a young Irish girl who, as a science project,  developed a potential improvement on the RSA Encryption system.  Her project won several national and international  awards and led to this book.  Highly recommended!   Wikipedia website pages are another good source of the basic material.

In its simplest terms, an individual has public and private keys,  each consisting of two values.  For the public key the values are n, the "modulus",  and e, a "magic" encrypting integer.  The private key values are n, the same modulus value that appears in the public key, and d, a number which can decrypt any text encrypted using the public key.  

This program contains a simple worked example using small keys and has pages allowing "Alice" and "Bob" to simulate exchanging encrypted messages.  Key modulus values from 16 to 1024 bits in length are supported.  By the way, a handy rule of thumb for converting between binary and decimal number sizes is to multiply binary lengths by 0.3 to get decimal lengths.    So the program handles keys roughly from 6 to 300 digits long.  Key modulus lengths are significant in two ways: 

1. The RSA generation technique depends on the fact that it is generally difficult to factor a number which is the product of two "large" prime numbers.  This is the way that RSA determines the n value.    If the two prime factors of n  and the public e value are known, the private d value could be calculated, a bad thing!   
2. The n value also determines the number of different plain-text values that can be encrypted.  So with large n, we can can combine multiple characters into a single block and instead of 26 or 128 or even 256 possible numbers for the bad guys to play with, we can can millions or trillions of multi-character phrases to decipher, a much harder nut to crack.  

    For a little math break, we can figure out the block size for a 300 digit key modulus if we want to be able to encrypt all 256 possible single byte character values.   The requirement is that 256^x  <= 10³⁰⁰, or, taking the log of both sides, x log(256) = 300 log(10)  so, since log(10)=1,  x = 300 / log(256) = 300 / 2.41 = 124.5 or 124 characters per block. 

Using the program should be pretty much self explanatory.  There are a couple of pages of text describing the calculation of the keys once three independent variables (the two primes and the e value) are chosen and the theory behind message "signing", proving that the sender is who they say they are.   The last two pages represent the traditional correspondents, Alice and Bob who can exchange messages, hopefully with minimal training on our part to assist them.

Non-programmers are welcome to read on, but may want to skip to the bottom of this page to download executable version of the program.

Notes for Programmers

The program uses a modified version of our UBigInts big integers unit.  Modifications in UBigIntsV4 include functions and procedures related to generating large random numbers and a few bug fixes.  UBigIntsV4 is included with the source for this demo and will replace the UBigIntsV3  unit distributed as part of the DFF Library file after I get a chance to perform some more testing of the changes.

The mathematics behind RSA key generation are well known.  In fact, public disclosure of the encryption/decryption algorithm is one of the basic tenets of software cryptographic  systems.  The BigInt methods GCD,  InvMod, and ModPow  have existed in past versions and are used in generating keys and in encrypting/decrypting messages in this program.    The BigInts test program allows these functions to be tested with user input values and was a convenient tool for manually performing the required operations while the code was being developed.  

The trickiest part of the code was in the MakeRSAKey procedure, specifically handling the blocking.   It took longer than it should have for me to recognize that even though the encryption/decryption operations are symmetric (i.e. encrypting with the private key and encrypting with the public key works just as well as the other way around), separate Encrypt and Decrypt procedures are required.  While we can take Blocksize characters at time while encrypting,  the cipher-text consists of numbers which are padded out (with zeros on the left) to the number of digits in the key modulus.   Therefore, when decrypting, we must take modulus length characters at a time instead of Blocksize characters.     I have no idea how other implementations handle this problem, but mine requires that we know whether we are encrypting or decrypting.  This does not seem to be a big handicap..                

A TKeyObj class was defined to hold parameters for each actor.  It contains their name, their current key values and the associated block and key size values.  There is a TTabsheet control for each actor and each tab sheet contains a dozen or so controls which made for rather tedious duplication of code to handle each entry or button click.  If I were starting over, I would look at making TKeyObj a TTabsheet descendant but it never got quite tedious enough to make me start over.    

Addendum March 21, 2012:  A viewer recently asked about converting RSA keys back to integer values because he wants to incorporate them into Java code.  I'm not sure of the details, but I could tell him that if using standard 64 bit integers,  this is only feasible for keys which are less that 2⁶³-1, 1ithe maximum 64 bit integer value.  So, only keys up to 63 bits could be so converted.   In the process of reviewing the code I did however find a number documentation errors which I corrected and posted as an update today.  No other changes except to the description text screens.   

June21, 2012:  Program was reposted today with more cleanup of button placement and labels.  Also, then "big integer" random number generation routines have been moved to the standard UBigIntsV3 unit and updated with the new release of the DF library unit, DFFLIBV14.  

Running/Exploring the Program 

Suggestions for Further Explorations