RSA Public Key Demo

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa® 365 Puzzlers  Calendar 2017

Mensa® 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

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 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:

bulletReduce BlockSize value by 1 or
bulletIncrease the number of digits in one of the random prime factors of N by 1 digit.  

Either of these

Running/Exploring the Program 

bullet Download source
bullet Download  executable
bulletDownload latest version of the DFF Library unit, DFFLibV15. (required to recompile the program).

Suggestions for Further Explorations

bullet Add button to allow user to load the example key parameters for Alice and Bob to simplify checking of encrypting/decrypting for user input messages. 
bullet Add optional "signature authentication"  to the Alice/Bob exchange
bullet Allow users to save and restore key parameters.  Would enable actual email message exchange by using copy/paste between this program and an email program. 

   

Original Date: March 12, 2009 

Modified: May 15, 2018

`

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2018, Gary Darby    All rights reserved.