Public-Key Encryption by RSA Algorithm
The purpose of this page is to demonstrate step by step how a public-key encryption system
We use the RSA algorithm (named after the inventors Rivest, Shamir, Adleman) with very small primes. The basic functions are
Note: This page is only for explaining the mechanism. In practice
more advanced algorithms und much larger primes are used!
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,
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
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
math page | start page