RSA RSA加密算法详解序言算法说明真描述密钥的生成加密解密证明RSA算法c如何快速计算实现RSA算法的有效实现` a^m mod n `？ C码怎么计算`(N )？ C代码如何计算` e )相对于`(n ) `的乘法逆矩阵` d )？ C码如何检测一个数是素数？ 如何找到足够大的素数` p，q `？
RSA加密算法详细信息
随着网络的快速发展和普及，对称密码算法越来越难以满足网络通信中对安全性的需求，随着人们对密码学研究的深入，出现了不对称密码算法，并迅速应用于网络通信。 ()。 额，随便胡说八道：
在由n个网络用户组成的网络通信区域中，如果使用对称加密算法来确保通信安全，则任意两个用户之间的通信需要一个密钥，因此管理的密钥为[n-1]！ 个，在用户数多的情况下，该数量庞大，消耗的资源也庞大； 与对称加密算法相比，使用非对称加密算法可以节省更多的资源，因为任何用户与其他用户通信所需的密钥对只有2n个。
算法说明我是这么理解的
RSA算法公开公钥，任何人都可以用公钥加密，但得到的密文只能由持有密钥的人解密。
如果RSA算法只具有公钥和密文，则很难解密密文的原因如下。
对于两个不相等的大素数p，q的乘积n，当只知道n而不知道p，q时，cqdtd的正整数中与n为素数的数很难计算(这个数称为[n] )。
由欧拉函数可知，(n )=(p-1 ) * ) q-1 )。
真密钥的生成选择两个不相等的大素数p，q，计算(n=p*q，(n )=(p-1 ) ) q-1 )，随机数e ) 0e) n )，e和) n )彼此互质。 计算d=e^(-1 ) mod(n ) n ) )，也就是说，计算e对) n )的乘法逆矩阵)。
经过以上计算得到：
公钥： KU={e，n}
私钥： KR={d，p，q}或KR={d，n}
加密对明文进行分组，zrdsw在每个分组中拥有cqdtd，明文c用m表示密文。
已知：明文m，公钥KU={e，n}，
有： C=M^e mod n。
解密包括密文c、密钥KR={d，n}、
有： M=C^d mod n。
解密证书m
=C^d mod n
=(m^emodn ) ^d mod n
=M^ed mod n
=m^(1k) n ) ) mod n ) ed=1 mod (n ) n，因为k是整数) ) ) ) ) ) ) ) )=m^(1k) n ) ) ) ) ) ) n ) n ) n ) n ) n ) n ) n
=[m*(m^k(n ) ] mod n
=mmodn*[(m^(n ) ) ^k ] mod n
=mmodn*1^kmodn((n )=n-1，m^ ) n-1 ) mod n=1，因此m^) n ) mod n=1) ) ) )。
=M mod n
=M
正如我之前所说：
对于两个不相等的大素数p，q的乘积n，当只知道n而不知道p，q时，很难求出(n ) ) n是两个大素数的乘积，所以不能用质数，而是用欧拉函数求出) n )，而且n是因此
RSA算法c要实现RSA算法的有效实现，如何快速计算a^m mod n？ 这里是辅助计算的算法—— 快速取模指数算法
举个例子：
a^13=(() ) a^1)2*a^1) ^2 * a^0) )2*a^1
上式中最右边的a的乘数与13的二进制数中表示1101各位的值有关。 例如
101的第一位是1，(() a^1)2*a^1)2*a^0)2*a^1的第一位a的乘数是1，
101第二位是1，() (a^1)2*a^1)2*a^0)2*a^1第二a的乘数是1，
101第三位为0，() (a^1)2*a^1)2*a^0)2*a^1第3a的乘数为0，
101第四位是1，() (a^1)2*a^1)2*a^0)2*a^1第四a的乘数是1。
a^13=(((a^1)2*a^1) ^2 * a^0)2*a^1计算a^13 mod n不会简化计算过程，但对括号中的每个值进行mod n运算可以大大简化计算过程这意味着：
a^13modn=((a^1modn )2modn*a^1modn ) ^2 mod n * a^0 mod n )2modn*a^1modn
当然，a的乘数的二进制表示等号右边有几位就有几个括号和a。
在上面的计算中，可以看到等号的右边不断地重复着(x ) ^2 mod n * a^y mod n。 x是上次计算的结果，y是当前计算对应的位的值。
c代码intmod_square(inta，
int m, int n){int i, j, c;for (i = 0; m / pow(2, i) >= 1; i++);//判断 m 二进制有几位int ZU[100];j = i; c = 1;for (; i > 0; i--)//用 ZU 数组存放 m 二进制各位，从低位到高位存放{ZU[i - 1] = m / pow(2, i - 1);m = m % int(pow(2, i - 1));}for (; j > 0; j--){if (ZU[j - 1] == 0)c = (c*c) % n;//位值为 0 时else c = (((c*c) % n)*a) % n;//位值为 1 时}return c;} 如何计算φ(n)?对于φ(n)可以使用欧拉函数的性质求得。
欧拉函数的性质：
(1)n是素数时，φ(n)=n-1;
(2)n=p*q,且p和q是互异的素数时，φ(n) = φ(p) * φ(q) = (p-1) * (q-1);
(3)对于任何大于1的整数均可表示成素数幂之积的形式，即n= p1^e1 * p2^e2 * p3^e3 *p4^e4 ..... pt^et，pi (i=1,2,...,t)是素数，有以下定理成立。
定理：
φ(n)=p1^(e1-1)*(p1-1) * p2^(e2-1)*(p2-1) *..... pt^(et-1) * (pt-1)
或表示成：
φ(n)=n * (1- 1/p1) * (1- 1/p2) * (1- 1/p3) * ..... (1- 1/pt)
查了一些资料，发现p1、p2、p3.....pt等都是n的质因数，下面介绍快速求得n表示成素数幂之积的形式中的素数的方法：
(因为表达能力不足，只能用代码描述 ：)
这个循环中输出的i都是n的质因数，可以用φ(n)=n * (1- 1/p1) * (1- 1/p2) * (1- 1/p3) * ..... (1- 1/pt)求φ(n)。
可以用扩展fkdgb算法、欧拉函数等来计算乘法逆元，但只有扩展fkdgb算法具有普遍性，故这里介绍扩展fkdgb算法c代码实现。
扩展fkdgb算法的一种描述：
要计算a^(-1) mond n，引入中间变量Xi,基于商qi和余数ri之间的关系，首先将n和a分别赋值给ri的前两个变量，将0和1分别赋值给xi的前两个变量，完成初始化；然后循环利用qi = ri-1 / ri，ri+1 = ri-1 - qi * ri和xi+1 = xi - qi * xi,直到余数ri = 1结束循环,xi就是a对于n的乘法逆元。前提是a与n互素，否则a对于n的乘法逆元不存在。