RSA with small numbers

Introduction

I was inspired to do this demo by a marvellous essay on RSA encryption on www.muppetlabs.com. The RSA keys used by your browser are 1024-bit numbers, which are a little hard to check by hand.  This demo allows you to create your own RSA key pair using any prime you like up to 241. This makes it much easier to see what's going on, but I wouldn't rely on it to keep your credit card number safe.  (I know that IE's Help About says "Cipher Strength 128-bit".  This refers to the 128-bit symmetric encryption keys used for SSL sessions ('symmetric' means that the decryption process is just the reverse of the encryption process).  But 1024-bit RSA keys are used for the exchange of the session keys between client and server.  A good 1024-bit RSA key is thought to be about as secure as a 128-bit symmetric key but it is much slower, so it is used just to kickstart the symmetric session).

Click here to run the demo (requires .NET CLR).

Click here to download all the source code (rsa.zip - 10 KB)

The C# files:

• RSAEncryptor.cs - key generation and encryption logic
• frmMain.cs - the UI

Using the demo

To create a key pair, fire up the demo and enter two primes p and q . 7 and 29 are a good example.  The demo starts by displaying n (the product of the two primes) and Φ(n) (the number of integers between 1 and n-1 that have no factors in common with n).  Even I can prove that if p and q are primes then
Φ(n) = (p-1) * (q-1), so it's easy for us to compute even though it is the great secret at the heart of the code.  Now the demo tries to find d and e such that de = cΦ(n) + 1 for some integer c (with a couple of other restrictions).  When it finds these, you've got yourself an RSA public and private key pair.  For the primes 7 and 29 the demo will give you the key pair private (n=203, d=5) and public (n=203, e=101)

The next step is to use it.  The first thing to recognise when composing a message is that you can't encrypt just any number.  You can only encrypt a number between 2 and n-2 that has no factors in common with n.  In real life, you could ensure this by encrypting only numbers less than the smaller of p and q; since p and q would be 512 bits long there would be no shortage of messages.  The owner of the key could publish an upper bound for messages that would give no clue about p and q.

The second point is that you can encrypt the message using either the public or the private key, as long as you make sure that you use the other key to do the decryption!  Encrypting with the public key is what someone does when they want to send the message to you.  Encrypting with the private key is what you do when you want to digitally sign the message.

Enter your 'message' number and click either the 'Encrypt using public key' or 'Encrypt using private key' button.  Using our example, the encryption of the number 6 using the private key is:

6⁵ mod 203 = 62

And the encryption of 62 using the public key is:

62¹⁰¹ mod 203 = 6   - back to the original message!

The last section of the demo shows the complete public and private encipherments for your key pair.  The key is used to encipher each integer from 2 to n-2, excluding those that are multiples of p or q.  Two features to notice are:

• If a is enciphered as b by the public key, then b will be enciphered as a by the private key, and vice versa
• Every number in the table is enciphered to another number in the table (sometimes a number may be enciphered to itself)

Note: An RSA key is safe only if it is impractical to factorise n into p and q, because p and q reveal Φ(n) which, combined with e, reveals the secret number d.  This is why in real life the primes need to be so big.  Also, when creating a real RSA key you need to be a bit careful in your prime number selection.  Some big primes will produce an n that is vulnerable to factorisation tricks.  Please see mathworld.wolfram.com/RSAEncryption.html  for details.

The modpower function

In order to do encryption and decryption with our keys we need a function that computes a^b mod c. The trouble is that a^b will be way too big for a 32-bit integer type, even though for our purpose a is less than c. So we need a way to break it down.

The first thing to recognise is that xy mod c = ( x mod c )( y mod c ) mod c.
For example, consider x = 17, y = 8, c = 6:

xy mod c = 136 mod 6 = 4

x mod c = 17 mod 6 = 5

y mod c = 8 mod 6 = 2

( x mod c )( y mod c ) mod c = 5 * 2 mod 6 = 10 mod 6 = 4

Now, let's break b down into its binary representation.  For example, consider b = 23:

23 = 16 + 4 + 2 + 1 = 2⁴ + 2² + 2¹ + 2⁰ (ie the binary representation is 10111₂)

So a²³ = a^{2^4 + 2^2 + 2^1 + 2^0} = a^{2^4}.a^{2^2}. a^{2^1}. a^{2^0}

Thus a²³ mod c = a^{2^4}.a^{2^2}. a^{2^1}. a^{2^0} mod c

= a^{2^4} mod c . a^{2^2} mod c . a^{2^1} mod c . a mod c

This allows us to deal with each 'bit' separately.  To handle bit 2, for example, we must compute a^{2^2} mod c. We can also see that we can ignore the bits that are zero. 

Now a^{2^2} = (a²)²

Once again we can break this down, because a^{b^d} mod c = ((a^b mod c) ^d) mod c, so

(a²)² mod c = ((a² mod c)²) mod c

We can handle this as long as we can handle the square of any number < c.  (Incidentally, for 32-bit arithmetic this limits c to 65,536. Since c in our case is the product of two primes that should be of similar magnitude to each other, our primes will be ≈ 256.  The demo enforces a limit of 241 on each prime to ensure that we don't get any overflows).

 Now look at a^{2^3} mod c = ((a²)²) ² mod c.

This can be rewritten as (((a² mod c)²) mod c) ² mod c

This includes the term ((a² mod c)²) mod c that we already calculated when handling (a²)², and we can see a pattern emerging:

• To handle the 0^th bit, we compute (a mod c).  Call this residual₀
• To handle the 1^st bit, we compute (residual₀² mod c). Call this residual₁
• To handle the 2^nd bit, we compute (residual₁² mod c). Call this residual₂
• To handle the n^th bit, we compute (residual_n-1² mod c).  Call this residual_n

 Then a^b mod c = residual_i . residual_j . residual_k ... mod c,

where residual_i , residual_j , etc are the residuals for the non-zero bits of b. Computing the residuals is an O(log₂ b) operation, and multiplying them together is another O(log₂ b) operation.