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:
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:
- There is no quick algorithm known to factorization a large number.
- It's very quick to test if a number is prime.
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:
In this situation we will have that:
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:
- Ke = (n, e).
- Kd = (n, d).
- ƒ(P) ≡ Pe mod n where P stands for plain text.
- ƒ-1(C) ≡ Cd mod n where C stands for cipher text.
A sketch of proof
P ≡ ƒ-1(ƒ(P)) ≡ ƒ(ƒ-1(P)) ≡ Ped (mod n).For this proof we will use Fermat's little theorem:
xp-1 ≡ 1 (mod p)
for any prime p and any number x that is not divisible by pProof:
(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)
xp-1.(p - 1)! ≡ (p - 1)! (mod p)
Since p does not divide (p - 1)!
xp - 1 ≡ 1 (mod p)
And we finish our proof.
(2) P ≡ Ped (mod q).
Now we are in condition to prove:
P ≡ Ped (mod n).
Proof:
First of all, we have to notice that what we want to prove is equivalent(1) P ≡ Ped (mod p)
(2) P ≡ Ped (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):
Ped ≡ Ped-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:Ped ≡ (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:
xe (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:
951 < n < 952Obviously 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)
For understand how we get the values (n, e, d) take a look at here!
P ≡ Ped (mod n).
ReplyDeleteProof:
First of all, we have to notice that what we want to prove is equivalent
(1) P ≡ Ped (mod p)
(2) P ≡ Ped (mod q).
can you explain this part please.