C语言 实现RSA算法

RSA 算法是一种用于数据加密和数字签名的公钥加密算法，主要用于保证数据在传输过程中的安全性。

在 C 语言中实现 RSA 算法需要经过以下步骤：

1. 选择两个大质数 p 和 q，并计算 n=pq。

2. 计算欧拉函数 φ(n)，其中φ(n) = (p-1)(q-1)。

3. 选择一个整数 e，使得 e 与φ(n) 互质，并计算 d，使得 ed ≡ 1 (mod φ(n))。

4. 公钥是 (e,n)，私钥是 (d,n)。

5. 加密过程：对于明文 M，计算密文 C=Me mod n。

6. 解密过程：对于密文 C，计算明文 M=Cd mod n。

以下是一个简单的 C 语言实现的 RSA 算法的例子：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

// 求模运算
long long modulo(long long base, long long exponent, long long mod)
{
long long x = 1;
long long y = base;
while (exponent > 0)
{
if (exponent % 2 == 1)
x = (x * y) % mod;
y = (y * y) % mod;
exponent = exponent / 2;
}
return x % mod;
}

// 扩展欧几里得算法
long long gcdExtended(long long a, long long b, long long *x, long long *y)
{
if (a == 0)
{
*x = 0, *y = 1;
return b;
}
long long x1, y1;
long long gcd = gcdExtended(b%a, a, &x1, &y1);
*x = y1 - (b/a) * x1;
*y = x1;
return gcd;
}

//