密码学中的RSA算法

2.RSA算法

RSA公钥密码算法是以发明者R.Rivest、A.Shamir和L.Adleman的名字命名的，它的安全性是基于整数因子分解问题的困难性。RSA算法是第一个能同时用于加密和数字签名的算法，易于理解和操作；是被研究得最广泛的公钥算法，经历了各种攻击的考验，逐渐为人们接受；也被普遍认为是目前最优秀、应用最广泛的公钥算法之一。

1) RSA算法描述

选取两个大素数p和q，计算其乘积：n= pq和欧拉函数巾(n)=（p一1）(q-l)；然后随机选取加密密钥e，l<e<中(n)，满足e和( p-1)(q-l‘)互素。最后用欧几里德扩展算法计算解密密钥d，以满足ed=l（mocl（p-l）(q-l))，即

d= e-1 mod（（p-l） （q-l）） e和n是公钥，d和n是私钥。

RSA算法对明文以分组为单位进行加密，每个分组的二进制均小于n。即分组的大小必须小于或等于1092（朋）位；在实际应用中，分组的大小是啦，其中2k<n≤2.k+1。对明文分组M，加密过程如下C=lVfmodn：。对密文分晓乱，解密过程如下：M_Cdmodn。