Schnorr Non-interactive Zero-Knowledge Proof in Java

ZeroKnowledgeProof.java

///usr/bin/env jbang "$0" "$@" ; exit $?

//DEPS org.bouncycastle:bcprov-jdk18on:1.72

import org.bouncycastle.crypto.digests.SHA256Digest;
import org.bouncycastle.jce.ECNamedCurveTable;
import org.bouncycastle.jce.spec.ECParameterSpec;
import org.bouncycastle.math.ec.ECPoint;

import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.nio.charset.StandardCharsets;
import java.security.SecureRandom;
import java.util.Objects;

import static java.math.BigInteger.ONE;
import static java.math.BigInteger.ZERO;

/**
 * Unevaluated prototype of IETF RFC 8235 §3.3 with §4.
 */
public record ZeroKnowledgeProof(BigInteger challenge, BigInteger response) {

  public static void main(String... args) {
    var spec = new ParameterSpec(
        ECNamedCurveTable.getParameterSpec("prime256v1"),
        "myUserName".getBytes(StandardCharsets.UTF_8),
        new byte[0]
    );
    var secret = new BigInteger(1, "mySecretValue".getBytes(StandardCharsets.UTF_8));
    var proof = spec.proveKnowledgeOf(secret);
    var publicKey = spec.generator.multiply(secret);
    System.out.println(spec.verify(proof, publicKey));
  }

  public ZeroKnowledgeProof {
    Objects.requireNonNull(challenge);
    Objects.requireNonNull(response);
  }

  public record ParameterSpec(ECParameterSpec spec, ECPoint generator, byte[] userId, byte[] otherInfo) {

    public ParameterSpec {
      Objects.requireNonNull(spec);
      Objects.requireNonNull(generator);
      Objects.requireNonNull(userId);
      Objects.requireNonNull(otherInfo);

      if (userId.length == 0) {
        throw new IllegalArgumentException("Prevent replay with userId");
      }

      if (!generator.getCurve().equals(spec.getCurve()) || generator.multiply(spec.getH()).isInfinity()) {
        throw new IllegalArgumentException("Illegal generator");
      }
    }

    public ParameterSpec(ECParameterSpec spec, byte[] userId, byte[] otherInfo) {
      this(spec, spec.getG(), userId, otherInfo);
    }

    public ZeroKnowledgeProof proveKnowledgeOf(BigInteger secret) {
      var a = secret;
      var G = generator;
      var n = spec.getN();
      var A = G.multiply(a);

      while (true) {
        var v = choose(n);
        var V = G.multiply(v);
        var c = new BigInteger(1, commitment(G, V, A, userId, otherInfo));
        var r = v.subtract(c.multiply(a)).mod(n);
        if (c.mod(n).compareTo(ZERO) != 0 && r.compareTo(ZERO) != 0) {
          return new ZeroKnowledgeProof(c, r);
        }
      }
    }

    public boolean verify(ZeroKnowledgeProof proof, ECPoint publicKey) {
      var A = publicKey;
      if (A.getCurve().equals(spec.getCurve()) && !A.multiply(spec.getH()).isInfinity()) {
        var G = generator;
        var V = G.multiply(proof.response).add(A.multiply(proof.challenge));
        return new BigInteger(1, commitment(G, V, A, userId, otherInfo)).compareTo(proof.challenge) == 0;
      } else {
        return false;
      }
    }
  }

  /**
   * BSI TR-03111 v2.10 § 4.1.1 Algorithm 2
   */
  private static BigInteger choose(BigInteger n) {
    var value = new byte[n.bitLength() / 8];
    new SecureRandom().nextBytes(value);
    return new BigInteger(1, value).mod(n.subtract(ONE)).add(ONE);
  }

  /**
   * Assumes input is not longer than Integer.MAX_VALUE, which is generally true on JVM.
   */
  private static void update(SHA256Digest digest, byte[] in) {
    var prefix = ByteBuffer.allocate(Integer.SIZE / Byte.SIZE).order(ByteOrder.LITTLE_ENDIAN).putInt(in.length).array();
    digest.update(prefix, 0, prefix.length);
    digest.update(in, 0, in.length);
  }

  private static void update(SHA256Digest digest, ECPoint point) {
    var normalized = point.normalize();
    update(digest, normalized.getXCoord().getEncoded());
    update(digest, normalized.getYCoord().getEncoded());
  }

  /**
   * Uses an injective concatenation function to hash the input values
   */
  private static byte[] commitment(ECPoint G, ECPoint V, ECPoint A, byte[] userId, byte[] otherInfo) {
    var digest = new SHA256Digest();
    var out = new byte[digest.getByteLength()];

    update(digest, G);
    update(digest, V);
    update(digest, A);
    update(digest, userId);
    update(digest, otherInfo);

    digest.doFinal(out, 0);

    return out;
  }
}