Android签名背后的RSA数学原理

内容概要：在Android签名中，用到了RSA，在使用HTTPS时，其TLS协议也用到了RSA。RSA是如何应用到这两个方面的呢？有什么不同？为什么RSA这么难破解？其中的数学原理又是什么样的？本文就这些问题进行探讨。

一、RSA是什么

首先简要介绍下RSA，RSA由Ron Rivest，Adi Shamir，Leonard Adleman三人于1977年提出，是一种公开密钥的加密算法，其基于费马-欧拉定理和大数的质因数分解难题，广泛应用在Android签名、SSH、TLS中。

二、RSA的应用场景

正如开篇所说，RSA即可以用在Android的签名验证中，也可以用在TLS的加密解密中。他们具体是如何应用的呢？为了让大家更好的理解，我将他们的过程简化，使用具体的数字来加以说明。

（一）RSA在Android的签名验证中的应用

首先是前期工作，生成公钥和私钥，我们先随机选择两个不相等的质数p，q，为3和11，用他们的积33作为公钥的一部分，再计算33的欧拉函数：

算出结果为20，选择一个小于20且与20互质的正整数作为公钥的另一部分，这里选择7，用数字E代表。再利用费马-欧拉定理的推广计算出私钥D，费马-欧拉定理的推广如下：

其中E和D为正整数，且满足

使用该公式可以计算出私钥为3

此时销毁公钥的组成部分p和q，保留积pq，也就是销毁3和11，保留33。到此，公钥和私钥都已经获得了。 下面假设我们Android签名时生成的摘要A为2，在打包时，使用私钥D，通过下面的公式计算出签名8：

Android客户端在安装时，取出签名8和公钥E和pq进行验证，也就是7和33，再代入到费马-欧拉定理推广公式中。就可以直接算出摘要

计算出摘要后再和存储在本地的摘要，也就是数字2做对比，就可以验证签名是否被篡改了。在GIT的SSH协议中，也是利用的RSA私钥签名，公钥验证的方式，只不过是先由服务端发送一个随机数字给客户端，客户端用私钥签名后，再发给服务端，由服务端用公钥验证。所以，可以说，在签名验证的场景中，我们实际上是使用私钥进行签名，使用公钥进行验证。

（二）RSA在TLS的加解密中的应用

RSA在TLS中的主要应用是在三次握手中加解密对话密钥，同样，我们首先得到公钥私钥，这里不再赘述，公钥pq为33，E为7，私钥D为3。在握手时，客户端会生成一个随机数A用于对话密钥，同样假设为2，客户端使用公钥加密该数字：

得到加密后的数字29，服务端根据费马-欧拉定理的推广公式利用私钥D进行解密

这样便计算出客户端传来的加密之前的数字为2，所以，可以说，在TLS中等加解密的场景中，我们是使用公钥加密，私钥解密。

三、RSA为什么难破解

说完了RSA的两个应用场景，我们来看下为什么RSA难以破解，破解RSA的关键就是找到私钥D，其中私钥D的生成公式为:

我们已知的有公钥E和p与q的积pq，所以找到D的关键就是根据pq得到p和q了，在上面的例子中pq为33，我们可以很轻松的找到其质因数为3和11，但是在实际应用中pq都是大数，其二进制往往有2048位，在目前的数学界中，并没有一个方法可以快速得到大数的质因数，只能通过穷举的方式来得到。按照目前人类的计算机能力，破解可能需要上百年，破解的开销是远远大于你的收益，当然，如果量子计算机被真正掌握，破解也是可以的。

四、费马-欧拉定理扩展公式的推导

下面探讨一下RSA的核心公式是如何从费马-欧拉定理推导出来的 再回顾一下核心公式：

而费马-欧拉定理为：

其中

为欧拉函数，代表小于等于n的正整数中，所有与n互质的个数

我们将欧拉函数中的n换为两个质数，利用其积性函数的性质，便有了下面的公式：

继续进行扩展，

此时我们可以将ED代入公式中，

便得出扩展公式:

本文来自网易实践者社区，经作者冯越新授权发布