公钥密码加密解密（ELGamal，ECC椭圆曲线）

p=int(input("请输入素数p："))
g=int(input("请输入生成元g："))
x=int(input("请输入私钥x∈(1,p-1)："))
y=(g**x) % p
print("公钥为(" + str(y) +','+ str(g) +','+ str(p) + ')'+'\n'+"私钥为："+str(x))
k=int(input("请输入随机数k∈(1,p-1)："))
m=int(input("请输入明文m："))

# 加密函数
def encrypt(m):
 c1=(g**k)%p
 c2=(m*(y**k))%p
 return (c1,c2)

#分数模运算
def calculateMod(numerator, denominator, p):
    numerator_mod_p = (numerator % p + p) % p  # 处理负数情况
    denominator_mod_p = (denominator % p + p) % p

    # 计算逆元
    denominator_inverse = 1
    for i in range(1, p):
        # 判断i是否为分母的逆元
        if (denominator_mod_p * i) % p == 1:
            denominator_inverse = i
            break

    result = (numerator_mod_p * denominator_inverse) % p
    return result

c1,c2=encrypt(m)    #获得密文
#解密函数
def decrypt(c1,c2):
    plaintext=calculateMod(c2,c1**x,p)
    return plaintext

print("密文为："+str(encrypt(m)))
print("解密后的明文为："+str(decrypt(c1,c2)))

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

class ellipse         //定义椭圆类
{
public:
    int a;             //椭圆的长半轴
    int b;            //椭圆的短半轴
    int p;           //椭圆所在的有限域Fp
    ellipse(int u, int i, int o)   //构造函数
    {
        a = u;
        b = i;
        p = o;
    };
    int count = 0;   //记录点的个数,初始化为0
    typedef struct point     //定义点的数据结构
    {
        int x = 0;
        int y = 0;
    }Point;
    Point P[100];         //储存100个点
    void showPoint();     //显示点的函数
};
void ellipse::showPoint()   //显示点的函数定义
{
    for (int x = 0; x < p; x++)   //遍历Fp域中的x值
    {
        int temp = (x * x * x + a * x + b) % p;  //计算y的平方根的值
        for (int y = 0; y <= p; y++)   //遍历Fp域中的y值
        {
            if ((y * y - temp) % p == 0)   //如果y满足椭圆方程
            {
                P[count].x = x;            //记录点的x坐标
                P[count].y = y;           //记录点的y坐标
                count++;                  //点的个数加1
            }
        }
    }
    //输出点的坐标
    for (int j = 0; j < count; j++)
    {
        cout << "(" << P[j].x << "," << P[j].y << ")";
    }
}

// 计算最大公约数  
int get_gcd(int a, int b) {
    if (b == 0)
        return a;
    return get_gcd(b, a % b);
}

//分数模运算
int calculateMod(int numerator, int denominator, int p) {
    int numeratorModP = (numerator % p + p) % p; // 处理负数情况
    int denominatorModP = (denominator % p + p) % p;

    // 计算逆元
    int denominatorInverse = 1;
    for (int i = 1; i < p; ++i)
    {//判断i是否为分母的逆元
        if ((denominatorModP * i) % p == 1) {
            denominatorInverse = i;
            break;
        }
    }

    int result = (numeratorModP * denominatorInverse) % p;
    return result;
}

// 计算P+Q函数 
vector<int> calculate_p_q(int x1, int y1, int x2, int y2, int a, int b, int p) {
    int flag = 1;               //标记PQ是否同号,1为同号,-1为异号
    int member;                  //PQ的分子
    int denominator;           //PQ的分母
    if (x1 == x2 && y1 == y2) {    //P、Q重合,则P+Q=3P       
        member = 3 * (x1 * x1) + a;
        denominator = 2 * y1;
    }
    else {                       //P、Q不重合
        member = y2 - y1;
        denominator = x2 - x1;

    }

    //将分子和分母化为最简
    int gcd_value = get_gcd(member, denominator);
    member = member / gcd_value;
    denominator = denominator / gcd_value;

    // 计算x3,y3 
    int x3 = calculateMod(member * member - x1 * denominator * denominator - x2 * denominator * denominator, denominator * denominator, p);
    int y3 = calculateMod(member * (x1 - x3) - denominator * y1, denominator, p);
    vector<int> result;  //定义一个向量用于返回值
    result.push_back(x3);  //将x3的值添加到result中
    result.push_back(y3);  //将y3的值添加到result中
    return result;      //返回result
}

// 计算nP函数
vector<int> calculate_np(int x, int y, int n, int a, int b, int p) {
    // 记录P的坐标
    int x_old = x;
    int y_old = y;
    vector<int> result;  // 用于返回P的值
    for (int i = 0; i < n - 1; i++) {
        // 调用calculate_p_q()函数计算P+P的值
        vector<int> P_add_P = calculate_p_q(x_old, y_old, x_old, y_old, a, b, p);
        // 更新P的坐标值为P+P
        x_old = P_add_P[0];
        y_old = P_add_P[1];
    }
    // 将P的新坐标添加到result中
    result.push_back(x_old);
    result.push_back(y_old);
    return result;
}
vector<int> encrypt(int g1,int g2,int d,int a,int b,int p)
{
    //加密过程
    vector<int> publickey = calculate_np(g1, g2, d, a, b, p);//计算公钥
    cout << "公钥为：" << '(' << publickey[0] << ',' << publickey[1] << ')' << endl;
    int k;
    cout << "请输入随机数k：";
    cin >> k;
    vector<int> kY = calculate_np(publickey[0], publickey[1], k, a, b, p);
    vector<int> c1, c2;//密文
    c1 = calculate_np(g1, g2, k, a, b, p);//计算c1
    int x, y;
    cout << "请输入明文x, y:";
    cin >> x >> y;
    c2 = calculate_p_q(x, y, kY[0], kY[1], a, b, p);//计算c2
    //储存密文
    vector<int> result;
    result.push_back(c1[0]); result.push_back(c1[1]); result.push_back(c2[0]); result.push_back(c2[1]);
    return result;
}

//解密过程
vector<int> decrypt(vector<int> c,int d,int a,int b,int p)
{
    vector<int> dc1 = calculate_np(c[0], c[1], d, a, b, p);
    dc1[1] = -dc1[1];   // -dc1
    vector<int> result;
    result = calculate_p_q(c[2],c[3],dc1[0],dc1[1], a, b, p);
    return result;
}


int main()
{
    int a, b, p;
    cout << "请输入a,b,p:";//生成元
    cin >> a >> b >> p;
    ellipse A(a, b, p);
    cout << "椭圆曲线上的点集为：";
    A.showPoint();
    int g1, g2;
    cout << endl << "请输入生成元：";
    cin >> g1 >> g2;
    int d;//私钥
    cout << "请输入私钥d：";
    cin >> d;
    //加密过程
    vector<int> c= encrypt(g1, g2, d, a, b, p);
    cout << "密文为：" << endl;
    cout << '(' << c[0] << ',' << c[1] << ')';
    cout << '(' << c[2] << ',' << c[3] << ')';

    //解密过程
    vector<int>m= decrypt(c,d, a, b, p);
    cout <<endl <<"明文为：" << endl;
    cout << '(' << m[0] << ',' << m[1] << ')';
}