This is an automated email from the ASF dual-hosted git repository. sandreoli pushed a commit to branch review-mike in repository https://gitbox.apache.org/repos/asf/incubator-milagro-crypto-c.git
commit ce9dbdf1c415f1a3c0b41bbf2eba79b453efe332 Author: Samuele Andreoli <[email protected]> AuthorDate: Tue Apr 7 22:35:53 2020 +0100 Extract inversion mod q from crt --- include/ff.h.in | 17 +++++++++-------- include/paillier.h | 2 ++ src/ff.c.in | 9 +++------ src/paillier.c | 30 ++++++++++++++++-------------- test/test_ff_consistency_WWW.c.in | 3 ++- test/test_paillier_decrypt.c | 2 ++ 6 files changed, 34 insertions(+), 29 deletions(-) diff --git a/include/ff.h.in b/include/ff.h.in index 7f35af0..c6e4f6b 100644 --- a/include/ff.h.in +++ b/include/ff.h.in @@ -360,13 +360,14 @@ extern int FF_WWW_cfactor(BIG_XXX *x,sign32 s,int n); extern int FF_WWW_prime(BIG_XXX *x,csprng *R,int n); /** @brief Combine rp and rq using the Chinese Remainder Theorem * - @param r FF instance, on exit the solution of the system - @param rp FF instance, solution modulo p - @param rq FF instance, solution modulo q - @param p FF instance, MUST be coprime with q - @param q FF instance, MUST be coprime with p - @param n size of p and q in BIGs - */ -extern void FF_WWW_crt(BIG_XXX *r, BIG_XXX *rp, BIG_XXX *rq, BIG_XXX *p, BIG_XXX *q, int n); + @param r FF instance, on exit the solution of the system + @param rp FF instance, solution modulo p + @param rq FF instance, solution modulo q + @param p FF instance, MUST be coprime with q + @param invp FF instance, p^(-1) mod q + @param pq FF instance, p*q + @param n size of p in BIGs + */ +extern void FF_WWW_crt(BIG_XXX *r, BIG_XXX *rp, BIG_XXX *rq, BIG_XXX *p, BIG_XXX *invpq, BIG_XXX *pq, int n); #endif diff --git a/include/paillier.h b/include/paillier.h index 029e162..7ce3a72 100644 --- a/include/paillier.h +++ b/include/paillier.h @@ -68,6 +68,8 @@ typedef struct BIG_1024_58 invp[FFLEN_2048]; /**< Precomputed \f$ p^{-1} \pmod{2^m} \f$ */ BIG_1024_58 invq[FFLEN_2048]; /**< Precomputed \f$ q^{-1} \pmod{2^m} \f$ */ + BIG_1024_58 invpq[HFLEN_2048]; /**< Precomputed \f$ p^{-1} \pmod{q} \f$ */ + BIG_1024_58 p2[FFLEN_2048]; /**< Precomputed \f$ p^2 \f$ */ BIG_1024_58 q2[FFLEN_2048]; /**< Precomputed \f$ q^2 \f$ */ diff --git a/src/ff.c.in b/src/ff.c.in index 6e53ffb..d6a678c 100644 --- a/src/ff.c.in +++ b/src/ff.c.in @@ -1191,18 +1191,15 @@ int FF_WWW_prime(BIG_XXX p[],csprng *rng,int n) } /* Chinese Remainder Theorem to reconstruct results mod pq*/ -void FF_WWW_crt(BIG_XXX *r, BIG_XXX *rp, BIG_XXX *rq, BIG_XXX *p, BIG_XXX *q, int n) +void FF_WWW_crt(BIG_XXX *r, BIG_XXX *rp, BIG_XXX *rq, BIG_XXX *p, BIG_XXX *invp, BIG_XXX *pq, int n) { #ifndef C99 - BIG_XXX pq[FFLEN_WWW], invp[HFLEN_WWW], c[FFLEN_WWW], a[FFLEN_WWW], b[2*FFLEN_WWW]; + BIG_XXX c[FFLEN_WWW], a[FFLEN_WWW], b[2*FFLEN_WWW]; #else - BIG_XXX pq[2*n], invp[n], c[2*n], a[2*n], b[4*n]; + BIG_XXX c[2*n], a[2*n], b[4*n]; #endif - FF_WWW_mul(pq, p, q, n); - // c = p * (p^-1 mod q) - FF_WWW_invmodp(invp, p, q, n); FF_WWW_mul(c, p, invp, n); // a = (rq - rp) mod pq diff --git a/src/paillier.c b/src/paillier.c index 0437d17..c58611e 100644 --- a/src/paillier.c +++ b/src/paillier.c @@ -97,8 +97,9 @@ void PAILLIER_KEY_PAIR(csprng *RNG, octet *P, octet* Q, PAILLIER_public_key *PUB FF_2048_norm(PRIV->mp, 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); + // Also use this to precompute p^(-1) mod q + FF_2048_invmodp(PRIV->invpq, PRIV->p, PRIV->q, HFLEN_2048); + FF_2048_sub(PRIV->mq, PRIV->q, PRIV->invpq, HFLEN_2048); FF_2048_norm(PRIV->mq, HFLEN_2048); /* Public Key */ @@ -118,16 +119,17 @@ void PAILLIER_KEY_PAIR(csprng *RNG, octet *P, octet* Q, PAILLIER_public_key *PUB /* Clean secrets from private key */ void PAILLIER_PRIVATE_KEY_KILL(PAILLIER_private_key *PRIV) { - FF_2048_zero(PRIV->p, HFLEN_2048); - FF_2048_zero(PRIV->q, HFLEN_2048); - FF_2048_zero(PRIV->lp, HFLEN_2048); - FF_2048_zero(PRIV->lq, HFLEN_2048); - FF_2048_zero(PRIV->p2, FFLEN_2048); - FF_2048_zero(PRIV->q2, FFLEN_2048); - FF_2048_zero(PRIV->mp, HFLEN_2048); - FF_2048_zero(PRIV->mq, HFLEN_2048); - FF_2048_zero(PRIV->invp, FFLEN_2048); - FF_2048_zero(PRIV->invq, FFLEN_2048); + FF_2048_zero(PRIV->p, HFLEN_2048); + FF_2048_zero(PRIV->q, HFLEN_2048); + FF_2048_zero(PRIV->lp, HFLEN_2048); + FF_2048_zero(PRIV->lq, HFLEN_2048); + FF_2048_zero(PRIV->p2, FFLEN_2048); + FF_2048_zero(PRIV->q2, FFLEN_2048); + FF_2048_zero(PRIV->mp, HFLEN_2048); + FF_2048_zero(PRIV->mq, HFLEN_2048); + FF_2048_zero(PRIV->invp, FFLEN_2048); + FF_2048_zero(PRIV->invq, FFLEN_2048); + FF_2048_zero(PRIV->invpq, HFLEN_2048); } // Paillier encryption @@ -229,7 +231,8 @@ void PAILLIER_DECRYPT(PAILLIER_private_key *PRIV, octet* CT, octet* PT) FF_2048_dmod(ptq, ws, PRIV->q, HFLEN_2048); /* Combine results using CRT */ - FF_2048_crt(pt, ptp, ptq, PRIV->p, PRIV->q, HFLEN_2048); + FF_2048_mul(ws, PRIV->p, PRIV->q, HFLEN_2048); + FF_2048_crt(pt, ptp, ptq, PRIV->p, PRIV->invpq, ws, HFLEN_2048); // Output FF_2048_toOctet(PT, pt, FFLEN_2048); @@ -238,7 +241,6 @@ void PAILLIER_DECRYPT(PAILLIER_private_key *PRIV, octet* CT, octet* PT) FF_2048_zero(pt, FFLEN_2048); FF_2048_zero(ptp, HFLEN_2048); FF_2048_zero(ptq, HFLEN_2048); - FF_2048_zero(ws, FFLEN_2048); FF_2048_zero(dws, 2 * FFLEN_2048); } diff --git a/test/test_ff_consistency_WWW.c.in b/test/test_ff_consistency_WWW.c.in index 59f1d42..f394f9b 100644 --- a/test/test_ff_consistency_WWW.c.in +++ b/test/test_ff_consistency_WWW.c.in @@ -259,6 +259,7 @@ int main() /* Testing CRT */ FF_WWW_mul(N,P,Q,HFLEN_WWW); + FF_WWW_invmodp(E,P,Q,HFLEN_WWW); for (i=0; i<10; i++) { @@ -281,7 +282,7 @@ int main() FF_WWW_mul(G,C,D,HFLEN_WWW); FF_WWW_mod(G,Q,FFLEN_WWW); - FF_WWW_crt(L,F,G,P,Q,HFLEN_WWW); + FF_WWW_crt(L,F,G,P,E,N,HFLEN_WWW); if(FF_WWW_comp(L,H,HFLEN_WWW)) { diff --git a/test/test_paillier_decrypt.c b/test/test_paillier_decrypt.c index c9fde68..c44247c 100644 --- a/test/test_paillier_decrypt.c +++ b/test/test_paillier_decrypt.c @@ -132,6 +132,8 @@ int main(int argc, char** argv) FF_2048_zero(PRIV.invq, FFLEN_2048); FF_2048_invmod2m(PRIV.invq, PRIV.q, HFLEN_2048); + + FF_2048_invmodp(PRIV.invpq, PRIV.p, PRIV.q, HFLEN_2048); } // Read LP
