You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@milagro.apache.org by sa...@apache.org on 2019/12/06 15:07:46 UTC
[incubator-milagro-crypto-c] 07/10: use inversion modulo 2^m trick
for division
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 <sa...@yahoo.it>
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);
}
-