RSA 算法描述
RSA算法
RSA 算法描述
*RSA是Rivet，Shamir和Adleman于1978年在美国麻省理工学院研制出来的，它是一种比较典型的公开密钥加密算法。
*基础
大数分解和素性检测——将两个大素数相乘在计算上很容易实现，但将该乘积分解为两个大素数因子的计算量是相当巨大的，以至于在实际计算中是不能实现的。
1.RSA密码体制的建立：
(1)选择两个不同的大素数p和q；
(2)计算乘积n=pq和Φ(n)=(p-1)(q-1)；
(3)选择大于1小于Φ(n)的随机整数e，使得gcd(e,Φ(n))=1；
(4)计算d使得de=1mod Φ(n)；
(5)对每一个密钥k=(n,p,q,d,e)，定义加密变换为Ek(x)=xemodn，解密变换为Dk(x)=ydmodn，这里x,y∈Zn；
(6)以{e,n}为公开密钥，{p,q,d}为私有密钥。
2.RSA算法实例:
下面用两个小素数7和17来建立一个简单的RSA算法：
(1)选择两个素数p=7和q=17；
(2)计算n=pq=7 17=119，计算Φ(n)=(p-1)(q-1)=6 16=96；
(3)选择一个随机整数e=5，它小于Φ(n)＝96并且于96互素；
(4)求出d，使得de=1mod96且d<96，此处求出d=77，因为
77 5＝385＝4 96＋1；
(5)输入明文M＝19，计算19模119的5次幂，Me＝195＝66mod119,传出密文C＝66；
(6)接收密文66，计算66模119的77次幂；Cd=6677≡19mod119得到明文19。
题目：
hdu1211（水题）、pku2447、zoj2320、http://acm.timus.ru/problem.aspx?space=1&num=1141
PS:
专家建议
p和q的长度应只差几个数字。
(p-1)和(q-1)都应该包含大的素因子。
gcd(p-1,q-1)应该很小。
e的选择
为了提高RSA的加密速度。最常用的三个e值是3,17和65537。（X.509中建议采用65537，PEM中建议采用3，PKCS#1中建议采用3或65537）。