05d8bc1f67667898fa9c4c25e84d2d21
RSA 算法

1 引言

  RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
  在之前的文章中已经介绍了DES对称加密算法,本篇文章将详细介绍RSA非对称加密算法

2 密码学知识

  明文:是指没有加密的文字(或者字符串)。
  加密:是以某种特殊的算法改变原有的信息数据,使得未授权的用户即使获得了已加密的信息,但因不知解密的方法,仍然无法了解信息的内容。
  密文:密文是对明文进行加密后的报文。
  对称加密:对称是指,在对明文进行加密,对密文执行解密加密过程采用相同的规则(通常将双方采用的规则称为"密钥")。
例如:
  (1)甲方选择某一种加密规则,对信息进行加密;
  (2)乙方使用同一种规则,对信息进行解密。
  非对称加密:非对称加密是指通信双方采用不同的密钥进行加密解密。
例如:
  (1)乙方生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。
  (2)甲方获取乙方的公钥,然后用它对信息加密。
  (3)乙方得到加密后的信息,用私钥解密。

3 数学知识

3.1 互质关系

  如果两个正整数,除了数字1之外没有其他公因子,我们称这两个数是互质关系。关于互质关系,有以下结论:

(1)任意两个质数构成互质关系,比如19和61。
(2)一个数是质数,另一个数只要不是前者的倍数,两者就构成互质关系,比如7和10。
(3)如果两个数中,较大的那个数是质数,则两者构成互质关系,比如97和57。
(4)1和任意一个自然数都是互质关系。
(5)p是大于1的整数,则p和p-1构成互质关系,比如57和56。
(6)p是大于1的奇数,则p和p-2构成互质关系,比如17和15。

3.2 欧拉函数

  任意给定正整数n,计算在小于等于n的正整数之中,有多少个与n构成互质关系。计算这个值的方法叫做欧拉函数,以φ(n)表示。例如φ(8)=4,含义为在1到8之中,与8形成互质关系的有1,3,5,7,共有4个数。
欧拉函数计算:
  欧拉函数计算可以分为以下几种情形:

(1)当n = 1时,φ(1) = 1,因为1与任何正整数构成互质关系,包括1自己本身。
(2)如果n是质数,则,φ(n) = n-1。应为质数与每个小于他的数都构成互质关系。
例如:φ(7) = 6,因为7与1, 2, 3, 4, 5, 6均构成互质关系。
(3)如果n是质数的某一个次方,即n = p^k(p为质数,k>=1),则
φ(n) = φ(p^k) = p^k - p^(k-1)
例如:n = 9 = 3^2。
φ(9) = 3^2 -3^1 = 6。9与1, 2, 4, 5, 7, 8构成互质关系。
(4)若n可以分解成两个互质的整数之积。
n = p1 * p2,则 φ(n) = φ(p1 * p2) = φ(p1) * φ(p2)
例如:φ(24) = φ(3 * 8) = φ(3) * φ(8) = 2 * 4 = 8。
24与1, 5, 7, 11, 13, 17, 19, 23共有8个数构成互质关系。
(5)因为任意大于1的整数,都可以写成一系列质数的积。
n = p1^k1 * p2^k2 * ... * pr^kr
根据情形(4)得到:
φ(n) = φ(p1^k1) * φ(p2^k2) * ... * φ(pr^kr)
再根据情形(3)得到:
φ(n) = p1^k1 * p2^k2 * ... * pr^kr * (1-(1/p1)) * (1-(1/p2)) * ... * (1-(1/pr))
最终得到:

top Created with Sketch.