RSA encryption is probably the the most well known type of encryption.  It was invented in the late 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman.  Most descriptions/explanations of the algorithm involve heavy math that tends to scare people away.  This is unfortunate as the only prerequisite for understanding the algorithm is a decent background in algebra.  I'll try to cover the basics in this article.

A High-Level Overview

RSA is classified as a public key infrastructure (PKI).  In the RSA cryptosystem, each participant has a public key and a private key.  The public key is published to, well the public.  The private key remains private to the participant that owns the key.  When a message is transfered between two participants, the sender of the message looks up the receiver's public key.  The message is then encrypted with this key and send to the receiver.  The message can only be decrypted with the private key.

What Exactly Makes a Key a Key

Keys in most cryptosystems are integers, but not just an arbitrary integer.  The keys are generated in pairs in a manner which makes the cryptosystem secure.  Specifically, in RSA encryption the keys are pairs of integers (X, Y)private and (X, Y)public

Key Generation

This is where the math usually starts to become unnecessarily complicated, and scare people away.  I'm going to tone things down to a reasonable level.

There are 3 main steps in generating RSA keys.

  1. Pick two prime numbers, name then P and Q.
  2. Pick a 3rd, different, prime number, E, such that  1 < E < PQ and E does not divide ((P-1)(Q-1)) evenly.  (E doesn't necessarily have to be prime, but it makes things the easiest.  by definition E must be relatively prime to ((P-1)(Q-1)), meaning no common prime factors).
  3. This is the most difficult part.  Compute D such that D is the multiplicative inverse of E mod ((P-1)(Q-1)).

Public key is the pair (PQ, E), and the private key is the pair (PQ, D).

Example:

 

  1. P=13, Q=23, PQ = 299, (P-1)(Q-1) = 264
  2. E = 29
  3. To calculate D, use the method known as the “The Extended Euclidean Algorithm“

 

  • Step 0:  264 = 29*9 + 3;   p0 = 0
  • Step 1:  29 = 9*3 + 2;       p1 = 1
  • Step 2:  3 = 1*2 + 1;         p2 = (0 - 1*9) mod 264 = 255
  • Step 3:  2 = 2*1 +0;          p3 = (1 - 255*9) mod 264 = 82
  • Step 4:                              p4 = (255-82*1) mod 264 = 173

D = 173

This give the following keys:

Public (299, 29)

Private (299, 173)

Encrypting/Decrypting

This part is trivial.  To encrypt a message T apply the equation C = ( TE ) mod PQ.  The result, C, is the encrypted message (cypher text).  To decrypt a message apply the equation T = ( CD ) mod PQ.

Example:  Given our key pairs from above. 

To encrypt the message “2“:   C = (229) mod 299 = 266

To decrypt the cipher text “266“:  T = (266173)mod 299 = 2

Note: even if you know the public key, (299, 29), and the message “266” there is no way to decrypt the message, without having the private key.  Well, almost no way.