一个简单的实例:A向B发送信息的加解密,签名和验证
通过有限域椭圆曲线构建一个循环群,利用椭圆曲线的离散对数问题实现对信息加解密,原理和实现参考链接:有限域上的椭圆曲线加密|附加解密cpp代码_哔哩哔哩_bilibili
签名和验证:
代码如下:
头文件:hash.h
#pragma once#include <stdio.h>#include <stdlib.h>#include <stdint.h>#include <string.h>#include<iostream>using namespace std;template<typename T1, typename T2>constexpr auto SHA256_ROTL(T1 a, T2 b) { return ((a << (32 - b)) | (a >> b)); }template<typename T1, typename T2>constexpr auto SHA256_SR(T1 a, T2 b) { return ((a >> b)); }template<typename T1, typename T2, typename T3>constexpr auto SHA256_Ch(T1 x, T2 y, T3 z) { return ((x&y) ^ ((~x)&z)); }template<typename T1, typename T2, typename T3>constexpr auto SHA256_Maj(T1 x, T2 y, T3 z) { return ((x & y) ^ (x & z) ^ (y & z)); }template<typename T1>constexpr auto SHA256_E0(T1 x) { return SHA256_ROTL(x, 2) ^ SHA256_ROTL(x, 13) ^ SHA256_ROTL(x, 22); }template<typename T1>constexpr auto SHA256_E1(T1 x) { return SHA256_ROTL(x, 6) ^ SHA256_ROTL(x, 11) ^ SHA256_ROTL(x, 25); }template<typename T1>constexpr auto SHA256_O0(T1 x) { return SHA256_SR(x, 3) ^ SHA256_ROTL(x, 18) ^ SHA256_ROTL(x, 7); }template<typename T1>constexpr auto SHA256_O1(T1 x) { return SHA256_ROTL(x, 17) ^ SHA256_ROTL(x, 19) ^ SHA256_SR(x, 10); }extern char* StrSHA256(const char* str, long long length, char* sha256) {char * pp, *ppend;unsigned int a, b, c, d, e, f, g, h, h1, h2, h3, h4, h5, h6, h7, h0, w[64];unsigned int L;h0 = 0x6a09e667, h1 = 0xbb67ae85, h2 = 0x3c6ef372, h3 = 0xa54ff53a;h4 = 0x510e527f, h5 = 0x9b05688c, h6 = 0x1f83d9ab, h7 = 0x5be0cd19;unsigned int k[64] = {0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,};if (length % 64 >= 56)L = length + (128 - length % 64);elseL = length + (64 - length % 64);if (!(pp = (char *)malloc((unsigned long)L)))return 0;int i = 0;for (i = 0; i < length; i++) {pp[i + 3 - 2 * (i % 4)] = str[i];if (i >= 64) {pp[i + 3 - 2 * (i % 4)] = str[i];}}for (i = length; i < L; i++)if (i == length)pp[i + 3 - 2 * (i % 4)] = 128;elsepp[i + 3 - 2 * (i % 4)] = 0;*((long*)(pp + L - 4)) = length << 3;*((long*)(pp + L - 8)) = length >> 29;ppend = pp + L;for (; pp < ppend; pp += 64) {for (i = 0; i < 16; i++) {w[i] = ((long*)pp)[i];}for (i = 16; i < 64; i++) {w[i] = (SHA256_O1(w[i - 2]) + w[i - 7] + SHA256_O0(w[i - 15]) + w[i - 16]);}a = h0, b = h1, c = h2, d = h3, e = h4, f = h5, g = h6, h = h7;for (i = 0; i < 64; i++) {unsigned int temp1 = h + SHA256_E1(e) + SHA256_Ch(e, f, g) + k[i] + w[i];unsigned int temp2 = SHA256_E0(a) + SHA256_Maj(a, b, c);h = g, g = f, f = e;e = d + temp1;d = c, c = b, b = a;a = temp1 + temp2;}h0 += a, h1 += b, h2 += c, h3 += d;h4 += e, h5 += f, h6 += g, h7 += h;};sprintf(sha256, "%08X%08X%08X%08X%08X%08X%08X%08X", h0, h1, h2, h3, h4, h5, h6, h7);return sha256;}int myhash(const char* text){char sha256[65];//puts(StrSHA256(text, strlen(text), sha256));StrSHA256(text, strlen(text), sha256);//cout << sha256 << endl;int num = 0, j=1;for (char i : sha256){num = num + (int)i*j++;}return num;}
头文件:ECurve.h
#pragma once#include <iostream>#include<cmath>#include<vector>#include<string>#include <cstdlib>#include <ctime>#include"hash.h"using namespace std;struct point {long int x;long int y;point(long int x1 = 0, long int y1 = 0) :x(x1), y(y1) {}friend inline bool operator == (const point& P, const point& Q) {return (P.x == Q.x&&P.y == Q.y);//记得加friend,以外部函数的方式调用}};class ECurve{public:ECurve(int p1=0, int a1=0, int b1=0) : p(p1), a(a1), b(b1) {}//构造函数ECurve(const ECurve& C);//拷贝构造ECurve& operator=(const ECurve& C);//拷贝赋值~ECurve(){}//析构函数void showEpab();//显示循环群元素int unEqLamda(point P, point Q);//计算P不等于Q时的Lamdaint equalLamda(point P); //计算P等于Q时的Lamdapoint PplusQ(point P, point Q);//计算P+Qpoint kP(int k,point P); //计算kP int getOrd(point P);//求该元素的阶vector<int> EncodeMsg(int key, point A_Q, point B_Q, string message);//对明文加密string DcodeMsg(int key, vector<int> secret); //对密文解密vector<int> sign(const char* msg, int A_private_key, point P, int n);//签名bool verify(const char* msg, vector<int> sig, point P, int n);//对签名验证private:int p, a, b;//构建循环群的参数};//ECurve::ECurve(int p1, int a1, int b1) :p(p1), a(a1), b(b1) {}inline ECurve::ECurve(const ECurve& C) {p = C.p;a = C.a;b = C.b;}inline ECurve& ECurve::operator=(const ECurve& C) {p = C.p;a = C.a;b = C.b;return *this;}//求两数最大公因式int gcd(int x, int y){if (y == 0)return x;elsereturn gcd(y, x%y);}//求得分母逆元(扩展欧几里得)int get_inverse_element(int num, int p){for (int i = 1; i < p; i++){if (((i*num) % p) == 1)return i;}return -1;}void ECurve::showEpab(){int n = 0;//存储该曲线循环群元素个数unsigned long long z;for (int x = 1; x < p; x++){z = pow(x,3)+ a * x + b;if (z >= p) //模p平方剩余{for (int y = 1; y < p; y++){if (((y*y) % p) == (z % p)) //成立求得一个循环群元素{cout << "(" << x << "," << y << ") ";n += 1;}}}}cout << endl << "该曲线循环群元素个数:" << n << endl;}int ECurve::unEqLamda(point P, point Q) {long int up = ((Q.y - P.y) % p + p) % p, down = ((Q.x - P.x) % p + p) % p;//分子、分母//将分子和分母化为最简long int gcd_value = gcd(up, down);up = int(up / gcd_value);down = int(down / gcd_value);//求分母的逆元long int inverse_value = get_inverse_element(down, p);long long int lamda = (up*inverse_value);//求得lamdareturn lamda;}int ECurve::equalLamda(point P) {long int up = ((3 * P.x * P.x + a) % p + p) % p, down = ((2 * P.y) % p + p) % p;//分子、分母//将分子和分母化为最简long int gcd_value = gcd(up, down);up = int(up / gcd_value);down = int(down / gcd_value);//求分母的逆元long int inverse_value = get_inverse_element(down, p);long long int lamda = (up*inverse_value);//求得lamdareturn lamda;}point ECurve::PplusQ(point P , point Q ){point temp;if ((P.x == 0 && P.y == 0) || (Q.x == 0 && Q.y == 0)) //P为O or Q为O 情况,返回非零那一个if (P.x == 0)temp.x = Q.x, temp.y = Q.y;elsetemp.x = P.x, temp.y = P.y;else if (P.x == Q.x&&P.y == p - Q.y)//P为Q的加法逆元,相加为无穷远点(0,0){temp.x = 0;temp.y = 0;return temp;}else{//P,Q都不为O时且非加法逆元long long int lamda;if (P==Q)//P and Q 相等情况lamda = equalLamda(P);else//P and Q 不相等lamda = unEqLamda(P, Q);temp.x = ((lamda * lamda - P.x - Q.x) % p +p) % p;temp.y = ((lamda * (P.x - temp.x) - P.y) % p + p) % p;}return temp;}point ECurve::kP(int k, point P){point temp;if (k == 1)temp.x = P.x, temp.y = P.y;else{temp = PplusQ(P, P); //k个P相加for (; k > 2; k--){temp = PplusQ(temp, P);}}return temp;}int ECurve::getOrd(point P) //求元素的阶{int n = 1;point temp = P;while (1){n += 1;temp = PplusQ(temp, P);if (temp.x == 0 && temp.y == 0)break;}return n;}//对明文加密vector<int> ECurve::EncodeMsg(int A_key, point P, point B_Q, string message){vector<int> secretMsg; //密文point C1;//A的公钥C1 = kP(A_key, P);secretMsg.push_back(C1.x);secretMsg.push_back(C1.y);point kQ;kQ = kP(A_key, B_Q);unsigned long int C2;for (int i = 0; i < message.length(); i++)//对逐个字符编码加密{C2 = (int)message[i] + kQ.x;secretMsg.push_back(C2);}return secretMsg;}//对密文解密string ECurve::DcodeMsg(int B_key, vector<int> secret){string Dmessage=""; //明文point C1;C1.x = secret[0];C1.y = secret[1];point xC1;xC1 = kP(B_key, C1);int num;for (int i = 2; i < secret.size(); i++)//对逐个数字解密编码{num = secret[i] - xC1.x;Dmessage += (char)num;}return Dmessage;}vector<int> ECurve::sign(const char* msg, int A_private_key, point P, int n){point A_Q;A_Q = kP(A_private_key, P);int d = rand() % (n - 2 + 1) + 1;//随机数[1,n)point K;K = kP(d, P);int r = K.x%n;int e;e = myhash(msg);int inv_d = get_inverse_element(d, n);int s = (inv_d*(e + A_private_key * r)) % n;vector<int> temp;temp.push_back(A_Q.x);temp.push_back(A_Q.y);temp.push_back(r);temp.push_back(s);return temp;}bool ECurve::verify(const char* msg, vector<int> sig, point P, int n){point Q;Q.x = sig[0];Q.y = sig[1];int r = sig[2];int s = sig[3];if ((r <= 0 && r >= n)|| (s <= 0 && s >= n))return false;int inv_s = get_inverse_element(s, n);int w = inv_s % n;int e = myhash(msg);int u1 = (e * w) % n;int u2 = (r * w) % n;point temp, temp1, temp2;temp1 = kP(u1, P);temp2 = kP(u2, Q);temp = PplusQ(temp1, temp2);int v = temp.x%n;return v == r;}
主函数:main.cpp
#include"ECurve.h"namespace myspace{void test_one(){int p = 2833, a = 1, b = 1;ECurve C(p, a, b);C.showEpab();point P;P.x = 1341;P.y = 854;cout << "在以上循环群中选出一个点P(" << P.x << "," << P.y << ")" << endl;int n = C.getOrd(P);cout << "生成元P(" << P.x << "," << P.y << ")的阶为:" << n << endl;int B_private_key;cout << "输入B的私钥:";cin >> B_private_key;point B_Q; //B的公钥B_Q = C.kP(B_private_key, P);cout <<"由生成元P("<<P.x<<","<<P.y<<"),私钥:"<< B_private_key <<",生成B的公钥Q("<<B_Q.x<<","<<B_Q.y<<")"<<endl;cout << endl << "===========A获得B的公钥,向B发送消息==========="<<endl;cout << "输入A的私钥:";int A_private_key;cin >> A_private_key;cout << "输入明文:";string A_Msg;cin >> A_Msg;vector<int> A_EncodeMsg;//明文加密-密文A_EncodeMsg = C.EncodeMsg(A_private_key, P, B_Q, A_Msg);cout << "A加密后将:";for (int i = 0; i < A_EncodeMsg.size(); i++){cout << A_EncodeMsg[i]<<"-";}cout << "发送给B" << endl;cout << endl << "===========B解密==========="<< endl;string B_DecodeMsg;//密文解密-明文int mykey;while (1){cout << "输入B的私钥:";cin >> mykey;B_DecodeMsg = C.DcodeMsg(mykey, A_EncodeMsg);//用私钥解密cout << "B解密得到明文:";cout << B_DecodeMsg;cout << endl;}}void test_two() //求元素的阶{int p = 11, a = 1, b = 6;ECurve C(p, a, b);C.showEpab();point P;cout << "=========求元素的阶=========" << endl;while (1){cout << "在以上循环群中选出一个点P:";cin >> P.x >> P.y;int n = C.getOrd(P);cout << "生成元P(" << P.x << "," << P.y << ")的阶为:" << n << endl;}}void test_three() //求P+Q的结果{int p = 11, a = 1, b = 6;ECurve C(p, a, b);C.showEpab();point P;P.x = 2;P.y = 7;cout << "=========求P+Q=========" << endl;while (1){point Q;cout << "在以上循环群中选出一个点Q:";cin >> Q.x >> Q.y;point T;T = C.PplusQ(P, Q);cout << "T: " << T.x << "," << T.y << endl;}}void test_four()//求kP{int p = 2833, a = 1, b = 1;ECurve C(p, a, b);C.showEpab();point P;P.x = 1341;P.y = 854;cout << "=========求kP=========" << endl;while (1){int k;cout << "输入k:";cin >> k;point temp;temp = C.kP(k, P);cout << "temp: " << temp.x << "," << temp.y << endl;}}void test_myhash(){const char* text = "asd";int num = myhash(text);cout << num;}void sign_verify(){int p = 2833, a = 1, b = 1;ECurve C(p, a, b);point P;P.x = 1341;P.y = 854;int n = C.getOrd(P);cout << "===========sign_verify()===========" << endl;cout << "输入A的私钥:";int A_private_key;cin >> A_private_key;const char* msg = "this is an important message";const char* msg2 = "thix is an important message";vector<int> sig;sig = C.sign(msg, A_private_key, P, n);bool test;test = C.verify(msg2, sig, P, n);cout << test;}void testIN_hash() {string text;cin >> text;const char* text2 = text.c_str();int num=myhash(text2);cout << num;//char sha256[65];//puts(StrSHA256(text2, strlen(text2), sha256));}}int main(){myspace::test_one(); //加密解密//myspace::test_two(); //求元素的阶//myspace::test_three();//求P+Q的结果//myspace::test_four();//求kP//myspace::sign_verify(); //私钥输入随机一个数,修改msg和msg2,内容相同为1,不同为0//myspace::test_myhash();//myspace::testIN_hash(); //对输入字符哈希return 0;}
ECC有限域椭圆曲线加密算法实例---构建椭圆曲线的循环群 利用椭圆曲线离散对数问题实现信息的加密解密 签名和验证