RSA算法介绍
RSA算法步骤可以描述如下： 步骤1：生成公钥和私钥。
① 用计算机随机生成两个大素数p和q（保密），然后计算这两个素数的乘积n=pq（公开）。
② 计算小于n并且与n互质的整数的个数，即欧拉函数ϕ(n)=(p–1)(q–1) （保密）。利用p和q有条件的生成加密密钥e，这里的条件是：随机整数e满足1③ 计算与n互质的解密密钥d。计算公式为de=1 mod ϕ(n)（保密）。 ④ 销毁p、q、ϕ(n)；公开公钥{e，n}，保管好私钥{d，n}。步骤2：加密和解密。
利用RSA加密的第一步是将明文数字化，并取长度小于log2n位的数字作明文块。 加密方法：C=E(M)≡Me mod n 解密方法：M=D(C)≡Cd mod n
【例】利用RSA算法加密和解密的示例。 步骤1：按照上述RSA算法步骤生成密钥。
① 生成两个素数：p=17，q=11，计算n=pq=17×11=187。 ② 计算ϕ(n)= (p–1)×(q–1)=16*10=160。选择e，使得e和ϕ(n)=160互质，且小于ϕ(n)，例如取e=7。
③ 计算d，满足de=1 mod 160=1，且d<160。这里d=23，因为23×7=161=10×16+1。 ④ 由此，公钥为{7,187}，私钥为{23,187}。
步骤2：利用RSA算法加密和解密的过程示例如图所示。
加密 明文 m=88 公钥{7,187}
私钥{23,187}
88 7 mod 187 =11 密文 c=11 解密 11 23 mod 187 =11 明文 m=88
图 利用RSA算法加密和解密的示例
