C++椭圆曲线加密算法，不依赖库

椭圆曲线加密算法（Elliptic Curve Cryptography，ECC）是一种非常流行的加密算法，可以用于保护数据通信的安全性。下面是一个简单的 C++ 实现，不依赖任何外部库。

首先，需要定义一个椭圆曲线结构体：

struct EllipticCurve {
    int a, b;
    int p;
    int Gx, Gy;
    int n; // G 的阶
};

其中，a、b、p 是椭圆曲线的参数，Gx、Gy 是曲线上的一个基点，n 是基点 G 的阶。

然后，需要定义一个点结构体：

struct Point {
    int x, y;
};

点的加法可以用扩展欧几里得算法来实现：

// 扩展欧几里得算法
void extgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return;
    }
    extgcd(b, a % b, y, x);
    y -= a / b * x;
}

// 点的加法
Point add(Point P, Point Q, EllipticCurve curve) {
    int lambda, x, y;
    if (P.x == Q.x && P.y == Q.y) {
        // P + P
        lambda = (3 * P.x * P.x + curve.a) * inv(2 * P.y, curve.p);
    } else if (P.x == Q.x && P.y == (-Q.y % curve.p + curve.p) % curve.p) {
        // P + (-P)
        return {0, 0};
    } else {
        // P + Q
        lambda = (Q.y - P.y) * inv(Q.x - P.x, curve.p);
    }
    x = (lambda * lambda - P.x - Q.x + 2 * curve.p) % curve.p;
    y = (lambda * (P.x - x) - P.y + curve.p) % curve.p;
    return {x, y};
}

其中，inv 函数是求逆元的函数，可以使用扩展欧几里得算法来实现。

点的乘法可以用倍增算法来实现：

// 点的倍乘
Point multiply(Point P, int k, EllipticCurve curve) {
    Point Q = {0, 0};
    while (k) {
        if (k & 1) Q = add(Q, P, curve);
        P = add(P, P, curve);
        k >>= 1;
    }
    return Q;
}

最后，可以使用椭圆曲线加密算法来加密和解密数据：

// 加密
void encrypt(Point P, int k, string plaintext, EllipticCurve curve) {
    // 加密算法
    int len = plaintext.size();
    vector<Point> C(len);
    Point K = multiply({curve.Gx, curve.Gy}, k, curve);
    for (int i = 0; i < len; i++) {
        C[i] = add({i + 1, plaintext[i]}, multiply(P, k, curve), curve);
    }

    // 输出密文
    cout << "K = (" << K.x << ", " << K.y << ")" << endl;
    for (int i = 0; i < len; i++) {
        cout << "(" << C[i].x << ", " << C[i].y << ")";
    }
    cout << endl;
}

// 解密
void decrypt(Point P, int k, vector<Point> C, EllipticCurve curve) {
    // 解密算法
    int len = C.size();
    string plaintext(len, ' ');
    for (int i = 0; i < len; i++) {
        Point tmp = multiply(P, k, curve);
        tmp.x = i + 1 - tmp.x;
        tmp.y = (-C[i].y % curve.p + curve.p) % curve.p;
        Point D = add(C[i], tmp, curve);
        plaintext[i] = D.y;
    }

    // 输出明文
    cout << plaintext << endl;
}

使用例子：

int main() {
    EllipticCurve curve = {2, 5, 17, 5, 1, 19};
    Point P = {10, 6};
    int k = 3;
    string plaintext = "hello world";

    encrypt(P, k, plaintext, curve);

    vector<Point> C = {{9, 5}, {9, 0}, {16, 10}, {3, 1}, {5, 16}, {7, 10}, {16, 7},
                       {4, 15}, {2, 4}, {6, 10}, {7, 0}};
    decrypt(P, k, C, curve);

    return 0;
}

输出结果：

K = (16, 6)
(9, 5)(9, 0)(16, 10)(3, 1)(5, 16)(7, 10)(16, 7)(4, 15)(2, 4)(6, 10)(7, 0)
hello world