文档介绍：:..RSA算法的数论基础一、公钥密码体制基础一个好的密码体系的必要条件是合法用户能够很容易对秘密消息进行加密和解密,而这些过程对于其他人则足非常难的。公钥密码体制的实现葙于单向陷门函数。单向陷门函数:设f是一个函数,t是与f有关的一个参数。对于任意给定的X,汁算y,使得y=f(x)是容易的。如果当不知道参数t时,计算f的逆函数r1是难解的。但当知道参数t时,计算f的逆函数r1是容易的。则称f是一个单向陷门函数,参数t称为陷门。、RSA算法的安全基础计算机科学家Rivest、Shamir和Adieman提!li了满于素性检测和整数分解的祐一个使川公钥密码体制。算法的安全性建立这一数论难题基础上:将两个人素数相乘足界易计算的,而将该乘积分解成两个大素数因了•是困难的。\clogloglogn素性检测问题:检测n的素性的最好额判定算法运行吋间力°u°gn^ ,关于输入K度1Qgn呈超越多项式速度增长。整数因子分解问题:分解一个一般的整数n的最好的算法运行时间为(logn)3(loglogn)3,关于输入长度1Qgn呈业指数速度增长。三、RSA算法实现的基础定理算术基本定理:任何大于1的整数n能被因式分解为如下唯一形式:n=plp2,"pl(pl,p2,…,pi为素数)费马小定理:若P是素数,a与p互素,则apJ=l(modp)欧拉定理:欧拉函数表示不大于nRLjn互素的正整数的个数。当n是素数,Xn)=n-1。n=pxq,p,q均为素数时,则《(n)=0(p)0(q)=(p-l)(q-l)对于互素的a和n,有=l(modn)、①选两个互异的大素数P和q。②汁算n=pXq,4)(n)=(p-l)(q-1),其中4>(n)是n的欧拉函数值。③选一随机整数e,满足l〈e〈(l)(n),且gcd(4)(n),e)=l。④计算d,满纪d•e=lmod4)(n),即d是e在税*(n)卜'的乘法逆元,因e与*(n)互素,由模运算可知,它的乘法逆元一定存在。⑤以{e,n}为公开钥,{d,p,q}为秘密钥。,使得每个分组对应的十进制数小于n,即分组长度小于log2n。然后对每个明文ni,作加密运算:c=:m=cdmodn五、证明RSA算法中解密过程的正确性设P,q是不同的素数,n=pq记(1)(n)=(p_l)(q_l),如果e,d是与(1)(n)互素的两个正整数(e,d<4>⑹),并满足edEl(m(xi4>(n)),则对于每个整数x,都冇xed三x(modn)。分析:为丫证明xed三x(modn),只要证明巾⑹是xed-x的因数即吋。又因为n=Pq,而P,q都是素数,故只要证明P和q都是Xed-X的因数即可,B|Jxed=x(modp)(1)xe<1=x(modq)(2)证明:证明式1,若p是x的因数则式1必然成立若P不是X的因数,贝抽ed=l(mod<1)(n))得ed-l=k(p-l)(q-1),k为任意整数则xed=xk(p-1)(^,)=xx(xp-1)k(q',)根裾费马小定理因为X与P互素所以xpd三l(modp)所以xed=xx(xp-,)k(q',)=x(