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/25 09:51:23 UTC
[incubator-milagro-crypto-c] 02/02: make invmodp CT
This is an automated email from the ASF dual-hosted git repository.
sandreoli pushed a commit to branch issue74-review-ct
in repository https://gitbox.apache.org/repos/asf/incubator-milagro-crypto-c.git
commit 55d903760cb1b9bd04098a072f2f28130a9e2ce7
Author: Samuele Andreoli <sa...@yahoo.it>
AuthorDate: Wed Mar 25 09:41:03 2020 +0000
make invmodp CT
---
src/big.c.in | 131 +++++++++++++++++++++++++++++++--------------------------
src/ff.c.in | 134 +++++++++++++++++++++++++++++++++--------------------------
2 files changed, 147 insertions(+), 118 deletions(-)
diff --git a/src/big.c.in b/src/big.c.in
index c8c4929..6bc18f2 100644
--- a/src/big.c.in
+++ b/src/big.c.in
@@ -1351,6 +1351,7 @@ void BIG_XXX_moddiv(BIG_XXX r,BIG_XXX a1,BIG_XXX b1,BIG_XXX m)
BIG_XXX_copy(b,b1);
BIG_XXX_mod(a,m);
+ BIG_XXX_mod(b,m);
BIG_XXX_invmodp(z,b,m);
BIG_XXX_mul(d,a,z);
@@ -1479,69 +1480,83 @@ void BIG_XXX_invmod2m(BIG_XXX a)
BIG_XXX_mod2m(a,BIGBITS_XXX);
}
-/* Set r=1/a mod p. Binary method */
-/* SU= 240 */
+/* Set r=1/a mod p. Kaliski method - on entry a < p*/
void BIG_XXX_invmodp(BIG_XXX r,BIG_XXX a,BIG_XXX p)
{
- BIG_XXX u,v,x1,x2,t,one;
- BIG_XXX_mod(a,p);
- BIG_XXX_copy(u,a);
- BIG_XXX_copy(v,p);
- BIG_XXX_one(one);
- BIG_XXX_copy(x1,one);
- BIG_XXX_zero(x2);
+ int k, p1, pu, pv, psw, pmv;
+ BIG_XXX u, v, s, w;
+
+ BIG_XXX_copy(u, p);
+ BIG_XXX_copy(v,a);
+ BIG_XXX_zero(r);
+ BIG_XXX_one(s);
- while (BIG_XXX_comp(u,one)!=0 && BIG_XXX_comp(v,one)!=0)
+ // v = a2^BIGBITS_XXX mod p
+ for (k = 0; k < BIGBITS_XXX; k++)
{
- while (BIG_XXX_parity(u)==0)
- {
- BIG_XXX_fshr(u,1);
- if (BIG_XXX_parity(x1)!=0)
- {
- BIG_XXX_add(x1,p,x1);
- BIG_XXX_norm(x1);
- }
- BIG_XXX_fshr(x1,1);
- }
- while (BIG_XXX_parity(v)==0)
- {
- BIG_XXX_fshr(v,1);
- if (BIG_XXX_parity(x2)!=0)
- {
- BIG_XXX_add(x2,p,x2);
- BIG_XXX_norm(x2);
- }
- BIG_XXX_fshr(x2,1);
- }
- if (BIG_XXX_comp(u,v)>=0)
- {
- BIG_XXX_sub(u,u,v);
- BIG_XXX_norm(u);
- if (BIG_XXX_comp(x1,x2)>=0) BIG_XXX_sub(x1,x1,x2);
- else
- {
- BIG_XXX_sub(t,p,x2);
- BIG_XXX_add(x1,x1,t);
- }
- BIG_XXX_norm(x1);
- }
- else
- {
- BIG_XXX_sub(v,v,u);
- BIG_XXX_norm(v);
- if (BIG_XXX_comp(x2,x1)>=0) BIG_XXX_sub(x2,x2,x1);
- else
- {
- BIG_XXX_sub(t,p,x1);
- BIG_XXX_add(x2,x2,t);
- }
- BIG_XXX_norm(x2);
- }
+ BIG_XXX_sub(w, v, p);
+ BIG_XXX_norm(w);
+ BIG_XXX_cmove(v, w, (BIG_XXX_comp(v, p) > 0));
+ BIG_XXX_fshl(v, 1);
+ }
+
+ // CT Kaliski almost inverse
+ // The correction step is included
+ for (k = 0; k < 2 * BIGBITS_XXX; k++)
+ {
+ p1 = !BIG_XXX_iszilch(v);
+
+ pu = BIG_XXX_parity(u);
+ pv = BIG_XXX_parity(v);
+ // Cases 2-4 of Kaliski
+ psw = p1 & ((!pu) | (pv & (BIG_XXX_comp(u,v)>0)));
+ // Cases 3-4 of Kaliski
+ pmv = p1 & pu & pv;
+
+ // Swap necessary for cases 2-4 of Kaliski
+ BIG_XXX_cswap(u, v, psw);
+ BIG_XXX_cswap(r, s, psw);
+
+ // Addition and subtraction for cases 3-4 of Kaliski
+ BIG_XXX_sub(w, v, u);
+ BIG_XXX_norm(w);
+ BIG_XXX_cmove(v, w, pmv);
+
+ BIG_XXX_add(w, r, s);
+ BIG_XXX_norm(w);
+ BIG_XXX_cmove(s, w, pmv);
+
+ // Subtraction for correction step
+ BIG_XXX_sub(w, r, p);
+ BIG_XXX_norm(w);
+ BIG_XXX_cmove(r, w, (!p1) & (BIG_XXX_comp(r, p) > 0));
+
+ // Shifts for all Kaliski cases and correction step
+ BIG_XXX_fshl(r, 1);
+ BIG_XXX_fshr(v, 1);
+
+ // Restore u,v,r,s to the original position
+ BIG_XXX_cswap(u, v, psw);
+ BIG_XXX_cswap(r, s, psw);
+ }
+
+ // Last step of kaliski
+ // Moved after the correction step
+ BIG_XXX_sub(w, r, p);
+ BIG_XXX_norm(w);
+ BIG_XXX_cmove(r, w, (BIG_XXX_comp(r,p)>0));
+
+ BIG_XXX_sub(r, p, r);
+ BIG_XXX_norm(r);
+
+ // Restore inverse from Montgomery form
+ for (k = 0; k < BIGBITS_XXX; k++)
+ {
+ BIG_XXX_add(w, r, p);
+ BIG_XXX_norm(w);
+ BIG_XXX_cmove(r, w, BIG_XXX_parity(r));
+ BIG_XXX_fshr(r, 1);
}
- if (BIG_XXX_comp(u,one)==0)
- BIG_XXX_copy(r,x1);
- else
- BIG_XXX_copy(r,x2);
}
/* set x = x mod 2^m */
diff --git a/src/ff.c.in b/src/ff.c.in
index 50a2e81..4b678f3 100644
--- a/src/ff.c.in
+++ b/src/ff.c.in
@@ -541,74 +541,88 @@ void FF_WWW_dmod(BIG_XXX r[],BIG_XXX a[],BIG_XXX b[],int n)
FF_WWW_mod(r,b,n);
}
-/* Set r=1/a mod p. Binary method - a<p on entry */
-
+/* Set r=1/a mod p. Kaliski method - a<p on entry */
void FF_WWW_invmodp(BIG_XXX r[],BIG_XXX a[],BIG_XXX p[],int n)
{
#ifndef C99
- BIG_XXX u[FFLEN_WWW],v[FFLEN_WWW],x1[FFLEN_WWW],x2[FFLEN_WWW],t[FFLEN_WWW],one[FFLEN_WWW];
+ BIG_XXX u[FFLEN_WWW],v[FFLEN_WWW],s[FFLEN_WWW],w[FFLEN_WWW];
#else
- BIG_XXX u[n],v[n],x1[n],x2[n],t[n],one[n];
+ BIG_XXX u[n],v[n],s[n],w[n];
#endif
- FF_WWW_copy(u,a,n);
- FF_WWW_copy(v,p,n);
- FF_WWW_one(one,n);
- FF_WWW_copy(x1,one,n);
- FF_WWW_zero(x2,n);
-
- // reduce n in here as well!
- while (FF_WWW_comp(u,one,n)!=0 && FF_WWW_comp(v,one,n)!=0)
+
+ int k, p1, pu, pv, psw, pmv;
+
+ FF_WWW_copy(u, p, n);
+ FF_WWW_copy(v, a, n);
+ FF_WWW_zero(r, n);
+ FF_WWW_one(s, n);
+
+ // v = a2^(n*BIGBITS_XXX) mod p
+ for(k = 0; k < n*BIGBITS_XXX; k++)
{
- while (FF_WWW_parity(u)==0)
- {
- FF_WWW_shr(u,n);
- if (FF_WWW_parity(x1)!=0)
- {
- FF_WWW_add(x1,p,x1,n);
- FF_WWW_norm(x1,n);
- }
- FF_WWW_shr(x1,n);
- }
- while (FF_WWW_parity(v)==0)
- {
- FF_WWW_shr(v,n);
- if (FF_WWW_parity(x2)!=0)
- {
- FF_WWW_add(x2,p,x2,n);
- FF_WWW_norm(x2,n);
- }
- FF_WWW_shr(x2,n);
- }
- if (FF_WWW_comp(u,v,n)>=0)
- {
+ FF_WWW_sub(w, v, p, n);
+ FF_WWW_norm(w, n);
+ FF_WWW_cmove(v, w, (FF_WWW_comp(v, p, n) > 0), n);
+ FF_WWW_shl(v, n);
+ }
- FF_WWW_sub(u,u,v,n);
- FF_WWW_norm(u,n);
- if (FF_WWW_comp(x1,x2,n)>=0) FF_WWW_sub(x1,x1,x2,n);
- else
- {
- FF_WWW_sub(t,p,x2,n);
- FF_WWW_add(x1,x1,t,n);
- }
- FF_WWW_norm(x1,n);
- }
- else
- {
- FF_WWW_sub(v,v,u,n);
- FF_WWW_norm(v,n);
- if (FF_WWW_comp(x2,x1,n)>=0) FF_WWW_sub(x2,x2,x1,n);
- else
- {
- FF_WWW_sub(t,p,x1,n);
- FF_WWW_add(x2,x2,t,n);
- }
- FF_WWW_norm(x2,n);
- }
+ // CT Kaliski almost inverse
+ // The correction step is included
+ for (k = 0; k < 2*n*BIGBITS_XXX; k++)
+ {
+ p1 = !FF_WWW_iszilch(v, n);
+
+ pu = FF_WWW_parity(u);
+ pv = FF_WWW_parity(v);
+ // Cases 2-4 of Kaliski
+ psw = p1 & ((!pu) | (pv & (FF_WWW_comp(u, v, n)>0)));
+ // Cases 3-4 of Kaliski
+ pmv = p1 & pu & pv;
+
+ // Swap for cases 2-4 of Kaliski
+ FF_WWW_cswap(u, v, psw, n);
+ FF_WWW_cswap(r, s, psw, n);
+
+ // Addition and subtraction for cases 3-4 of Kaliski
+ FF_WWW_sub(w, v, u, n);
+ FF_WWW_norm(w, n);
+ FF_WWW_cmove(v, w, pmv, n);
+
+ FF_WWW_add(w, r, s, n);
+ FF_WWW_norm(w, n);
+ FF_WWW_cmove(s, w, pmv, n);
+
+ // Subtraction for correction step
+ FF_WWW_sub(w, r, p, n);
+ FF_WWW_norm(w, n);
+ FF_WWW_cmove(r, w, (!p1) & (FF_WWW_comp(r, p, n)>0), n);
+
+ // Shifts for all Kaliski cases and correction step
+ FF_WWW_shl(r, n);
+ FF_WWW_shr(v, n);
+
+ // Restore u,v,r,s to the original position
+ FF_WWW_cswap(u, v, psw, n);
+ FF_WWW_cswap(r, s, psw, n);
+ }
+
+ // Last step of Kaliski
+ // Moved after the correction step
+ FF_WWW_sub(w, r, p, n);
+ FF_WWW_norm(w, n);
+ FF_WWW_cmove(r, w, (FF_WWW_comp(r, p, n)>0), n);
+
+ FF_WWW_sub(r, p, r, n);
+ FF_WWW_norm(r, n);
+
+ // Restore inverse from Montgomery form
+ for (k = 0; k < n*BIGBITS_XXX; k++)
+ {
+ FF_WWW_add(w, r, p, n);
+ FF_WWW_norm(w, n);
+ FF_WWW_cmove(r, w, FF_WWW_parity(r), n);
+ FF_WWW_shr(r, n);
}
- if (FF_WWW_comp(u,one,n)==0)
- FF_WWW_copy(r,x1,n);
- else
- FF_WWW_copy(r,x2,n);
}
/* nesidue mod m */