#include <iostream>
#include <stdlib.h>
#include <Windows.h>
#include <time.h>
#include <fstream>
#include<cassert>
#include<conio.h>
#include<cstring>
#include "pke_api.h"

using namespace std;
#define sk_len  5 * N;
#define	pk_len  6 * N


typedef short int i16;
typedef  int i32;
typedef long long int i64;



inline i32 centered_modulo(const i32 x, const i32 N) {
// MODULO(x,N) 1 // residue mod odd integer N with reps.  in [-N/2,...,N/2]
// input: x \in Int; N odd positive int
	i32 t = x % N;
	if (t < -N / 2) {
		return t + N;
	}
	else if (t > N / 2) {
		return t - N;
	}
	else {
		return t;
	}	
}

inline void print_vec(i32 * data, const int len) {
	for (register int i = 0; i < len; i++) {
		printf("%d ", data[i]);
	}
	printf("\n");
}

i32 evaluate1(i32 *data, const int len) {
	i32 sum = 0;
	for (register int i = 0; i < len; i++) {
		sum += data[i];
	}

	return sum;
}
/********************声明函数*************************/
int int_inv_int(int a, int b);
void shiftMulModp(int x[], int a[], int b[], int pp, int halfpp);
void shifMul_Add_Mod(int x[], int a[], int b[], int c[], int pp, int halfpp);
int poly_inv_poly(int a[], int b[],  int d);

/************************************
N为多项式的项数，d1=N/3,私钥多项式f1的空间L(d1,d1-1),私钥多项式g1的空间L(d1,d1-1),工作密钥r1的空间L(d1,d1)，当N=157时，d1=53，因此f1和g1中系数为-1和1的总项数为df1=dg1=105,r1中系数为-1和1的总项数为dr1=106
************************************/
/*
the 3rd deso NOT abide
d=N/3;
d1=d+1; ???
*/
int N;
int p;
int q1;
int q2;
int df1;
int dg1;
int d1;// 1s in r1
int dr1;// total in r1, dr1-d1 = -1s in rq
int half_p;
int half_q1;
int half_q2;

int MM;
int NN;
unsigned int Enc_Sum_Time = 0;
unsigned int Dec_Sum_Time = 0;


//a为一个多项式，n为多项式的长度
int deg(int a[],int n)
{
	int i;
	for(i = n-1;a[i] == 0 && i >=0;i--)
		;
	return i;
}

//获取私钥f、fp和gsk
int get_sk()
{
	int* f_SubScript = new int[df1];//通过随机化下标来随机选取f1和g1
	int* g_SubScript = new int[dg1];
	
	int* f = new int[N]();
	int* fp = new int[N]();  //用来存储f模p的逆元
	int* fq1 = new int[N]();  //用来存储f模q1的逆元
loop1:
	/***********************随机选取f**************************/
	for (int i = 0; i<df1; i++) {//获取随机化下标（即随机确定多项式f1的某些项为1或-1）
		f_SubScript[i] = (rand() * rand()) % N;
		for (int j = 0; j<i; j++) {
			if (f_SubScript[i] == f_SubScript[j]) {//判断是否出现重复的下标
				f_SubScript[i] = rand() % N;
				j = -1;//将会执行j++, 从而是由0号开始比较
			}
		}
	}
	for (int i = 0; i<d1; i++) {//通过随机化下标来设置多项式f1的系数	
		f[f_SubScript[i]] = 1;
	}
	for (int i = d1; i<df1; i++) {
		f[f_SubScript[i]] = -1;
	}

	/******************判断f在环Rp中是否可逆并获得f模p的逆fp，可逆，往下执行；否则，重新生成f********************/
	long flagp = 0;
	flagp = poly_inv_poly(fp, f, p);
	if (flagp == 0)
		goto loop1;

	/***********输出f在模p情况下的逆元fp，用于解密*****************/
	ofstream fout_fp("F:\\coding\\d-ntru\\fp.txt");
	assert(fout_fp);
	for (int i = 0; i<N; i++)
	{
		if (fp[i] > half_p) {
			fp[i] -= p;
		}
		
		fout_fp << fp[i] << " ";
	}
	fout_fp.close();

	/*****************判断f在环Rq1中是否可逆并获得f模q1的逆fq1，可逆，往下执行；否则，重新生成f*******************/
	long flagq1 = 0;
	flagq1 = poly_inv_poly(fq1, f, q1);

	if (flagq1 == 0)
		goto loop1;

	/***********输出f在模q情况下的逆元fq1，用于计算公钥*****************/
	ofstream fout_fq1("F:\\coding\\d-ntru\\fq1.txt");
	assert(fout_fq1);
	for (int i = 0; i<N; i++)
	{
		if (fq1[i] > half_q1)
			fq1[i] -= q1;
		fout_fq1 << fq1[i] << " ";
	}
	fout_fq1.close();
	

	int* g = new int[N]();
	int* gq1 = new int[N]();  //用来存储g模q1的逆元
	int* gsk = new int[N]();

loop2:

	/********************随机选取多项式g**********************/
	for (int i = 0; i<dg1; i++) {		
		g_SubScript[i] = (rand() * rand()) % N;
		for (int j = 0; j<i; j++) {
			if (g_SubScript[i] == g_SubScript[j]) {
				g_SubScript[i] = rand() % N;
				j = -1;//将会执行j++, 从而是由0号开始比较
			}
		}
	}
	for (int i = 0; i<d1; i++) {//通过随机化下标来设置多项式g1的系数
		g[g_SubScript[i]] = 1;
	}
	for (int i = d1; i<dg1; i++) {
		g[g_SubScript[i]] = -1;
	}

	/***************判断g在环Rq1中是否可逆并获得g模q1的逆gq1，可逆，往下执行；否则，重新生成g*******************/
	long glagq1 = 0;
	glagq1 = poly_inv_poly(gq1, g, q1);
	if (glagq1 == 0)
		goto loop2;

     /******输出私钥g*******/
	ofstream fout_g("F:\\coding\\d-ntru\\g.txt");
	assert(fout_g);
	for (int i = 0; i < N ; i++) {
		fout_g << g[i] << " ";
	}
	fout_g.close();


	/******输出g在模q1下的逆元gq1*******/
	ofstream fout_gq1("F:\\coding\\d-ntru\\gq1.txt");
	assert(fout_gq1);
	for (int i = 0; i < N ; i++) {
		fout_gq1 << gq1[i] << " ";
	}
	fout_gq1.close();


	/*****计算私钥gsk = （p关于q1的逆 * gq1）mod q1,并输出私钥gsk******/
	ofstream fout_gsk("F:\\coding\\d-ntru\\gsk.txt");
	assert(fout_gsk);
	//计算私钥gsk = （ p关于q1的逆 * gq1）mod q1
	int inv_p = (int_inv_int(q1,p)) % q1;
	for (int i = 0; i<N; i++)//计算g1p1*Zp_inv_q1
	{
		gsk[i] = (gq1[i] * inv_p) % q1;
		if (gsk[i] > half_q1) {
			gsk[i] -= q1;
		}
		if(gsk[i] < -half_q1)
			gsk[i] += q1;
		fout_gsk << gsk[i] << " ";
	}
	fout_gsk.close();

	/**********输出私钥f***************/
    ofstream fout_ff("F:\\coding\\d-ntru\\f.txt");
	assert(fout_ff);
	for (int i = 0; i < N; i++){
		fout_ff << f[i] <<" ";		
	}
	fout_ff.close();

	system("del D:\\test\\key\\gq1.txt");	
	delete[] f_SubScript;
	delete[] g_SubScript;
	delete[] f;
	delete[] fp;
	delete[] fq1;
	delete[] g;
	delete[] gq1;
	delete[] gsk;
	return 0;
}

//获取公钥h1,h2
int get_pk() {

	/************读取fq1**************/
	int* fq1 = new int[N]();
	ifstream fin_fq1("F:\\coding\\d-ntru\\fq1.txt");
	assert(fin_fq1);
	for(int i=0;i<N;i++){
		fin_fq1 >> fq1[i];
	}
	fin_fq1.close();


	/****************读取私钥g*******************/
	int* g = new int[N]();
	ifstream fin_g("F:\\coding\\d-ntru\\g.txt");
	assert(fin_g);
	for(int i=0;i<N;i++){
		fin_g >> g[i];
	}
	fin_g.close();

	/************产生公钥h1***************/
	int* h1 = new int[N]();
	shiftMulModp(h1, g, fq1, q1, half_q1);  //h1 = fq1*g (mod q1,mod x^N-1)


	/**********保存公钥h1***************/
    ofstream fout_h1("F:\\coding\\d-ntru\\h1.txt");
	assert(fout_h1);
	for (int i = 0; i<N; i++)
	{
		h1[i] = (h1[i] * p) % q1;
		if (h1[i] > half_q1)
			h1[i] -= q1;

		if(h1[i] < -half_q1)
			h1[i] += q1;
		
		fout_h1 << h1[i] << " ";
	}
	fout_h1.close();


	/**************************产生公钥h2************************/
	int* h2 = new int[N]();
	ofstream fout_h2("F:\\coding\\d-ntru\\h2.txt");
	assert(fout_h2);
	for (int i = 0; i<N; i++) {		
		h2[i] = rand() % q2;
		if (h2[i] > half_q2)
			h2[i] -= q2;

		if(h2[i] < -half_q2)
			h2[i] += q2;
		
		fout_h2 << h2[i] << " ";
	
	}
	fout_h2.close();

	delete[] fq1;
	delete[] g;
	delete[] h1;
	delete[] h2;
	return 0;
}

/*****************************************************************
通过N维数组来表示一个N-1次的多项式，并计算两个多项式的模乘运算
输入：数组a[]和数组b[],其中要求数组a的各个分量属于{-1,0,1}
输出：通过循环移位来计算x=(a*b)(mod(x^N-1))
*****************************************************************/
void shiftMulMod(int x[], int a[], int b[]) {
	int* c = new int[2 * N - 1]();
	for (int i = 0; i<N; i++) {
		if (a[i] == 1) {//当a[i]=1时，对i=0到N-1，计算c[i+local] = c[i+local]+b[i]
			for (int j = 0; j<N; j++) {
				c[i + j] += b[j];
			}
		}
		else if (a[i] == -1) {//当a[i]=-1时，对i=0到N-1，计算c[i+local] = c[i+local]-b[i]
			for (int j = 0; j<N; j++) {
				c[i + j] -= b[j];
			}
		}//当a[i]=0时，不需要进行操作
	}
	for (int i = 0; i<N - 1; i++) {
		x[i] = c[i] + c[i + N];
	}
	x[N - 1] = c[N - 1];

	delete[] c;
}

/*****************************************************************
通过N维数组来表示一个N-1次的多项式，并计算两个多项式的模乘运算
输入：数组a[]和数组b[],其中要求数组a的各个分量属于{-1,0,1}
输出：通过循环移位来计算x=(a*b)(modp,mod(x^N-1))
*****************************************************************/
void shiftMulModp(int x[], int a[], int b[], int pp, int halfpp) {
	int* c = new int[2 * N - 1]();
	for (int i = 0; i<N; i++) {
		if (a[i] == 1) {//当a[i]=1时，对i=0到N-1，计算c[i+local] = c[i+local]+b[i]
			for (int j = 0; j<N; j++) {
				c[i + j] += b[j];
			}
		}
		else if (a[i] == -1) {//当a[i]=-1时，对i=0到N-1，计算c[i+local] = c[i+local]-b[i]
			for (int j = 0; j<N; j++) {
				c[i + j] -= b[j];
			}
		}//当a[i]=0时，不需要进行操作
	}
	for (int i = 0; i<N - 1; i++) {
		x[i] = (c[i] + c[i + N]) % pp;
		if (x[i] > halfpp) {
			x[i] -= pp;
		}
		else if (x[i] < -halfpp) {
			x[i] += pp;
		}
	}
	x[N - 1] = c[N - 1] % pp;
	if (x[N - 1] > halfpp) {
		x[N - 1] -=  pp;
	}
	else if (x[N - 1] < -halfpp) {
		x[N - 1] += pp;
	}
	delete[] c;
}

/*****************************************************************
通过N维数组来表示一个N-1次的多项式
输入：数组a[]、数组b[]和数组c[],其中要求数组a[]的各个分量属于{-1,0,1}
输出：计算x = ( a * b + c)(mod pp,mod(x^N-1))
*****************************************************************/
void shifMul_Add1_Modp(int x[], int a[], int b[], int c[], int pp, int halfpp) {
	int* d = new int[2 * N - 1]();
	for (int i = 0; i<N; i++) {
		if (a[i] == 1) {//当a[i]=1时，对i=0到N-1，计算c[i+local] = c[i+local]+b[i]
			for (int j = 0; j<N; j++) {
				d[i + j] += b[j];
			}
		}
		else if (a[i] == -1) {//当a[i]=-1时，对i=0到N-1，计算c[i+local] = c[i+local]-b[i]
			for (int j = 0; j<N; j++) {
				d[i + j] -= b[j];
			}
		}//当a[i]=0时，不需要进行操作
	}
	for (int i = 0; i<N - 1; i++) {
		x[i] = (c[i] + d[i] + d[i + N]) % pp;
		if (x[i]>halfpp) {
			x[i] = x[i] - pp;
		}
		else if (x[i]<-halfpp) {
			x[i] = x[i] + pp;
		}
	}

	x[N - 1] = (c[N - 1] + d[N - 1]) % pp;
	if (x[N - 1]>halfpp) {
		x[N - 1] = x[N - 1] - pp;
	}
	else if (x[N - 1]<-halfpp) {
		x[N - 1] = x[N - 1] + pp;
	}
	delete[] d;
}

/*****************************************************************
通过N维数组来表示一个N-1次的多项式
输入：数组a[]、数组b[]、数组c[]和数组d[],其中要求数组a[]的各个分量属于{-1,0,1}
输出：计算x = ( a * b + c + d)(mod pp,mod(x^N-1))
*****************************************************************/
void shifMul_Add2_Modp(int x[], int a[], int b[], int c[], int d[], int pp, int halfpp) {
	int* e = new int[2 * N - 1]();
	for (int i = 0; i<N; i++) {
		if (a[i] == 1) {//当a[i]=1时，对i=0到N-1，计算c[i+local] = c[i+local]+b[i]
			for (int j = 0; j<N; j++) {
				e[i + j] += b[j];
			}
		}
		else if (a[i] == -1) {//当a[i]=-1时，对i=0到N-1，计算c[i+local] = c[i+local]-b[i]
			for (int j = 0; j<N; j++) {
				e[i + j] -= b[j];
			}
		}//当a[i]=0时，不需要进行操作
	}
	for (int i = 0; i<N - 1; i++) {
		x[i] = (c[i] + d[i] + e[i] + e[i + N]) % pp;
		if (x[i]>halfpp) {
			x[i] = x[i] - pp;
		}
		else if (x[i]<-halfpp) {
			x[i] = x[i] + pp;
		}
	}

	x[N - 1] = (c[N - 1] + d[N - 1] + e[N - 1]) % pp;
	if (x[N - 1]>halfpp) {
		x[N - 1] = x[N - 1] - pp;
	}
	else if (x[N - 1]<-halfpp) {
		x[N - 1] = x[N - 1] + pp;
	}
	delete[] e;
}

/*****************************************************************
通过N维数组来表示一个N-1次的多项式
输入：数组a[]、数组b[]
输出：对i等于0到N-1,计算x[i] = a[i] + b[i]
*****************************************************************/
void intSub(int x[], int a[], int b[]) {//计算x[] = a[] - b[]
	for (int i = 0; i<N; i++) {
		x[i] = a[i] - b[i];
	}
}

/*****************************************************************
通过N维数组来表示一个N-1次的多项式
输入：数组a[]、数组b[],素数pp和halfpp = pp/2
输出：x = a*b(modpp,mod(x^N - 1))
与上面的通过移位来实现多项式的模乘运算不同，cyclicConvolutionMulModp不要求a或b的系数属于{-1,0,1}
*****************************************************************/
void cyclicConvolutionMulModp(int x[], int a[], int b[], int pp, int halfpp) {//计算x=(a*b)(modp,mod(x^N-1))
	int n_1 = N - 1;
	for (int i = 0; i<N; i++) {
		x[i] = 0;
		for (int j = 0; j<N; j++) {
			x[i] += a[(i + j + 1) % N] * b[n_1 - j];
		}
		x[i] = x[i] % pp;
		if (x[i]>halfpp) {
			x[i] = x[i] - pp;
		}
		else if (x[i]<-halfpp) {
			x[i] = x[i] + pp;
		}
	}
}

/**********************************
多项式模减运算
其中c[]用来记录最后的结果，d表示模数
************************************/
void poly_mod_sub_poly(int a[], int b[],int c[], int d)
{
	for(int i=0;i<N;i++)
	{
		c[i] = (a[i] - b[i]) % d;
		if(c[i] > d/2)
			c[i] -= d;
		if(c[i] <-d/2)
			c[i] += d;
	}
}

/**********************************
多项式模乘运算
其中c[]用来记录最后的结果，d表示模数
************************************/
void poly_mod_mul_poly(int a[], int b[],int c[], int d)
{

	int  i;
	for(i = 0; i < N; i++) {
		int j;
		for(j = 0; j < N; j++) {
			if(i + j >= N) {
				c[i + j -N] += a[i] * b[j];
				c[i + j -N] %= d;
				if(c[i + j -N] > d/2 )
					c[i + j -N] -= d;
				if(c[i + j -N] < -d/2 )
					c[i + j -N] += d;
				
			} else {
				c[i + j] += a[i] * b[j];
				c[i + j ] %= d;
				if(c[i + j ] > d/2 )
					c[i + j ] -= d;
				if(c[i + j ] < -d/2 )
					c[i + j ] += d;
			}
		}
	}
}

/***********************************
整数求逆元，b在模a条件下的逆元
************************************/
int int_inv_int(int a, int b)  
{
	if(b < 0)
		b = b + a;
	int a0 = a,b0 = b;

	int t0 = 0,t = 1,s0 = 1,s = 0;

	int q = a0 / b0,r = a0-q*b0;

	while(r > 0)
	{
		int temp = t0 - q*t;
		t0 = t;
		t = temp ;
		
		temp = s0 - q*s;
		s0 = s;
		s = temp;

		a0 = b0;
		b0 = r;
		q = a0/b0;
		r = a0 - q*b0;
	}
	r = b0;
	if(r == 1)
	{
		//t = t % b;
		//if(t > b/2)
			//t -= b; 
		return t;
	}
	else
		return 0;
}

/*****************************
计算多项式除法
******************************/
void poly_mod_div_poly(int a[], int b[],int rx[], int qx[], int d)
{
	int deg_a = deg(a,N);
	int deg_b = deg(b,N);

	
	for(int i=0;i<=deg_a;i++)
		rx[i] = a[i];
	
	if(deg_a < deg_b){
		return;
	}

	int inv_b = int_inv_int(d,b[deg_b]);

	for(int i = deg_a - deg_b; i >= 0; i--){

		qx[i] = (rx[deg_b + i] * inv_b) % d;
		rx[deg_b + i] = 0;
		for(int j = deg_b + i - 1; j >= i; j--)
			rx[j] -= qx[i] * b[j - i];	

	}
	
}

/****************************
多项式求逆元
数组a用来记录多项式逆元
*****************************/
int poly_inv_poly(int a[], int b[],  int d)
{

	int deg_b = deg(b,N);
	
	int (*q)[349] = new int[(349 + 2)][349];
	int (*r)[349] = new int[(349 + 2)][349];
	int (*s)[349] = new int[(349 + 2)][349];
	int (*t)[349] = new int[(349 + 2)][349];

	for(int j = 0;j<(349+2);j++)
	{
		memset(q[j],0,349*sizeof(int));
		memset(r[j],0,349*sizeof(int));
		memset(s[j],0,349*sizeof(int));
		memset(t[j],0,349*sizeof(int));
	}

	s[0][0] = 1;
	t[1][0] = 1;

	int inv_b = int_inv_int(d, b[deg_b]);


	for(int j = 0; j < deg_b; j++) {
		r[0][N-1-j] = -inv_b * b[deg_b - 1-j];
		r[0][N-1-j] %= d; 
	}
	r[0][0] -= 1;
	r[0][0] %= d;
	q[2][N-deg_b] = inv_b; 


	for(int i = 0;i<N;i++)
		r[1][i] = b[i];
	

	int i = 2;
	for(; i < (349+2); i++) {
	
		poly_mod_div_poly(r[i-2], r[i-1], r[i], q[i],d);
		for(int j=0;j<N;j++)
		{ 
			r[i][j] %= d;
			q[i][j] %= d;
		}

		int deg_r = deg(r[i],N);

		if(deg_r < 0) {
			return 0;
		}
		else if(deg_r ==0){
			break;
		}
	}

	for(int k = 2; k <= i; k++) {
		int *temp1 = new int [349]();
		int *temp2 = new int [349]();

		poly_mod_mul_poly(q[k], s[k - 1],temp1,d);
		poly_mod_mul_poly(q[k], t[k - 1],temp2,d);

		poly_mod_sub_poly( s[k - 2], temp1, s[k], d);
		poly_mod_sub_poly(t[k - 2], temp2, t[k], d);


	}

	int inv_r =  int_inv_int(d,r[i][0]);
	
	for(int k = 0; k < N; k++) {
		a[k] = (t[i][k]  * inv_r) % d;
		if(a[k] > d/2)
			a[k] -= d;
		if(a[k] < -d/2)
			a[k] += d;
	}

	return 1;
}

//使用公钥h1、h2来加密明文m,得到密文c1,c2
void new_Enc(int m[], int h1[], int h2[], int c1[], int c2[])
{

	/**********************产生工作密钥r1********************/
	int* r1_SubScript = new int[dr1];
	int* r1 = new int[N]();
	int* r2 = new int[N]();
	srand(unsigned(time(NULL)));
	for (int i = 0; i<dr1; i++)
	{		
		r1_SubScript[i] = rand() % N;
		for (int j = 0; j<i; j++)//去重
		{
			if (r1_SubScript[i] == r1_SubScript[j])
			{
				r1_SubScript[i] = rand() % N;
				j = -1;//将会执行j++, 从而是由0号开始比较
			}
		}
	}
	for (int i = 0; i<d1; i++)
	{
		r1[r1_SubScript[i]] = 1;//SetCoeff(r1, r1_SubScript[i]);
	}
	for (int i = d1; i<dr1; i++)
	{
		r1[r1_SubScript[i]] = -1;//SetCoeff(r1, r1_SubScript[i],-1);
	}
	/**********************产生工作密钥r2*************************/
	srand(unsigned(time(NULL)));
	for (int i = 0; i<N; i++)
	{		
		r2[i] = rand() % 3 - 1;//SetCoeff(r2,i,rand()%3-1);
	}	

	i32 eva_r1 = evaluate1(r1, N);
	printf("evaluate r1: %d\n", eva_r1);
	i32 eva_r2 = evaluate1(r2, N);
	printf("evaluate r2: %d\n", eva_r2);

	/*****************加密得到c1 = (r1*h1 + r2)(mod q1,mod x^N-1)************ ******/
	shifMul_Add1_Modp(c1, r1, h1, r2, q1, half_q1);

	/*******************加密得到c2 = (r1*h2 + r2 + M)(mod q2,mod x^N-1)********* ********/
	shifMul_Add2_Modp(c2, r1, h2, r2, m, q2, half_q2);

	delete[] r1_SubScript;
	delete[] r1;
	delete[] r2;
}

/***********************使解密c1,c2得到明文decrypt_m****************************/ 
void new_Dec(int c1[], int c2[], int f[], int fp[], int gsk[], int h2[], int decrypt_m[])
{
	int* s = new int[N]();
	shiftMulModp(s, f, c1, q1, half_q1);//计算s=f*c1(mod q1,mod(x^N-1))

	int* r2 = new int[N]();
	shiftMulModp(r2, fp, s, p, half_p);//恢复工作密钥r2=s*fp(mod p,mod(x^N-1))

	int* f_r2 = new int[N]();
	shiftMulMod(f_r2, f, r2);//计算f_r2=f*r2(mod (x^N-1))

	int* temp1 = new int[N]();
	intSub(temp1, s, f_r2);//计算temp1 = s - f_r2
	int* r1 = new int[N]();
	cyclicConvolutionMulModp(r1, temp1, gsk, q1, half_q1);//恢复工作密钥r1=(gsk*(s-f*r2))(modq1,mod(x^N-1))

	int* h2_r1 = new int[N]();
	shiftMulMod(h2_r1, r1, h2);
	int* temp2 = new int[N]();
	intSub(temp2, c2, h2_r1);//计算temp2 = c2 - h2_r1 = c2 - h2*r1(mod(x^N-1))
							 //int decrypt_m[N] = {0};
	intSub(decrypt_m, temp2, r2);//计算decrypt_m = temp2 -r2 = c2 - h2*r1 - r2
	for (int i = 0; i<N; i++)
	{
		decrypt_m[i] = decrypt_m[i] % q2;
		if (decrypt_m[i ]> half_q2) {
			decrypt_m[i] = decrypt_m[i] - q2;
		}
		else if (decrypt_m[i] < -half_q2) {
			decrypt_m[i] = decrypt_m[i] + q2;
		}
	}
	delete[] s;
	delete[] r2;
	delete[] f_r2;
	delete[] temp1;
	delete[] r1;
	delete[] h2_r1;
	delete[] temp2;
}

void SetData(byte type)
{
	if (type == 1)//安全参数k=120时的各个系统参数
	{
		N = 157;
		p = 3;
		q1 = 269;
		q2 = 271;
		df1 = 105;
		dg1 = 105;
		d1 = 53;
		dr1 = 106;
		half_p = p / 2;
		half_q1 = q1 / 2;
		half_q2 = q2 / 2;
		MM = 158;//明文空间需要的字节数
	}
	else if (type == 2)//安全参数k=172时的各个系统参数
	{
		N = 223;
		p = 3;
		q1 = 269;
		q2 = 271;
		df1 = 149;
		dg1 = 149;
		d1 = 75;
		dr1 = 150;
		half_p = p / 2;
		half_q1 = q1 / 2;
		half_q2 = q2 / 2;
		MM = 225;//明文空间需要的字节数
	}
	else if (type == 3)//安全参数k=270时的各个系统参数
	{
		N = 349;
		p = 3;
		q1 = 521;
		q2 = 523;
		df1 = 223;// <> 2d1-1
		dg1 = 223;// <> 2d1-1
		d1 = 117; // 1s in r1
		dr1 =224;//<> 2d1// total in r1, dr1-d1 = -1s in rq
		half_p = p / 2;
		half_q1 = q1 / 2;
		half_q2 = q2 / 2;
		MM = 393;//明文空间需要的字节数
	}
}

int pke_keygen(unsigned char *pk, unsigned char *sk)
{
	if(pk == nullptr || sk == nullptr)
		return 0;
	get_sk();
	get_pk();
	int* f = new int[N]();
	int* fp = new int[N]();
	int* gq1 = new int[N]();
	int* h1 = new int[N]();
	int* h2 = new int[N]();

	ifstream fingq1("F:\\coding\\d-ntru\\gq1.txt");
	for (int i = 0; i < N; i++) 
	{
		fingq1 >> gq1[i];
		if(gq1[i] < 0)
			gq1[i] += q1;
		
		//gq1保存为三位的unsigned char
		if(gq1[i] >= 510)
		{
			sk[3 * i] = 255;
			sk[3 * i + 1] = 255;
			sk[3 * i + 2 ] = gq1[i] - 510;
		}
		else if(gq1[i] < 510 && gq1[i] >= 255)
		{
			sk[3 * i] = 255;
			sk[3 * i + 1] = gq1[i] - 255;
			sk[3 * i + 2] = 0;
		}
		else if(gq1[i] < 255 && gq1[i] >= 0 )
		{
			sk[3 * i] = gq1[i];
			sk[3 * i + 1] = 0;
			sk[3 * i + 2] = 0;
		}
	}
	fingq1.close();

	ifstream fin_f("F:\\coding\\d-ntru\\f.txt");
	for(int i = 0;i < N;i++){
		fin_f >> f[i];
		sk[3 * N + i] = ++f[i];
	}
	fin_f.close();

	ifstream finfp("F:\\coding\\d-ntru\\fp.txt");
	for (int i = 0; i<N; i++) {
		finfp >> fp[i];
		sk[4 * N + i] = ++fp[i];
	}
	finfp.close();

	ifstream finh1("F:\\coding\\d-ntru\\h1.txt");
	for(int i = 0;i < N;i++){
		finh1 >> h1[i];
		if(h1[i] < 0)
			h1[i] += q1;
		//h1保存为三位的unsigned char
		if(h1[i] >= 510)
		{
			pk[3 * i] = 255;
			pk[3 * i + 1] = 255;
			pk[3 * i + 2] = h1[i] - 510;
		}
		else if(h1[i] < 510 && h1[i] >= 255)
		{
			pk[3 * i] = 255;
			pk[3 * i + 1] = h1[i] - 255;
			pk[3 * i + 2] = 0;
		}
		else if(h1[i] < 255 && h1[i] >= 0 )
		{
			pk[3 * i] = h1[i];
			pk[3 * i + 1] = 0;
			pk[3 * i + 2] = 0;
		}
	}
	finh1.close();

	
	ifstream finh2("F:\\coding\\d-ntru\\h2.txt");
	for(int i = 0;i < N;i++){
		finh2 >> h2[i];
		if(h2[i] < 0)
			h2[i] += q2;
		//h2保存为后三位的unsigned char
		if(h2[i] >= 510)
		{
			pk[3 * N + 3 * i] = 255;
			pk[3 * N + 3 * i + 1] = 255;
			pk[3 * N + 3 * i + 2] = h2[i] - 510;
		}
		else if(h2[i] < 510 && h2[i] >= 255)
		{
			pk[3 * N + 3 * i] = 255;
			pk[3 * N + 3 * i + 1] = h2[i] - 255;
			pk[3 * N + 3 * i + 2] = 0;
		}
		else if(h2[i] < 255 && h2[i] >= 0 )
		{
			pk[3 * N + 3 * i] = h2[i];
			pk[3 * N + 3 * i + 1] = 0;
			pk[3 * N + 3 * i + 2] = 0;
		}
	}
	finh2.close();

	delete[] f;
	delete[] fp;
	delete[] gq1;
	delete[] h1;
	delete[] h2;
	return 1;
}


int INDCPAgame(i32 * m, i32 * h1, i32 * h2, i32 * c1, i32 * c2) {
	i32 eva_r1 = d1 - (dr1 - d1);
	printf("evaluate r1 shoule be %d.\n", eva_r1);
	i32 eva_h1 = centered_modulo(evaluate1(h1,N), q1);
	i32 eva_h2 = centered_modulo(evaluate1(h2,N), q2);

	i32 eva_c1 = centered_modulo(evaluate1(c1, N), q1);
	i32 eva_c2 = centered_modulo(evaluate1(c2, N), q2);
	printf("evaluate cipher c1 mod q1 : %d\n", eva_c1);
	printf("evaluate cipher c2 mod q2 : %d\n", eva_c2);
	i32 eva_m = centered_modulo(evaluate1(m, N),q2);
	printf("evaluate plaintext m mod q2: %d\n", eva_m);

	i32 evar2_c1 = centered_modulo(eva_c1 - eva_h1 * eva_r1, q1);
	i32 evar2_c2 = centered_modulo(eva_c2 - eva_m - eva_h2 * eva_r1, q2);
	printf("evaluate r2 shoule be (c1 - h1*r1) mod q1 : %d\n", evar2_c1);
	printf("evaluate r2 shoule be (c2 - h2*r1 - m) mod q2 : %d\n", evar2_c2);
	if (evar2_c1 == evar2_c2) {
		return 0;
	}
	else {
		return 1;
	}
}
int pke_enc(unsigned char *pk, unsigned char *m, unsigned long long mlen, unsigned char *c, unsigned long long *clen )
{
	
	int* mm = new int[N]();
	int* h1 = new int[N]();
	int* h2 = new int[N]();
	int* c1 = new int[N]();
	int* c2 = new int[N]();

	for(int i = 0;i < N;i++)
	{
		mm[i] = m[3 * i] + m[3 * i + 1] + m[3 * i + 2];
		if(mm[i] > half_q2)
			mm[i] -= q2;
		h1[i] = pk[3 * i] + pk[3 * i + 1] + pk[3 * i+ 2];
		if(h1[i] > half_q1)
			h1[i] -= q1;		
	}
	for(int i = 0;i < N;i++)
	{
		h2[i] = pk[3 * N + 3 * i] + pk[3 * N + 3 * i + 1] + pk[3 * N + 3 * i+ 2];
		if(h2[i] > half_q2)
			h2[i] -= q2;		
	}
//	i32 eva_m = evaluate1(mm, N);
//	printf("evaluate message: %d\n", eva_m);
	
	new_Enc(mm, h1, h2, c1, c2);//得到c1,c2
	if (INDCPAgame(mm, h1, h2, c1, c2)==0) {
		printf("is not IND-CPA!\n");
	}
	else {
		printf("attack failed!\n");
	}
/*
	i32 eva_c1 = evaluate1(c1, N);
	i32 eva_c2 = evaluate1(c2, N);

	printf("evaluate cipher c1,c2: %d, %d\n",eva_c1,eva_c2 );
	printf("evaluate cipher c1 mod q1 : %d\n", centered_modulo(eva_c1,q1));
	printf("evaluate cipher c2 mod q2 : %d\n", centered_modulo(eva_c2, q2));

	printf("evaluate cipher (c2 - m) mod q2 : %d\n", centered_modulo(eva_c2 - eva_m,q2));

//	printf("C2==C1+M ?? : %d\n", eva_c2-eva_c1-eva_m);
*/
	//输出c1到c中
	for(int i = 0;i < N;i++)
	{
		if(c1[i] < 0)
			c1[i] += q1;
		if(c1[i] >= 510)
		{
			c[3 * i] = 255;
			c[3 * i + 1] = 255;
			c[3 *i + 2] = c1[i] - 510;
		}
		else if(c1[i] < 510 && c1[i] >= 255)
		{
			c[3 * i] = 255;
			c[3 * i + 1] = c1[i] - 255;
			c[3 * i + 2] = 0;
		}
		else if(c1[i] < 255 && c1[i] >= 0 )
		{
			c[3 * i] = c1[i];
			c[3 * i + 1] = 0;
			c[3 * i + 2] = 0;
		}
	}

	//输出c2到c中
	for(int i = 0;i < N;i++)
	{
		if(c2[i] < 0)
			c2[i] += q2;
		if(c2[i] >= 510)
		{
			c[3 * N + 3 * i] = 255;
			c[3 * N + 3 * i + 1] = 255;
			c[3 * N + 3 * i + 2] = c2[i] - 510;
		}
		else if(c2[i] < 510 && c2[i] >= 255)
		{
			c[3 * N + 3 * i] = 255;
			c[3 * N + 3 * i + 1] = c2[i] - 255;
			c[3 * N + 3 * i + 2] = 0;
		}
		else if(c2[i] < 255 && c2[i] >= 0 )
		{
			c[3 * N + 3 * i] = c2[i];
			c[3 * N + 3 * i + 1] = 0;
			c[3 * N + 3 * i + 2] = 0;
		}
	}

	*clen = 6 * N;
	delete[] mm;
	delete[] h1;
	delete[] h2;
	delete[] c1;
	delete[] c2;
	return 1;
}

int pke_dec(unsigned char *sk, unsigned char *c, unsigned long long clen, unsigned char *m, unsigned long long *mlen )
{
	int* c1 = new int[N]();
	int* c2 = new int[N]();
	int* f = new int[N]();
	int* fp = new int[N]();
	int* gsk = new int[N]();
	int* h2 = new int[N]();
	int* decrypt_m = new int[N]();

	ifstream fingsk("F:\\coding\\d-ntru\\gsk.txt");
	for (int i = 0; i < N; i++)
	{
		fingsk >> gsk[i];
	}	
	fingsk.close();

	ifstream finh2("F:\\coding\\d-ntru\\h2.txt");
	for (int i = 0; i < N; i++)
	{
		finh2 >> h2[i];
	}	
	finh2.close();


	//获取私钥f
	for (int i = 0; i < N; i++)
	{
		f[i] = (int)sk[3 * N + i] - 1;
	}	

	//获取私钥fp
	for (int i = 0; i < N; i++)
	{
		fp[i] = (int)sk[4 * N + i] - 1;
	}

	//获取c1
	for(int i = 0;i < N;i++)
	{
		c1[i] = c[3 * i] + c[3 * i + 1] + c[3 * i+ 2];
		if(c1[i] > half_q1)
			c1[i] -= q1;
	}

	//获取c2
	for(int i = 0;i < N;i++)
	{
		c2[i] = c[3 * N + 3 * i] + c[3 * N + 3 * i + 1] + c[3 * N + 3 * i+ 2];
		if(c2[i] > half_q2)
			c2[i] -= q2;
	}

	new_Dec(c1, c2, f, fp, gsk, h2, decrypt_m);
	
	cout << endl;
	//cout << "解密结果为:"<<endl;
	for(int i = 0;i < N;i++)
	{
		if(decrypt_m[i] < 0)
			decrypt_m[i] += q2;
		if(decrypt_m[i] > half_q2)
			decrypt_m[i] -= q2;

		//cout << decrypt_m[i]<<" ";

		if(decrypt_m[i] >= 510)
		{
			m[3 * i] = 255; 
			m[3 * i + 1] = 255;
			m[3 * i + 2] = decrypt_m[i] - 510;
		}
		else if(decrypt_m[i] < 510 && decrypt_m[i] >= 255)
		{
			m[3 * i] = 255;
			m[3 * i + 1] = decrypt_m[i] - 255;
			m[3 * i + 2] = 0;
		}
		else if(decrypt_m[i] < 255 && decrypt_m[i] >= 0 )
		{
			m[3 * i] = decrypt_m[i];
			m[3 * i + 1] = 0;
			m[3 * i + 2] = 0;
		}
	}

	*mlen = 3 * N;

	delete[] c1;
	delete[] c2;
	delete[] f;
	delete[] fp;
	delete[] gsk;
	delete[] h2;
	delete[] decrypt_m;

	return 1;
}

int main()
{
	clock_t Enc_Begin_Time,Enc_End_Time,Dec_Begin_Time,Dec_End_Time;
	int Enctime,Dectime;
	char datatype;
	for (datatype = 1; datatype <= 3; datatype++) {

		SetData(datatype);
		unsigned char* pk = new unsigned char[6 * N]();
		unsigned char* sk = new unsigned char[5 * N]();
		unsigned char* c = new unsigned char[6 * N]();
		unsigned char* decrypt_m = new unsigned char[3 * N]();
		unsigned char* m = new unsigned char[3 * N]();
		unsigned long long clen = 0;
		unsigned long long decrypt_len = 0;
		int mlen = N;

		pke_keygen(pk, sk);

		//cout << "初始明文m为：" << endl;
		for (int i = 0; i < N; i++)
		{
			srand(time(NULL) + i);
			int rd = rand() % q2;
			if (rd >= 510)
			{
				m[3 * i] = 255;
				m[3 * i + 1] = 255;
				m[3 * i + 2] = rd - 510;
			}
			else if (rd < 510 && rd >= 255)
			{
				m[3 * i] = 255;
				m[3 * i + 1] = rd - 255;
				m[3 * i + 2] = 0;
			}
			else if (rd < 255 && rd >= 0)
			{
				m[3 * i] = rd;
				m[3 * i + 1] = 0;
				m[3 * i + 2] = 0;
			}

			if (rd > half_q2)
				rd -= q2;
		//	cout << rd << " ";
		}
		//cout << endl << endl;

		int times = 1;
		while (times <= 1)
		{

			Enc_Begin_Time = clock();
			pke_enc(pk, m, mlen, c, &clen);
			Enc_End_Time = clock();
			Enctime = Enc_End_Time - Enc_Begin_Time;
			Enc_Sum_Time += Enctime;


			Dec_Begin_Time = clock();
			pke_dec(sk, c, clen, decrypt_m, &decrypt_len);
			Dec_End_Time = clock();
			Dectime = Dec_End_Time - Dec_Begin_Time;
			Dec_Sum_Time += Dectime;
			times++;

		}

		/*cout << "解密结果为：" << endl;
		for(int i = 0; i< 3 * N;i++)
			cout << (int)decrypt_m[i] << " ";
		cout << endl << endl;*/
		/*
		cout << endl;
		cout << "密文长度为：" << clen * times << "字节" << endl;
		cout << "解密得到的明文长度为：" << decrypt_len * times << "字节" << endl;

		cout << "加密时间为：" << Enc_Sum_Time << "ms" << endl;
		cout << "解密时间为：" << Dec_Sum_Time << "ms" << endl;
		*/
		delete[] c;
		delete[] decrypt_m;
		delete[] m;
		delete[] pk;
		delete[] sk;
		//cout << "hello world!";
	}
	return 0;
}