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 2020/03/09 10:28:51 UTC
[incubator-milagro-crypto-c] 01/01: Use new trick in paillier
ecnryption and keygen
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 <sa...@yahoo.it>
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