五分钟知识科普:什么是 RSA 算法

来自:五分钟学算法(微信号:blgczzz),作者:进击的HelloWorld


RSA 算法历史

RSA 是 1977 年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。

当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。

但实际上,在 1973 年,在英国政府通讯总部工作的数学家克利福德·柯克斯(Clifford Cocks)在一个内部文件中提出了一个相同的算法,但他的发现被列入机密,一直到 1997 年才被发表。

RSA 算法基础知识

密码学知识

明文:是指没有加密的文字(或者字符串)。

加密:是以某种特殊的算法改变原有的信息数据,使得未授权的用户即使获得了已加密的信息,但因不知解密的方法,仍然无法了解信息的内容。

密文:密文是对明文进行加密后的报文。

对称加密:对称是指,在对明文进行加密,对密文执行解密加密过程采用相同的规则(通常将双方采用的规则称为"密钥")。

例如:
  (1)甲方选择某一种加密规则,对信息进行加密;
  (2)乙方使用同一种规则,对信息进行解密。

非对称加密:非对称加密是指通信双方采用不同的密钥进行加密解密。

例如:
  (1)乙方生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。
  (2)甲方获取乙方的公钥,然后用它对信息加密。
  (3)乙方得到加密后的信息,用私钥解密。

数学知识

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

同余定理:给定一个正整数 m,如果两个整数a和b满足a-b能够被m整除,即(a-b)/m得到一个整数,那么就称整数 a 与 b 对模 m 同余,记作 a ≡ b(mod m)。

RSA 算法流程

(1)选择两个不相等的质数p和q

例如:选择两个不等质数分别为 61 和 53 (实际应用中选择的质数都相当大)。

(2)计算p和q的乘积n

n = p*q = 61 * 53 = 3233。

(3)计算 n 的欧拉函数 φ(n)

φ(3233) = φ(61 * 53) = φ(61) * φ(53)。

由于 61 为质数,因此 φ(61) = 61 - 1 = 60。同理 φ(53) = 53  - 1 = 52。则 φ(3233) = 60 * 52 = 3120。

(4)随机选择一个整数 e ,条件是1< e < φ(n),且 e 与 φ(n) 互质

随机选择一个质数e,保证1< e < 3120,这里选择e = 17。

(5)计算e对于φ(n)的模反元素d
e * d ≡ 1 (mod φ(n))。其中e = 17,φ(n) = 3120。

设e*d是φ(n)的k的整数倍,余数为1。则上式可以转化为:
17 * d = 3120k + 1。继续转化得到:
17 * d + 3120y = 1。其中y = -k。

其中,对于d的求解转化为二元一次方程求解。此方程可以使用扩展欧几里得方法进行求解。通过辗转相除法计算出一组解为(2753,-15)。

解得d = 2753

(6)将n和e封装成公钥,n和d封装成私钥

加密公钥为(3233,17),私钥为(3233,2753)。

RSA 算法分析

那么 RSA 算法是如何保证安全性的呢?

在 RSA 算法中 n 与 e 是公开的,那么破解 RSA 加密的步骤即为通过 n 与 e 计算出私钥 d 的值。

(1)ed ≡ 1 (mod φ(n))。只有知道 e 和 φ(n),才能算出 d 。
(2)φ(n) = (p-1)(q-1)。只有知道 p 和 q ,才能算出 φ(n)。

由此得出密码破解的实质问题是:从p * q的值n,去求出 (p-1) 和 (q-1)。换句话说,只要求出 p 和 q 的值,我们就能求出 d 的值而得到私钥。但是,当 p 和 q 是是很大的质数时,从它们的积 p * q 去分解因子 p 和 q ,这是一个公认的数学难题。

比如当p * q大到1024位时,迄今为止还没有人能够利用任何计算工具去完成分解因子的任务。

虽然理论上 RSA 是可以破解的,但是随着密钥长度增加,破解的代价是不可接受的。

因此,只要密钥长度足够长,用 RSA 加密的信息实际上是不能被解破的。目前被破解的最长 RSA 密钥就是 768 位。

RSA 算法总结

RSA 的安全性依赖于大数分解,因此 RSA 算法加密安全性较高。但是,RSA 算法为保证安全性,会大大提升密钥长度,导致运算速度变慢。这导致它在大量数据加密时并不适用。

推荐↓↓↓
黑客技术与网络安全
上一篇:什么是自签名数字证书? 下一篇:循序渐进学加密