您好,欢迎访问山东渔翁信息技术股份有限公司官方网站
渔翁信息

专注密码硬件研发生产定制

咨询热线: 400-6686-188

产品中心

热门产品

联系我们

咨询热线:400-6686-188

市场合作:孙经理:13806311977

售后服务:房经理:0631-5651692

邮箱:support@fisherman-it.com

地址:济南市高新区齐鲁软件园F座

新闻中心 您的位置:首页 > 新闻中心 >

RSA算法的加密和解密

文章出处:渔翁信息作者:渔翁信息人气:发表时间:2019-03-21 11:39

在RSA密码体制中,每个用户都拥有两个密钥:公钥PK≡{e,n}和私钥SK≡{a,n}。公钥PK≡{e,n}用于加密,也称为加密密钥,可以在网络、电话簿等媒体上进行公布。私钥SK≡{a,n}用于解密,也称为解密密钥,必须保密。每个用户把加密密钥PK公开,使得系统中的任何其他用户都可以使用,而对解密密钥SK中的d则必须严格保密。

1.密钥生成

下面讨论RSA公钥密码体制中的每个参数是如何计算的。

(1)选取两个保密的大素数p和q(p和q一般为100位以上的十进制数)。

(2)计算n≡p×q。n称为RSA算法的模数。

(3) φ(n)≡(p-1)(q-1),其中p(m)是n的欧拉函数值。

(4)选取一个随机整数e(即加密密钥),使之满足1<e<φ(n),且gcd(φ(n),e)≡1。

(5)计算解密密钥d,满足d*e≡1mod φ(m),即d是e在模φ(n)下的乘法逆元,因e与p(n)互素,由模运算可知,它的乘法逆元一定存在。

(6)以PK≡{e,n}为公钥并公布,SK≡{d,n}为私钥并保留。此时,p,q不再需要,可以销毁。

2.加密

加密时首先将明文比特串分组,使得每个分组对应的十进制数小于n,即分组长度小于log2n。然后对每个明文分组mi;做一次加密运算,所有分组的密文构成的序列即是原始消息的加密结果。即mi满足0≤mi<n,设ci为分组信息mi加密后的密文,则加密算法为

Ci≡mie mod n

Ci为密文,且0≤Ci<n

3.解密

解密时对每一个密文分组c≤c<n)的解密算法为Mi≡cidmod n。

下面证明RSA算法中解密过程的正确性。

证明:由加密过程知c≡ me mod n,所以

Cd mod n≡ med mod n≡m1modΦ(n)mod n ≡ mkΦ(n)+1 mod n

下面分两种情况:

(1)m与n互素,则由欧拉定理得

mkΦ(n)≡1modn, mkΦ(n)≡1modn, mkΦ(n)+1≡ m mod n

即cdmodn≡m。

(2)gcd(m,n)≠1,先看 gcd(m,n)≡1的含义,由于n≡pq,所以gcd(m,n)≡1意味着m不是p的倍数也不是q的倍数。因此gcd(m,n)41意味着m是p的倍数或q的倍数,不妨设m≡Cp,其中c为一正整数。此时必有gcd(m,q)≡1,否则m也是q的倍数,从而是pq的倍数,与m<n≡pg矛盾。

由gcd(m,q)≡1及欧拉定理得mΦ(q)≡1modq

所以mΦ(q)≡1modq,[ mΦ(q)] Φ(p)≡1modq, mkΦ(n)≡1modq

因此存在一整数r,使得mkΦ(n)≡1+rq,两边同乘以m=cp得mkΦ(n)+1=m+rcpq=m+rcn

即mkΦ(n)+1≡ m mod n,所以 cdmod n≡m。


  1. 一键分享到

返回顶部