不对称密钥密码体系之RSA
公钥密码的特性：
1.加密和解密使用不同的钥匙
2.从一个钥匙推出另一个钥匙在计算上不可行
3.每个钥匙都可以做加密和解密
RSA算法：
1978年, MIT三位数学家 R.L.Rivest，A.Shamir和L.Adleman发明了RSA算法。 RSA算法可用于加密、又可用于数字签字，易懂且易于实现，是目前仍然安全并且逐步被广泛应用的一种体制。 国际上一些标准化组织ISO、ITU、及SWIFT等均已接受RSA体制作为标准。
RSA涉及的一些数论知识...
Euler函数：
设n为一正整数，小于n且与n互素的整数的个数，称为Euler数。
1.若n为素数，则Φ(n)=n-1
2.若n为两个素数的乘积，则Φ(n)=Φ(p1)Φ(p2)=(p1)x(p2)
Euler定理：
若a与n互素，则aΦ(n)≡1 mod n
RSA密钥对生成步骤
1.独立地选取两个大素数p和q，计算n=pXq，计算Φ(n)=(p-1)(q-1)
2.选一整数e，（1<=e<Φ(n)，e与Φ(n)互素）。在模Φ(n)下，e有唯一逆元，计算d=e-1mod (Φ(n))
3.取公钥为（n，e），私钥为（n，d），并销毁p、q
RSA加密和解密的步骤
加密前，首先将明文分成比n小的数据分组，再对每个每个分组加密
加密：C=Me（mod n）
解密：M=Cd（mod n）
RSA密钥对生成实例
1.独立选取两个素数（这里取的素数很小）p1=47和p2=71
n=47X71=3337
Φ(n)=（47-1）（71-1）=3220
2.选整数e=79，（1<=e<3220，3220与79互素）。在模3220下，79有逆元d=1019
3.取公钥（3337，79），私钥（3337，1019），销毁47，71
加密消息“RSA”，ascii码为828365 分成比n小的数据，为了简单，M1=82，M2=83，M3=65
加密后：C1=274，C2=2251，C3=541
结果：274，2251，541
解密后：M1=82，M2=83，M3=65
结果是正确的，过程就不写出来了，套用公式就能算。
RSA的速度：
硬件实现：比DES大约慢1000倍
软件实现：比DES大约慢100倍
相同安全强度所需的密钥长度比较：
image
RSA的缺点：
受到素数产生技术的限制，产生密钥很麻烦。
分组长度很长，为保证足够安全，n至少要600比特以上，使运算代价很高，且随着大数分解技术的发展，这个长度还需要增加，不利于数据格式的标准化。
网友评论