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:
- 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!
- 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 256x
<= 10300, 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 263-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 DFF library unit, DFFLIBV14.
February 10, 2015: An astute German user, Frank, recently
discovered an error in the key generation process which produced invalid keys
about 1 to 20 times. The program uses a BlockSize field to control
encrypting and decrypting multiple characters at a time for efficiency.
The first piece of generated keys is N, and the algorithm calculates encrypted
and decrypted values modulo N. For this to work, N must be larger
than the largest value that can be contained in BlockSize bytes. N is
generated as the product of two random prime numbers and must be larger than 2Keysize.
For example, with Keysize=16, this minimum is 65536. Without
checking, I foolishly assumed that the product of two 3-digit primes would
contain at least 6 digits and therefore be guaranteed larger then 65536.
That turns out not to be true: e.g.101x103 =10402; way too small.
Version 2.1 posted today now loops generating random primes until the product
exceeds 2Keysize .
Frank shared a "stress test" program he wrote to generate thousand of keys,
encrypting and decrypting various message and comparing the final result with
the input plaintext. It was was very useful in finding the bug in my code.
"Just for fun" I plan to extend the program to include timing tests to see
if either of these two alternative solutions is faster: