C#RSA密码以及利用欧几里得算法实现两数互质的判断

article/2025/7/20 1:12:50

最近做课程设计,想到以前看过RSA密码的相关内容，于是就想用刚学的C#做一个数字加密系统。RSA加密的流程如下：

来看一个“玩具式”的例子：

(1)选取两个素数p=2,q=11,于是N=22.

(2)构造数 $\phi (22)=(2-1)\times (11-1)=10$ ,这是小于22且不含因数2和11的自然数的个数。

(3)选一个小于 $\phi (22)=10$ 且与10互素的数a,可选择的数有3,7,和9.我们选a=3。

(4)求方程 $ab\equiv 1+\phi (22)r(mod N)$ 的自然数解,从而求出b。在我们这个情况下,求得

$3\times 7-10\times 2=1$

于是我们选择的a使得b=7.

(5)为了让人们能够对一串小于22的自然数u加密,我们公开 $（a,N）=(3,22)$ $(a,N)=(3,22)$ .加密的操作如下：

$u\rightarrow v\equiv u^{3}(mod22)$

(6)我们知道数b,就可以对v进行解密;别人谁也做不到.

$u\equiv v^{7}(mod22)$

现在来看我们这个私密的RSA密码是如何运作的。首先让我们对数173124进行加密,然后将加密的结果解密.我们把这个数分裂成（17）（3）（12）（4）。注意分段法一定要把数字分成前后两数组合小于N的最大整数，列如：不能把（17）拆分成（1）和（7）也不能将（3）和后面的（1）组合成（31>22）。进行如下加密：

$17\rightarrow 17^{3}=223\times 22+\textbf{7}$

$3\rightarrow 3^{3}=22\times 1+\textbf{5}$

$12\rightarrow 12^{3}=78\times 22+\mathbf{12}$

$4\rightarrow 4^{3}=22\times 2+\textbf{20}$

加了密的数串于是为 $v=(7)(5)(12)(20)$

通过规定的方法对它解密如下：

$7\rightarrow 7^{7}=37422\times 22+\mathbf{17}$

$5\rightarrow 5^{7}=3551\times 22+\mathbf{3}$

$12\rightarrow 12^{7}=1628718\times 22+\boldsymbol{12}$

$20\rightarrow 20^{7}=58181818\times 22+\textbf{4}$

我在编写程序寻找自选数a的过程中发现如果要寻找合适的a就要编写一套判断两数互质的算法，如果列出两个数的素数分解式再判断是否有重合未免太过复杂也很难操作，正好在这一章的内容里有欧几里得算法(辗转求余算法)，我才突然醒悟：这不就是求最大公因数吗！如果最大公因数是1，则代表两数互质。

所以，先复习一下欧几里得算法，这个算法可简述为以下等式：

$hcf(a,b)=hcf(b,r)$

$hcf(x,y)$ 表示对x,y求最大公因数。

而我们有长除法 $a=b\times q+r$

来看一个例子(7540,546)

$(1)7540=546\times 13+442\Rightarrow hcf(7540,546)=hcf(546,442)$

$(2)546=442\times 1+104\Rightarrow hcf(546,442)=hcf(442,104)$

$(3)442=104\times 4+26\Rightarrow hcf(442,104)=hcf(104,26)$

$(4)104=26\times 4+0\Rightarrow hcf(7540,526)=26$

求得的最大公因数是26.

选取候选数a的代码：

int[] a = new int[20];
Find_relativelyPrime(phi,p,q,ref a)；//求解a
public void Find_relativelyPrime(int phi,int p,int q,ref int[] a){int k = phi;int count=0;for(int i = 2; i < phi; i++){int j = i;while (j!=0&&j!=1){Euclid(ref phi,ref j);//欧几里得运算}//若经历过循环欧几里得运算余数j=1，两数互质；若j=0；两数存在最大公因数，因此不互质；if (j != 0 && i!=p && i!=q) {//若两数互质，且i不等于构造欧拉数phi(p,q)的两因子，则选取为候选公开数i加入数组a;a[count]=i;count++;}if (count == 20)break;phi = k;}}public void Euclid(ref int phi,ref int i){int temp=i;i = phi % i;phi = temp;}

案例来自于《数学桥》。如果把加密后的数字进行ASCII转换，就可以得到更复杂的加密密钥。