diff options
Diffstat (limited to 'core/src/main/java/org/spongycastle/pqc/crypto/gmss')
17 files changed, 5449 insertions, 0 deletions
diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSDigestProvider.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSDigestProvider.java new file mode 100644 index 00000000..373ca503 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSDigestProvider.java @@ -0,0 +1,8 @@ +package org.spongycastle.pqc.crypto.gmss; + +import org.spongycastle.crypto.Digest; + +public interface GMSSDigestProvider +{ + Digest get(); +} diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSKeyGenerationParameters.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSKeyGenerationParameters.java new file mode 100644 index 00000000..27d7b697 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSKeyGenerationParameters.java @@ -0,0 +1,26 @@ +package org.spongycastle.pqc.crypto.gmss; + +import java.security.SecureRandom; + +import org.spongycastle.crypto.KeyGenerationParameters; + +public class GMSSKeyGenerationParameters + extends KeyGenerationParameters +{ + + private GMSSParameters params; + + public GMSSKeyGenerationParameters( + SecureRandom random, + GMSSParameters params) + { + // XXX key size? + super(random, 1); + this.params = params; + } + + public GMSSParameters getParameters() + { + return params; + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSKeyPairGenerator.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSKeyPairGenerator.java new file mode 100644 index 00000000..bb1ef36d --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSKeyPairGenerator.java @@ -0,0 +1,476 @@ +package org.spongycastle.pqc.crypto.gmss; + +import java.security.SecureRandom; +import java.util.Vector; + +import org.spongycastle.crypto.AsymmetricCipherKeyPair; +import org.spongycastle.crypto.AsymmetricCipherKeyPairGenerator; +import org.spongycastle.crypto.Digest; +import org.spongycastle.crypto.KeyGenerationParameters; +import org.spongycastle.pqc.crypto.gmss.util.GMSSRandom; +import org.spongycastle.pqc.crypto.gmss.util.WinternitzOTSVerify; +import org.spongycastle.pqc.crypto.gmss.util.WinternitzOTSignature; + + +/** + * This class implements key pair generation of the generalized Merkle signature + * scheme (GMSS). + * + * @see GMSSSigner + */ +public class GMSSKeyPairGenerator + implements AsymmetricCipherKeyPairGenerator +{ + /** + * The source of randomness for OTS private key generation + */ + private GMSSRandom gmssRandom; + + /** + * The hash function used for the construction of the authentication trees + */ + private Digest messDigestTree; + + /** + * An array of the seeds for the PRGN (for main tree, and all current + * subtrees) + */ + private byte[][] currentSeeds; + + /** + * An array of seeds for the PRGN (for all subtrees after next) + */ + private byte[][] nextNextSeeds; + + /** + * An array of the RootSignatures + */ + private byte[][] currentRootSigs; + + /** + * Class of hash function to use + */ + private GMSSDigestProvider digestProvider; + + /** + * The length of the seed for the PRNG + */ + private int mdLength; + + /** + * the number of Layers + */ + private int numLayer; + + + /** + * Flag indicating if the class already has been initialized + */ + private boolean initialized = false; + + /** + * Instance of GMSSParameterset + */ + private GMSSParameters gmssPS; + + /** + * An array of the heights of the authentication trees of each layer + */ + private int[] heightOfTrees; + + /** + * An array of the Winternitz parameter 'w' of each layer + */ + private int[] otsIndex; + + /** + * The parameter K needed for the authentication path computation + */ + private int[] K; + + private GMSSKeyGenerationParameters gmssParams; + + /** + * The GMSS OID. + */ + public static final String OID = "1.3.6.1.4.1.8301.3.1.3.3"; + + /** + * The standard constructor tries to generate the GMSS algorithm identifier + * with the corresponding OID. + * + * @param digestProvider provider for digest implementations. + */ + public GMSSKeyPairGenerator(GMSSDigestProvider digestProvider) + { + this.digestProvider = digestProvider; + messDigestTree = digestProvider.get(); + + // set mdLength + this.mdLength = messDigestTree.getDigestSize(); + // construct randomizer + this.gmssRandom = new GMSSRandom(messDigestTree); + + } + + /** + * Generates the GMSS key pair. The public key is an instance of + * JDKGMSSPublicKey, the private key is an instance of JDKGMSSPrivateKey. + * + * @return Key pair containing a JDKGMSSPublicKey and a JDKGMSSPrivateKey + */ + private AsymmetricCipherKeyPair genKeyPair() + { + if (!initialized) + { + initializeDefault(); + } + + // initialize authenticationPaths and treehash instances + byte[][][] currentAuthPaths = new byte[numLayer][][]; + byte[][][] nextAuthPaths = new byte[numLayer - 1][][]; + Treehash[][] currentTreehash = new Treehash[numLayer][]; + Treehash[][] nextTreehash = new Treehash[numLayer - 1][]; + + Vector[] currentStack = new Vector[numLayer]; + Vector[] nextStack = new Vector[numLayer - 1]; + + Vector[][] currentRetain = new Vector[numLayer][]; + Vector[][] nextRetain = new Vector[numLayer - 1][]; + + for (int i = 0; i < numLayer; i++) + { + currentAuthPaths[i] = new byte[heightOfTrees[i]][mdLength]; + currentTreehash[i] = new Treehash[heightOfTrees[i] - K[i]]; + + if (i > 0) + { + nextAuthPaths[i - 1] = new byte[heightOfTrees[i]][mdLength]; + nextTreehash[i - 1] = new Treehash[heightOfTrees[i] - K[i]]; + } + + currentStack[i] = new Vector(); + if (i > 0) + { + nextStack[i - 1] = new Vector(); + } + } + + // initialize roots + byte[][] currentRoots = new byte[numLayer][mdLength]; + byte[][] nextRoots = new byte[numLayer - 1][mdLength]; + // initialize seeds + byte[][] seeds = new byte[numLayer][mdLength]; + // initialize seeds[] by copying starting-seeds of first trees of each + // layer + for (int i = 0; i < numLayer; i++) + { + System.arraycopy(currentSeeds[i], 0, seeds[i], 0, mdLength); + } + + // initialize rootSigs + currentRootSigs = new byte[numLayer - 1][mdLength]; + + // ------------------------- + // ------------------------- + // --- calculation of current authpaths and current rootsigs (AUTHPATHS, + // SIG)------ + // from bottom up to the root + for (int h = numLayer - 1; h >= 0; h--) + { + GMSSRootCalc tree = new GMSSRootCalc(this.heightOfTrees[h], this.K[h], digestProvider); + try + { + // on lowest layer no lower root is available, so just call + // the method with null as first parameter + if (h == numLayer - 1) + { + tree = this.generateCurrentAuthpathAndRoot(null, currentStack[h], seeds[h], h); + } + else + // otherwise call the method with the former computed root + // value + { + tree = this.generateCurrentAuthpathAndRoot(currentRoots[h + 1], currentStack[h], seeds[h], h); + } + + } + catch (Exception e1) + { + e1.printStackTrace(); + } + + // set initial values needed for the private key construction + for (int i = 0; i < heightOfTrees[h]; i++) + { + System.arraycopy(tree.getAuthPath()[i], 0, currentAuthPaths[h][i], 0, mdLength); + } + currentRetain[h] = tree.getRetain(); + currentTreehash[h] = tree.getTreehash(); + System.arraycopy(tree.getRoot(), 0, currentRoots[h], 0, mdLength); + } + + // --- calculation of next authpaths and next roots (AUTHPATHS+, ROOTS+) + // ------ + for (int h = numLayer - 2; h >= 0; h--) + { + GMSSRootCalc tree = this.generateNextAuthpathAndRoot(nextStack[h], seeds[h + 1], h + 1); + + // set initial values needed for the private key construction + for (int i = 0; i < heightOfTrees[h + 1]; i++) + { + System.arraycopy(tree.getAuthPath()[i], 0, nextAuthPaths[h][i], 0, mdLength); + } + nextRetain[h] = tree.getRetain(); + nextTreehash[h] = tree.getTreehash(); + System.arraycopy(tree.getRoot(), 0, nextRoots[h], 0, mdLength); + + // create seed for the Merkle tree after next (nextNextSeeds) + // SEEDs++ + System.arraycopy(seeds[h + 1], 0, this.nextNextSeeds[h], 0, mdLength); + } + // ------------ + + // generate JDKGMSSPublicKey + GMSSPublicKeyParameters publicKey = new GMSSPublicKeyParameters(currentRoots[0], gmssPS); + + // generate the JDKGMSSPrivateKey + GMSSPrivateKeyParameters privateKey = new GMSSPrivateKeyParameters(currentSeeds, nextNextSeeds, currentAuthPaths, + nextAuthPaths, currentTreehash, nextTreehash, currentStack, nextStack, currentRetain, nextRetain, nextRoots, currentRootSigs, gmssPS, digestProvider); + + // return the KeyPair + return (new AsymmetricCipherKeyPair(publicKey, privateKey)); + } + + /** + * calculates the authpath for tree in layer h which starts with seed[h] + * additionally computes the rootSignature of underlaying root + * + * @param currentStack stack used for the treehash instance created by this method + * @param lowerRoot stores the root of the lower tree + * @param seed starting seeds + * @param h actual layer + */ + private GMSSRootCalc generateCurrentAuthpathAndRoot(byte[] lowerRoot, Vector currentStack, byte[] seed, int h) + { + byte[] help = new byte[mdLength]; + + byte[] OTSseed = new byte[mdLength]; + OTSseed = gmssRandom.nextSeed(seed); + + WinternitzOTSignature ots; + + // data structure that constructs the whole tree and stores + // the initial values for treehash, Auth and retain + GMSSRootCalc treeToConstruct = new GMSSRootCalc(this.heightOfTrees[h], this.K[h], digestProvider); + + treeToConstruct.initialize(currentStack); + + // generate the first leaf + if (h == numLayer - 1) + { + ots = new WinternitzOTSignature(OTSseed, digestProvider.get(), otsIndex[h]); + help = ots.getPublicKey(); + } + else + { + // for all layers except the lowest, generate the signature of the + // underlying root + // and reuse this signature to compute the first leaf of acual layer + // more efficiently (by verifiing the signature) + ots = new WinternitzOTSignature(OTSseed, digestProvider.get(), otsIndex[h]); + currentRootSigs[h] = ots.getSignature(lowerRoot); + WinternitzOTSVerify otsver = new WinternitzOTSVerify(digestProvider.get(), otsIndex[h]); + help = otsver.Verify(lowerRoot, currentRootSigs[h]); + } + // update the tree with the first leaf + treeToConstruct.update(help); + + int seedForTreehashIndex = 3; + int count = 0; + + // update the tree 2^(H) - 1 times, from the second to the last leaf + for (int i = 1; i < (1 << this.heightOfTrees[h]); i++) + { + // initialize the seeds for the leaf generation with index 3 * 2^h + if (i == seedForTreehashIndex && count < this.heightOfTrees[h] - this.K[h]) + { + treeToConstruct.initializeTreehashSeed(seed, count); + seedForTreehashIndex *= 2; + count++; + } + + OTSseed = gmssRandom.nextSeed(seed); + ots = new WinternitzOTSignature(OTSseed, digestProvider.get(), otsIndex[h]); + treeToConstruct.update(ots.getPublicKey()); + } + + if (treeToConstruct.wasFinished()) + { + return treeToConstruct; + } + System.err.println("Baum noch nicht fertig konstruiert!!!"); + return null; + } + + /** + * calculates the authpath and root for tree in layer h which starts with + * seed[h] + * + * @param nextStack stack used for the treehash instance created by this method + * @param seed starting seeds + * @param h actual layer + */ + private GMSSRootCalc generateNextAuthpathAndRoot(Vector nextStack, byte[] seed, int h) + { + byte[] OTSseed = new byte[numLayer]; + WinternitzOTSignature ots; + + // data structure that constructs the whole tree and stores + // the initial values for treehash, Auth and retain + GMSSRootCalc treeToConstruct = new GMSSRootCalc(this.heightOfTrees[h], this.K[h], this.digestProvider); + treeToConstruct.initialize(nextStack); + + int seedForTreehashIndex = 3; + int count = 0; + + // update the tree 2^(H) times, from the first to the last leaf + for (int i = 0; i < (1 << this.heightOfTrees[h]); i++) + { + // initialize the seeds for the leaf generation with index 3 * 2^h + if (i == seedForTreehashIndex && count < this.heightOfTrees[h] - this.K[h]) + { + treeToConstruct.initializeTreehashSeed(seed, count); + seedForTreehashIndex *= 2; + count++; + } + + OTSseed = gmssRandom.nextSeed(seed); + ots = new WinternitzOTSignature(OTSseed, digestProvider.get(), otsIndex[h]); + treeToConstruct.update(ots.getPublicKey()); + } + + if (treeToConstruct.wasFinished()) + { + return treeToConstruct; + } + System.err.println("N�chster Baum noch nicht fertig konstruiert!!!"); + return null; + } + + /** + * This method initializes the GMSS KeyPairGenerator using an integer value + * <code>keySize</code> as input. It provides a simple use of the GMSS for + * testing demands. + * <p> + * A given <code>keysize</code> of less than 10 creates an amount 2^10 + * signatures. A keySize between 10 and 20 creates 2^20 signatures. Given an + * integer greater than 20 the key pair generator creates 2^40 signatures. + * + * @param keySize Assigns the parameters used for the GMSS signatures. There are + * 3 choices:<br> + * 1. keysize <= 10: creates 2^10 signatures using the + * parameterset<br> + * P = (2, (5, 5), (3, 3), (3, 3))<br> + * 2. keysize > 10 and <= 20: creates 2^20 signatures using the + * parameterset<br> + * P = (2, (10, 10), (5, 4), (2, 2))<br> + * 3. keysize > 20: creates 2^40 signatures using the + * parameterset<br> + * P = (2, (10, 10, 10, 10), (9, 9, 9, 3), (2, 2, 2, 2)) + * @param secureRandom not used by GMSS, the SHA1PRNG of the SUN Provider is always + * used + */ + public void initialize(int keySize, SecureRandom secureRandom) + { + + KeyGenerationParameters kgp; + if (keySize <= 10) + { // create 2^10 keys + int[] defh = {10}; + int[] defw = {3}; + int[] defk = {2}; + // XXX sec random neede? + kgp = new GMSSKeyGenerationParameters(secureRandom, new GMSSParameters(defh.length, defh, defw, defk)); + } + else if (keySize <= 20) + { // create 2^20 keys + int[] defh = {10, 10}; + int[] defw = {5, 4}; + int[] defk = {2, 2}; + kgp = new GMSSKeyGenerationParameters(secureRandom, new GMSSParameters(defh.length, defh, defw, defk)); + } + else + { // create 2^40 keys, keygen lasts around 80 seconds + int[] defh = {10, 10, 10, 10}; + int[] defw = {9, 9, 9, 3}; + int[] defk = {2, 2, 2, 2}; + kgp = new GMSSKeyGenerationParameters(secureRandom, new GMSSParameters(defh.length, defh, defw, defk)); + } + + // call the initializer with the chosen parameters + this.initialize(kgp); + + } + + + /** + * Initalizes the key pair generator using a parameter set as input + */ + public void initialize(KeyGenerationParameters param) + { + + this.gmssParams = (GMSSKeyGenerationParameters)param; + + // generate GMSSParameterset + this.gmssPS = new GMSSParameters(gmssParams.getParameters().getNumOfLayers(), gmssParams.getParameters().getHeightOfTrees(), + gmssParams.getParameters().getWinternitzParameter(), gmssParams.getParameters().getK()); + + this.numLayer = gmssPS.getNumOfLayers(); + this.heightOfTrees = gmssPS.getHeightOfTrees(); + this.otsIndex = gmssPS.getWinternitzParameter(); + this.K = gmssPS.getK(); + + // seeds + this.currentSeeds = new byte[numLayer][mdLength]; + this.nextNextSeeds = new byte[numLayer - 1][mdLength]; + + // construct SecureRandom for initial seed generation + SecureRandom secRan = new SecureRandom(); + + // generation of initial seeds + for (int i = 0; i < numLayer; i++) + { + secRan.nextBytes(currentSeeds[i]); + gmssRandom.nextSeed(currentSeeds[i]); + } + + this.initialized = true; + } + + /** + * This method is called by generateKeyPair() in case that no other + * initialization method has been called by the user + */ + private void initializeDefault() + { + int[] defh = {10, 10, 10, 10}; + int[] defw = {3, 3, 3, 3}; + int[] defk = {2, 2, 2, 2}; + + KeyGenerationParameters kgp = new GMSSKeyGenerationParameters(new SecureRandom(), new GMSSParameters(defh.length, defh, defw, defk)); + this.initialize(kgp); + + } + + public void init(KeyGenerationParameters param) + { + this.initialize(param); + + } + + public AsymmetricCipherKeyPair generateKeyPair() + { + return genKeyPair(); + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSKeyParameters.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSKeyParameters.java new file mode 100644 index 00000000..d2dcbba7 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSKeyParameters.java @@ -0,0 +1,22 @@ +package org.spongycastle.pqc.crypto.gmss; + +import org.spongycastle.crypto.params.AsymmetricKeyParameter; + +public class GMSSKeyParameters + extends AsymmetricKeyParameter +{ + private GMSSParameters params; + + public GMSSKeyParameters( + boolean isPrivate, + GMSSParameters params) + { + super(isPrivate); + this.params = params; + } + + public GMSSParameters getParameters() + { + return params; + } +}
\ No newline at end of file diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSLeaf.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSLeaf.java new file mode 100644 index 00000000..ade340ad --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSLeaf.java @@ -0,0 +1,376 @@ +package org.spongycastle.pqc.crypto.gmss; + +import org.spongycastle.crypto.Digest; +import org.spongycastle.pqc.crypto.gmss.util.GMSSRandom; +import org.spongycastle.util.Arrays; +import org.spongycastle.util.encoders.Hex; + + +/** + * This class implements the distributed computation of the public key of the + * Winternitz one-time signature scheme (OTSS). The class is used by the GMSS + * classes for calculation of upcoming leafs. + */ +public class GMSSLeaf +{ + + /** + * The hash function used by the OTS and the PRNG + */ + private Digest messDigestOTS; + + /** + * The length of the message digest and private key + */ + private int mdsize, keysize; + + /** + * The source of randomness for OTS private key generation + */ + private GMSSRandom gmssRandom; + + /** + * Byte array for distributed computation of the upcoming leaf + */ + private byte[] leaf; + + /** + * Byte array for storing the concatenated hashes of private key parts + */ + private byte[] concHashs; + + /** + * indices for distributed computation + */ + private int i, j; + + /** + * storing 2^w + */ + private int two_power_w; + + /** + * Winternitz parameter w + */ + private int w; + + /** + * the amount of distributed computation steps when updateLeaf is called + */ + private int steps; + + /** + * the internal seed + */ + private byte[] seed; + + /** + * the OTS privateKey parts + */ + byte[] privateKeyOTS; + + /** + * This constructor regenerates a prior GMSSLeaf object + * + * @param digest an array of strings, containing the name of the used hash + * function and PRNG and the name of the corresponding + * provider + * @param otsIndex status bytes + * @param numLeafs status ints + */ + public GMSSLeaf(Digest digest, byte[][] otsIndex, int[] numLeafs) + { + this.i = numLeafs[0]; + this.j = numLeafs[1]; + this.steps = numLeafs[2]; + this.w = numLeafs[3]; + + messDigestOTS = digest; + + gmssRandom = new GMSSRandom(messDigestOTS); + + // calulate keysize for private key and the help array + mdsize = messDigestOTS.getDigestSize(); + int mdsizeBit = mdsize << 3; + int messagesize = (int)Math.ceil((double)(mdsizeBit) / (double)w); + int checksumsize = getLog((messagesize << w) + 1); + this.keysize = messagesize + + (int)Math.ceil((double)checksumsize / (double)w); + this.two_power_w = 1 << w; + + // calculate steps + // ((2^w)-1)*keysize + keysize + 1 / (2^h -1) + + // initialize arrays + this.privateKeyOTS = otsIndex[0]; + this.seed = otsIndex[1]; + this.concHashs = otsIndex[2]; + this.leaf = otsIndex[3]; + } + + /** + * The constructor precomputes some needed variables for distributed leaf + * calculation + * + * @param digest an array of strings, containing the digest of the used hash + * function and PRNG and the digest of the corresponding + * provider + * @param w the winterniz parameter of that tree the leaf is computed + * for + * @param numLeafs the number of leafs of the tree from where the distributed + * computation is called + */ + GMSSLeaf(Digest digest, int w, int numLeafs) + { + this.w = w; + + messDigestOTS = digest; + + gmssRandom = new GMSSRandom(messDigestOTS); + + // calulate keysize for private key and the help array + mdsize = messDigestOTS.getDigestSize(); + int mdsizeBit = mdsize << 3; + int messagesize = (int)Math.ceil((double)(mdsizeBit) / (double)w); + int checksumsize = getLog((messagesize << w) + 1); + this.keysize = messagesize + + (int)Math.ceil((double)checksumsize / (double)w); + this.two_power_w = 1 << w; + + // calculate steps + // ((2^w)-1)*keysize + keysize + 1 / (2^h -1) + this.steps = (int)Math + .ceil((double)(((1 << w) - 1) * keysize + 1 + keysize) + / (double)(numLeafs)); + + // initialize arrays + this.seed = new byte[mdsize]; + this.leaf = new byte[mdsize]; + this.privateKeyOTS = new byte[mdsize]; + this.concHashs = new byte[mdsize * keysize]; + } + + public GMSSLeaf(Digest digest, int w, int numLeafs, byte[] seed0) + { + this.w = w; + + messDigestOTS = digest; + + gmssRandom = new GMSSRandom(messDigestOTS); + + // calulate keysize for private key and the help array + mdsize = messDigestOTS.getDigestSize(); + int mdsizeBit = mdsize << 3; + int messagesize = (int)Math.ceil((double)(mdsizeBit) / (double)w); + int checksumsize = getLog((messagesize << w) + 1); + this.keysize = messagesize + + (int)Math.ceil((double)checksumsize / (double)w); + this.two_power_w = 1 << w; + + // calculate steps + // ((2^w)-1)*keysize + keysize + 1 / (2^h -1) + this.steps = (int)Math + .ceil((double)(((1 << w) - 1) * keysize + 1 + keysize) + / (double)(numLeafs)); + + // initialize arrays + this.seed = new byte[mdsize]; + this.leaf = new byte[mdsize]; + this.privateKeyOTS = new byte[mdsize]; + this.concHashs = new byte[mdsize * keysize]; + + initLeafCalc(seed0); + } + + private GMSSLeaf(GMSSLeaf original) + { + this.messDigestOTS = original.messDigestOTS; + this.mdsize = original.mdsize; + this.keysize = original.keysize; + this.gmssRandom = original.gmssRandom; + this.leaf = Arrays.clone(original.leaf); + this.concHashs = Arrays.clone(original.concHashs); + this.i = original.i; + this.j = original.j; + this.two_power_w = original.two_power_w; + this.w = original.w; + this.steps = original.steps; + this.seed = Arrays.clone(original.seed); + this.privateKeyOTS = Arrays.clone(original.privateKeyOTS); + } + + /** + * initialize the distributed leaf calculation reset i,j and compute OTSseed + * with seed0 + * + * @param seed0 the starting seed + */ + // TODO: this really looks like it should be either always called from a constructor or nextLeaf. + void initLeafCalc(byte[] seed0) + { + this.i = 0; + this.j = 0; + byte[] dummy = new byte[mdsize]; + System.arraycopy(seed0, 0, dummy, 0, seed.length); + this.seed = gmssRandom.nextSeed(dummy); + } + + GMSSLeaf nextLeaf() + { + GMSSLeaf nextLeaf = new GMSSLeaf(this); + + nextLeaf.updateLeafCalc(); + + return nextLeaf; + } + + /** + * Processes <code>steps</code> steps of distributed leaf calculation + * + * @return true if leaf is completed, else false + */ + private void updateLeafCalc() + { + byte[] buf = new byte[messDigestOTS.getDigestSize()]; + + // steps times do + // TODO: this really needs to be looked at, the 10000 has been added as + // prior to this the leaf value always ended up as zeros. + for (int s = 0; s < steps + 10000; s++) + { + if (i == keysize && j == two_power_w - 1) + { // [3] at last hash the + // concatenation + messDigestOTS.update(concHashs, 0, concHashs.length); + leaf = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(leaf, 0); + return; + } + else if (i == 0 || j == two_power_w - 1) + { // [1] at the + // beginning and + // when [2] is + // finished: get the + // next private key + // part + i++; + j = 0; + // get next privKey part + this.privateKeyOTS = gmssRandom.nextSeed(seed); + } + else + { // [2] hash the privKey part + messDigestOTS.update(privateKeyOTS, 0, privateKeyOTS.length); + privateKeyOTS = buf; + messDigestOTS.doFinal(privateKeyOTS, 0); + j++; + if (j == two_power_w - 1) + { // after w hashes add to the + // concatenated array + System.arraycopy(privateKeyOTS, 0, concHashs, mdsize + * (i - 1), mdsize); + } + } + } + + throw new IllegalStateException("unable to updateLeaf in steps: " + steps + " " + i + " " + j); + } + + /** + * Returns the leaf value. + * + * @return the leaf value + */ + public byte[] getLeaf() + { + return Arrays.clone(leaf); + } + + /** + * This method returns the least integer that is greater or equal to the + * logarithm to the base 2 of an integer <code>intValue</code>. + * + * @param intValue an integer + * @return The least integer greater or equal to the logarithm to the base 2 + * of <code>intValue</code> + */ + private int getLog(int intValue) + { + int log = 1; + int i = 2; + while (i < intValue) + { + i <<= 1; + log++; + } + return log; + } + + /** + * Returns the status byte array used by the GMSSPrivateKeyASN.1 class + * + * @return The status bytes + */ + public byte[][] getStatByte() + { + + byte[][] statByte = new byte[4][]; + statByte[0] = new byte[mdsize]; + statByte[1] = new byte[mdsize]; + statByte[2] = new byte[mdsize * keysize]; + statByte[3] = new byte[mdsize]; + statByte[0] = privateKeyOTS; + statByte[1] = seed; + statByte[2] = concHashs; + statByte[3] = leaf; + + return statByte; + } + + /** + * Returns the status int array used by the GMSSPrivateKeyASN.1 class + * + * @return The status ints + */ + public int[] getStatInt() + { + + int[] statInt = new int[4]; + statInt[0] = i; + statInt[1] = j; + statInt[2] = steps; + statInt[3] = w; + return statInt; + } + + /** + * Returns a String representation of the main part of this element + * + * @return a String representation of the main part of this element + */ + public String toString() + { + String out = ""; + + for (int i = 0; i < 4; i++) + { + out = out + this.getStatInt()[i] + " "; + } + out = out + " " + this.mdsize + " " + this.keysize + " " + + this.two_power_w + " "; + + byte[][] temp = this.getStatByte(); + for (int i = 0; i < 4; i++) + { + if (temp[i] != null) + { + out = out + new String(Hex.encode(temp[i])) + " "; + } + else + { + out = out + "null "; + } + } + return out; + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSParameters.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSParameters.java new file mode 100644 index 00000000..c78d50e3 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSParameters.java @@ -0,0 +1,155 @@ +package org.spongycastle.pqc.crypto.gmss; + +import org.spongycastle.util.Arrays; + +/** + * This class provides a specification for the GMSS parameters that are used by + * the GMSSKeyPairGenerator and GMSSSignature classes. + * + * @see org.spongycastle.pqc.crypto.gmss.GMSSKeyPairGenerator + */ +public class GMSSParameters +{ + /** + * The number of authentication tree layers. + */ + private int numOfLayers; + + /** + * The height of the authentication trees of each layer. + */ + private int[] heightOfTrees; + + /** + * The Winternitz Parameter 'w' of each layer. + */ + private int[] winternitzParameter; + + /** + * The parameter K needed for the authentication path computation + */ + private int[] K; + + /** + * The constructor for the parameters of the GMSSKeyPairGenerator. + * + * @param layers the number of authentication tree layers + * @param heightOfTrees the height of the authentication trees + * @param winternitzParameter the Winternitz Parameter 'w' of each layer + * @param K parameter for authpath computation + */ + public GMSSParameters(int layers, int[] heightOfTrees, int[] winternitzParameter, int[] K) + throws IllegalArgumentException + { + init(layers, heightOfTrees, winternitzParameter, K); + } + + private void init(int layers, int[] heightOfTrees, + int[] winternitzParameter, int[] K) + throws IllegalArgumentException + { + boolean valid = true; + String errMsg = ""; + this.numOfLayers = layers; + if ((numOfLayers != winternitzParameter.length) + || (numOfLayers != heightOfTrees.length) + || (numOfLayers != K.length)) + { + valid = false; + errMsg = "Unexpected parameterset format"; + } + for (int i = 0; i < numOfLayers; i++) + { + if ((K[i] < 2) || ((heightOfTrees[i] - K[i]) % 2 != 0)) + { + valid = false; + errMsg = "Wrong parameter K (K >= 2 and H-K even required)!"; + } + + if ((heightOfTrees[i] < 4) || (winternitzParameter[i] < 2)) + { + valid = false; + errMsg = "Wrong parameter H or w (H > 3 and w > 1 required)!"; + } + } + + if (valid) + { + this.heightOfTrees = Arrays.clone(heightOfTrees); + this.winternitzParameter = Arrays.clone(winternitzParameter); + this.K = Arrays.clone(K); + } + else + { + throw new IllegalArgumentException(errMsg); + } + } + + public GMSSParameters(int keySize) + throws IllegalArgumentException + { + if (keySize <= 10) + { // create 2^10 keys + int[] defh = {10}; + int[] defw = {3}; + int[] defk = {2}; + this.init(defh.length, defh, defw, defk); + } + else if (keySize <= 20) + { // create 2^20 keys + int[] defh = {10, 10}; + int[] defw = {5, 4}; + int[] defk = {2, 2}; + this.init(defh.length, defh, defw, defk); + } + else + { // create 2^40 keys, keygen lasts around 80 seconds + int[] defh = {10, 10, 10, 10}; + int[] defw = {9, 9, 9, 3}; + int[] defk = {2, 2, 2, 2}; + this.init(defh.length, defh, defw, defk); + } + } + + /** + * Returns the number of levels of the authentication trees. + * + * @return The number of levels of the authentication trees. + */ + public int getNumOfLayers() + { + return numOfLayers; + } + + /** + * Returns the array of height (for each layer) of the authentication trees + * + * @return The array of height (for each layer) of the authentication trees + */ + public int[] getHeightOfTrees() + { + return Arrays.clone(heightOfTrees); + } + + /** + * Returns the array of WinternitzParameter (for each layer) of the + * authentication trees + * + * @return The array of WinternitzParameter (for each layer) of the + * authentication trees + */ + public int[] getWinternitzParameter() + { + return Arrays.clone(winternitzParameter); + } + + /** + * Returns the parameter K needed for authentication path computation + * + * @return The parameter K needed for authentication path computation + */ + public int[] getK() + { + return Arrays.clone(K); + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSPrivateKeyParameters.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSPrivateKeyParameters.java new file mode 100644 index 00000000..29e84b1f --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSPrivateKeyParameters.java @@ -0,0 +1,1041 @@ +package org.spongycastle.pqc.crypto.gmss; + +import java.util.Vector; + +import org.spongycastle.crypto.Digest; +import org.spongycastle.pqc.crypto.gmss.util.GMSSRandom; +import org.spongycastle.pqc.crypto.gmss.util.WinternitzOTSignature; +import org.spongycastle.util.Arrays; + + +/** + * This class provides a specification for a GMSS private key. + */ +public class GMSSPrivateKeyParameters + extends GMSSKeyParameters +{ + private int[] index; + + private byte[][] currentSeeds; + private byte[][] nextNextSeeds; + + private byte[][][] currentAuthPaths; + private byte[][][] nextAuthPaths; + + private Treehash[][] currentTreehash; + private Treehash[][] nextTreehash; + + private Vector[] currentStack; + private Vector[] nextStack; + + private Vector[][] currentRetain; + private Vector[][] nextRetain; + + private byte[][][] keep; + + private GMSSLeaf[] nextNextLeaf; + private GMSSLeaf[] upperLeaf; + private GMSSLeaf[] upperTreehashLeaf; + + private int[] minTreehash; + + private GMSSParameters gmssPS; + + private byte[][] nextRoot; + private GMSSRootCalc[] nextNextRoot; + + private byte[][] currentRootSig; + private GMSSRootSig[] nextRootSig; + + private GMSSDigestProvider digestProvider; + + private boolean used = false; + + /** + * An array of the heights of the authentication trees of each layer + */ + private int[] heightOfTrees; + + /** + * An array of the Winternitz parameter 'w' of each layer + */ + private int[] otsIndex; + + /** + * The parameter K needed for the authentication path computation + */ + private int[] K; + + /** + * the number of Layers + */ + private int numLayer; + + /** + * The hash function used to construct the authentication trees + */ + private Digest messDigestTrees; + + /** + * The message digest length + */ + private int mdLength; + + /** + * The PRNG used for private key generation + */ + private GMSSRandom gmssRandom; + + + /** + * The number of leafs of one tree of each layer + */ + private int[] numLeafs; + + + /** + * Generates a new GMSS private key + * + * @param currentSeed seed for the generation of private OTS keys for the + * current subtrees + * @param nextNextSeed seed for the generation of private OTS keys for the next + * subtrees + * @param currentAuthPath array of current authentication paths + * @param nextAuthPath array of next authentication paths + * @param currentTreehash array of current treehash instances + * @param nextTreehash array of next treehash instances + * @param currentStack array of current shared stacks + * @param nextStack array of next shared stacks + * @param currentRetain array of current retain stacks + * @param nextRetain array of next retain stacks + * @param nextRoot the roots of the next subtree + * @param currentRootSig array of signatures of the roots of the current subtrees + * @param gmssParameterset the GMSS Parameterset + * @see org.spongycastle.pqc.crypto.gmss.GMSSKeyPairGenerator + */ + + public GMSSPrivateKeyParameters(byte[][] currentSeed, byte[][] nextNextSeed, + byte[][][] currentAuthPath, byte[][][] nextAuthPath, + Treehash[][] currentTreehash, Treehash[][] nextTreehash, + Vector[] currentStack, Vector[] nextStack, + Vector[][] currentRetain, Vector[][] nextRetain, byte[][] nextRoot, + byte[][] currentRootSig, GMSSParameters gmssParameterset, + GMSSDigestProvider digestProvider) + { + this(null, currentSeed, nextNextSeed, currentAuthPath, nextAuthPath, + null, currentTreehash, nextTreehash, currentStack, nextStack, + currentRetain, nextRetain, null, null, null, null, nextRoot, + null, currentRootSig, null, gmssParameterset, digestProvider); + } + + /** + * /** + * + * @param index tree indices + * @param keep keep array for the authPath algorithm + * @param currentTreehash treehash for authPath algorithm of current tree + * @param nextTreehash treehash for authPath algorithm of next tree (TREE+) + * @param currentStack shared stack for authPath algorithm of current tree + * @param nextStack shared stack for authPath algorithm of next tree (TREE+) + * @param currentRetain retain stack for authPath algorithm of current tree + * @param nextRetain retain stack for authPath algorithm of next tree (TREE+) + * @param nextNextLeaf array of upcoming leafs of the tree after next (LEAF++) of + * each layer + * @param upperLeaf needed for precomputation of upper nodes + * @param upperTreehashLeaf needed for precomputation of upper treehash nodes + * @param minTreehash index of next treehash instance to receive an update + * @param nextRoot the roots of the next trees (ROOT+) + * @param nextNextRoot the roots of the tree after next (ROOT++) + * @param currentRootSig array of signatures of the roots of the current subtrees + * (SIG) + * @param nextRootSig array of signatures of the roots of the next subtree + * (SIG+) + * @param gmssParameterset the GMSS Parameterset + */ + public GMSSPrivateKeyParameters(int[] index, byte[][] currentSeeds, + byte[][] nextNextSeeds, byte[][][] currentAuthPaths, + byte[][][] nextAuthPaths, byte[][][] keep, + Treehash[][] currentTreehash, Treehash[][] nextTreehash, + Vector[] currentStack, Vector[] nextStack, + Vector[][] currentRetain, Vector[][] nextRetain, + GMSSLeaf[] nextNextLeaf, GMSSLeaf[] upperLeaf, + GMSSLeaf[] upperTreehashLeaf, int[] minTreehash, byte[][] nextRoot, + GMSSRootCalc[] nextNextRoot, byte[][] currentRootSig, + GMSSRootSig[] nextRootSig, GMSSParameters gmssParameterset, + GMSSDigestProvider digestProvider) + { + + super(true, gmssParameterset); + + // construct message digest + + this.messDigestTrees = digestProvider.get(); + this.mdLength = messDigestTrees.getDigestSize(); + + + // Parameter + this.gmssPS = gmssParameterset; + this.otsIndex = gmssParameterset.getWinternitzParameter(); + this.K = gmssParameterset.getK(); + this.heightOfTrees = gmssParameterset.getHeightOfTrees(); + // initialize numLayer + this.numLayer = gmssPS.getNumOfLayers(); + + // initialize index if null + if (index == null) + { + this.index = new int[numLayer]; + for (int i = 0; i < numLayer; i++) + { + this.index[i] = 0; + } + } + else + { + this.index = index; + } + + this.currentSeeds = currentSeeds; + this.nextNextSeeds = nextNextSeeds; + + this.currentAuthPaths = currentAuthPaths; + this.nextAuthPaths = nextAuthPaths; + + // initialize keep if null + if (keep == null) + { + this.keep = new byte[numLayer][][]; + for (int i = 0; i < numLayer; i++) + { + this.keep[i] = new byte[(int)Math.floor(heightOfTrees[i] / 2)][mdLength]; + } + } + else + { + this.keep = keep; + } + + // initialize stack if null + if (currentStack == null) + { + this.currentStack = new Vector[numLayer]; + for (int i = 0; i < numLayer; i++) + { + this.currentStack[i] = new Vector(); + } + } + else + { + this.currentStack = currentStack; + } + + // initialize nextStack if null + if (nextStack == null) + { + this.nextStack = new Vector[numLayer - 1]; + for (int i = 0; i < numLayer - 1; i++) + { + this.nextStack[i] = new Vector(); + } + } + else + { + this.nextStack = nextStack; + } + + this.currentTreehash = currentTreehash; + this.nextTreehash = nextTreehash; + + this.currentRetain = currentRetain; + this.nextRetain = nextRetain; + + this.nextRoot = nextRoot; + + this.digestProvider = digestProvider; + + if (nextNextRoot == null) + { + this.nextNextRoot = new GMSSRootCalc[numLayer - 1]; + for (int i = 0; i < numLayer - 1; i++) + { + this.nextNextRoot[i] = new GMSSRootCalc( + this.heightOfTrees[i + 1], this.K[i + 1], this.digestProvider); + } + } + else + { + this.nextNextRoot = nextNextRoot; + } + this.currentRootSig = currentRootSig; + + // calculate numLeafs + numLeafs = new int[numLayer]; + for (int i = 0; i < numLayer; i++) + { + numLeafs[i] = 1 << heightOfTrees[i]; + } + // construct PRNG + this.gmssRandom = new GMSSRandom(messDigestTrees); + + if (numLayer > 1) + { + // construct the nextNextLeaf (LEAFs++) array for upcoming leafs in + // tree after next (TREE++) + if (nextNextLeaf == null) + { + this.nextNextLeaf = new GMSSLeaf[numLayer - 2]; + for (int i = 0; i < numLayer - 2; i++) + { + this.nextNextLeaf[i] = new GMSSLeaf(digestProvider.get(), otsIndex[i + 1], numLeafs[i + 2], this.nextNextSeeds[i]); + } + } + else + { + this.nextNextLeaf = nextNextLeaf; + } + } + else + { + this.nextNextLeaf = new GMSSLeaf[0]; + } + + // construct the upperLeaf array for upcoming leafs in tree over the + // actual + if (upperLeaf == null) + { + this.upperLeaf = new GMSSLeaf[numLayer - 1]; + for (int i = 0; i < numLayer - 1; i++) + { + this.upperLeaf[i] = new GMSSLeaf(digestProvider.get(), otsIndex[i], + numLeafs[i + 1], this.currentSeeds[i]); + } + } + else + { + this.upperLeaf = upperLeaf; + } + + // construct the leafs for upcoming leafs in treehashs in tree over the + // actual + if (upperTreehashLeaf == null) + { + this.upperTreehashLeaf = new GMSSLeaf[numLayer - 1]; + for (int i = 0; i < numLayer - 1; i++) + { + this.upperTreehashLeaf[i] = new GMSSLeaf(digestProvider.get(), otsIndex[i], numLeafs[i + 1]); + } + } + else + { + this.upperTreehashLeaf = upperTreehashLeaf; + } + + if (minTreehash == null) + { + this.minTreehash = new int[numLayer - 1]; + for (int i = 0; i < numLayer - 1; i++) + { + this.minTreehash[i] = -1; + } + } + else + { + this.minTreehash = minTreehash; + } + + // construct the nextRootSig (RootSig++) + byte[] dummy = new byte[mdLength]; + byte[] OTSseed = new byte[mdLength]; + if (nextRootSig == null) + { + this.nextRootSig = new GMSSRootSig[numLayer - 1]; + for (int i = 0; i < numLayer - 1; i++) + { + System.arraycopy(currentSeeds[i], 0, dummy, 0, mdLength); + gmssRandom.nextSeed(dummy); + OTSseed = gmssRandom.nextSeed(dummy); + this.nextRootSig[i] = new GMSSRootSig(digestProvider.get(), otsIndex[i], + heightOfTrees[i + 1]); + this.nextRootSig[i].initSign(OTSseed, nextRoot[i]); + } + } + else + { + this.nextRootSig = nextRootSig; + } + } + + // we assume this only gets called from nextKey so used is never copied. + private GMSSPrivateKeyParameters(GMSSPrivateKeyParameters original) + { + super(true, original.getParameters()); + + this.index = Arrays.clone(original.index); + this.currentSeeds = Arrays.clone(original.currentSeeds); + this.nextNextSeeds = Arrays.clone(original.nextNextSeeds); + this.currentAuthPaths = Arrays.clone(original.currentAuthPaths); + this.nextAuthPaths = Arrays.clone(original.nextAuthPaths); + this.currentTreehash = original.currentTreehash; + this.nextTreehash = original.nextTreehash; + this.currentStack = original.currentStack; + this.nextStack = original.nextStack; + this.currentRetain = original.currentRetain; + this.nextRetain = original.nextRetain; + this.keep = Arrays.clone(original.keep); + this.nextNextLeaf = original.nextNextLeaf; + this.upperLeaf = original.upperLeaf; + this.upperTreehashLeaf = original.upperTreehashLeaf; + this.minTreehash = original.minTreehash; + this.gmssPS = original.gmssPS; + this.nextRoot = Arrays.clone(original.nextRoot); + this.nextNextRoot = original.nextNextRoot; + this.currentRootSig = original.currentRootSig; + this.nextRootSig = original.nextRootSig; + this.digestProvider = original.digestProvider; + this.heightOfTrees = original.heightOfTrees; + this.otsIndex = original.otsIndex; + this.K = original.K; + this.numLayer = original.numLayer; + this.messDigestTrees = original.messDigestTrees; + this.mdLength = original.mdLength; + this.gmssRandom = original.gmssRandom; + this.numLeafs = original.numLeafs; + } + + public boolean isUsed() + { + return this.used; + } + + public void markUsed() + { + this.used = true; + } + + public GMSSPrivateKeyParameters nextKey() + { + GMSSPrivateKeyParameters nKey = new GMSSPrivateKeyParameters(this); + + nKey.nextKey(gmssPS.getNumOfLayers() - 1); + + return nKey; + } + + /** + * This method updates the GMSS private key for the next signature + * + * @param layer the layer where the next key is processed + */ + private void nextKey(int layer) + { + // only for lowest layer ( other layers indices are raised in nextTree() + // method ) + if (layer == numLayer - 1) + { + index[layer]++; + } // else System.out.println(" --- nextKey on layer " + layer + " + // index is now : " + index[layer]); + + // if tree of this layer is depleted + if (index[layer] == numLeafs[layer]) + { + if (numLayer != 1) + { + nextTree(layer); + index[layer] = 0; + } + } + else + { + updateKey(layer); + } + } + + /** + * Switch to next subtree if the current one is depleted + * + * @param layer the layer where the next tree is processed + */ + private void nextTree(int layer) + { + // System.out.println("NextTree method called on layer " + layer); + // dont create next tree for the top layer + if (layer > 0) + { + // raise index for upper layer + index[layer - 1]++; + + // test if it is already the last tree + boolean lastTree = true; + int z = layer; + do + { + z--; + if (index[z] < numLeafs[z]) + { + lastTree = false; + } + } + while (lastTree && (z > 0)); + + // only construct next subtree if last one is not already in use + if (!lastTree) + { + gmssRandom.nextSeed(currentSeeds[layer]); + + // last step of distributed signature calculation + nextRootSig[layer - 1].updateSign(); + + // last step of distributed leaf calculation for nextNextLeaf + if (layer > 1) + { + nextNextLeaf[layer - 1 - 1] = nextNextLeaf[layer - 1 - 1].nextLeaf(); + } + + // last step of distributed leaf calculation for upper leaf + upperLeaf[layer - 1] = upperLeaf[layer - 1].nextLeaf(); + + // last step of distributed leaf calculation for all treehashs + + if (minTreehash[layer - 1] >= 0) + { + upperTreehashLeaf[layer - 1] = upperTreehashLeaf[layer - 1].nextLeaf(); + byte[] leaf = this.upperTreehashLeaf[layer - 1].getLeaf(); + // if update is required use the precomputed leaf to update + // treehash + try + { + currentTreehash[layer - 1][minTreehash[layer - 1]] + .update(this.gmssRandom, leaf); + // System.out.println("UUUpdated TH " + + // minTreehash[layer - 1]); + if (currentTreehash[layer - 1][minTreehash[layer - 1]] + .wasFinished()) + { + // System.out.println("FFFinished TH " + + // minTreehash[layer - 1]); + } + } + catch (Exception e) + { + System.out.println(e); + } + } + + // last step of nextNextAuthRoot calculation + this.updateNextNextAuthRoot(layer); + + // ******************************************************** / + + // NOW: advance to next tree on layer 'layer' + + // NextRootSig --> currentRootSigs + this.currentRootSig[layer - 1] = nextRootSig[layer - 1] + .getSig(); + + // ----------------------- + + // nextTreehash --> currentTreehash + // nextNextTreehash --> nextTreehash + for (int i = 0; i < heightOfTrees[layer] - K[layer]; i++) + { + this.currentTreehash[layer][i] = this.nextTreehash[layer - 1][i]; + this.nextTreehash[layer - 1][i] = this.nextNextRoot[layer - 1] + .getTreehash()[i]; + } + + // NextAuthPath --> currentAuthPath + // nextNextAuthPath --> nextAuthPath + for (int i = 0; i < heightOfTrees[layer]; i++) + { + System.arraycopy(nextAuthPaths[layer - 1][i], 0, + currentAuthPaths[layer][i], 0, mdLength); + System.arraycopy(nextNextRoot[layer - 1].getAuthPath()[i], + 0, nextAuthPaths[layer - 1][i], 0, mdLength); + } + + // nextRetain --> currentRetain + // nextNextRetain --> nextRetain + for (int i = 0; i < K[layer] - 1; i++) + { + this.currentRetain[layer][i] = this.nextRetain[layer - 1][i]; + this.nextRetain[layer - 1][i] = this.nextNextRoot[layer - 1] + .getRetain()[i]; + } + + // nextStack --> currentStack + this.currentStack[layer] = this.nextStack[layer - 1]; + // nextNextStack --> nextStack + this.nextStack[layer - 1] = this.nextNextRoot[layer - 1] + .getStack(); + + // nextNextRoot --> nextRoot + this.nextRoot[layer - 1] = this.nextNextRoot[layer - 1] + .getRoot(); + // ----------------------- + + // ----------------- + byte[] OTSseed = new byte[mdLength]; + byte[] dummy = new byte[mdLength]; + // gmssRandom.setSeed(currentSeeds[layer]); + System + .arraycopy(currentSeeds[layer - 1], 0, dummy, 0, + mdLength); + OTSseed = gmssRandom.nextSeed(dummy); // only need OTSSeed + OTSseed = gmssRandom.nextSeed(dummy); + OTSseed = gmssRandom.nextSeed(dummy); + // nextWinSig[layer-1]=new + // GMSSWinSig(OTSseed,algNames,otsIndex[layer-1],heightOfTrees[layer],nextRoot[layer-1]); + nextRootSig[layer - 1].initSign(OTSseed, nextRoot[layer - 1]); + + // nextKey for upper layer + nextKey(layer - 1); + } + } + } + + /** + * This method computes the authpath (AUTH) for the current tree, + * Additionally the root signature for the next tree (SIG+), the authpath + * (AUTH++) and root (ROOT++) for the tree after next in layer + * <code>layer</code>, and the LEAF++^1 for the next next tree in the + * layer above are updated This method is used by nextKey() + * + * @param layer + */ + private void updateKey(int layer) + { + // ----------current tree processing of actual layer--------- + // compute upcoming authpath for current Tree (AUTH) + computeAuthPaths(layer); + + // -----------distributed calculations part------------ + // not for highest tree layer + if (layer > 0) + { + + // compute (partial) next leaf on TREE++ (not on layer 1 and 0) + if (layer > 1) + { + nextNextLeaf[layer - 1 - 1] = nextNextLeaf[layer - 1 - 1].nextLeaf(); + } + + // compute (partial) next leaf on tree above (not on layer 0) + upperLeaf[layer - 1] = upperLeaf[layer - 1].nextLeaf(); + + // compute (partial) next leaf for all treehashs on tree above (not + // on layer 0) + + int t = (int)Math + .floor((double)(this.getNumLeafs(layer) * 2) + / (double)(this.heightOfTrees[layer - 1] - this.K[layer - 1])); + + if (index[layer] % t == 1) + { + // System.out.println(" layer: " + layer + " index: " + + // index[layer] + " t : " + t); + + // take precomputed node for treehash update + // ------------------------------------------------ + if (index[layer] > 1 && minTreehash[layer - 1] >= 0) + { + byte[] leaf = this.upperTreehashLeaf[layer - 1].getLeaf(); + // if update is required use the precomputed leaf to update + // treehash + try + { + currentTreehash[layer - 1][minTreehash[layer - 1]] + .update(this.gmssRandom, leaf); + // System.out.println("Updated TH " + minTreehash[layer + // - 1]); + if (currentTreehash[layer - 1][minTreehash[layer - 1]] + .wasFinished()) + { + // System.out.println("Finished TH " + + // minTreehash[layer - 1]); + } + } + catch (Exception e) + { + System.out.println(e); + } + // ------------------------------------------------ + } + + // initialize next leaf precomputation + // ------------------------------------------------ + + // get lowest index of treehashs + this.minTreehash[layer - 1] = getMinTreehashIndex(layer - 1); + + if (this.minTreehash[layer - 1] >= 0) + { + // initialize leaf + byte[] seed = this.currentTreehash[layer - 1][this.minTreehash[layer - 1]] + .getSeedActive(); + this.upperTreehashLeaf[layer - 1] = new GMSSLeaf( + this.digestProvider.get(), this.otsIndex[layer - 1], t, seed); + this.upperTreehashLeaf[layer - 1] = this.upperTreehashLeaf[layer - 1].nextLeaf(); + // System.out.println("restarted treehashleaf (" + (layer - + // 1) + "," + this.minTreehash[layer - 1] + ")"); + } + // ------------------------------------------------ + + } + else + { + // update the upper leaf for the treehash one step + if (this.minTreehash[layer - 1] >= 0) + { + this.upperTreehashLeaf[layer - 1] = this.upperTreehashLeaf[layer - 1].nextLeaf(); + // if (minTreehash[layer - 1] > 3) + // System.out.print("#"); + } + } + + // compute (partial) the signature of ROOT+ (RootSig+) (not on top + // layer) + nextRootSig[layer - 1].updateSign(); + + // compute (partial) AUTHPATH++ & ROOT++ (not on top layer) + if (index[layer] == 1) + { + // init root and authpath calculation for tree after next + // (AUTH++, ROOT++) + this.nextNextRoot[layer - 1].initialize(new Vector()); + } + + // update root and authpath calculation for tree after next (AUTH++, + // ROOT++) + this.updateNextNextAuthRoot(layer); + } + // ----------- end distributed calculations part----------------- + } + + /** + * This method returns the index of the next Treehash instance that should + * receive an update + * + * @param layer the layer of the GMSS tree + * @return index of the treehash instance that should get the update + */ + private int getMinTreehashIndex(int layer) + { + int minTreehash = -1; + for (int h = 0; h < heightOfTrees[layer] - K[layer]; h++) + { + if (currentTreehash[layer][h].wasInitialized() + && !currentTreehash[layer][h].wasFinished()) + { + if (minTreehash == -1) + { + minTreehash = h; + } + else if (currentTreehash[layer][h].getLowestNodeHeight() < currentTreehash[layer][minTreehash] + .getLowestNodeHeight()) + { + minTreehash = h; + } + } + } + return minTreehash; + } + + /** + * Computes the upcoming currentAuthpath of layer <code>layer</code> using + * the revisited authentication path computation of Dahmen/Schneider 2008 + * + * @param layer the actual layer + */ + private void computeAuthPaths(int layer) + { + + int Phi = index[layer]; + int H = heightOfTrees[layer]; + int K = this.K[layer]; + + // update all nextSeeds for seed scheduling + for (int i = 0; i < H - K; i++) + { + currentTreehash[layer][i].updateNextSeed(gmssRandom); + } + + // STEP 1 of Algorithm + int Tau = heightOfPhi(Phi); + + byte[] OTSseed = new byte[mdLength]; + OTSseed = gmssRandom.nextSeed(currentSeeds[layer]); + + // STEP 2 of Algorithm + // if phi's parent on height tau + 1 if left node, store auth_tau + // in keep_tau. + // TODO check it, formerly was + // int L = Phi / (int) Math.floor(Math.pow(2, Tau + 1)); + // L %= 2; + int L = (Phi >>> (Tau + 1)) & 1; + + byte[] tempKeep = new byte[mdLength]; + // store the keep node not in keep[layer][tau/2] because it might be in + // use + // wait until the space is freed in step 4a + if (Tau < H - 1 && L == 0) + { + System.arraycopy(currentAuthPaths[layer][Tau], 0, tempKeep, 0, + mdLength); + } + + byte[] help = new byte[mdLength]; + // STEP 3 of Algorithm + // if phi is left child, compute and store leaf for next currentAuthPath + // path, + // (obtained by veriying current signature) + if (Tau == 0) + { + // LEAFCALC !!! + if (layer == numLayer - 1) + { // lowest layer computes the + // necessary leaf completely at this + // time + WinternitzOTSignature ots = new WinternitzOTSignature(OTSseed, + digestProvider.get(), otsIndex[layer]); + help = ots.getPublicKey(); + } + else + { // other layers use the precomputed leafs in + // nextNextLeaf + byte[] dummy = new byte[mdLength]; + System.arraycopy(currentSeeds[layer], 0, dummy, 0, mdLength); + gmssRandom.nextSeed(dummy); + help = upperLeaf[layer].getLeaf(); + this.upperLeaf[layer].initLeafCalc(dummy); + + // WinternitzOTSVerify otsver = new + // WinternitzOTSVerify(algNames, otsIndex[layer]); + // byte[] help2 = otsver.Verify(currentRoot[layer], + // currentRootSig[layer]); + // System.out.println(" --- " + layer + " " + + // ByteUtils.toHexString(help) + " " + + // ByteUtils.toHexString(help2)); + } + System.arraycopy(help, 0, currentAuthPaths[layer][0], 0, mdLength); + } + else + { + // STEP 4a of Algorithm + // get new left currentAuthPath node on height tau + byte[] toBeHashed = new byte[mdLength << 1]; + System.arraycopy(currentAuthPaths[layer][Tau - 1], 0, toBeHashed, + 0, mdLength); + // free the shared keep[layer][tau/2] + System.arraycopy(keep[layer][(int)Math.floor((Tau - 1) / 2)], 0, + toBeHashed, mdLength, mdLength); + messDigestTrees.update(toBeHashed, 0, toBeHashed.length); + currentAuthPaths[layer][Tau] = new byte[messDigestTrees.getDigestSize()]; + messDigestTrees.doFinal(currentAuthPaths[layer][Tau], 0); + + // STEP 4b and 4c of Algorithm + // copy right nodes to currentAuthPath on height 0..Tau-1 + for (int i = 0; i < Tau; i++) + { + + // STEP 4b of Algorithm + // 1st: copy from treehashs + if (i < H - K) + { + if (currentTreehash[layer][i].wasFinished()) + { + System.arraycopy(currentTreehash[layer][i] + .getFirstNode(), 0, currentAuthPaths[layer][i], + 0, mdLength); + currentTreehash[layer][i].destroy(); + } + else + { + System.err + .println("Treehash (" + + layer + + "," + + i + + ") not finished when needed in AuthPathComputation"); + } + } + + // 2nd: copy precomputed values from Retain + if (i < H - 1 && i >= H - K) + { + if (currentRetain[layer][i - (H - K)].size() > 0) + { + // pop element from retain + System.arraycopy(currentRetain[layer][i - (H - K)] + .lastElement(), 0, currentAuthPaths[layer][i], + 0, mdLength); + currentRetain[layer][i - (H - K)] + .removeElementAt(currentRetain[layer][i + - (H - K)].size() - 1); + } + } + + // STEP 4c of Algorithm + // initialize new stack at heights 0..Tau-1 + if (i < H - K) + { + // create stacks anew + int startPoint = Phi + 3 * (1 << i); + if (startPoint < numLeafs[layer]) + { + // if (layer < 2) { + // System.out.println("initialized TH " + i + " on layer + // " + layer); + // } + currentTreehash[layer][i].initialize(); + } + } + } + } + + // now keep space is free to use + if (Tau < H - 1 && L == 0) + { + System.arraycopy(tempKeep, 0, + keep[layer][(int)Math.floor(Tau / 2)], 0, mdLength); + } + + // only update empty stack at height h if all other stacks have + // tailnodes with height >h + // finds active stack with lowest node height, choses lower index in + // case of tie + + // on the lowest layer leafs must be computed at once, no precomputation + // is possible. So all treehash updates are done at once here + if (layer == numLayer - 1) + { + for (int tmp = 1; tmp <= (H - K) / 2; tmp++) + { + // index of the treehash instance that receives the next update + int minTreehash = getMinTreehashIndex(layer); + + // if active treehash is found update with a leaf + if (minTreehash >= 0) + { + try + { + byte[] seed = new byte[mdLength]; + System.arraycopy( + this.currentTreehash[layer][minTreehash] + .getSeedActive(), 0, seed, 0, mdLength); + byte[] seed2 = gmssRandom.nextSeed(seed); + WinternitzOTSignature ots = new WinternitzOTSignature( + seed2, this.digestProvider.get(), this.otsIndex[layer]); + byte[] leaf = ots.getPublicKey(); + currentTreehash[layer][minTreehash].update( + this.gmssRandom, leaf); + } + catch (Exception e) + { + System.out.println(e); + } + } + } + } + else + { // on higher layers the updates are done later + this.minTreehash[layer] = getMinTreehashIndex(layer); + } + } + + /** + * Returns the largest h such that 2^h | Phi + * + * @param Phi the leaf index + * @return The largest <code>h</code> with <code>2^h | Phi</code> if + * <code>Phi!=0</code> else return <code>-1</code> + */ + private int heightOfPhi(int Phi) + { + if (Phi == 0) + { + return -1; + } + int Tau = 0; + int modul = 1; + while (Phi % modul == 0) + { + modul *= 2; + Tau += 1; + } + return Tau - 1; + } + + /** + * Updates the authentication path and root calculation for the tree after + * next (AUTH++, ROOT++) in layer <code>layer</code> + * + * @param layer + */ + private void updateNextNextAuthRoot(int layer) + { + + byte[] OTSseed = new byte[mdLength]; + OTSseed = gmssRandom.nextSeed(nextNextSeeds[layer - 1]); + + // get the necessary leaf + if (layer == numLayer - 1) + { // lowest layer computes the necessary + // leaf completely at this time + WinternitzOTSignature ots = new WinternitzOTSignature(OTSseed, + digestProvider.get(), otsIndex[layer]); + this.nextNextRoot[layer - 1].update(nextNextSeeds[layer - 1], ots + .getPublicKey()); + } + else + { // other layers use the precomputed leafs in nextNextLeaf + this.nextNextRoot[layer - 1].update(nextNextSeeds[layer - 1], nextNextLeaf[layer - 1].getLeaf()); + this.nextNextLeaf[layer - 1].initLeafCalc(nextNextSeeds[layer - 1]); + } + } + + public int[] getIndex() + { + return index; + } + + /** + * @return The current index of layer i + */ + public int getIndex(int i) + { + return index[i]; + } + + public byte[][] getCurrentSeeds() + { + return Arrays.clone(currentSeeds); + } + + public byte[][][] getCurrentAuthPaths() + { + return Arrays.clone(currentAuthPaths); + } + + /** + * @return The one-time signature of the root of the current subtree + */ + public byte[] getSubtreeRootSig(int i) + { + return currentRootSig[i]; + } + + + public GMSSDigestProvider getName() + { + return digestProvider; + } + + /** + * @return The number of leafs of each tree of layer i + */ + public int getNumLeafs(int i) + { + return numLeafs[i]; + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSPublicKeyParameters.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSPublicKeyParameters.java new file mode 100644 index 00000000..381ed00b --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSPublicKeyParameters.java @@ -0,0 +1,33 @@ +package org.spongycastle.pqc.crypto.gmss; + + +public class GMSSPublicKeyParameters + extends GMSSKeyParameters +{ + /** + * The GMSS public key + */ + private byte[] gmssPublicKey; + + /** + * The constructor. + * + * @param key a raw GMSS public key + * @param gmssParameterSet an instance of GMSSParameterset + */ + public GMSSPublicKeyParameters(byte[] key, GMSSParameters gmssParameterSet) + { + super(false, gmssParameterSet); + this.gmssPublicKey = key; + } + + /** + * Returns the GMSS public key + * + * @return The GMSS public key + */ + public byte[] getPublicKey() + { + return gmssPublicKey; + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSRootCalc.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSRootCalc.java new file mode 100644 index 00000000..88e87e9c --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSRootCalc.java @@ -0,0 +1,596 @@ +package org.spongycastle.pqc.crypto.gmss; + +import java.util.Enumeration; +import java.util.Vector; + +import org.spongycastle.crypto.Digest; +import org.spongycastle.util.Arrays; +import org.spongycastle.util.Integers; +import org.spongycastle.util.encoders.Hex; + + +/** + * This class computes a whole Merkle tree and saves the needed values for + * AuthPath computation. It is used for precomputation of the root of a + * following tree. After initialization, 2^H updates are required to complete + * the root. Every update requires one leaf value as parameter. While computing + * the root all initial values for the authentication path algorithm (treehash, + * auth, retain) are stored for later use. + */ +public class GMSSRootCalc +{ + + /** + * max height of the tree + */ + private int heightOfTree; + + /** + * length of the messageDigest + */ + private int mdLength; + + /** + * the treehash instances of the tree + */ + private Treehash[] treehash; + + /** + * stores the retain nodes for authPath computation + */ + private Vector[] retain; + + /** + * finally stores the root of the tree when finished + */ + private byte[] root; + + /** + * stores the authentication path y_1(i), i = 0..H-1 + */ + private byte[][] AuthPath; + + /** + * the value K for the authentication path computation + */ + private int K; + + /** + * Vector element that stores the nodes on the stack + */ + private Vector tailStack; + + /** + * stores the height of all nodes laying on the tailStack + */ + private Vector heightOfNodes; + /** + * The hash function used for the construction of the authentication trees + */ + private Digest messDigestTree; + + /** + * An array of strings containing the name of the hash function used to + * construct the authentication trees and used by the OTS. + */ + private GMSSDigestProvider digestProvider; + + /** + * stores the index of the current node on each height of the tree + */ + private int[] index; + + /** + * true if instance was already initialized, false otherwise + */ + private boolean isInitialized; + + /** + * true it instance was finished + */ + private boolean isFinished; + + /** + * Integer that stores the index of the next seed that has to be omitted to + * the treehashs + */ + private int indexForNextSeed; + + /** + * temporary integer that stores the height of the next treehash instance + * that gets initialized with a seed + */ + private int heightOfNextSeed; + + /** + * This constructor regenerates a prior treehash object + * + * @param digest an array of strings, containing the digest of the used hash + * function and PRNG and the digest of the corresponding + * provider + * @param statByte status bytes + * @param statInt status ints + */ + public GMSSRootCalc(Digest digest, byte[][] statByte, int[] statInt, + Treehash[] treeH, Vector[] ret) + { + this.messDigestTree = digestProvider.get(); + this.digestProvider = digestProvider; + // decode statInt + this.heightOfTree = statInt[0]; + this.mdLength = statInt[1]; + this.K = statInt[2]; + this.indexForNextSeed = statInt[3]; + this.heightOfNextSeed = statInt[4]; + if (statInt[5] == 1) + { + this.isFinished = true; + } + else + { + this.isFinished = false; + } + if (statInt[6] == 1) + { + this.isInitialized = true; + } + else + { + this.isInitialized = false; + } + + int tailLength = statInt[7]; + + this.index = new int[heightOfTree]; + for (int i = 0; i < heightOfTree; i++) + { + this.index[i] = statInt[8 + i]; + } + + this.heightOfNodes = new Vector(); + for (int i = 0; i < tailLength; i++) + { + this.heightOfNodes.addElement(Integers.valueOf(statInt[8 + heightOfTree + + i])); + } + + // decode statByte + this.root = statByte[0]; + + this.AuthPath = new byte[heightOfTree][mdLength]; + for (int i = 0; i < heightOfTree; i++) + { + this.AuthPath[i] = statByte[1 + i]; + } + + this.tailStack = new Vector(); + for (int i = 0; i < tailLength; i++) + { + this.tailStack.addElement(statByte[1 + heightOfTree + i]); + } + + // decode treeH + this.treehash = GMSSUtils.clone(treeH); + + // decode ret + this.retain = GMSSUtils.clone(ret); + } + + /** + * Constructor + * + * @param heightOfTree maximal height of the tree + * @param digestProvider an array of strings, containing the name of the used hash + * function and PRNG and the name of the corresponding + * provider + */ + public GMSSRootCalc(int heightOfTree, int K, GMSSDigestProvider digestProvider) + { + this.heightOfTree = heightOfTree; + this.digestProvider = digestProvider; + this.messDigestTree = digestProvider.get(); + this.mdLength = messDigestTree.getDigestSize(); + this.K = K; + this.index = new int[heightOfTree]; + this.AuthPath = new byte[heightOfTree][mdLength]; + this.root = new byte[mdLength]; + // this.treehash = new Treehash[this.heightOfTree - this.K]; + this.retain = new Vector[this.K - 1]; + for (int i = 0; i < K - 1; i++) + { + this.retain[i] = new Vector(); + } + + } + + /** + * Initializes the calculation of a new root + * + * @param sharedStack the stack shared by all treehash instances of this tree + */ + public void initialize(Vector sharedStack) + { + this.treehash = new Treehash[this.heightOfTree - this.K]; + for (int i = 0; i < this.heightOfTree - this.K; i++) + { + this.treehash[i] = new Treehash(sharedStack, i, this.digestProvider.get()); + } + + this.index = new int[heightOfTree]; + this.AuthPath = new byte[heightOfTree][mdLength]; + this.root = new byte[mdLength]; + + this.tailStack = new Vector(); + this.heightOfNodes = new Vector(); + this.isInitialized = true; + this.isFinished = false; + + for (int i = 0; i < heightOfTree; i++) + { + this.index[i] = -1; + } + + this.retain = new Vector[this.K - 1]; + for (int i = 0; i < K - 1; i++) + { + this.retain[i] = new Vector(); + } + + this.indexForNextSeed = 3; + this.heightOfNextSeed = 0; + } + + /** + * updates the root with one leaf and stores needed values in retain, + * treehash or authpath. Additionally counts the seeds used. This method is + * used when performing the updates for TREE++. + * + * @param seed the initial seed for treehash: seedNext + * @param leaf the height of the treehash + */ + public void update(byte[] seed, byte[] leaf) + { + if (this.heightOfNextSeed < (this.heightOfTree - this.K) + && this.indexForNextSeed - 2 == index[0]) + { + this.initializeTreehashSeed(seed, this.heightOfNextSeed); + this.heightOfNextSeed++; + this.indexForNextSeed *= 2; + } + // now call the simple update + this.update(leaf); + } + + /** + * Updates the root with one leaf and stores the needed values in retain, + * treehash or authpath + */ + public void update(byte[] leaf) + { + + if (isFinished) + { + System.out.print("Too much updates for Tree!!"); + return; + } + if (!isInitialized) + { + System.err.println("GMSSRootCalc not initialized!"); + return; + } + + // a new leaf was omitted, so raise index on lowest layer + index[0]++; + + // store the nodes on the lowest layer in treehash or authpath + if (index[0] == 1) + { + System.arraycopy(leaf, 0, AuthPath[0], 0, mdLength); + } + else if (index[0] == 3) + { + // store in treehash only if K < H + if (heightOfTree > K) + { + treehash[0].setFirstNode(leaf); + } + } + + if ((index[0] - 3) % 2 == 0 && index[0] >= 3) + { + // store in retain if K = H + if (heightOfTree == K) + // TODO: check it + { + retain[0].insertElementAt(leaf, 0); + } + } + + // if first update to this tree is made + if (index[0] == 0) + { + tailStack.addElement(leaf); + heightOfNodes.addElement(Integers.valueOf(0)); + } + else + { + + byte[] help = new byte[mdLength]; + byte[] toBeHashed = new byte[mdLength << 1]; + + // store the new leaf in help + System.arraycopy(leaf, 0, help, 0, mdLength); + int helpHeight = 0; + // while top to nodes have same height + while (tailStack.size() > 0 + && helpHeight == ((Integer)heightOfNodes.lastElement()) + .intValue()) + { + + // help <-- hash(stack top element || help) + System.arraycopy(tailStack.lastElement(), 0, toBeHashed, 0, + mdLength); + tailStack.removeElementAt(tailStack.size() - 1); + heightOfNodes.removeElementAt(heightOfNodes.size() - 1); + System.arraycopy(help, 0, toBeHashed, mdLength, mdLength); + + messDigestTree.update(toBeHashed, 0, toBeHashed.length); + help = new byte[messDigestTree.getDigestSize()]; + messDigestTree.doFinal(help, 0); + + // the new help node is one step higher + helpHeight++; + if (helpHeight < heightOfTree) + { + index[helpHeight]++; + + // add index 1 element to initial authpath + if (index[helpHeight] == 1) + { + System.arraycopy(help, 0, AuthPath[helpHeight], 0, + mdLength); + } + + if (helpHeight >= heightOfTree - K) + { + if (helpHeight == 0) + { + System.out.println("M���P"); + } + // add help element to retain stack if it is a right + // node + // and not stored in treehash + if ((index[helpHeight] - 3) % 2 == 0 + && index[helpHeight] >= 3) + // TODO: check it + { + retain[helpHeight - (heightOfTree - K)] + .insertElementAt(help, 0); + } + } + else + { + // if element is third in his line add it to treehash + if (index[helpHeight] == 3) + { + treehash[helpHeight].setFirstNode(help); + } + } + } + } + // push help element to the stack + tailStack.addElement(help); + heightOfNodes.addElement(Integers.valueOf(helpHeight)); + + // is the root calculation finished? + if (helpHeight == heightOfTree) + { + isFinished = true; + isInitialized = false; + root = (byte[])tailStack.lastElement(); + } + } + + } + + /** + * initializes the seeds for the treehashs of the tree precomputed by this + * class + * + * @param seed the initial seed for treehash: seedNext + * @param index the height of the treehash + */ + public void initializeTreehashSeed(byte[] seed, int index) + { + treehash[index].initializeSeed(seed); + } + + /** + * Method to check whether the instance has been initialized or not + * + * @return true if treehash was already initialized + */ + public boolean wasInitialized() + { + return isInitialized; + } + + /** + * Method to check whether the instance has been finished or not + * + * @return true if tree has reached its maximum height + */ + public boolean wasFinished() + { + return isFinished; + } + + /** + * returns the authentication path of the first leaf of the tree + * + * @return the authentication path of the first leaf of the tree + */ + public byte[][] getAuthPath() + { + return GMSSUtils.clone(AuthPath); + } + + /** + * returns the initial treehash instances, storing value y_3(i) + * + * @return the initial treehash instances, storing value y_3(i) + */ + public Treehash[] getTreehash() + { + return GMSSUtils.clone(treehash); + } + + /** + * returns the retain stacks storing all right nodes near to the root + * + * @return the retain stacks storing all right nodes near to the root + */ + public Vector[] getRetain() + { + return GMSSUtils.clone(retain); + } + + /** + * returns the finished root value + * + * @return the finished root value + */ + public byte[] getRoot() + { + return Arrays.clone(root); + } + + /** + * returns the shared stack + * + * @return the shared stack + */ + public Vector getStack() + { + Vector copy = new Vector(); + for (Enumeration en = tailStack.elements(); en.hasMoreElements();) + { + copy.addElement(en.nextElement()); + } + return copy; + } + + /** + * Returns the status byte array used by the GMSSPrivateKeyASN.1 class + * + * @return The status bytes + */ + public byte[][] getStatByte() + { + + int tailLength; + if (tailStack == null) + { + tailLength = 0; + } + else + { + tailLength = tailStack.size(); + } + byte[][] statByte = new byte[1 + heightOfTree + tailLength][64]; //FIXME: messDigestTree.getByteLength() + statByte[0] = root; + + for (int i = 0; i < heightOfTree; i++) + { + statByte[1 + i] = AuthPath[i]; + } + for (int i = 0; i < tailLength; i++) + { + statByte[1 + heightOfTree + i] = (byte[])tailStack.elementAt(i); + } + + return statByte; + } + + /** + * Returns the status int array used by the GMSSPrivateKeyASN.1 class + * + * @return The status ints + */ + public int[] getStatInt() + { + + int tailLength; + if (tailStack == null) + { + tailLength = 0; + } + else + { + tailLength = tailStack.size(); + } + int[] statInt = new int[8 + heightOfTree + tailLength]; + statInt[0] = heightOfTree; + statInt[1] = mdLength; + statInt[2] = K; + statInt[3] = indexForNextSeed; + statInt[4] = heightOfNextSeed; + if (isFinished) + { + statInt[5] = 1; + } + else + { + statInt[5] = 0; + } + if (isInitialized) + { + statInt[6] = 1; + } + else + { + statInt[6] = 0; + } + statInt[7] = tailLength; + + for (int i = 0; i < heightOfTree; i++) + { + statInt[8 + i] = index[i]; + } + for (int i = 0; i < tailLength; i++) + { + statInt[8 + heightOfTree + i] = ((Integer)heightOfNodes + .elementAt(i)).intValue(); + } + + return statInt; + } + + /** + * @return a human readable version of the structure + */ + public String toString() + { + String out = ""; + int tailLength; + if (tailStack == null) + { + tailLength = 0; + } + else + { + tailLength = tailStack.size(); + } + + for (int i = 0; i < 8 + heightOfTree + tailLength; i++) + { + out = out + getStatInt()[i] + " "; + } + for (int i = 0; i < 1 + heightOfTree + tailLength; i++) + { + out = out + new String(Hex.encode(getStatByte()[i])) + " "; + } + out = out + " " + digestProvider.get().getDigestSize(); + return out; + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSRootSig.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSRootSig.java new file mode 100644 index 00000000..f08529cf --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSRootSig.java @@ -0,0 +1,666 @@ +package org.spongycastle.pqc.crypto.gmss; + +import org.spongycastle.crypto.Digest; +import org.spongycastle.pqc.crypto.gmss.util.GMSSRandom; +import org.spongycastle.util.encoders.Hex; + + +/** + * This class implements the distributed signature generation of the Winternitz + * one-time signature scheme (OTSS), described in C.Dods, N.P. Smart, and M. + * Stam, "Hash Based Digital Signature Schemes", LNCS 3796, pages 96–115, + * 2005. The class is used by the GMSS classes. + */ +public class GMSSRootSig +{ + + /** + * The hash function used by the OTS + */ + private Digest messDigestOTS; + + /** + * The length of the message digest and private key + */ + private int mdsize, keysize; + + /** + * The private key + */ + private byte[] privateKeyOTS; + + /** + * The message bytes + */ + private byte[] hash; + + /** + * The signature bytes + */ + private byte[] sign; + + /** + * The Winternitz parameter + */ + private int w; + + /** + * The source of randomness for OTS private key generation + */ + private GMSSRandom gmssRandom; + + /** + * Sizes of the message + */ + private int messagesize; + + /** + * Some precalculated values + */ + private int k; + + /** + * Some variables for storing the actual status of distributed signing + */ + private int r, test, counter, ii; + + /** + * variables for storing big numbers for the actual status of distributed + * signing + */ + private long test8, big8; + + /** + * The necessary steps of each updateSign() call + */ + private int steps; + + /** + * The checksum part + */ + private int checksum; + + /** + * The height of the tree + */ + private int height; + + /** + * The current intern OTSseed + */ + private byte[] seed; + + /** + * This constructor regenerates a prior GMSSRootSig object used by the + * GMSSPrivateKeyASN.1 class + * + * @param digest an array of strings, containing the digest of the used hash + * function, the digest of the PRGN and the names of the + * corresponding providers + * @param statByte status byte array + * @param statInt status int array + */ + public GMSSRootSig(Digest digest, byte[][] statByte, int[] statInt) + { + messDigestOTS = digest; + gmssRandom = new GMSSRandom(messDigestOTS); + + this.counter = statInt[0]; + this.test = statInt[1]; + this.ii = statInt[2]; + this.r = statInt[3]; + this.steps = statInt[4]; + this.keysize = statInt[5]; + this.height = statInt[6]; + this.w = statInt[7]; + this.checksum = statInt[8]; + + this.mdsize = messDigestOTS.getDigestSize(); + + this.k = (1 << w) - 1; + + int mdsizeBit = mdsize << 3; + this.messagesize = (int)Math.ceil((double)(mdsizeBit) / (double)w); + + this.privateKeyOTS = statByte[0]; + this.seed = statByte[1]; + this.hash = statByte[2]; + + this.sign = statByte[3]; + + this.test8 = ((statByte[4][0] & 0xff)) + | ((long)(statByte[4][1] & 0xff) << 8) + | ((long)(statByte[4][2] & 0xff) << 16) + | ((long)(statByte[4][3] & 0xff)) << 24 + | ((long)(statByte[4][4] & 0xff)) << 32 + | ((long)(statByte[4][5] & 0xff)) << 40 + | ((long)(statByte[4][6] & 0xff)) << 48 + | ((long)(statByte[4][7] & 0xff)) << 56; + + this.big8 = ((statByte[4][8] & 0xff)) + | ((long)(statByte[4][9] & 0xff) << 8) + | ((long)(statByte[4][10] & 0xff) << 16) + | ((long)(statByte[4][11] & 0xff)) << 24 + | ((long)(statByte[4][12] & 0xff)) << 32 + | ((long)(statByte[4][13] & 0xff)) << 40 + | ((long)(statByte[4][14] & 0xff)) << 48 + | ((long)(statByte[4][15] & 0xff)) << 56; + } + + /** + * The constructor generates the PRNG and initializes some variables + * + * @param digest an array of strings, containing the digest of the used hash + * function, the digest of the PRGN and the names of the + * corresponding providers + * @param w the winternitz parameter + * @param height the heigth of the tree + */ + public GMSSRootSig(Digest digest, int w, int height) + { + messDigestOTS = digest; + gmssRandom = new GMSSRandom(messDigestOTS); + + this.mdsize = messDigestOTS.getDigestSize(); + this.w = w; + this.height = height; + + this.k = (1 << w) - 1; + + int mdsizeBit = mdsize << 3; + this.messagesize = (int)Math.ceil((double)(mdsizeBit) / (double)w); + } + + /** + * This method initializes the distributed sigature calculation. Variables + * are reseted and necessary steps are calculated + * + * @param seed0 the initial OTSseed + * @param message the massage which will be signed + */ + public void initSign(byte[] seed0, byte[] message) + { + + // create hash of message m + this.hash = new byte[mdsize]; + messDigestOTS.update(message, 0, message.length); + this.hash = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(this.hash, 0); + + // variables for calculation of steps + byte[] messPart = new byte[mdsize]; + System.arraycopy(hash, 0, messPart, 0, mdsize); + int checkPart = 0; + int sumH = 0; + int checksumsize = getLog((messagesize << w) + 1); + + // ------- calculation of necessary steps ------ + if (8 % w == 0) + { + int dt = 8 / w; + // message part + for (int a = 0; a < mdsize; a++) + { + // count necessary hashs in 'sumH' + for (int b = 0; b < dt; b++) + { + sumH += messPart[a] & k; + messPart[a] = (byte)(messPart[a] >>> w); + } + } + // checksum part + this.checksum = (messagesize << w) - sumH; + checkPart = checksum; + // count necessary hashs in 'sumH' + for (int b = 0; b < checksumsize; b += w) + { + sumH += checkPart & k; + checkPart >>>= w; + } + } // end if ( 8 % w == 0 ) + else if (w < 8) + { + long big8; + int ii = 0; + int dt = mdsize / w; + + // first d*w bytes of hash (main message part) + for (int i = 0; i < dt; i++) + { + big8 = 0; + for (int j = 0; j < w; j++) + { + big8 ^= (messPart[ii] & 0xff) << (j << 3); + ii++; + } + // count necessary hashs in 'sumH' + for (int j = 0; j < 8; j++) + { + sumH += (int)(big8 & k); + big8 >>>= w; + } + } + // rest of message part + dt = mdsize % w; + big8 = 0; + for (int j = 0; j < dt; j++) + { + big8 ^= (messPart[ii] & 0xff) << (j << 3); + ii++; + } + dt <<= 3; + // count necessary hashs in 'sumH' + for (int j = 0; j < dt; j += w) + { + sumH += (int)(big8 & k); + big8 >>>= w; + } + // checksum part + this.checksum = (messagesize << w) - sumH; + checkPart = checksum; + // count necessary hashs in 'sumH' + for (int i = 0; i < checksumsize; i += w) + { + sumH += checkPart & k; + checkPart >>>= w; + } + }// end if(w<8) + else if (w < 57) + { + long big8; + int r = 0; + int s, f, rest, ii; + + // first a*w bits of hash where a*w <= 8*mdsize < (a+1)*w (main + // message part) + while (r <= ((mdsize << 3) - w)) + { + s = r >>> 3; + rest = r % 8; + r += w; + f = (r + 7) >>> 3; + big8 = 0; + ii = 0; + for (int j = s; j < f; j++) + { + big8 ^= (messPart[j] & 0xff) << (ii << 3); + ii++; + } + big8 >>>= rest; + // count necessary hashs in 'sumH' + sumH += (big8 & k); + + } + // rest of message part + s = r >>> 3; + if (s < mdsize) + { + rest = r % 8; + big8 = 0; + ii = 0; + for (int j = s; j < mdsize; j++) + { + big8 ^= (messPart[j] & 0xff) << (ii << 3); + ii++; + } + + big8 >>>= rest; + // count necessary hashs in 'sumH' + sumH += (big8 & k); + } + // checksum part + this.checksum = (messagesize << w) - sumH; + checkPart = checksum; + // count necessary hashs in 'sumH' + for (int i = 0; i < checksumsize; i += w) + { + sumH += (checkPart & k); + checkPart >>>= w; + } + }// end if(w<57) + + // calculate keysize + this.keysize = messagesize + + (int)Math.ceil((double)checksumsize / (double)w); + + // calculate steps: 'keysize' times PRNG, 'sumH' times hashing, + // (1<<height)-1 updateSign() calls + this.steps = (int)Math.ceil((double)(keysize + sumH) + / (double)((1 << height))); + // ---------------------------- + + // reset variables + this.sign = new byte[keysize * mdsize]; + this.counter = 0; + this.test = 0; + this.ii = 0; + this.test8 = 0; + this.r = 0; + // define the private key messagesize + this.privateKeyOTS = new byte[mdsize]; + // copy the seed + this.seed = new byte[mdsize]; + System.arraycopy(seed0, 0, this.seed, 0, mdsize); + + } + + /** + * This Method performs <code>steps</code> steps of distributed signature + * calculaion + * + * @return true if signature is generated completly, else false + */ + public boolean updateSign() + { + // steps times do + + for (int s = 0; s < steps; s++) + { // do 'step' times + + if (counter < keysize) + { // generate the private key or perform + // the next hash + oneStep(); + } + if (counter == keysize) + {// finish + return true; + } + } + + return false; // leaf not finished yet + } + + /** + * @return The private OTS key + */ + public byte[] getSig() + { + + return sign; + } + + /** + * @return The one-time signature of the message, generated step by step + */ + private void oneStep() + { + // -------- if (8 % w == 0) ---------- + if (8 % w == 0) + { + if (test == 0) + { + // get current OTSprivateKey + this.privateKeyOTS = gmssRandom.nextSeed(seed); + // System.arraycopy(privateKeyOTS, 0, hlp, 0, mdsize); + + if (ii < mdsize) + { // for main message part + test = hash[ii] & k; + hash[ii] = (byte)(hash[ii] >>> w); + } + else + { // for checksum part + test = checksum & k; + checksum >>>= w; + } + } + else if (test > 0) + { // hash the private Key 'test' times (on + // time each step) + messDigestOTS.update(privateKeyOTS, 0, privateKeyOTS.length); + privateKeyOTS = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(privateKeyOTS, 0); + test--; + } + if (test == 0) + { // if all hashes done copy result to siganture + // array + System.arraycopy(privateKeyOTS, 0, sign, counter * mdsize, + mdsize); + counter++; + + if (counter % (8 / w) == 0) + { // raise array index for main + // massage part + ii++; + } + } + + }// ----- end if (8 % w == 0) ----- + // ---------- if ( w < 8 ) ---------------- + else if (w < 8) + { + + if (test == 0) + { + if (counter % 8 == 0 && ii < mdsize) + { // after every 8th "add + // to signature"-step + big8 = 0; + if (counter < ((mdsize / w) << 3)) + {// main massage + // (generate w*8 Bits + // every time) part + for (int j = 0; j < w; j++) + { + big8 ^= (hash[ii] & 0xff) << (j << 3); + ii++; + } + } + else + { // rest of massage part (once) + for (int j = 0; j < mdsize % w; j++) + { + big8 ^= (hash[ii] & 0xff) << (j << 3); + ii++; + } + } + } + if (counter == messagesize) + { // checksum part (once) + big8 = checksum; + } + + test = (int)(big8 & k); + // generate current OTSprivateKey + this.privateKeyOTS = gmssRandom.nextSeed(seed); + // System.arraycopy(privateKeyOTS, 0, hlp, 0, mdsize); + + } + else if (test > 0) + { // hash the private Key 'test' times (on + // time each step) + messDigestOTS.update(privateKeyOTS, 0, privateKeyOTS.length); + privateKeyOTS = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(privateKeyOTS, 0); + test--; + } + if (test == 0) + { // if all hashes done copy result to siganture + // array + System.arraycopy(privateKeyOTS, 0, sign, counter * mdsize, + mdsize); + big8 >>>= w; + counter++; + } + + }// ------- end if(w<8)-------------------------------- + // --------- if w < 57 ----------------------------- + else if (w < 57) + { + + if (test8 == 0) + { + int s, f, rest; + big8 = 0; + ii = 0; + rest = r % 8; + s = r >>> 3; + // --- message part--- + if (s < mdsize) + { + if (r <= ((mdsize << 3) - w)) + { // first message part + r += w; + f = (r + 7) >>> 3; + } + else + { // rest of message part (once) + f = mdsize; + r += w; + } + // generate long 'big8' with minimum w next bits of the + // message array + for (int i = s; i < f; i++) + { + big8 ^= (hash[i] & 0xff) << (ii << 3); + ii++; + } + // delete bits on the right side, which were used already by + // the last loop + big8 >>>= rest; + test8 = (big8 & k); + } + // --- checksum part + else + { + test8 = (checksum & k); + checksum >>>= w; + } + // generate current OTSprivateKey + this.privateKeyOTS = gmssRandom.nextSeed(seed); + // System.arraycopy(privateKeyOTS, 0, hlp, 0, mdsize); + + } + else if (test8 > 0) + { // hash the private Key 'test' times (on + // time each step) + messDigestOTS.update(privateKeyOTS, 0, privateKeyOTS.length); + privateKeyOTS = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(privateKeyOTS, 0); + test8--; + } + if (test8 == 0) + { // if all hashes done copy result to siganture + // array + System.arraycopy(privateKeyOTS, 0, sign, counter * mdsize, + mdsize); + counter++; + } + + } + } + + /** + * This method returns the least integer that is greater or equal to the + * logarithm to the base 2 of an integer <code>intValue</code>. + * + * @param intValue an integer + * @return The least integer greater or equal to the logarithm to the base 2 + * of <code>intValue</code> + */ + public int getLog(int intValue) + { + int log = 1; + int i = 2; + while (i < intValue) + { + i <<= 1; + log++; + } + return log; + } + + /** + * This method returns the status byte array + * + * @return statBytes + */ + public byte[][] getStatByte() + { + + byte[][] statByte = new byte[5][mdsize]; + statByte[0] = privateKeyOTS; + statByte[1] = seed; + statByte[2] = hash; + statByte[3] = sign; + statByte[4] = this.getStatLong(); + + return statByte; + } + + /** + * This method returns the status int array + * + * @return statInt + */ + public int[] getStatInt() + { + int[] statInt = new int[9]; + statInt[0] = counter; + statInt[1] = test; + statInt[2] = ii; + statInt[3] = r; + statInt[4] = steps; + statInt[5] = keysize; + statInt[6] = height; + statInt[7] = w; + statInt[8] = checksum; + return statInt; + } + + /** + * Converts the long parameters into byte arrays to store it in + * statByte-Array + */ + public byte[] getStatLong() + { + byte[] bytes = new byte[16]; + + bytes[0] = (byte)((test8) & 0xff); + bytes[1] = (byte)((test8 >> 8) & 0xff); + bytes[2] = (byte)((test8 >> 16) & 0xff); + bytes[3] = (byte)((test8 >> 24) & 0xff); + bytes[4] = (byte)((test8) >> 32 & 0xff); + bytes[5] = (byte)((test8 >> 40) & 0xff); + bytes[6] = (byte)((test8 >> 48) & 0xff); + bytes[7] = (byte)((test8 >> 56) & 0xff); + + bytes[8] = (byte)((big8) & 0xff); + bytes[9] = (byte)((big8 >> 8) & 0xff); + bytes[10] = (byte)((big8 >> 16) & 0xff); + bytes[11] = (byte)((big8 >> 24) & 0xff); + bytes[12] = (byte)((big8) >> 32 & 0xff); + bytes[13] = (byte)((big8 >> 40) & 0xff); + bytes[14] = (byte)((big8 >> 48) & 0xff); + bytes[15] = (byte)((big8 >> 56) & 0xff); + + return bytes; + } + + /** + * returns a string representation of the instance + * + * @return a string representation of the instance + */ + public String toString() + { + String out = "" + this.big8 + " "; + int[] statInt = new int[9]; + statInt = this.getStatInt(); + byte[][] statByte = new byte[5][mdsize]; + statByte = this.getStatByte(); + for (int i = 0; i < 9; i++) + { + out = out + statInt[i] + " "; + } + for (int i = 0; i < 5; i++) + { + out = out + new String(Hex.encode(statByte[i])) + " "; + } + + return out; + } + +} diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSSigner.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSSigner.java new file mode 100644 index 00000000..2a78d385 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSSigner.java @@ -0,0 +1,403 @@ +package org.spongycastle.pqc.crypto.gmss; + +import java.security.SecureRandom; + +import org.spongycastle.crypto.CipherParameters; +import org.spongycastle.crypto.Digest; +import org.spongycastle.crypto.params.ParametersWithRandom; +import org.spongycastle.pqc.crypto.MessageSigner; +import org.spongycastle.pqc.crypto.gmss.util.GMSSRandom; +import org.spongycastle.pqc.crypto.gmss.util.GMSSUtil; +import org.spongycastle.pqc.crypto.gmss.util.WinternitzOTSVerify; +import org.spongycastle.pqc.crypto.gmss.util.WinternitzOTSignature; +import org.spongycastle.util.Arrays; + +/** + * This class implements the GMSS signature scheme. + */ +public class GMSSSigner + implements MessageSigner +{ + + /** + * Instance of GMSSParameterSpec + */ + //private GMSSParameterSpec gmssParameterSpec; + + /** + * Instance of GMSSUtilities + */ + private GMSSUtil gmssUtil = new GMSSUtil(); + + + /** + * The raw GMSS public key + */ + private byte[] pubKeyBytes; + + /** + * Hash function for the construction of the authentication trees + */ + private Digest messDigestTrees; + + /** + * The length of the hash function output + */ + private int mdLength; + + /** + * The number of tree layers + */ + private int numLayer; + + /** + * The hash function used by the OTS + */ + private Digest messDigestOTS; + + /** + * An instance of the Winternitz one-time signature + */ + private WinternitzOTSignature ots; + + /** + * Array of strings containing the name of the hash function used by the OTS + * and the corresponding provider name + */ + private GMSSDigestProvider digestProvider; + + /** + * The current main tree and subtree indices + */ + private int[] index; + + /** + * Array of the authentication paths for the current trees of all layers + */ + private byte[][][] currentAuthPaths; + + /** + * The one-time signature of the roots of the current subtrees + */ + private byte[][] subtreeRootSig; + + + /** + * The GMSSParameterset + */ + private GMSSParameters gmssPS; + + /** + * The PRNG + */ + private GMSSRandom gmssRandom; + + GMSSKeyParameters key; + + // XXX needed? Source of randomness + private SecureRandom random; + + + /** + * The standard constructor tries to generate the MerkleTree Algorithm + * identifier with the corresponding OID. + * + * @param digest the digest to use + */ + // TODO + public GMSSSigner(GMSSDigestProvider digest) + { + digestProvider = digest; + messDigestTrees = digest.get(); + messDigestOTS = messDigestTrees; + mdLength = messDigestTrees.getDigestSize(); + gmssRandom = new GMSSRandom(messDigestTrees); + } + + public void init(boolean forSigning, + CipherParameters param) + { + + if (forSigning) + { + if (param instanceof ParametersWithRandom) + { + ParametersWithRandom rParam = (ParametersWithRandom)param; + + // XXX random needed? + this.random = rParam.getRandom(); + this.key = (GMSSPrivateKeyParameters)rParam.getParameters(); + initSign(); + + } + else + { + + this.random = new SecureRandom(); + this.key = (GMSSPrivateKeyParameters)param; + initSign(); + } + } + else + { + this.key = (GMSSPublicKeyParameters)param; + initVerify(); + + } + + } + + + /** + * Initializes the signature algorithm for signing a message. + */ + private void initSign() + { + messDigestTrees.reset(); + // set private key and take from it ots key, auth, tree and key + // counter, rootSign + GMSSPrivateKeyParameters gmssPrivateKey = (GMSSPrivateKeyParameters)key; + + if (gmssPrivateKey.isUsed()) + { + throw new IllegalStateException("Private key already used"); + } + + // check if last signature has been generated + if (gmssPrivateKey.getIndex(0) >= gmssPrivateKey.getNumLeafs(0)) + { + throw new IllegalStateException("No more signatures can be generated"); + } + + // get Parameterset + this.gmssPS = gmssPrivateKey.getParameters(); + // get numLayer + this.numLayer = gmssPS.getNumOfLayers(); + + // get OTS Instance of lowest layer + byte[] seed = gmssPrivateKey.getCurrentSeeds()[numLayer - 1]; + byte[] OTSSeed = new byte[mdLength]; + byte[] dummy = new byte[mdLength]; + System.arraycopy(seed, 0, dummy, 0, mdLength); + OTSSeed = gmssRandom.nextSeed(dummy); // secureRandom.nextBytes(currentSeeds[currentSeeds.length-1]);secureRandom.nextBytes(OTSseed); + this.ots = new WinternitzOTSignature(OTSSeed, digestProvider.get(), gmssPS.getWinternitzParameter()[numLayer - 1]); + + byte[][][] helpCurrentAuthPaths = gmssPrivateKey.getCurrentAuthPaths(); + currentAuthPaths = new byte[numLayer][][]; + + // copy the main tree authentication path + for (int j = 0; j < numLayer; j++) + { + currentAuthPaths[j] = new byte[helpCurrentAuthPaths[j].length][mdLength]; + for (int i = 0; i < helpCurrentAuthPaths[j].length; i++) + { + System.arraycopy(helpCurrentAuthPaths[j][i], 0, currentAuthPaths[j][i], 0, mdLength); + } + } + + // copy index + index = new int[numLayer]; + System.arraycopy(gmssPrivateKey.getIndex(), 0, index, 0, numLayer); + + // copy subtreeRootSig + byte[] helpSubtreeRootSig; + subtreeRootSig = new byte[numLayer - 1][]; + for (int i = 0; i < numLayer - 1; i++) + { + helpSubtreeRootSig = gmssPrivateKey.getSubtreeRootSig(i); + subtreeRootSig[i] = new byte[helpSubtreeRootSig.length]; + System.arraycopy(helpSubtreeRootSig, 0, subtreeRootSig[i], 0, helpSubtreeRootSig.length); + } + + gmssPrivateKey.markUsed(); + } + + /** + * Signs a message. + * + * @return the signature. + */ + public byte[] generateSignature(byte[] message) + { + + byte[] otsSig = new byte[mdLength]; + byte[] authPathBytes; + byte[] indexBytes; + + otsSig = ots.getSignature(message); + + // get concatenated lowest layer tree authentication path + authPathBytes = gmssUtil.concatenateArray(currentAuthPaths[numLayer - 1]); + + // put lowest layer index into a byte array + indexBytes = gmssUtil.intToBytesLittleEndian(index[numLayer - 1]); + + // create first part of GMSS signature + byte[] gmssSigFirstPart = new byte[indexBytes.length + otsSig.length + authPathBytes.length]; + System.arraycopy(indexBytes, 0, gmssSigFirstPart, 0, indexBytes.length); + System.arraycopy(otsSig, 0, gmssSigFirstPart, indexBytes.length, otsSig.length); + System.arraycopy(authPathBytes, 0, gmssSigFirstPart, (indexBytes.length + otsSig.length), authPathBytes.length); + // --- end first part + + // --- next parts of the signature + // create initial array with length 0 for iteration + byte[] gmssSigNextPart = new byte[0]; + + for (int i = numLayer - 1 - 1; i >= 0; i--) + { + + // get concatenated next tree authentication path + authPathBytes = gmssUtil.concatenateArray(currentAuthPaths[i]); + + // put next tree index into a byte array + indexBytes = gmssUtil.intToBytesLittleEndian(index[i]); + + // create next part of GMSS signature + + // create help array and copy actual gmssSig into it + byte[] helpGmssSig = new byte[gmssSigNextPart.length]; + System.arraycopy(gmssSigNextPart, 0, helpGmssSig, 0, gmssSigNextPart.length); + // adjust length of gmssSigNextPart for adding next part + gmssSigNextPart = new byte[helpGmssSig.length + indexBytes.length + subtreeRootSig[i].length + authPathBytes.length]; + + // copy old data (help array) and new data in gmssSigNextPart + System.arraycopy(helpGmssSig, 0, gmssSigNextPart, 0, helpGmssSig.length); + System.arraycopy(indexBytes, 0, gmssSigNextPart, helpGmssSig.length, indexBytes.length); + System.arraycopy(subtreeRootSig[i], 0, gmssSigNextPart, (helpGmssSig.length + indexBytes.length), subtreeRootSig[i].length); + System.arraycopy(authPathBytes, 0, gmssSigNextPart, (helpGmssSig.length + indexBytes.length + subtreeRootSig[i].length), authPathBytes.length); + + } + // --- end next parts + + // concatenate the two parts of the GMSS signature + byte[] gmssSig = new byte[gmssSigFirstPart.length + gmssSigNextPart.length]; + System.arraycopy(gmssSigFirstPart, 0, gmssSig, 0, gmssSigFirstPart.length); + System.arraycopy(gmssSigNextPart, 0, gmssSig, gmssSigFirstPart.length, gmssSigNextPart.length); + + // return the GMSS signature + return gmssSig; + } + + /** + * Initializes the signature algorithm for verifying a signature. + */ + private void initVerify() + { + messDigestTrees.reset(); + + GMSSPublicKeyParameters gmssPublicKey = (GMSSPublicKeyParameters)key; + pubKeyBytes = gmssPublicKey.getPublicKey(); + gmssPS = gmssPublicKey.getParameters(); + // get numLayer + this.numLayer = gmssPS.getNumOfLayers(); + + + } + + /** + * This function verifies the signature of the message that has been + * updated, with the aid of the public key. + * + * @param message the message + * @param signature the signature associated with the message + * @return true if the signature has been verified, false otherwise. + */ + public boolean verifySignature(byte[] message, byte[] signature) + { + + boolean success = false; + // int halfSigLength = signature.length >>> 1; + messDigestOTS.reset(); + WinternitzOTSVerify otsVerify; + int otsSigLength; + + byte[] help = message; + + byte[] otsSig; + byte[] otsPublicKey; + byte[][] authPath; + byte[] dest; + int nextEntry = 0; + int index; + // Verify signature + + // --- begin with message = 'message that was signed' + // and then in each step message = subtree root + for (int j = numLayer - 1; j >= 0; j--) + { + otsVerify = new WinternitzOTSVerify(digestProvider.get(), gmssPS.getWinternitzParameter()[j]); + otsSigLength = otsVerify.getSignatureLength(); + + message = help; + // get the subtree index + index = gmssUtil.bytesToIntLittleEndian(signature, nextEntry); + + // 4 is the number of bytes in integer + nextEntry += 4; + + // get one-time signature + otsSig = new byte[otsSigLength]; + System.arraycopy(signature, nextEntry, otsSig, 0, otsSigLength); + nextEntry += otsSigLength; + + // compute public OTS key from the one-time signature + otsPublicKey = otsVerify.Verify(message, otsSig); + + // test if OTSsignature is correct + if (otsPublicKey == null) + { + System.err.println("OTS Public Key is null in GMSSSignature.verify"); + return false; + } + + // get authentication path from the signature + authPath = new byte[gmssPS.getHeightOfTrees()[j]][mdLength]; + for (int i = 0; i < authPath.length; i++) + { + System.arraycopy(signature, nextEntry, authPath[i], 0, mdLength); + nextEntry = nextEntry + mdLength; + } + + // compute the root of the subtree from the authentication path + help = new byte[mdLength]; + + help = otsPublicKey; + + int count = 1 << authPath.length; + count = count + index; + + for (int i = 0; i < authPath.length; i++) + { + dest = new byte[mdLength << 1]; + + if ((count % 2) == 0) + { + System.arraycopy(help, 0, dest, 0, mdLength); + System.arraycopy(authPath[i], 0, dest, mdLength, mdLength); + count = count / 2; + } + else + { + System.arraycopy(authPath[i], 0, dest, 0, mdLength); + System.arraycopy(help, 0, dest, mdLength, help.length); + count = (count - 1) / 2; + } + messDigestTrees.update(dest, 0, dest.length); + help = new byte[messDigestTrees.getDigestSize()]; + messDigestTrees.doFinal(help, 0); + } + } + + // now help contains the root of the maintree + + // test if help is equal to the GMSS public key + if (Arrays.areEqual(pubKeyBytes, help)) + { + success = true; + } + + return success; + } + + +}
\ No newline at end of file diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSUtils.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSUtils.java new file mode 100644 index 00000000..1f79bdde --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/GMSSUtils.java @@ -0,0 +1,145 @@ +package org.spongycastle.pqc.crypto.gmss; + +import java.util.Enumeration; +import java.util.Vector; + +import org.spongycastle.util.Arrays; + +class GMSSUtils +{ + static GMSSLeaf[] clone(GMSSLeaf[] data) + { + if (data == null) + { + return null; + } + GMSSLeaf[] copy = new GMSSLeaf[data.length]; + + System.arraycopy(data, 0, copy, 0, data.length); + + return copy; + } + + static GMSSRootCalc[] clone(GMSSRootCalc[] data) + { + if (data == null) + { + return null; + } + GMSSRootCalc[] copy = new GMSSRootCalc[data.length]; + + System.arraycopy(data, 0, copy, 0, data.length); + + return copy; + } + + static GMSSRootSig[] clone(GMSSRootSig[] data) + { + if (data == null) + { + return null; + } + GMSSRootSig[] copy = new GMSSRootSig[data.length]; + + System.arraycopy(data, 0, copy, 0, data.length); + + return copy; + } + + static byte[][] clone(byte[][] data) + { + if (data == null) + { + return null; + } + byte[][] copy = new byte[data.length][]; + + for (int i = 0; i != data.length; i++) + { + copy[i] = Arrays.clone(data[i]); + } + + return copy; + } + + static byte[][][] clone(byte[][][] data) + { + if (data == null) + { + return null; + } + byte[][][] copy = new byte[data.length][][]; + + for (int i = 0; i != data.length; i++) + { + copy[i] = clone(data[i]); + } + + return copy; + } + + static Treehash[] clone(Treehash[] data) + { + if (data == null) + { + return null; + } + Treehash[] copy = new Treehash[data.length]; + + System.arraycopy(data, 0, copy, 0, data.length); + + return copy; + } + + static Treehash[][] clone(Treehash[][] data) + { + if (data == null) + { + return null; + } + Treehash[][] copy = new Treehash[data.length][]; + + for (int i = 0; i != data.length; i++) + { + copy[i] = clone(data[i]); + } + + return copy; + } + + static Vector[] clone(Vector[] data) + { + if (data == null) + { + return null; + } + Vector[] copy = new Vector[data.length]; + + for (int i = 0; i != data.length; i++) + { + copy[i] = new Vector(); + for (Enumeration en = data[i].elements(); en.hasMoreElements();) + { + copy[i].addElement(en.nextElement()); + } + } + + return copy; + } + + static Vector[][] clone(Vector[][] data) + { + if (data == null) + { + return null; + } + Vector[][] copy = new Vector[data.length][]; + + for (int i = 0; i != data.length; i++) + { + copy[i] = clone(data[i]); + } + + return copy; + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/Treehash.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/Treehash.java new file mode 100644 index 00000000..82784e34 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/Treehash.java @@ -0,0 +1,525 @@ +package org.spongycastle.pqc.crypto.gmss; + +import java.util.Vector; + +import org.spongycastle.crypto.Digest; +import org.spongycastle.pqc.crypto.gmss.util.GMSSRandom; +import org.spongycastle.util.Integers; +import org.spongycastle.util.encoders.Hex; + + +/** + * This class implements a treehash instance for the Merkle tree traversal + * algorithm. The first node of the stack is stored in this instance itself, + * additional tail nodes are stored on a tailstack. + */ +public class Treehash +{ + + /** + * max height of current treehash instance. + */ + private int maxHeight; + + /** + * Vector element that stores the nodes on the stack + */ + private Vector tailStack; + + /** + * Vector element that stores the height of the nodes on the stack + */ + private Vector heightOfNodes; + + /** + * the first node is stored in the treehash instance itself, not on stack + */ + private byte[] firstNode; + + /** + * seedActive needed for the actual node + */ + private byte[] seedActive; + + /** + * the seed needed for the next re-initialization of the treehash instance + */ + private byte[] seedNext; + + /** + * number of nodes stored on the stack and belonging to this treehash + * instance + */ + private int tailLength; + + /** + * the height in the tree of the first node stored in treehash + */ + private int firstNodeHeight; + + /** + * true if treehash instance was already initialized, false otherwise + */ + private boolean isInitialized; + + /** + * true if the first node's height equals the maxHeight of the treehash + */ + private boolean isFinished; + + /** + * true if the nextSeed has been initialized with index 3*2^h needed for the + * seed scheduling + */ + private boolean seedInitialized; + + /** + * denotes the Message Digest used by the tree to create nodes + */ + private Digest messDigestTree; + + /** + * This constructor regenerates a prior treehash object + * + * @param name an array of strings, containing the name of the used hash + * function and PRNG and the name of the corresponding provider + * @param statByte status bytes + * @param statInt status ints + */ + public Treehash(Digest name, byte[][] statByte, int[] statInt) + { + this.messDigestTree = name; + + // decode statInt + this.maxHeight = statInt[0]; + this.tailLength = statInt[1]; + this.firstNodeHeight = statInt[2]; + + if (statInt[3] == 1) + { + this.isFinished = true; + } + else + { + this.isFinished = false; + } + if (statInt[4] == 1) + { + this.isInitialized = true; + } + else + { + this.isInitialized = false; + } + if (statInt[5] == 1) + { + this.seedInitialized = true; + } + else + { + this.seedInitialized = false; + } + + this.heightOfNodes = new Vector(); + for (int i = 0; i < tailLength; i++) + { + this.heightOfNodes.addElement(Integers.valueOf(statInt[6 + i])); + } + + // decode statByte + this.firstNode = statByte[0]; + this.seedActive = statByte[1]; + this.seedNext = statByte[2]; + + this.tailStack = new Vector(); + for (int i = 0; i < tailLength; i++) + { + this.tailStack.addElement(statByte[3 + i]); + } + } + + /** + * Constructor + * + * @param tailStack a vector element where the stack nodes are stored + * @param maxHeight maximal height of the treehash instance + * @param digest an array of strings, containing the name of the used hash + * function and PRNG and the name of the corresponding provider + */ + public Treehash(Vector tailStack, int maxHeight, Digest digest) + { + this.tailStack = tailStack; + this.maxHeight = maxHeight; + this.firstNode = null; + this.isInitialized = false; + this.isFinished = false; + this.seedInitialized = false; + this.messDigestTree = digest; + + this.seedNext = new byte[messDigestTree.getDigestSize()]; + this.seedActive = new byte[messDigestTree.getDigestSize()]; + } + + /** + * Method to initialize the seeds needed for the precomputation of right + * nodes. Should be initialized with index 3*2^i for treehash_i + * + * @param seedIn + */ + public void initializeSeed(byte[] seedIn) + { + System.arraycopy(seedIn, 0, this.seedNext, 0, this.messDigestTree + .getDigestSize()); + this.seedInitialized = true; + } + + /** + * initializes the treehash instance. The seeds must already have been + * initialized to work correctly. + */ + public void initialize() + { + if (!this.seedInitialized) + { + System.err.println("Seed " + this.maxHeight + " not initialized"); + return; + } + + this.heightOfNodes = new Vector(); + this.tailLength = 0; + this.firstNode = null; + this.firstNodeHeight = -1; + this.isInitialized = true; + System.arraycopy(this.seedNext, 0, this.seedActive, 0, messDigestTree + .getDigestSize()); + } + + /** + * Calculates one update of the treehash instance, i.e. creates a new leaf + * and hashes if possible + * + * @param gmssRandom an instance of the PRNG + * @param leaf The byte value of the leaf needed for the update + */ + public void update(GMSSRandom gmssRandom, byte[] leaf) + { + + if (this.isFinished) + { + System.err + .println("No more update possible for treehash instance!"); + return; + } + if (!this.isInitialized) + { + System.err + .println("Treehash instance not initialized before update"); + return; + } + + byte[] help = new byte[this.messDigestTree.getDigestSize()]; + int helpHeight = -1; + + gmssRandom.nextSeed(this.seedActive); + + // if treehash gets first update + if (this.firstNode == null) + { + this.firstNode = leaf; + this.firstNodeHeight = 0; + } + else + { + // store the new node in help array, do not push it on the stack + help = leaf; + helpHeight = 0; + + // hash the nodes on the stack if possible + while (this.tailLength > 0 + && helpHeight == ((Integer)heightOfNodes.lastElement()) + .intValue()) + { + // put top element of the stack and help node in array + // 'tobehashed' + // and hash them together, put result again in help array + byte[] toBeHashed = new byte[this.messDigestTree + .getDigestSize() << 1]; + + // pop element from stack + System.arraycopy(this.tailStack.lastElement(), 0, toBeHashed, + 0, this.messDigestTree.getDigestSize()); + this.tailStack.removeElementAt(this.tailStack.size() - 1); + this.heightOfNodes + .removeElementAt(this.heightOfNodes.size() - 1); + + System.arraycopy(help, 0, toBeHashed, this.messDigestTree + .getDigestSize(), this.messDigestTree + .getDigestSize()); + messDigestTree.update(toBeHashed, 0, toBeHashed.length); + help = new byte[messDigestTree.getDigestSize()]; + messDigestTree.doFinal(help, 0); + + // increase help height, stack was reduced by one element + helpHeight++; + this.tailLength--; + } + + // push the new node on the stack + this.tailStack.addElement(help); + this.heightOfNodes.addElement(Integers.valueOf(helpHeight)); + this.tailLength++; + + // finally check whether the top node on stack and the first node + // in treehash have same height. If so hash them together + // and store them in treehash + if (((Integer)heightOfNodes.lastElement()).intValue() == this.firstNodeHeight) + { + byte[] toBeHashed = new byte[this.messDigestTree + .getDigestSize() << 1]; + System.arraycopy(this.firstNode, 0, toBeHashed, 0, + this.messDigestTree.getDigestSize()); + + // pop element from tailStack and copy it into help2 array + System.arraycopy(this.tailStack.lastElement(), 0, toBeHashed, + this.messDigestTree.getDigestSize(), + this.messDigestTree.getDigestSize()); + this.tailStack.removeElementAt(this.tailStack.size() - 1); + this.heightOfNodes + .removeElementAt(this.heightOfNodes.size() - 1); + + // store new element in firstNode, stack is then empty + messDigestTree.update(toBeHashed, 0, toBeHashed.length); + this.firstNode = new byte[messDigestTree.getDigestSize()]; + messDigestTree.doFinal(this.firstNode, 0); + this.firstNodeHeight++; + + // empty the stack + this.tailLength = 0; + } + } + + // check if treehash instance is completed + if (this.firstNodeHeight == this.maxHeight) + { + this.isFinished = true; + } + } + + /** + * Destroys a treehash instance after the top node was taken for + * authentication path. + */ + public void destroy() + { + this.isInitialized = false; + this.isFinished = false; + this.firstNode = null; + this.tailLength = 0; + this.firstNodeHeight = -1; + } + + /** + * Returns the height of the lowest node stored either in treehash or on the + * stack. It must not be set to infinity (as mentioned in the paper) because + * this cases are considered in the computeAuthPaths method of + * JDKGMSSPrivateKey + * + * @return Height of the lowest node + */ + public int getLowestNodeHeight() + { + if (this.firstNode == null) + { + return this.maxHeight; + } + else if (this.tailLength == 0) + { + return this.firstNodeHeight; + } + else + { + return Math.min(this.firstNodeHeight, ((Integer)heightOfNodes + .lastElement()).intValue()); + } + } + + /** + * Returns the top node height + * + * @return Height of the first node, the top node + */ + public int getFirstNodeHeight() + { + if (firstNode == null) + { + return maxHeight; + } + return firstNodeHeight; + } + + /** + * Method to check whether the instance has been initialized or not + * + * @return true if treehash was already initialized + */ + public boolean wasInitialized() + { + return this.isInitialized; + } + + /** + * Method to check whether the instance has been finished or not + * + * @return true if treehash has reached its maximum height + */ + public boolean wasFinished() + { + return this.isFinished; + } + + /** + * returns the first node stored in treehash instance itself + * + * @return the first node stored in treehash instance itself + */ + public byte[] getFirstNode() + { + return this.firstNode; + } + + /** + * returns the active seed + * + * @return the active seed + */ + public byte[] getSeedActive() + { + return this.seedActive; + } + + /** + * This method sets the first node stored in the treehash instance itself + * + * @param hash + */ + public void setFirstNode(byte[] hash) + { + if (!this.isInitialized) + { + this.initialize(); + } + this.firstNode = hash; + this.firstNodeHeight = this.maxHeight; + this.isFinished = true; + } + + /** + * updates the nextSeed of this treehash instance one step needed for the + * schedulng of the seeds + * + * @param gmssRandom the prng used for the seeds + */ + public void updateNextSeed(GMSSRandom gmssRandom) + { + gmssRandom.nextSeed(seedNext); + } + + /** + * Returns the tailstack + * + * @return the tailstack + */ + public Vector getTailStack() + { + return this.tailStack; + } + + /** + * Returns the status byte array used by the GMSSPrivateKeyASN.1 class + * + * @return The status bytes + */ + public byte[][] getStatByte() + { + + byte[][] statByte = new byte[3 + tailLength][this.messDigestTree + .getDigestSize()]; + statByte[0] = firstNode; + statByte[1] = seedActive; + statByte[2] = seedNext; + for (int i = 0; i < tailLength; i++) + { + statByte[3 + i] = (byte[])tailStack.elementAt(i); + } + return statByte; + } + + /** + * Returns the status int array used by the GMSSPrivateKeyASN.1 class + * + * @return The status ints + */ + public int[] getStatInt() + { + + int[] statInt = new int[6 + tailLength]; + statInt[0] = maxHeight; + statInt[1] = tailLength; + statInt[2] = firstNodeHeight; + if (this.isFinished) + { + statInt[3] = 1; + } + else + { + statInt[3] = 0; + } + if (this.isInitialized) + { + statInt[4] = 1; + } + else + { + statInt[4] = 0; + } + if (this.seedInitialized) + { + statInt[5] = 1; + } + else + { + statInt[5] = 0; + } + for (int i = 0; i < tailLength; i++) + { + statInt[6 + i] = ((Integer)heightOfNodes.elementAt(i)).intValue(); + } + return statInt; + } + + /** + * returns a String representation of the treehash instance + */ + public String toString() + { + String out = "Treehash : "; + for (int i = 0; i < 6 + tailLength; i++) + { + out = out + this.getStatInt()[i] + " "; + } + for (int i = 0; i < 3 + tailLength; i++) + { + if (this.getStatByte()[i] != null) + { + out = out + new String(Hex.encode((this.getStatByte()[i]))) + " "; + } + else + { + out = out + "null "; + } + } + out = out + " " + this.messDigestTree.getDigestSize(); + return out; + } + +}
\ No newline at end of file diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/util/GMSSRandom.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/util/GMSSRandom.java new file mode 100644 index 00000000..367aae0e --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/util/GMSSRandom.java @@ -0,0 +1,78 @@ +package org.spongycastle.pqc.crypto.gmss.util; + +import org.spongycastle.crypto.Digest; + +/** + * This class provides a PRNG for GMSS + */ +public class GMSSRandom +{ + /** + * Hash function for the construction of the authentication trees + */ + private Digest messDigestTree; + + /** + * Constructor + * + * @param messDigestTree2 + */ + public GMSSRandom(Digest messDigestTree2) + { + + this.messDigestTree = messDigestTree2; + } + + /** + * computes the next seed value, returns a random byte array and sets + * outseed to the next value + * + * @param outseed byte array in which ((1 + SEEDin +RAND) mod 2^n) will be + * stored + * @return byte array of H(SEEDin) + */ + public byte[] nextSeed(byte[] outseed) + { + // RAND <-- H(SEEDin) + byte[] rand = new byte[outseed.length]; + messDigestTree.update(outseed, 0, outseed.length); + rand = new byte[messDigestTree.getDigestSize()]; + messDigestTree.doFinal(rand, 0); + + // SEEDout <-- (1 + SEEDin +RAND) mod 2^n + addByteArrays(outseed, rand); + addOne(outseed); + + // System.arraycopy(outseed, 0, outseed, 0, outseed.length); + + return rand; + } + + private void addByteArrays(byte[] a, byte[] b) + { + + byte overflow = 0; + int temp; + + for (int i = 0; i < a.length; i++) + { + temp = (0xFF & a[i]) + (0xFF & b[i]) + overflow; + a[i] = (byte)temp; + overflow = (byte)(temp >> 8); + } + } + + private void addOne(byte[] a) + { + + byte overflow = 1; + int temp; + + for (int i = 0; i < a.length; i++) + { + temp = (0xFF & a[i]) + overflow; + a[i] = (byte)temp; + overflow = (byte)(temp >> 8); + } + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/util/GMSSUtil.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/util/GMSSUtil.java new file mode 100644 index 00000000..57678d85 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/util/GMSSUtil.java @@ -0,0 +1,151 @@ +package org.spongycastle.pqc.crypto.gmss.util; + +/** + * This class provides several methods that are required by the GMSS classes. + */ +public class GMSSUtil +{ + /** + * Converts a 32 bit integer into a byte array beginning at + * <code>offset</code> (little-endian representation) + * + * @param value the integer to convert + */ + public byte[] intToBytesLittleEndian(int value) + { + byte[] bytes = new byte[4]; + + bytes[0] = (byte)((value) & 0xff); + bytes[1] = (byte)((value >> 8) & 0xff); + bytes[2] = (byte)((value >> 16) & 0xff); + bytes[3] = (byte)((value >> 24) & 0xff); + return bytes; + } + + /** + * Converts a byte array beginning at <code>offset</code> into a 32 bit + * integer (little-endian representation) + * + * @param bytes the byte array + * @return The resulting integer + */ + public int bytesToIntLittleEndian(byte[] bytes) + { + + return ((bytes[0] & 0xff)) | ((bytes[1] & 0xff) << 8) + | ((bytes[2] & 0xff) << 16) | ((bytes[3] & 0xff)) << 24; + } + + /** + * Converts a byte array beginning at <code>offset</code> into a 32 bit + * integer (little-endian representation) + * + * @param bytes the byte array + * @param offset the integer offset into the byte array + * @return The resulting integer + */ + public int bytesToIntLittleEndian(byte[] bytes, int offset) + { + return ((bytes[offset++] & 0xff)) | ((bytes[offset++] & 0xff) << 8) + | ((bytes[offset++] & 0xff) << 16) + | ((bytes[offset] & 0xff)) << 24; + } + + /** + * This method concatenates a 2-dimensional byte array into a 1-dimensional + * byte array + * + * @param arraycp a 2-dimensional byte array. + * @return 1-dimensional byte array with concatenated input array + */ + public byte[] concatenateArray(byte[][] arraycp) + { + byte[] dest = new byte[arraycp.length * arraycp[0].length]; + int indx = 0; + for (int i = 0; i < arraycp.length; i++) + { + System.arraycopy(arraycp[i], 0, dest, indx, arraycp[i].length); + indx = indx + arraycp[i].length; + } + return dest; + } + + /** + * This method prints the values of a 2-dimensional byte array + * + * @param text a String + * @param array a 2-dimensional byte array + */ + public void printArray(String text, byte[][] array) + { + System.out.println(text); + int counter = 0; + for (int i = 0; i < array.length; i++) + { + for (int j = 0; j < array[0].length; j++) + { + System.out.println(counter + "; " + array[i][j]); + counter++; + } + } + } + + /** + * This method prints the values of a 1-dimensional byte array + * + * @param text a String + * @param array a 1-dimensional byte array. + */ + public void printArray(String text, byte[] array) + { + System.out.println(text); + int counter = 0; + for (int i = 0; i < array.length; i++) + { + System.out.println(counter + "; " + array[i]); + counter++; + } + } + + /** + * This method tests if an integer is a power of 2. + * + * @param testValue an integer + * @return <code>TRUE</code> if <code>testValue</code> is a power of 2, + * <code>FALSE</code> otherwise + */ + public boolean testPowerOfTwo(int testValue) + { + int a = 1; + while (a < testValue) + { + a <<= 1; + } + if (testValue == a) + { + return true; + } + + return false; + } + + /** + * This method returns the least integer that is greater or equal to the + * logarithm to the base 2 of an integer <code>intValue</code>. + * + * @param intValue an integer + * @return The least integer greater or equal to the logarithm to the base 2 + * of <code>intValue</code> + */ + public int getLog(int intValue) + { + int log = 1; + int i = 2; + while (i < intValue) + { + i <<= 1; + log++; + } + return log; + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/util/WinternitzOTSVerify.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/util/WinternitzOTSVerify.java new file mode 100644 index 00000000..0a1e52eb --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/util/WinternitzOTSVerify.java @@ -0,0 +1,344 @@ +package org.spongycastle.pqc.crypto.gmss.util; + +import org.spongycastle.crypto.Digest; + +/** + * This class implements signature verification of the Winternitz one-time + * signature scheme (OTSS), described in C.Dods, N.P. Smart, and M. Stam, "Hash + * Based Digital Signature Schemes", LNCS 3796, pages 96–115, 2005. The + * class is used by the GMSS classes. + */ +public class WinternitzOTSVerify +{ + + private Digest messDigestOTS; + + /** + * The Winternitz parameter + */ + private int w; + + /** + * The constructor + * + * @param digest the name of the hash function used by the OTS and the provider + * name of the hash function + * @param w the Winternitz parameter + */ + public WinternitzOTSVerify(Digest digest, int w) + { + this.w = w; + + messDigestOTS = digest; + } + + /** + * @return The length of the one-time signature + */ + public int getSignatureLength() + { + int mdsize = messDigestOTS.getDigestSize(); + int size = ((mdsize << 3) + (w - 1)) / w; + int logs = getLog((size << w) + 1); + size += (logs + w - 1) / w; + + return mdsize * size; + } + + /** + * This method computes the public OTS key from the one-time signature of a + * message. This is *NOT* a complete OTS signature verification, but it + * suffices for usage with CMSS. + * + * @param message the message + * @param signature the one-time signature + * @return The public OTS key + */ + public byte[] Verify(byte[] message, byte[] signature) + { + + int mdsize = messDigestOTS.getDigestSize(); + byte[] hash = new byte[mdsize]; // hash of message m + + // create hash of message m + messDigestOTS.update(message, 0, message.length); + hash = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hash, 0); + + int size = ((mdsize << 3) + (w - 1)) / w; + int logs = getLog((size << w) + 1); + int keysize = size + (logs + w - 1) / w; + + int testKeySize = mdsize * keysize; + + if (testKeySize != signature.length) + { + return null; + } + + byte[] testKey = new byte[testKeySize]; + + int c = 0; + int counter = 0; + int test; + + if (8 % w == 0) + { + int d = 8 / w; + int k = (1 << w) - 1; + byte[] hlp = new byte[mdsize]; + + // verify signature + for (int i = 0; i < hash.length; i++) + { + for (int j = 0; j < d; j++) + { + test = hash[i] & k; + c += test; + + System.arraycopy(signature, counter * mdsize, hlp, 0, mdsize); + + while (test < k) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test++; + } + + System.arraycopy(hlp, 0, testKey, counter * mdsize, mdsize); + hash[i] = (byte)(hash[i] >>> w); + counter++; + } + } + + c = (size << w) - c; + for (int i = 0; i < logs; i += w) + { + test = c & k; + + System.arraycopy(signature, counter * mdsize, hlp, 0, mdsize); + + while (test < k) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test++; + } + System.arraycopy(hlp, 0, testKey, counter * mdsize, mdsize); + c >>>= w; + counter++; + } + } + else if (w < 8) + { + int d = mdsize / w; + int k = (1 << w) - 1; + byte[] hlp = new byte[mdsize]; + long big8; + int ii = 0; + // create signature + // first d*w bytes of hash + for (int i = 0; i < d; i++) + { + big8 = 0; + for (int j = 0; j < w; j++) + { + big8 ^= (hash[ii] & 0xff) << (j << 3); + ii++; + } + for (int j = 0; j < 8; j++) + { + test = (int)(big8 & k); + c += test; + + System.arraycopy(signature, counter * mdsize, hlp, 0, mdsize); + + while (test < k) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test++; + } + + System.arraycopy(hlp, 0, testKey, counter * mdsize, mdsize); + big8 >>>= w; + counter++; + } + } + // rest of hash + d = mdsize % w; + big8 = 0; + for (int j = 0; j < d; j++) + { + big8 ^= (hash[ii] & 0xff) << (j << 3); + ii++; + } + d <<= 3; + for (int j = 0; j < d; j += w) + { + test = (int)(big8 & k); + c += test; + + System.arraycopy(signature, counter * mdsize, hlp, 0, mdsize); + + while (test < k) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test++; + } + + System.arraycopy(hlp, 0, testKey, counter * mdsize, mdsize); + big8 >>>= w; + counter++; + } + + // check bytes + c = (size << w) - c; + for (int i = 0; i < logs; i += w) + { + test = c & k; + + System.arraycopy(signature, counter * mdsize, hlp, 0, mdsize); + + while (test < k) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test++; + } + + System.arraycopy(hlp, 0, testKey, counter * mdsize, mdsize); + c >>>= w; + counter++; + } + }// end if(w<8) + else if (w < 57) + { + int d = (mdsize << 3) - w; + int k = (1 << w) - 1; + byte[] hlp = new byte[mdsize]; + long big8, test8; + int r = 0; + int s, f, rest, ii; + // create signature + // first a*w bits of hash where a*w <= 8*mdsize < (a+1)*w + while (r <= d) + { + s = r >>> 3; + rest = r % 8; + r += w; + f = (r + 7) >>> 3; + big8 = 0; + ii = 0; + for (int j = s; j < f; j++) + { + big8 ^= (hash[j] & 0xff) << (ii << 3); + ii++; + } + + big8 >>>= rest; + test8 = (big8 & k); + c += test8; + + System.arraycopy(signature, counter * mdsize, hlp, 0, mdsize); + + while (test8 < k) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test8++; + } + + System.arraycopy(hlp, 0, testKey, counter * mdsize, mdsize); + counter++; + + } + // rest of hash + s = r >>> 3; + if (s < mdsize) + { + rest = r % 8; + big8 = 0; + ii = 0; + for (int j = s; j < mdsize; j++) + { + big8 ^= (hash[j] & 0xff) << (ii << 3); + ii++; + } + + big8 >>>= rest; + test8 = (big8 & k); + c += test8; + + System.arraycopy(signature, counter * mdsize, hlp, 0, mdsize); + + while (test8 < k) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test8++; + } + + System.arraycopy(hlp, 0, testKey, counter * mdsize, mdsize); + counter++; + } + // check bytes + c = (size << w) - c; + for (int i = 0; i < logs; i += w) + { + test8 = (c & k); + + System.arraycopy(signature, counter * mdsize, hlp, 0, mdsize); + + while (test8 < k) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test8++; + } + + System.arraycopy(hlp, 0, testKey, counter * mdsize, mdsize); + c >>>= w; + counter++; + } + }// end if(w<57) + + byte[] TKey = new byte[mdsize]; + messDigestOTS.update(testKey, 0, testKey.length); + TKey = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(TKey, 0); + + return TKey; + + } + + /** + * This method returns the least integer that is greater or equal to the + * logarithm to the base 2 of an integer <code>intValue</code>. + * + * @param intValue an integer + * @return The least integer greater or equal to the logarithm to the base + * 256 of <code>intValue</code> + */ + public int getLog(int intValue) + { + int log = 1; + int i = 2; + while (i < intValue) + { + i <<= 1; + log++; + } + return log; + } + +} diff --git a/core/src/main/java/org/spongycastle/pqc/crypto/gmss/util/WinternitzOTSignature.java b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/util/WinternitzOTSignature.java new file mode 100644 index 00000000..2ec2c1ad --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/crypto/gmss/util/WinternitzOTSignature.java @@ -0,0 +1,404 @@ +package org.spongycastle.pqc.crypto.gmss.util; + +import org.spongycastle.crypto.Digest; + +/** + * This class implements key pair generation and signature generation of the + * Winternitz one-time signature scheme (OTSS), described in C.Dods, N.P. Smart, + * and M. Stam, "Hash Based Digital Signature Schemes", LNCS 3796, pages + * 96–115, 2005. The class is used by the GMSS classes. + */ + +public class WinternitzOTSignature +{ + + /** + * The hash function used by the OTS + */ + private Digest messDigestOTS; + + /** + * The length of the message digest and private key + */ + private int mdsize, keysize; + + /** + * An array of strings, containing the name of the used hash function, the + * name of the PRGN and the names of the corresponding providers + */ + // private String[] name = new String[2]; + /** + * The private key + */ + private byte[][] privateKeyOTS; + + /** + * The Winternitz parameter + */ + private int w; + + /** + * The source of randomness for OTS private key generation + */ + private GMSSRandom gmssRandom; + + /** + * Sizes of the message and the checksum, both + */ + private int messagesize, checksumsize; + + /** + * The constructor generates an OTS key pair, using <code>seed0</code> and + * the PRNG + * + * @param seed0 the seed for the PRGN + * @param digest an array of strings, containing the name of the used hash + * function, the name of the PRGN and the names of the + * corresponding providers + * @param w the Winternitz parameter + */ + public WinternitzOTSignature(byte[] seed0, Digest digest, int w) + { + // this.name = name; + this.w = w; + + messDigestOTS = digest; + + gmssRandom = new GMSSRandom(messDigestOTS); + + // calulate keysize for private and public key and also the help + // array + + mdsize = messDigestOTS.getDigestSize(); + int mdsizeBit = mdsize << 3; + messagesize = (int)Math.ceil((double)(mdsizeBit) / (double)w); + + checksumsize = getLog((messagesize << w) + 1); + + keysize = messagesize + + (int)Math.ceil((double)checksumsize / (double)w); + + /* + * mdsize = messDigestOTS.getDigestLength(); messagesize = + * ((mdsize<<3)+(w-1))/w; + * + * checksumsize = getlog((messagesize<<w)+1); + * + * keysize = messagesize + (checksumsize+w-1)/w; + */ + // define the private key messagesize + privateKeyOTS = new byte[keysize][mdsize]; + + // gmssRandom.setSeed(seed0); + byte[] dummy = new byte[mdsize]; + System.arraycopy(seed0, 0, dummy, 0, dummy.length); + + // generate random bytes and + // assign them to the private key + for (int i = 0; i < keysize; i++) + { + privateKeyOTS[i] = gmssRandom.nextSeed(dummy); + } + } + + /** + * @return The private OTS key + */ + public byte[][] getPrivateKey() + { + return privateKeyOTS; + } + + /** + * @return The public OTS key + */ + public byte[] getPublicKey() + { + byte[] helppubKey = new byte[keysize * mdsize]; + + byte[] help = new byte[mdsize]; + int two_power_t = 1 << w; + + for (int i = 0; i < keysize; i++) + { + // hash w-1 time the private key and assign it to the public key + messDigestOTS.update(privateKeyOTS[i], 0, privateKeyOTS[i].length); + help = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(help, 0); + for (int j = 2; j < two_power_t; j++) + { + messDigestOTS.update(help, 0, help.length); + help = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(help, 0); + } + System.arraycopy(help, 0, helppubKey, mdsize * i, mdsize); + } + + messDigestOTS.update(helppubKey, 0, helppubKey.length); + byte[] tmp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(tmp, 0); + return tmp; + } + + /** + * @return The one-time signature of the message, generated with the private + * key + */ + public byte[] getSignature(byte[] message) + { + byte[] sign = new byte[keysize * mdsize]; + // byte [] message; // message m as input + byte[] hash = new byte[mdsize]; // hash of message m + int counter = 0; + int c = 0; + int test = 0; + // create hash of message m + messDigestOTS.update(message, 0, message.length); + hash = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hash, 0); + + if (8 % w == 0) + { + int d = 8 / w; + int k = (1 << w) - 1; + byte[] hlp = new byte[mdsize]; + + // create signature + for (int i = 0; i < hash.length; i++) + { + for (int j = 0; j < d; j++) + { + test = hash[i] & k; + c += test; + + System.arraycopy(privateKeyOTS[counter], 0, hlp, 0, mdsize); + + while (test > 0) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test--; + } + System.arraycopy(hlp, 0, sign, counter * mdsize, mdsize); + hash[i] = (byte)(hash[i] >>> w); + counter++; + } + } + + c = (messagesize << w) - c; + for (int i = 0; i < checksumsize; i += w) + { + test = c & k; + + System.arraycopy(privateKeyOTS[counter], 0, hlp, 0, mdsize); + + while (test > 0) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test--; + } + System.arraycopy(hlp, 0, sign, counter * mdsize, mdsize); + c >>>= w; + counter++; + } + } + else if (w < 8) + { + int d = mdsize / w; + int k = (1 << w) - 1; + byte[] hlp = new byte[mdsize]; + long big8; + int ii = 0; + // create signature + // first d*w bytes of hash + for (int i = 0; i < d; i++) + { + big8 = 0; + for (int j = 0; j < w; j++) + { + big8 ^= (hash[ii] & 0xff) << (j << 3); + ii++; + } + for (int j = 0; j < 8; j++) + { + test = (int)(big8 & k); + c += test; + + System.arraycopy(privateKeyOTS[counter], 0, hlp, 0, mdsize); + + while (test > 0) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test--; + } + System.arraycopy(hlp, 0, sign, counter * mdsize, mdsize); + big8 >>>= w; + counter++; + } + } + // rest of hash + d = mdsize % w; + big8 = 0; + for (int j = 0; j < d; j++) + { + big8 ^= (hash[ii] & 0xff) << (j << 3); + ii++; + } + d <<= 3; + for (int j = 0; j < d; j += w) + { + test = (int)(big8 & k); + c += test; + + System.arraycopy(privateKeyOTS[counter], 0, hlp, 0, mdsize); + + while (test > 0) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test--; + } + System.arraycopy(hlp, 0, sign, counter * mdsize, mdsize); + big8 >>>= w; + counter++; + } + + // check bytes + c = (messagesize << w) - c; + for (int i = 0; i < checksumsize; i += w) + { + test = c & k; + + System.arraycopy(privateKeyOTS[counter], 0, hlp, 0, mdsize); + + while (test > 0) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test--; + } + System.arraycopy(hlp, 0, sign, counter * mdsize, mdsize); + c >>>= w; + counter++; + } + }// end if(w<8) + else if (w < 57) + { + int d = (mdsize << 3) - w; + int k = (1 << w) - 1; + byte[] hlp = new byte[mdsize]; + long big8, test8; + int r = 0; + int s, f, rest, ii; + // create signature + // first a*w bits of hash where a*w <= 8*mdsize < (a+1)*w + while (r <= d) + { + s = r >>> 3; + rest = r % 8; + r += w; + f = (r + 7) >>> 3; + big8 = 0; + ii = 0; + for (int j = s; j < f; j++) + { + big8 ^= (hash[j] & 0xff) << (ii << 3); + ii++; + } + + big8 >>>= rest; + test8 = (big8 & k); + c += test8; + + System.arraycopy(privateKeyOTS[counter], 0, hlp, 0, mdsize); + while (test8 > 0) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test8--; + } + System.arraycopy(hlp, 0, sign, counter * mdsize, mdsize); + counter++; + + } + // rest of hash + s = r >>> 3; + if (s < mdsize) + { + rest = r % 8; + big8 = 0; + ii = 0; + for (int j = s; j < mdsize; j++) + { + big8 ^= (hash[j] & 0xff) << (ii << 3); + ii++; + } + + big8 >>>= rest; + test8 = (big8 & k); + c += test8; + + System.arraycopy(privateKeyOTS[counter], 0, hlp, 0, mdsize); + while (test8 > 0) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test8--; + } + System.arraycopy(hlp, 0, sign, counter * mdsize, mdsize); + counter++; + } + // check bytes + c = (messagesize << w) - c; + for (int i = 0; i < checksumsize; i += w) + { + test8 = (c & k); + + System.arraycopy(privateKeyOTS[counter], 0, hlp, 0, mdsize); + + while (test8 > 0) + { + messDigestOTS.update(hlp, 0, hlp.length); + hlp = new byte[messDigestOTS.getDigestSize()]; + messDigestOTS.doFinal(hlp, 0); + test8--; + } + System.arraycopy(hlp, 0, sign, counter * mdsize, mdsize); + c >>>= w; + counter++; + } + }// end if(w<57) + + return sign; + } + + /** + * This method returns the least integer that is greater or equal to the + * logarithm to the base 2 of an integer <code>intValue</code>. + * + * @param intValue an integer + * @return The least integer greater or equal to the logarithm to the base 2 + * of <code>intValue</code> + */ + public int getLog(int intValue) + { + int log = 1; + int i = 2; + while (i < intValue) + { + i <<= 1; + log++; + } + return log; + } + +} |