Broccoli Products home | contact us | about us
Profile Services Downloads Workshop Extras

The RSA Algorithm
(by Lou Brown, last updated 15-MAR-2010)

The Brief
This is a guide for C# developers who want to implement the RSA algorithm in their applications. Even though RSA was developed in the late 70's, it is still unhackable, and still used today to secure every credit card transaction on the Internet.

Two code files are available to help demonstrate the principles. SimpleProgram.cs encrypts and decrypts a single character using small prime numbers. HelloWorldProgram.cs uses larger numbers to encrypt and decrypt a short message. Both are single C# files that compile as console applications. The function names and code shown on this page are taken from these files. I have compiled and run both files on XP with VS2005.

Another file you will need is the BroccoliProducts.Maths library, which contains a class called JumboInteger for dealing with very large numbers.

File: BroccoliProducts.Maths.dll
Current Build: 1.0.0.6 (20th March, 2010)
System Requirements:    Windows XP


How Does RSA Work?
RSA makes use of a mathematical one-way function - the multiplying of two prime numbers. If someone told you they had multiplied two prime numbers together and the answer was 175,828,273, it would be a real chore working out that the two prime numbers were 17,159 and 10,247. Even computers do not like this sort of mathematics. However multiplying 17,159 and 10,247 together is, of course, a trivial task. This function is easy to do one-way and difficult to reverse - it is asymmetric, and RSA is known as an asymmetric cipher.

A chap called Rivest (who is the "R" is RSA) devised a one-way function that uses this asymmetric function to transform a number into gobbledygook. He then devised another function which, if the two original prime numbers are known, transforms the gobbledygook back into the original number.

The following is a simple example of the RSA algorithm in action. The code for this sample can be found in SimpleProgram.cs.

Although I have done my best to explain the programmatic flow, I am not equipped to explain the Euclidean mathematics which RSA is reliant upon. And most of this is buried in the JumboInteger class away from view anyway. I have added a link at the bottom of this page for anyone who really gets of on Prime Number Theory.
This example assumes Alice wants to send a message to Bob.

A     Alice picks two prime numbers, p and q. She chooses 17 and 11. These numbers she keeps to herself.
B Alice multiplies the two numbers together to get another number N. In this case, N is 17 x 11, which is 187.

N = 17 x 11

N = 187
C Alice chooses another number, e, between 1 and N. The numbers e and N must be co-prime - they must not share any factors. She chooses e = 7.

e = 7
D Alice can now publish N and e. This is her public key:{e,N} = {7,187}
E Bob wants to send Alice a message - the letter "X", which in ASCII is 88. He looks up her public key {7,187} and applies the following formula:

C = Me % N

C = 887 % 187

C = 11
F Bob now sends the encrypted number C = 11 to Alice.

C = 11
G Alice knows something no one else does. She knows the values of p and q, and these two numbers can be combined to produce another number d, her private key, where:

(e x d) % ((p-1)(q-1)) = 1

(7 x d) % 160 = 1

d = 23

Alice's private key is {d} = {23}
H Alice decrypts the message in a similar way to how it was encrypted:

M = Cd % N

M = 1123 % 187

M = 88

In ASCII, 88 is "X".


The JumboInteger Class
In reality the numbers p and q need to be massive. At least 10340 to be unhackable by 100,000 personal computers in 1000 years. Computer languages such as C and Visual Basic do not currently have the ability to calculate AB where A and B are 10340 (although the forthcoming version of Microsoft's .NET will include a large integer class). A special type of integer is required that will support large number mathematics - the JumboInteger.

The JumboInteger class is included in the BroccoliProducts.Math library, which is freely available.

JumboInteger objects can be used as if they were Int32 objects. However because of the potential size of a JumboInteger, caution should be taken that the operations being performed are written in the most efficient way possible. The JumboInteger class can represent numbers up to ±101073741824, but doing anything other than basic addition and subtraction from a number that large could tie up a personal computer for tens of years.

The HelloWorldProgram.cs demonstrates using JumboInteger to perform an RSA encryption and decryption.

Randomly Generating a Prime Number

There is a function in the JumboInteger class MakeRandomPrime( Int32 iBits ), which generates a random number iBits long. To do this MakeRandomPrime generates random numbers, iBits wide, until one is found that may be prime. I use the term "may be" because the only way to be absolutely sure a number is prime is to divide it by every number from 2 up to the number, and this would take too long for large numbers.

The process of filtering possibly prime numbers employed by MakeRandomPrime is as follows:

1    The number must NOT be even. It must not be divisible by 2.
2 The number must NOT be divisible by 3.
3 The number must NOT be divisible by 5.
4 The number must pass 5 rounds of the Miller-Rabin primality test.

The Miller-Rabin primality test is a probabilistic algorithm for determining whether a number is prime or composite.
5 The number must NOT be divisible by small prime numbers between 7 and 27449.
6 The number must pass Fermet's law, which states that a number P may be prime when:

2P % P = 2

Please be aware that for large prime numbers, 1024 bits and more, this function can take several minutes.
The HelloWorldProgram C# File

The HelloWorldProgram.cs file demonstrates RSA using prime numbers of 512 bits to encrypt and decrypt the message "Hello World!". The steps involved are similar to those described above for the SimpleProgram.cs example, but there is some extra code for making sure the numbers d and e are valid.

The string "Hello World!" is 12 characters long, which in Unicode, is 24 bytes, or 192 bits. The value of N=pxq must be larger than 192 bits, so both p and q must be at least 192/2 bits, or 96 bits. However in this example I am using 512 bit prime numbers to demonstrate handling jumbo integers.
A     Convert the message M into a JumboInteger.

The message is converted into an array of bytes, and then into a JumboInteger object, M, as follows:

byte[] bufferPlainText = Encoding.Unicode.GetBytes(strMessage);
JumboInteger M = new JumboInteger();
M.SetRaw(bufferPlainText);

B Generate two distinct prime numbers p and q.

Start by choosing prime number p, 512 bits wide.

JumboInteger p = new JumboInteger();
p.MakeRandomPrime(uiBits);

Next, choose prime number q, making sure that q does not equal p.
C Calculate N = p x q

Declare another JumboInteger, N, and set it to the product of prime numbers p and q.

JumboInteger N = p * q;

D Choose numbers e and d

Firstly, calculate a number phi = (p-1) x (q-1) as this will be repeatedly used from now on.

JumboInteger phi = (p - 1) * (q - 1);

The value of e must be between 1 and N, and less than 64000. The number e must also be relatively prime to phi, that is, the numbers e and phi must not share any divisors.

The number d must be the modular inverse of e and phi. The modular inverse can be calculated as follows:

ed == 1 % phi

E Publish the public key, hide the private key

In RSA the key pair consists of a public key and a private key. The public key consists of two numbers, e and N. The private key is the number d.
F Calculate the ciphertext

The ciphertext is calculated from the following formula:

C = Me % N

C is the encrypted message as a JumboInteger, M is the original message, e is the public key exponent, and N was calculated from p and q.

Note that this function is written:

JumboInteger C = M.PowerMod(e, N);

and not:

JumboInteger C = M.Power(e) % N;

Raising a number to the power of d would take forever, even if d is relatively small. But there is a mathematical shortcut that can be employed if the result is being modulated, and this shortcut is in the PowerMod function.
G Decrypt the ciphertext and convert it back into a string

The ciphertext can be decrypted using the private key:

M = Cd % N

In the code, this function is represented as:

JumboInteger M2 = C.PowerMod(d, N);

Once C is decrypted to M2, M2 is converted back into a string value, and displayed.

In reality, the RSA algorithm is slow and processor-intensive compared to block ciphers such as DES and IDEA. RSA is rarely used for encrypting whole messages or real-time encryption of audio. Instead, RSA is used as a key wrapper for fast single-key encryption algorithms.

For example, a message could be encrypted using the DES algorithm, and a randomly generated DES key. This DES key is then encrypted using an RSA public key. The recipient of the message decrypts the wrapped DES key with their private RSA key, and deciphers the message. This use of RSA as a key-wrapper has the benefits of a fast encryption algorithm and no key-distribution problem.

MORE INFORMATION

Wikipedia - RSA

Wikipedia - Public Key Cryptography

Wikipedia - The Miller-Rabin Primality Test

Bletchley Park - World War II Code Breakers

SOFTWARE WORKSHOP SUPPORT
If you have any questions or have found an error, or would like more explanation of one of the items in the Software Workshop please contact Software Support.

Return to the Software Workshop.
Return to the Home Page.
Broccoli Products Ltd © 1998-2010 Broccoli Products Ltd
Reg Number: 2895355
Reg Office: 27 Old Gloucester Street, London. WC1N 3AX 		Bug Report Form Privacy Policy
Copyright Notice
Liability Disclaimer
Contact Us