RSA Demo Applet

You may wish to read an overview of RSA Public Key Cryptography.

To operate the demo:

• Provide values for p and q (where p and q are prime numbers. Try p = 223 and q = 199) and click on the Calculate N button. This will calculate the value of N (called the modulus). It will also provide values for E and D (the public and private exponents) such that:
  1. E < n
  2. E is Relatively Prime to (p - 1) * (q - 1)
     This means that E and (p - 1) * (q - 1) have no common factors except 1
  3. E * D - 1 is evenly divisible by (p -1) * (q - 1)

  We call (E, N) the Public Key and (D, N) the Private Key.

  To start with, you might want to just leave the values of p and q as they are. The reason is that if p and q are too small, then N will be smaller than the values we are trying to encrypt or decrypt. When this happens, the system does not work properly.

  Just as a check, it seems N should be greater than 40,000. This will allow all of the ASCII characters up to 128 to be encoded without problems.

• Next type a short message into the M field and click on the Encrypt button. This will encrypt your message by combining two letters at a time into a block. Each block will be encrypted using the RSA algorithm:
  block^E mod N

  The result will be the encrypted message shown in the Ciphertext field.

• Clicking on the Decrypt button will then reverse the process by decrypting each of the encrypted values using the RSA algorithm:
  block^D mod N

Your comments and suggestions are welcome: Richard Holowczak richard_holowczak@baruch.cuny.edu

Overview of RSA Public Key Cryptography

A digital Key is a set of bits that are used to encrypt and decrypt messages. A form of cryptography called Public key cryptography uses two different keys:

• A Public Key which is used is used to encrypt messages.
• A Private Key is used to decrypt ciphertext and reveal the original message.

Public and Private keys are generated in pairs so that only a specific pair of keys can perform the encryption and decryption functions. Any keys other than the specific pair will not work. A Public key is made known to everyone in the world. The matching private key is kept a secret by its owner.

In the following example, Alice would like to send a message to Bill. She uses Bill's Public Key (which everyone knows) to encrypt the message. The ciphertext is then sent to Bill. Once he receives it, he can decrypt the ciphertext using his Private key. Only Bill's Private key can be used to decrypt.

RSA is a particular form of public key cryptography named after its inventors: Ronald Rivest, Adi Shamir, and Leonard Adleman in 1977. In RSA cryptography, a public and private key pair are generated using the following steps:

• Choose two large prime numbers p and q
  Generally, p and q are over 100 digits long.
• Compute the value of the modulus n as: n = p * q
• Choose a key E that is relatively prime to (p-1) * (q-1)
  Choose a key D such that E*D = 1 mod (p-1) * (q-1)
  In other words, E*D - 1 is evenly divisible by [ (p-1) * (q-1) ]

• The Public Key is the combination of (E,n)
  This is used to encrypt messages.
• The Private Key is the combination of (D,n)
  This is used to decrypt ciphertext and reveal the original message.

Given a Message M, to encrypt into ciphertext C, we use the following formula:
C = M^E mod n
Our public key is (E, n)

Given a Ciphertext C, to decrypt into plaintext message M we use the following formula:
M = C^D mod n
Our private key is (D, n)

In practice, the message M is broken up into blocks (e.g., 64 bits at a time) and processed by the encryption algorithm.

The strength in RSA lies in the difficulty of factoring n. That is, guessing p and q given only the value of n. Currently this is a difficult problem in mathematics. A brute force approach, that is trying all potential p and q would take many thousands of years (depending on the size of the original p and q).

As the number of digits in p and q grow large, factoring becomes more difficult. So we consider the Key Size as directly related to the strength of the encryption. With n at 512 bits (154 digits), we consider this to be strong encryption. Total key size (E, n) or (D, n) would be 1024 bits.

Details of RSA cryptography and other cryptography techniques can be found in the RSA web site: http://www.rsa.com

In particular, the 216 page FAQ contains a significant number of definitions of concepts related to security, cryptography and Electronic Commerce.

How does this demo work?

Java to the Rescue

I had originally attempted to provide a demo using several other tools such as MS Excel, JavaScript and others. However, I kept running into the problem that as the numbers got very large, these environments could not represent them accurately. I could have written something in C++ (which includes classes for arbitrary sized integers), however, I wanted something that would be easily portable and accessible over the web. Fortunately, I came across a special feature of Java called the bigInteger class described here.

This demo was written in the Java programming language. Specifically, it runs within a web browser as what is called a Java Applet. It was developed using the Java Development Kit version 1.1. The JDK 1.1 includes a special class called bigInteger that allows arbitrarily sized integers to be stored and operated upon. For example, the E, N and D are all represented as type bigInteger in the applet.

Generating the Public and Private Keys

The first part of the demo provides text boxes where the user can supply the values of p and q. Ideally p and q should be large prime numbers, however for the purposes of this demo, relatively small (less than 1000) values can be used. Presently simple checks are done on p and q to see if they are indeed prime.

Once p and q have been specified, clicking on the Calculate N button will generate the modulus n as p * q and will also calculate (p-1) * (q-1) which is used for other calculations later on.

The value of E is then automatically suggested as a number that is relatively prime to (p-1) * (q-1). This is accomplished by looping a variable from 2 to N and checking to see if the greatest common divisor (GCD) of this variable and (p-1) * (q-1) is one. Typically, the variable reaches 5 as its choice for E. Fortunately, the bigInteger class includes a method called gcd(bigInteger) that returns the GCD of two bigIntegers.

The value of D is then suggested by computing the mod-inverse of E. This gives a value for D such that E*D = 1 mod (p-1) * (q-1)

Once again, the bigInteger class comes to the rescue with a method called modInverse. This method is used to derive D given the value of E.

Encrypting a Message

At this point, we have now generated the necessary Public Key (E,n) and Private key (D,n). A message can be typed into the message field (labled M) and the Encrypt button can be clicked on.

Clicking on the Encrypt button causes the following steps to take place:

1. Each letter in the message is represented as its ASCII code number. In ASCII, 'A' is coded as 65, 'B' is coded as 66 and so on.
   Click here to see a list of ASCII codes.
   For this example, the message "Secret!" is coded as: 83 101 99 114 101 116 33
2. Each ASCII code number is then represented in binary notation using 8 bits.
   For this example, the binary codes become: 01010011 01100101 01100011 01110010 01100101 01110100 00100001
3. Each pair of characters is then assembled into blocks. This is done by taking two 8 bit numbers and representing them side by side as one 16 bit number. In this example, there are 7 original characters that form 4 blocks:
   0101001101100101 0110001101110010 0110010101110100 0000000000100001
   Note that the last character is padded with zeros.
   Real applications of RSA use blocks of up to 8 or 16 characters each (64 or 128 bits in length).
4. Each message block is then represented as a decimal number that will be encrypted. For this example, the code blocks in decimal are:
   21349 25458 25972 33
5. Each number is then encrypted using the RSA formula: block^E mod N. The first block will be encrypted using: 21349⁵ mod 44377
   The encrypted numbers are: 25743 38082 24556 39256
6. Finally, each encrypted block is (internally) represented as a 16 bit binary number that is split into two 8 bit numbers and then displayed as the ASCII character equivalents: J&7'
   Note that some ASCII characters can not be displayed which is why you might see some garbage characters or simply blank boxes.

Decrypting a Ciphertext

Decrypting a message uses the RSA decryption algorithm block^D mod N to decrypt the encrypted message blocks. Clicking on the Decrypt button causes the following:

1. Each encrypted code block in the Ciphertext is run through the decryption algorithm. For example, the first encrypted block: 25743³⁵¹⁶⁵ mod 44377
2. Each decrypted block is then represented as a 16 bit binary number. This 16 bit binary number is split into two 8 bit binary numbers that represent the ASCII characters of the original message M.
3. Each 8 bit number is represented as an ASCII character in the final field.

Acknowledgments

This program was inspired by this JavaScript example of RSA designed by Cary Sullivan and Rummy Makmur. (sullivca@ucs.orst.edu and makmur@flop.engr.orst.edu).

Additional Links

• http://islab.oregonstate.edu/koc/ece575/02Project/Mor/
• http://homex.coolconnect.com/member2/wailian/QuickStartRSA/

Even better, if the above links are not working, just do a search on Google for "RSA demo java applet"