Skip to content

Instantly share code, notes, and snippets.

@sander
Last active October 26, 2022 20:13
Show Gist options
  • Save sander/12906612706c10388ad08c30b9119b97 to your computer and use it in GitHub Desktop.
Save sander/12906612706c10388ad08c30b9119b97 to your computer and use it in GitHub Desktop.
Schnorr Non-interactive Zero-Knowledge Proof in 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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment