标签：r1 r2 基础 RSA 算法 x2 x1 互质

RSA算法的必要性

密码学是一门保密通信技术，它将明文信息按双方约定的法则转换成只有特定人群才能看懂的密文以保证信息的安全传输。这样即使接收者之外的人得到传递的密文，也不知道信息的真正内容，从而达到安全传递信息的目的。

古典密码学和近代密码学一般是通过转译和反转译的方法，先将所发信息通过特殊的方法（这种方法收发双方事先约定好且保密）将所传递信息编码转译成一段看似没有规律的密文，将这段密文传给接收者后使用相同的方法反转译，获得真正信息。在传递过程中，即使密文被他人截获，由于不清楚破译方法，截获者也无法知晓真实信息，以此达到保护信息的目的。

但是，这种加密算法显然是有缺陷的。由于破译算法同时被发送者和接收者所共同知晓，那么第三方只需入侵当中任何一端，拿到编码（解码）方式，那么这种加密方式就不再安全。很明显，如果采用这种传统的加密算法，那么我们个人秘密和国家安全有一部分就被别人所掌握了。那么如何解决这个问题，让安全掌握在自己手里呢？

1976年，Whitefield Diffie和Martin Hellman发表了论文《密码学的新方向》，这标志着公钥密码学的诞生，他们因此也获得了2015年的图灵奖。公钥密码就能解决刚刚提到的问题，为什么呢？公钥密码体制的特点是采用两个相关的密钥将加密与解密操作分开，其中一个密钥是公开的，称为公钥，用于加密；另一个密钥是保密的，为用户专有，称为私钥，用于解密。

而最经典的公钥加密算法莫过于1987年由Rivest、Shamir和Adleman用数论方法构造的RSA算法，它是迄今为止理论上最成熟，最完善的公钥密码体制并已得到广泛应用。

RSA算法的安全性可以归纳为大整数分解的困难性，即给定两个大素数，将他们相乘很容易，但给出它们的乘积再找出它们的因子很困难。目前为止，世界上还尚未有任何可靠的攻击RSA算法的手段，只要密钥长度足够长而且使用方法得当，那用RSA加密的信息是很难破解的。

RSA算法基本内容

使用RSA算法加密大概分为一下几步：

1. 找两个大素数p，q。
2. 令N = p * q。
3. 令L = (p - 1) * (q - 1）。
4. 寻找比L小的且与L互质的一个数e。
5. 利用辗转相除法得出e*d-L*x=1，得到公钥N、e和私钥d。
6. 密文A^e % N = R（A为明文）。
7. 明文R^d % N = A (R为密文）。

RSA算法的安全性显而易见，由于RSA算法中取余数的操作只能单项进行，无法进行逆运算，在不知道私钥的情况下，即使是发送者也无法将密文破译成明文，而私钥只有接收者知道，从而使安全由接收者一方掌握。

RSA算法推导与证明

上文的1至5步都是在为生成公钥与私钥做准备，因此证明RSA算法的可行性的关键在于证明第6、7步。
换句话说，利用1至5步生成的公钥和私钥，真的能够完成第6、7步的转换吗？下面我们来证明一下。由于证明过程需要很多有关的数论，我尽力用更基础的数学语言来描述清楚。

在进行A^e % N = R操作时，实质是将A^e/N

则：
A^e = N * x + R

A^ed =（N * x + R)^d=x₁N^d+x₂N^d-1R¹+x₃N^d-2R²+……+x_dR^d（二项式定理）

A^ed/N =（x₁N^d+x₂N^d-1R¹+x₃N^d-2R²+……+x_dR^d）/N（等式两边同时除以N）

通过观察，可以看到等式右边前d-1项都是N的倍数，因此 A^ed/N 余数与 R^d/N 余数相等（由二项式定理得x_d=1）
即：A^ed % N = R^d % N

如果要证明 R^d % N = A，那么只需证明A^ed % N = A即可

在第5步中，我们利用辗转相除法得到等式e*d-L*x=1

进一步转换：

A^ed = A^1+L*x = A*A^L*x

如果要证明 A^ed % N = A，那么只需证明A^L*x = 1即可。

欧拉-费马定理

“A^L*x = 1”究竟成立吗，实际上是成立的，并且这个等式就是欧拉-费马定理（Euler-Fermat theorem）的最后结论的公式

欧拉-费马定理内容

设a,m∋N，且a和m互质，则a^ɸ(m) ≡ 1 (mod m) (即a^ɸ(m) % m = 1)。

其中ɸ(m)是欧拉函数，指的是小于m且与m互质的自然数的个数。而我们的步骤2和步骤3，实际上就是一个求ɸ(m)的过程，这两步同样是一个定理，但篇幅限制再次不过多赘述来证明它。

证明欧拉-费马定理预备工作

想要证明欧拉-费马定理，让我们先来了解三个小引理。

设a,m∋N，且a和m互质，并将所有小于m且与m互质的自然数组成一个集合X{x₁ , x₂ , …… , x_ɸ(m)}。

将集合X每一个元素同时乘上a得到一个新的集合P{ax₁ , ax₂ , …… , ax_ɸ(m)}。

我们可以得到

引理一：P中的元素模m的结果两两不同。

我们可以利用反证法来证明：

假设P中存在两个元素 p_i % m = p_j % m （ i ≠ j , i > j）

那么（ p_i - p_j ）% m = 0

(ax₁ - ax₂) % m = 0

a(x₁ - x₂) % m = 0

因为a与m互质，所以一定是 x₁ - x₂ = 0，才能使上式成立，

但是 x₁ 与 x₂是不相等的两个数，所以假设不成立。

引理一证毕。

引理二：P中的元素模m的结果均与m互质。

我们依然可以利用反证法来证明：

假设存在 p_i 与m不互质，

则p_i = ax_i = km + r

由于 ax_i 与m不互质

那么 ax_i - km 与m最大公约数一定大于1。（我们将其设为c）

c既是m的约数，也是r的约数，那么一定是 ax_i 的约数，且c > 1,

那么m和 ax_i 不互质，

但是前提条件中，a和m互质，x_i 也和m互质，

那么 ax_i 应该和m互质才对，

也就是说，以“存在 p_i 与m不互质”为假设得到的结论与前提条件矛盾，

所以假设不成立，所以引理二成立

引理二证毕。

引理三：若r₁与r₂均与m互质，且（r₁ * r₂）% m = r₂，则r₁ % m = 1。

证明这个引理，我们需要分情况讨论。

1.当 r₁ * r₂ = 0 ，（r₁ * r₂） % m = 0，不符合前提，舍去。

2.当 r₁ * r₂ < 0 , （r₁ * r₂） % m = r₁ * r₂

且（r₁ * r₂）% m = r₂，

所以r₁ = 1，所以r₁ % m = 1。

3.当 r₁ * r₂ > 0 ,

（r₁ * r₂） % m = r₂ 时

r₁ * r₂ = km + r₂，

（r₁ - 1） * r₂ = km，

（r₁ - 1） * r₂ % m = 0，

因为r₂ 与 m 互质，

所以（r₁ - 1） % m = 0，

所以 r₁ % m = 1。

引理三证毕。

模的四则运算

与实数一样，模算也可以进行四则运算

其中加减乘较为简单，这里给出运算规则且不再证明

设 a % m = r₁ ， b % m = r₂，则：

模加：（a + b） % m = r₁ + r₂

模减：（a - b） % m = r₁ - r₂

模乘：（a * b） % m = r₁ * r₂

证明欧拉-费马定理

在上面做了充分的准备后，证明欧拉-费马定理也就不是什么难事了。

首先，由于引理一和引理二，我们可以发现，

集合X和集合P中的元素是一一映射的关系，

因为它们都能表示“所有小于m且与m互质的自然数的集合”

所以我们得到等式关系：

p₁ * p₂ * …… * p_ɸ(m) % m = x₁ * x₂ * …… * x_ɸ(m) % m

ax₁ * ax₂ * …… * ax_ɸ(m) % m = x₁ * x₂ * …… * x_ɸ(m) % m

a^ɸ(m) * x₁ * x₂ * …… * x_ɸ(m) % m = x₁ * x₂ * …… * x_ɸ(m) % m

a^ɸ(m) * x₁ * x₂ * …… * x_ɸ(m) % m = x₁ % m * x₂ % m * …… * x_ɸ(m) % m（四则运算中的模乘）

a^ɸ(m) * x₁ * x₂ * …… * x_ɸ(m) % m = x₁ * x₂ * …… * x_ɸ(m)

根据引理三得：

a^ɸ(m) % m = 1

欧拉-费马定理证毕。

另外，特别的，当 m 为质数 p 是

a^（p-1） % p = 1

这就是大名鼎鼎的费马小定理（Fermat's little theorem）。

小结

通过证明欧拉-费马定理，我们证明了RSA算法的可行性和安全性。这篇博客将证明过程用不简洁的语言描述，意在帮助还没有学习过数论的同志理解RSA算法原理，还请知识体系更为完善的同志给予一些包涵。

标签：r1,r2,基础,RSA,算法,x2,x1,互质
From： https://www.cnblogs.com/xiangyang050615/p/17835148.html