信息安全——ELGamal数字签名方案的实现_lishuhuakai的博客-程序员宅基地

技术标签: Info Security  信息安全  数字签名l  ELGama  

ELGamal数字签名方案的实现

1. 问题描述

为简化问题,我们取p=19,g=2,私钥x=9,则公钥y=29 mod 19=18。消息m的ELGamal签名为(r,s),其中r=gk mod p,s=(h(m)-xr)k-1 mod (p-1)

2.基本要求

   考虑p取大素数的情况。

3. 实现提示

①     模n求逆a-1modn运算。

②     模n的大数幂乘运算

       由于大素数的本原元要求得很费事,所以签名所需要的数值我已经事先给出,当然这些数值比较小,有兴趣的同学可以自行将数值变大.

       ELGamal离不开大数包的支持!

BigInteger.h

#pragma once
#include <cstring>
#include <string>
#include <algorithm>
#include <assert.h>
#include <ctime>
#include <iostream>

using namespace std;
const int maxLength = 512;
const int primeLength = 30;
const int primesBelow2000[303] = {
	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
	101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
	211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
	307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
	401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
	503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
	601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
	701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
	809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
	907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,
	1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,
	1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193,
	1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297,
	1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
	1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499,
	1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597,
	1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699,
	1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
	1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889,
	1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999 };

class BigInteger
{
	typedef unsigned char byte;
public:
	BigInteger(void);
	BigInteger(__int64 value);
	BigInteger(unsigned __int64 value);
	BigInteger(const BigInteger &bi);
	BigInteger(string value, int radix);
	BigInteger(byte inData[], int inLen);
	BigInteger(unsigned int inData[], int inLen);

    BigInteger operator -();
	BigInteger operator =(const BigInteger &bi2);

	BigInteger operator +(BigInteger &bi2);
	BigInteger operator -(BigInteger bi2);

	BigInteger operator /(BigInteger bi2);
	BigInteger operator *(BigInteger bi2);
	void singleByteDivide(BigInteger &bi1, BigInteger &bi2, BigInteger &outQuotient, BigInteger &outRemainder);
	void multiByteDivide(BigInteger &bi1, BigInteger &bi2, BigInteger &outQuotient, BigInteger &outRemainder);

	BigInteger operator %(BigInteger bi2);

	BigInteger operator +=(BigInteger bi2);
	BigInteger operator -=(BigInteger bi2);

    int bitCount();
	BigInteger modPow(BigInteger exp, BigInteger n);
	

	friend ostream& operator<<(ostream& output, BigInteger &bi1);
	friend BigInteger GetPrime();
	friend bool Miller_Robin(BigInteger &bi1);
	friend BigInteger MultipInverse(BigInteger &bi1, BigInteger &n);
	friend BigInteger extended_euclidean(BigInteger n, BigInteger m, BigInteger &x, BigInteger &y); 
	friend BigInteger MultipInverse(BigInteger &bi1, BigInteger &n);   //求乘法逆
	friend BigInteger Gcd(BigInteger &bi1, BigInteger &bi2);   //求最大公约数
	friend bool IsPrime (BigInteger &obj);

	BigInteger BarrettReduction(BigInteger x, BigInteger n, BigInteger constant);

	bool operator >=(BigInteger bi2)
	{
		return ((*this) == bi2 || (*this) > bi2);
	}

	bool operator >(BigInteger bi2);
	bool operator ==(BigInteger bi2);
	bool operator !=(BigInteger bi2);
	
	
	int shiftRight(unsigned int buffer[], int bufLen, int shiftVal);
	BigInteger operator <<(int shiftVal);
	int shiftLeft(unsigned int buffer[], int bufLen, int shiftVal);
	bool operator <(BigInteger bi2);

	string DecToHex(unsigned int value, string format);
	string ToHexString();

public:
	~BigInteger(void);	

public:
	int dataLength;
		// number of actual chars used
	unsigned int *data;
};

BigInteger.cpp

#include "BigInteger.h"

BigInteger::BigInteger(void)   //默认的构造函数
: dataLength(0), data(0)
{
	data = new unsigned int[maxLength];
	memset(data, 0, maxLength * sizeof(unsigned int));
	dataLength = 1;
}

BigInteger::BigInteger(__int64 value)   //用一个64位的值来初始化大数
{
	data = new unsigned int[maxLength];
	memset(data, 0, maxLength * sizeof(unsigned int));   //先清零
	__int64 tempVal = value;

	dataLength = 0;
	while (value != 0 && dataLength < maxLength)
	{
		data[dataLength] = (unsigned int)(value & 0xFFFFFFFF);   //取低位
		value = value >> 32;   //进位
		dataLength++;
	}

	if (tempVal > 0)         // overflow check for +ve value
	{
		if (value != 0 || (data[maxLength - 1] & 0x80000000) != 0)
			assert(false);
	}
	else if (tempVal < 0)    // underflow check for -ve value
	{
		if (value != -1 || (data[dataLength - 1] & 0x80000000) == 0)
			assert(false);
	}

	if (dataLength == 0)
		dataLength = 1;
}

BigInteger::BigInteger(unsigned __int64 value)   //用一个无符号的64位整数来初始化大数
{
	data = new unsigned int[maxLength];
	memset(data, 0, maxLength * sizeof(unsigned int));

	dataLength = 0;
	while (value != 0 && dataLength < maxLength)
	{
		data[dataLength] = (unsigned int)(value & 0xFFFFFFFF);
		value >>= 32;
		dataLength++;
	}

	if (value != 0 || (data[maxLength - 1] & 0x80000000) != 0)
		assert(false);

	if (dataLength == 0)   //防止输入的value=0
		dataLength = 1;
}

BigInteger::BigInteger(const BigInteger &bi)   //用大数初始化大数
{
	data = new unsigned int[maxLength];
	dataLength = bi.dataLength;

	for (int i = 0; i < maxLength; i++)   //考虑到有负数的情况,所以每一位都要复制
		data[i] = bi.data[i];
}

BigInteger::~BigInteger(void)
{
	if (data != NULL)
	{
		delete []data;
	}
}

BigInteger::BigInteger(string value, int radix)   //输入转换函数,将字符串转换成对应进制的大数
{   //一般不处理负数
	BigInteger multiplier((__int64)1);
	BigInteger result;
	transform(value.begin(), value.end(), value.begin(), toupper);   //将小写字母转换成为大写

	int limit = 0;

	if (value[0] == '-')   
		limit = 1;

	for (int i = value.size() - 1; i >= limit; i--)
	{
		int posVal = (int)value[i];

		if (posVal >= '0' && posVal <= '9')  //将字符转换成数字
			posVal -= '0';
		else if (posVal >= 'A' && posVal <= 'Z')
			posVal = (posVal - 'A') + 10;
		else
			posVal = 9999999;       // arbitrary large 输入别的字符


		if (posVal >= radix)   //不能大于特定的进制,否则终止
		{
			assert(false);
		}
		else
		{
			result = result + (multiplier * BigInteger((__int64)posVal));

			if ((i - 1) >= limit)   //没有到达尾部
				multiplier = multiplier * BigInteger((__int64)radix);
		}
	}
	
	if (value[0] == '-')   //符号最后再处理
	   result = -result;

	if (value[0] == '-')     //输入为负数,但得到的结果为正数,可能溢出了
	{
		if ((result.data[maxLength - 1] & 0x80000000) == 0)   
			assert(false);
	}
	else    //或者说,输入为正数,得到的结果为负数,也可能溢出了
	{
		if ((result.data[maxLength - 1] & 0x80000000) != 0)  
			assert(false);
	}


	data = new unsigned int[maxLength];
	//memset(data, 0, maxLength * sizeof(unsigned int));
	for (int i = 0; i < maxLength; i++)
		data[i] = result.data[i];

	dataLength = result.dataLength;
}

BigInteger::BigInteger(byte inData[], int inLen)   //用一个char类型的数组来初始化大数
{
	dataLength = inLen >> 2;   //一个unsigned int占32位,而一个unsigned char只占8位
	//因此dataLength应该是至少是inLen/4,不一定整除

	int leftOver = inLen & 0x3;  
	//取最低两位的数值,为什么要这样干呢?实际上是为了探测len是不是4的倍数,好确定dataLength的长度
	if (leftOver != 0)    //不能整除的话,dataLength要加1
		dataLength++;


	if (dataLength > maxLength)
		assert(false);

	data = new unsigned int[maxLength];
	memset(data, 0, maxLength * sizeof(unsigned int));

	for (int i = inLen - 1, j = 0; i >= 3; i -= 4, j++)   
	{
		data[j] = (unsigned int)((inData[i - 3] << 24) + (inData[i - 2] << 16) + (inData[i - 1] << 8) + inData[i]);
//我们知道:一个unsigned int占32位,而一个unsigned char只占8位,因此四个unsigned char才能组成一个unsigned int
//因此取inData[i - 3]为前32-25位,inData[i - 2]为前24-17~~~
//i % 4 = 0 or 1 or 2 or 3 余0表示恰好表示完
	}

	if (leftOver == 1)
		data[dataLength - 1] = (unsigned int)inData[0];
	else if (leftOver == 2)
		data[dataLength - 1] = (unsigned int)((inData[0] << 8) + inData[1]);
	else if (leftOver == 3)
		data[dataLength - 1] = (unsigned int)((inData[0] << 16) + (inData[1] << 8) + inData[2]);


	while (dataLength > 1 && data[dataLength - 1] == 0)
		dataLength--;
}

BigInteger::BigInteger(unsigned int inData[], int inLen)   //用一个unsigned int型数组初始化大数
{
	dataLength = inLen;

	if (dataLength > maxLength)
		assert(false);

	data = new unsigned int[maxLength];
	memset(data, 0, maxLength * sizeof(maxLength));

	for (int i = dataLength - 1, j = 0; i >= 0; i--, j++)
		data[j] = inData[i];

	while (dataLength > 1 && data[dataLength - 1] == 0)
		dataLength--;
}

BigInteger BigInteger::operator *(BigInteger bi2)   //乘法的重载
{
	BigInteger bi1(*this);
	int lastPos = maxLength - 1;
	bool bi1Neg = false, bi2Neg = false;

	//首先对两个乘数取绝对值
	try
	{
		if ((this->data[lastPos] & 0x80000000) != 0)     //bi1为负数
		{
			bi1Neg = true; 
			bi1 = -bi1;
		}
		if ((bi2.data[lastPos] & 0x80000000) != 0)     //bi2为负数
		{
			bi2Neg = true; bi2 = -bi2;
		}
	}
	catch (...) { }

	BigInteger result;

	//绝对值相乘
	try
	{
		for (int i = 0; i < bi1.dataLength; i++)
		{
			if (bi1.data[i] == 0) continue;

			unsigned __int64 mcarry = 0;
			for (int j = 0, k = i; j < bi2.dataLength; j++, k++)
			{
				// k = i + j
				unsigned __int64 val = ((unsigned __int64)bi1.data[i] * (unsigned __int64)bi2.data[j]) + (unsigned __int64)result.data[k] + mcarry;
				result.data[k] = (unsigned __int64)(val & 0xFFFFFFFF);   //取低位
				mcarry = (val >> 32);   //进位
			}

			if (mcarry != 0)
			result.data[i + bi2.dataLength] = (unsigned int)mcarry;
		}
	}
	catch (...)
	{
		assert(false);
	}


	result.dataLength = bi1.dataLength + bi2.dataLength;
	if (result.dataLength > maxLength)
		result.dataLength = maxLength;

	while (result.dataLength > 1 && result.data[result.dataLength - 1] == 0)
		result.dataLength--;

	// overflow check (result is -ve)溢出检查
	if ((result.data[lastPos] & 0x80000000) != 0)  //结果为负数
	{
		if (bi1Neg != bi2Neg && result.data[lastPos] == 0x80000000)    //两乘数符号不同
		{
			// handle the special case where multiplication produces
			// a max negative number in 2's complement.

			if (result.dataLength == 1)
				return result;
			else
			{
				bool isMaxNeg = true;
				for (int i = 0; i < result.dataLength - 1 && isMaxNeg; i++)
				{
					if (result.data[i] != 0)
						isMaxNeg = false;
				}

				if (isMaxNeg)
					return result;
			}
		}

		assert(false);
	}

	//两乘数符号不同,结果为负数
	if (bi1Neg != bi2Neg)
		return -result;

	return result;
}

BigInteger BigInteger::operator =(const BigInteger &bi2)
{
	if (&bi2 == this)
	{
		return *this;
	}
	if (data != NULL)
	{
		delete []data;
		data = NULL;
	}
	data = new unsigned int[maxLength];
	memset(data, 0, maxLength * sizeof(unsigned int));

	dataLength = bi2.dataLength;

	for (int i = 0; i < maxLength; i++)
		data[i] = bi2.data[i];
	return *this;
}

BigInteger BigInteger::operator +(BigInteger &bi2)
{
	int lastPos = maxLength - 1;
	bool bi1Neg = false, bi2Neg = false;
	BigInteger bi1(*this);
	BigInteger result;

    if ((this->data[lastPos] & 0x80000000) != 0)     //bi1为负数
	      bi1Neg = true; 
	if ((bi2.data[lastPos] & 0x80000000) != 0)     //bi2为负数
			bi2Neg = true; 

	if(bi1Neg == false && bi2Neg == false)   //bi1与bi2都是正数
	{
		result.dataLength = (this->dataLength > bi2.dataLength) ? this->dataLength : bi2.dataLength;

		__int64 carry = 0;
		for (int i = 0; i < result.dataLength; i++)   //从低位开始,逐位相加
		{
			__int64 sum = (__int64)this->data[i] + (__int64)bi2.data[i] + carry;
			carry = sum >> 32;   //进位
			result.data[i] = (unsigned int)(sum & 0xFFFFFFFF);  //取低位结果
		}

		if (carry != 0 && result.dataLength < maxLength)
		{
			result.data[result.dataLength] = (unsigned int)(carry);
			result.dataLength++;
		}

		while (result.dataLength > 1 && result.data[result.dataLength - 1] == 0)
			result.dataLength--;


		//溢出检查
		if ((this->data[lastPos] & 0x80000000) == (bi2.data[lastPos] & 0x80000000) &&
			(result.data[lastPos] & 0x80000000) != (this->data[lastPos] & 0x80000000))
		{
			assert(false);
		}
		return result;
	}
	//关键在于,负数全部要转化成为正数来做
	if(bi1Neg == false && bi2Neg == true)   //bi1正,bi2负
	{
		BigInteger bi3 = -bi2;
		if(bi1 > bi3)
		{
		 result = bi1 - bi3; 
		 return result;
		}
		else
		{
		 result = -(bi3 - bi1);
		 return result;
		}
	}

	if(bi1Neg == true && bi2Neg == false)  //bi1负,bi2正
	{
        BigInteger bi3 = -bi1;
		if(bi3 > bi2)
		{
		 result = -(bi3 - bi2);
		 return result;
		}
		else
		{
		 result = bi2 - bi3;
		 return result;
		}
	}

    if(bi1Neg == true && bi2Neg == true)  //bi1负,bi2负
	{
		result = - ((-bi1) + (-bi2));
		return result;
	}
}

BigInteger BigInteger::operator -()
{
	//逐位取反并+1
	if (this->dataLength == 1 && this->data[0] == 0)
		return *this;

	BigInteger result(*this);

	for (int i = 0; i < maxLength; i++)
		result.data[i] = (unsigned int)(~(this->data[i]));   //取反

	__int64 val, carry = 1;
	int index = 0;

	while (carry != 0 && index < maxLength)  //+1;
	{
		val = (__int64)(result.data[index]);
		val++;   //由于值加了1个1,往前面的进位最多也只是1个1,因此val++就完了

		result.data[index] = (unsigned int)(val & 0xFFFFFFFF);   //取低位部分
		carry = val >> 32;   //进位

		index++;
	}

	if ((this->data[maxLength - 1] & 0x80000000) == (result.data[maxLength - 1] & 0x80000000))
		result.dataLength = maxLength;

	while (result.dataLength > 1 && result.data[result.dataLength - 1] == 0)
		result.dataLength--;
	
	return result;
}

BigInteger BigInteger::modPow(BigInteger exp, BigInteger n)   //求this^exp mod n
{
	if ((exp.data[maxLength - 1] & 0x80000000) != 0)   //指数是负数
	return BigInteger((__int64)0);

	BigInteger resultNum((__int64)1);
	BigInteger tempNum;
	bool thisNegative = false;

	if ((this->data[maxLength - 1] & 0x80000000) != 0)   //底数是负数
	{
		tempNum = -(*this) % n;
		thisNegative = true;
	}
	else
		tempNum = (*this) % n;  //保证(tempNum * tempNum) < b^(2k)

	if ((n.data[maxLength - 1] & 0x80000000) != 0)   //n为负
		n = -n;

	//计算 constant = b^(2k) / m
	//constant主要用于后面的Baeert Reduction算法
	BigInteger constant;

	int i = n.dataLength << 1;
	constant.data[i] = 0x00000001;
	constant.dataLength = i + 1;

	constant = constant / n;
	int totalBits = exp.bitCount();
	int count = 0;

	//平方乘法算法
	for (int pos = 0; pos < exp.dataLength; pos++)
	{
		unsigned int mask = 0x01;

		for (int index = 0; index < 32; index++)
		{
			if ((exp.data[pos] & mask) != 0)  //某一个bit不为0
			resultNum = BarrettReduction(resultNum * tempNum, n, constant);
			//resultNum = resultNum * tempNum mod n

			mask <<= 1; //不断左移

			tempNum = BarrettReduction(tempNum * tempNum, n, constant);
			//tempNum = tempNum * tempNum mod n

			if (tempNum.dataLength == 1 && tempNum.data[0] == 1)
			{
				if (thisNegative && (exp.data[0] & 0x1) != 0)    //指数为奇数
					return -resultNum;
				return resultNum;
			}
			count++;
			if (count == totalBits)
				break;
		}
	}

	if (thisNegative && (exp.data[0] & 0x1) != 0)    //底数为负数,指数为奇数
		return -resultNum;

	return resultNum;
}

int BigInteger::bitCount()   //计算字节数
{
	while (dataLength > 1 && data[dataLength - 1] == 0)
		dataLength--;

	unsigned int value = data[dataLength - 1];
	unsigned int mask = 0x80000000;
	int bits = 32;

	while (bits > 0 && (value & mask) == 0)   //计算最高位的bit
	{
		bits--;
		mask >>= 1;
	}
	bits += ((dataLength - 1) << 5);   //余下的位都有32bit
	//左移5位,相当于乘以32,即2^5
	return bits;
}

BigInteger BigInteger::BarrettReduction(BigInteger x, BigInteger n, BigInteger constant)
{

//算法,Baeert Reduction算法,在计算大规模的除法运算时很有优势
//原理如下
//Z mod N=Z-[Z/N]*N=Z-{[Z/b^(n-1)]*[b^2n/N]/b^(n+1)}*N=Z-q*N
//q=[Z/b^(n-1)]*[b^2n/N]/b^(n+1)
//其中,[]表示取整运算,A^B表示A的B次幂

	int k = n.dataLength,
		kPlusOne = k + 1,
		kMinusOne = k - 1;

	BigInteger q1;

	// q1 = x / b^(k-1)
	for (int i = kMinusOne, j = 0; i < x.dataLength; i++, j++)
		q1.data[j] = x.data[i];
	q1.dataLength = x.dataLength - kMinusOne;
	if (q1.dataLength <= 0)
		q1.dataLength = 1;


	BigInteger q2 = q1 * constant;
	BigInteger q3;

	// q3 = q2 / b^(k+1)
	for (int i = kPlusOne, j = 0; i < q2.dataLength; i++, j++)
		q3.data[j] = q2.data[i];
	q3.dataLength = q2.dataLength - kPlusOne;
	if (q3.dataLength <= 0)
		q3.dataLength = 1;


	// r1 = x mod b^(k+1)
	// i.e. keep the lowest (k+1) words
	BigInteger r1;
	int lengthToCopy = (x.dataLength > kPlusOne) ? kPlusOne : x.dataLength;
	for (int i = 0; i < lengthToCopy; i++)
		r1.data[i] = x.data[i];
	r1.dataLength = lengthToCopy;


	// r2 = (q3 * n) mod b^(k+1)
	// partial multiplication of q3 and n

	BigInteger r2;
	for (int i = 0; i < q3.dataLength; i++)
	{
		if (q3.data[i] == 0) continue;

		unsigned __int64 mcarry = 0;
		int t = i;
		for (int j = 0; j < n.dataLength && t < kPlusOne; j++, t++)
		{
			// t = i + j
			unsigned __int64 val = ((unsigned __int64)q3.data[i] * (unsigned __int64)n.data[j]) +
				(unsigned __int64)r2.data[t] + mcarry;

			r2.data[t] = (unsigned int)(val & 0xFFFFFFFF);
			mcarry = (val >> 32);
		}

		if (t < kPlusOne)
			r2.data[t] = (unsigned int)mcarry;
	}
	r2.dataLength = kPlusOne;
	while (r2.dataLength > 1 && r2.data[r2.dataLength - 1] == 0)
		r2.dataLength--;

	r1 -= r2;
	if ((r1.data[maxLength - 1] & 0x80000000) != 0)        // negative
	{
		BigInteger val;
		val.data[kPlusOne] = 0x00000001;
		val.dataLength = kPlusOne + 1;
		r1 += val;
	}

	while (r1 >= n)
		r1 -= n;

	return r1;
}

bool BigInteger::operator >(BigInteger bi2)
{
	int pos = maxLength - 1;
	BigInteger bi1(*this);

	// bi1 is negative, bi2 is positive
	if ((bi1.data[pos] & 0x80000000) != 0 && (bi2.data[pos] & 0x80000000) == 0)
		return false;

	// bi1 is positive, bi2 is negative
	else if ((bi1.data[pos] & 0x80000000) == 0 && (bi2.data[pos] & 0x80000000) != 0)
		return true;

	// same sign
	int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
	for (pos = len - 1; pos >= 0 && bi1.data[pos] == bi2.data[pos]; pos--) ;

	if (pos >= 0)
	{
		if (bi1.data[pos] > bi2.data[pos])
			return true;
		return false;
	}
	return false;
}

bool BigInteger::operator ==(BigInteger bi2)
{
	if (this->dataLength != bi2.dataLength)
		return false;

	for (int i = 0; i < this->dataLength; i++)
	{
		if (this->data[i] != bi2.data[i])
			return false;
	}
	return true;
}

bool BigInteger::operator !=(BigInteger bi2)
{
	if(this->dataLength != bi2.dataLength)
		return true;
	for(int i = 0; i < this->dataLength; i++)
	{
		if(this->data[i] != bi2.data[i])
			return true;
	}
	return false;
}

BigInteger BigInteger::operator %(BigInteger bi2)
{
	BigInteger bi1(*this);
	BigInteger quotient;
	BigInteger remainder(bi1);

	int lastPos = maxLength - 1;
	bool dividendNeg = false;

	if ((bi1.data[lastPos] & 0x80000000) != 0)     // bi1 negative
	{
		bi1 = -bi1;
		dividendNeg = true;
	}
	if ((bi2.data[lastPos] & 0x80000000) != 0)     // bi2 negative
		bi2 = -bi2;

	if (bi1 < bi2)
	{
		return remainder;
	}

	else
	{
		if (bi2.dataLength == 1)
			singleByteDivide(bi1, bi2, quotient, remainder);   //bi2只占一个位置时,用singleByteDivide更快
		else
			multiByteDivide(bi1, bi2, quotient, remainder);   //bi2占多个位置时,用multiByteDivide更快

		if (dividendNeg)
			return -remainder;

		return remainder;
	}
}

void BigInteger::singleByteDivide(BigInteger &bi1, BigInteger &bi2,
					  BigInteger &outQuotient, BigInteger &outRemainder)
{//outQuotient商,outRemainder余数

	unsigned int result[maxLength];   //用来存储结果
	memset(result, 0, sizeof(unsigned int) * maxLength);
	int resultPos = 0;

	for (int i = 0; i < maxLength; i++)   //将bi1复制至outRemainder
		outRemainder.data[i] = bi1.data[i];
	outRemainder.dataLength = bi1.dataLength;

	while (outRemainder.dataLength > 1 && outRemainder.data[outRemainder.dataLength - 1] == 0)
		outRemainder.dataLength--;

	unsigned __int64 divisor = (unsigned __int64)bi2.data[0];
	int pos = outRemainder.dataLength - 1;
	unsigned __int64 dividend = (unsigned __int64)outRemainder.data[pos];   //取最高位的数值


	if (dividend >= divisor)   //被除数>除数
	{
		unsigned __int64 quotient = dividend / divisor;
		result[resultPos++] = (unsigned __int64)quotient;   //结果

		outRemainder.data[pos] = (unsigned __int64)(dividend % divisor);   //余数
	}
	pos--;

	while (pos >= 0)
	{
		dividend = ((unsigned __int64)outRemainder.data[pos + 1] << 32) + (unsigned __int64)outRemainder.data[pos];   //前一位的余数和这一位的值相加
		unsigned __int64 quotient = dividend / divisor;   //得到结果
		result[resultPos++] = (unsigned int)quotient;   //结果取低位

		outRemainder.data[pos + 1] = 0;   //前一位的余数清零
		outRemainder.data[pos--] = (unsigned int)(dividend % divisor);   //得到这一位的余数
	}

	outQuotient.dataLength = resultPos;   //商的长度是resultPos的长度
	int j = 0;
	for (int i = outQuotient.dataLength - 1; i >= 0; i--, j++)  //将商反转过来 
		outQuotient.data[j] = result[i];
	for (; j < maxLength; j++)   //商的其余位都要置0
		outQuotient.data[j] = 0;

	while (outQuotient.dataLength > 1 && outQuotient.data[outQuotient.dataLength - 1] == 0)
		outQuotient.dataLength--;

	if (outQuotient.dataLength == 0)
		outQuotient.dataLength = 1;

	while (outRemainder.dataLength > 1 && outRemainder.data[outRemainder.dataLength - 1] == 0)
		outRemainder.dataLength--;
}

void BigInteger::multiByteDivide(BigInteger &bi1, BigInteger &bi2,
					 BigInteger &outQuotient, BigInteger &outRemainder)
{
	unsigned int result[maxLength];
	memset(result, 0, sizeof(unsigned int) * maxLength);   //结果置零 

	int remainderLen = bi1.dataLength + 1;   //余数长度
	unsigned int *remainder = new unsigned int[remainderLen];
	memset(remainder, 0, sizeof(unsigned int) * remainderLen);   //余数置零

	unsigned int mask = 0x80000000;
	unsigned int val = bi2.data[bi2.dataLength - 1];
	int shift = 0, resultPos = 0;

	while (mask != 0 && (val & mask) == 0)
	{
		shift++; mask >>= 1;
	}   
	//最高位从高到低找出shift个0位
	for (int i = 0; i < bi1.dataLength; i++)
		remainder[i] = bi1.data[i];   //将bi1复制到remainder之中
	this->shiftLeft(remainder, remainderLen, shift);   //remainder左移shift位
	bi2 = bi2 << shift;   //向左移shift位,将空位填满
	//由于两个数都扩大了相同的倍数,所以结果不变

	int j = remainderLen - bi2.dataLength;   //j表示两个数长度的差值,也是要计算的次数
	int pos = remainderLen - 1;   //pos指示余数的最高位的位置,现在pos=bi1.dataLength

	//以下的步骤并没有别的意思,主要是用来试商
	unsigned __int64 firstDivisorByte = bi2.data[bi2.dataLength - 1];   //第一个除数
	unsigned __int64 secondDivisorByte = bi2.data[bi2.dataLength - 2];  //第二个除数 

	int divisorLen = bi2.dataLength + 1;   //除数的长度
	unsigned int *dividendPart = new unsigned int[divisorLen];   //起名为除数的部分
	memset(dividendPart, 0, sizeof(unsigned int) * divisorLen);

	while (j > 0)
	{
		unsigned __int64 dividend = ((unsigned __int64)remainder[pos] << 32) + (unsigned __int64)remainder[pos - 1];   //取余数的高两位

		unsigned __int64 q_hat = dividend / firstDivisorByte;   //得到一个商
		unsigned __int64 r_hat = dividend % firstDivisorByte;   //以及一个余数

		bool done = false;   //表示没有做完
		while (!done)
		{
			done = true;

			if (q_hat == 0x100000000 || (q_hat * secondDivisorByte) > ((r_hat << 32) + remainder[pos - 2]))   //这里主要用来调整商的大小 
			//(q_hat * secondDivisorByte) > ((r_hat << 32) + remainder[pos - 2]))是害怕上的商过大,减之后变为负数
	        //商q_hat也不能超过32bit
			{
				q_hat--;   //否则的话,就商小一点,余数大一点
				r_hat += firstDivisorByte;

				if (r_hat < 0x100000000)   //如果余数小于32bit,就继续循环
					done = false;
			}
		}

		for (int h = 0; h < divisorLen; h++)   //取被除数的高位部分,高位部分长度与除数长度一致
			dividendPart[h] = remainder[pos - h];

		BigInteger kk(dividendPart, divisorLen);
		BigInteger ss = bi2 * BigInteger((__int64)q_hat);

		while (ss > kk)   //调节商的大小
		{
			q_hat--;
			ss -= bi2;
		}
		BigInteger yy = kk - ss;   //得到余数

		for (int h = 0; h < divisorLen; h++)  //将yy高位和remainder低位拼接起来,得到余数
			remainder[pos - h] = yy.data[bi2.dataLength - h];   //取得真正的余数

		result[resultPos++] = (unsigned int)q_hat;

		pos--;
		j--;
	}

	outQuotient.dataLength = resultPos;
	int y = 0;
	for (int x = outQuotient.dataLength - 1; x >= 0; x--, y++)   //将商反转过来
		outQuotient.data[y] = result[x];
	for (; y < maxLength; y++)   //商的其余位都要置0
		outQuotient.data[y] = 0;

	while (outQuotient.dataLength > 1 && outQuotient.data[outQuotient.dataLength - 1] == 0)
		outQuotient.dataLength--;

	if (outQuotient.dataLength == 0)
		outQuotient.dataLength = 1;

	outRemainder.dataLength = this->shiftRight(remainder, remainderLen, shift);

	for (y = 0; y < outRemainder.dataLength; y++)
		outRemainder.data[y] = remainder[y];
	for (; y < maxLength; y++)
		outRemainder.data[y] = 0;

	delete []remainder;
	delete []dividendPart;
}

int BigInteger::shiftRight(unsigned int buffer[], int bufferLen,int shiftVal)   //右移操作
{//自己用图画模拟一下移位操作,就能很快明白意义了
	int shiftAmount = 32;
	int invShift = 0;
	int bufLen = bufferLen;

	while (bufLen > 1 && buffer[bufLen - 1] == 0)
		bufLen--;

	for (int count = shiftVal; count > 0; )
	{
		if (count < shiftAmount)
		{
			shiftAmount = count;
			invShift = 32 - shiftAmount;
		}

		unsigned __int64 carry = 0;
		for (int i = bufLen - 1; i >= 0; i--)
		{
			unsigned __int64 val = ((unsigned __int64)buffer[i]) >> shiftAmount;
			val |= carry;

			carry = ((unsigned __int64)buffer[i]) << invShift;
			buffer[i] = (unsigned int)(val);
		}

		count -= shiftAmount;
	}

	while (bufLen > 1 && buffer[bufLen - 1] == 0)
		bufLen--;

	return bufLen;
}

BigInteger BigInteger::operator <<(int shiftVal)
{
	BigInteger result(*this);
	result.dataLength = shiftLeft(result.data, maxLength, shiftVal);

	return result;
}

int BigInteger::shiftLeft(unsigned int buffer[], int bufferLen, int shiftVal)
{
	int shiftAmount = 32;
	int bufLen = bufferLen;

	while (bufLen > 1 && buffer[bufLen - 1] == 0)
		bufLen--;

	for (int count = shiftVal; count > 0; )
	{
		if (count < shiftAmount)
			shiftAmount = count;

		unsigned __int64 carry = 0;
		for (int i = 0; i < bufLen; i++)
		{
			unsigned __int64 val = ((unsigned __int64)buffer[i]) << shiftAmount;
			val |= carry;

			buffer[i] = (unsigned int)(val & 0xFFFFFFFF);
			carry = val >> 32;
		}

		if (carry != 0)
		{
			if (bufLen + 1 <= bufferLen)
			{
				buffer[bufLen] = (unsigned int)carry;
				bufLen++;
			}
		}
		count -= shiftAmount;
	}
	return bufLen;
}

bool BigInteger::operator <(BigInteger bi2)
{
	BigInteger bi1(*this);
	int pos = maxLength - 1;

	// bi1 is negative, bi2 is positive
	if ((bi1.data[pos] & 0x80000000) != 0 && (bi2.data[pos] & 0x80000000) == 0)
		return true;

	// bi1 is positive, bi2 is negative
	else if ((bi1.data[pos] & 0x80000000) == 0 && (bi2.data[pos] & 0x80000000) != 0)
		return false;

	// same sign
	int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
	for (pos = len - 1; pos >= 0 && bi1.data[pos] == bi2.data[pos]; pos--) ;

	if (pos >= 0)
	{
		if (bi1.data[pos] < bi2.data[pos])
			return true;
		return false;
	}
	return false;
}

BigInteger BigInteger::operator +=(BigInteger bi2)
{
	*this = *this + bi2;
	return *this;
}

BigInteger BigInteger::operator /(BigInteger bi2)
{
	BigInteger bi1(*this);
	BigInteger quotient;
	BigInteger remainder;

	int lastPos = maxLength - 1;
	bool divisorNeg = false, dividendNeg = false;

	if ((bi1.data[lastPos] & 0x80000000) != 0)     // bi1 negative
	{
		bi1 = -bi1;
		dividendNeg = true;
	}
	if ((bi2.data[lastPos] & 0x80000000) != 0)     // bi2 negative
	{
		bi2 = -bi2;
		divisorNeg = true;
	}

	if (bi1 < bi2)
	{
		return quotient;
	}

	else
	{
		if (bi2.dataLength == 1)
			singleByteDivide(bi1, bi2, quotient, remainder);
		else
			multiByteDivide(bi1, bi2, quotient, remainder);

		if (dividendNeg != divisorNeg)
			return -quotient;

		return quotient;
	}
}

BigInteger BigInteger::operator -=(BigInteger bi2)
{
	*this = *this - bi2;
	return *this;
}

BigInteger BigInteger::operator -(BigInteger bi2)   //减法的重载
{
	BigInteger bi1(*this);
	BigInteger result;
	int lastPos = maxLength - 1;
	bool bi1Neg = false, bi2Neg = false;

	if ((this->data[lastPos] & 0x80000000) != 0)     // bi1 negative
	    bi1Neg = true; 
	if ((bi2.data[lastPos] & 0x80000000) != 0)     // bi1 negative
		bi2Neg = true;

	if(bi1Neg == false && bi2Neg == false)   //bi1,bi2都为正数
	{
		if(bi1 < bi2)
	    {
		 result = -(bi2 - bi1);
		 return result;
	    }
		result.dataLength = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;

		__int64 carryIn = 0;
		for (int i = 0; i < result.dataLength; i++)   //从低位开始减
		{
			__int64 diff;

			diff = (__int64)bi1.data[i] - (__int64)bi2.data[i] - carryIn;
			result.data[i] = (unsigned int)(diff & 0xFFFFFFFF);

			if (diff < 0)
				carryIn = 1;
			else
				carryIn = 0;
		}

		if (carryIn != 0)
		{
			for (int i = result.dataLength; i < maxLength; i++)
				result.data[i] = 0xFFFFFFFF;
			result.dataLength = maxLength;
		}

		// fixed in v1.03 to give correct datalength for a - (-b)
		while (result.dataLength > 1 && result.data[result.dataLength - 1] == 0)
			result.dataLength--;

		// overflow check

		if ((bi1.data[lastPos] & 0x80000000) != (bi2.data[lastPos] & 0x80000000) &&
			(result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
		{
			assert(false);
		}

		return result;
	}

	if(bi1Neg == true && bi2Neg == false)    //bi1负,bi2正
	{
		result = -(-bi1 + bi2);
		return result;
	}

	if(bi1Neg == false && bi2Neg == true)   //bi1正,bi2负
	{
		result = bi1 + (-bi2);
		return result;
	}

	if(bi1Neg == true && bi2Neg == true)   //bi1,bi2皆为负
	{
		BigInteger bi3 = -bi1, bi4 = -bi2;
		if(bi3 > bi4)
		{
		 result = -(bi3 - bi4);
		 return result;
		}
		else
		{
			result = bi4 - bi3;
			return result;
		}
	}
}

string BigInteger::DecToHex(unsigned int value, string format)   //10进制数转换成16进制数,并用string表示
{
	string HexStr;
	int a[100]; 
	int i = 0; 
	int m = 0;
	int mod = 0; 
	char hex[16]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
	while(value > 0) 
	{ 
		mod = value % 16; 
		a[i++] = mod; 
		value = value/16; 

	} 

	for(i = i - 1; i >= 0; i--)
	{ 
		m=a[i];
		HexStr.push_back(hex[m]);
	} 

	while (format == string("X8") && HexStr.size() < 8)
	{
		HexStr = "0" + HexStr;
	}

	return HexStr;
}

string BigInteger::ToHexString()  //功能:将一个大数用16进制的string表示出来
{
	string result = DecToHex(data[dataLength - 1], string("X"));

	for (int i = dataLength - 2; i >= 0; i--)
	{
		result += DecToHex(data[i], string("X8"));
	}

	return result;
}

ostream& operator<<(ostream& output, BigInteger &obj)//以16进制输出数值
{
	 //if ((obj.data[obj.dataLength-1] & 0x80000000) != 0)     // bi1 negative
	for(int i = obj.dataLength - 1; i >= 0; i--)
		output << hex << obj.data[i];
	return output;
}


bool Miller_Robin(BigInteger &bi1)   //Miller_Robin算法
{
	BigInteger one((__int64)1), two((__int64)2), sum, a, b, temp;
	int k = 0, len = primeLength / 2;
	temp = sum = bi1 - one;
	while((sum.data[0] & 0x00000001) == 0)   //只要sum不为奇数,sum就一直往右移
	{
		sum.dataLength = sum.shiftRight(sum.data, maxLength, 1);   //右移一位
		k++;
	}
	//sum即为要求的奇数,k即是要求的2的次数
	srand((unsigned)time(0));
	for(int i = 0; i < len; i++)
	{
		a.data[i] =(unsigned int)rand ();
		if(a.data[i] != 0) a.dataLength = i + 1;
	}

	b = a.modPow(sum, bi1);  //b = a^m mod bi1
	if (b == one) return true;   

	for(int i = 0; i < k; i++)
	{
		if(b == temp) return true;
		else b = b.modPow(two, bi1);  //b = b^2 mod bi1
	}
    return false;
}

bool IsPrime (BigInteger &obj)
{
	BigInteger zero;
	for(int i = 0; i < 303; i++)   //先用一些素数对这个整数进行筛选
	{
		BigInteger prime((__int64)primesBelow2000[i]);
		if(obj % prime == zero)
			return false;
	}
	cout << "第一轮素性检验通过… … … …" << endl;
	cout << "正在进行Miller_Robin素性检验… … … …" << endl;
	if(Miller_Robin(obj))   //进行1次Miller_Robin检验
		return true;  //通过了就返回result	  
	return false;//表明result是合数,没有通过检验
}

BigInteger GetPrime()
{
	BigInteger one((__int64)1), two((__int64)2), result;
	srand((unsigned)time(0));

	//随机产生一个大整数
	for(int i = 0; i < primeLength; i++)
	{
		result.data[i] =(unsigned int)rand();
		if(result.data[i] != 0)
		result.dataLength = i + 1;
	}

	result.data[0] |= 0x00000001;   //保证这个整数为奇数
	while(!IsPrime(result))   //如果没有通过检验,就+2,继续检验
	{
	 result = result + two;

	 cout << "检验没有通过,进行下一个数的检验,运行之中… … … …" << endl;
	 cout << endl;
	}
	return result;
	
}




BigInteger extended_euclidean(BigInteger n, BigInteger m, BigInteger &x, BigInteger &y)   //扩展的欧几里德算法  
{  
	BigInteger x1((__int64)1), x2, x3(n);  
    BigInteger y1, y2((__int64)1), y3(m); 
	BigInteger zero;
    while(x3 % y3 != zero)  
    {  
		BigInteger d = x3 / y3;  
		BigInteger t1, t2, t3;  
        t1 = x1 - d * y1;  
        t2 = x2 - d * y2;  
        t3 = x3 - d * y3;  
        x1 = y1; x2 = y2; x3 = y3;  
        y1 = t1; y2 = t2; y3 = t3;  
    }  
    x = y1; y = y2;  
    return y3;  
} 

/*
BigInteger extended_euclidean(BigInteger n,BigInteger m,BigInteger &x,BigInteger &y)  
{  
	BigInteger zero, one((__int64)1);
    if(m == zero) { x = one; y = zero; return n; }  
    BigInteger g = extended_euclidean(m, n%m, x, y);  
    BigInteger t = x - n / m * y;  
    x = y;  
    y = t;  
    return g;  
}  
*/

BigInteger Gcd(BigInteger &bi1, BigInteger &bi2)
{
	BigInteger x, y;
	BigInteger g = extended_euclidean(bi1, bi2, x, y);
	return g;
}

BigInteger MultipInverse(BigInteger &bi1, BigInteger &n)   //求乘法逆元
{
   BigInteger x, y;
   extended_euclidean(bi1, n, x, y);
   if ((x.data[maxLength-1] & 0x80000000) != 0)     // x negative
	   x = x + n;
  // unsigned int i =  x.data[maxLength-1] & 0x80000000;
  // cout << i << endl;
   return x;
}

还需要一个用于计算消息hash值的MD5~

md5.h

 #include <stdio.h>
// #include <stdint.h>
 #include <string.h>
 #include <assert.h>

 #define ROTL32(dword, n) ((dword) << (n) ^ ((dword) >> (32 - (n))))
 /*MD5的结果数据长度*/
 static const unsigned int MD5_HASH_SIZE   = 16;

 /*每次处理的BLOCK的大小*/
 static const unsigned int MD5_BLOCK_SIZE = 64;
 //================================================================================================
 /*MD5的算法*/
 
 
 /*md5算法的上下文,保存一些状态,中间数据,结果*/
 typedef struct md5_ctx
 {
     /*处理的数据的长度*/
     unsigned __int64 length;
     /*还没有处理的数据长度*/
     unsigned __int64 unprocessed;
     /*取得的HASH结果(中间数据)*/
     unsigned int  hash[4];
 } md5_ctx;
 
 

 
 static void md5_init(md5_ctx *ctx)
 {
     ctx->length = 0;
     ctx->unprocessed = 0;
 
     /* initialize state */
	 /*不要奇怪为什么初始数值与参考数值不同,这是因为我们使用的数据结构的关系,大的在低位,小的在高位,8位8位一读*/
     ctx->hash[0] = 0x67452301; /*应该这样读0x01234567*/
     ctx->hash[1] = 0xefcdab89; /*0x89abcdef*/
     ctx->hash[2] = 0x98badcfe; /*0xfedcba98*/
     ctx->hash[3] = 0x10325476; /*0x76543210*/
 }
 
 #define MD5_F(x, y, z) ((((y) ^ (z)) & (x)) ^ (z))
 #define MD5_G(x, y, z) (((x) & (z)) | ((y) & (~z)))
 #define MD5_H(x, y, z) ((x) ^ (y) ^ (z))
 #define MD5_I(x, y, z) ((y) ^ ((x) | (~z)))
 
 /* 一共4轮,每一轮使用不同函数*/
 #define MD5_ROUND1(a, b, c, d, x, s, ac) {        \
         (a) += MD5_F((b), (c), (d)) + (x) + (ac); \
         (a) = ROTL32((a), (s));                   \
         (a) += (b);                               \
     }
 #define MD5_ROUND2(a, b, c, d, x, s, ac) {        \
         (a) += MD5_G((b), (c), (d)) + (x) + (ac); \
         (a) = ROTL32((a), (s));                   \
         (a) += (b);                               \
     }
 #define MD5_ROUND3(a, b, c, d, x, s, ac) {        \
         (a) += MD5_H((b), (c), (d)) + (x) + (ac); \
         (a) = ROTL32((a), (s));                   \
         (a) += (b);                               \
     }
 #define MD5_ROUND4(a, b, c, d, x, s, ac) {        \
         (a) += MD5_I((b), (c), (d)) + (x) + (ac); \
         (a) = ROTL32((a), (s));                   \
         (a) += (b);                               \
     }
 

 static void md5_process_block(unsigned int state[4], const unsigned int block[MD5_BLOCK_SIZE / 4])
 {
     register unsigned a, b, c, d;
     a = state[0];
     b = state[1];
     c = state[2];
     d = state[3];
 
     const unsigned int *x = block;
 
 
     MD5_ROUND1(a, b, c, d, x[ 0],  7, 0xd76aa478);
     MD5_ROUND1(d, a, b, c, x[ 1], 12, 0xe8c7b756);
     MD5_ROUND1(c, d, a, b, x[ 2], 17, 0x242070db);
     MD5_ROUND1(b, c, d, a, x[ 3], 22, 0xc1bdceee);
     MD5_ROUND1(a, b, c, d, x[ 4],  7, 0xf57c0faf);
     MD5_ROUND1(d, a, b, c, x[ 5], 12, 0x4787c62a);
     MD5_ROUND1(c, d, a, b, x[ 6], 17, 0xa8304613);
     MD5_ROUND1(b, c, d, a, x[ 7], 22, 0xfd469501);
     MD5_ROUND1(a, b, c, d, x[ 8],  7, 0x698098d8);
     MD5_ROUND1(d, a, b, c, x[ 9], 12, 0x8b44f7af);
     MD5_ROUND1(c, d, a, b, x[10], 17, 0xffff5bb1);
     MD5_ROUND1(b, c, d, a, x[11], 22, 0x895cd7be);
     MD5_ROUND1(a, b, c, d, x[12],  7, 0x6b901122);
     MD5_ROUND1(d, a, b, c, x[13], 12, 0xfd987193);
     MD5_ROUND1(c, d, a, b, x[14], 17, 0xa679438e);
     MD5_ROUND1(b, c, d, a, x[15], 22, 0x49b40821);
 
     MD5_ROUND2(a, b, c, d, x[ 1],  5, 0xf61e2562);
     MD5_ROUND2(d, a, b, c, x[ 6],  9, 0xc040b340);
     MD5_ROUND2(c, d, a, b, x[11], 14, 0x265e5a51);
     MD5_ROUND2(b, c, d, a, x[ 0], 20, 0xe9b6c7aa);
     MD5_ROUND2(a, b, c, d, x[ 5],  5, 0xd62f105d);
     MD5_ROUND2(d, a, b, c, x[10],  9,  0x2441453);
     MD5_ROUND2(c, d, a, b, x[15], 14, 0xd8a1e681);
     MD5_ROUND2(b, c, d, a, x[ 4], 20, 0xe7d3fbc8);
     MD5_ROUND2(a, b, c, d, x[ 9],  5, 0x21e1cde6);
     MD5_ROUND2(d, a, b, c, x[14],  9, 0xc33707d6);
     MD5_ROUND2(c, d, a, b, x[ 3], 14, 0xf4d50d87);
     MD5_ROUND2(b, c, d, a, x[ 8], 20, 0x455a14ed);
     MD5_ROUND2(a, b, c, d, x[13],  5, 0xa9e3e905);
     MD5_ROUND2(d, a, b, c, x[ 2],  9, 0xfcefa3f8);
     MD5_ROUND2(c, d, a, b, x[ 7], 14, 0x676f02d9);
     MD5_ROUND2(b, c, d, a, x[12], 20, 0x8d2a4c8a);
 
     MD5_ROUND3(a, b, c, d, x[ 5],  4, 0xfffa3942);
     MD5_ROUND3(d, a, b, c, x[ 8], 11, 0x8771f681);
     MD5_ROUND3(c, d, a, b, x[11], 16, 0x6d9d6122);
     MD5_ROUND3(b, c, d, a, x[14], 23, 0xfde5380c);
     MD5_ROUND3(a, b, c, d, x[ 1],  4, 0xa4beea44);
     MD5_ROUND3(d, a, b, c, x[ 4], 11, 0x4bdecfa9);
     MD5_ROUND3(c, d, a, b, x[ 7], 16, 0xf6bb4b60);
     MD5_ROUND3(b, c, d, a, x[10], 23, 0xbebfbc70);
     MD5_ROUND3(a, b, c, d, x[13],  4, 0x289b7ec6);
     MD5_ROUND3(d, a, b, c, x[ 0], 11, 0xeaa127fa);
     MD5_ROUND3(c, d, a, b, x[ 3], 16, 0xd4ef3085);
     MD5_ROUND3(b, c, d, a, x[ 6], 23,  0x4881d05);
     MD5_ROUND3(a, b, c, d, x[ 9],  4, 0xd9d4d039);
     MD5_ROUND3(d, a, b, c, x[12], 11, 0xe6db99e5);
     MD5_ROUND3(c, d, a, b, x[15], 16, 0x1fa27cf8);
     MD5_ROUND3(b, c, d, a, x[ 2], 23, 0xc4ac5665);
 
     MD5_ROUND4(a, b, c, d, x[ 0],  6, 0xf4292244);
     MD5_ROUND4(d, a, b, c, x[ 7], 10, 0x432aff97);
     MD5_ROUND4(c, d, a, b, x[14], 15, 0xab9423a7);
     MD5_ROUND4(b, c, d, a, x[ 5], 21, 0xfc93a039);
     MD5_ROUND4(a, b, c, d, x[12],  6, 0x655b59c3);
     MD5_ROUND4(d, a, b, c, x[ 3], 10, 0x8f0ccc92);
     MD5_ROUND4(c, d, a, b, x[10], 15, 0xffeff47d);
     MD5_ROUND4(b, c, d, a, x[ 1], 21, 0x85845dd1);
     MD5_ROUND4(a, b, c, d, x[ 8],  6, 0x6fa87e4f);
     MD5_ROUND4(d, a, b, c, x[15], 10, 0xfe2ce6e0);
     MD5_ROUND4(c, d, a, b, x[ 6], 15, 0xa3014314);
     MD5_ROUND4(b, c, d, a, x[13], 21, 0x4e0811a1);
     MD5_ROUND4(a, b, c, d, x[ 4],  6, 0xf7537e82);
     MD5_ROUND4(d, a, b, c, x[11], 10, 0xbd3af235);
     MD5_ROUND4(c, d, a, b, x[ 2], 15, 0x2ad7d2bb);
     MD5_ROUND4(b, c, d, a, x[ 9], 21, 0xeb86d391);
 
     state[0] += a;
     state[1] += b;
     state[2] += c;
     state[3] += d;
 }
 
 
 static void md5_update(md5_ctx *ctx, const unsigned char *buf, unsigned int size)
 {
     /*为什么不是=,因为在某些环境下,可以多次调用zen_md5_update,但这种情况,必须保证前面的调用,每次都没有unprocessed*/
     ctx->length += size;
 
     /*每个处理的块都是64字节*/
     while (size >= MD5_BLOCK_SIZE)
     {
         md5_process_block(ctx->hash, reinterpret_cast<const unsigned int *>(buf));
         buf  += MD5_BLOCK_SIZE;    /*buf指针每一次向后挪动64*/
         size -= MD5_BLOCK_SIZE;   /*每一次处理64个字符*/
     }
 
     ctx->unprocessed = size;   /*未处理的字符数数目记录下来*/
 }
 
 

 static void md5_final(md5_ctx *ctx, const unsigned char *buf, unsigned int size, unsigned char *result)
 {
     unsigned int message[MD5_BLOCK_SIZE / 4];
	 memset(message, 0 ,(MD5_BLOCK_SIZE / 4) * sizeof(unsigned int));
     /*保存剩余的数据,我们要拼出最后1个(或者两个)要处理的块,前面的算法保证了,最后一个块肯定小于64个字节*/
     if (ctx->unprocessed)
     {
         memcpy(message, buf + size - ctx->unprocessed, static_cast<unsigned int>( ctx->unprocessed));
		/*================================================================================
		 这里的memcpy复制很有趣,是按照字节复制比如说buf --- 0x11 0x14 0xab 0x23 0xcd  |
		 ctx>unprocessed_=5 现在copy至 message --- 0x23ab1411 0x000000cd
		 这样的话,下面的也很好解释了!
		=================================================================================*/
     }
	   /*=================================================================================
        用法:static_cast < type-id > ( expression )
        该运算符把expression转换为type-id类型
        ==================================================================================*/

     /*得到0x80要添加在的位置(在unsigned int 数组中)*/
     unsigned int index = ((unsigned int)ctx->length & 63) >> 2;
	 /*一次性处理64个unsigned int型数据,(unsigned int)ctx->length_ & 63求出余下多少未处理的字符*/

     unsigned int shift = ((unsigned int)ctx->length & 3) * 8;
	 /*一个message里面可以放置4个字符数据,找到应该移动的位数*/
 
     /*添加0x80进去,并且把余下的空间补充0*/
     message[index++] ^= 0x80 << shift;   /*^ 位异或*/
 
     /*如果这个block还无法处理,其后面的长度无法容纳长度64bit,那么先处理这个block*/
     if (index > 14)
     {
         while (index < 16)
         {
             message[index++] = 0;
         }
 
         md5_process_block(ctx->hash, message);
         index = 0;
     }
 
     /*补0*/
     while (index < 14)
     {
         message[index++] = 0;
     }
 
     /*保存长度,注意是bit位的长度*/
     unsigned __int64 data_len = (ctx->length) << 3;
 
     message[14] = (unsigned int) (data_len & 0x00000000FFFFFFFF);
     message[15] = (unsigned int) ((data_len & 0xFFFFFFFF00000000ULL) >> 32);
 
     md5_process_block(ctx->hash, message);
     memcpy(result, &ctx->hash, MD5_HASH_SIZE);  
 }
 
 
  unsigned char* md5(const unsigned char *buf,  unsigned int  size,   unsigned char result[MD5_HASH_SIZE])  
 {  
     md5_ctx ctx;  
     md5_init(&ctx);   /*初始化*/
     md5_update(&ctx, buf, size);     
     md5_final(&ctx, buf, size, result);  
     return result;  
 }  
 
然后才是ELGamal的实现~

ELGamal.h

#include <string>
#include "BigInteger.h"
#include "md5.h"


/*
*事先说明一句:由于大素数的本原元很难求得,所以这里的数字签名所需要的数字我都提前给出
*避免了没必要的十分耗时的生成过程,大家也可以直接修改这些数字,即使是很大的数也支持!
*/

/*测试数据:
* 素数 p = 19, 本原元 g = 2, 私钥 x = 9, 公钥 y = 18, 随机取值 k = 5
*/

string prime("19"), prielem("2"), key("9"), pubKey("18"), randomK("5");

/*数的初始化*/
/*p 素数 g 本原元 x 私钥 y 公钥 k 随机取值*/
BigInteger p(prime, 10),g(prielem, 10), x(key, 10), y(pubKey, 10), k(randomK, 10),
		one((__int64)1), two((__int64)2);

/*签名*/
void elgamalSign(unsigned char *message, int len, BigInteger &r, BigInteger &s)
{
    
	/*m 为消息所对应的明文数值*/
	unsigned char result[16] ={0};
	md5(message, len, result);

    /*输出MD5值*/
	cout << "消息的MD5散列值为:" ;
	for (int i = 0; i < 16; i++)
	 printf ("%02x", result[i]);
	cout << endl;

	/*用md5作为消息的hash值*/
	/*用hash值初始化m*/
	BigInteger m(result, 16), pMinusOne(p - one);
	BigInteger  k1;

	r = g.modPow(k, p);

	/*k1 为 k 在 p - 1 下的逆元*/
	k1 = MultipInverse(k, pMinusOne);

	s = ((m - x * r) * k1 ) % pMinusOne;
	
}
/*签名验证*/
bool elgamalVerifiSign(unsigned char *message, int len, BigInteger &r, BigInteger &s)
{
    cout << "接收到消息的MD5散列值为:";
    unsigned char result[16] ={0};

	md5(message, len, result);
	for (int i = 0; i < 16; i++)
	 printf ("%02x", result[i]);
	cout << endl;

    BigInteger leftValue, rightValue;
    BigInteger m(result, 16);

	leftValue = (y.modPow(r, p) * r.modPow(s, p)) % p;
	rightValue = g.modPow(m, p);
	if (leftValue == rightValue)
	{
		return true;
	}
	else
	{
		return false;
	}

}
最后上一个主函数测试一下!

main.cpp

//本原元的概念:若模n下a的阶d=φ(n),a就是n的本原元(又称为原根)。此时a是Z*_n的生成元。
/*======================================================
Diffie-Hellman 算法下面就给出一个快速求大素数 p 及其本原根的算法
算法如下:
P1. 利用素性验证算法,生成一个大素数 q;
P2. 令 p = q * 2 + 1;
P3. 利用素性验证算法,验证 p 是否是素数,如果 p 是合数,则跳转到 P1;
P4. 生成一个随机数 g,1 < g < p - 1;
P5. 验证 g2 mod p 和 gq mod p 都不等于 1,否则跳转到 P4;
P6. g 是大素数 p 的本原根。
======================================================*/
#include "ELGamal.h"

int main()
{
/*================================================================
//求一个大素数以及其本原元有点难度,速度慢到不行,我丢弃了这个想法,素数和本原元直接输入
BigInteger p((__int64)3), q, two((__int64)2), one((__int64)1), g, zero;
srand((unsigned)time(0));
bool flag = false;
while(!flag)
{
	q = GetPrime(); //得到一个大素数
	//cout << q << endl;
	//system("pause");
	p = q * two + one;
	if(IsPrime(p))
	flag = true;
}
	   
while ((g * g) % p != one && (g * q) % p != one )
{   
	unsigned int len = rand() % 20;
	for (int i = 0; i < len; i++)   //产生一个随机数g
	{
		g.data[i] = (unsigned int)rand ();
	    if(g.data[i] != 0)
		g.dataLength = i + 1;
	}
}
cout << p << endl;
cout << g << endl;
========================================================*/
	cout << "签名者 A:" << endl;
	
    string message;
	BigInteger r, s;

	cout << "请输入要签名的消息:" << endl;
	cin >> message;
    
	elgamalSign((unsigned char *)message.c_str(), message.length(), r, s);

    cout << "签名信息如下:" << endl;

	/*不要奇怪为什么r总是等于d,去看一下r的定义就知道了。
	*r  = g^k mod p[g是mod p 下的本原元, k是任意取的常数(k 与 p - 1互素),p是素数]
	*由于以上的这些数都提前给定了,所以结果也肯定是一个常数
	*/
	cout << "r = " << r << endl;
	cout << "s = " << s << endl;
    cout << endl;
	/*
	unsigned int len = rand() % 10;
	for (int i = 0; i < len; i++)
	{
		k.data[i] = (unsigned int)rand ();
	    if(k.data[i] != 0)
		k.dataLength = i + 1;
	}
	temp = p - one;
	while(Gcd(k,p - one) != one)
	{
		k = k + two;
	}
	cout << k <<endl;
	*/

	cout << "现在将 消息 以及 r s 传递给接收方 B ~~~ ~~~" << endl;
    cout << endl;
	cout << "接受者 B:" << endl;
	if (elgamalVerifiSign((unsigned char *)message.c_str(), message.length(), r, s))
	{
		cout << "签名有效" << endl;
	}
	else
	{
        cout << "签名无效" << endl;
	}

	system ("pause");
	return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lishuhuakai/article/details/9117619

智能推荐

Eclipse编码修改和设置_kevin_cat的博客-程序员宅基地_eclipse编码修改

编码修改分类:1.工作空间编码2.项目编码3.文件编码1.工作空间编码2.项目编码3文件编码修改

python3解析JSON之demjson_kfyzjd2008的博客-程序员宅基地_demjson python3

安装好python之后自带的就有一个json解析库使用 JSON 函数需要导入 json 库:import json。json.dumps 将 Python 对象编码成 JSON 字符串 json.loads 将已编码的 JSON 字符串解码为 Python 对象 但是有时我们会遇到不是很标准的JSON,这是这个库就无法解析了。例如:{0:"00000...

Caffe-如何修改为deploy.prototxt用于测试_路人K_的博客-程序员宅基地

(1)将原网络文件去掉(以下部分)layer { name: "data" type: "Data" top: "data" top: "label" include { phase: TRAIN } transform_param { crop_size: 227 mean_value: 104 mean_value: 117 ...

Windows XP Service Pack 2中弹出窗口拦截器的研究_Amom的博客-程序员宅基地

1 引言1.1 研究背景微软公司于2004年8月份正式发布了耗资庞大的Windows XP Service Pack 2(英文版),这不是一次简单的补丁打包升级,而是融入了众多新技术的Windows系统更新。微软声称SP2解决了以往的众多系统漏洞并且大大加强了Windows的安全性。对于Web开发者来说,值得关注的是SP2在IE中加入了Pop-up(弹出窗口拦截)功能,这将影响到世界上绝大部分使用

随便推点

我收集了39节从0入门《人工智能+Python》视频课,价值1999,免费下载 等会就删!..._吴师兄学算法的博客-程序员宅基地

近几年来人工智能常常成为热门议题,经久不衰。2020年以来,在各种政策红利催化、5G商用助推、物联网、大数据、AI芯片技术大规模落地后,几乎所有人都已经笃定,人工智能就是IT人未来的新风...

记录greendao3.0的学习使用_kevin_321V的博客-程序员宅基地

关于greendao数据库的使用Greendao是目前比较热门数据库框架,将对象映射到 SQLite 数据库中的轻量且快速的 ORM 解决方案。具备精简、性能最大化、内存开销最小化、易于使用的 APIs、等诸多有点,下面记录一下greendao的初步学习使用。使用只需要按照以下几步来做:一、 通过项目app的moudle下的gradle引入依赖:compile 'org.green

输入一个数字,输出它的阶乘结果。(c语言)_蓝创精英团队的博客-程序员宅基地_输入一个数输出它的阶乘

#define _CRT_SECURE_NO_WARNINGS#include&amp;lt;stdio.h&amp;gt;#include&amp;lt;stdlib.h&amp;gt;//输入一个数字,显示出它的阶乘void main(char* args){ int num=0; int i=0; int result=1; printf(&quot;输入需要阶乘的数字:&quot;); scanf(&quot;%d&quot;,&amp;am...

golang微服务框架go-micro 入门笔记2.1 micro工具之微应用利器micro web_imwinlion的博客-程序员宅基地

micro web micro 功能非常强大,本文将详细阐述micro web 命令行的功能 阅读本文前你可能需要进行如下知识储备 golang分布式微服务框架go-micro 入门笔记1:搭建go-micro环境, golang微服务框架go-micro 入门笔记2.1 micro工具之micro api 本文应用环境 名称 描述 操作系统 ...

推荐文章

热门文章

相关标签