Public-Key Encryption by RSA Algorithm

Objective

The purpose of this page is to demonstrate step by step how a public-key encryption system works. We use the RSA algorithm (named after the inventors Rivest, Shamir, Adleman) with very small primes. The basic functions are implemented in JavaScript and can be viewed in the source.
Note: This page is only for explaining the mechanism. In practice more advanced algorithms und much larger primes are used!
(Idea and most code taken from a no more existing student's page at University Honors College (Oregon State), a more realistic demo-implementation can be found here.)

Overview

Working with a public-key encryption system has mainly three phases:

Key Generation: Whoever wants to receive secret messages creates a public key (which is published) and a private key (kept secret). The keys are generated in a way that conceals their construction and makes it 'difficult' to find the private key by only knowing the public key.
Encryption: A secret message to any person can be encrypted by his/her public key (that could be officially listed like phone numbers).
Decryption: Only the person being addressed can easily decrypt the secret message using the private key.

RSA Key Generation

From two selected primes the computer will generate the public and the private key:

Pick 2 (different) primes: p = q =

n = (n = p.q)

φ = (φ = φ(n) = (p-1).(q-1); needed to determine e and d)

e = (arbitrary, but less than n and relatively prime to φ)

d = (inverse of e modulo φ: e.d mod φ = 1)

From these numbers the keys are composed:

the public key is the pair (e,n).
the private key is the pair (d,n).

Only the public key (e,n) is published; all the other numbers involved (p,q,φ,d) must be kept private! The main property of this construction is that it is 'difficult' to compute d just from the numbers e and n ('difficult' in the sense that the computation is more and more time-consuming the larger numbers are involved). More precisely:

It is 'difficult' to compute d without knowing φ.
It is 'difficult' to factorize n into p.q (which is needed for computing φ).

RSA Encryption

First of all we need the public key of the person to whom we want to send the message:
(e,n) = ( , ) (Enter appropriate values or )

Next we need the message. For simplicity let us demonstrate this here with just one letter. (In secure applications letters are never encrypted individually, but in whole blocks.)
Pick a letter to cipher:
Before we can encrypt this letter we must :
m = (here we take just the index in the alphabet)

itself is very simple: m' = (m' = m^e mod n)

The value m' is the encrypted message sent to the receiver.

RSA Decryption

First of all we need the private key of the person who got the encrypted message:
(d,n) = ( , ) (Enter appropriate values or )

Next we need the encrypted message:
m' = (Enter an appropriate value or )

again is very simple: m = (m = m'^d mod n)

The should match with the above chosen letter:

Auxiliary Functions (for Testing)

Greatest common divisor (GCD)

That two numbers are relatively prime means that they have no divisor in common, i.e. their GCD (greatest common divisor) is 1. The greatest common divisor can be efficiently computed via the Euclidean Algorithm.

Cofactors (extended GCD)

The greatest common divisor d of two numbers m and n can be written as a linear combination of these two numbers: d = c₁.m + c₂.n The numbers c₁,c₂ are called cofactors and can be computed via a simple extension of the Euclidean Algorithm (extended GCD-computation).

The computation of the cofactors is useful for finding the (multiplicative) inverse of a number n w.r.t. a module m. Given two relatively prime numbers m,n, such that their GCD is 1 we have for the cofactors:

1 = c₁.m + c₂.n Looking at this equation modulo m, we get: c₂.n mod m = 1 Hence c₂ is the (multiplicative) inverse of n modulo m.

Power modulo m

Both encryption and decryption need a power reduced modulo a module m. If the whole power is computed before starting the modulo computation, this may be very inefficient and involve large numbers. Therefore, a more efficient method reducing already the intermediate powers modulo m is used.