不对称密钥密码体系之RSA

不对称密钥密码体系之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)=Φ(p₁)Φ(p₂)=(p₁)x(p₂)

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=M^e（mod n）
解密：M=C^d（mod n）

RSA密钥对生成实例

1.独立选取两个素数（这里取的素数很小）p₁=47和p₂=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小的数据，为了简单，M₁=82，M₂=83，M₃=65

加密后：C₁=274，C₂=2251，C₃=541
结果：274，2251，541

解密后：M₁=82，M₂=83，M₃=65
结果是正确的，过程就不写出来了，套用公式就能算。

RSA的速度：
硬件实现：比DES大约慢1000倍
软件实现：比DES大约慢100倍

相同安全强度所需的密钥长度比较：

image

RSA的缺点：
受到素数产生技术的限制，产生密钥很麻烦。

分组长度很长，为保证足够安全，n至少要600比特以上，使运算代价很高，且随着大数分解技术的发展，这个长度还需要增加，不利于数据格式的标准化。