java_src/src/test/java/com/google/crypto/tink/subtle/Field25519Test.java

// Copyright 2017 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
////////////////////////////////////////////////////////////////////////////////

package com.google.crypto.tink.subtle;

import static com.google.crypto.tink.subtle.Field25519.FIELD_LEN;
import static com.google.crypto.tink.subtle.Field25519.LIMB_CNT;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;

import java.math.BigInteger;
import java.security.SecureRandom;
import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

/**
 * Unit tests for {@link Field25519}.
 *
 * <p>TODO(quannguyen): Add more tests. Note that several functions assume that the inputs are in
 * reduced forms, so testing them don't guarantee that its uses are safe. There may be integer
 * overflow when they aren't used correctly.
 */
@RunWith(JUnit4.class)
public final class Field25519Test {
  /**
   * The idea of basic tests is simple. We generate random numbers, make computations with
   * Field25519 and compare the results with Java BigInteger.
   */
  private static final int NUM_BASIC_TESTS = 1024;

  private static final SecureRandom rand = new SecureRandom();
  private static final BigInteger P =
      BigInteger.valueOf(2).pow(255).subtract(BigInteger.valueOf(19));
  BigInteger[] x = new BigInteger[NUM_BASIC_TESTS];
  BigInteger[] y = new BigInteger[NUM_BASIC_TESTS];

  @Before
  public void setUp() {
    for (int i = 0; i < NUM_BASIC_TESTS; i++) {
      x[i] = (new BigInteger(FIELD_LEN * 8, rand)).mod(P);
      y[i] = (new BigInteger(FIELD_LEN * 8, rand)).mod(P);
    }
  }

  @Test
  public void testBasicSum() {
    for (int i = 0; i < NUM_BASIC_TESTS; i++) {
      BigInteger expectedResult = x[i].add(y[i]).mod(P);
      byte[] xBytes = toLittleEndian(x[i]);
      byte[] yBytes = toLittleEndian(y[i]);
      long[] output = new long[LIMB_CNT * 2 + 1];
      Field25519.sum(output, Field25519.expand(xBytes), Field25519.expand(yBytes));
      Field25519.reduceCoefficients(output);
      BigInteger result = new BigInteger(reverse(Field25519.contract(output)));
      assertEquals("Sum x[i] + y[i]: " + x[i] + "+" + y[i], expectedResult, result);
    }
  }

  @Test
  public void testBasicSub() {
    for (int i = 0; i < NUM_BASIC_TESTS; i++) {
      BigInteger expectedResult = x[i].subtract(y[i]).mod(P);
      byte[] xBytes = toLittleEndian(x[i]);
      byte[] yBytes = toLittleEndian(y[i]);
      long[] output = new long[LIMB_CNT * 2 + 1];
      Field25519.sub(output, Field25519.expand(xBytes), Field25519.expand(yBytes));
      Field25519.reduceCoefficients(output);
      BigInteger result = new BigInteger(reverse(Field25519.contract(output)));
      assertEquals("Subtraction x[i] - y[i]: " + x[i] + "-" + y[i], expectedResult, result);
    }
  }

  @Test
  public void testBasicProduct() {
    for (int i = 0; i < NUM_BASIC_TESTS; i++) {
      BigInteger expectedResult = x[i].multiply(y[i]).mod(P);
      byte[] xBytes = toLittleEndian(x[i]);
      byte[] yBytes = toLittleEndian(y[i]);
      long[] output = new long[LIMB_CNT * 2 + 1];
      Field25519.product(output, Field25519.expand(xBytes), Field25519.expand(yBytes));
      Field25519.reduceSizeByModularReduction(output);
      Field25519.reduceCoefficients(output);
      BigInteger result = new BigInteger(reverse(Field25519.contract(output)));
      assertEquals("Product x[i] * y[i]: " + x[i] + "*" + y[i], expectedResult, result);
    }
  }

  @Test
  public void testBasicMult() {
    for (int i = 0; i < NUM_BASIC_TESTS; i++) {
      BigInteger expectedResult = x[i].multiply(y[i]).mod(P);
      byte[] xBytes = toLittleEndian(x[i]);
      byte[] yBytes = toLittleEndian(y[i]);
      long[] output = new long[LIMB_CNT * 2 + 1];
      Field25519.mult(output, Field25519.expand(xBytes), Field25519.expand(yBytes));
      BigInteger result = new BigInteger(reverse(Field25519.contract(output)));
      assertEquals("Multiplication x[i] * y[i]: " + x[i] + "*" + y[i], expectedResult, result);
    }
  }

  @Test
  public void testBasicScalarProduct() {
    final long scalar = 121665;
    for (int i = 0; i < NUM_BASIC_TESTS; i++) {
      BigInteger expectedResult = x[i].multiply(BigInteger.valueOf(scalar)).mod(P);
      byte[] xBytes = toLittleEndian(x[i]);
      long[] output = new long[LIMB_CNT * 2 + 1];
      Field25519.scalarProduct(output, Field25519.expand(xBytes), scalar);
      Field25519.reduceSizeByModularReduction(output);
      Field25519.reduceCoefficients(output);
      BigInteger result = new BigInteger(reverse(Field25519.contract(output)));
      assertEquals("Scalar product x[i] * 10 " + x[i] + "*" + 10, expectedResult, result);
    }
  }

  @Test
  public void testBasicSquare() {
    for (int i = 0; i < NUM_BASIC_TESTS; i++) {
      BigInteger expectedResult = x[i].multiply(x[i]).mod(P);
      byte[] xBytes = toLittleEndian(x[i]);
      long[] output = new long[LIMB_CNT * 2 + 1];
      Field25519.square(output, Field25519.expand(xBytes));
      Field25519.reduceSizeByModularReduction(output);
      Field25519.reduceCoefficients(output);
      BigInteger result = new BigInteger(reverse(Field25519.contract(output)));
      assertEquals("Square x[i] * x[i]: " + x[i] + "*" + x[i], expectedResult, result);
    }
  }

  @Test
  public void testBasicInverse() {
    for (int i = 0; i < NUM_BASIC_TESTS; i++) {
      BigInteger expectedResult = x[i].modInverse(P);
      byte[] xBytes = toLittleEndian(x[i]);
      long[] output = new long[LIMB_CNT * 2 + 1];
      Field25519.inverse(output, Field25519.expand(xBytes));
      BigInteger result = new BigInteger(reverse(Field25519.contract(output)));
      assertEquals("Inverse: x[i]^(-1) mod P: " + x[i], expectedResult, result);
    }
  }

  @Test
  public void testContractExpand() {
    for (int i = 0; i < NUM_BASIC_TESTS; i++) {
      byte[] xBytes = toLittleEndian(x[i]);
      byte[] result = Field25519.contract(Field25519.expand(xBytes));
      assertArrayEquals(xBytes, result);
    }
  }

  private byte[] toLittleEndian(BigInteger n) {
    byte[] b = new byte[32];
    byte[] nBytes = n.toByteArray();
    System.arraycopy(nBytes, 0, b, 32 - nBytes.length, nBytes.length);
    for (int i = 0; i < b.length / 2; i++) {
      byte t = b[i];
      b[i] = b[b.length - i - 1];
      b[b.length - i - 1] = t;
    }
    return b;
  }

  private byte[] reverse(byte[] x) {
    byte[] r = new byte[x.length];
    for (int i = 0; i < x.length; i++) {
      r[i] = x[x.length - i - 1];
    }
    return r;
  }
}