RSA算法C++实现 报告+源代码bool prime(int n)
{
int m=sqrt(n);
for(int i=2;i<m;i++)
{
if(n%i==0)
break;
}
if(i>=m)
return 1;
else return 0;
}
RSA算法是一种非对称加密算法，它基于大数因子分解的困难性，广泛应用于网络安全领域，如数据加密、数字签名等。在这个C++实现中，主要包括以下几个关键知识点：
1. **素数检测**：在RSA算法中，选择两个大素数p和q是至关重要的。在给出的代码片段中，`prime(int n)`函数用于判断一个整数n是否为素数。它通过计算n的平方根m，并检查2到m-1之间的所有数是否能整除n，若找到一个能整除的数，则n不是素数，返回0；若没有找到，则n是素数，返回1。
2. **欧拉函数**：欧拉函数φ(n)表示小于等于n且与n互质的正整数的个数。在RSA中，欧拉函数用于确定公钥e的选择范围，要求e与φ(n)互素。
3. **模幂运算**：模幂运算`(a^b) % n`是RSA算法中的基础操作，用于加密和解密。在C++实现中，`multiplication(int a, int b, int n)`函数实现了这个运算，通过循环累乘并取模的方式得到结果。
4. **扩展欧几里得算法**：该算法用于计算两个整数的最大公约数，并且可以找到它们的乘法逆元。在RSA中，我们需要找到e的模φ(n)的乘法逆元d。`ExtendedEuclid(int f, int d, int *result)`函数实现这一功能，通过迭代过程计算出乘法逆元。
5. **RSA密钥生成**：根据上述步骤，B首先找到两个大素数p和q，计算n=p*q和φ(n)=(p-1)*(q-1)，然后选择e使得1<e<φ(n)且e与φ(n)互素，最后通过扩展欧几里得算法找到d，使得d为e的模φ(n)的乘法逆元。e和n构成公钥，d和n构成私钥。
6. **加密和解密过程**：加密时，明文m通过公式`c = m^e mod n`计算得出密文c；解密时，密文c通过公式`m = c^d mod n`还原为明文m。
7. **主函数**：主程序会引导用户输入两个素数p和q，验证它们的素性，然后输入公钥指数e，计算私钥d，接着对明文进行加密和解密。加密函数`Encryption()`和解密函数`Decipher()`实现上述的加密和解密公式。
8. **算法流程**：整个流程包括输入素数、计算欧拉函数、生成公私钥对、加密和解密操作。流程图有助于直观地理解每个步骤。
通过这个C++实现，学习者可以深入理解RSA算法的工作原理，以及如何在实际编程中应用这些数学概念。同时，实验过程中的团队合作也强调了协作和沟通的重要性，这对于提升个人技能和团队效率有着积极的影响。
