拓展欧几里得和RSA公钥加密

欧几里得

首先了解什么是欧里几德算法：

在求两个数的最大公因数的时候，我们常用的“辗转相除法”就是欧几里得算法。

举个栗子🖐：

求51和136的最大公因数。

首先计算$136/51=2 ...34$

取51和34，再次计算$51/34=1 …17$

取34和17，再次计算$34/17=2$

至此，我们得到51和136的最大公因数为17.

上面的计算式子我们也可以写成

$34=136-51\times2$

$17=51-34\times1$

（之所以这么写是因为后面扩展欧几里得的时候这样看更加方便）

扩展欧几里得算法：

对于给定的整数a和b，扩展的欧几里得算法不仅可以计算出最大公因数，并且可以得到两个整数 x 和 y，使其满足：

$ax+by=d=gcd(a,b)$

其中$d=gcd(a,b)$也就是a和b的最大公因数

对于上面的例子51和136，我们代入进这个式子可以得到

$51x+136y=17=gcd(51,136)$

具体计算的x和y的过程：

首先我们按照上面的过程计算出最大公因子为17。
列出式子$17=51-34\times1$
将“$34=136-51\times21$”代入进上式的34中，可以得到$17=51-(136-51\times2)\times1$

即$17=51\times3-136\times1$
至此我们得到式子$51\times3-136\times1=17$，即x=3，y=1

那么这个算法有什么用呢？🧐🧐

答案是用于RSA加密🥳🥳

简而言之，RSA即“公开密钥密码体制”。利用“非对称性”——即从一个方向计算很容易，而从另一个方向计算则很难，加密容易解密难！（例如，计算两个大质数的乘积很容易，但是从这个乘积计算出这两个因子则非常困难）。

利用这种思想，前辈们设计出RSA算法：

生成步骤：

举个例子🖐：

选择两个素数$p=61,q=53$
计算$p\times q=61\times 53=3233$

$z=\varphi(n)=(p-1)\times(q-1)=60\times 52=3120$
这里$e$和$d$的选择就可以用到伟大的扩展欧几里得算法了：
$e$需要和$z$互质，我们可以任意选择质数，计算$z$ 和$e$ 是否最大质数为1。比如这里我们选择$e=17$
接下来计算$d$，我们需要有$d\times e\:mod\:z=1$，可以得到$17\times d-3120\times k=1$
这就符合上面的欧几里得条件了：17和3120互质，最大公因数为1
套用扩展欧几里得公式，有计算最大公因子：

$9=3120-17\times 183$

$8=17-9\times 1$

$1=9-8\times 1$

计算$d$和$k$：

$\[\begin{equation*}\begin{split}1&=9-8\times 1\\&=9-(17-9\times1)\\&=9\times2-17\times1\\&=(3120-17\times183)\times2-17\times1\\&=3120\times2-367\times17\end{split} \end{equation*}\] $

即$17\times(-367)-3120\times(-2)=1$
至此我们可以得到$d=-367$。公钥即为$(3233，17)$，私钥为$(3233,-367)$
不过这里得到私钥-367感觉有点奇怪，我们可以加上个3120。因为$\[\begin{equation*}\begin{split}&17\times(-367)-3120\times(-2)\\&=[17\times(-367)+17\times3120]-[3120\times(-2)+17\times3120]\\&=17\times2753+15\times3120\\&=1\end{split} \end{equation*}\] $
优化后的私钥即为$(3233,2753)$