RSA讲解

        相对于DES而言，RSA是一个极为简单的加密算法，它的密码强度取决于数学难题的不可解。此外，它还是非对称密码体制中的一个重要算法。

        何为非对称密码体制？首先要从对称密码体制说起，DES就是一个典型的对称密码算法，即加密密钥和解密密钥是相同的。那非对称密码体制，顾名思义，就是加密密钥和解密密钥不同，它存在一个公私密钥对，用公钥加密、私钥解密即为加密算法。那么问题来了，如果用私钥加密、公钥解密，又作何解呢？其实这就是所谓的数字签名，这里先不做详解。

        回归正题，RSA加密的流程可以做如下理解：

        首先是密钥的生成。选择两个互异的大素数p和q，计算n=p*q，f(n)=(p-1)*(q-1)，选择一个随机整数e（0<e<f(n)），且满足gcd(e,f(n))=1。计算d=e^-1modf(n)。

        [注]：以上需要保密的有：p、q、f(n)、d；

                 公开的有：n、e；

        那么，公钥为{e，n}，私钥为{d，n}。

        这样，基本配置就完成了，那加密即C=M^e mod n，解密为M=C^d mod n。

        以上，看似已经可以实现RSA的加解密了，但其实这里还存在三个问题。

        一、明文转化为二进制

               将明文分组后对应成二进制，然后对每组分别进行加密。这里存在一个与DES相同的问题，分组不

               足时的补位，我们依然按照补0来实现。

        二、大素数的选取

               大素数是指1024位或2048位的素数，这将会是一个很复杂的过程，所以在编程实现时，我们只能

               尽可能的选取较大的素数。可以用Miller-Rabin算法来检测素数。

        三、快速取模问题

               即如何快速计算a^m mod n，这个方法并不复杂，这里就不做详解了。

        至此，一个完整的RSA算法就结束了，下面附一张RSA的流程图来更清楚的表述。