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

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

void HashMsg(const unsigned char *msg, unsigned long long mlen, unsigned char buf[32])
{
    sha256_t hash;
	sha256_init(&hash);
	sha256_update(&hash, msg, mlen);
	sha256_update(&hash, msg, mlen);
	sha256_final(&hash, buf);
}

void KAZ_DS_OrderBase(mpz_t Modular,
                      mpz_t FiModular,
                      mpz_t Base,
                      mpz_t OrderBase)
{
    mpz_t tmp, G1;
    mpz_inits(tmp, G1, NULL);

    int nFiModular=KAZ_DS_GET_PFactors(FiModular);

    mpz_t *pFactors=malloc(nFiModular*sizeof(mpz_t));
    int *q=malloc(nFiModular*sizeof(int));
    int *e=malloc(nFiModular*sizeof(int));
    int *esimpan=malloc(nFiModular*sizeof(int));

    for(int i=0; i<nFiModular; i++) mpz_init(pFactors[i]);
    for(int i=0; i<nFiModular; i++) q[i]=0;
    for(int i=0; i<nFiModular; i++) e[i]=0;
    for(int i=0; i<nFiModular; i++) esimpan[i]=0;

    KAZ_DS_PFactors(FiModular, pFactors, q, e);

    for(int j=0; j<nFiModular; j++){
        for(int i=1; i<=e[j]; i++){
            mpz_set_ui(tmp, q[j]);
            mpz_pow_ui(tmp, tmp, i);
            mpz_divexact(tmp, FiModular, tmp);
            mpz_powm(tmp, Base, tmp, Modular);

            if(mpz_cmp_ui(tmp, 1)!=0){
                esimpan[j]=i-1;
                break;
            }
        }
    }

    mpz_set_ui(G1, 1);
    for(int j=0; j<nFiModular; j++){
        mpz_set_ui(tmp, q[j]);
        mpz_pow_ui(tmp, tmp, esimpan[j]);
        mpz_mul(G1, G1, tmp);
    }

    mpz_divexact(OrderBase, FiModular, G1);
}

void KAZ_DS_CRT(mpz_t ord,
                mpz_t *pfactors,
                mpz_t *candidatex,
                int nof,
                mpz_t crt)
{
    mpz_t tmp;
    mpz_init(tmp);

    mpz_t *b=malloc(nof*sizeof(mpz_t));
    mpz_t *binv=malloc(nof*sizeof(mpz_t));

    for(int i=0; i<nof; i++) mpz_init(b[i]);
    for(int i=0; i<nof; i++) mpz_init(binv[i]);
    for(int i=0; i<nof; i++) mpz_divexact(b[i], ord, pfactors[i]);
    for(int i=0; i<nof; i++){
        mpz_set(tmp, pfactors[i]);
        mpz_invert(binv[i], b[i], tmp);
    }

    mpz_set_ui(crt, 0);

    for(int i=0; i<nof; i++){
        mpz_set(tmp, candidatex[i]);
        mpz_mul(tmp, tmp, b[i]);
        mpz_mul(tmp, tmp, binv[i]);
        mpz_mod(tmp, tmp, ord);
        mpz_add(crt, crt, tmp);
        mpz_mod(crt, crt, ord);
    }
}

int KAZ_DS_GET_PFactors(mpz_t input)
{
    mpz_t inp, prod;
    mpz_inits(inp, prod, NULL);
    mpz_set(inp, input);
    mpz_set_ui(prod, 1);

    int div=2, count=0;
    int i=0;

    while(mpz_cmp_ui(inp, 1)>0){
        while(mpz_divisible_ui_p(inp, div)>0){
            count++;
            mpz_divexact_ui(inp, inp, div);
            mpz_mul_ui(prod, prod, div);
        }

        if(mpz_cmp_ui(prod, 1)>0){
            i++;
        }
        mpz_set_ui(prod, 1);
        div++;
        count=0;
    }

    return i;
}

void KAZ_DS_PFactors(mpz_t ord,
                     mpz_t *pfacs,
                     int *qlist,
                     int *elist)
{
    mpz_t inp, prod;
    mpz_inits(inp, prod, NULL);
    mpz_set(inp, ord);
    mpz_set_ui(prod, 1);

    int div=2, count=0;
    unsigned long long i=0;

    while(mpz_cmp_ui(inp, 1)>0){
        while(mpz_divisible_ui_p(inp, div)>0){
            count++;
            mpz_divexact_ui(inp, inp, div);
            mpz_mul_ui(prod, prod, div);
        }

        if(mpz_cmp_ui(prod, 1)>0){

            mpz_set(pfacs[i], prod);
            qlist[i]=div;
            elist[i]=count;
            i++;
        }
        mpz_set_ui(prod, 1);
        div++;
        count=0;
    }

    mpz_clear(inp);
}

char* KAZ_DS_MLOG(mpz_t n,
                 mpz_t ord,
                 mpz_t g,
                 mpz_t h,
                 mpz_t *pfactors,
                 int *qlist,
                 int *elist,
                 int saiz,
                 mpz_t kaz_crt)
{
    mpz_t tmp, tmp2, exp, G, H, j, delta, alpha, beta;
    mpz_inits(tmp, tmp2, exp, G, H, j, delta, alpha, beta, NULL);

    unsigned long kk=0;
    mpz_set_ui(kaz_crt, 0);

    int SAIZ=saiz;

    mpz_t *candidateX=malloc(SAIZ*sizeof(mpz_t));
    for(int i=0; i<SAIZ; i++) mpz_init(candidateX[i]);
    for(int i=0; i<SAIZ; i++) mpz_set_ui(candidateX[i], 0);
    for(int i=SAIZ-1; i>=0; i--){
        mpz_set_ui(delta, 1);
        kk=0;
        mpz_t *l=malloc(elist[i]*sizeof(mpz_t));

        for(int ii=0; ii<elist[i]; ii++) mpz_init(l[ii]);
        for(int j=1; j<=elist[i]; j++){
            mpz_divexact_ui(tmp, ord, qlist[i]);
            mpz_powm(alpha, g, tmp, n);

            if(elist[i]==1){
                mpz_powm(beta, h, tmp, n);
                mpz_t k, limits;
                mpz_inits(k, limits, NULL);
                mpz_set_ui(k, 0);
                mpz_set_ui(limits, qlist[i]);
                mpz_pow_ui(limits, limits, j);
                mpz_sub_ui(limits, limits, 1);

                while(mpz_cmp(k, limits)<1){
                    mpz_t tmp3; mpz_init(tmp3);
                    mpz_powm(tmp3, alpha, k, n);

                    if(mpz_cmp(tmp3, beta)==0){
                        break;
                    }
                    if(mpz_cmp(k, limits)>=0){
                        return "FAIL";
                    }
                    mpz_add_ui(k, k, 1);
                }

                mpz_set(candidateX[i], k);
            }else{
                mpz_t tmp5;
                mpz_init(tmp5);

                mpz_set_ui(tmp, qlist[i]);
                mpz_pow_ui(tmp, tmp, j); //q[i]^j
                mpz_divexact(tmp, ord, tmp); //n/q[i]^j
                mpz_powm(beta, h, tmp, n);
                mpz_neg(tmp, tmp);
                mpz_powm(tmp5, delta, tmp, n);
                mpz_mul(beta, beta, tmp5);
                mpz_mod(beta, beta, n);

                mpz_t k, limits;
                mpz_inits(k, limits, NULL);

                mpz_set_ui(k, 0);
                mpz_set_ui(limits, qlist[i]);
                mpz_pow_ui(limits, limits, j);
                mpz_sub_ui(limits, limits, 1);

                while(mpz_cmp(k, limits)<1){
                    mpz_t tmp3; mpz_init(tmp3);
                    mpz_powm(tmp3, alpha, k, n);

                    if(mpz_cmp(tmp3, beta)==0){
                        break;
                    }
                    if(mpz_cmp(k, limits)>=0){
                        return "FAIL";
                    }
                    mpz_add_ui(k, k, 1);
                }

                mpz_set(l[kk], k);

                mpz_t pwr, tmp4, tmp6;
                mpz_inits(pwr, tmp4, tmp6, NULL);

                mpz_set_ui(pwr, qlist[i]);
                mpz_pow_ui(pwr, pwr, (j-1));
                mpz_mul(pwr, l[kk], pwr);
                mpz_powm(tmp4, g, pwr, n);
                mpz_mul(delta, delta, tmp4);
                mpz_mod(delta, delta, n);
                mpz_add(candidateX[i], candidateX[i], pwr);
                kk++;
            }
        }

        mpz_mod(candidateX[i], candidateX[i], pfactors[i]);
    }

    int k = SAIZ;
    KAZ_DS_CRT(ord, pfactors, candidateX, k, kaz_crt);
}

void KAZ_DS_KeyGen(unsigned char *kaz_ds_verify_key,
                   unsigned char *kaz_ds_sign_key)
{
    mpz_t N, g, Gg, R, GRg, ALPHA, V1, V2, V3;
    mpz_inits(N, g, Gg, R, GRg, ALPHA, V1, V2, V3, NULL);

    //1) Get all system parameters
    mpz_set_str(N, KAZ_DS_SP_N, 10);
    mpz_set_str(g, KAZ_DS_SP_G, 10);
    mpz_set_str(Gg, KAZ_DS_SP_ORDERG, 10);
    mpz_set_str(R, KAZ_DS_SP_R, 10);
    mpz_set_str(GRg, KAZ_DS_SP_GRg, 10);

    int ss=KAZ_DS_SP_SECURITY;
    int nphiGg=KAZ_DS_SP_LENPHIORDERG;

    //2) Generate ALPHA & (V1, V2, V3)
    KAZ_DS_RANDOM(nphiGg-2, nphiGg-1, ALPHA);
    mpz_mod(V1, ALPHA, GRg);

    int nGRg=KAZ_DS_GET_PFactors(GRg);

    mpz_t *pFactors=malloc(nGRg*sizeof(mpz_t));
    int *qz=malloc(nGRg*sizeof(int));
    int *ez=malloc(nGRg*sizeof(int));

    for(int i=0; i<nGRg; i++) mpz_init(pFactors[i]);
    for(int i=0; i<nGRg; i++) qz[i]=0;
    for(int i=0; i<nGRg; i++) ez[i]=0;

    KAZ_DS_PFactors(GRg, pFactors, qz, ez);

    KAZ_DS_RANDOM(ss, ss+1, V2);
    mpz_nextprime(V2, V2);
    mpz_mul_ui(V2, V2, qz[nGRg-1]);
    mpz_mod(V3, ALPHA, V2);

    //3) Set kaz_ds_sign_key=(ALPHA, V2) & kaz_ds_verify_key=(V1, V2, V3)
    size_t ALPHASIZE=mpz_sizeinbase(ALPHA, 16);
	size_t V1SIZE=mpz_sizeinbase(V1, 16);
	size_t V2SIZE=mpz_sizeinbase(V2, 16);
	size_t V3SIZE=mpz_sizeinbase(V3, 16);

	unsigned char *ALPHABYTE=(unsigned char*) malloc(ALPHASIZE*sizeof(unsigned char));
	mpz_export(ALPHABYTE, &ALPHASIZE, 1, sizeof(char), 0, 0, ALPHA);

	unsigned char *V1BYTE=(unsigned char*) malloc(V1SIZE*sizeof(unsigned char));
	mpz_export(V1BYTE, &V1SIZE, 1, sizeof(char), 0, 0, V1);

	unsigned char *V2BYTE=(unsigned char*) malloc(V2SIZE*sizeof(unsigned char));
	mpz_export(V2BYTE, &V2SIZE, 1, sizeof(char), 0, 0, V2);

	unsigned char *V3BYTE=(unsigned char*) malloc(V3SIZE*sizeof(unsigned char));
	mpz_export(V3BYTE, &V3SIZE, 1, sizeof(char), 0, 0, V3);

	for(int i=0; i<CRYPTO_SECRETKEYBYTES; i++) kaz_ds_sign_key[i]=0;

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

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

	je=CRYPTO_SECRETKEYBYTES-KAZ_DS_V3BYTES-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_V3BYTES-KAZ_DS_V2BYTES-KAZ_DS_V1BYTES-1;
	for(int i=ALPHASIZE-1; i>=0; i--){
		kaz_ds_sign_key[je]=ALPHABYTE[i];
		je--;
	}

	/*for(int i=0; i<CRYPTO_SECRETKEYBYTES; i++) printf("%d ", kaz_ds_sign_key[i]);
	printf("\n");
	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=ALPHASIZE-1; i>=0; i--){
		kaz_ds_sign_key[je]=ALPHABYTE[i];
		je--;
	}*/

	for(int i=0; i<CRYPTO_PUBLICKEYBYTES; i++) kaz_ds_verify_key[i]=0;

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

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

	je=CRYPTO_PUBLICKEYBYTES-KAZ_DS_V3BYTES-KAZ_DS_V2BYTES-1;
	for(int i=V1SIZE-1; i>=0; i--){
		kaz_ds_verify_key[je]=V1BYTE[i];
		je--;
	}

    //gmp_printf("ALPHA=%Zd\nV1=%Zd\nV2=%Zd\n", ALPHA, V1,V2);
    //gmp_printf("ALPHA=%Zd\nV1=%Zd\nV2=%Zd\nV3=%Zd\n", ALPHA, V1, V2, V3);
	mpz_clears(N, g, Gg, R, GRg, ALPHA, V1, V2, V3, NULL);
}

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 N, g, Gg, R, GRg, ALPHA, V1, V2, V3, r, GRgV2, tmp, S1, S2, S3, rF, rho, w4, w5, w6, hashValue;
    mpz_inits(N, g, Gg, R, GRg, ALPHA, V1, V2, V3, r, GRgV2, tmp, S1, S2, S3, rF, rho, w4, w5, w6, hashValue, NULL);

    //1) Get all system parameters
    mpz_set_str(N, KAZ_DS_SP_N, 10);
    mpz_set_str(g, KAZ_DS_SP_G, 10);
    mpz_set_str(Gg, KAZ_DS_SP_ORDERG, 10);
    mpz_set_str(R, KAZ_DS_SP_R, 10);
    mpz_set_str(GRg, KAZ_DS_SP_GRg, 10);

    int ss=KAZ_DS_SP_SECURITY;
    int nphiGg=KAZ_DS_SP_LENPHIORDERG;

    //2) Get kaz_ds_sign_key=(ALPHA, V2)
    int ALPHASIZE=0;
	for(int i=0; i<KAZ_DS_ALPHABYTES; i++){
        if((int)sk[i]==0) ALPHASIZE++;
        else break;
	}

	int V1SIZE=0;
	for(int i=KAZ_DS_ALPHABYTES; i<CRYPTO_SECRETKEYBYTES-KAZ_DS_V3BYTES-KAZ_DS_V2BYTES; i++){
        if((int)sk[i]==0) V1SIZE++;
        else break;
	}

	int V2SIZE=0;
	for(int i=KAZ_DS_ALPHABYTES+KAZ_DS_V1BYTES; i<CRYPTO_SECRETKEYBYTES-KAZ_DS_V3BYTES; i++){
        if((int)sk[i]==0) V2SIZE++;
        else break;
	}

	int V3SIZE=0;
	for(int i=KAZ_DS_ALPHABYTES+KAZ_DS_V1BYTES+KAZ_DS_V2BYTES; i<CRYPTO_SECRETKEYBYTES; i++){
        if((int)sk[i]==0) V3SIZE++;
        else break;
	}

	unsigned char *ALPHABYTE=(unsigned char*) malloc((KAZ_DS_ALPHABYTES-ALPHASIZE)*sizeof(unsigned char));
	unsigned char *V1BYTE=(unsigned char*) malloc((KAZ_DS_V1BYTES-V1SIZE)*sizeof(unsigned char));
	unsigned char *V2BYTE=(unsigned char*) malloc((KAZ_DS_V2BYTES-V2SIZE)*sizeof(unsigned char));
	unsigned char *V3BYTE=(unsigned char*) malloc((KAZ_DS_V3BYTES-V3SIZE)*sizeof(unsigned char));

	for(int i=0; i<KAZ_DS_ALPHABYTES-ALPHASIZE; i++) ALPHABYTE[i]=0;
	for(int i=0; i<KAZ_DS_V1BYTES-V1SIZE; i++) V1BYTE[i]=0;
	for(int i=0; i<KAZ_DS_V2BYTES-V2SIZE; i++) V2BYTE[i]=0;
	for(int i=0; i<KAZ_DS_V3BYTES-V3SIZE; i++) V3BYTE[i]=0;

	for(int i=0; i<KAZ_DS_ALPHABYTES-ALPHASIZE; i++){ALPHABYTE[i]=sk[i+ALPHASIZE];}
	for(int i=0; i<KAZ_DS_V1BYTES-V1SIZE; i++){V1BYTE[i]=sk[i+(KAZ_DS_ALPHABYTES+V1SIZE)];}
	for(int i=0; i<KAZ_DS_V2BYTES-V2SIZE; i++){V2BYTE[i]=sk[i+(KAZ_DS_ALPHABYTES+KAZ_DS_V1BYTES+V2SIZE)];}
	for(int i=0; i<KAZ_DS_V3BYTES-V3SIZE; i++){V3BYTE[i]=sk[i+(KAZ_DS_ALPHABYTES+KAZ_DS_V1BYTES+KAZ_DS_V2BYTES+V3SIZE)];}

    mpz_import(ALPHA, KAZ_DS_ALPHABYTES-ALPHASIZE, 1, sizeof(char), 0, 0, ALPHABYTE);
    mpz_import(V1, KAZ_DS_V1BYTES-V1SIZE, 1, sizeof(char), 0, 0, V1BYTE);
	mpz_import(V2, KAZ_DS_V2BYTES-V2SIZE, 1, sizeof(char), 0, 0, V2BYTE);
	mpz_import(V3, KAZ_DS_V3BYTES-V3SIZE, 1, sizeof(char), 0, 0, V3BYTE);

	//gmp_printf("ALPHA=%Zd\nV1=%Zd\nV2=%Zd\nV3=%Zd\n", ALPHA, V1, V2, V3);

	//3) Generate the hash value of the message
	unsigned char buf[CRYPTO_BYTES]={0};
    HashMsg(m, mlen, buf);

    mpz_import(hashValue, CRYPTO_BYTES, 1, sizeof(char), 0, 0, buf);

    //4) Generate S1, S2, S3
    do{
        KAZ_DS_RANDOM(nphiGg-2, nphiGg-1, r);
        mpz_nextprime(r, r);

        mpz_mod(tmp, r, GRg);
        mpz_powm(S1, R, tmp, Gg);

        mpz_mod(S3, r, V2);

        mpz_mul(GRgV2, GRg, V2);
        mpz_powm(S2, ALPHA, S3, GRgV2);
        mpz_add(S2, S2, hashValue);
        mpz_mod(S2, S2, GRgV2);
        mpz_invert(tmp, r, GRgV2);
        mpz_mul(S2, S2, tmp);
        mpz_mod(S2, S2, GRgV2);

        int nGRg=KAZ_DS_GET_PFactors(GRg);

        mpz_t *pFactors=malloc(nGRg*sizeof(mpz_t));
        int *qz=malloc(nGRg*sizeof(int));
        int *ez=malloc(nGRg*sizeof(int));

        for(int i=0; i<nGRg; i++) mpz_init(pFactors[i]);
        for(int i=0; i<nGRg; i++) qz[i]=0;
        for(int i=0; i<nGRg; i++) ez[i]=0;

        KAZ_DS_PFactors(GRg, pFactors, qz, ez);
        KAZ_DS_MLOG(Gg, GRg, R, S1, pFactors, qz, ez, nGRg, rF);

        mpz_divexact_ui(rho, V2, qz[nGRg-1]);
        mpz_powm(w4, V3, S3, rho);
        mpz_add(w4, w4, hashValue);
        mpz_mod(w4, w4, rho);
        mpz_invert(tmp, S3, rho);
        mpz_mul(w4, w4, tmp);
        mpz_mod(w4, w4, rho);

        mpz_powm(w5, V1, S3, GRg);
        mpz_add(w5, w5, hashValue);
        mpz_mod(w5, w5, GRg);
        mpz_invert(tmp, rF, GRg);
        mpz_mul(w5, w5, tmp);
        mpz_mod(w5, w5, GRg);

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

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

        mpz_set(modulus[0], rho);
        mpz_set(modulus[1], GRg);
        mpz_set(candidate[0], w4);
        mpz_set(candidate[1], w5);

        mpz_mul(tmp, GRg, rho);
        KAZ_DS_CRT(tmp, modulus, candidate, 2, w6);
    }while(mpz_cmp(w6, S2)==0);

    //gmp_printf("S1=%Zd\nS2=%Zd\nS3=%Zd\nh=%Zd\n", S1, S2, S3, hashValue);

    //5) Set signature=(S1, S2)
    size_t S1SIZE=mpz_sizeinbase(S1, 16);
	size_t S2SIZE=mpz_sizeinbase(S2, 16);
	size_t S3SIZE=mpz_sizeinbase(S3, 16);

    for(int i=0; i<mlen+KAZ_DS_S1BYTES+KAZ_DS_S2BYTES+KAZ_DS_S3BYTES; i++) signature[i]=0;

	unsigned char *S1BYTE=(unsigned char*) malloc(S1SIZE*sizeof(unsigned char));
	mpz_export(S1BYTE, &S1SIZE, 1, sizeof(char), 0, 0, S1);

	unsigned char *S2BYTE=(unsigned char*) malloc(S2SIZE*sizeof(unsigned char));
	mpz_export(S2BYTE, &S2SIZE, 1, sizeof(char), 0, 0, S2);

	unsigned char *S3BYTE=(unsigned char*) malloc(S3SIZE*sizeof(unsigned char));
	mpz_export(S3BYTE, &S3SIZE, 1, sizeof(char), 0, 0, S3);

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

	je=KAZ_DS_S3BYTES+KAZ_DS_S2BYTES+KAZ_DS_S1BYTES-1;
	for(int i=S3SIZE-1; i>=0; i--){
		signature[je]=S3BYTE[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=S1SIZE-1; i>=0; i--){
		signature[je]=S1BYTE[i];
		je--;
	}

	*signlen=mlen+KAZ_DS_S1BYTES+KAZ_DS_S2BYTES+KAZ_DS_S3BYTES;

    free(S1BYTE);
    free(S2BYTE);
    free(S3BYTE);

	mpz_clears(N, g, Gg, R, GRg, ALPHA, V1, V2, V3, r, GRgV2, tmp, S1, S2, S3, rF, rho, w4, w5, w6, hashValue, NULL);

    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 N, g, Gg, R, GRg, tmp, V1, V2, V3, S1, S2, S3, hashValue, w0, w1, w2, w3, w4, w5, w6, rho, z0, z1, y1, y2, rF;
    mpz_inits(N, g, Gg, R, GRg, tmp, V1, V2, V3, S1, S2, S3, hashValue, w0, w1, w2, w3, w4, w5, w6, rho, z0, z1, y1, y2, rF, NULL);

    //1) Get all system parameters
    mpz_set_str(N, KAZ_DS_SP_N, 10);
    mpz_set_str(g, KAZ_DS_SP_G, 10);
    mpz_set_str(Gg, KAZ_DS_SP_ORDERG, 10);
    mpz_set_str(R, KAZ_DS_SP_R, 10);
    mpz_set_str(GRg, KAZ_DS_SP_GRg, 10);

    int ss=KAZ_DS_SP_SECURITY;
    int nphiGg=KAZ_DS_SP_LENPHIORDERG;

    //2) Get kaz_ds_verify_key=(V1, V2, V3)
	int V1SIZE=0;
	for(int i=0; i<KAZ_DS_V1BYTES; i++){
        if((int)pk[i]==0) V1SIZE++;
        else break;
	}

	int V2SIZE=0;
	for(int i=KAZ_DS_V1BYTES; i<CRYPTO_PUBLICKEYBYTES-KAZ_DS_V3BYTES; i++){
        if((int)pk[i]==0) V2SIZE++;
        else break;
	}

	int V3SIZE=0;
	for(int i=KAZ_DS_V1BYTES+KAZ_DS_V2BYTES; i<CRYPTO_PUBLICKEYBYTES; i++){
        if((int)pk[i]==0) V3SIZE++;
        else break;
	}

	unsigned char *V1BYTE=(unsigned char*) malloc((KAZ_DS_V1BYTES-V1SIZE)*sizeof(unsigned char));
	unsigned char *V2BYTE=(unsigned char*) malloc((KAZ_DS_V2BYTES-V2SIZE)*sizeof(unsigned char));
	unsigned char *V3BYTE=(unsigned char*) malloc((KAZ_DS_V3BYTES-V3SIZE)*sizeof(unsigned char));

	for(int i=0; i<KAZ_DS_V1BYTES-V1SIZE; i++) V1BYTE[i]=0;
	for(int i=0; i<KAZ_DS_V2BYTES-V2SIZE; i++) V2BYTE[i]=0;
	for(int i=0; i<KAZ_DS_V3BYTES-V3SIZE; i++) V3BYTE[i]=0;

	for(int i=0; i<KAZ_DS_V1BYTES-V1SIZE; i++){V1BYTE[i]=pk[i+V1SIZE];}
	for(int i=0; i<KAZ_DS_V2BYTES-V2SIZE; i++){V2BYTE[i]=pk[i+KAZ_DS_V1BYTES+V2SIZE];}
	for(int i=0; i<KAZ_DS_V3BYTES-V3SIZE; i++){V3BYTE[i]=pk[i+KAZ_DS_V1BYTES+KAZ_DS_V2BYTES+V3SIZE];}

	mpz_import(V1, KAZ_DS_V1BYTES-V1SIZE, 1, sizeof(char), 0, 0, V1BYTE);
	mpz_import(V2, KAZ_DS_V2BYTES-V2SIZE, 1, sizeof(char), 0, 0, V2BYTE);
	mpz_import(V3, KAZ_DS_V3BYTES-V3SIZE, 1, sizeof(char), 0, 0, V3BYTE);

	//gmp_printf("V1=%Zd\nV2=%Zd\nV3=%Zd\n", V1, V2, V3);

    //3) Get signature=(S1, S2, S3, m)
    int S1SIZE=0;
	for(int i=0; i<KAZ_DS_S1BYTES; i++){
        if((int)sm[i]==0) S1SIZE++;
        else break;
	}

	int S2SIZE=0;
	for(int i=KAZ_DS_S1BYTES; i<KAZ_DS_S1BYTES+KAZ_DS_S2BYTES; i++){
        if((int)sm[i]==0) S2SIZE++;
        else break;
	}

	int S3SIZE=0;
	for(int i=KAZ_DS_S1BYTES+KAZ_DS_S2BYTES; i<KAZ_DS_S1BYTES+KAZ_DS_S2BYTES+KAZ_DS_S3BYTES; i++){
        if((int)sm[i]==0) S3SIZE++;
        else break;
	}

	int MSIZE=0;
	for(int i=KAZ_DS_S1BYTES+KAZ_DS_S2BYTES+KAZ_DS_S3BYTES; i<smlen; i++){
        if((int)sm[i]==0) MSIZE++;
        else break;
	}

	unsigned char *S1BYTE=(unsigned char*) malloc((KAZ_DS_S1BYTES-S1SIZE)*sizeof(unsigned char));
	unsigned char *S2BYTE=(unsigned char*) malloc((KAZ_DS_S2BYTES-S2SIZE)*sizeof(unsigned char));
	unsigned char *S3BYTE=(unsigned char*) malloc((KAZ_DS_S3BYTES-S3SIZE)*sizeof(unsigned char));
	unsigned char *MBYTE=(unsigned char*) malloc((smlen-(KAZ_DS_S1BYTES+KAZ_DS_S2BYTES+KAZ_DS_S3BYTES)-MSIZE)*sizeof(unsigned char));

	for(int i=0; i<KAZ_DS_S1BYTES-S1SIZE; i++) S1BYTE[i]=0;
	for(int i=0; i<KAZ_DS_S2BYTES-S2SIZE; i++) S2BYTE[i]=0;
	for(int i=0; i<KAZ_DS_S3BYTES-S3SIZE; i++) S3BYTE[i]=0;
	for(int i=0; i<smlen-(KAZ_DS_S1BYTES+KAZ_DS_S2BYTES+KAZ_DS_S3BYTES)-MSIZE; i++) MBYTE[i]=0;

	for(int i=0; i<KAZ_DS_S1BYTES-S1SIZE; i++){S1BYTE[i]=sm[i+S1SIZE];}
	for(int i=0; i<KAZ_DS_S2BYTES-S2SIZE; i++){S2BYTE[i]=sm[i+(KAZ_DS_S1BYTES+S2SIZE)];}
	for(int i=0; i<KAZ_DS_S3BYTES-S3SIZE; i++){S3BYTE[i]=sm[i+(KAZ_DS_S1BYTES+KAZ_DS_S2BYTES+S3SIZE)];}
	for(int i=0; i<smlen-(KAZ_DS_S1BYTES+KAZ_DS_S2BYTES+KAZ_DS_S3BYTES)-MSIZE; i++){MBYTE[i]=sm[i+(KAZ_DS_S1BYTES+KAZ_DS_S2BYTES+KAZ_DS_S3BYTES+MSIZE)];}

    mpz_import(S1, KAZ_DS_S1BYTES-S1SIZE, 1, sizeof(char), 0, 0, S1BYTE);
	mpz_import(S2, KAZ_DS_S2BYTES-S2SIZE, 1, sizeof(char), 0, 0, S2BYTE);
	mpz_import(S3, KAZ_DS_S3BYTES-S3SIZE, 1, sizeof(char), 0, 0, S3BYTE);

	//4) Compute the hash value of the message
    unsigned char buf[CRYPTO_BYTES]={0}; int len=smlen-KAZ_DS_S1BYTES-KAZ_DS_S2BYTES-KAZ_DS_S3BYTES-MSIZE;
    HashMsg(MBYTE, len, buf);

    mpz_import(hashValue, CRYPTO_BYTES, 1, sizeof(char), 0, 0, buf);

    //gmp_printf("S1=%Zd\nS2=%Zd\nS3=%Zd\nh=%Zd\nSelesai\n\n", S1, S2, S3, hashValue);

    //5) Compute & check w0=w1
    mpz_mul(w0, S2, S3);
    mpz_mod(w0, w0, V2);
    mpz_sub(w0, w0, hashValue);
    mpz_mod(w0, w0, V2);

    mpz_powm(w1, V3, S3, V2);

    //gmp_printf("w0=%Zd\nw1=%Zd\n", w0, w1);

    if(mpz_cmp(w0, w1)!=0){printf("mpz_cmp(w0, w1)\n");
        return -4; //REJECT SIGNATURE
    }

    int nGRg=KAZ_DS_GET_PFactors(GRg);

    mpz_t *pFactors=malloc(nGRg*sizeof(mpz_t));
    int *qz=malloc(nGRg*sizeof(int));
    int *ez=malloc(nGRg*sizeof(int));

    for(int i=0; i<nGRg; i++) mpz_init(pFactors[i]);
    for(int i=0; i<nGRg; i++) qz[i]=0;
    for(int i=0; i<nGRg; i++) ez[i]=0;

    KAZ_DS_PFactors(GRg, pFactors, qz, ez);
    KAZ_DS_MLOG(Gg, GRg, R, S1, pFactors, qz, ez, nGRg, rF);

    mpz_divexact_ui(tmp, GRg, qz[nGRg-1]);
    mpz_mul(w2, tmp, S3);
    mpz_mod(w2, w2, GRg);

    mpz_mul(w3, tmp, rF);
    mpz_mod(w3, w3, GRg);

    if(mpz_cmp(w2, w3)!=0){printf("mpz_cmp(w2, w3)\n");
        return -4; //REJECT SIGNATURE
    }

    mpz_divexact_ui(rho, V2, qz[nGRg-1]);
    mpz_powm(w4, V3, S3, rho);
    mpz_add(w4, w4, hashValue);
    mpz_mod(w4, w4, rho);
    mpz_invert(tmp, S3, rho);
    mpz_mul(w4, w4, tmp);
    mpz_mod(w4, w4, rho);

    mpz_powm(w5, V1, S3, GRg);
    mpz_add(w5, w5, hashValue);
    mpz_mod(w5, w5, GRg);
    mpz_invert(tmp, rF, GRg);
    mpz_mul(w5, w5, tmp);
    mpz_mod(w5, w5, GRg);

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

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

    mpz_set(modulus[0], rho);
    mpz_set(modulus[1], GRg);
    mpz_set(candidate[0], w4);
    mpz_set(candidate[1], w5);

    mpz_mul(tmp, GRg, rho);
    KAZ_DS_CRT(tmp, modulus, candidate, 2, w6);

    if(mpz_cmp(w6, S2)==0){printf("mpz_cmp(w6, S2)\n");
        return -4; //REJECT SIGNATURE
    }

    mpz_powm(z0, R, hashValue, Gg);
    mpz_powm(tmp, V1, S3, GRg);
    mpz_powm(z1, R, tmp, Gg);

    mpz_powm(tmp, S1, S2, Gg);
	mpz_powm(y1, g, tmp, N);

	mpz_mul(tmp, z0, z1);
	mpz_powm(y2, g, tmp, N);

	if(mpz_cmp(y1, y2)==0){
        memcpy(m, MBYTE, len);
        *mlen=len;

        free(S1BYTE);
        free(S2BYTE);
        free(S3BYTE);
        free(MBYTE);

        mpz_clears(N, g, Gg, R, GRg, tmp, V1, V2, V3, S1, S2, S3, hashValue, w0, w1, w2, w3, w4, w5, w6, rho, z0, z1, y1, y2, rF, NULL);

        return 0;
	}

	/*gmp_printf("V1=%Zd\nV2=%Zd\nV3=%Zd\n", V1, V2, V3);
	gmp_printf("S1=%Zd\nS2=%Zd\nS3=%Zd\nh=%Zd\n", S1, S2, S3, hashValue);
	gmp_printf("w0=%Zd\nw1=%Zd\n", w0, w1);
	gmp_printf("y1=%Zd\ny2=%Zd\n\n", y1, y2);*/

	return -4;
}

void KAZ_DS_RANDOM(int lb,
                   int ub,
                   mpz_t out){
    ////time_t seed;
	//srand((unsigned) time(&seed));

	//mpz_t randNUM; mpz_init(randNUM);

	mpz_t lbound, ubound;

	gmp_randstate_t gmpRandState;
    gmp_randinit_mt(gmpRandState);
	mpz_inits(lbound, ubound, NULL);

	mpz_ui_pow_ui(lbound, 2, lb);
	mpz_ui_pow_ui(ubound, 2, ub);

	unsigned int sd=100000;

	do{
		// initialize state for a Mersenne Twister algorithm. This algorithm is fast and has good randomness properties.

		//gmp_randseed_ui(gmpRandState, sd);
		gmp_randseed_ui(gmpRandState, rand()+sd);
		mpz_urandomb(out, gmpRandState, ub);
		sd+=1;
	}while((mpz_cmp(out, lbound) == -1) || (mpz_cmp(out, ubound) == 1));

	// empty the memory location for the random generator state
    //gmp_randclear(gmpRandState);
}

/*void KAZ_DS_RANDOM(int lb,
                   int ub,
                   mpz_t out){
    time_t seed;
	srand((unsigned) time(&seed));

	mpz_t randNUM; mpz_init(randNUM);

	mpz_t lbound, ubound;

	gmp_randstate_t gmpRandState;

	mpz_inits(lbound, ubound, NULL);

	mpz_ui_pow_ui(lbound, 2, lb);
	mpz_ui_pow_ui(ubound, 2, ub);

	do{
		// initialize state for a Mersenne Twister algorithm. This algorithm is fast and has good randomness properties.
		gmp_randinit_mt(gmpRandState);
		gmp_randseed_ui(gmpRandState, rand());
		mpz_urandomb(out, gmpRandState, ub);
	}while((mpz_cmp(out, lbound) == -1) || (mpz_cmp(out, ubound) == 1));

	// empty the memory location for the random generator state
    gmp_randclear(gmpRandState);
}*/
