#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <openssl/evp.h>

#include "rng.h"
#include "api.h"
#include "gmp.h"
#include "kaz_api.h"

void HashMsg(const unsigned char *msg, unsigned int mlen, unsigned char buf[CRYPTO_BYTES])
{
    // Initialize the digest context and compute the hash
	EVP_MD_CTX *mdctx = EVP_MD_CTX_new();
    const EVP_MD *md = EVP_sha256();

    EVP_DigestInit_ex(mdctx, md, NULL);
    EVP_DigestUpdate(mdctx, msg, mlen);
    EVP_DigestFinal_ex(mdctx, buf, &mlen);

    // Clean up
    EVP_MD_CTX_free(mdctx);
}

void KAZ_DS_CRT(int size, mpz_t *x, mpz_t *modulus, mpz_t crt)
{
    mpz_t *c=malloc(size*sizeof(mpz_t));
    mpz_t u, prod;

    mpz_inits(u, prod, NULL);
    for(int i=0; i<size; i++) mpz_init(c[i]);

    mpz_set_ui(c[0], 0);

    for(int i=1; i<size; i++){
        mpz_set_ui(c[i], 1);

        for(int j=0; j<=i-1; j++){
            mpz_invert(u, modulus[j], modulus[i]);
            mpz_mul(c[i], c[i], u);
            mpz_mod(c[i], c[i], modulus[i]);
        }
    }

    mpz_set(u, x[0]);
    mpz_set(crt, u);

    for(int i=1; i<size; i++){
        mpz_sub(u, x[i], crt);
        mpz_mul(u, u, c[i]);
        mpz_mod(u, u, modulus[i]);
        mpz_set_ui(prod, 1);

        for(int j=0; j<=i-1; j++) mpz_mul(prod, prod, modulus[j]);

        mpz_mul(u, u, prod);
        mpz_add(crt, crt, u);
    }

    for(int i=0; i<size; i++) mpz_clear(c[i]);
	free(c);
	mpz_set_ui(u, 0);
	mpz_set_ui(prod, 0);
    mpz_clears(u, prod, NULL);
}

void KAZ_DS_KEYGEN(unsigned char *kaz_ds_verify_key, unsigned char *kaz_ds_sign_key)
{
    mpz_t G1, G1RHO, phiG1RHO, phiphiG1RHO, q, Q, phiQ, qQ, G1qQRHO, G1RHOQ, A, GV1, G1A;
    mpz_t a, b, ALPHA, OMEGA1, V1, V2, SK, SKG1Q, tmp;

    mpz_inits(G1, G1RHO, phiG1RHO, phiphiG1RHO, q, Q, phiQ, qQ, G1qQRHO, G1RHOQ, A, GV1, G1A, NULL);
    mpz_inits(a, b, ALPHA, OMEGA1, V1, V2, SK, SKG1Q, tmp, NULL);

    //Get all system parameters and precomputed parameters
    mpz_set_str(G1, KAZ_DS_SP_G1, 10);
    mpz_set_str(q, KAZ_DS_SP_q, 10);
    mpz_set_str(Q, KAZ_DS_SP_Q, 10);
	mpz_set_str(A, KAZ_DS_SP_A, 10);
	
	mpz_set_str(G1RHO, KAZ_DS_SP_G1RHO, 10);
	mpz_set_str(G1RHOQ, KAZ_DS_SP_G1QRHO, 10);
	mpz_set_str(G1qQRHO, KAZ_DS_SP_G1qQRHO, 10);
	mpz_set_str(phiG1RHO, KAZ_DS_SP_PHIG1RHO, 10);
	mpz_set_str(phiphiG1RHO, KAZ_DS_SP_PHIPHIG1RHO, 10);
	mpz_set_str(phiQ, KAZ_DS_SP_PHIQ, 10);
	mpz_set_str(qQ, KAZ_DS_SP_qQ, 10);

	int k=KAZ_DS_SP_K;
	int LG1=KAZ_DS_SP_LG1RHO;
	
	unsigned char RAN[200];
	unsigned char *SKBYTE=NULL;
	unsigned char *V1BYTE=NULL;
	unsigned char *V2BYTE=NULL;
	
	//1) Generate random prime a,  random OMEGA1
	randombytes(RAN, KAZ_DS_SP_RAN);
	mpz_import(a, KAZ_DS_SP_RAN, 1, sizeof(char), 0, 0, RAN);	
	mpz_nextprime(a, a);

	randombytes(RAN, KAZ_DS_SP_RAN);
	mpz_import(OMEGA1, KAZ_DS_SP_RAN, 1, sizeof(char), 0, 0, RAN);
	
	//2) Compute b
	mpz_mul(tmp, OMEGA1, phiG1RHO);
	mpz_powm(b, a, phiphiG1RHO, tmp);
	
	mpz_divexact(G1A, G1, A);
	
	do{	
		//3) Generate random ALPHA	
		randombytes(RAN, (k+LG1)/8);
		mpz_import(ALPHA, (k+LG1)/8, 1, sizeof(char), 0, 0, RAN);
		mpz_mul_ui(ALPHA, ALPHA, 2);

		//4) Compute V1
		mpz_mod(V1, ALPHA, G1RHO);
		
		//5) Compute V2
		mpz_mul(tmp, phiQ, b);
		mpz_powm(V2, ALPHA, tmp, qQ);
		mpz_mul(V2, V2, Q);
		mpz_mod(V2, V2, qQ);

		//6) Compute Secret Signing SK
		mpz_powm(SK, ALPHA, tmp, G1qQRHO);
		
		mpz_mod(SKG1Q, SK, G1RHOQ);
		// Compute GCD(V1, G1/A)
		mpz_gcd(GV1, V1, G1A);
	}while(mpz_cmp_ui(SKG1Q,0)==0 || mpz_cmp_ui(GV1, 1)!=0);

    //6) Set kaz_ds_sign_key=(SK) & kaz_ds_verify_key=(V1, V2)
    size_t SKSIZE=mpz_sizeinbase(SK, 16);
	size_t V1SIZE=mpz_sizeinbase(V1, 16);
	size_t V2SIZE=mpz_sizeinbase(V2, 16);
	
	// Avoid zero-sized allocations
    if (SKSIZE == 0) SKSIZE = 1;
    if (V1SIZE == 0) V1SIZE = 1;
    if (V2SIZE == 0) V2SIZE = 1;

	SKBYTE=(unsigned char*) malloc(SKSIZE*sizeof(unsigned char));
	V1BYTE=(unsigned char*) malloc(V1SIZE*sizeof(unsigned char));
	V2BYTE=(unsigned char*) malloc(V2SIZE*sizeof(unsigned char));
	
	if (!SKBYTE || !V1BYTE || !V2BYTE) {
        fprintf(stderr, "KAZ-SIGN-KEYGEN: Memory allocation failed.\n");
		printf("KAZ-SIGN-KEYGEN: Memory allocation failed.\n");
		goto cleanup;
    }
	
	mpz_export(SKBYTE, &SKSIZE, 1, sizeof(char), 0, 0, SK);
	mpz_export(V1BYTE, &V1SIZE, 1, sizeof(char), 0, 0, V1);
	mpz_export(V2BYTE, &V2SIZE, 1, sizeof(char), 0, 0, V2);
	
	// Clear output keys
    memset(kaz_ds_sign_key, 0, CRYPTO_SECRETKEYBYTES);
    memset(kaz_ds_verify_key, 0, CRYPTO_PUBLICKEYBYTES);
	
	//for(int i=0; i<CRYPTO_SECRETKEYBYTES; i++) kaz_ds_sign_key[i]=0;
	//for(int i=0; i<CRYPTO_PUBLICKEYBYTES; i++) kaz_ds_verify_key[i]=0;

	int je=CRYPTO_SECRETKEYBYTES-1;
	
	for(int i=V2SIZE-1; i>=0; i--){
		kaz_ds_sign_key[je]=V2BYTE[i];
		je--;
	}

	je=CRYPTO_SECRETKEYBYTES-KAZ_DS_V2BYTES-1;
	for(int i=V1SIZE-1; i>=0; i--){
		kaz_ds_sign_key[je]=V1BYTE[i];
		je--;
	}
	
	je=CRYPTO_SECRETKEYBYTES-KAZ_DS_V2BYTES-KAZ_DS_V1BYTES-1;
	
	for(int i=SKSIZE-1; i>=0; i--){
		kaz_ds_sign_key[je]=SKBYTE[i];
		je--;
	}

	je=CRYPTO_PUBLICKEYBYTES-1;
	for(int i=V2SIZE-1; i>=0; i--){
		kaz_ds_verify_key[je]=V2BYTE[i];
		je--;
	}

	je=CRYPTO_PUBLICKEYBYTES-KAZ_DS_V2BYTES-1;
	for(int i=V1SIZE-1; i>=0; i--){
		kaz_ds_verify_key[je]=V1BYTE[i];
		je--;
	}
	
	cleanup:
		mpz_set_ui(G1, 0);mpz_set_ui(G1RHO, 0);mpz_set_ui(phiG1RHO, 0);mpz_set_ui(phiphiG1RHO, 0);mpz_set_ui(q, 0);mpz_set_ui(Q, 0);
		mpz_set_ui(phiQ, 0);mpz_set_ui(qQ, 0);mpz_set_ui(G1qQRHO, 0);mpz_set_ui(G1RHOQ, 0);mpz_set_ui(A, 0);mpz_set_ui(GV1, 0);mpz_set_ui(G1A, 0);
		mpz_set_ui(a, 0);mpz_set_ui(b, 0);mpz_set_ui(ALPHA, 0);mpz_set_ui(OMEGA1, 0);mpz_set_ui(V1, 0);mpz_set_ui(V2, 0);
		mpz_set_ui(SKG1Q, 0);mpz_set_ui(SK, 0);mpz_set_ui(tmp, 0);
		
		mpz_clears(G1, G1RHO, phiG1RHO, phiphiG1RHO, q, Q, phiQ, qQ, G1qQRHO, G1RHOQ, A, GV1, G1A, NULL);
		mpz_clears(a, b, ALPHA, OMEGA1, V1, V2, SKG1Q, SK, tmp, NULL);
		memset(RAN, 0, 200);

		if (SKBYTE) {
			memset(SKBYTE, 0, SKSIZE);
			free(SKBYTE);
		}
		if (V1BYTE) {
			memset(V1BYTE, 0, V1SIZE);
			free(V1BYTE);
		}
		if (V2BYTE) {
			memset(V2BYTE, 0, V2SIZE);
			free(V2BYTE);
		}
}

int KAZ_DS_SIGNATURE(unsigned char *signature, unsigned long long *signlen, const unsigned char *m, unsigned long long mlen, const unsigned char *sk)
{
    mpz_t G1RHO, phiG1RHO, phiphiG1RHO, q, Q, qQ, phiqQ, G1qQRHO, G1QRHO, phiQ, V1, V2, SK;
    mpz_t hashValue, r1, OMEGA2, BETA, r2, OMEGA3, BETA2, S1, S2, tmp, W2, Y1, SF1;

    mpz_inits(G1RHO, phiG1RHO, phiphiG1RHO, q, Q, qQ, phiqQ, G1qQRHO, G1QRHO, phiQ, V1, V2, SK, NULL);
    mpz_inits(hashValue, r1, OMEGA2, BETA, r2, OMEGA3, BETA2, S1, S2, tmp, W2, Y1, SF1, NULL);
	
    // Get all system parameters and precomputed parameters
	mpz_set_str(G1RHO, KAZ_DS_SP_G1RHO, 10);
	mpz_set_str(q, KAZ_DS_SP_q, 10);
	mpz_set_str(Q, KAZ_DS_SP_Q, 10);

	mpz_set_str(G1qQRHO, KAZ_DS_SP_G1qQRHO, 10);
	mpz_set_str(phiG1RHO, KAZ_DS_SP_PHIG1RHO, 10);
	mpz_set_str(phiphiG1RHO, KAZ_DS_SP_PHIPHIG1RHO, 10);
	mpz_set_str(qQ, KAZ_DS_SP_qQ, 10);
	mpz_set_str(phiqQ, KAZ_DS_SP_PHIqQ, 10);
	mpz_set_str(G1QRHO, KAZ_DS_SP_G1QRHO, 10);
	mpz_set_str(phiQ, KAZ_DS_SP_PHIQ, 10);

    //1) Get kaz_ds_sign_key=(SK)
	unsigned char *V1BYTE=NULL;
	unsigned char *V2BYTE=NULL;
	unsigned char *SKBYTE=NULL;
	unsigned char *SBYTE=NULL;
	unsigned char *S2BYTE=NULL;
	
	V1BYTE=(unsigned char*) malloc((KAZ_DS_V1BYTES)*sizeof(unsigned char));
	V2BYTE=(unsigned char*) malloc((KAZ_DS_V2BYTES)*sizeof(unsigned char));
	SKBYTE=(unsigned char*) malloc((KAZ_DS_SKBYTES)*sizeof(unsigned char));
	
	if (!SKBYTE || !V1BYTE || !V2BYTE) {
        fprintf(stderr, "KAZ-SIGN-SIGNATURE: Memory allocation failed.\n");
		printf("KAZ-SIGN-SIGNATURE: Memory allocation failed.\n");
		goto cleanup;
    }

	//for(int i=0; i<KAZ_DS_V1BYTES; i++) V1BYTE[i]=0;
	//for(int i=0; i<KAZ_DS_V2BYTES; i++) V2BYTE[i]=0;
	//for(int i=0; i<KAZ_DS_SKBYTES; i++) SKBYTE[i]=0;
	
	// Clear output keys
    memset(V1BYTE, 0, KAZ_DS_V1BYTES);
    memset(V2BYTE, 0, KAZ_DS_V2BYTES);
	memset(SKBYTE, 0, KAZ_DS_SKBYTES);
	
	for(int i=0; i<KAZ_DS_SKBYTES; i++){SKBYTE[i]=sk[i];}
	for(int i=0; i<KAZ_DS_V1BYTES; i++){V1BYTE[i]=sk[i+KAZ_DS_SKBYTES];}
	for(int i=0; i<KAZ_DS_V2BYTES; i++){V2BYTE[i]=sk[i+KAZ_DS_SKBYTES+KAZ_DS_V1BYTES];}
	
	mpz_import(V1, KAZ_DS_V1BYTES, 1, sizeof(char), 0, 0, V1BYTE);
	mpz_import(V2, KAZ_DS_V2BYTES, 1, sizeof(char), 0, 0, V2BYTE);
	mpz_import(SK, KAZ_DS_SKBYTES, 1, sizeof(char), 0, 0, SKBYTE);

	//2) Compute HASHValue(m)
	unsigned char buf[CRYPTO_BYTES];
	HashMsg(m, mlen, buf);
	mpz_import(hashValue, CRYPTO_BYTES, 1, sizeof(char), 0, 0, buf);

	unsigned char RAN[200];
	int lenS=0, lenG1qQ=mpz_sizeinbase(G1qQRHO, 2);
	
	mpz_t *x=malloc(2*sizeof(mpz_t));
	mpz_t *modulus=malloc(2*sizeof(mpz_t));
	
	//3) Generate random prime r, random OMEGA2
	randombytes(RAN, KAZ_DS_SP_RAN);
	mpz_import(r1, KAZ_DS_SP_RAN, 1, sizeof(char), 0, 0, RAN);
	mpz_nextprime(r1, r1);

	randombytes(RAN, KAZ_DS_SP_RAN);
	mpz_import(OMEGA2, KAZ_DS_SP_RAN, 1, sizeof(char), 0, 0, RAN);

	//4) Compute BETA
	mpz_mul(tmp, OMEGA2, phiG1RHO);
	mpz_powm(BETA, r1, phiphiG1RHO, tmp);
	
	//5) Generate random prime r, random OMEGA2
	randombytes(RAN, KAZ_DS_SP_RAN);
	mpz_import(r2, KAZ_DS_SP_RAN, 1, sizeof(char), 0, 0, RAN);
	mpz_nextprime(r2, r2);

	randombytes(RAN, KAZ_DS_SP_RAN);
	mpz_import(OMEGA3, KAZ_DS_SP_RAN, 1, sizeof(char), 0, 0, RAN);

	//6) Compute BETA
	mpz_mul(tmp, OMEGA3, phiG1RHO);
	mpz_powm(BETA2, r2, phiphiG1RHO, tmp);
	
	// unsigned int S2=0;
	mpz_set_ui(S2, 0);
	
	while(true){	
		//7) Compute Signature
		mpz_mul(tmp, phiqQ, BETA);
		mpz_powm(S1, hashValue, tmp, G1qQRHO); //h^{phiqQ*beta}
		mpz_mul(tmp, phiqQ, BETA2);
		mpz_powm(tmp, hashValue, tmp, G1qQRHO);//h^{phiqQ*beta2}
		mpz_add(S1, S1, tmp); //h^{phiqQ*beta} + h^{phiqQ*beta2}
		mpz_mod(S1, S1, G1qQRHO);
		mpz_mul(S1, S1, SK);
		mpz_mod(S1, S1, G1qQRHO);
		
		lenS=mpz_sizeinbase(S1, 2);
		
		//FILTER 3
		mpz_powm(Y1, V1, phiQ, G1QRHO);
		mpz_powm(tmp, hashValue, phiqQ, G1QRHO);
		mpz_mul_ui(tmp, tmp, 2);
		mpz_mod(tmp, tmp, G1QRHO);
		mpz_mul(Y1, Y1, tmp);
		mpz_mod(Y1, Y1, G1QRHO);

		for(int i=0; i<2; i++) mpz_init(x[i]);
		for(int i=0; i<2; i++) mpz_init(modulus[i]);
	
		mpz_divexact(x[0], V2, Q);
		mpz_set(x[1], Y1);

		mpz_set(modulus[0], q);
		mpz_set(modulus[1], G1QRHO);

		KAZ_DS_CRT(2, x, modulus, SF1);
		
		//mpz_mod(tmp, S, G1qQ);
		mpz_sub(W2, S1, SF1);
		
		if(lenS==lenG1qQ && mpz_cmp(S1, SF1)!=0){
			//gmp_printf("S=%Zd\nSF1=%Zd\nW2=%Zd\n", S, SF1, W2);
			break;
		}
		else {
			// S2=S2+1;//printf("Salt = %d\n", salt);
			mpz_add_ui(S2, S2, 1);
			mpz_add_ui(hashValue, hashValue, 1);
		}
	}
		
    //6) Set signature=(S, m)
    size_t SSIZE=mpz_sizeinbase(S1, 16);
	size_t S2SIZE=mpz_sizeinbase(S2, 16);
	
	// Avoid zero-sized allocations
    if (SSIZE == 0) SSIZE = KAZ_DS_S1BYTES;
	if (S2SIZE == 0) S2SIZE = KAZ_DS_S2BYTES;
	
	SBYTE=(unsigned char*) malloc(SSIZE*sizeof(unsigned char));
	S2BYTE=(unsigned char*) malloc(S2SIZE*sizeof(unsigned char));
	
	memset(SBYTE, 0, KAZ_DS_S1BYTES);
	memset(S2BYTE, 0, KAZ_DS_S2BYTES);
	
	mpz_export(SBYTE, &SSIZE, 1, sizeof(char), 0, 0, S1);
	mpz_export(S2BYTE, &S2SIZE, 1, sizeof(char), 0, 0, S2);
	
	// Clear output signature
	memset(signature, 0, mlen+KAZ_DS_S2BYTES+KAZ_DS_S1BYTES);

	int je=mlen+KAZ_DS_S2BYTES+KAZ_DS_S1BYTES-1;
	for(int i=mlen-1; i>=0; i--){
		signature[je]=m[i];
		je--;
	}

	je=KAZ_DS_S2BYTES+KAZ_DS_S1BYTES-1;
	for(int i=S2SIZE-1; i>=0; i--){
		signature[je]=S2BYTE[i];
		je--;
	}
	
	je=KAZ_DS_S1BYTES-1;
	for(int i=SSIZE-1; i>=0; i--){
		signature[je]=SBYTE[i];
		je--;
	}

	*signlen=mlen+KAZ_DS_S2BYTES+KAZ_DS_S1BYTES;
	
	cleanup:
		for(int i=0; i<2; i++) mpz_clear(x[i]);
		for(int i=0; i<2; i++) mpz_clear(modulus[i]);
		free(x);
		free(modulus);
		
		mpz_set_ui(G1RHO, 0);mpz_set_ui(phiG1RHO, 0);mpz_set_ui(phiphiG1RHO, 0);mpz_set_ui(q, 0);mpz_set_ui(Q, 0);mpz_set_ui(SK, 0);
		mpz_set_ui(phiQ, 0);mpz_set_ui(qQ, 0);mpz_set_ui(G1qQRHO, 0);mpz_set_ui(G1QRHO, 0);mpz_set_ui(V1, 0);mpz_set_ui(V2, 0);
		mpz_set_ui(hashValue, 0);mpz_set_ui(r1, 0);mpz_set_ui(OMEGA2, 0);mpz_set_ui(BETA, 0);mpz_set_ui(r2, 0);mpz_set_ui(OMEGA3, 0);
		mpz_set_ui(BETA2, 0);mpz_set_ui(S1, 0);mpz_set_ui(tmp, 0);mpz_set_ui(W2, 0);mpz_set_ui(Y1, 0);mpz_set_ui(SF1, 0);
		
		mpz_clears(G1RHO, phiG1RHO, phiphiG1RHO, q, Q, qQ, phiqQ, G1qQRHO, G1QRHO, phiQ, V1, V2, SK, NULL);
		mpz_clears(hashValue, r1, OMEGA2, BETA, r2, OMEGA3, BETA2, S1, S2, tmp, W2, Y1, SF1, NULL);
		
		memset(RAN, 0, 200);
		memset(buf, 0, CRYPTO_BYTES);

		if (SKBYTE) {
			memset(SKBYTE, 0, KAZ_DS_SKBYTES);
			free(SKBYTE);
		}
		if (V1BYTE) {
			memset(V1BYTE, 0, KAZ_DS_V1BYTES);
			free(V1BYTE);
		}
		if (V2BYTE) {
			memset(V2BYTE, 0, KAZ_DS_V2BYTES);
			free(V2BYTE);
		}
		if (SBYTE) {
			memset(SBYTE, 0, KAZ_DS_S1BYTES);
			free(SBYTE);
		}
		if (S2BYTE) {
			memset(S2BYTE, 0, KAZ_DS_S2BYTES);
			free(S2BYTE);
		}

	return 0;
}

int KAZ_DS_VERIFICATION(unsigned char *m, unsigned long long *mlen, const unsigned char *sm, unsigned long long smlen, const unsigned char *pk)
{
    mpz_t G0, G1, R, G1RHO, q, Q, phiQ, G1QRHO, G1qQRHO, qQ, phiqQ, hashValue, V1, V2, S1, S2, A, G1A;
    mpz_t tmp, tmp2, SF1, SF2, e, W0, W2, W3, W4, W5, VQ, Y1, Y2, y1, y2, y3, y4;

    mpz_inits(G0, G1, R, G1RHO, q, Q, phiQ, G1QRHO, G1qQRHO, qQ, phiqQ, hashValue, V1, V2, S1, S2, A, G1A, NULL);
    mpz_inits(tmp, tmp2, SF1, SF2, e, W0, W2, W3, W4, W5, VQ, Y1, Y2, y1, y2, y3, y4, NULL);

    // Get all system parameters and precomputed parameters
    mpz_set_str(G0, KAZ_DS_SP_G0, 10);
	mpz_set_str(G1, KAZ_DS_SP_G1, 10);
    mpz_set_str(R, KAZ_DS_SP_R, 10);
    mpz_set_str(G1RHO, KAZ_DS_SP_G1RHO, 10);
    mpz_set_str(q, KAZ_DS_SP_q, 10);
    mpz_set_str(Q, KAZ_DS_SP_Q, 10);
	mpz_set_str(A, KAZ_DS_SP_A, 10);
    
	mpz_set_str(G1QRHO, KAZ_DS_SP_G1QRHO, 10);
	mpz_set_str(G1qQRHO, KAZ_DS_SP_G1qQRHO, 10);
	mpz_set_str(phiQ, KAZ_DS_SP_PHIQ, 10);
	mpz_set_str(qQ, KAZ_DS_SP_qQ, 10);
	mpz_set_str(phiqQ, KAZ_DS_SP_PHIqQ, 10);

	unsigned char *V1BYTE=NULL;
	unsigned char *V2BYTE=NULL;
	unsigned char *SBYTE=NULL;
	unsigned char *S2BYTE=NULL;
	unsigned char *MBYTE=NULL;
	
    //1) Get kaz_ds_verify_key=(V1, V2)
	V1BYTE=(unsigned char*) malloc((KAZ_DS_V1BYTES)*sizeof(unsigned char));
	V2BYTE=(unsigned char*) malloc((KAZ_DS_V2BYTES)*sizeof(unsigned char));

	//for(int i=0; i<KAZ_DS_V1BYTES; i++) V1BYTE[i]=0;
	//for(int i=0; i<KAZ_DS_V2BYTES; i++) V2BYTE[i]=0;
	
	if (!V1BYTE || !V2BYTE) {
        fprintf(stderr, "KAZ-SIGN-KEYGEN: Memory allocation failed.\n");
		printf("KAZ-SIGN-VERIFICATION: Memory allocation failed.\n");
		goto cleanup;
    }
	
	// Clear output keys
	memset(V1BYTE, 0, KAZ_DS_V1BYTES);
	memset(V2BYTE, 0, KAZ_DS_V2BYTES);

	for(int i=0; i<KAZ_DS_V1BYTES; i++){V1BYTE[i]=pk[i];}
	for(int i=0; i<KAZ_DS_V2BYTES; i++){V2BYTE[i]=pk[i+KAZ_DS_V1BYTES];}

	mpz_import(V1, KAZ_DS_V1BYTES, 1, sizeof(char), 0, 0, V1BYTE);
	mpz_import(V2, KAZ_DS_V2BYTES, 1, sizeof(char), 0, 0, V2BYTE);

    //2) Get signature=(S, m)
    int len=smlen-KAZ_DS_S2BYTES-KAZ_DS_S1BYTES;

    SBYTE=(unsigned char*) malloc((KAZ_DS_S1BYTES)*sizeof(unsigned char));
	S2BYTE=(unsigned char*) malloc((KAZ_DS_S2BYTES)*sizeof(unsigned char));
	MBYTE=(unsigned char*) malloc(len*sizeof(unsigned char));

	//for(int i=0; i<KAZ_DS_SBYTES-1; i++) SBYTE[i]=0;
	//for(int i=0; i<len; i++) MBYTE[i]=0;
	
	if (!SBYTE || !S2BYTE || !MBYTE) {
        fprintf(stderr, "KAZ-SIGN-VERIFICATION: Memory allocation failed.\n");
		printf("KAZ-SIGN-VERIFICATION: Memory allocation failed.\n");
		goto cleanup;
    }
	
	// Clear output signature
	memset(SBYTE, 0, KAZ_DS_S1BYTES);
	memset(S2BYTE, 0, KAZ_DS_S2BYTES);
	memset(MBYTE, 0, len);
   
	for(int i=0; i<KAZ_DS_S1BYTES; i++){SBYTE[i]=sm[i];}
	//unsigned int S2=(unsigned int)((sm[KAZ_DS_SBYTES-2]) << 8) | (sm[KAZ_DS_SBYTES-1]);
	for(int i=0; i<KAZ_DS_S2BYTES; i++){S2BYTE[i]=sm[i+KAZ_DS_S1BYTES];}
	for(int i=0; i<len; i++){MBYTE[i]=sm[i+KAZ_DS_S1BYTES+KAZ_DS_S2BYTES];}

    mpz_import(S1, KAZ_DS_S1BYTES, 1, sizeof(char), 0, 0, SBYTE);
	mpz_import(S2, KAZ_DS_S2BYTES, 1, sizeof(char), 0, 0, S2BYTE);
    
	//3) Compute the hash value of the message
    unsigned char buf[CRYPTO_BYTES]={0};
    HashMsg(MBYTE, len, buf);
    mpz_import(hashValue, CRYPTO_BYTES, 1, sizeof(char), 0, 0, buf);
	mpz_add(hashValue, hashValue, S2);

    //4) Filtering Procedures
	if(mpz_cmp_ui(S2, 65535)>0){
        printf("Filter 0...\n");
        return -4;
    }
	
    //FILTER 1
    mpz_mod(tmp, S1, G1qQRHO);
    mpz_sub(W0, tmp, S1);

    if(mpz_cmp_ui(W0, 0)!=0){
        printf("Filter 1...\n");
        return -4;
    }

	//FILTER 2
	int lenS=mpz_sizeinbase(S1, 2);
	int lenG1qQ=mpz_sizeinbase(G1qQRHO, 2);
	int W1=lenS-lenG1qQ;
	
	if(W1!=0){
        printf("Filter 2...\n");
        return -4;
    }
	
	//FILTER 3
	mpz_powm(Y1, V1, phiQ, G1QRHO);
	mpz_powm(tmp, hashValue, phiqQ, G1QRHO);
	mpz_mul_ui(tmp, tmp, 2);
	mpz_mod(tmp, tmp, G1QRHO);
	mpz_mul(Y1, Y1, tmp);
	mpz_mod(Y1, Y1, G1QRHO);

	mpz_t *x=malloc(2*sizeof(mpz_t));
    mpz_t *modulus=malloc(2*sizeof(mpz_t));

    for(int i=0; i<2; i++) mpz_init(x[i]);
	for(int i=0; i<2; i++) mpz_init(modulus[i]);

	mpz_divexact(x[0], V2, Q);
	mpz_set(x[1], Y1);

	mpz_set(modulus[0], q);
	mpz_set(modulus[1], G1QRHO);

	KAZ_DS_CRT(2, x, modulus, SF1);
	
	mpz_mod(tmp, S1, G1qQRHO);
    mpz_sub(W2, tmp, SF1);

    if(mpz_cmp_ui(W2, 0)==0){
        printf("Filter 3...\n");
        return -4;
    }
	
	//FILTER 4
	mpz_powm(Y2, V1, phiQ, G1RHO);
	mpz_powm(tmp, hashValue, phiqQ, G1RHO);
	mpz_mul_ui(tmp, tmp, 2);
	mpz_mod(tmp, tmp, G1RHO);
	mpz_mul(Y2, Y2, tmp);
	mpz_mod(Y2, Y2, G1RHO);

    for(int i=0; i<2; i++) mpz_init(x[i]);
	for(int i=0; i<2; i++) mpz_init(modulus[i]);

	mpz_divexact(x[0], V2, Q);
	mpz_set(x[1], Y2);
	
	mpz_gcd(e, Q, G1RHO);
	mpz_divexact(tmp, qQ, e);
	
	mpz_set(modulus[0], tmp);
	mpz_set(modulus[1], G1RHO);

	KAZ_DS_CRT(2, x, modulus, SF2);
	
	mpz_divexact(tmp2, G1qQRHO, e);
	mpz_mod(tmp, S1, tmp2);
    mpz_sub(W3, tmp, SF2);

    if(mpz_cmp_ui(W3, 0)==0){
        printf("Filter 4...\n");
        return -4;
    }

	//FILTER 5
    mpz_mul(W4, Q, S1);
	mpz_mod(W4, W4, qQ);
	mpz_mul_ui(W5, V2, 2);
	mpz_mod(W5, W5, qQ);
	mpz_sub(W5, W5, W4);

    if(mpz_cmp_ui(W5, 0)!=0){
        printf("Filter 5...\n");
        return -4;
    }

    //5) Verifying Procedures
	mpz_powm(y1, R, S1, G0);

    mpz_powm(y2, V1, phiQ, G1);
	mpz_powm(tmp, hashValue, phiqQ, G1);
	mpz_powm(tmp2, hashValue, phiqQ, G1);
	mpz_add(tmp, tmp, tmp2);
	mpz_mod(tmp, tmp, G1);
    mpz_mul(y2, y2, tmp);
    mpz_mod(y2, y2, G1);
	mpz_powm(y2, R, y2, G0);

    if(mpz_cmp(y1, y2)!=0){
		printf("Invalid...\n");
        return -4;
	}
	
	// BARU TAMBAH
	mpz_divexact(G1A, G1RHO, A);
	
	mpz_powm(tmp2, V1, phiQ, G1A);
	mpz_invert(tmp2, tmp2, G1A);
	mpz_mul(y3, S1, tmp2);
	mpz_mod(y3, y3, G1A);
	
	mpz_powm(y4, hashValue, phiqQ, G1A);
	mpz_mul_ui(y4, y4, 2);
	mpz_mod(y4, y4, G1A);
	
	if(mpz_cmp(y3, y4)!=0){
		return -4;
	}

    memcpy(m, MBYTE, len);
    *mlen=len;

	cleanup:
		for(int i=0; i<2; i++) mpz_clear(x[i]);
		for(int i=0; i<2; i++) mpz_clear(modulus[i]);
		free(x);
		free(modulus);
		
		mpz_set_ui(G0, 0);mpz_set_ui(R, 0);mpz_set_ui(G1RHO, 0);mpz_set_ui(q, 0);mpz_set_ui(Q, 0);mpz_set_ui(phiQ, 0);
		mpz_set_ui(G1QRHO, 0);mpz_set_ui(G1qQRHO, 0);mpz_set_ui(qQ, 0);mpz_set_ui(phiqQ, 0);mpz_set_ui(hashValue, 0);
		mpz_set_ui(V1, 0);mpz_set_ui(V2, 0);mpz_set_ui(S1, 0);mpz_set_ui(A, 0);mpz_set_ui(G1A, 0);
		mpz_set_ui(tmp, 0);mpz_set_ui(tmp2, 0);mpz_set_ui(SF1, 0);mpz_set_ui(SF2, 0);mpz_set_ui(e, 0);mpz_set_ui(W0, 0);mpz_set_ui(W2, 0);
		mpz_set_ui(W3, 0);mpz_set_ui(W4, 0);mpz_set_ui(W5, 0);mpz_set_ui(VQ, 0);mpz_set_ui(Y1, 0);mpz_set_ui(Y2, 0);mpz_set_ui(y1, 0);
		mpz_set_ui(y2, 0);mpz_set_ui(y3, 0);mpz_set_ui(y4, 0);
		
		mpz_clears(G0, G1, R, G1RHO, q, Q, phiQ, G1QRHO, G1qQRHO, qQ, phiqQ, hashValue, V1, V2, S1, S2, A, G1A, NULL);
		mpz_clears(tmp, tmp2, SF1, SF2, e, W0, W2, W3, W4, W5, VQ, Y1, Y2, y1, y2, y3, y4, NULL);
		
		memset(buf, 0, CRYPTO_BYTES);
		free(V1BYTE);
		free(V2BYTE);
		free(SBYTE);
		free(S2BYTE);
		free(MBYTE);

	return 0;
}