44 changes: 22 additions & 22 deletions core/src/main/java/org/bouncycastle/math/raw/Nat256.java
Original file line number Diff line number Diff line change
Expand Up @@ -926,8 +926,8 @@ public static void square(int[] x, int[] zz)
}

long x_3 = x[3] & M;
long zz_5 = zz[5] & M;
long zz_6 = zz[6] & M;
long zz_5 = (zz[5] & M) + (zz_4 >>> 32); zz_4 &= M;
long zz_6 = (zz[6] & M) + (zz_5 >>> 32); zz_5 &= M;
{
zz_3 += x_3 * x_0;
w = (int)zz_3;
Expand All @@ -941,8 +941,8 @@ public static void square(int[] x, int[] zz)
}

long x_4 = x[4] & M;
long zz_7 = zz[7] & M;
long zz_8 = zz[8] & M;
long zz_7 = (zz[7] & M) + (zz_6 >>> 32); zz_6 &= M;
long zz_8 = (zz[8] & M) + (zz_7 >>> 32); zz_7 &= M;
{
zz_4 += x_4 * x_0;
w = (int)zz_4;
Expand All @@ -958,8 +958,8 @@ public static void square(int[] x, int[] zz)
}

long x_5 = x[5] & M;
long zz_9 = zz[9] & M;
long zz_10 = zz[10] & M;
long zz_9 = (zz[9] & M) + (zz_8 >>> 32); zz_8 &= M;
long zz_10 = (zz[10] & M) + (zz_9 >>> 32); zz_9 &= M;
{
zz_5 += x_5 * x_0;
w = (int)zz_5;
Expand All @@ -977,8 +977,8 @@ public static void square(int[] x, int[] zz)
}

long x_6 = x[6] & M;
long zz_11 = zz[11] & M;
long zz_12 = zz[12] & M;
long zz_11 = (zz[11] & M) + (zz_10 >>> 32); zz_10 &= M;
long zz_12 = (zz[12] & M) + (zz_11 >>> 32); zz_11 &= M;
{
zz_6 += x_6 * x_0;
w = (int)zz_6;
Expand All @@ -998,8 +998,8 @@ public static void square(int[] x, int[] zz)
}

long x_7 = x[7] & M;
long zz_13 = zz[13] & M;
long zz_14 = zz[14] & M;
long zz_13 = (zz[13] & M) + (zz_12 >>> 32); zz_12 &= M;
long zz_14 = (zz[14] & M) + (zz_13 >>> 32); zz_13 &= M;
{
zz_7 += x_7 * x_0;
w = (int)zz_7;
Expand Down Expand Up @@ -1035,7 +1035,7 @@ public static void square(int[] x, int[] zz)
w = (int)zz_14;
zz[14] = (w << 1) | c;
c = w >>> 31;
w = zz[15] + (int)(zz_14 >> 32);
w = zz[15] + (int)(zz_14 >>> 32);
zz[15] = (w << 1) | c;
}

Expand Down Expand Up @@ -1090,8 +1090,8 @@ public static void square(int[] x, int xOff, int[] zz, int zzOff)
}

long x_3 = x[xOff + 3] & M;
long zz_5 = zz[zzOff + 5] & M;
long zz_6 = zz[zzOff + 6] & M;
long zz_5 = (zz[zzOff + 5] & M) + (zz_4 >>> 32); zz_4 &= M;
long zz_6 = (zz[zzOff + 6] & M) + (zz_5 >>> 32); zz_5 &= M;
{
zz_3 += x_3 * x_0;
w = (int)zz_3;
Expand All @@ -1105,8 +1105,8 @@ public static void square(int[] x, int xOff, int[] zz, int zzOff)
}

long x_4 = x[xOff + 4] & M;
long zz_7 = zz[zzOff + 7] & M;
long zz_8 = zz[zzOff + 8] & M;
long zz_7 = (zz[zzOff + 7] & M) + (zz_6 >>> 32); zz_6 &= M;
long zz_8 = (zz[zzOff + 8] & M) + (zz_7 >>> 32); zz_7 &= M;
{
zz_4 += x_4 * x_0;
w = (int)zz_4;
Expand All @@ -1122,8 +1122,8 @@ public static void square(int[] x, int xOff, int[] zz, int zzOff)
}

long x_5 = x[xOff + 5] & M;
long zz_9 = zz[zzOff + 9] & M;
long zz_10 = zz[zzOff + 10] & M;
long zz_9 = (zz[zzOff + 9] & M) + (zz_8 >>> 32); zz_8 &= M;
long zz_10 = (zz[zzOff + 10] & M) + (zz_9 >>> 32); zz_9 &= M;
{
zz_5 += x_5 * x_0;
w = (int)zz_5;
Expand All @@ -1141,8 +1141,8 @@ public static void square(int[] x, int xOff, int[] zz, int zzOff)
}

long x_6 = x[xOff + 6] & M;
long zz_11 = zz[zzOff + 11] & M;
long zz_12 = zz[zzOff + 12] & M;
long zz_11 = (zz[zzOff + 11] & M) + (zz_10 >>> 32); zz_10 &= M;
long zz_12 = (zz[zzOff + 12] & M) + (zz_11 >>> 32); zz_11 &= M;
{
zz_6 += x_6 * x_0;
w = (int)zz_6;
Expand All @@ -1162,8 +1162,8 @@ public static void square(int[] x, int xOff, int[] zz, int zzOff)
}

long x_7 = x[xOff + 7] & M;
long zz_13 = zz[zzOff + 13] & M;
long zz_14 = zz[zzOff + 14] & M;
long zz_13 = (zz[zzOff + 13] & M) + (zz_12 >>> 32); zz_12 &= M;
long zz_14 = (zz[zzOff + 14] & M) + (zz_13 >>> 32); zz_13 &= M;
{
zz_7 += x_7 * x_0;
w = (int)zz_7;
Expand Down Expand Up @@ -1199,7 +1199,7 @@ public static void square(int[] x, int xOff, int[] zz, int zzOff)
w = (int)zz_14;
zz[zzOff + 14] = (w << 1) | c;
c = w >>> 31;
w = zz[zzOff + 15] + (int)(zz_14 >> 32);
w = zz[zzOff + 15] + (int)(zz_14 >>> 32);
zz[zzOff + 15] = (w << 1) | c;
}

Expand Down
Original file line number Diff line number Diff line change
@@ -0,0 +1,175 @@
package org.bouncycastle.math.ec.custom.sec.test;

import java.math.BigInteger;
import java.security.SecureRandom;

import org.bouncycastle.asn1.sec.SECObjectIdentifiers;
import org.bouncycastle.asn1.x9.X9ECParameters;
import org.bouncycastle.crypto.ec.CustomNamedCurves;
import org.bouncycastle.math.ec.ECFieldElement;
import org.bouncycastle.math.raw.Nat256;

import junit.framework.TestCase;

public class SecP256R1FieldTest extends TestCase
{
private static final SecureRandom RANDOM = new SecureRandom();

private static final X9ECParameters DP = CustomNamedCurves
.getByOID(SECObjectIdentifiers.secp256r1);
private static final BigInteger Q = DP.getCurve().getField().getCharacteristic();

public void testMultiply1()
{
int COUNT = 1000;

for (int i = 0; i < COUNT; ++i)
{
ECFieldElement x = generateMultiplyInput_Random();
ECFieldElement y = generateMultiplyInput_Random();

BigInteger X = x.toBigInteger(), Y = y.toBigInteger();
BigInteger R = X.multiply(Y).mod(Q);

ECFieldElement z = x.multiply(y);
BigInteger Z = z.toBigInteger();

assertEquals(R, Z);
}
}

public void testMultiply2()
{
int COUNT = 100;
ECFieldElement[] inputs = new ECFieldElement[COUNT];
BigInteger[] INPUTS = new BigInteger[COUNT];

for (int i = 0; i < inputs.length; ++i)
{
inputs[i] = generateMultiplyInput_Random();
INPUTS[i] = inputs[i].toBigInteger();
}

for (int j = 0; j < inputs.length; ++j)
{
for (int k = 0; k < inputs.length; ++k)
{
BigInteger R = INPUTS[j].multiply(INPUTS[k]).mod(Q);

ECFieldElement z = inputs[j].multiply(inputs[k]);
BigInteger Z = z.toBigInteger();

assertEquals(R, Z);
}
}
}

public void testSquare()
{
int COUNT = 1000;

for (int i = 0; i < COUNT; ++i)
{
ECFieldElement x = generateMultiplyInput_Random();

BigInteger X = x.toBigInteger();
BigInteger R = X.multiply(X).mod(Q);

ECFieldElement z = x.square();
BigInteger Z = z.toBigInteger();

assertEquals(R, Z);
}
}

/**
* Test multiplication with specifically selected values that triggered a bug in the modular
* reduction in OpenSSL (last affected version 0.9.8g).
*
* See "Practical realisation and elimination of an ECC-related software bug attack", B. B.
* Brumley, M. Barbarosa, D. Page, F. Vercauteren.
*/
public void testMultiply_OpenSSLBug()
{
int COUNT = 100;

for (int i = 0; i < COUNT; ++i)
{
ECFieldElement x = generateMultiplyInputA_OpenSSLBug();
ECFieldElement y = generateMultiplyInputB_OpenSSLBug();

BigInteger X = x.toBigInteger(), Y = y.toBigInteger();
BigInteger R = X.multiply(Y).mod(Q);

ECFieldElement z = x.multiply(y);
BigInteger Z = z.toBigInteger();

assertEquals(R, Z);
}
}

/**
* Test squaring with specifically selected values that triggered a bug in the modular reduction
* in OpenSSL (last affected version 0.9.8g).
*
* See "Practical realisation and elimination of an ECC-related software bug attack", B. B.
* Brumley, M. Barbarosa, D. Page, F. Vercauteren.
*/
public void testSquare_OpenSSLBug()
{
int COUNT = 100;

for (int i = 0; i < COUNT; ++i)
{
ECFieldElement x = generateSquareInput_OpenSSLBug();

BigInteger X = x.toBigInteger();
BigInteger R = X.multiply(X).mod(Q);

ECFieldElement z = x.square();
BigInteger Z = z.toBigInteger();

assertEquals(R, Z);
}
}

private ECFieldElement fe(BigInteger x)
{
return DP.getCurve().fromBigInteger(x);
}

private ECFieldElement generateMultiplyInput_Random()
{
return fe(new BigInteger(DP.getCurve().getFieldSize() + 32, RANDOM).mod(Q));
}

private ECFieldElement generateMultiplyInputA_OpenSSLBug()
{
int[] x = Nat256.create();
x[0] = RANDOM.nextInt() >>> 1;
x[4] = 3;
x[7] = -1;

return fe(Nat256.toBigInteger(x));
}

private ECFieldElement generateMultiplyInputB_OpenSSLBug()
{
int[] x = Nat256.create();
x[0] = RANDOM.nextInt() >>> 1;
x[3] = 1;
x[7] = -1;

return fe(Nat256.toBigInteger(x));
}

private ECFieldElement generateSquareInput_OpenSSLBug()
{
int[] x = Nat256.create();
x[0] = RANDOM.nextInt() >>> 1;
x[4] = 2;
x[7] = -1;

return fe(Nat256.toBigInteger(x));
}
}
Original file line number Diff line number Diff line change
@@ -0,0 +1,140 @@
package org.bouncycastle.math.ec.custom.sec.test;

import java.math.BigInteger;
import java.security.SecureRandom;

import org.bouncycastle.asn1.sec.SECObjectIdentifiers;
import org.bouncycastle.asn1.x9.X9ECParameters;
import org.bouncycastle.crypto.ec.CustomNamedCurves;
import org.bouncycastle.math.ec.ECFieldElement;
import org.bouncycastle.math.raw.Nat;

import junit.framework.TestCase;

public class SecP384R1FieldTest extends TestCase
{
private static final SecureRandom RANDOM = new SecureRandom();

private static final X9ECParameters DP = CustomNamedCurves
.getByOID(SECObjectIdentifiers.secp384r1);
private static final BigInteger Q = DP.getCurve().getField().getCharacteristic();

public void testMultiply1()
{
int COUNT = 1000;

for (int i = 0; i < COUNT; ++i)
{
ECFieldElement x = generateMultiplyInput_Random();
ECFieldElement y = generateMultiplyInput_Random();

BigInteger X = x.toBigInteger(), Y = y.toBigInteger();
BigInteger R = X.multiply(Y).mod(Q);

ECFieldElement z = x.multiply(y);
BigInteger Z = z.toBigInteger();

assertEquals(R, Z);
}
}

public void testMultiply2()
{
int COUNT = 100;
ECFieldElement[] inputs = new ECFieldElement[COUNT];
BigInteger[] INPUTS = new BigInteger[COUNT];

for (int i = 0; i < inputs.length; ++i)
{
inputs[i] = generateMultiplyInput_Random();
INPUTS[i] = inputs[i].toBigInteger();
}

for (int j = 0; j < inputs.length; ++j)
{
for (int k = 0; k < inputs.length; ++k)
{
BigInteger R = INPUTS[j].multiply(INPUTS[k]).mod(Q);

ECFieldElement z = inputs[j].multiply(inputs[k]);
BigInteger Z = z.toBigInteger();

assertEquals(R, Z);
}
}
}

public void testSquare()
{
int COUNT = 1000;

for (int i = 0; i < COUNT; ++i)
{
ECFieldElement x = generateMultiplyInput_Random();

BigInteger X = x.toBigInteger();
BigInteger R = X.multiply(X).mod(Q);

ECFieldElement z = x.square();
BigInteger Z = z.toBigInteger();

assertEquals(R, Z);
}
}

public void testSquare_CarryBug()
{
int COUNT = 100;

for (int i = 0; i < COUNT; ++i)
{
ECFieldElement x = generateSquareInput_CarryBug();

BigInteger X = x.toBigInteger();
BigInteger R = X.multiply(X).mod(Q);

ECFieldElement z = x.square();
BigInteger Z = z.toBigInteger();

assertEquals(R, Z);
}
}

/*
* Based on another example input demonstrating the carry propagation bug in Nat192.square, as
* reported by Joseph Friel on dev-crypto.
*/
public void testSquare_CarryBug_Reported()
{
ECFieldElement x = fe(new BigInteger("2fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd", 16));

BigInteger X = x.toBigInteger();
BigInteger R = X.multiply(X).mod(Q);

ECFieldElement z = x.square();
BigInteger Z = z.toBigInteger();

assertEquals(R, Z);
}

private ECFieldElement fe(BigInteger x)
{
return DP.getCurve().fromBigInteger(x);
}

private ECFieldElement generateMultiplyInput_Random()
{
return fe(new BigInteger(DP.getCurve().getFieldSize() + 32, RANDOM).mod(Q));
}

private ECFieldElement generateSquareInput_CarryBug()
{
int[] x = Nat.create(12);
x[0] = RANDOM.nextInt() >>> 1;
x[6] = 2;
x[10] = -1 << 16;
x[11] = -1;

return fe(Nat.toBigInteger(12, x));
}
}