加密 - 通过 JavaScript 实现的 RSA 数据加密/解密
4.72/5 (25投票s)
演示在 HTML 页面中使用 RSA 算法
引言
RSA 是一种用于加密和身份验证的公钥密码系统；它由三位科学家命名：Ron Rivest、Adi Shamir 和 Leonard Adleman。该算法比任何其他算法都更安全。该加密技术使用的最新密钥长度为 512 位至 2048 位。
随着计算机的出现，以 teraflop 速度进行计算已成为可能，因此此类算法很容易被破解。但 RSA 加密使用了两个大素数的概念，它们的乘积不容易被因子分解。让我们看看该算法的工作原理，并使用 JavaScript 理解其实现。
数学背景
模运算
RSA 使用模运算。这类似于常规算术，但仅使用小于选定值（称为模数）的正整数。加法、减法和乘法与常规数学一样，但没有除法。您可以使用任何值作为模数；图中使用 13，因此计数为 0、1、2、...、11、12、0、1、2 ... 涉及模运算的表达式使用的符号是
x = y (mod m)
读作“x 等价于 y，模 m”。这意味着 x 和 y 除以 m 的余数相同。例如，7 = 23 (mod 8) 和 22 = 13 (mod 9)。以下陈述是模运算的基本原理
a + kp = a (mod p)
您可以在图上可视化这一点 - 每次添加 p 时，您都会绕着圆圈回到起点。无论您从哪里开始，圆圈有多大，或者您执行多少次，这总是成立的。
素数和互素
- 如果一个数的唯一因子是 1 和它本身，那么它就是素数。例如，17 是素数，但 15 不是，因为它可以被 3 和 5 整除。
- 如果两个数的最大公约数是 1，则称它们互为素数。这些数本身不必是素数。例如，8 和 9 互为素数，但 8 和 10 不是，因为它们都可以被 2 整除。
- 如果有一对不同的素数，它们总是互为素数。
中国剩余定理
该定理提供了一种组合两个使用不同模数的模方程的方法。
|
定理 |
||
 |
x = y (mod pq) | |
|
证明 |
||
|
x = y + kp | |
|
x - y = kp | |
|
p 整除 (x - y) | |
| 类似地，q 整除 (x - y) | ||
| 由于 p 和 q 互为素数，pq 整除 (x - y) | ||
|
x - y = l(pq) | |
|
x = y (mod pq) | |
费马/欧拉定理
该定理是一个令人惊讶的恒等式，它将指数与模数联系起来。
|
定理 |
p-1 = 1 (mod p) 如果 p 是素数且 x  0 (mod p) |
|
|
证明 |
||
由于 p 是素数，这些数与 p 互为素数 |
||
| 0 与 p 不互为素数 | ||
| Q 包括 (mod p) 中所有与 p 互为素数的数 | ||
| 现在考虑集合 U，通过将 Q 的每个元素乘以 x (mod p) 得到 | ||
| U 的每个元素都与 p 互为素数 | ||
| i = xQj (mod p) 其中 i j |
||
| Qi = Qj (mod p) 因为 x 0 |
||
| U 的元素是不同的 | ||
| U 是 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) | ||
使用代码
此 RSA 实现使用 32 位密钥。有两个文件：input.htm 和 output.htm。input.htm 文件的代码如下
<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>
output.htm 文件的代码如下
<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>
现在，创建文件后，您可以从浏览器中运行 input.htm 文件并提供必要的值。点击提交按钮将打开 output.htm 文件并显示必要的结果。
代码兼容性
该代码已在 IE 4.0 及以上版本以及 Netscape Navigator 上进行了测试。
RSA 算法的工作原理
假设 B 想向 A 发送一条消息。A 和 B 已经交换了他们的公钥。让我们尝试理解这如何工作
- A 先生选择两个素数。例如 p = 53 和 q = 61。
- A 先生计算 p * q = 3233。这是他发送给 B 的公钥。
- A 先生计算 e 的值，使得 GCD (( p – 1 ) * ( q – 1 ), e) = 1。这也发送给 B。
- 假设 B 先生想发送消息 M = 999 给 A。
- B 先生加密消息，c = Me (mod N) = 9997 (mod 3233) = 3026。
- B 先生将 c 发送给 A 先生。
- A 先生解码 c = 3026。首先，他找到 d，使得 e * d = 1 (mod ( ( p – 1 ) * ( q - 1) ) )。
- 该方程使用扩展欧几里得算法求解。因此 d = 1783。
- 其次，A 先生使用以下公式解码加密消息 c：cd (mod N) = 30261783 (mod 3233) = 999。
关注点
- 公钥 N 的因子，即 p 和 q，应该足够大，以便不容易因子分解 N。
- 一般而言，素数的阶应该为 160 位（512 位）到 640 位（2048 位）。
- 目前没有算法可以在合理的时间内分解上述阶的数字。
- 因此，RSA 算法通过此类算法的不可用性得到保护。
结论
- 必须使用穷举法来分解 N。
- 分解 N 的算法的运行时间相对于 N 的长度呈指数增长。
- 尽管如此，存在一个更快的算法来分解 N 的可能性非常小。
进一步建议
- RSA 的可能攻击
- 判断一个数是否为素数的算法（时间复杂度较低的算法）。
- 当前使用的最大素数。
我建议读者尝试研究这些主题，以便更多地了解 RSA 加密方案。我拥有必要的内容，但现在不想让事情变得复杂。
RSA 的实现
- SSL（安全套接层）
- 防火墙
- ATM 机
- 数字签名
- 证书
联系方式
将您的建议、意见和问题发送至 gauravsonline@gmail.com