不对称密钥密码体系之RSA

时间:2022-04-04 07:37:33

公钥密码的特性:

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倍

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

不对称密钥密码体系之RSA

RSA的缺点:

受到素数产生技术的限制,产生密钥很麻烦。

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