一、RSA算法

RSA是非对称加密算法中的代表，它的重要性不言而喻，为了弄清楚RSA算法，我们一起来完成一项任务：

背景：现在是疫情时代，假如小明和女朋友被迫在两个城市，小明为了表达感情，想发给对方一句蜜语，但是不能让其他任何人知道。

蜜语用计算机语言表达：105 ，32 ，73，111，118，101，32，117，因为明文，所以想用RSA算法加密。如何做呢？

分为三步：

1、先搞清楚RSA的算法步骤

2、对每一个数字加密

3、对方能够解密

下来，我们一起完成帮小明完成心愿。

RSA的算法步骤：

1、随机选两个不相等的质数p和q

2、计算p和q的乘积n

3、计算n的欧拉函数 φ(n)

4、随机选择一个整数e，条件是1<e<φ(n),且e与φ(n)互质

5、计算e对于φ(n)的模反元素d

6、n和e为公钥，n和d为私钥

我们按照步骤，首先生成公钥和私钥

1、选两个质数 13和7

2、n=13*7=91

3、φ(143)=φ(13*7)=φ(13)*φ(7)=12*6=72

4、随机取一个数为5

5、通过扩展欧几里得算法，可以得出d=29

6、公钥：(91,5) 私钥：（91,29）

然后加密

m ^e ≡ c (mod n)

已知：m等于要发送的蜜语，e=5,n=91，求c （c为加密后的信息）

m=105，32 ，73，111，118，101，32，117

加密后的蜜语：14，2， 47，76,27, 82,2,52

最后解密

c ^d ≡ m (mod n)

已知：加密后的蜜语c，d=29,n=91 求m (m为原始蜜语）

c=14，2， 47，76,27, 82,2,52

解密后：14,32,73,20,27,10,32,26

存在问题：

1、当n比较小的时候，要加密的数比n大时，可能存在解密出来的数和原来的数差一个模。比如111，加密后是76，解密后是20, 20+91=111，其中91是模

2、模反元素求出的结果是负数

负数+模

解决思路：

选n的时候，选大一点，我们学习算法的时候，为了好计算，所以取的值比较小。如果原始数值也很大的时候，就考虑分割加密，比如，我们的n=91，要加密105，就分成两部分加密，比如加密一个10，再加密一个5，解密后，还是105，因为它只不过是字符序列而已。

二、质数

也称素数：大于1的自然数中，除了1和它自身外，不能被其它自然数整除

质数分布规律，随着数字越大，质数分布越稀疏

孪生质数：相差为2的质数对，如（3,5）（5,7）

在这里，我介绍下数学界数论的四大猜想

孪生素数猜想

存在无限个孪生质数对

欧拉：瑞士数学家、自然科学家1707年4月15日～1783年9月18日

13岁读大学、15岁大学毕业、16岁获得硕士学位，18世纪最杰出的数学家之一，不满十岁，就开始自学《代数学》，1766年患白内障，几乎失明。

哥德巴赫：德国的一个中学数学老师，1742年，给欧拉写信，提出了哥德巴赫猜想

哥德巴赫猜想

（a）任何一个＞=6之偶数，都可以表示成两个奇质数之和。

(b) 任何一个＞=9之奇数，都可以表示成三个奇质数之和。

从 9+9开始，逐步减少每个数里所含质数因子的个数，直到最后使每个数里都是一个质数为止，这样就证明了哥德巴赫猜想。中国的数学家在这个问题上是领先世界的。

华罗庚只有初中学历，由于家庭原因，被迫辍学，但是他的自学能力特别强，出版的数学著作数不胜数，上学的时候学习过他的文章，主要讲统筹，比如，烧水的时候，同时干点别的事情。我只是简单地提下。

陈景润有口吃，被停职，但是他的研究能力很厉害，上帝关了一道门，但是同时开了一扇窗。华罗庚发现了陈景润的才能，被带到研究院，陈景润研究哥德巴赫猜想，证明了1+2，大偶数为一个素数及一个不超过两个素数的乘积之和。迄今为止，是这个问题研究的终结点。

四色猜想

四色问题的内容是：“任何一张平面地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”用数学语言表示，即“将平面任意地细分为不相重叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”

费马猜想

形如xⁿ+yⁿ=zⁿ的方程，当n>2时不可能有整数解。“关于此，我确信已发现了一种美妙的证法，可惜这里空白的地方太小，写不下”，费马很有趣，美妙的证法，没法让其他人知道。

费马 1601年8月17日～1665年1月12日，法国律师和业余数学家

三、欧拉函数

同余类：模m同余的整数构成的集合

完系：在模m同余类中每一个类取一个数构成的集合叫m的一个完全剩余系，简称完系

最小非负完系：0，1,2，... ,m-1

互质是公约数只有1的两个整数，叫做互质整数，互质也称互素。

缩系（既约剩余系）：{1,2,...m}中与m互素的数的集合

Φ(m)=s，s为缩系的个数

换句话说，对正整数n，小于n的正整数中与n互质的数的数目

积性函数：f(ab)=f(a)*f(b)

欧拉函数φ(n)是积性函数。如果m,n互素，Φ(m*n)=Φ(m)*Φ(n)

例如，3和5互素，由于φ(3）=2，φ(5）=4，φ(15)=φ(3)*φ(5)=2*4=8

积性函数证明

构造了一个nm的矩阵，找到同时与nm互素的元素

GCD(km+r,m)=GCD(r, m)，所以每一列的 n 个元素同时与 m 互素，当且仅当 GCD(r,m)=1

与m互素的列共有Φ(m)个，假设第r列与m互素，r,m+r,2m+r, (n-1)m+r 是mod n的一个完系，在这一列中与n互素的共有Φ(n)个，所以Φ(mm)=Φ(m)*Φ(n)

欧拉定理：

m^φ(ⁿ⁾≡ 1 (mod n)

它能做什么？简化幂的模运算，还能做什么，与RSA算法有什么关系？这个后面就会知道

欧拉定理证明：

设x1,x2...x_φn与n互质

ax1 (mod n),ax2 (mod n)...ax_φn ( mod n)也与n互质，经过排序后与x1,x2...x_φn相同

所以aX1 * aX2 * ... * aX_φn ≡ X1 * X2 * ...* X_φn （mod n）

(a^φ(ⁿ-1)X1 * X2 * ...* X_φn ≡ 0 (mod n)

因为X1 * X2 * ...... * X_φn与n互质，所以 (a^φ(ⁿ-1)|n 即 a^φ(ⁿ⁾≡ 1 (mod n)

费马小定理：

引理1：

若a，b，c为任意3个整数,m为正整数，且(m,c)=1，则当a·c≡b·c(mod m)时，有a≡b(mod m)

引理2：

设m是一个整数且m>1，b是一个整数且(m,b)=1。如果a[1],a[2],a[3],a[4],…a[m]是模m的一个完全剩余系，则b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]也构成模m的一个完全剩余系。

构造一个p的完全剩余系

P={1,2,3,...,p-1}

因为 (a,p)=1，由引理2可得

A={a,2a,3a,...,(p-1)a},也是p的一个完全剩余系。由完全剩余系的性质

a*2a*3a*...*(p-1)a≡1*2*3*...*(p-1) (mod p)

所以1*2*3*...*(p-1)*a^p-1≡1*2*3*...*(p-1) (mod p)

(p-1)! *a^p-1≡(p-1)! (mod p)

((p-1),p)=1,两边同时约去 (p-1)!

a^p-1≡1(mod p)

它是欧拉定理的一个特殊情况，当p为质数时，φ(p) =p-1

四、模反元素

ed ≡ 1 mod φ(n)，已知e和φ(n)，求d，用扩展欧几里得算法

欧几里得是古希腊雅典著名的数学家，他著有《几何原本》，是当时的一本教科书，是欧式几何学的开创人。

欧几里得算法，就是碾转相除法，求两个正整数的最大公约数，已知a,b 求gcd(a,b)=gcd(b,a mod b)，编程中经常用递归去计算

扩展欧几里得算法

ed=kφ(n)+1

ed-kφ(n)=1

符合ax+by=1，求解x

裴蜀定理：对于任何整数a、b和gcd(a,b)=d,则一定存在整数x,y，使得ax+by=d

推论，a,b互质的充分必要条件是存在整数x,y,使得ax+by=1

a*x+b*y = gcd(a , b)

= gcd(b , a mod b)

= b * x1 + (a mod b) * y1

= b * x1 + (a - a / b * b) * y1 即

a*x+b*y = b * x1 + (a - a / b * b) * y1

化简上式，得

a*x+b*y = a*y1 - b*a/b*y1 + b*x1 ，即

a * x + b * y

= a * y1 + b * (x1-a/b*y1)

所以

x=y1

y=x1 - a/b*y1

用代码表示：

void exgcd(int a, int b, int &d, int &x ,int &y)
{

    if ( !b )
    {

　　　　　d = a;

        x = 1;

        y = 0;

        return;
    }

    int x1,y1;

    exgcd( b , a % b , d , x1 , y1 );

    x = y1;

    y = x1 - ( a / b ) * y1;

    return ;
}