用欧拉公式在C++里实现RAS加密解密算法

欧拉公式可以表示为：

$$e^{ix} = \cos(x) + i\sin(x)$$

其中，$i$ 是虚数单位，满足 $i^2=-1$。

RAS算法是一种非对称加密算法，其中，加密和解密使用不同的密钥。

加密过程：

1. 选择两个不同的质数 $p$ 和 $q$，计算 $n=pq$。

2. 选择一个整数 $e$，满足 $1<e<\phi(n)$，且 $e$ 与 $\phi(n)$ 互质，其中 $\phi(n)=(p-1)(q-1)$。

3. 将要加密的明文 $M$ 转换为整数 $m$，使得 $0\leq m<n$。

4. 计算密文 $C\equiv m^e\pmod{n}$。

解密过程：

1. 找到一个整数 $d$，满足 $ed\equiv1\pmod{\phi(n)}$。

2. 计算明文 $M\equiv C^d\pmod{n}$。

下面是用欧拉公式在C++里实现RAS加密解密算法的代码：

#include <iostream>
#include <cmath>
using namespace std;

// 快速幂算法
long long pow_mod(long long a, long long b, long long mod) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

// 求最大公约数
long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 求扩展欧几里得算法
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    long long d = exgcd(b, a % b, x, y);
    long long z = x; x = y; y = z - a / b * y;
    return d;
}

// RAS加密算法
long long ras_encrypt(long long m, long long e, long long n) {
    return pow_mod(m, e, n);
}

// RAS解密算法
long long ras_decrypt(long long c, long long d, long long n) {
    return pow_mod(c, d, n);
}

// 生成密钥
void generate_key(long long p, long long q, long long &n, long long &e, long long &d) {
    n = p * q;
    long long phi = (p - 1) * (q - 1);
    do {
        e = rand() % (phi - 2) + 2;
    } while (gcd(e, phi) != 1);
    exgcd(e, phi, d, n);
    if (d < 0) d += phi;
}

int main() {
    long long p = 61, q = 53; // 选择两个质数
    long long n, e, d;
    generate_key(p, q, n, e, d); // 生成公钥和私钥
    cout << "公钥: (" << e << ", " << n << ")" << endl;
    cout << "私钥: (" << d << ", " << n << ")" << endl;

    long long m = 123; // 明文
    long long c = ras_encrypt(m, e, n); // 加密
    long long m2 = ras_decrypt(c, d, n); // 解密
    cout << "明文: " << m << endl;
    cout << "密文: " << c << endl;
    cout << "解密: " << m2 << endl;

    return 0;
}