summaryrefslogtreecommitdiff
path: root/repackaged/bcprov/src/main/java/com/android/org/bouncycastle/math/raw/Mod.java
diff options
context:
space:
mode:
Diffstat (limited to 'repackaged/bcprov/src/main/java/com/android/org/bouncycastle/math/raw/Mod.java')
-rw-r--r--repackaged/bcprov/src/main/java/com/android/org/bouncycastle/math/raw/Mod.java578
1 files changed, 482 insertions, 96 deletions
diff --git a/repackaged/bcprov/src/main/java/com/android/org/bouncycastle/math/raw/Mod.java b/repackaged/bcprov/src/main/java/com/android/org/bouncycastle/math/raw/Mod.java
index 7d0c48d7..80e45ca1 100644
--- a/repackaged/bcprov/src/main/java/com/android/org/bouncycastle/math/raw/Mod.java
+++ b/repackaged/bcprov/src/main/java/com/android/org/bouncycastle/math/raw/Mod.java
@@ -3,15 +3,51 @@ package com.android.org.bouncycastle.math.raw;
import java.util.Random;
-import com.android.org.bouncycastle.util.Pack;
+import com.android.org.bouncycastle.util.Integers;
+
+/*
+ * Modular inversion as implemented in this class is based on the paper "Fast constant-time gcd
+ * computation and modular inversion" by Daniel J. Bernstein and Bo-Yin Yang.
+ */
/**
* @hide This class is not part of the Android public SDK API
*/
public abstract class Mod
{
+ private static final int M30 = 0x3FFFFFFF;
+ private static final long M32L = 0xFFFFFFFFL;
+
+ /** @deprecated Will be removed. */
+ public static void add(int[] p, int[] x, int[] y, int[] z)
+ {
+ int len = p.length;
+ int c = Nat.add(len, x, y, z);
+ if (c != 0)
+ {
+ Nat.subFrom(len, p, z);
+ }
+ }
+
+ public static void checkedModOddInverse(int[] m, int[] x, int[] z)
+ {
+ if (0 == modOddInverse(m, x, z))
+ {
+ throw new ArithmeticException("Inverse does not exist.");
+ }
+ }
+
+ public static void checkedModOddInverseVar(int[] m, int[] x, int[] z)
+ {
+ if (!modOddInverseVar(m, x, z))
+ {
+ throw new ArithmeticException("Inverse does not exist.");
+ }
+ }
+
public static int inverse32(int d)
{
+// assert (d & 1) == 1;
// int x = d + (((d + 1) & 4) << 1); // d.x == 1 mod 2**4
int x = d; // d.x == 1 mod 2**3
x *= 2 - d * x; // d.x == 1 mod 2**6
@@ -22,72 +58,152 @@ public abstract class Mod
return x;
}
- public static void invert(int[] p, int[] x, int[] z)
+ /** @deprecated Use {@link #checkedModOddInverseVar(int[], int[], int[])} instead. */
+ public static void invert(int[] m, int[] x, int[] z)
{
- int len = p.length;
- if (Nat.isZero(len, x))
- {
- throw new IllegalArgumentException("'x' cannot be 0");
- }
- if (Nat.isOne(len, x))
- {
- System.arraycopy(x, 0, z, 0, len);
- return;
- }
+ checkedModOddInverseVar(m, x, z);
+ }
- int[] u = Nat.copy(len, x);
- int[] a = Nat.create(len);
- a[0] = 1;
- int ac = 0;
+ public static int modOddInverse(int[] m, int[] x, int[] z)
+ {
+ int len32 = m.length;
+// assert len32 > 0;
+// assert (m[0] & 1) != 0;
+// assert m[len32 - 1] != 0;
- if ((u[0] & 1) == 0)
- {
- ac = inversionStep(p, u, len, a, ac);
- }
- if (Nat.isOne(len, u))
+ int bits = (len32 << 5) - Integers.numberOfLeadingZeros(m[len32 - 1]);
+ int len30 = (bits + 29) / 30;
+
+ int[] t = new int[4];
+ int[] D = new int[len30];
+ int[] E = new int[len30];
+ int[] F = new int[len30];
+ int[] G = new int[len30];
+ int[] M = new int[len30];
+
+ E[0] = 1;
+ encode30(bits, x, 0, G, 0);
+ encode30(bits, m, 0, M, 0);
+ System.arraycopy(M, 0, F, 0, len30);
+
+ int eta = -1;
+ int m0Inv32 = inverse32(M[0]);
+ int maxDivsteps = getMaximumDivsteps(bits);
+
+ for (int divSteps = 0; divSteps < maxDivsteps; divSteps += 30)
{
- inversionResult(p, ac, a, z);
- return;
+ eta = divsteps30(eta, F[0], G[0], t);
+ updateDE30(len30, D, E, t, m0Inv32, M);
+ updateFG30(len30, F, G, t);
}
- int[] v = Nat.copy(len, p);
- int[] b = Nat.create(len);
- int bc = 0;
+ int signF = F[len30 - 1] >> 31;
+ cnegate30(len30, signF, F);
- int uvLen = len;
+ /*
+ * D is in the range (-2.M, M). First, conditionally add M if D is negative, to bring it
+ * into the range (-M, M). Then normalize by conditionally negating (according to signF)
+ * and/or then adding M, to bring it into the range [0, M).
+ */
+ cnormalize30(len30, signF, D, M);
- for (;;)
+ decode30(bits, D, 0, z, 0);
+// assert 0 != Nat.lessThan(len32, z, m);
+
+ return Nat.equalTo(len30, F, 1) & Nat.equalToZero(len30, G);
+ }
+
+ public static boolean modOddInverseVar(int[] m, int[] x, int[] z)
+ {
+ int len32 = m.length;
+// assert len32 > 0;
+// assert (m[0] & 1) != 0;
+// assert m[len32 - 1] != 0;
+
+ int bits = (len32 << 5) - Integers.numberOfLeadingZeros(m[len32 - 1]);
+ int len30 = (bits + 29) / 30;
+
+ int[] t = new int[4];
+ int[] D = new int[len30];
+ int[] E = new int[len30];
+ int[] F = new int[len30];
+ int[] G = new int[len30];
+ int[] M = new int[len30];
+
+ E[0] = 1;
+ encode30(bits, x, 0, G, 0);
+ encode30(bits, m, 0, M, 0);
+ System.arraycopy(M, 0, F, 0, len30);
+
+ int clzG = Integers.numberOfLeadingZeros(G[len30 - 1] | 1) - (len30 * 30 + 2 - bits);
+ int eta = -1 - clzG;
+ int lenDE = len30, lenFG = len30;
+ int m0Inv32 = inverse32(M[0]);
+ int maxDivsteps = getMaximumDivsteps(bits);
+
+ int divsteps = 0;
+ while (!Nat.isZero(lenFG, G))
{
- while (u[uvLen - 1] == 0 && v[uvLen - 1] == 0)
+ if (divsteps >= maxDivsteps)
{
- --uvLen;
+ return false;
}
- if (Nat.gte(uvLen, u, v))
- {
- Nat.subFrom(uvLen, v, u);
-// assert (u[0] & 1) == 0;
- ac += Nat.subFrom(len, b, a) - bc;
- ac = inversionStep(p, u, uvLen, a, ac);
- if (Nat.isOne(uvLen, u))
- {
- inversionResult(p, ac, a, z);
- return;
- }
- }
- else
+ divsteps += 30;
+
+ eta = divsteps30Var(eta, F[0], G[0], t);
+ updateDE30(lenDE, D, E, t, m0Inv32, M);
+ updateFG30(lenFG, F, G, t);
+
+ int fn = F[lenFG - 1];
+ int gn = G[lenFG - 1];
+
+ int cond = (lenFG - 2) >> 31;
+ cond |= fn ^ (fn >> 31);
+ cond |= gn ^ (gn >> 31);
+
+ if (cond == 0)
{
- Nat.subFrom(uvLen, u, v);
-// assert (v[0] & 1) == 0;
- bc += Nat.subFrom(len, a, b) - ac;
- bc = inversionStep(p, v, uvLen, b, bc);
- if (Nat.isOne(uvLen, v))
- {
- inversionResult(p, bc, b, z);
- return;
- }
+ F[lenFG - 2] |= fn << 30;
+ G[lenFG - 2] |= gn << 30;
+ --lenFG;
}
}
+
+ int signF = F[lenFG - 1] >> 31;
+
+ /*
+ * D is in the range (-2.M, M). First, conditionally add M if D is negative, to bring it
+ * into the range (-M, M). Then normalize by conditionally negating (according to signF)
+ * and/or then adding M, to bring it into the range [0, M).
+ */
+ int signD = D[lenDE - 1] >> 31;
+ if (signD < 0)
+ {
+ signD = add30(lenDE, D, M);
+ }
+ if (signF < 0)
+ {
+ signD = negate30(lenDE, D);
+ signF = negate30(lenFG, F);
+ }
+// assert 0 == signF;
+
+ if (!Nat.isOne(lenFG, F))
+ {
+ return false;
+ }
+
+ if (signD < 0)
+ {
+ signD = add30(lenDE, D, M);
+ }
+// assert 0 == signD;
+
+ decode30(bits, D, 0, z, 0);
+// assert !Nat.gte(len32, z, m);
+
+ return true;
}
public static int[] random(int[] p)
@@ -116,88 +232,358 @@ public abstract class Mod
return s;
}
- public static void add(int[] p, int[] x, int[] y, int[] z)
+ /** @deprecated Will be removed. */
+ public static void subtract(int[] p, int[] x, int[] y, int[] z)
{
int len = p.length;
- int c = Nat.add(len, x, y, z);
+ int c = Nat.sub(len, x, y, z);
if (c != 0)
{
- Nat.subFrom(len, p, z);
+ Nat.addTo(len, p, z);
}
}
- public static void subtract(int[] p, int[] x, int[] y, int[] z)
+ private static int add30(int len30, int[] D, int[] M)
{
- int len = p.length;
- int c = Nat.sub(len, x, y, z);
- if (c != 0)
+// assert len30 > 0;
+// assert D.length >= len30;
+// assert M.length >= len30;
+
+ int c = 0, last = len30 - 1;
+ for (int i = 0; i < last; ++i)
{
- Nat.addTo(len, p, z);
+ c += D[i] + M[i];
+ D[i] = c & M30; c >>= 30;
}
+ c += D[last] + M[last];
+ D[last] = c; c >>= 30;
+ return c;
}
- private static void inversionResult(int[] p, int ac, int[] a, int[] z)
+ private static void cnegate30(int len30, int cond, int[] D)
{
- if (ac < 0)
+// assert len30 > 0;
+// assert D.length >= len30;
+
+ int c = 0, last = len30 - 1;
+ for (int i = 0; i < last; ++i)
{
- Nat.add(p.length, a, p, z);
+ c += (D[i] ^ cond) - cond;
+ D[i] = c & M30; c >>= 30;
}
- else
+ c += (D[last] ^ cond) - cond;
+ D[last] = c;
+ }
+
+ private static void cnormalize30(int len30, int condNegate, int[] D, int[] M)
+ {
+// assert len30 > 0;
+// assert D.length >= len30;
+// assert M.length >= len30;
+
+ int last = len30 - 1;
+
{
- System.arraycopy(a, 0, z, 0, p.length);
+ int c = 0, condAdd = D[last] >> 31;
+ for (int i = 0; i < last; ++i)
+ {
+ int di = D[i] + (M[i] & condAdd);
+ di = (di ^ condNegate) - condNegate;
+ c += di; D[i] = c & M30; c >>= 30;
+ }
+ {
+ int di = D[last] + (M[last] & condAdd);
+ di = (di ^ condNegate) - condNegate;
+ c += di; D[last] = c;
+ }
+ }
+
+ {
+ int c = 0, condAdd = D[last] >> 31;
+ for (int i = 0; i < last; ++i)
+ {
+ int di = D[i] + (M[i] & condAdd);
+ c += di; D[i] = c & M30; c >>= 30;
+ }
+ {
+ int di = D[last] + (M[last] & condAdd);
+ c += di; D[last] = c;
+ }
+// assert c >> 30 == 0;
}
}
- private static int inversionStep(int[] p, int[] u, int uLen, int[] x, int xc)
+ private static void decode30(int bits, int[] x, int xOff, int[] z, int zOff)
{
- int len = p.length;
- int count = 0;
- while (u[0] == 0)
+// assert bits > 0;
+// assert x != z;
+
+ int avail = 0;
+ long data = 0L;
+
+ while (bits > 0)
{
- Nat.shiftDownWord(uLen, u, 0);
- count += 32;
+ while (avail < Math.min(32, bits))
+ {
+ data |= (long)x[xOff++] << avail;
+ avail += 30;
+ }
+
+ z[zOff++] = (int)data; data >>>= 32;
+ avail -= 32;
+ bits -= 32;
+ }
+ }
+
+ private static int divsteps30(int eta, int f0, int g0, int[] t)
+ {
+ int u = 1, v = 0, q = 0, r = 1;
+ int f = f0, g = g0;
+
+ for (int i = 0; i < 30; ++i)
+ {
+// assert (f & 1) == 1;
+// assert (u * f0 + v * g0) == f << i;
+// assert (q * f0 + r * g0) == g << i;
+
+ int c1 = eta >> 31;
+ int c2 = -(g & 1);
+
+ int x = (f ^ c1) - c1;
+ int y = (u ^ c1) - c1;
+ int z = (v ^ c1) - c1;
+
+ g += x & c2;
+ q += y & c2;
+ r += z & c2;
+
+ c1 &= c2;
+ eta = (eta ^ c1) - (c1 + 1);
+
+ f += g & c1;
+ u += q & c1;
+ v += r & c1;
+
+ g >>= 1;
+ u <<= 1;
+ v <<= 1;
}
+ t[0] = u;
+ t[1] = v;
+ t[2] = q;
+ t[3] = r;
+
+ return eta;
+ }
+
+ private static int divsteps30Var(int eta, int f0, int g0, int[] t)
+ {
+ int u = 1, v = 0, q = 0, r = 1;
+ int f = f0, g = g0, m, w, x, y, z;
+ int i = 30, limit, zeros;
+
+ for (;;)
{
- int zeroes = getTrailingZeroes(u[0]);
- if (zeroes > 0)
+ // Use a sentinel bit to count zeros only up to i.
+ zeros = Integers.numberOfTrailingZeros(g | (-1 << i));
+
+ g >>= zeros;
+ u <<= zeros;
+ v <<= zeros;
+ eta -= zeros;
+ i -= zeros;
+
+ if (i <= 0)
+ {
+ break;
+ }
+
+// assert (f & 1) == 1;
+// assert (g & 1) == 1;
+// assert (u * f0 + v * g0) == f << (30 - i);
+// assert (q * f0 + r * g0) == g << (30 - i);
+
+ if (eta < 0)
{
- Nat.shiftDownBits(uLen, u, zeroes, 0);
- count += zeroes;
+ eta = -eta;
+ x = f; f = g; g = -x;
+ y = u; u = q; q = -y;
+ z = v; v = r; r = -z;
+
+ // Handle up to 6 divsteps at once, subject to eta and i.
+ limit = (eta + 1) > i ? i : (eta + 1);
+ m = (-1 >>> (32 - limit)) & 63;
+
+ w = (f * g * (f * f - 2)) & m;
+ }
+ else
+ {
+ // Handle up to 4 divsteps at once, subject to eta and i.
+ limit = (eta + 1) > i ? i : (eta + 1);
+ m = (-1 >>> (32 - limit)) & 15;
+
+ w = f + (((f + 1) & 4) << 1);
+ w = (-w * g) & m;
}
+
+ g += f * w;
+ q += u * w;
+ r += v * w;
+
+// assert (g & m) == 0;
}
- for (int i = 0; i < count; ++i)
+ t[0] = u;
+ t[1] = v;
+ t[2] = q;
+ t[3] = r;
+
+ return eta;
+ }
+
+ private static void encode30(int bits, int[] x, int xOff, int[] z, int zOff)
+ {
+// assert bits > 0;
+// assert x != z;
+
+ int avail = 0;
+ long data = 0L;
+
+ while (bits > 0)
{
- if ((x[0] & 1) != 0)
+ if (avail < Math.min(30, bits))
{
- if (xc < 0)
- {
- xc += Nat.addTo(len, p, x);
- }
- else
- {
- xc += Nat.subFrom(len, p, x);
- }
+ data |= (x[xOff++] & M32L) << avail;
+ avail += 32;
}
-// assert xc == 0 || xc == 1;
- Nat.shiftDownBit(len, x, xc);
+ z[zOff++] = (int)data & M30; data >>>= 30;
+ avail -= 30;
+ bits -= 30;
}
-
- return xc;
}
- private static int getTrailingZeroes(int x)
+ private static int getMaximumDivsteps(int bits)
+ {
+ return (49 * bits + (bits < 46 ? 80 : 47)) / 17;
+ }
+
+ private static int negate30(int len30, int[] D)
{
-// assert x != 0;
+// assert len30 > 0;
+// assert D.length >= len30;
- int count = 0;
- while ((x & 1) == 0)
+ int c = 0, last = len30 - 1;
+ for (int i = 0; i < last; ++i)
{
- x >>>= 1;
- ++count;
+ c -= D[i];
+ D[i] = c & M30; c >>= 30;
}
- return count;
+ c -= D[last];
+ D[last] = c; c >>= 30;
+ return c;
+ }
+
+ private static void updateDE30(int len30, int[] D, int[] E, int[] t, int m0Inv32, int[] M)
+ {
+// assert len30 > 0;
+// assert D.length >= len30;
+// assert E.length >= len30;
+// assert M.length >= len30;
+// assert m0Inv32 * M[0] == 1;
+
+ final int u = t[0], v = t[1], q = t[2], r = t[3];
+ int di, ei, i, md, me, mi, sd, se;
+ long cd, ce;
+
+ /*
+ * We accept D (E) in the range (-2.M, M) and conceptually add the modulus to the input
+ * value if it is initially negative. Instead of adding it explicitly, we add u and/or v (q
+ * and/or r) to md (me).
+ */
+ sd = D[len30 - 1] >> 31;
+ se = E[len30 - 1] >> 31;
+
+ md = (u & sd) + (v & se);
+ me = (q & sd) + (r & se);
+
+ mi = M[0];
+ di = D[0];
+ ei = E[0];
+
+ cd = (long)u * di + (long)v * ei;
+ ce = (long)q * di + (long)r * ei;
+
+ /*
+ * Subtract from md/me an extra term in the range [0, 2^30) such that the low 30 bits of the
+ * intermediate D/E values will be 0, allowing clean division by 2^30. The final D/E are
+ * thus in the range (-2.M, M), consistent with the input constraint.
+ */
+ md -= (m0Inv32 * (int)cd + md) & M30;
+ me -= (m0Inv32 * (int)ce + me) & M30;
+
+ cd += (long)mi * md;
+ ce += (long)mi * me;
+
+// assert ((int)cd & M30) == 0;
+// assert ((int)ce & M30) == 0;
+
+ cd >>= 30;
+ ce >>= 30;
+
+ for (i = 1; i < len30; ++i)
+ {
+ mi = M[i];
+ di = D[i];
+ ei = E[i];
+
+ cd += (long)u * di + (long)v * ei + (long)mi * md;
+ ce += (long)q * di + (long)r * ei + (long)mi * me;
+
+ D[i - 1] = (int)cd & M30; cd >>= 30;
+ E[i - 1] = (int)ce & M30; ce >>= 30;
+ }
+
+ D[len30 - 1] = (int)cd;
+ E[len30 - 1] = (int)ce;
+ }
+
+ private static void updateFG30(int len30, int[] F, int[] G, int[] t)
+ {
+// assert len30 > 0;
+// assert F.length >= len30;
+// assert G.length >= len30;
+
+ final int u = t[0], v = t[1], q = t[2], r = t[3];
+ int fi, gi, i;
+ long cf, cg;
+
+ fi = F[0];
+ gi = G[0];
+
+ cf = (long)u * fi + (long)v * gi;
+ cg = (long)q * fi + (long)r * gi;
+
+// assert ((int)cf & M30) == 0;
+// assert ((int)cg & M30) == 0;
+
+ cf >>= 30;
+ cg >>= 30;
+
+ for (i = 1; i < len30; ++i)
+ {
+ fi = F[i];
+ gi = G[i];
+
+ cf += (long)u * fi + (long)v * gi;
+ cg += (long)q * fi + (long)r * gi;
+
+ F[i - 1] = (int)cf & M30; cf >>= 30;
+ G[i - 1] = (int)cg & M30; cg >>= 30;
+ }
+
+ F[len30 - 1] = (int)cf;
+ G[len30 - 1] = (int)cg;
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-03 16:10:19 +0000