This is an automated email from the ASF dual-hosted git repository. sandreoli pushed a commit to branch issue73-new-paillier-trick in repository https://gitbox.apache.org/repos/asf/incubator-milagro-crypto-c.git
commit 5aed5931bba05f48ac4d0b28d83ace564b325e30 Author: Samuele Andreoli <[email protected]> AuthorDate: Sun Mar 8 18:21:29 2020 +0000 Use new trick in paillier ecnryption and keygen --- examples/example_paillier.c | 3 -- include/ff.h.in | 10 +++++ include/paillier.h | 4 +- src/ff.c.in | 10 ++++- src/paillier.c | 89 +++++++++++++++++----------------------- test/test_paillier_consistency.c | 3 +- test/test_paillier_encrypt.c | 11 ----- test/test_paillier_keygen.c | 16 +------- 8 files changed, 60 insertions(+), 86 deletions(-) diff --git a/examples/example_paillier.c b/examples/example_paillier.c index 4c57a39..98eebc6 100644 --- a/examples/example_paillier.c +++ b/examples/example_paillier.c @@ -107,9 +107,6 @@ int paillier(csprng *RNG) printf("N: "); FF_4096_output(PUB.n, HFLEN_4096); printf("\n"); - printf("G: "); - FF_4096_output(PUB.g, FFLEN_4096); - printf("\n"); printf("Secret Key \n"); printf("L_p: "); diff --git a/include/ff.h.in b/include/ff.h.in index 0bcf458..0384cc9 100644 --- a/include/ff.h.in +++ b/include/ff.h.in @@ -298,6 +298,16 @@ extern void FF_WWW_power(BIG_XXX *r,BIG_XXX *x,int e,BIG_XXX *p,int n); @param n size of FF in BIGs */ extern void FF_WWW_pow(BIG_XXX *r,BIG_XXX *x,BIG_XXX *e,BIG_XXX *p,int n); +/** @brief Calculate r=x^e mod p + * + @param r FF instance, on exit = x^e mod p + @param x FF instance + @param e FF exponent + @param p FF modulus + @param n size of base in BIGs + @param en size of exponent in BIGs + */ +extern void FF_WWW_hpow(BIG_XXX *r, BIG_XXX *x, BIG_XXX *e, BIG_XXX *p, int n, int en); /** @brief Calculate r=x^e.y^f mod m * @param r FF instance, on exit = x^e.y^f mod p diff --git a/include/paillier.h b/include/paillier.h index 794ef6e..029e162 100644 --- a/include/paillier.h +++ b/include/paillier.h @@ -50,9 +50,7 @@ extern "C" { */ typedef struct { - BIG_512_60 n[FFLEN_4096]; /**< Paillier Modulus - \f$ n = pq \f$ */ - BIG_512_60 g[FFLEN_4096]; /**< Public Base - \f$ g = n+1 \f$ */ - + BIG_512_60 n[HFLEN_4096]; /**< Paillier Modulus - \f$ n = pq \f$ */ BIG_512_60 n2[FFLEN_4096]; /**< Precomputed \f$ n^2 \f$ */ } PAILLIER_public_key; diff --git a/src/ff.c.in b/src/ff.c.in index 3f83bc2..ea773a8 100644 --- a/src/ff.c.in +++ b/src/ff.c.in @@ -959,7 +959,7 @@ void FF_WWW_power(BIG_XXX r[],BIG_XXX x[],int e,BIG_XXX p[],int n) } /* r=x^e mod p, faster but not side channel resistant */ -void FF_WWW_pow(BIG_XXX r[],BIG_XXX x[],BIG_XXX e[],BIG_XXX p[],int n) +void FF_WWW_hpow(BIG_XXX r[], BIG_XXX x[], BIG_XXX e[], BIG_XXX p[], int n, int en) { int i,b; #ifndef C99 @@ -974,7 +974,7 @@ void FF_WWW_pow(BIG_XXX r[],BIG_XXX x[],BIG_XXX e[],BIG_XXX p[],int n) FF_WWW_nres(r,p,n); FF_WWW_nres(w,p,n); - for (i=8*MODBYTES_XXX*n-1; i>=0; i--) + for (i=8*MODBYTES_XXX*en-1; i>=0; i--) { FF_WWW_modsqr(r,r,p,ND,n); b=BIG_XXX_bit(e[i/BIGBITS_XXX],i%BIGBITS_XXX); @@ -983,6 +983,12 @@ void FF_WWW_pow(BIG_XXX r[],BIG_XXX x[],BIG_XXX e[],BIG_XXX p[],int n) FF_WWW_redc(r,p,ND,n); } +/* r=x^e mod p, faster but not side channel resistant */ +void FF_WWW_pow(BIG_XXX r[],BIG_XXX x[],BIG_XXX e[],BIG_XXX p[],int n) +{ + FF_WWW_hpow(r, x, e, p, n, n); +} + /* double exponentiation r=x^e.y^f mod p */ void FF_WWW_pow2(BIG_XXX r[],BIG_XXX x[],BIG_XXX e,BIG_XXX y[],BIG_XXX f,BIG_XXX p[],int n) { diff --git a/src/paillier.c b/src/paillier.c index c5d6ae5..31d7a81 100644 --- a/src/paillier.c +++ b/src/paillier.c @@ -33,12 +33,7 @@ void PAILLIER_KEY_PAIR(csprng *RNG, octet *P, octet* Q, PAILLIER_public_key *PUB char oct[FS_2048]; octet OCT = {0, FS_2048, oct}; - // Public key - BIG_1024_58 g[FFLEN_2048]; - - // Workspace for CRT precomputations - BIG_1024_58 ff[FFLEN_2048]; - BIG_1024_58 dff[2*FFLEN_2048]; + BIG_1024_58 n[FFLEN_2048]; /* Private key */ @@ -92,33 +87,25 @@ void PAILLIER_KEY_PAIR(csprng *RNG, octet *P, octet* Q, PAILLIER_public_key *PUB FF_2048_norm(PRIV->p2, FFLEN_2048); FF_2048_norm(PRIV->q2, FFLEN_2048); - // g = n + 1 - FF_2048_mul(g, PRIV->p, PRIV->q, HFLEN_2048); - FF_2048_inc(g, 1, FFLEN_2048); + // mp = (((g^(p-1) mod p^2) -1) / p)^(-1) mod p + // Using g = n+1, g^(p-1) = 1 + n(p-1) mod p^2, i.e. + // mp = (n(p-1)/p)^(-1) = -q^(-1) mod p - // (((g^(p-1) mod p^2) - 1) / p)^(-1) mod p for dec/enc with CRT - FF_2048_skpow(ff, g, PRIV->lp, PRIV->p2, FFLEN_2048, HFLEN_2048); - FF_2048_dec(ff, 1, FFLEN_2048); - FF_2048_mul(dff, ff, PRIV->invp, FFLEN_2048); - FF_2048_invmodp(PRIV->mp, dff, PRIV->p, HFLEN_2048); + // (-q)^(-1) mod p + FF_2048_invmodp(PRIV->mp, PRIV->q, PRIV->p, HFLEN_2048); + FF_2048_sub(PRIV->mp, PRIV->p, PRIV->mp, HFLEN_2048); + FF_2048_norm(PRIV->mp, HFLEN_2048); - // (((g^(q-1) mod q^2) - 1) / q)^(-1) mod q for dec/enc with CRT - FF_2048_skpow(ff, g, PRIV->lq, PRIV->q2, FFLEN_2048, HFLEN_2048); - FF_2048_dec(ff, 1, FFLEN_2048); - FF_2048_mul(dff, ff, PRIV->invq, FFLEN_2048); - FF_2048_invmodp(PRIV->mq, dff, PRIV->q, HFLEN_2048); + // (-p)^(-1) mod q + FF_2048_invmodp(PRIV->mq, PRIV->p, PRIV->q, HFLEN_2048); + FF_2048_sub(PRIV->mq, PRIV->q, PRIV->mq, HFLEN_2048); + FF_2048_norm(PRIV->mq, HFLEN_2048); /* Public Key */ - // g = n + 1 - FF_2048_toOctet(&OCT, g, FFLEN_2048); - FF_4096_zero(PUB->g, FFLEN_4096); - FF_4096_fromOctet(PUB->g, &OCT, HFLEN_4096); - OCT_empty(&OCT); - // n - FF_2048_dec(g, 1, FFLEN_2048); - FF_2048_toOctet(&OCT, g, FFLEN_2048); + FF_2048_mul(n, PRIV->p, PRIV->q, HFLEN_2048); + FF_2048_toOctet(&OCT, n, FFLEN_2048); FF_4096_zero(PUB->n, FFLEN_4096); FF_4096_fromOctet(PUB->n, &OCT, HFLEN_4096); OCT_empty(&OCT); @@ -126,10 +113,6 @@ void PAILLIER_KEY_PAIR(csprng *RNG, octet *P, octet* Q, PAILLIER_public_key *PUB // Precompute n^2 for public key FF_4096_sqr(PUB->n2, PUB->n, HFLEN_4096); FF_4096_norm(PUB->n2, FFLEN_4096); - - // Clean memory - FF_2048_zero(ff, FFLEN_2048); - FF_2048_zero(dff, 2*FFLEN_2048); } /* Clean secrets from private key */ @@ -150,41 +133,49 @@ void PAILLIER_PRIVATE_KEY_KILL(PAILLIER_private_key *PRIV) // Paillier encryption void PAILLIER_ENCRYPT(csprng *RNG, PAILLIER_public_key *PUB, octet* PT, octet* CT, octet* R) { - // Random r < n^2 - BIG_512_60 r[FFLEN_4096]; - // plaintext BIG_512_60 pt[HFLEN_4096]; - // ciphertext - BIG_512_60 ct[FFLEN_4096]; + // workspaces + BIG_512_60 ws1[FFLEN_4096]; + BIG_512_60 ws2[FFLEN_4096]; + BIG_512_60 dws[2 * FFLEN_4096]; - FF_4096_fromOctet(pt,PT,HFLEN_4096); + FF_4096_fromOctet(pt, PT, HFLEN_4096); // In production generate R from RNG if (RNG!=NULL) { - FF_4096_randomnum(r, PUB->n2, RNG,FFLEN_4096); + FF_4096_randomnum(ws1, PUB->n2, RNG,FFLEN_4096); } else { - FF_4096_fromOctet(r, R, FFLEN_4096); + FF_4096_fromOctet(ws1, R, FFLEN_4096); } - // ct = g^pt * r^n mod n2 - FF_4096_skpow2(ct, PUB->g, pt, r, PUB->n, PUB->n2, FFLEN_4096, HFLEN_4096); - - // Output - FF_4096_toOctet(CT, ct, FFLEN_4096); - // Output R for Debug if (R!=NULL) { - FF_4096_toOctet(R, r, FFLEN_4096); + FF_4096_toOctet(R, ws1, FFLEN_4096); } + // r^n + FF_4096_hpow(ws1, ws1, PUB->n, PUB->n2, FFLEN_4096, HFLEN_4096); + + // g^pt = 1 + pt * n + FF_4096_mul(ws2, pt, PUB->n, HFLEN_4096); + FF_4096_inc(ws2, 1, FFLEN_4096); + FF_4096_norm(ws2, FFLEN_4096); + + // ct = g^pt * r^n mod n^2 + FF_4096_mul(dws, ws1, ws2, FFLEN_4096); + FF_4096_dmod(ws1, dws, PUB->n2, FFLEN_4096); + + // Output + FF_4096_toOctet(CT, ws1, FFLEN_4096); + // Clean memory - FF_4096_zero(r, FFLEN_4096); + FF_4096_zero(ws2, FFLEN_4096); FF_4096_zero(pt, HFLEN_4096); } @@ -298,14 +289,10 @@ void PAILLIER_MULT(PAILLIER_public_key *PUB, octet* CT1, octet* PT, octet* CT) // Read a public key from its octet representation void PAILLIER_PK_fromOctet(PAILLIER_public_key *PUB, octet *PK) { - FF_4096_zero(PUB->n, FFLEN_4096); FF_4096_fromOctet(PUB->n, PK, HFLEN_4096); FF_4096_sqr(PUB->n2, PUB->n, HFLEN_4096); FF_4096_norm(PUB->n2, FFLEN_4096); - - FF_4096_copy(PUB->g, PUB->n, FFLEN_4096); - FF_4096_inc(PUB->g, 1, HFLEN_4096); } // Write a public key to an octet diff --git a/test/test_paillier_consistency.c b/test/test_paillier_consistency.c index 7c1d1ab..8ca3aba 100644 --- a/test/test_paillier_consistency.c +++ b/test/test_paillier_consistency.c @@ -125,8 +125,7 @@ int paillier(csprng *RNG) PAILLIER_PK_toOctet(&PUBOCT, &PUB); PAILLIER_PK_fromOctet(&PUBIN, &PUBOCT); - ff_4096_compare(PUB.n, PUBIN.n, "n not correctly loaded", FFLEN_4096); - ff_4096_compare(PUB.g, PUBIN.g, "g not correctly loaded", FFLEN_4096); + ff_4096_compare(PUB.n, PUBIN.n, "n not correctly loaded", HFLEN_4096); ff_4096_compare(PUB.n2, PUBIN.n2, "n^2 not correctly loaded", FFLEN_4096); // Set plaintext values diff --git a/test/test_paillier_encrypt.c b/test/test_paillier_encrypt.c index 97b6800..37f0756 100644 --- a/test/test_paillier_encrypt.c +++ b/test/test_paillier_encrypt.c @@ -73,7 +73,6 @@ int main(int argc, char** argv) PAILLIER_public_key PUB; const char* Nline = "N = "; - const char* Gline = "G = "; char rgolden[FS_4096]= {0}; octet RGOLDEN = {0,sizeof(rgolden),rgolden}; @@ -116,16 +115,6 @@ int main(int argc, char** argv) FF_4096_norm(PUB.n2, FFLEN_4096); } - - // Read G - if (!strncmp(line,Gline, strlen(Gline))) - { - len = strlen(Gline); - linePtr = line + len; - FF_4096_zero(PUB.g, FFLEN_4096); - read_FF_4096(PUB.g, linePtr, HFLEN_4096); - } - // Read R if (!strncmp(line,Rline, strlen(Rline))) { diff --git a/test/test_paillier_keygen.c b/test/test_paillier_keygen.c index a7f8689..f6018b1 100644 --- a/test/test_paillier_keygen.c +++ b/test/test_paillier_keygen.c @@ -82,8 +82,7 @@ void ff_2048_compare(char *x_name, char* y_name, BIG_1024_58 *x, BIG_1024_58 *y, void clean_public(PAILLIER_public_key *PUB) { - FF_4096_zero(PUB->n, FFLEN_4096); - FF_4096_zero(PUB->g, FFLEN_4096); + FF_4096_zero(PUB->n, HFLEN_4096); FF_4096_zero(PUB->n2, FFLEN_4096); } @@ -124,7 +123,6 @@ int main(int argc, char** argv) PAILLIER_private_key PRIVGOLDEN; PAILLIER_public_key PUBGOLDEN; const char* Nline = "N = "; - const char* Gline = "G = "; const char* LPline = "LP = "; const char* MPline = "MP = "; const char* LQline = "LQ = "; @@ -161,21 +159,12 @@ int main(int argc, char** argv) testSeed = 1; } - // Read G - if (!strncmp(line, Gline, strlen(Gline))) - { - len = strlen(Gline); - linePtr = line + len; - read_FF_4096(PUBGOLDEN.g, linePtr, HFLEN_4096); - } - // Read N if (!strncmp(line, Nline, strlen(Nline))) { len = strlen(Nline); linePtr = line + len; - FF_4096_zero(PUBGOLDEN.n, FFLEN_4096); read_FF_4096(PUBGOLDEN.n, linePtr, HFLEN_4096); FF_4096_sqr(PUBGOLDEN.n2, PUBGOLDEN.n, HFLEN_4096); @@ -267,8 +256,7 @@ int main(int argc, char** argv) ff_2048_compare("PRIV.invq", "PRIVGOLDEN.invq", PRIV.invq, PRIVGOLDEN.invq, FFLEN_2048); ff_2048_compare("PRIV.q2", "PRIVGOLDEN.q2", PRIV.q2, PRIVGOLDEN.q2, FFLEN_2048); - ff_4096_compare("PUB.n", "PUBGOLDEN.n", PUB.n, PUBGOLDEN.n, FFLEN_4096); - ff_4096_compare("PUB.g", "PUBGOLDEN.g", PUB.g, PUBGOLDEN.g, FFLEN_4096); + ff_4096_compare("PUB.n", "PUBGOLDEN.n", PUB.n, PUBGOLDEN.n, HFLEN_4096); ff_4096_compare("PUB.n2", "PUBGOLDEN.n2", PUB.n2, PUBGOLDEN.n2, FFLEN_4096); // Clean keys for next test vector
