信息计算2019级1班27号许鹏程

许鹏程 · 发表于 2022-6-2 12:07:09

ECC椭圆曲线加解密

ECC是一种基于椭圆曲线数学的公开密钥加密算法，其本质是利用离散对数问题实现加密。一条椭圆曲线就是一组被 y^2 = x^3 + ax + b 定义的且满足 4a^3 + 27b^2 ≠ 0 的点集。

ECC技术要求
通常将Fp上的一条椭圆曲线描述为T=(p,a,b,G,n,h)p、a、b确定一条椭圆曲线（p为质数，(mod p)运算）G为基点，n为点G的阶，h是椭圆曲线上所有点的个数m与n相除的商的整数部分

参量选择要求：

p越大安全性越好，但会导致计算速度变慢
200-bit左右可满足一般安全要求
n应为质数
h≤4；p≠n×h ；pt≠1(mod n) (1≤t＜20)
4a3＋27b2≠0 (mod p)

许鹏程 · 发表于 2022-6-2 12:07:29

#pragma once
#include <vector>
#include "stdafx.h"
#include "Key.h"
#include "StdAfx.h"
#include "ECC.h"
#include <math.h>
#include <sstream>
#include <stdlib.h>
#include <string>
#include <iomanip>
class ECC
{
public:
ECC(int a,int b,int p);
virtual ~ECC(void);
void encrypt(const std::vector<Point> &Pm,Key &key,std::vector<Cipher> &result,int k=-1);
void decrypt(const std::vector<Cipher>& ciphers,int x,std::vector<Point> &result);
const std::vector<Generator> getGenerators()const;
void genKey(Key& result,int gIndex=-1,int x=-1);
void decodePlainPoints(const std::vector<Point>& Pm,std::string &result);
void encodePlainText(const char* plainText,std::vector<Point> &result);
static bool isPrime(int n);
protected:
int mA,mB,mP;
std::vector<Point> mPoints;
std::vector<Generator> mGenerators;
Dictionary mDictionary;
private:
void getAllPoints();
void getAllOrders();
int getOrder(const Point&p);
int ex_gcd(int a,int b,int& x,int& y);
int getInverse(int a,int p);
Point getMultiplePoint(int k,const Point& p);
Point add(const Point& p1,const Point& p2);
int mod(int a,int p);
};
ECC::ECC(int a = 4, int b = 20, int p = 29)
{
this->mA = a;
this->mB = b;
this->mP = p;
this->getAllPoints();
this->getAllOrders();
}
ECC::~ECC(void)
{
}
void ECC::getAllPoints()
{
int left, right = 0;
for (int x = 0; x < mP; x++)
{
right = x * x * x + mA * x + mB;
for (int y = 0; y < mP; y++)
{
left = y * y;
if (mod(left, mP) == mod(right, mP))
{
mPoints.push_back(Point(x, y));
}
}
}
}
class Key
{
public:
Key(void);
Key(const Generator& g, int x, const Point& Q);//生成元g,私钥x，公钥Q
virtual ~Key(void);
const Point& getPublicKey()const;
const int getPrivateKey()const;
const Generator& getGenerator()const;
protected:
Generator m_g;//生成元
Point m_Q;//公钥
int m_x;//私钥
};
void ECC::getAllOrders()
{
for (std::vector<Point>::const_iterator it = mPoints.begin(); it != mPoints.end(); it++)
{
mGenerators.push_back(Generator(*it, getOrder(*it)));
}
}
int ECC::getOrder(const Point& p)
{
int i = 1;
Point q = add(p, p);
while (q != p && q.isInfinity() == false)
{
i++;
q = add(p, q);
}
return ++i;
}
int ECC::ex_gcd(int a, int b, int& x, int& y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
int ans = this->ex_gcd(b, a % b, x, y);
int tmp = x;
x = y;
y = tmp - a / b * y;
return ans;
}
int ECC::getInverse(int a, int p)
{
int x, y;
int n = ex_gcd(a, p, x, y);
if (1 % n != 0) return -1;
x *= 1 / n;
p = abs(p);
int ans = x % p;
if (ans <= 0) ans += p;
return ans;
}
Point ECC::getMultiplePoint(int k, const Point& p)
{
Point q(p);
for (int i = 1; i < k; i++)
{
q = add(p, q);
}
return q;
}
Point ECC::add(const Point& p, const Point& q)
{
int lambda, m, n;
int x, y;
if (p.isInfinity())
{
return q;
}
if (q.isInfinity())
{
return p;
}
if (p == q)
{
m = mod(3 * p.X * p.X + mA, mP);
n = mod(2 * p.Y, mP);
}
else//P≠Q
{
m = mod(q.Y - p.Y, mP);
n = mod(q.X - p.X, mP);
}
if (n == 0)
{
return Point::Infinity();
}
lambda = mod(m * getInverse(n, mP), mP);
x = mod(lambda * lambda - p.X - q.X, mP);
y = mod(lambda * (p.X - x) - p.Y, mP);
return Point(x, y);
}
int ECC::mod(int a, int p)
{
if (a >= 0)
{
return a % p;
}
else
{
return ((a % p) + p) % p;
}
}
void ECC::encrypt(const std::vector<Point>& Pm, Key& key, std::vector<Cipher>& result, int k)
{
bool flag = k <= 1 || k > key.getGenerator().Order;
for (std::vector<Point>::const_iterator it = Pm.begin(); it != Pm.end(); it++)
{
if (flag)
{
k = rand() % (key.getGenerator().Order - 1) + 1;
}
Point C1 = getMultiplePoint(k, key.getGenerator().Value);
Point C2 = add(*it, getMultiplePoint(k, key.getPublicKey()));
result.push_back(Cipher(C1, C2));
}
}
void ECC::encodePlainText(const char* plainText, std::vector<Point>& result)
{
mDictionary = Dictionary(plainText);
while (*plainText != '\0')
{
int index = mDictionary.getIndex(*plainText);
result.push_back(mPoints[index]);
plainText++;
}
}
void ECC::decodePlainPoints(const std::vector<Point>& Pm, std::string& result)
{
std::stringstream ss;
for (std::vector<Point>::const_iterator it = Pm.begin(); it != Pm.end(); it++)
{
for (unsigned int i = 0; i < mPoints.size(); i++)
{
if (mPoints[i] == *it)
{
unsigned char ch = mDictionary.getChar(i);
ss << ch;
break;
}
}
}
ss >> result;
}
void ECC::decrypt(const std::vector<Cipher>& ciphers, int x, std::vector<Point>& result)
{
for (std::vector<Cipher>::const_iterator it = ciphers.begin(); it != ciphers.end(); it++)
{
Point C1R = Point(it->C1.X, -it->C1.Y);
Point Pm = add(it->C2, getMultiplePoint(x, C1R));
result.push_back(Pm);
}
}
bool ECC::isPrime(int n)
{
if (n < 2)
return false;
if (n == 2 || n == 3)
return true;
if (n % 6 != 1 && n % 6 != 5)
return false;
float n_sqrt = floor(sqrt((float)n));
for (int i = 5; i <= n_sqrt; i += 6)
{
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
//g是生成元,x是私钥
void ECC::genKey(Key& result, int gIndex, int x)
{
int n;
Generator G;
if (gIndex < 0 || isPrime(mGenerators[gIndex].Order) == false)
{
do
{
gIndex = rand() % mGenerators.size();
n = mGenerators[gIndex].Order;
} while (isPrime(n) == false);
}
else
{
n = mGenerators[gIndex].Order;
}
G = mGenerators[gIndex];
if (x >= n || x <= 1)
{
x = rand() % (n - 1) + 1;
}
Point Q = getMultiplePoint(x, G.Value);
result = Key(G, x, Q);
}
const std::vector<Generator> ECC::getGenerators()const
{
return mGenerators;
}
Key::Key(const Generator& g, int x, const Point& Q)
{
this->m_g = g;
this->m_Q = Q;
this->m_x = x;
}
Key::Key(void)
{
}
Key::~Key(void)
{
}
const Point& Key::getPublicKey()const
{
return m_Q;
}
const int Key::getPrivateKey()const
{
return m_x;
}
const Generator& Key::getGenerator()const
{
return m_g;
}
using namespace std;
template <typename T>
void print(const vector<T>& list)
{
for (unsigned int i = 0; i < list.size(); i++)
{
if (i % 4 == 0)
{
cout << endl;
}
cout << setw(3) << setfill(' ') << i << "、" << list[i] << "\t\t";
}
cout << endl;
cout << "-------------------------------------------------------" << endl;
}
int main()
{
int a, b, p, x, k;
Key key;
cout << "椭圆曲线方程为：" << "y^2 = x^3 + ax + b (mod p)" << endl;
//选取方程参数
input: cout << "请输入a的值（a是整数，a>0）：";
cin >> a;
cout << "请输入b的值（b是整数，b>0）：";
cin >> b;
cout << "请输入p的值（p是大素数，但目前用Int32表示）：";
cin >> p;
if (ECC::isPrime(p) == false)
{
cout << "p不是素数，请重新输入！" << endl;
goto input;
}
if ((4 * (a * a * a) + 27 * (b * b)) % p == 0)
{//当4a^3+27b^2≠0时，是一条非奇异椭圆曲线，此时可以在E(a,b)定义一个阿贝尔群
cout << "输入的参数有误，请重新输入！" << endl;
goto input;
}
//初始化椭圆曲线方程
ECC ecc(a, b, p);
//获取所有生成元以及对应的阶
vector<Generator> generators = ecc.getGenerators();
cout << "下面是生成元及对应的阶数：" << endl;
print(generators);
//选择基点G
cout << "请选择基点G（x,y）的序号：";//G=P
cin >> k;
//输入私钥
cout << "请输入私钥（x<" << generators[k].Order << "）：x = ";
cin >> x;
//产生公私钥对
ecc.genKey(key, k, x);
if (generators[k] != key.getGenerator())
{
cout << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
cout << "你选择的生成元为：G = " << generators[k] << endl;
cout << "该生成元的阶数为：ord(G) = " << generators[k].Order << ",不是素数" << endl;
cout << "生成元已自动变更为：G = " << key.getGenerator() << endl;
cout << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
}
cout << "生成的公钥为：Q = " << key.getPublicKey() << endl;
cout << "目前的私钥为：x = " << key.getPrivateKey() << endl;
//输入随机数k
cout << "请输入k的值来计算 kG,kQ+Pm，输入负数使用随机值（1<k<" << key.getGenerator().Order << "）：k = ";
cin >> k;
vector<Point> encodedPoints;
vector<Cipher> cipheredPoints;
//将明文m编码为椭圆曲线上的点
ecc.encodePlainText("Hello，我是明文", encodedPoints);
cout << "编码后的明文点集为：Pme = " << endl;
print(encodedPoints);
//加密
ecc.encrypt(encodedPoints, key, cipheredPoints, k);
cout << "加密后的密文点集为：Pc = " << endl;
print(cipheredPoints);
vector<Point> decryptedPoints;
string decodedText;
//解密
ecc.decrypt(cipheredPoints, key.getPrivateKey(), decryptedPoints);
cout << "解密后的明文点集为：Pm = " << endl;
print(decryptedPoints);
//解码明文点集，得到明文字符串
ecc.decodePlainPoints(decryptedPoints, decodedText);
cout << "解码后的字符串明文为：" << endl;
cout << decodedText << endl;
system("Pause");
return 0;
}

复制代码

许鹏程 · 发表于 2022-6-2 14:39:49

RSA签名

RSA 数字签名算法(RSASA)的本质，仍然是 RSA 加密/解密算法.
RSA签名分为两步:
1)将待签名的 M 进行 Hash，从而得到 H
2)将 H 进行 RSA 私钥加密.

RSA签名的过程如下：

　　（1）A⽣成⼀对密钥（公钥和私钥），私钥不公开，A⾃⼰保留。公钥为公开的，任何⼈可以获取。

　　（2）A⽤⾃⼰的私钥对消息加签，形成签名，并将加签的消息和消息本⾝⼀起传递给B。

　　（3）B收到消息后，在获取A的公钥进⾏验签，如果验签出来的内容与消息本⾝⼀致，证明消息是A回复的。

许鹏程 · 发表于 2022-6-2 14:45:47

import javax.crypto.Cipher;
import netscape.javascript.JSException;
import java.io.ByteArrayOutputStream;
import java.security.*;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import java.util.Map;
public class RsaUtils {
public static final String Encryption = "RSA";
public static final String Privatesignature = "SHA256withRSA";
private static final int MAX_ENCRYPT_BLOCK = 245 ;
private static final int MAX_DECRYPT_BLOCK = 256;
public static void main(String[] args) throws Exception{
String publicKey = "rsa_public_key.pem 公钥内容";
String privateKey = "pkcs8_rsa_private_key.pem中密钥内容";
try {
System.out.println("私钥:" + privateKey);
System.out.println("公钥:" + publicKey);
String data = "{"user_name":"张三","password":"666666"}";
String encryptData = encrypt(data, getPublicKey(publicKey));
System.out.println("加密后内容:" + encryptData);
String decryptData = decrypt(encryptData, getPrivateKey(privateKey));
System.out.println("解密后内容:" + decryptData);
String sign = sign(data, getPrivateKey(privateKey));
System.out.println("签名后结果:" + decryptData);
boolean result = verify(data, getPublicKey(publicKey), sign);
System.out.print("验签结果:" + result);
} catch (Exception e) {
e.printStackTrace();
System.out.print("加解密异常");
}
}
public static String dnRSA(String tslPublicKey,String privateKey,String pamStr,String sign) throws Exception {
if(verify(pamStr, getPublicKey(tslPublicKey), sign)){
String result = decrypt(pamStr, getPrivateKey(privateKey));
return result;
}else{
return null;
}
}
public static KeyPair getKeyPair() throws Exception {
KeyPairGenerator generator = KeyPairGenerator.getInstance(Encryption);
generator.initialize(1024);
return generator.generateKeyPair();
}
public static PrivateKey getPrivateKey(String privateKey) throws Exception {
KeyFactory keyFactory = KeyFactory.getInstance(Encryption);
byte[] decodedKey = Base64.decodeBase64(privateKey.getBytes());
PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(decodedKey);
return keyFactory.generatePrivate(keySpec);
}
public static JSONObject enRSAjson(String publicKey,String thirdPrivateKey,String pamStr) throws Exception {
JSONObject json = new JSONObject();
String encryptData = encrypt(pamStr, getPublicKey(publicKey));
String sign = sign(encryptData, getPrivateKey(thirdPrivateKey));
json.put("payload",encryptData);
json.put("sign",sign);
return json;
}
public static PublicKey getPublicKey(String publicKey) throws Exception {
KeyFactory keyFactory = KeyFactory.getInstance(Encryption);
byte[] decodedKey = Base64.decodeBase64(publicKey.getBytes());
X509EncodedKeySpec keySpec = new X509EncodedKeySpec(decodedKey);
return keyFactory.generatePublic(keySpec);
}
public static String encrypt(String data, PublicKey publicKey) throws Exception {
Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");
cipher.init(Cipher.ENCRYPT_MODE, publicKey);
int inputLen = data.getBytes().length;
ByteArrayOutputStream out = new ByteArrayOutputStream();
int offset = 0;
byte[] cache;
int i = 0;
while (inputLen - offset > 0) {
if (inputLen - offset > MAX_ENCRYPT_BLOCK) {
cache = cipher.doFinal(data.getBytes(), offset, MAX_ENCRYPT_BLOCK);
} else {
cache = cipher.doFinal(data.getBytes(), offset, inputLen - offset);
}
out.write(cache, 0, cache.length);
i++;
offset = i * MAX_ENCRYPT_BLOCK;
}
byte[] encryptedData = out.toByteArray();
out.close();
return new String(Base64.encodeBase64String(encryptedData));
}
public static String decrypt(String data, PrivateKey privateKey) throws Exception {
Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");
cipher.init(Cipher.DECRYPT_MODE, privateKey);
byte[] dataBytes = Base64.decodeBase64(data);
int inputLen = dataBytes.length;
ByteArrayOutputStream out = new ByteArrayOutputStream();
int offset = 0;
byte[] cache;
int i = 0;
while (inputLen - offset > 0) {
if (inputLen - offset > MAX_DECRYPT_BLOCK) {
cache = cipher.doFinal(dataBytes, offset, MAX_DECRYPT_BLOCK);
} else {
cache = cipher.doFinal(dataBytes, offset, inputLen - offset);
}
out.write(cache, 0, cache.length);
i++;
offset = i * MAX_DECRYPT_BLOCK;
}
byte[] decryptedData = out.toByteArray();
out.close();
return new String(decryptedData, "UTF-8");
}
public static String sign(String data, PrivateKey privateKey) throws Exception {
byte[] keyBytes = privateKey.getEncoded();
PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(keyBytes);
KeyFactory keyFactory = KeyFactory.getInstance(Encryption);
PrivateKey key = keyFactory.generatePrivate(keySpec);
Signature signature = Signature.getInstance(Privatesignature);
signature.initSign(key);
signature.update(data.getBytes());
return new String(Base64.decodeBase64(signature.sign()));
}
public static boolean verify(String srcData, PublicKey publicKey, String sign) throws Exception {
byte[] keyBytes = publicKey.getEncoded();
X509EncodedKeySpec keySpec = new X509EncodedKeySpec(keyBytes);
KeyFactory keyFactory = KeyFactory.getInstance(Encryption);
PublicKey key = keyFactory.generatePublic(keySpec);
Signature signature = Signature.getInstance(Privatesignature);
signature.initVerify(key);
signature.update(srcData.getBytes());
return signature.verify(Base64.decodeBase64(sign.getBytes()));
}
}

复制代码

		自动登录	找回密码
密码			立即注册

信息计算2019级1班27号许鹏程

浏览过的版块