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:50 UTC
[incubator-milagro-crypto-c] branch issue73-new-paillier-trick
created (now 5aed593)
This is an automated email from the ASF dual-hosted git repository.
sandreoli pushed a change to branch issue73-new-paillier-trick
in repository https://gitbox.apache.org/repos/asf/incubator-milagro-crypto-c.git.
at 5aed593 Use new trick in paillier ecnryption and keygen
This branch includes the following new commits:
new 5aed593 Use new trick in paillier ecnryption and keygen
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
[incubator-milagro-crypto-c] 01/01: Use new trick in paillier
ecnryption and keygen
Posted by sa...@apache.org.
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