上一篇：从Android中RSA算法到密码学非对称性加密算法到大数因子多项式分解（二）

上回说到RSA体制的建立与破译就等价于素数判别与大数分解问题。那么为什么这么说，其中的联系在哪呢？这要从大数分解说起。

因为要说的是数学，所以必须先交代几个概念才显得像那么回事，咳咳...对于数论或者密码学高手，请略过此节。直接看下面代码和实例即可。

1.素数/合数
在自然数中，我们将那些可以被2整除的数叫作偶数，如2、4、6、8、10、...等，剩下的那些自然数就叫作奇数，如1、3、5、7、9、...等。这样，所有的自然数就被分成了偶数和奇数两大类。 　　另一方面，除去1以外，有的数除了1和它本身以外，不能再被别的整数整除，如2、3、5、7、11、13、17、...等，这种数称作素数(也称质数)。质数中，除了2之外，其它的质数都是奇数。有的数除了1和它本身以外，还能被别的整数整除，这种数就叫合数，如4、6、8、9、10、12、14、...等，就是合数。奇数中有合数（例如9、15、21等）。偶数中除了2之外，其他的偶数都是合数。1这个数比较特殊，它既不算质数也不算合数。这样，所有的自然数就又被分为0、1和素数、合数四类。

2.数的因子
什么是数的因子?因子就是所有可以整除这个数的数,不包括这个数自身. 　　因数包括这个数本身而因子不包括，如：比如15的因子是1，3，5 　　而因数为1,3,5,15。 　　完数是指此数的所有因子之和等于此数，例如：28=1+2+4+7+14.

3.互质（又叫互素）
互质，公约数只有1的两个整数，叫做互质整数·公约数只有1的两个自然数，叫做互质自然数，后者是前者的特殊情形。

4.欧拉函数
在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。 同理，φ(2)=1<1>，φ(3)=1<1,2>，φ(4)=2<1,3>，φ(7)=6<1,2,3,4,5,6>

通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)

其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4

当x为素数时，φ(x)==m-1。

5. 大数分解
一言蔽之：任意找两个大大的素数q,p，将其相乘N=q*p。现在只已知N，反求q和p。
注：数学上的长篇大论这里省略掉，本质就是反求q和p。本文讲究实效，所以多余内容请自行百度<大数因子分解等>。

概念说完，下面就说说本文重点：为何大数分解能够使信息保密？

一言蔽之，我决定直接举例：

6. 由大数分解算法到非对称性加密算法实例
这里为了能最有效最简约的将这个过程说清楚，我们将采用较小的素数来举例。
例子：假设你是一个密钥制作者BOSS，为两用户A1,A2服务。
1. 首先选择两个素数p=11,q=13
2. 求出:N=pq=143,以及根据欧拉函数公式求出:φ(N)=143(1-1/11)(1-1/13)=120.
3. 任意选择与φ(N)=120互素的两个正整数e1=7,e2=13.
4. 分别建立同余方程7x=1(mod 120), 13x=1(mod 120)
5. 解得x=103(mod 120), x=37(mod 120)
6. 取得d1=103,d2=37
7. 于是BOSS现在开始给A1,A2发密钥了：A1的密钥{e1,d1}={7,103}; A2的密钥{e2,d2}={13,37}
8. 现在BOSS将N=143,e1=7,e2=13公开成为公钥，而将d1=103,d2=37分别给用户A1,A2作为它们的私钥。

答案出来了：现在BOSS的公钥143已知，要想破解出私钥，我需要从143的大数分解中求得q和p的值，进而通过步骤2~6求出d1,d2，若q和p很难分解，那么私钥d1,d2就很难破解了。

7. 同余方程
大家看到了上面的例子中主要涉及到一个核心算法：一次同余方程求解。这个东西展开篇幅很大。故我想放到下回再说。
这里给出一个mini demo，帮助你理解上面的内容：

一堆鸡蛋，3个3个数余2，5个5个数余1，7个7个数余6，问这堆鸡蛋最少有多少个？
对于这个问题用数学的语言来描述就是：N = 2(mod 3) = 1(mod 5) = 6(mod 7); 求解最小N。
答案：101

接着说例子6，若我们想要破解公钥143，得到私钥103和37最关键的步骤就是把143进行大数分解，得到11和13。这就涉及到大数分解算法。目前流行的大数分解算法有：试除法、蒙特卡罗方法、Pollard算法、椭圆曲线ECM算法等。

这里我只介绍比较适合在计算机上跑的Pollard算法。

8. Pollard Rho算法JAVA实现
算法本身比较深奥，要理解的请自行百度，这里只说干货:)

import java.math.BigInteger;  
import java.security.SecureRandom;  
      
class PollardRho  
{  
    private final static BigInteger ZERO = new BigInteger("0");  
    private final static BigInteger ONE  = new BigInteger("1");  
    private final static BigInteger TWO  = new BigInteger("2");  
    private final static SecureRandom random = new SecureRandom();  
  
    public static BigInteger rho(BigInteger N)   
    {  
        BigInteger divisor;  
        BigInteger c  = new BigInteger(N.bitLength(), random);  
        BigInteger x  = new BigInteger(N.bitLength(), random);  
        BigInteger xx = x;  
  
        if (N.mod(TWO).compareTo(ZERO) == 0) return TWO;  
  
        do   
        {  
            x  =  x.multiply(x).mod(N).add(c).mod(N);  
            xx = xx.multiply(xx).mod(N).add(c).mod(N);  
            xx = xx.multiply(xx).mod(N).add(c).mod(N);  
            divisor = x.subtract(xx).gcd(N);  
        } while((divisor.compareTo(ONE)) == 0);  
  
        return divisor;  
    }  
  
    public static void factor(BigInteger N)   
    {  
        if (N.compareTo(ONE) == 0) return;  
        if (N.isProbablePrime(20))   
        {   
            System.out.println(N);   
            return;   
        }  
        BigInteger divisor = rho(N);  
        factor(divisor);  
        factor(N.divide(divisor));  
    }  
   
    public static void main(String[] args)   
    {  
        BigInteger N = BigInteger.valueOf(4620);  //这里4620是一个大数，是我随便找的几个素数之积
        factor(N);  
    }  
}

结果：


2*2*3*5*7*11=4620 这样就实现了大数分解

这次由于篇幅关系，例子6中只说到如何生成密钥。在后面的帖子中，我们将以这个例子为主线，向大家展示一个完整的商业级加密通信过程，讨论该算法是如何利用密钥进行信息加密，网络传输，如何生成签名和证书，最后到用户A1,A2手中又是如何解密，如何完成身份识别验证的。敬请关注谢谢！

备注：论坛将此文的（二）附在（一）的4楼了，有找不到的朋友找到（一）向下翻。

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)