五分钟知识科普:什么是 RSA 算法点击蓝色“五分钟学算法”关注我哟 加个“星标”,一起学算法 RSA 算法历史RSA 是 1977 年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。 当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。 但实际上,在 1973 年,在英国政府通讯总部工作的数学家克利福德·柯克斯(Clifford Cocks)在一个内部文件中提出了一个相同的算法,但他的发现被列入机密,一直到 1997 年才被发表。 RSA 算法基础知识密码学知识明文:是指没有加密的文字(或者字符串)。 加密:是以某种特殊的算法改变原有的信息数据,使得未授权的用户即使获得了已加密的信息,但因不知解密的方法,仍然无法了解信息的内容。 密文:密文是对明文进行加密后的报文。 对称加密:对称是指,在对明文进行加密,对密文执行解密加密过程采用相同的规则(通常将双方采用的规则称为"密钥")。 例如: 非对称加密:非对称加密是指通信双方采用不同的密钥进行加密解密。 例如: 数学知识互质关系:如果两个正整数,除了数字 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是φ(n)的k的整数倍,余数为1。则上式可以转化为: 其中,对于d的求解转化为二元一次方程求解。此方程可以使用扩展欧几里得方法进行求解。通过辗转相除法计算出一组解为(2753,-15)。 解得d = 2753。 (6)将n和e封装成公钥,n和d封装成私钥 加密公钥为(3233,17),私钥为(3233,2753)。 RSA 算法分析那么 RSA 算法是如何保证安全性的呢? 在 RSA 算法中 n 与 e 是公开的,那么破解 RSA 加密的步骤即为通过 n 与 e 计算出私钥 d 的值。
由此得出密码破解的实质问题是:从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 算法为保证安全性,会大大提升密钥长度,导致运算速度变慢。这导致它在大量数据加密时并不适用。 END原 创 热 文 推 荐 |
朋友会在“发现-看一看”看到你“在看”的内容