RSA(Rivest-Shamir-Adleman)算法是基于大数不可能被质因数分解假设的公钥体系。简单地说就是找两个很大的质数。一个用来做对外公开的公钥(Public key),另一个不告诉任何人,称为私钥(Private key)。 RSA体制的密钥生成可以简单描述如下: (1)选择两个大素数p和q(p≠q)。(一般为100位以上的十进制数) (2)计算出n=pq及φ(n)=(p-1)(q-1) ,这里φ(n)是Euler函数。 (3)选择一个随机整数e(加密密钥),且满足1<e<φ(n),满足gcd(e,φ(n))=1。 (4)计算解密密钥  ed  mod φ(n)=1,计算解密密钥d. (5)明文为a ,对每一个密钥k=(n,p,q,d,e),定义加密变换为:Ek(a)= aemod n = c,定义解密变换为:Dk(c)= cd mod n = a。 (6)公布整数n和加密密钥e。以{e,n}作为公开密钥,以{d,n}作为私有密钥。

例题一:

P=7,q=19,选择e=5,求d=?

明文为6,求密文。

解: n=pq=719=133, φ(n)=6*18=108 e=5,  e与108互质,满足要求 5d mod 108=1 某个数 5d  除以108,余数为1

求5的倍数:

  1. 108*1+1=109

  2. 108*2+1=217

  3. 108*3+1=325

  4. 5d=325

  5. d=65

加密: c=6^5 mod 133=62 验证: 62^65 mod 133=6

例题二:

两个质数p=11,q=13,请选择一个e,然后求d=?明文为85,求密文。

解: n=pq=1113=143,φ(n)=(p-1)(q-1)=(11-1)(13-1)=120 选e=7,e与120互质,满足要求 7d mod 120 = 1 某个数7d除以120,余数为1,求7的倍数:

  1. 120*1+1=121

  2. 120*2+1=241

  3. 120*3+1=361

  4. 120*x+1=xxx

  5. 120*6+1=721

721为7的倍数 7d=721      d=103 加密: c=85^7 mod 143 = 123 验证: 123^103 mod 143 = 85



Published

20 April 2011