 |
Web Development »
Client side scripting »
General
Intermediate
Encryption - RSA implemented through Java Script to Encryt/Decrypt dataBy Gaurav SainiDemonstrate the use of RSA algorithm in HTML pages |
Javascript, Java, Win2K, Visual-Studio, Dev
|
|
Advanced Search Add to IE Search |
|
|
|
||||||||||||||||
RSA is a public key cryptosystem for both encryption and authentication; it was given by three scientists viz. Ron Rivest, Adi Shamir and Leonard Adleman. This algorithm is much secure than any other algorithm. The latest key size used for this encryption technique is 512 bits to 2048 bits.
With the advent of computers it has become possible to perform computations at teraflop speeds so such algorithms could easily be cracked. But RSA encryption uses the concept of two large prime numbers, such that, their product could not be easily factorized. Let us see how this algorithm works and understand its implementation using Java Script.
RSA uses modular arithmetic. This is similar to conventional arithmetic, but only uses positive integers that are less than a chosen value, called the modulus. Addition, subtraction and multiplication work like regular maths, but there is no division. You can use any value for the modulus; the diagram uses 13, so counting goes 0, 1, 2, ..., 11, 12, 0, 1, 2 ... The notation used for expressions involving modular arithmetic is:
x = y (mod m) Which reads as "x is equivalent to
y, modulo m". What this means is that x and y leave
the same remainder when divided by m. For example, 7 = 23 (mod 8)
and 22 = 13 (mod 9). The following statement is a basic principle of
modular arithmetic: a + kp = a (mod p)
You can visualize this on the diagram - each time you add p you go
round the circle, back to where you started. It doesn't matter where you start,
how big the circle is, or how many times you do it, it's always true.
This theorem provides a way to combine two modular equations that use different moduli.
|
Theorem |
||
 |
x = y (mod pq) | |
|
Proof |
||
|
x = y + kp | |
|
x - y = kp | |
|
p divides (x - y) | |
| by a similar route, q divides (x - y) | ||
| as p and q are coprime, pq divides (x - y) | ||
|
x - y = l(pq) | |
|
x = y (mod pq) | |
This theorem is a surprising identity that relates the exponent to the modulus.
|
Theorem |
p-1 = 1 (mod p) if p is prime and x  0 (mod p) | |
|
Proof |
||
as p is prime, these numbers are coprime to p | ||
| 0 is not coprime to p | ||
| Q includes all the numbers in (mod p) coprime to p | ||
| now consider the set U, obtained by multiplying each element of Q by x (mod p) | ||
| each element of U is coprime to p | ||
| i = xQj (mod p) with i j | ||
| Qi = Qj (mod p) as x 0 | ||
| elements of U are distinct | ||
| U is a permutation of Q | ||
| U1.U2 ... Up-1 = Q1.Q2 ... Qp-1 (mod p) | ||
| xQ1.xQ2 ... xQp-1 = Q1.Q2 ... Qp-1 (mod p) | ||
| 1.Q2 ... Qp-1 | ||
| xp-1 = 1 (mod p) | ||
This implementation of RSA uses 32 bit key. There are two files: input.htm and output.htm. The code for the input.htm file is as follows:
<html>
<head>
<title>Input</title>
<script language="JavaScript">
<!-- hide from old browsers
function gcd (a, b)
{
var r;
while (b>0)
{
r=a%b;
a=b;
b=r;
}
return a;
}
function rel_prime(phi)
{
var rel=5;
while (gcd(phi,rel)!=1)
rel++;
return rel;
}
function power(a, b)
{
var temp=1, i;
for(i=1;i<=b;i++)
temp*=a;
return temp;
}
function encrypt(N, e, M)
{
var r,i=0,prod=1,rem_mod=0;
while (e>0)
{
r=e % 2;
if (i++==0)
rem_mod=M % N;
else
rem_mod=power(rem_mod,2) % N;
if (r==1)
{
prod*=rem_mod;
prod=prod % N;
}
e=parseInt(e/2);
}
return prod;
}
function calculate_d(phi,e)
{
var x,y,x1,x2,y1,y2,temp,r,orig_phi;
orig_phi=phi;
x2=1;x1=0;y2=0;y1=1;
while (e>0)
{
temp=parseInt(phi/e);
r=phi-temp*e;
x=x2-temp*x1;
y=y2-temp*y1;
phi=e;e=r;
x2=x1;x1=x;
y2=y1;y1=y;
if (phi==1)
{
y2+=orig_phi;
break;
}
}
return y2;
}
function decrypt(c, d, N)
{
var r,i=0,prod=1,rem_mod=0;
while (d>0)
{
r=d % 2;
if (i++==0)
rem_mod=c % N;
else
rem_mod=power(rem_mod,2) % N;
if (r==1)
{
prod*=rem_mod;
prod=prod % N;
}
d=parseInt(d/2);
}
return prod;
}
function openNew()
{
var subWindow=window.open(
"Output.htm", "Obj","HEIGHT=400,WIDTH=600,SCROLLBARS=YES");
var p=parseInt(document.Input.p.value);
var q=parseInt(document.Input.q.value);
var M=parseInt(document.Input.M.value);
var N=p * q;
var phi=(p-1)*(q-1);
var e=rel_prime(phi);
var c=encrypt(N,e,M);
var d=calculate_d(phi,e);
subWindow.document.Output.N.value=N;
subWindow.document.Output.phi.value=phi;
subWindow.document.Output.e.value=e;
subWindow.document.Output.c.value=c;
subWindow.document.Output.d.value=d;
subWindow.document.Output.M.value=decrypt(c,d,N);
}
// end scripting here -->
</script>
</head>
<body>
<p><font size="6">Input Form</font></p>
<hr>
<form name="Input">
<table border="0" width="100%" height="109">
<tr>
<td width="24%" height="23">
<font color="#0000FF">Enter P</font></td>
<td width="76%" height="23">
<input type="text" name="p" size="20"></td>
</tr>
<tr>
<td width="24%" height="23"><font color="#0000FF">
Enter Q</font></td>
<td width="76%" height="23">
<input type="text" name="q" size="20"></td>
</tr>
<tr>
<td width="24%" height="20">
<font color="#0000FF">Enter any Number ( M )</font></td>
<td width="76%" height="20"><input type="text" name="M" size="20">
<font size="1" color="#FF0000">(1-1000)</font></td>
</tr>
<tr>
<td width="24%" height="19"><input type="button"
value="Submit" name="Submit" onClick="openNew()"></td>
<td width="76%" height="19"><input type="reset"
value="Reset" name="Reset"></td>
</tr>
</table>
</form>
<p> </p>
</body>
</html>
The code for the output.htm file is as follows:
<html>
<head>
<title>Output</title>
</head>
<body>
<p><font size="6">Output Form</font></p>
<hr>
<p><font color="#FF0000">1. N = p * q
</font></p>
<p><font color="#FF0000">2.
phi = ( p - 1 ) * ( q - 1
) </font></p>
<p><font color="#FF0000">3. GCD
( phi , e ) = 1</font></p>
<p><font color="#FF0000">4.
Encrypted Text ( c ) = M<sup>e</sup>
* ( mod N )</font></p>
<p><font color="#FF0000">5.
e * d = 1 * ( mod phi )</font></p>
<p><font color="#FF0000">6.
Decrypted Text = c<sup>d</sup> * (
mod N )</font></p>
<form name="Output">
<table border="0" width="100%">
<tr>
<td width="22%"><font color="#0000FF">N
</font></td>
<td width="78%"><input type="text" name="N"
size="20"></td>
</tr>
<tr>
<td width="22%"><font color="#0000FF">Phi</font></td>
<td width="78%"><input type="text"
name="phi" size="20"></td>
</tr>
<tr>
<td width="22%"><font color="#0000FF">e
</font></td>
<td width="78%">
<input type="text" name="e" size="20"></td>
</tr>
<tr>
<td width="22%"><font color="#0000FF">Encrypted Text
</font></td>
<td width="78%">
<input type="text" name="c" size="20"></td>
</tr>
<tr>
<td width="22%"><font color="#0000FF">d
</font></td>
<td width="78%"><input type="text" name="d" size="20">
</td>
</tr>
<tr>
<td width="22%"><font color="#0000FF">
Decrypted Text</font></td>
<td width="78%"><input type="text" name="M" size="20"></td>
</tr>
<tr>
<td width="22%">
<input type="button" value="Close" name="Close"
onClick="window.close()"></td>
<td width="78%"> </td>
</tr>
</table>
</form>
<p> </p>
</body>
</html>
Now, after creating the files you can run the input.htm file from your browser and provide the necessary values. Clicking the Submit button will open the output.htm file with the necessary outputs.
The code has been tested on IE 4.0 and above as well as on Netscape Navigator.
Suppose that B wants to send a message to A. A and B have exchanged their public keys. Let us try to understand how this works:
I would suggest that the readers should try to work on these topics so as to learn more about the RSA encryption scheme. I am having the necessary content, but I don't want to complicate the things write now.
Send your recommendations, suggestions and problems at email@gauravsonline.com
General 
News 
Question 
Answer 
Joke 
Rant 
Admin
Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads.
|
PermaLink |
Privacy |
Terms of Use
Last Updated: 9 Sep 2003 Editor: Nishant Sivakumar |
Copyright 2003 by Gaurav Saini Everything else Copyright © CodeProject, 1999-2010 Web17 | Advertise on the Code Project |
