Skip to content

Latest commit

 

History

History
946 lines (821 loc) · 49.6 KB

README.md

File metadata and controls

946 lines (821 loc) · 49.6 KB
Raw

JCA-Provider

A provider for the Java Cryptography Architecture. Implementations are available for the Schnorr Signature based on prime fields and elliptic curves.

1. Table of Contents

  1. Build
  2. Installation
  3. Schnorr Signatures on prime fields
  4. KeyPairGenerator Usage 1. 2048-bit prime p, 512-bit prime q 2. 1024-bit prime p, 160-bit prime q 3. 4096-bit prime p, 1024-bit prime q 4. Custom security parameter
  5. Signature Usage 1. Simple Use 2. Custom SecureRandom 3. NIO 4. Message Digest configuration 5. (Deterministic) NonceGenerators
  6. Schnorr Signatures on elliptic curves
  7. KeyPairGenerator Usage 1. Brainpool Curves 2. NIST Curves 3. SafeCurves 4. Custom Curves
  8. Signature Usage 1. Simple Use 2. Custom SecureRandom 3. NIO 4. Message Digest configuration 5. (Deterministic) NonceGenerators 6. Point Multiplication methods
  9. Links

1. Build

Maven is required to compile the library. A whole build will take some time - currently up to eight minutes on my laptop. This is mainly due to the unit tests belonging to the jca-schnorrsig and jca-ecschnorrsig sub-modules. For example, the to be tested custom domain parameter generation includes the costly search for random Schnorr Groups satisfying specified security limits. The suite for Schnorr Signatures over Elliptic Curves, however, will test every provided curve together with three different message digests and four different NonceGenerators. This results in 168 to be tested configurations for the Brainpool curves alone.

The build will need a JDK 8 since I'm using the -Xdoclint:none option to turn off the new doclint. This option doesn't exist in pre Java 8. Aside from that, the build targets JDK 7+. Use

$ mvn clean install

to build the library along with the unit tests. Instead, you might want execute

$ mvn clean install -DskipTests

to reduce the build time significantly.

TOC

2. Installation

Cryptographic Service Providers can be installed in two ways:

  • on the normal Java classpath
  • as a bundled extension

The jca-bundle sub-module builds an uber-jar with the relevant binaries.

Furthermore, a Cryptographic Service Provider (CSP) must be registered before it can be put to use. CSPs can be registered statically by editing a security properties configuration file or dynamically at runtime:

import java.security.Provider;
import java.security.Security;
...
Provider provider = new de.christofreichardt.crypto.Provider();
Security.addProvider(provider);

See the section Installing Providers of the official JCA Reference Guide for more details.

TOC

3. Schnorr Signatures on prime fields

Public domain parameter g, G = ⟨g⟩, |G| = q, p = qr + 1, p prime, q prime, H: {0,1}* → ℤq
Secret key x ∊R (ℤq)×
Public key h ≡p gx
Signing M∊{0,1}* r ∊R (ℤq)×, s ≡p gr, e ≡q H(M ‖ s), y ≡q r + ex
Signature (e,y) ∊ ℤq × ℤq
Verifying s ≡p gyh-e, check if H(M ‖ s) ≡q e holds.
Correctness gyh-e ≡p gyg-ex ≡p gy-ex ≡p gr

3.i KeyPairGenerator Usage

Key pairs can be generated by using precomputed Schnorr groups. This library provides Schnorr groups in different categories suitable for different security demands. Schnorr groups with a 2048-bit prime p and a 512-bit prime q are preset.

3.i.a 2048-bit prime p, 512-bit prime q

The subsequent example works with one of the precomputed Schnorr groups that are exhibiting default security parameters. It follows that, as mentioned above, p has 2048 bits and q has 512 bits. The KeyPairGenerator instance will select one of these groups at random.

import java.math.BigInteger;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
...
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("SchnorrSignature");
KeyPair keyPair = keyPairGenerator.generateKeyPair();
SchnorrPublicKey publicKey = (SchnorrPublicKey) keyPair.getPublic();
BigInteger q = publicKey.getSchnorrParams().getQ();
BigInteger p = publicKey.getSchnorrParams().getP();
assert q.bitLength() == 512;
assert p.bitLength() == 2048;
assert q.isProbablePrime(100);
assert p.isProbablePrime(100);
assert p.subtract(BigInteger.ONE).remainder(q).equals(BigInteger.ZERO);

3.i.b 1024-bit prime p, 160-bit prime q

Additionally, this library provides some precomputed Schnorr groups exhibiting minimal security parameters (1024-bit prime p, 160-bit prime q). This corresponds to the minimal parameter sizes of the Digital Signature Algorithm (DSA) as specified by the National Institute of Standards and Technology (NIST), see FIPS PUB 186-4 for more details. Such a group can be requested with the following code:

import java.math.BigInteger;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import de.christofreichardt.crypto.schnorrsignature.SchnorrPublicKey;
import de.christofreichardt.crypto.schnorrsignature.SchnorrSigKeyGenParameterSpec;
import de.christofreichardt.crypto.schnorrsignature.SchnorrSigKeyGenParameterSpec.Strength;
...
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("SchnorrSignature");
SchnorrSigKeyGenParameterSpec schnorrSigGenParameterSpec = new SchnorrSigKeyGenParameterSpec(Strength.MINIMAL);
keyPairGenerator.initialize(schnorrSigGenParameterSpec);
KeyPair keyPair = keyPairGenerator.generateKeyPair();
SchnorrPublicKey publicKey = (SchnorrPublicKey) keyPair.getPublic();
BigInteger q = publicKey.getSchnorrParams().getQ();
BigInteger p = publicKey.getSchnorrParams().getP();
assert q.bitLength() == 160;
assert p.bitLength() == 1024;
assert q.isProbablePrime(100);
assert p.isProbablePrime(100);
assert p.subtract(BigInteger.ONE).remainder(q).equals(BigInteger.ZERO);

3.i.c 4096-bit prime p, 1024-bit prime q

Even some groups with a 4096-bit prime p and a 1024-bit prime q can be fetched from the precomputed pool:

import java.math.BigInteger;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import de.christofreichardt.crypto.schnorrsignature.SchnorrPublicKey;
import de.christofreichardt.crypto.schnorrsignature.SchnorrSigKeyGenParameterSpec;
import de.christofreichardt.crypto.schnorrsignature.SchnorrSigKeyGenParameterSpec.Strength;
...
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("SchnorrSignature");
SchnorrSigKeyGenParameterSpec schnorrSigGenParameterSpec = new SchnorrSigKeyGenParameterSpec(Strength.STRONG);
keyPairGenerator.initialize(schnorrSigGenParameterSpec);
KeyPair keyPair = keyPairGenerator.generateKeyPair();
SchnorrPublicKey publicKey = (SchnorrPublicKey) keyPair.getPublic();
BigInteger q = publicKey.getSchnorrParams().getQ();
BigInteger p = publicKey.getSchnorrParams().getP();
assert q.bitLength() == 1024;
assert p.bitLength() == 4096;
assert q.isProbablePrime(100);
assert p.isProbablePrime(100);
assert p.subtract(BigInteger.ONE).remainder(q).equals(BigInteger.ZERO);

3.i.d Custom security parameter

If desired the KeyPairGenerator instance will compute a Schnorr group with custom security parameters from scratch. The subsequent code will try to generate a Schnorr group with a 1024-bit prime p and a 256-bit prime q. That is to say q will have 256 bit exactly but p may have some bits less than 1024. If the specified parameter should be matched exactly the last (boolean) parameter must be set to true. Dependent on the chosen security limits this computation may take some time.

import java.security.KeyPair;
import java.security.KeyPairGenerator;
import de.christofreichardt.crypto.schnorrsignature.SchnorrPublicKey;
import de.christofreichardt.crypto.schnorrsignature.SchnorrSigKeyGenParameterSpec;
...
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("SchnorrSignature");
SchnorrSigKeyGenParameterSpec schnorrSigGenParameterSpec = new SchnorrSigKeyGenParameterSpec(1024, 256, false);
keyPairGenerator.initialize(schnorrSigGenParameterSpec);
KeyPair keyPair = keyPairGenerator.generateKeyPair();
SchnorrPublicKey publicKey = (SchnorrPublicKey) keyPair.getPublic();
BigInteger q = publicKey.getSchnorrParams().getQ();
BigInteger p = publicKey.getSchnorrParams().getP();
assert q.bitLength() == 256;
assert q.isProbablePrime(100);
assert p.isProbablePrime(100);
assert p.subtract(BigInteger.ONE).remainder(q).equals(BigInteger.ZERO);

3.ii Signature Usage

Once you have generated a key pair, you can request a Signature instance either for the creation of a digital signature or for its verification.

3.ii.a Simple use

The subsequent example will use the default hash function (SHA-256). The nonce r needed for the computation of the digital signature will be generated by an internal SecureRandom instance which will seed itself upon the first request of random bytes. Hence if you sign the same document twice, both digital signature differ with high probability.

import java.io.File;
import java.nio.file.Files;
import java.security.KeyPair;
import java.security.Signature;
...
KeyPair keyPair = ...
File file = new File("loremipsum.txt");
byte[] bytes = Files.readAllBytes(file.toPath());
Signature signature = Signature.getInstance("SchnorrSignature");
signature.initSign(keyPair.getPrivate());
signature.update(bytes);
byte[] signatureBytes = signature.sign();
signature.initVerify(keyPair.getPublic());
signature.update(bytes);
boolean verified = signature.verify(signatureBytes);
assert verified;

3.ii.b Custom SecureRandom

It is essential that the nonce r is both unpredictable and unique as well as remains confidential. Note, that a single revealed r together with the corresponding signature (e,y) suffices to compute the secret private key x, simply by solving the linear congruence

y ≡q r + ex

If, on the other hand, the same r is used twice for two different documents, an adversary may obtain the private key by solving a system of linear congruences with two unknowns:

y1 ≡q r + e1x

y2 ≡q r + e2x

Similar considerations also apply to the Digital Signature Algorithm (DSA) specified by the NIST.

Since the default SecureRandom instance may obtain random numbers from the underlying OS, weaknesses of the native Random Number Generator (RNG) will be reflected by the signature. Thus, someone might want to use a custom SecureRandom for the generation of the nonces. The subsequent example uses the SHA1PRNG which produces pseudo random numbers. These pseudo random numbers will be computed deterministically but are hard to predict without knowledge of the seed.

import java.io.File;
import java.nio.file.Files;
import java.security.KeyPair;
import java.security.SecureRandom;
import java.security.Signature;
...
KeyPair keyPair = ...
File file = new File("loremipsum.txt");
byte[] bytes = Files.readAllBytes(file.toPath());
SecureRandom secureRandom = SecureRandom.getInstance("SHA1PRNG");
Signature signature = Signature.getInstance("SchnorrSignature");
signature.initSign(keyPair.getPrivate(), secureRandom);
signature.update(bytes);
byte[] signatureBytes = signature.sign();
signature.initVerify(keyPair.getPublic());
signature.update(bytes);
boolean verified = signature.verify(signatureBytes);
assert verified;

See also 3.1.d (Deterministic) NonceGenerators.

3.ii.c NIO

Suppose that you want digitally sign potentially large database dumps before archiving, thus ensuring data authenticity. The above shown approach wouldn't work well since the method byte[] readAllBytes(Path path) is not intended for reading in large files. One way to process large files like database dumps is to use NIO, see the next example:

import java.io.File;
import java.io.FileInputStream;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.security.KeyPair;
import java.security.SecureRandom;
import java.security.Signature;
...
KeyPair keyPair = ...
File largeDump = new File("dumped.sql");
Signature signature = Signature.getInstance("SchnorrSignature");
signature.initSign(keyPair.getPrivate());
int bufferSize = 512;
ByteBuffer buffer = ByteBuffer.allocate(bufferSize);
byte[] bytes = new byte[bufferSize];
try (FileInputStream fileInputStream = new FileInputStream(largeDump)) {
  FileChannel fileChannel = fileInputStream.getChannel();
  do {
    int read = fileChannel.read(buffer);
    if (read == -1)
      break;
    buffer.flip();
    buffer.get(bytes, 0, read);
    signature.update(bytes, 0, read);
    buffer.clear();
  } while(true);
}
byte[] signatureBytes = signature.sign();
...

The verification process is similar. The Signature instance must be initialized for verifying and thereupon the byte chunks must be processed. Finally, call the boolean verify(byte[] signature) method.

3.ii.d Message Digest configuration

Denoting the output length of the cryptographic hash function with t, this turns the signature

(e,y) ∊ ℤq × ℤq

essentially into

(e,y) ∊ ℤ2t × ℤq

Hence, assuming a 512-bit q, the preset SHA-256 is mapping only onto a very small subset of the domain ℤq. However, this seems not to be a problem. Neven et al. argue within their paper, see [Hash Function Requirements for Schnorr Signatures](http://www.neven.org/papers/schnorr.pdf), that

t = ⌈log2 q⌉/2

should be sufficient to provide a security level of t bits. Hence SHA-256 is a natural choice for a 512-bit sized q (which is the default). A 1024-bit sized q however would require a cryptographic hash function with 512 bit output length, e.g. SHA-512, to provide a security level of 512 bits.

The to be used hash function can be configured by setting a property of the JCA provider. The subsequent code snippet configures SHA-512:

import java.security.Provider;
import java.security.Security;
...
Provider provider = new de.christofreichardt.crypto.Provider();
provider.put("de.christofreichardt.crypto.schnorrsignature.messageDigest", "SHA-512");
Security.addProvider(provider);

This requires, that another installed JCA provider supplies this message digest algorithm. This is true for the SUN provider coming with the official Oracle JDK. Another popular JCA provider is The Legion of the Bouncy Castle. Installing this provider as well someone can use the Schnorr Signature e.g. together with the Skein-1024 message digest. Skein has been one of finalists of the SHA-3 competition and has an output length of 1024 bits.

3.ii.e (Deterministic) NonceGenerators

As mentioned in section 3.i.b, custom SecureRandom implementations can be injected into the Signature engine. Such implementations may use True Random Number Generators (TRNG) under the hood. Unfortunately, the efficiency of TRNGs is rather poor. Hence TRNGs might not produce enough random numbers in time for the desired throughput. As a consequence of their slowness TRNGs are often only used to (re)seed Pseudo Random Number Generators (PRNG) like SHA1PRNG coming with the SUN JCA provider.

In general, someone need not to be concerned about duplicate nonces so long as the employed algorithms and the RNG in use produces an (almost) uniform distribution over ℤq. The domain ℤq is simply too large even when using the minimal security parameters. Assuming a 256-bit sized q the number of possible values equals roughly the number of the elementary particles within the visible universe.

Another question is whether the entropy sources of conventional computer systems can be trusted. See the article Entropy Attacks! within Bernsteins cr.yp.to blog for a discussion. Someone might remember the Debian random number debacle too. Fortunately, there are methods available to generate the required nonces without access to high quality randomness. Ed25519 generates the nonce by computing

r ≡ H(hb, ... , h2b−1 || M)

whereas (hb, ... , h2b−1) is part of the hashed (secret) private key. My problem with this approach is that even SHA-512 produces only a 512-bit output and that aren't enough bits to compute an uniformly distributed r ∊R (ℤq)×, assuming a 512-bit sized q (which is the default). For this purpose H would have to output at least 512 + k bits thus producing a distribution with a statistical distance of at most 2-k to the uniform distribution. The subsequent

r ≡q SHA-512(x || M), ⌈log2 q⌉ = 512

would therefore produce a biased nonce. This isn't a problem for [Ed25519](http://ed25519.cr.yp.to/ed25519-20110926.pdf) because they are reducing r by a 252-bit sized modulus. See also section 9.2 "Generating a random number from a given interval" within Shoup's [A Computational Introduction to Number Theory and Algebra](http://www.shoup.net/ntb/).

Instead, I have followed RFC 6979 which describes the "Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)". At the heart of RFC 6979 is a PRNG based upon a keyed hash function (HMAC) which can produce an arbitrary number of random bits. I'm using HmacSha256 for the given algorithm. HmacSha256 comes with the SunJCE JCA provider that in turn is part of the Oracle JDK (and OpenJDK). The HmacSHA256PRNGNonceGenerator needs some additional key bytes. Hence its usage must be already considered when generating the key pair.

The deterministic HmacSHA256PRNGNonceGenerator can be injected as follows:

import java.io.File;
import java.nio.file.Files;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.Signature;
import de.christofreichardt.crypto.HmacSHA256PRNGNonceGenerator;
import de.christofreichardt.crypto.NonceGenerator;
import de.christofreichardt.crypto.schnorrsignature.SchnorrSigKeyGenParameterSpec;
import de.christofreichardt.crypto.schnorrsignature.SchnorrSigKeyGenParameterSpec.Strength;
import de.christofreichardt.crypto.schnorrsignature.SchnorrSigParameterSpec;
...
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("SchnorrSignature");
SchnorrSigKeyGenParameterSpec schnorrSigKeyGenParameterSpec = new SchnorrSigKeyGenParameterSpec(Strength.DEFAULT, true); // demands extra key bytes
keyPairGenerator.initialize(schnorrSigKeyGenParameterSpec);
KeyPair keyPair = keyPairGenerator.generateKeyPair();
File file = new File("loremipsum.txt");
byte[] bytes = Files.readAllBytes(file.toPath());
Signature signature = Signature.getInstance("SchnorrSignature");
NonceGenerator nonceGenerator = new HmacSHA256PRNGNonceGenerator();
SchnorrSigParameterSpec schnorrSigParameterSpec = new SchnorrSigParameterSpec(nonceGenerator);
signature.setParameter(schnorrSigParameterSpec);
signature.initSign(keyPair.getPrivate());
signature.update(bytes);
byte[] signatureBytes = signature.sign();
signature.initVerify(keyPair.getPublic());
signature.update(bytes);
boolean verified = signature.verify(signatureBytes);
assert verified;

As a consequence, if someone signs a document twice with the HmacSHA256PRNGNonceGenerator the produced signatures will be the same contrary to the traditional protocol because the generated nonces depend only on the to be signed message and on portions of the private key.

By default the Signature engine uses the AlmostUniformRandomNonceGenerator class together with a SecureRandom instance. This AlmostUniformRandomNonceGenerator produces the nonce r by requesting t random bits with

t = ⌈log2 q⌉⋅2

and summing up the corresponding powers of 2 thus ensuring an almost uniform distribution over ℤq. As alternative an `UniformRandomNonceGenerator` can be injected into the `Signature` engine. This one produces a perfect uniform distribution over ℤq. The `UniformRandomNonceGenerator` has the disadvantage that its runtime is probabilistic whereas the `AlmostUniformRandomNonceGenerator` has a constant runtime. Since the `UniformRandomNonceGenerator` doesn't need extra key bytes the following code is suffcient to inject it into the `Signature` engine: 
import java.io.File;
import java.nio.file.Files;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.Signature;
import de.christofreichardt.crypto.NonceGenerator;
import de.christofreichardt.crypto.UniformRandomNonceGenerator;
import de.christofreichardt.crypto.schnorrsignature.SchnorrSigParameterSpec;
...
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("SchnorrSignature");
KeyPair keyPair = keyPairGenerator.generateKeyPair();
File file = new File("loremipsum.txt");
byte[] bytes = Files.readAllBytes(file.toPath());
Signature signature = Signature.getInstance("SchnorrSignature");
NonceGenerator nonceGenerator = new UniformRandomNonceGenerator();
SchnorrSigParameterSpec schnorrSigParameterSpec = new SchnorrSigParameterSpec(nonceGenerator);
signature.setParameter(schnorrSigParameterSpec);
signature.initSign(keyPair.getPrivate());
signature.update(bytes);
byte[] signatureBytes = signature.sign();
signature.initVerify(keyPair.getPublic());
signature.update(bytes);
boolean verified = signature.verify(signatureBytes);
assert verified;

TOC

4. Schnorr Signatures on elliptic curves

Public domain parameter Elliptic curve E(𝔽p), p prime, #E(𝔽p)=n⋅d, n prime, d << n
g ∊ E(𝔽p), order(g) = n ⇒ [n]⋅g ≡E 𝓞, H: {0,1}* → ℤn
Secret key x ∊R (ℤn)×
Public key h ≡E [x]⋅g
Signing M∊{0,1}* r ∊R (ℤn)×, s ≡E [r]⋅g, e ≡n H(M ‖ s), y ≡n r + ex
Signature (e,y) ∊ ℤn × ℤn
Verifying s ≡E [y]⋅g + [-e]⋅h, check if H(M ‖ s) ≡n e holds.
Correctness [y]⋅g + [-e]⋅h ≡E [y]⋅g + [-ex]⋅g ≡E [y - ex]⋅g ≡E [r]⋅g

4.i KeyPairGenerator Usage

Key pairs can be generated by using some well known compilations of cryptographically strong curves. The 'Bundesamt für Sicherheit in der Informationstechnik' in its Technical Guideline TR-03111 recommends the use of the curves provided by the ECC Brainpool working group, which have been published by the RFC 5639. This JCA provider uses this curve compilation as default. The NIST recommended elliptic curves over prime fields specified by FIPS PUB 186-4 can be used too. Curves of both compilations have been critizised by the researchers Daniel J. Bernstein and Tanja Lange for various reasons, see their site SafeCurves: choosing safe curves for elliptic-curve cryptography for more information. This library therefore provides some curves recommended by this site as well. So long as all required domain parameter are provided the user may also apply arbitrary curves of his own choice.

4.i.a Brainpool Curves

RFC 5639 defines curves for each of the bit lengths 160, 192, 224, 256, 320, 384 and 512 together with corresponding twist curves. The 256-bit curve brainpoolP256r1 is used as default. All curves exhibit a prime number as group order, hence all points of a particular curve may serve as basepoints. Nevertheless RFC 5639 specifies additionally a basepoint for each curve. This one will be used as default:

import java.math.BigInteger;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import de.christofreichardt.crypto.ecschnorrsignature.CurveSpec;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrPublicKey;
import de.christofreichardt.scala.ellipticcurve.affine.AffineCoordinatesWithPrimeField.AffinePoint;
...
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("ECSchnorrSignature");
KeyPair keyPair = keyPairGenerator.generateKeyPair();
ECSchnorrPublicKey publicKey = (ECSchnorrPublicKey) keyPair.getPublic();
CurveSpec curveSpec = publicKey.getEcSchnorrParams().getCurveSpec();
BigInteger p = curveSpec.getCurve().p().bigInteger();
AffinePoint basePoint = curveSpec.getgPoint();
BigInteger order = curveSpec.getOrder();
assert p.bitLength() == 256;
assert p.isProbablePrime(100) && order.isProbablePrime(100);
assert basePoint.equals(publicKey.getEcSchnorrParams().getgPoint());
assert basePoint.multiply(order).isNeutralElement();

The next examples demonstrates how someone may retrieve a Brainpool curve with a particular bit length:

import java.math.BigInteger;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import de.christofreichardt.crypto.ecschnorrsignature.CurveSpec;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrPublicKey;
import de.christofreichardt.scala.ellipticcurve.affine.AffineCoordinatesWithPrimeField.AffinePoint;
...
final int BIT_LENGTH = 384;
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("ECSchnorrSignature");
keyPairGenerator.initialize(BIT_LENGTH);
KeyPair keyPair = keyPairGenerator.generateKeyPair();
ECSchnorrPublicKey publicKey = (ECSchnorrPublicKey) keyPair.getPublic();
CurveSpec curveSpec = publicKey.getEcSchnorrParams().getCurveSpec();
BigInteger p = curveSpec.getCurve().p().bigInteger();
AffinePoint basePoint = curveSpec.getgPoint();
BigInteger order = curveSpec.getOrder();
assert p.isProbablePrime(100) && order.isProbablePrime(100);
assert p.bitLength() == BIT_LENGTH;
assert basePoint.equals(publicKey.getEcSchnorrParams().getgPoint());
assert basePoint.multiply(order).isNeutralElement();

The above example retrieves the brainpoolP384r1 curve. For every brainpoolPnnnr1 curve exists a twist curve brainpoolPnnnt1 with a similar security profile whereas nnn denotes one of the valid bit lengths. The subsequent example retrieves the curve brainpoolP224t1 and demands a random base point which will be generated by the given SHA1PRNG SecureRandom instance:

import java.math.BigInteger;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.SecureRandom;
import de.christofreichardt.crypto.ecschnorrsignature.CurveSpec;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrPublicKey;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrSigKeyGenParameterSpec;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrSigKeyGenParameterSpec.CurveCompilation;
import de.christofreichardt.scala.ellipticcurve.affine.AffineCoordinatesWithPrimeField.AffinePoint;
...
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("ECSchnorrSignature");
final int BIT_LENGTH = 224;
final String CURVE_ID = "brainpoolP224t1";
ECSchnorrSigKeyGenParameterSpec ecSchnorrSigKeyGenParameterSpec = new ECSchnorrSigKeyGenParameterSpec(CurveCompilation.BRAINPOOL, CURVE_ID, true);
keyPairGenerator.initialize(ecSchnorrSigKeyGenParameterSpec, SecureRandom.getInstance("SHA1PRNG"));
KeyPair keyPair = keyPairGenerator.generateKeyPair();
ECSchnorrPublicKey publicKey = (ECSchnorrPublicKey) keyPair.getPublic();
CurveSpec curveSpec = publicKey.getEcSchnorrParams().getCurveSpec();
BigInteger p = curveSpec.getCurve().p().bigInteger();
AffinePoint basePoint = publicKey.getEcSchnorrParams().getgPoint();
BigInteger order = curveSpec.getOrder();
assert p.isProbablePrime(100) && order.isProbablePrime(100);
assert p.bitLength() == BIT_LENGTH;
assert basePoint.multiply(order).isNeutralElement();

4.i.b NIST Curves

FIPS PUB 186-4 specifies five curves over prime fields: P-192, P-224, P-256, P-384 and P-521. The next example shows how someone may create key pairs based upon the P-384 curve and the specified default base point:

import java.math.BigInteger;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import de.christofreichardt.crypto.ecschnorrsignature.CurveSpec;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrPublicKey;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrSigKeyGenParameterSpec;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrSigKeyGenParameterSpec.CurveCompilation;
import de.christofreichardt.scala.ellipticcurve.affine.AffineCoordinatesWithPrimeField.AffinePoint;
...
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("ECSchnorrSignature");
final int BIT_LENGTH = 384;
final String CURVE_ID = "P-384";
ECSchnorrSigKeyGenParameterSpec ecSchnorrSigKeyGenParameterSpec = new ECSchnorrSigKeyGenParameterSpec(CurveCompilation.NIST, CURVE_ID);
keyPairGenerator.initialize(ecSchnorrSigKeyGenParameterSpec);
KeyPair keyPair = keyPairGenerator.generateKeyPair();
ECSchnorrPublicKey publicKey = (ECSchnorrPublicKey) keyPair.getPublic();
CurveSpec curveSpec = publicKey.getEcSchnorrParams().getCurveSpec();
BigInteger p = curveSpec.getCurve().p().bigInteger();
AffinePoint basePoint = curveSpec.getgPoint();
BigInteger order = curveSpec.getOrder();
assert p.isProbablePrime(100) && order.isProbablePrime(100);
assert p.bitLength() == BIT_LENGTH;
assert basePoint.equals(publicKey.getEcSchnorrParams().getgPoint());
assert basePoint.multiply(order).isNeutralElement();

Again, all curves of the NIST compilation exhibit a prime number as group order.

4.i.c SafeCurves

SafeCurves lists several curves which passes their criteria. I have included M-221, Curve25519, M-383 and M-511 into this library to cover a wide range of security levels. Curve25519 had been introduced by Bernstein himself whereas M-221, M-383 and M-511 have been designed by Aranha et al, see their paper A note on high-security general-purpose elliptic curves. All of these curves can be expressed as Montgomery curves and will be processed by the corresponding group law from this library. The next examples shows how someone may compute key pairs based upon the M-551 curve with a random base point:

import java.math.BigInteger;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import de.christofreichardt.crypto.ecschnorrsignature.CurveSpec;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrPublicKey;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrSigKeyGenParameterSpec;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrSigKeyGenParameterSpec.CurveCompilation;
import de.christofreichardt.scala.ellipticcurve.affine.AffineCoordinatesWithPrimeField.AffinePoint;
...
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("ECSchnorrSignature");
final int BIT_LENGTH = 511;
final String CURVE_ID = "M-511";
ECSchnorrSigKeyGenParameterSpec ecSchnorrSigKeyGenParameterSpec = new ECSchnorrSigKeyGenParameterSpec(CurveCompilation.SAFECURVES, CURVE_ID, true);
keyPairGenerator.initialize(ecSchnorrSigKeyGenParameterSpec);
KeyPair keyPair = keyPairGenerator.generateKeyPair();
ECSchnorrPublicKey publicKey = (ECSchnorrPublicKey) keyPair.getPublic();
CurveSpec curveSpec = publicKey.getEcSchnorrParams().getCurveSpec();
BigInteger p = curveSpec.getCurve().p().bigInteger();
AffinePoint basePoint = publicKey.getEcSchnorrParams().getgPoint();
BigInteger order = curveSpec.getOrder();
assert p.isProbablePrime(100) && order.isProbablePrime(100);
assert p.bitLength() == BIT_LENGTH;
assert basePoint.multiply(order).isNeutralElement();

All of these curves (M-221, Curve25519, M-383 and M-511) exhibit 8 as cofactor, hence #E(𝔽p)=n⋅8.

4.i.d Custom Curves

Someone might want to inject curves of his own choice. The subsequent example shows how this can be achieved by defining a ShortWeierstrass curve found in "Elliptic Curves in Cryptography" by Blake, Seroussi and Smart:

import java.math.BigInteger;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import scala.math.BigInt;
import de.christofreichardt.crypto.ecschnorrsignature.CurveSpec;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrPublicKey;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrSigKeyGenParameterSpec;
import de.christofreichardt.scala.ellipticcurve.affine.AffineCoordinatesWithPrimeField.AffinePoint;
import de.christofreichardt.scala.ellipticcurve.affine.AffineCoordinatesWithPrimeField.PrimeField;
import de.christofreichardt.scala.ellipticcurve.affine.ShortWeierstrass;
import de.christofreichardt.scala.ellipticcurve.affine.ShortWeierstrass.OddCharCoefficients;
...
BigInteger a = new BigInteger("10");
BigInteger b = new BigInteger("1343632762150092499701637438970764818528075565078");
BigInteger p = new BigInteger("2").pow(160).add(new BigInteger("7"));
BigInteger order = new BigInteger("1461501637330902918203683518218126812711137002561");
OddCharCoefficients coefficients = new OddCharCoefficients(new BigInt(a), new BigInt(b));
PrimeField primeField = ShortWeierstrass.makePrimeField(new BigInt(p));
ShortWeierstrass.Curve curve = ShortWeierstrass.makeCurve(coefficients, primeField);
CurveSpec curveSpec = new CurveSpec(curve, order, BigInteger.ONE, null);
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("ECSchnorrSignature");
ECSchnorrSigKeyGenParameterSpec ecSchnorrSigKeyGenParameterSpec = new ECSchnorrSigKeyGenParameterSpec(curveSpec, true);
keyPairGenerator.initialize(ecSchnorrSigKeyGenParameterSpec);
KeyPair keyPair = keyPairGenerator.generateKeyPair();
ECSchnorrPublicKey publicKey = (ECSchnorrPublicKey) keyPair.getPublic();
AffinePoint basePoint = publicKey.getEcSchnorrParams().getgPoint();
assert basePoint.multiply(order).isNeutralElement();

4.ii Signature Usage

Once you have generated a key pair with one of the methods outlined above, you may create digital signatures. Signing is done with the private key whereas the verification process is done with the public key. All considerations regarding the generation of the nonces are the same as in the sections 3.ii.b Custom SecureRandom and 3.ii.e (Deterministic) NonceGenerators of the chapter 3. Schnorr Signatures on prime fields and therefore the corresponding sections within this chapter will focus on examples.

4.ii.a Simple Use

This works very similar as 3.ii.a Simple Use in chapter 3. Schnorr Signatures on prime fields. In fact, since the JCA architecture is generic regarding algorithms this isn't surprising.

import java.io.File;
import java.nio.file.Files;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.Signature;
...
KeyPair keyPair = ...
File file = new File("loremipsum.txt");
byte[] bytes = Files.readAllBytes(file.toPath());
Signature signature = Signature.getInstance("ECSchnorrSignature");
signature.initSign(keyPair.getPrivate());
signature.update(bytes);
byte[] signatureBytes = signature.sign();
signature.initVerify(keyPair.getPublic());
signature.update(bytes);
boolean verified = signature.verify(signatureBytes);
assert verified;

4.ii.b Custom SecureRandom

Someone might pursue her own strategy regarding RNGs, seeds and entropy sources. It is therefore possible to inject a custom SecureRandom implementation into the signature algorithm:

import java.io.File;
import java.nio.file.Files;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.SecureRandom;
import java.security.Signature;
...
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("ECSchnorrSignature");
KeyPair keyPair = keyPairGenerator.generateKeyPair();
File file = new File("loremipsum.txt");
byte[] bytes = Files.readAllBytes(file.toPath());
SecureRandom secureRandom = SecureRandom.getInstance("SHA1PRNG");
Signature signature = Signature.getInstance("ECSchnorrSignature");
signature.initSign(keyPair.getPrivate(), secureRandom);
signature.update(bytes);
byte[] signatureBytes = signature.sign();
signature.initVerify(keyPair.getPublic());
signature.update(bytes);
boolean verified = signature.verify(signatureBytes);
assert verified;

See also 3.ii.b Custom SecureRandom to understand why the nonces must be unpredictable, unique and confidential.

4.ii.c NIO

Suppose that you want protect a SEPA payment file with several thousand payment records against subsequent modification by applying a digital signature. The above shown approach wouldn't work well since the method byte[] readAllBytes(Path path) is not intended for reading in large files. Use NIO to efficiently process potentially large files instead:

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.Signature;
...
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("ECSchnorrSignature");
KeyPair keyPair = keyPairGenerator.generateKeyPair();
File file = new File("SEPA-payment.xml");
Signature signature = Signature.getInstance("ECSchnorrSignature");
signature.initSign(keyPair.getPrivate());
int bufferSize = 512;
ByteBuffer buffer = ByteBuffer.allocate(bufferSize);
try (FileInputStream fileInputStream = new FileInputStream(file)) {
  FileChannel fileChannel = fileInputStream.getChannel();
  do {
    int read = fileChannel.read(buffer);
    if (read == -1)
      break;
    buffer.flip();
    signature.update(buffer);
    buffer.clear();
  } while(true);
}
byte[] signatureBytes = signature.sign();
...

4.ii.d Message Digest configuration

The default curve brainpoolP256r1 exhibits a 256-bit number as group order. Hence the output length of the default hash function SHA-256 is adequate. In fact SHA-256 should be sufficient even for the curves brainpoolP512r1, brainpoolP512t1 and M-511 to provide a security level of 256 bits, see Hash Function Requirements for Schnorr Signatures by Neven et al for more details. It is however possible to configure another message digest by editing the appropriate property on the Provider class, for example

import java.security.Provider;
import java.security.Security;
...
Provider provider = new de.christofreichardt.crypto.Provider();
provider.put("de.christofreichardt.crypto.ecschnorrsignature.messageDigest", "SHA-512");
Security.addProvider(provider);

configures SHA-512 as message digest for the ECSchnorrSignature algorithm. The property value must be a valid algorithm name for message digests, that is to say an installed JCA provider must supply the corresponding algorithm. By using the Bouncy Castle provider someone can even configure the new SHA3-512 standard.

4.ii.e (Deterministic) NonceGenerators

A flaw within the underlying RNG may cause your nonces to be predictable and hence may expose your private key. Therefore, it might make sense to create deterministic nonces which are nevertheless unpredictable, unique and confidential. I have followed RFC 6979 and have provided a deterministic NonceGenerator based upon a HmacSha256 PRNG. The deterministic HmacSHA256PRNGNonceGenerator can be injected as follows:

import java.io.File;
import java.nio.file.Files;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.Signature;
import de.christofreichardt.crypto.HmacSHA256PRNGNonceGenerator;
import de.christofreichardt.crypto.NonceGenerator;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrSigKeyGenParameterSpec;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrSigKeyGenParameterSpec.CurveCompilation;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrSigParameterSpec;
...
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("ECSchnorrSignature");
// requests the 'M-383' curve together with the default base point and extra key bytes:
ECSchnorrSigKeyGenParameterSpec ecSchnorrSigKeyGenParameterSpec = new ECSchnorrSigKeyGenParameterSpec(CurveCompilation.SAFECURVES, "M-383", false, true);
keyPairGenerator.initialize(ecSchnorrSigKeyGenParameterSpec);
KeyPair keyPair = keyPairGenerator.generateKeyPair();
File file = new File("loremipsum.txt");
byte[] bytes = Files.readAllBytes(file.toPath());
Signature signature = Signature.getInstance("ECSchnorrSignature");
NonceGenerator nonceGenerator = new HmacSHA256PRNGNonceGenerator();
ECSchnorrSigParameterSpec ecSchnorrSigParameterSpec = new ECSchnorrSigParameterSpec(nonceGenerator);
signature.setParameter(ecSchnorrSigParameterSpec);
signature.initSign(keyPair.getPrivate());
signature.update(bytes);
byte[] signatureBytes = signature.sign();
signature.initVerify(keyPair.getPublic());
signature.update(bytes);
boolean verified = signature.verify(signatureBytes);
assert verified;

See also 3.ii.e (Deterministic) NonceGenerators for a more detailed discussion.

4.ii.f Point Multiplication methods

There exists several point multiplication methods beginning with the simple binary methods up to complex windowed methods. Some of these may leak secret data through timing. For example, the simple binary method applies a point doubling operation and depending on the just being processed bit of the scalar multiplier additionally a point addition. Hence switched on bits of the scalar multiplier are more expensive than turned off bits. Thus, timing attacks may reveal the secret nonce and furthermore the private key. At present this library provides two countermeasures against simple timing attacks: the Montgomery ladder and the Double-and-add-always method.

Since the signature scheme repeatedly requires multiplications of the same base point for different signatures some computations can be preprocessed. This is known as fixed point multiplication. This may be advantageous if many signatures are processed with the same private key.

In case of the unknown point multiplication the Montgomery ladder method is preselected. The subsequent example shows how someone can exchange the Montgomery ladder for the Double-and-add-always method:

import java.security.Provider;
import java.security.Security;
...
Provider provider = new de.christofreichardt.crypto.Provider();
put("de.christofreichardt.scala.ellipticcurve.multiplicationMethod", "DoubleAndAddAlways");
Security.addProvider(provider);

The subsequent code shows how someone can select the fixed point multiplication:

import java.io.File;
import java.nio.file.Files;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.Signature;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrSigParameterSpec;
import de.christofreichardt.crypto.ecschnorrsignature.ECSchnorrSigParameterSpec.PointMultiplicationStrategy;
...
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("ECSchnorrSignature");
KeyPair keyPair = keyPairGenerator.generateKeyPair();
File file = new File("../data/loremipsum.txt");
byte[] bytes = Files.readAllBytes(file.toPath());
Signature signature = Signature.getInstance("ECSchnorrSignature");
ECSchnorrSigParameterSpec ecSchnorrSigParameterSpec = new ECSchnorrSigParameterSpec(PointMultiplicationStrategy.FIXED_POINT);
signature.setParameter(ecSchnorrSigParameterSpec);
signature.initSign(keyPair.getPrivate());
signature.update(bytes);
byte[] signatureBytes = signature.sign();
signature.initVerify(keyPair.getPublic());
signature.update(bytes);
boolean verified = signature.verify(signatureBytes);
assert verified;

At present the only fixed point method available is the binary method with some built-in resistance against simple timing attacks - that is to say the multiplicationMethod property won't take effect when doing fixed point multiplication.

TOC

5. Links