加密算法介绍

RSA算法：

找两素数p和q
}o-d7}j.eLt0取n=p*q
Vz&OVew&C$K0取t=(p-1)*(q-1)
i!j;`1KE6p0取任何一个数e,要求满足e<t并且e与t互素（就是最大公约数为1）51Testing软件测试网&AB-I F0Y0x!]v
取d*e%t==151Testing软件测试网LmeXPR;a

yfgY%va0这样最终得到三个数： n  d  e

设消息为数M (M <n)51Testing软件测试网drr5{rd C*L
设c=(M**d)%n就得到了加密后的消息c
*_1D,`^/{&EO0设m=(c**e)%n则 m == M，从而完成对c的解密。51Testing软件测试网~4s"B
ct{0mH{
注：**表示次方,上面两式中的d和e可以互换。

 

RSA的安全性在于对于一个大数n，没有有效的方法能够将其分解51Testing软件测试网!i6zU]qZ"Y
从而在已知n d的情况下无法获得e；同样在已知n e的情况下无法51Testing软件测试网cgJa B)zV#I-q5gd
求得d。
%H6qs$cN,?/K0

 

举例：

p=4751Testing软件测试网NM ^b/J
y
q=5951Testing软件测试网y0w1czf
这样
;X6cGg~+o,[o x0n=p*q=2773
h\cIz0t k_0t=(p-1)*(q-1)=266851Testing软件测试网S_8Wr|H*W
取e=63，满足e<t并且e和t互素
mh~H!H w9mGB {#X:o0用perl简单穷举可以获得满主 e*d%t ==1的数d：51Testing软件测试网zKA7i6oz7\6fy
C:\Temp>perl -e "foreach $i (1..9999){ print($i),last if $i*63%2668==1 }"51Testing软件测试网&B7t+B2X[RB7Y _
847
bM5m|I'Q0即d＝847
,RuP&he*Cr0
-a#|6e7jx*R0最终我们获得关键的
l"e _
AI _0g6X0n=2773
O3}@M#b0d=84751Testing软件测试网#n;I?y,H~Nh
e=63
5Wh!]:F6Z|!`KQ
w'~051Testing软件测试网8E*g*~ a'FH8I
取消息M=244我们看看51Testing软件测试网|Y0zw~jbEv(d
51Testing软件测试网3~(cq5]B0P2bgYg
加密：51Testing软件测试网_dL,a:MCN
c=M**d%n = 244**847%2773
oc1B6@ z:R0d8C3y\0用perl的大数计算来算一下：
H
vgOG0C:\Temp>perl -Mbigint -e "print 244**847%2773"51Testing软件测试网?we,fzWr
46551Testing软件测试网v.Z-B2OS-fyp8@
即用d对M加密后获得加密信息c＝46551Testing软件测试网#f'gXQ:`$jS

3v2k~w_-B~0解密：51Testing软件测试网Zb ^;CsF R
我们可以用e来对加密后的c进行解密，还原M：
%al6Uj:MeC7l Z0m=c**e%n=465**63%2773 ：51Testing软件测试网!q.lV#w&}
C:\Temp>perl -Mbigint -e "print 465**63%2773"
N Fi2kRiC0244
s
G8VC&SoJf0即用e对c解密后获得m=244 , 该值和原始信息M相等。

 

注：2月28日写于msn共享空间