0%

密码学 | RSA 算法--基本原理篇「转载」

咱们每天说非对称加密,说公钥私钥,但是公钥和私钥到底是怎么产生的,加密和解密过程到底是怎么样的,不看看具体算法实现还真是感觉心里没底。RSA 算法是非对称加密算法鼻祖,至今仍然是最为广泛使用的算法之一,所以我们就来拆解一下 RSA 算法本身。


参考资料



宏观思路


学东西最怕的就是没有大思路,直接深入细节。所以开始之前,我们先宏观上讨论一下 RSA 算法到底是用来干嘛的?总体的实现思路又是怎样的呢?

说到最底层,RSA 算法的作用非常简单,就是生成公钥和私钥的。公钥用于加密信息,私钥用来解密,先上锁,后开锁。Alice 自己先买一把锁,然后把锁头发送给 Bob ,注意 Bob 给信息上锁的时候,肯定是不需要钥匙的,上了锁的信息发送给 Alice 之后,Alice 就可以用钥匙打开锁,拿到信息。锁和开锁明显是两个不同的过程,没有必要让钥匙参与到上锁过程中,这个就是非对称加密的的思想源头了。上锁的时候,Bob 只需要公钥,而 Alice 开锁的时候才需要私钥。所以公钥就是加密 key ,私钥就是解密 key 。实现加密和解密的第一步就是找到一个函数,函数的正向运算很容易,但是逆向运算很难。对应 RSA 的情况,也就是把公钥和信息作为参数进行运算,得到密文,这个过程要很容易,而逆向运算,由密文和公钥想要获得信息,是很难做到的。

当然,这个函数还必须有另外一个特点。就是逆向操作虽然默认很难做到的,但是如果拥有了特定的提示信息,操作就变得非常容易了。这里的提示信息,显然就是私钥。

总之,找到这样一个正向容易运算,反向默认很难,但是如果有了私钥就很容易运算的函数,就是实现 RSA 算法的核心思路。


具体实现


下面我们就来看看 RSA 算法具体的实现方式。

先来补充一个数学知识:取模运算。取模运算其实就是算余数。例如 3 mod 2 的结果就是1,mod 就是取模的意思。

RSA 使用的单向函数是这样的,拿出要加密的信息 m ,我们知道任何的计算机信息都能转换成二进制数,所以当然也能转换成十进制的一个整数。这里 m 是一个整数,接下来随机选择一个 e ,来作为 m 的指数。注意,这里的指数 e 的选择范围是有一定限制的,但是在这个范围内是任意选择的。接下来,进行 m 的 e 次方运算,然后对另一个随机选取整数 N 进行取模运算,最后得到的结果就是密文,用 c 表示 。举个例子,m 等于7 ,e 选择为2 ,N 选择23,这样,最后的密文 c 就等于49对23取模,结果是6。也就是说7经过加密,最后密文是6。这个运算有个特点,给定 m 和 e 以及 N 的值,很容易算出 c ,但是给定 c 和 e 以及 N 很难算出 m 来。这就是我们需要的单向函数。

于是,我们的锁就有了,也就是 ”e 次方然后对 N 取模“。那么,开这把锁的钥匙是什么呢?简单来说,就是让逆向运算过程变得简单的信息。

逆向运算,就是从密文得到信息。经过数学推导,可以得到这样的逆向运算过程,一定存在一个整数 d ,使得 c 的 d 次方对 N 取模,是可以得到 m 的。最终,e 和 N 按照一定规范组合到一起,就是公钥,而 d 和 N 组合到一起就是私钥。

总之,RSA 算法的单向函数找到了,于是加密用的锁也就找到了。但是其实这个函数本身不是 RSA 算法最复杂的地方,最复杂的内容在于如何由 e 算出 d 。而如何给定 e ,算出合适的 d ,其实是要引入第二个单向运算了,这就是整数分解问题了。


安全性取决与整数分解问题


如何运算出 d 的过程本节不展开。粗略来讲,从 e 运算出 d 的过程,涉及到 N 的整数分解问题。整个 RSA 算法的安全性就取决于整数分解这个基本数学问题。

来解释一下整数分解问题。整数分解就是把一个数分解成多个素数的乘积。素数就是那些只能被1和自己整除的整数,这个小时候咱们学过的。例如 45 可以分解成 3x3x5 。而 RSA 算法中的整数分解有一定的特殊性。被分解的数需要是两个,而不是多个素数的乘积。虽然由两个素数相乘获得结果非常简单,但是反过来,分解过程是很难的。很难的意思就是如果数足够大,即使用计算机也需要成千上万年才能算出来的问题,或者可以说“很难”就等于”实际中不能实现“。而这一点就是 RSA 算法的安全基石。如果有一天,有数学家找出整数分解的有效运算方法,那么 RSA 算法也就不能用了。

实际生成公钥和私钥的过程是,我们选出 p1 和 p2 两个大素数,让 N = p1 * p2 。随机选择一个指数 e ,这样公钥就有了。而在知道 p1 和 p2 的前提下,从公钥算出私钥,也就是算出 d ,是非常容易的。而外人,因为不知道 p1 和 p2 ,而只知道 N ,所以不可能从 e 算出 d ,也就是不可能用公钥算出私钥。

总之只要整数分解问题无解,那么 RSA 就是安全的。


总结


这就是 RSA 算法的工作原理了。宏观上的思路就是,要找到一个包含取模运算的单向函数,保证信息加密容易,而反向解密很难。另外,还要找到第二个单向函数,也就是整数分解问题的函数,保证在知道分解结果的条件下,从公钥算出私钥是容易的,而如果不知道,就不可能算出私钥。真正的 RSA 算法,是这两个单向函数的综合使用。但是对于如何进行解密,公钥和私钥生成的细节,我们没有展开,因为这涉及到更多的数学推导,下个小节 Peter 再给大家介绍。

请我喝杯咖啡吧~