This is an automated email from the ASF dual-hosted git repository. sandreoli pushed a commit to branch issue51 in repository https://gitbox.apache.org/repos/asf/incubator-milagro-crypto-c.git
commit fc31c16e2941e435d667247fc4e687913b536a4a Author: samuele-andreoli <[email protected]> AuthorDate: Wed Dec 4 11:28:36 2019 +0000 use inversion modulo 2^m trick for division --- include/ff.h.in | 7 +++++ include/paillier.h | 10 +++---- src/ff.c.in | 2 +- src/paillier.c | 69 ++++++++++---------------------------------- test/test_paillier_decrypt.c | 2 ++ test/test_paillier_keygen.c | 24 ++++++++------- 6 files changed, 44 insertions(+), 70 deletions(-) diff --git a/include/ff.h.in b/include/ff.h.in index 7c50c00..05907b8 100644 --- a/include/ff.h.in +++ b/include/ff.h.in @@ -211,6 +211,13 @@ extern void FF_WWW_dmod(BIG_XXX *x,BIG_XXX *y,BIG_XXX *z,int n); @param n size of FF in BIGs */ extern void FF_WWW_invmodp(BIG_XXX *x,BIG_XXX *y,BIG_XXX *z,int n); +/** @brief Invert an FF mod 2^(n*BIGBITS) + * + * @param U FF instance, on exit 1/a mod 2^(n*BIGBITS) + * @param a FF instance + * @param n size of FF in BIGs + */ +extern void FF_WWW_invmod2m(BIG_XXX U[],BIG_XXX a[],int n); /** @brief Create an FF from a random number generator * @param x FF instance, on exit x is a random number of length n BIGs with most significant bit a 1 diff --git a/include/paillier.h b/include/paillier.h index 30cae34..94bf087 100644 --- a/include/paillier.h +++ b/include/paillier.h @@ -57,9 +57,10 @@ typedef struct{ BIG_512_60 l[HFLEN_4096]; /**< Private Key (Euler totient of n) */ BIG_512_60 m[FFLEN_4096]; /**< Precomputed l^(-1) */ - BIG_512_60 p[HFLEN_4096]; /**< Secret Prime */ - BIG_512_60 q[HFLEN_4096]; /**< Secret Prime */ - BIG_512_60 n2[FFLEN_4096]; /**< Precomputed n^2 */ + BIG_512_60 p[HFLEN_4096]; /**< Secret Prime */ + BIG_512_60 q[HFLEN_4096]; /**< Secret Prime */ + BIG_512_60 invn[FFLEN_4096]; /**< Precomputed inverse of n */ + BIG_512_60 n2[FFLEN_4096]; /**< Precomputed n^2 */ }PAILLIER_private_key; /*! \brief Generate the key pair @@ -110,8 +111,7 @@ void PAILLIER_ENCRYPT(csprng *RNG, PAILLIER_public_key *PUB, octet* PT, octet* C * These are the decryption steps. * * <ol> - * <li> \f$ n2 = n*n \f$ - * <li> \f$ ctl = ct^l \pmod{n2} - 1 \f$ + * <li> \f$ ctl = ct^l \pmod{n^2} - 1 \f$ * <li> \f$ ctln = ctl / n \f$ * <li> \f$ pt = ctln * m \pmod{n} \f$ * </ol> diff --git a/src/ff.c.in b/src/ff.c.in index 946388c..a1dfd2d 100644 --- a/src/ff.c.in +++ b/src/ff.c.in @@ -635,7 +635,7 @@ static void FF_WWW_redc(BIG_XXX a[],BIG_XXX m[],BIG_XXX ND[],int n) } /* U=1/a mod 2^m - Arazi & Qi */ -static void FF_WWW_invmod2m(BIG_XXX U[],BIG_XXX a[],int n) +void FF_WWW_invmod2m(BIG_XXX U[],BIG_XXX a[],int n) { int i; #ifndef C99 diff --git a/src/paillier.c b/src/paillier.c index cacf40d..15532ab 100644 --- a/src/paillier.c +++ b/src/paillier.c @@ -27,42 +27,6 @@ under the License. #include "ff_2048.h" #include "paillier.h" -void FF_4096_divide(BIG_512_60 x[], BIG_512_60 y[], BIG_512_60 z[]) -{ - BIG_512_60 d[FFLEN_4096]; - BIG_512_60 q[FFLEN_4096]; - - FF_4096_zero(z,FFLEN_4096); - - while(FF_4096_comp(x,y,FFLEN_4096) <= 0) - { - // (Re)set values for d and q - FF_4096_one(q,FFLEN_4096); - FF_4096_copy(d,x,FFLEN_4096); - - // Left shift the denominator until bigger that remainder - while(FF_4096_comp(d,y,FFLEN_4096) == -1) - { - FF_4096_shl(d,FFLEN_4096); - FF_4096_shl(q,FFLEN_4096); - } - - // Right shift the denominator if bigger than the remainder - if(FF_4096_comp(d,y,FFLEN_4096) == 1) - { - FF_4096_shr(q,FFLEN_4096); - FF_4096_shr(d,FFLEN_4096); - } - - // y = y - d i.e. remainder - FF_4096_sub(y,y,d,FFLEN_4096); - FF_4096_norm(y,FFLEN_4096); - - // z = z + q i.e. update quotient - FF_4096_add(z,z,q,FFLEN_4096); - } -} - /* generate a Paillier key pair */ void PAILLIER_KEY_PAIR(csprng *RNG, octet *P, octet* Q, PAILLIER_public_key *PUB, PAILLIER_private_key *PRIV) { @@ -129,7 +93,6 @@ void PAILLIER_KEY_PAIR(csprng *RNG, octet *P, octet* Q, PAILLIER_public_key *PUB FF_2048_inc(p,1,HFLEN_2048); FF_2048_inc(q,1,HFLEN_2048); - // Output Private Key char oct[FS_2048]; octet OCT = {0,FS_2048, oct}; @@ -161,12 +124,15 @@ void PAILLIER_KEY_PAIR(csprng *RNG, octet *P, octet* Q, PAILLIER_public_key *PUB FF_2048_toOctet(&OCT, m, FFLEN_2048); FF_4096_zero(PRIV->m, FFLEN_4096); FF_4096_fromOctet(PRIV->m, &OCT, HFLEN_4096); - OCT_empty(&OCT); + OCT_clear(&OCT); // Precompute n^2 FF_4096_sqr(PRIV->n2, PRIV->n, HFLEN_4096); FF_4096_norm(PRIV->n2, FFLEN_4096); + // Precompute n^-1 mod 2^m + FF_4096_invmod2m(PRIV->invn, PRIV->n, FFLEN_4096); + // Output Public Key FF_4096_copy(PUB->n , PRIV->n , FFLEN_4096); FF_4096_copy(PUB->g , PRIV->g , FFLEN_4096); @@ -280,34 +246,31 @@ void PAILLIER_ENCRYPT(csprng *RNG, PAILLIER_public_key *PUB, octet* PT, octet* C /* Paillier decrypt */ void PAILLIER_DECRYPT(PAILLIER_private_key *PRIV, octet* CT, octet* PT) { - // Ciphertext + // Ciphertext BIG_512_60 ct[FFLEN_4096]; // Plaintext BIG_512_60 pt[FFLEN_4096]; - // ctl = ct^l mod n^2 - BIG_512_60 ctl[FFLEN_4096]; - - // ctln = ctl / n - BIG_512_60 ctln[FFLEN_4096]; + // ctln = (ct^l - 1) / n + BIG_512_60 ctln[2 * FFLEN_4096]; FF_4096_fromOctet(ct,CT,FFLEN_4096); - // ct^l mod n^2 - 1 - FF_4096_skpow(ctl,ct,PRIV->l,PRIV->n2,FFLEN_4096,HFLEN_4096); - FF_4096_dec(ctl,1,FFLEN_4096); + // (ct^l mod n^2) - 1 + FF_4096_skpow(ct,ct,PRIV->l,PRIV->n2,FFLEN_4096,HFLEN_4096); + FF_4096_dec(ct,1,FFLEN_4096); #ifdef DEBUG - printf("PAILLIER_DECRYPT ctl "); - FF_4096_output(ctl,FFLEN_4096); + printf("PAILLIER_DECRYPT ct^l-1 "); + FF_4096_output(ct,FFLEN_4096); printf("\n\n"); #endif - // ctln = ctl / n - // note that ctln fits into a FF_2048 element, + // Division using the inverse mod 2^m trick. + // ctln actually fits into a FF_2048 element // since ctln = ctl/n < n^2 / n = n - FF_4096_divide(PRIV->n, ctl, ctln); + FF_4096_mul(ctln,ct,PRIV->invn,FFLEN_4096); // pt = ctln * m mod n // the result fits into a FF_4096 element, @@ -345,7 +308,7 @@ void PAILLIER_DECRYPT(PAILLIER_private_key *PRIV, octet* CT, octet* PT) #endif // Clean memory - FF_4096_zero(ctl, FFLEN_4096); + FF_4096_zero(ct, FFLEN_4096); FF_4096_zero(ctln, FFLEN_4096); FF_4096_zero(pt, HFLEN_4096); } diff --git a/test/test_paillier_decrypt.c b/test/test_paillier_decrypt.c index f60d034..e050f79 100644 --- a/test/test_paillier_decrypt.c +++ b/test/test_paillier_decrypt.c @@ -111,6 +111,8 @@ int main(int argc, char** argv) FF_4096_sqr(PRIV.n2,PRIV.n, HFLEN_4096); FF_4096_norm(PRIV.n2, FFLEN_4096); + + FF_4096_invmod2m(PRIV.invn,PRIV.n,FFLEN_4096); #ifdef DEBUG printf("N = "); FF_4096_output(PRIV.n , FFLEN_4096); diff --git a/test/test_paillier_keygen.c b/test/test_paillier_keygen.c index fecb25d..e241d38 100644 --- a/test/test_paillier_keygen.c +++ b/test/test_paillier_keygen.c @@ -184,6 +184,8 @@ int main(int argc, char** argv) FF_4096_sqr(PRIVGOLDEN.n2,PRIVGOLDEN.n, HFLEN_4096); FF_4096_norm(PRIVGOLDEN.n2, FFLEN_4096); + FF_4096_invmod2m(PRIVGOLDEN.invn, PRIVGOLDEN.n, FFLEN_4096); + FF_4096_copy(PUBGOLDEN.n, PRIVGOLDEN.n, HFLEN_4096); FF_4096_copy(PUBGOLDEN.n2, PRIVGOLDEN.n2, FFLEN_4096); } @@ -255,16 +257,17 @@ int main(int argc, char** argv) printf("\n\n"); #endif - compare_FF("PRIV.p" , "PRIVGOLDEN.p" , PRIV.p , PRIVGOLDEN.p , HFLEN_4096); - compare_FF("PRIV.q" , "PRIVGOLDEN.q" , PRIV.q , PRIVGOLDEN.q , HFLEN_4096); - compare_FF("PRIV.l" , "PRIVGOLDEN.l" , PRIV.l , PRIVGOLDEN.l , FFLEN_4096); - compare_FF("PRIV.m" , "PRIVGOLDEN.m" , PRIV.m , PRIVGOLDEN.m , FFLEN_4096); - compare_FF("PRIV.n" , "PRIVGOLDEN.n" , PRIV.n , PRIVGOLDEN.n , FFLEN_4096); - compare_FF("PRIV.g" , "PRIVGOLDEN.g" , PRIV.g , PRIVGOLDEN.g , FFLEN_4096); - compare_FF("PRIV.n2", "PRIVGOLDEN.n2", PRIV.n2, PRIVGOLDEN.n2, FFLEN_4096); - - compare_FF("PUB.n" , "PUBGOLDEN.n" , PUB.n , PUBGOLDEN.n , FFLEN_4096); - compare_FF("PUB.g" , "PUBGOLDEN.g" , PUB.g , PUBGOLDEN.g , FFLEN_4096); + compare_FF("PRIV.p", "PRIVGOLDEN.p", PRIV.p, PRIVGOLDEN.p, HFLEN_4096); + compare_FF("PRIV.q", "PRIVGOLDEN.q", PRIV.q, PRIVGOLDEN.q, HFLEN_4096); + compare_FF("PRIV.l", "PRIVGOLDEN.l", PRIV.l, PRIVGOLDEN.l, FFLEN_4096); + compare_FF("PRIV.m", "PRIVGOLDEN.m", PRIV.m, PRIVGOLDEN.m, FFLEN_4096); + compare_FF("PRIV.n", "PRIVGOLDEN.n", PRIV.n, PRIVGOLDEN.n, FFLEN_4096); + compare_FF("PRIV.g", "PRIVGOLDEN.g", PRIV.g, PRIVGOLDEN.g, FFLEN_4096); + compare_FF("PRIV.invn", "PRIVGOLDEN.invn", PRIV.invn, PRIVGOLDEN.invn, FFLEN_4096); + compare_FF("PRIV.n2", "PRIVGOLDEN.n2", PRIV.n2, PRIVGOLDEN.n2, FFLEN_4096); + + compare_FF("PUB.n", "PUBGOLDEN.n", PUB.n, PUBGOLDEN.n, FFLEN_4096); + compare_FF("PUB.g", "PUBGOLDEN.g", PUB.g, PUBGOLDEN.g, FFLEN_4096); compare_FF("PUB.n2", "PUBGOLDEN.n2", PUB.n2, PUBGOLDEN.n2, FFLEN_4096); // Clean keys for next test vector @@ -281,4 +284,3 @@ int main(int argc, char** argv) printf("SUCCESS TEST PAILLIER KEYGEN PASSED\n"); exit(EXIT_SUCCESS); } -
