Public Key Encryption
Introduction

Task

Data Dictionary

Teacher's Tools

Bit Commitment

Blinding

Certificates

Digital Signatures

Key Distribution

Public Key

Secret Splitting

Security Basics

Symmetric Key



 Public Key Encryption involves a pair of keys.  One key is public, the other key is private.   The public key is published and can be easily found.  The private key is kept secret.  However, there is a special relationship between the public key and the private key that is shown by the following two drawings:

The original data can be encrypted with one key and decrypted with the other key.   While it is mathematically possible to use either key to encrypt or decrypt, there are definite reasons to use one method instead of the other.  If the top method is used, data will be encrypted with a public key, and only the individual that has the corresponding private key can decode the information.   Since the private key is a secret, there is only one individual that can decode the information.  If the bottom method is used, then anyone can decode the message.  The public keys are published and readily available.   The keys can be published into a database on a server that is accessible from the internet.  Therefore, more secure transmissions should use public key encryption. 

However, the bottom method still has its uses.  It can be used if the data can be interpreted by anyone who has access to the public key.  This is useful in e-commerce since many applications need access to your public key to verify that the data you are sending it is correct.  Most monetary transfers on the Web occur using the bottom method of public key cryptography.  Typically, the top method is used when a sender is encrypting an entire message and the receiver is decrypting it.   The bottom method is used when the sender uses a digital signature.

The backbone of public key cryptography is that a private and public pair of keys must be generated.  A popular algorithm for generating public and private keys is the RSA Algorithm.  RSA stands for Rivest, Shamir, Adleman, who are the gentlemen who developed the algorithm.   The algorithm is described below:

  1. Pick two prime numbers, p and q.
  2. Calculate N which is the product of p and q.
  3. Calculate L which is the product of (p-1) and (q-1)
  4. Pick a number e which is not a factor of L and is also prime.  N and e are the public key.
  5. Solve the following equation for d:   (de)mod(L)=1  d is the private key.

Note that the mod function returns the remainder.  Syntactically, you have the following situation:

Remainder = Number mod(divisor)

In an excel spreadsheet, you would enter this as:

Remainder = MOD(Number, divisor)

To encrypt a message, M,  the public key is typically used.   Therefore, the encryption is accomplished by the following equation:

C = Memod(N)

The scrambled data, C, can be decoded by the private key, d, by using the following algorithm:

M=Cdmod(N)

A simple example of this entire algorithm is presented below:

  1. Pick the two prime numbers to be p = 7 and q = 17.

  2. Calculate N. N= (7)(17) = 119

  3. Calculate L.  L = (6)(16) = 96

  4. Pick e = 5.

  5. Solve the following equation:  d*5mod(96)=1.  d = 77

Applying the encryption algorithm on a message, M=19, shows the following to be true:

C=195mod(96)=67

Decrypting with the private key shows the following to be true:

M=6777mod(96)=19

The RSA algorithm will typically use very large prime numbers. 

The RSA algorithm has specific rules about when to encrypt or decrypt using public and private keys.  The table below summarizes the use of the keys.

Action Key to Use
Send an encrypted message Use the receiver's public key
Decrypt an encrypted message Use the receiver's private key
Send an encrypted signature Use the sender's private key
Decrypt an encrypted signature to authenticate the sender Use the sender's public key

For more information on digital signatures, click here.

The success of the RSA algorithm is based on the prime numbers being quite large.  It will take a computer a very long time to factor L into two prime number parts.  The difficulty occurs since large prime numbers are very difficult to find.   In addition, it is very mathematically intensive to factor numbers.  Therefore the strength of the algorithm is based on the time that it would take to crack it. 

For more information on public key cryptography:

  1. "Public Key Cryptography" by Davin McCall is available http://yoyo.cc.monash.edu.au/~davmac/algrthm/pkc.htm. 1999.  Good reference for the creation of keys, encryption, and decryption.
  2. "RSA" by Serge Hallyn is available at http://www.cs.wm.edu/~hallyn/public_key/rsa.html.  March 29, 1996.
  3. "Public Key Cryptography"  by David Cyganski is available at  http://www.ece.wpi.edu/infoeng/textbook/node214.html.  February 17, 1998.
  4. "Using RSA Public Key Cryptography for Internet Security" by Pablo Mazzara  is available at http://www.iie.edu.uy/~mazzara/pgp/RSA.htm.  March 23, 1996.
  5. "Thirteen Reasons to Say 'No' to Public Key Cryptography" by Thierry Moreau is available at http://www.connotech.com/13REAS.htm.  March 4, 1998.
  6. "Problems & Attacks on RSA" by Jarrod Ammann, Mahesh Balaji, James Bolton, Khalifah Hamzah, John Stajdl, and Kris Zoerhoff is available at http://www.ee.mtu.edu/courses/ee465/groupa/problems.html.