RSA cryptosystem

In this post we will introduce some ideas behind the RSA cryptosystem, and present a simplified javascript implementation.

Motivation

 The RSA cryptosystem (Ron Rivest, Adi Shamir, Leonard Adleman; 1977) is one of the pioneers of public key cryptosystems.
  A public key cryptosystem is based on a pair of keys: Ke (encryption), Kd (decryption) in witch we expect that is not viable to encipher/decipher text without knowing the respective key and we expect that is trivial knowing it. Here we use some imprecise words, by not viable we mean that it's very expensive computationally and can't be done in a reasonable amount of time and by trivial we mean that it's inexpensive computationally.
  RSA uses as motivation two facts of the current state of number theory:

1. There is no quick algorithm known to factorization a large number.
2. It's very quick to test if a number is prime.

  If in the next years someone discover a quick algorithm for factorization, the RSA will no longer be useful. But this is very unlike to happen, given that there is a long history of tries.

How it works

  We choose two large primes: p, q; and set:

n = pq. 

 Again our assumption is that is rather easy for a computer to find two large primes p, q. But knowing n we cannot find the factors p, q in a reasonably amount of time.

  Next we choose a number e, that has no common factor to (p - 1)(q - 1) (for example choose an e that is a prime number) and have the propriety that:

max(p, q) < e < (p - 1)(q - 1).

  After that we find:

d ≡ e^-1 mod (p - 1)(q - 1).

For a reference on how to solve this equation take a look at here!
In this situation we will have that:

1. Ke = (n, e).
2. Kd = (n, d).
3. ƒ(P) ≡ P^e mod n    where P stands for plain text.
4. ƒ^-1(C) ≡ C^d mod n   where C stands for cipher text.

A sketch of proof

 Now we have to prove our assumption, witch is by no means obvious, that encipher and then deciphering will return the plain text:

P ≡ ƒ^-1(ƒ(P)) ≡ ƒ(ƒ^-1(P)) ≡ P^ed (mod n). 

 For this proof we will use Fermat's little theorem:

x^p-1 ≡ 1 (mod p)

for any prime p and any number x that is not divisible by p 

Proof:

(0.x (mod p), 1.x (mod p), 2.x (mod p), ... , (p - 1).x (mod p))

is a rearrangement of the sequence

(0, 1, 2, ...,  (p - 1)) 

Suppose that is not true, so there is:  

i, j (0 ≤ i, j < p and i ≠ j) with:

 i.x ≡ j.x (mod p) 

i - j ≡ 0 (mod p)

This is obviously false because p is prime. 

1.x . 2.x . ... . (p - 1).x ≡  1 . 2 . ... . (p - 1) (mod p)

x^p-1.(p - 1)! ≡ (p - 1)! (mod p)

Since p does not divide (p - 1)!

x^{p - 1} ≡ 1 (mod p)

And we finish our proof.

Now we are in condition to prove:

P  ≡ P^ed (mod n).

Proof:

First of all, we have to notice that what we want to prove is equivalent

(1) P  ≡ P^ed (mod p)
(2) P  ≡ P^ed (mod q).

Because p and q are relative primes. Now since:

e.d  ≡ 1 mod (p - 1)(q - 1)

We have that:

e.d - 1 = (q - 1).(p - 1).λ

for λ some positive integer. So if q does not divide P,  we have in (2):

P^ed ≡ P^ed-1.P ≡ P^{(q - 1)(p - 1)λ}.P ≡ (P^{(q - 1)})^{(p - 1)λ}.P (mod q)

Now by Fermat's little theorem we know that:

P^{(q - 1)} ≡ 1 (mod q)

So we can conclude:

P^ed ≡ (P^{(q - 1)})^{(p - 1)λ}.P ≡ 1^{(p - 1)λ}.P ≡ P (mod q).

Notice that if q divides P equation (2) is trivially true, and we can proceed in same fashion for equation (1). Now we finish our proof.

 

Javascript implementation

   Now we want to have some practical feeling about the algorithm. First of all we need to program a function to do the dirty work in modular exponentiation:

x^e   (mod m)

function modexp (x, e, n){
 if (e == 0)
  return 1;
 if (e == 1)
  return x % n;
 if (e % 2 == 0)
  return modexp ((x * x) % n, e / 2, n);
 return (x * modexp (x, e - 1, n)) % n; 
}

  We will work with the ASCII printable characters (95 total): empty space (code 32) to tilde (code 126), both for the plain and the cipher text, we will use every letters in plain text as P, and we will return 2 letters as C, so:

95¹ < n < 95²

  Obviously this situation is not what is used by your bank in real transactions. Here is our encryption function:

function RSA_encrypt (plain, n, e){
 var min = 32;    // first character
 var max = 126;    // last character
 var rng = max - min + 1; // total number
 
 var cipher = "";
 for (var i = 0; i < plain.length; i++){
  x = plain.charCodeAt(i) - min;
  x = modexp(x, e, n);
  
  k1 = Math.floor(x / rng) + min;
  k2 = x % rng + min;

  s = String.fromCharCode(k1, k2);
  cipher = cipher.concat(s);
 }
 return cipher;
}

 Here is our decryption function:

function RSA_decrypt (cipher, n, d){
 var min = 32;    // first character
 var max = 126;    // last character
 var rng = max - min + 1; // total number

 var plain = '';
 for (var i = 0; i < cipher.length; i+=2){
  x = (cipher.charCodeAt(i) - min) * rng;
  x += cipher.charCodeAt(i + 1) - min;
  x = modexp(x, d, n);
  plain = plain.concat(String.fromCharCode(x + min));
 }
 return plain; 
}

And here this code in action for:

(n, e, d) = (2047, 179, 411)

Type something:

The cipher text:

The plain text:

For understand how we get the values (n, e, d) take a look at here!