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!
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:
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 = c1.m + c2.n
The numbers c1,c2 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 = c1.m + c2.n
Looking at this equation modulo m, we get:
c2.n mod m = 1
Hence c2 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.