diff options
Diffstat (limited to 'core/src/main/java/org/bouncycastle/pqc/crypto/ntru')
16 files changed, 3950 insertions, 0 deletions
diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/IndexGenerator.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/IndexGenerator.java new file mode 100644 index 00000000..82974b30 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/IndexGenerator.java @@ -0,0 +1,239 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import org.bouncycastle.crypto.Digest; +import org.bouncycastle.util.Arrays; + +/** + * An implementation of the Index Generation Function in IEEE P1363.1. + */ +public class IndexGenerator +{ + private byte[] seed; + private int N; + private int c; + private int minCallsR; + private int totLen; + private int remLen; + private BitString buf; + private int counter; + private boolean initialized; + private Digest hashAlg; + private int hLen; + + /** + * Constructs a new index generator. + * + * @param seed a seed of arbitrary length to initialize the index generator with + * @param params NtruEncrypt parameters + */ + IndexGenerator(byte[] seed, NTRUEncryptionParameters params) + { + this.seed = seed; + N = params.N; + c = params.c; + minCallsR = params.minCallsR; + + totLen = 0; + remLen = 0; + counter = 0; + hashAlg = params.hashAlg; + + hLen = hashAlg.getDigestSize(); // hash length + initialized = false; + } + + /** + * Returns a number <code>i</code> such that <code>0 <= i < N</code>. + * + * @return + */ + int nextIndex() + { + if (!initialized) + { + buf = new BitString(); + byte[] hash = new byte[hashAlg.getDigestSize()]; + while (counter < minCallsR) + { + appendHash(buf, hash); + counter++; + } + totLen = minCallsR * 8 * hLen; + remLen = totLen; + initialized = true; + } + + while (true) + { + totLen += c; + BitString M = buf.getTrailing(remLen); + if (remLen < c) + { + int tmpLen = c - remLen; + int cThreshold = counter + (tmpLen + hLen - 1) / hLen; + byte[] hash = new byte[hashAlg.getDigestSize()]; + while (counter < cThreshold) + { + appendHash(M, hash); + counter++; + if (tmpLen > 8 * hLen) + { + tmpLen -= 8 * hLen; + } + } + remLen = 8 * hLen - tmpLen; + buf = new BitString(); + buf.appendBits(hash); + } + else + { + remLen -= c; + } + + int i = M.getLeadingAsInt(c); // assume c<32 + if (i < (1 << c) - ((1 << c) % N)) + { + return i % N; + } + } + } + + private void appendHash(BitString m, byte[] hash) + { + hashAlg.update(seed, 0, seed.length); + + putInt(hashAlg, counter); + + hashAlg.doFinal(hash, 0); + + m.appendBits(hash); + } + + private void putInt(Digest hashAlg, int counter) + { + hashAlg.update((byte)(counter >> 24)); + hashAlg.update((byte)(counter >> 16)); + hashAlg.update((byte)(counter >> 8)); + hashAlg.update((byte)counter); + } + + /** + * Represents a string of bits and supports appending, reading the head, and reading the tail. + */ + public static class BitString + { + byte[] bytes = new byte[4]; + int numBytes; // includes the last byte even if only some of its bits are used + int lastByteBits; // lastByteBits <= 8 + + /** + * Appends all bits in a byte array to the end of the bit string. + * + * @param bytes a byte array + */ + void appendBits(byte[] bytes) + { + for (int i = 0; i != bytes.length; i++) + { + appendBits(bytes[i]); + } + } + + /** + * Appends all bits in a byte to the end of the bit string. + * + * @param b a byte + */ + public void appendBits(byte b) + { + if (numBytes == bytes.length) + { + bytes = copyOf(bytes, 2 * bytes.length); + } + + if (numBytes == 0) + { + numBytes = 1; + bytes[0] = b; + lastByteBits = 8; + } + else if (lastByteBits == 8) + { + bytes[numBytes++] = b; + } + else + { + int s = 8 - lastByteBits; + bytes[numBytes - 1] |= (b & 0xFF) << lastByteBits; + bytes[numBytes++] = (byte)((b & 0xFF) >> s); + } + } + + /** + * Returns the last <code>numBits</code> bits from the end of the bit string. + * + * @param numBits number of bits + * @return a new <code>BitString</code> of length <code>numBits</code> + */ + public BitString getTrailing(int numBits) + { + BitString newStr = new BitString(); + newStr.numBytes = (numBits + 7) / 8; + newStr.bytes = new byte[newStr.numBytes]; + for (int i = 0; i < newStr.numBytes; i++) + { + newStr.bytes[i] = bytes[i]; + } + + newStr.lastByteBits = numBits % 8; + if (newStr.lastByteBits == 0) + { + newStr.lastByteBits = 8; + } + else + { + int s = 32 - newStr.lastByteBits; + newStr.bytes[newStr.numBytes - 1] = (byte)(newStr.bytes[newStr.numBytes - 1] << s >>> s); + } + + return newStr; + } + + /** + * Returns up to 32 bits from the beginning of the bit string. + * + * @param numBits number of bits + * @return an <code>int</code> whose lower <code>numBits</code> bits are the beginning of the bit string + */ + public int getLeadingAsInt(int numBits) + { + int startBit = (numBytes - 1) * 8 + lastByteBits - numBits; + int startByte = startBit / 8; + + int startBitInStartByte = startBit % 8; + int sum = (bytes[startByte] & 0xFF) >>> startBitInStartByte; + int shift = 8 - startBitInStartByte; + for (int i = startByte + 1; i < numBytes; i++) + { + sum |= (bytes[i] & 0xFF) << shift; + shift += 8; + } + + return sum; + } + + public byte[] getBytes() + { + return Arrays.clone(bytes); + } + } + + private static byte[] copyOf(byte[] src, int len) + { + byte[] tmp = new byte[len]; + + System.arraycopy(src, 0, tmp, 0, len < src.length ? len : src.length); + + return tmp; + } +}
\ No newline at end of file diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionKeyGenerationParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionKeyGenerationParameters.java new file mode 100644 index 00000000..d5caa352 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionKeyGenerationParameters.java @@ -0,0 +1,463 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; +import java.security.SecureRandom; +import java.util.Arrays; + +import org.bouncycastle.crypto.Digest; +import org.bouncycastle.crypto.KeyGenerationParameters; +import org.bouncycastle.crypto.digests.SHA256Digest; +import org.bouncycastle.crypto.digests.SHA512Digest; + +/** + * A set of parameters for NtruEncrypt. Several predefined parameter sets are available and new ones can be created as well. + */ +public class NTRUEncryptionKeyGenerationParameters + extends KeyGenerationParameters + implements Cloneable +{ + /** + * A conservative (in terms of security) parameter set that gives 256 bits of security and is optimized for key size. + */ + public static final NTRUEncryptionKeyGenerationParameters EES1087EP2 = new NTRUEncryptionKeyGenerationParameters(1087, 2048, 120, 120, 256, 13, 25, 14, true, new byte[]{0, 6, 3}, true, false, new SHA512Digest()); + + /** + * A conservative (in terms of security) parameter set that gives 256 bits of security and is a tradeoff between key size and encryption/decryption speed. + */ + public static final NTRUEncryptionKeyGenerationParameters EES1171EP1 = new NTRUEncryptionKeyGenerationParameters(1171, 2048, 106, 106, 256, 13, 20, 15, true, new byte[]{0, 6, 4}, true, false, new SHA512Digest()); + + /** + * A conservative (in terms of security) parameter set that gives 256 bits of security and is optimized for encryption/decryption speed. + */ + public static final NTRUEncryptionKeyGenerationParameters EES1499EP1 = new NTRUEncryptionKeyGenerationParameters(1499, 2048, 79, 79, 256, 13, 17, 19, true, new byte[]{0, 6, 5}, true, false, new SHA512Digest()); + + /** + * A parameter set that gives 128 bits of security and uses simple ternary polynomials. + */ + public static final NTRUEncryptionKeyGenerationParameters APR2011_439 = new NTRUEncryptionKeyGenerationParameters(439, 2048, 146, 130, 128, 9, 32, 9, true, new byte[]{0, 7, 101}, true, false, new SHA256Digest()); + + /** + * Like <code>APR2011_439</code>, this parameter set gives 128 bits of security but uses product-form polynomials and <code>f=1+pF</code>. + */ + public static final NTRUEncryptionKeyGenerationParameters APR2011_439_FAST = new NTRUEncryptionKeyGenerationParameters(439, 2048, 9, 8, 5, 130, 128, 9, 32, 9, true, new byte[]{0, 7, 101}, true, true, new SHA256Digest()); + + /** + * A parameter set that gives 256 bits of security and uses simple ternary polynomials. + */ + public static final NTRUEncryptionKeyGenerationParameters APR2011_743 = new NTRUEncryptionKeyGenerationParameters(743, 2048, 248, 220, 256, 10, 27, 14, true, new byte[]{0, 7, 105}, false, false, new SHA512Digest()); + + /** + * Like <code>APR2011_743</code>, this parameter set gives 256 bits of security but uses product-form polynomials and <code>f=1+pF</code>. + */ + public static final NTRUEncryptionKeyGenerationParameters APR2011_743_FAST = new NTRUEncryptionKeyGenerationParameters(743, 2048, 11, 11, 15, 220, 256, 10, 27, 14, true, new byte[]{0, 7, 105}, false, true, new SHA512Digest()); + + public int N, q, df, df1, df2, df3; + public int dr; + public int dr1; + public int dr2; + public int dr3; + public int dg; + int llen; + public int maxMsgLenBytes; + public int db; + public int bufferLenBits; + int bufferLenTrits; + public int dm0; + public int pkLen; + public int c; + public int minCallsR; + public int minCallsMask; + public boolean hashSeed; + public byte[] oid; + public boolean sparse; + public boolean fastFp; + public int polyType; + public Digest hashAlg; + + /** + * Constructs a parameter set that uses ternary private keys (i.e. </code>polyType=SIMPLE</code>). + * + * @param N number of polynomial coefficients + * @param q modulus + * @param df number of ones in the private polynomial <code>f</code> + * @param dm0 minimum acceptable number of -1's, 0's, and 1's in the polynomial <code>m'</code> in the last encryption step + * @param db number of random bits to prepend to the message + * @param c a parameter for the Index Generation Function ({@link org.bouncycastle.pqc.crypto.ntru.IndexGenerator}) + * @param minCallsR minimum number of hash calls for the IGF to make + * @param minCallsMask minimum number of calls to generate the masking polynomial + * @param hashSeed whether to hash the seed in the MGF first (true) or use the seed directly (false) + * @param oid three bytes that uniquely identify the parameter set + * @param sparse whether to treat ternary polynomials as sparsely populated ({@link org.bouncycastle.pqc.math.ntru.polynomial.SparseTernaryPolynomial} vs {@link org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial}) + * @param fastFp whether <code>f=1+p*F</code> for a ternary <code>F</code> (true) or <code>f</code> is ternary (false) + * @param hashAlg a valid identifier for a <code>java.security.MessageDigest</code> instance such as <code>SHA-256</code>. The <code>MessageDigest</code> must support the <code>getDigestLength()</code> method. + */ + public NTRUEncryptionKeyGenerationParameters(int N, int q, int df, int dm0, int db, int c, int minCallsR, int minCallsMask, boolean hashSeed, byte[] oid, boolean sparse, boolean fastFp, Digest hashAlg) + { + super(new SecureRandom(), db); + this.N = N; + this.q = q; + this.df = df; + this.db = db; + this.dm0 = dm0; + this.c = c; + this.minCallsR = minCallsR; + this.minCallsMask = minCallsMask; + this.hashSeed = hashSeed; + this.oid = oid; + this.sparse = sparse; + this.fastFp = fastFp; + this.polyType = NTRUParameters.TERNARY_POLYNOMIAL_TYPE_SIMPLE; + this.hashAlg = hashAlg; + init(); + } + + /** + * Constructs a parameter set that uses product-form private keys (i.e. </code>polyType=PRODUCT</code>). + * + * @param N number of polynomial coefficients + * @param q modulus + * @param df1 number of ones in the private polynomial <code>f1</code> + * @param df2 number of ones in the private polynomial <code>f2</code> + * @param df3 number of ones in the private polynomial <code>f3</code> + * @param dm0 minimum acceptable number of -1's, 0's, and 1's in the polynomial <code>m'</code> in the last encryption step + * @param db number of random bits to prepend to the message + * @param c a parameter for the Index Generation Function ({@link org.bouncycastle.pqc.crypto.ntru.IndexGenerator}) + * @param minCallsR minimum number of hash calls for the IGF to make + * @param minCallsMask minimum number of calls to generate the masking polynomial + * @param hashSeed whether to hash the seed in the MGF first (true) or use the seed directly (false) + * @param oid three bytes that uniquely identify the parameter set + * @param sparse whether to treat ternary polynomials as sparsely populated ({@link org.bouncycastle.pqc.math.ntru.polynomial.SparseTernaryPolynomial} vs {@link org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial}) + * @param fastFp whether <code>f=1+p*F</code> for a ternary <code>F</code> (true) or <code>f</code> is ternary (false) + * @param hashAlg a valid identifier for a <code>java.security.MessageDigest</code> instance such as <code>SHA-256</code> + */ + public NTRUEncryptionKeyGenerationParameters(int N, int q, int df1, int df2, int df3, int dm0, int db, int c, int minCallsR, int minCallsMask, boolean hashSeed, byte[] oid, boolean sparse, boolean fastFp, Digest hashAlg) + { + super(new SecureRandom(), db); + + this.N = N; + this.q = q; + this.df1 = df1; + this.df2 = df2; + this.df3 = df3; + this.db = db; + this.dm0 = dm0; + this.c = c; + this.minCallsR = minCallsR; + this.minCallsMask = minCallsMask; + this.hashSeed = hashSeed; + this.oid = oid; + this.sparse = sparse; + this.fastFp = fastFp; + this.polyType = NTRUParameters.TERNARY_POLYNOMIAL_TYPE_PRODUCT; + this.hashAlg = hashAlg; + init(); + } + + private void init() + { + dr = df; + dr1 = df1; + dr2 = df2; + dr3 = df3; + dg = N / 3; + llen = 1; // ceil(log2(maxMsgLenBytes)) + maxMsgLenBytes = N * 3 / 2 / 8 - llen - db / 8 - 1; + bufferLenBits = (N * 3 / 2 + 7) / 8 * 8 + 1; + bufferLenTrits = N - 1; + pkLen = db; + } + + /** + * Reads a parameter set from an input stream. + * + * @param is an input stream + * @throws java.io.IOException + */ + public NTRUEncryptionKeyGenerationParameters(InputStream is) + throws IOException + { + super(new SecureRandom(), -1); + DataInputStream dis = new DataInputStream(is); + N = dis.readInt(); + q = dis.readInt(); + df = dis.readInt(); + df1 = dis.readInt(); + df2 = dis.readInt(); + df3 = dis.readInt(); + db = dis.readInt(); + dm0 = dis.readInt(); + c = dis.readInt(); + minCallsR = dis.readInt(); + minCallsMask = dis.readInt(); + hashSeed = dis.readBoolean(); + oid = new byte[3]; + dis.read(oid); + sparse = dis.readBoolean(); + fastFp = dis.readBoolean(); + polyType = dis.read(); + + String alg = dis.readUTF(); + + if ("SHA-512".equals(alg)) + { + hashAlg = new SHA512Digest(); + } + else if ("SHA-256".equals(alg)) + { + hashAlg = new SHA256Digest(); + } + + init(); + } + + public NTRUEncryptionParameters getEncryptionParameters() + { + if (polyType == NTRUParameters.TERNARY_POLYNOMIAL_TYPE_SIMPLE) + { + return new NTRUEncryptionParameters(N, q, df, dm0, db, c, minCallsR, minCallsMask, hashSeed, oid, sparse, fastFp, hashAlg); + } + else + { + return new NTRUEncryptionParameters(N, q, df1, df2, df3, dm0, db, c, minCallsR, minCallsMask, hashSeed, oid, sparse, fastFp, hashAlg); + } + } + + public NTRUEncryptionKeyGenerationParameters clone() + { + if (polyType == NTRUParameters.TERNARY_POLYNOMIAL_TYPE_SIMPLE) + { + return new NTRUEncryptionKeyGenerationParameters(N, q, df, dm0, db, c, minCallsR, minCallsMask, hashSeed, oid, sparse, fastFp, hashAlg); + } + else + { + return new NTRUEncryptionKeyGenerationParameters(N, q, df1, df2, df3, dm0, db, c, minCallsR, minCallsMask, hashSeed, oid, sparse, fastFp, hashAlg); + } + } + + /** + * Returns the maximum length a plaintext message can be with this parameter set. + * + * @return the maximum length in bytes + */ + public int getMaxMessageLength() + { + return maxMsgLenBytes; + } + + /** + * Writes the parameter set to an output stream + * + * @param os an output stream + * @throws java.io.IOException + */ + public void writeTo(OutputStream os) + throws IOException + { + DataOutputStream dos = new DataOutputStream(os); + dos.writeInt(N); + dos.writeInt(q); + dos.writeInt(df); + dos.writeInt(df1); + dos.writeInt(df2); + dos.writeInt(df3); + dos.writeInt(db); + dos.writeInt(dm0); + dos.writeInt(c); + dos.writeInt(minCallsR); + dos.writeInt(minCallsMask); + dos.writeBoolean(hashSeed); + dos.write(oid); + dos.writeBoolean(sparse); + dos.writeBoolean(fastFp); + dos.write(polyType); + dos.writeUTF(hashAlg.getAlgorithmName()); + } + + + public int hashCode() + { + final int prime = 31; + int result = 1; + result = prime * result + N; + result = prime * result + bufferLenBits; + result = prime * result + bufferLenTrits; + result = prime * result + c; + result = prime * result + db; + result = prime * result + df; + result = prime * result + df1; + result = prime * result + df2; + result = prime * result + df3; + result = prime * result + dg; + result = prime * result + dm0; + result = prime * result + dr; + result = prime * result + dr1; + result = prime * result + dr2; + result = prime * result + dr3; + result = prime * result + (fastFp ? 1231 : 1237); + result = prime * result + ((hashAlg == null) ? 0 : hashAlg.getAlgorithmName().hashCode()); + result = prime * result + (hashSeed ? 1231 : 1237); + result = prime * result + llen; + result = prime * result + maxMsgLenBytes; + result = prime * result + minCallsMask; + result = prime * result + minCallsR; + result = prime * result + Arrays.hashCode(oid); + result = prime * result + pkLen; + result = prime * result + polyType; + result = prime * result + q; + result = prime * result + (sparse ? 1231 : 1237); + return result; + } + + public boolean equals(Object obj) + { + if (this == obj) + { + return true; + } + if (obj == null) + { + return false; + } + if (getClass() != obj.getClass()) + { + return false; + } + NTRUEncryptionKeyGenerationParameters other = (NTRUEncryptionKeyGenerationParameters)obj; + if (N != other.N) + { + return false; + } + if (bufferLenBits != other.bufferLenBits) + { + return false; + } + if (bufferLenTrits != other.bufferLenTrits) + { + return false; + } + if (c != other.c) + { + return false; + } + if (db != other.db) + { + return false; + } + if (df != other.df) + { + return false; + } + if (df1 != other.df1) + { + return false; + } + if (df2 != other.df2) + { + return false; + } + if (df3 != other.df3) + { + return false; + } + if (dg != other.dg) + { + return false; + } + if (dm0 != other.dm0) + { + return false; + } + if (dr != other.dr) + { + return false; + } + if (dr1 != other.dr1) + { + return false; + } + if (dr2 != other.dr2) + { + return false; + } + if (dr3 != other.dr3) + { + return false; + } + if (fastFp != other.fastFp) + { + return false; + } + if (hashAlg == null) + { + if (other.hashAlg != null) + { + return false; + } + } + else if (!hashAlg.getAlgorithmName().equals(other.hashAlg.getAlgorithmName())) + { + return false; + } + if (hashSeed != other.hashSeed) + { + return false; + } + if (llen != other.llen) + { + return false; + } + if (maxMsgLenBytes != other.maxMsgLenBytes) + { + return false; + } + if (minCallsMask != other.minCallsMask) + { + return false; + } + if (minCallsR != other.minCallsR) + { + return false; + } + if (!Arrays.equals(oid, other.oid)) + { + return false; + } + if (pkLen != other.pkLen) + { + return false; + } + if (polyType != other.polyType) + { + return false; + } + if (q != other.q) + { + return false; + } + if (sparse != other.sparse) + { + return false; + } + return true; + } + + public String toString() + { + StringBuilder output = new StringBuilder("EncryptionParameters(N=" + N + " q=" + q); + if (polyType == NTRUParameters.TERNARY_POLYNOMIAL_TYPE_SIMPLE) + { + output.append(" polyType=SIMPLE df=" + df); + } + else + { + output.append(" polyType=PRODUCT df1=" + df1 + " df2=" + df2 + " df3=" + df3); + } + output.append(" dm0=" + dm0 + " db=" + db + " c=" + c + " minCallsR=" + minCallsR + " minCallsMask=" + minCallsMask + + " hashSeed=" + hashSeed + " hashAlg=" + hashAlg + " oid=" + Arrays.toString(oid) + " sparse=" + sparse + ")"); + return output.toString(); + } +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionKeyPairGenerator.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionKeyPairGenerator.java new file mode 100644 index 00000000..7a648c8f --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionKeyPairGenerator.java @@ -0,0 +1,113 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import org.bouncycastle.crypto.AsymmetricCipherKeyPair; +import org.bouncycastle.crypto.AsymmetricCipherKeyPairGenerator; +import org.bouncycastle.crypto.KeyGenerationParameters; +import org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.Polynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.ProductFormPolynomial; +import org.bouncycastle.pqc.math.ntru.util.Util; + +/** + * Generates key pairs.<br/> + * The parameter p is hardcoded to 3. + */ +public class NTRUEncryptionKeyPairGenerator + implements AsymmetricCipherKeyPairGenerator +{ + private NTRUEncryptionKeyGenerationParameters params; + + /** + * Constructs a new instance with a set of encryption parameters. + * + * @param param encryption parameters + */ + public void init(KeyGenerationParameters param) + { + this.params = (NTRUEncryptionKeyGenerationParameters)param; + } + + /** + * Generates a new encryption key pair. + * + * @return a key pair + */ + public AsymmetricCipherKeyPair generateKeyPair() + { + int N = params.N; + int q = params.q; + int df = params.df; + int df1 = params.df1; + int df2 = params.df2; + int df3 = params.df3; + int dg = params.dg; + boolean fastFp = params.fastFp; + boolean sparse = params.sparse; + + Polynomial t; + IntegerPolynomial fq; + IntegerPolynomial fp = null; + + // choose a random f that is invertible mod 3 and q + while (true) + { + IntegerPolynomial f; + + // choose random t, calculate f and fp + if (fastFp) + { + // if fastFp=true, f is always invertible mod 3 + t = params.polyType == NTRUParameters.TERNARY_POLYNOMIAL_TYPE_SIMPLE ? Util.generateRandomTernary(N, df, df, sparse, params.getRandom()) : ProductFormPolynomial.generateRandom(N, df1, df2, df3, df3, params.getRandom()); + f = t.toIntegerPolynomial(); + f.mult(3); + f.coeffs[0] += 1; + } + else + { + t = params.polyType == NTRUParameters.TERNARY_POLYNOMIAL_TYPE_SIMPLE ? Util.generateRandomTernary(N, df, df - 1, sparse, params.getRandom()) : ProductFormPolynomial.generateRandom(N, df1, df2, df3, df3 - 1, params.getRandom()); + f = t.toIntegerPolynomial(); + fp = f.invertF3(); + if (fp == null) + { + continue; + } + } + + fq = f.invertFq(q); + if (fq == null) + { + continue; + } + break; + } + + // if fastFp=true, fp=1 + if (fastFp) + { + fp = new IntegerPolynomial(N); + fp.coeffs[0] = 1; + } + + // choose a random g that is invertible mod q + DenseTernaryPolynomial g; + while (true) + { + g = DenseTernaryPolynomial.generateRandom(N, dg, dg - 1, params.getRandom()); + if (g.invertFq(q) != null) + { + break; + } + } + + IntegerPolynomial h = g.mult(fq, q); + h.mult3(q); + h.ensurePositive(q); + g.clear(); + fq.clear(); + + NTRUEncryptionPrivateKeyParameters priv = new NTRUEncryptionPrivateKeyParameters(h, t, fp, params.getEncryptionParameters()); + NTRUEncryptionPublicKeyParameters pub = new NTRUEncryptionPublicKeyParameters(h, params.getEncryptionParameters()); + return new AsymmetricCipherKeyPair(pub, priv); + } +}
\ No newline at end of file diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionKeyParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionKeyParameters.java new file mode 100644 index 00000000..27a7987c --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionKeyParameters.java @@ -0,0 +1,20 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import org.bouncycastle.crypto.params.AsymmetricKeyParameter; + +public class NTRUEncryptionKeyParameters + extends AsymmetricKeyParameter +{ + final protected NTRUEncryptionParameters params; + + public NTRUEncryptionKeyParameters(boolean privateKey, NTRUEncryptionParameters params) + { + super(privateKey); + this.params = params; + } + + public NTRUEncryptionParameters getParameters() + { + return params; + } +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionParameters.java new file mode 100644 index 00000000..eeb38391 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionParameters.java @@ -0,0 +1,410 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; +import java.util.Arrays; + +import org.bouncycastle.crypto.Digest; +import org.bouncycastle.crypto.digests.SHA256Digest; +import org.bouncycastle.crypto.digests.SHA512Digest; + +/** + * A set of parameters for NtruEncrypt. Several predefined parameter sets are available and new ones can be created as well. + */ +public class NTRUEncryptionParameters + implements Cloneable +{ + + public int N, q, df, df1, df2, df3; + public int dr; + public int dr1; + public int dr2; + public int dr3; + public int dg; + int llen; + public int maxMsgLenBytes; + public int db; + public int bufferLenBits; + int bufferLenTrits; + public int dm0; + public int pkLen; + public int c; + public int minCallsR; + public int minCallsMask; + public boolean hashSeed; + public byte[] oid; + public boolean sparse; + public boolean fastFp; + public int polyType; + public Digest hashAlg; + + /** + * Constructs a parameter set that uses ternary private keys (i.e. </code>polyType=SIMPLE</code>). + * + * @param N number of polynomial coefficients + * @param q modulus + * @param df number of ones in the private polynomial <code>f</code> + * @param dm0 minimum acceptable number of -1's, 0's, and 1's in the polynomial <code>m'</code> in the last encryption step + * @param db number of random bits to prepend to the message + * @param c a parameter for the Index Generation Function ({@link org.bouncycastle.pqc.crypto.ntru.IndexGenerator}) + * @param minCallsR minimum number of hash calls for the IGF to make + * @param minCallsMask minimum number of calls to generate the masking polynomial + * @param hashSeed whether to hash the seed in the MGF first (true) or use the seed directly (false) + * @param oid three bytes that uniquely identify the parameter set + * @param sparse whether to treat ternary polynomials as sparsely populated ({@link org.bouncycastle.pqc.math.ntru.polynomial.SparseTernaryPolynomial} vs {@link org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial}) + * @param fastFp whether <code>f=1+p*F</code> for a ternary <code>F</code> (true) or <code>f</code> is ternary (false) + * @param hashAlg a valid identifier for a <code>java.security.MessageDigest</code> instance such as <code>SHA-256</code>. The <code>MessageDigest</code> must support the <code>getDigestLength()</code> method. + */ + public NTRUEncryptionParameters(int N, int q, int df, int dm0, int db, int c, int minCallsR, int minCallsMask, boolean hashSeed, byte[] oid, boolean sparse, boolean fastFp, Digest hashAlg) + { + this.N = N; + this.q = q; + this.df = df; + this.db = db; + this.dm0 = dm0; + this.c = c; + this.minCallsR = minCallsR; + this.minCallsMask = minCallsMask; + this.hashSeed = hashSeed; + this.oid = oid; + this.sparse = sparse; + this.fastFp = fastFp; + this.polyType = NTRUParameters.TERNARY_POLYNOMIAL_TYPE_SIMPLE; + this.hashAlg = hashAlg; + init(); + } + + /** + * Constructs a parameter set that uses product-form private keys (i.e. </code>polyType=PRODUCT</code>). + * + * @param N number of polynomial coefficients + * @param q modulus + * @param df1 number of ones in the private polynomial <code>f1</code> + * @param df2 number of ones in the private polynomial <code>f2</code> + * @param df3 number of ones in the private polynomial <code>f3</code> + * @param dm0 minimum acceptable number of -1's, 0's, and 1's in the polynomial <code>m'</code> in the last encryption step + * @param db number of random bits to prepend to the message + * @param c a parameter for the Index Generation Function ({@link org.bouncycastle.pqc.crypto.ntru.IndexGenerator}) + * @param minCallsR minimum number of hash calls for the IGF to make + * @param minCallsMask minimum number of calls to generate the masking polynomial + * @param hashSeed whether to hash the seed in the MGF first (true) or use the seed directly (false) + * @param oid three bytes that uniquely identify the parameter set + * @param sparse whether to treat ternary polynomials as sparsely populated ({@link org.bouncycastle.pqc.math.ntru.polynomial.SparseTernaryPolynomial} vs {@link org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial}) + * @param fastFp whether <code>f=1+p*F</code> for a ternary <code>F</code> (true) or <code>f</code> is ternary (false) + * @param hashAlg a valid identifier for a <code>java.security.MessageDigest</code> instance such as <code>SHA-256</code> + */ + public NTRUEncryptionParameters(int N, int q, int df1, int df2, int df3, int dm0, int db, int c, int minCallsR, int minCallsMask, boolean hashSeed, byte[] oid, boolean sparse, boolean fastFp, Digest hashAlg) + { + this.N = N; + this.q = q; + this.df1 = df1; + this.df2 = df2; + this.df3 = df3; + this.db = db; + this.dm0 = dm0; + this.c = c; + this.minCallsR = minCallsR; + this.minCallsMask = minCallsMask; + this.hashSeed = hashSeed; + this.oid = oid; + this.sparse = sparse; + this.fastFp = fastFp; + this.polyType = NTRUParameters.TERNARY_POLYNOMIAL_TYPE_PRODUCT; + this.hashAlg = hashAlg; + init(); + } + + private void init() + { + dr = df; + dr1 = df1; + dr2 = df2; + dr3 = df3; + dg = N / 3; + llen = 1; // ceil(log2(maxMsgLenBytes)) + maxMsgLenBytes = N * 3 / 2 / 8 - llen - db / 8 - 1; + bufferLenBits = (N * 3 / 2 + 7) / 8 * 8 + 1; + bufferLenTrits = N - 1; + pkLen = db; + } + + /** + * Reads a parameter set from an input stream. + * + * @param is an input stream + * @throws IOException + */ + public NTRUEncryptionParameters(InputStream is) + throws IOException + { + DataInputStream dis = new DataInputStream(is); + N = dis.readInt(); + q = dis.readInt(); + df = dis.readInt(); + df1 = dis.readInt(); + df2 = dis.readInt(); + df3 = dis.readInt(); + db = dis.readInt(); + dm0 = dis.readInt(); + c = dis.readInt(); + minCallsR = dis.readInt(); + minCallsMask = dis.readInt(); + hashSeed = dis.readBoolean(); + oid = new byte[3]; + dis.read(oid); + sparse = dis.readBoolean(); + fastFp = dis.readBoolean(); + polyType = dis.read(); + + String alg = dis.readUTF(); + + if ("SHA-512".equals(alg)) + { + hashAlg = new SHA512Digest(); + } + else if ("SHA-256".equals(alg)) + { + hashAlg = new SHA256Digest(); + } + + init(); + } + + public NTRUEncryptionParameters clone() + { + if (polyType == NTRUParameters.TERNARY_POLYNOMIAL_TYPE_SIMPLE) + { + return new NTRUEncryptionParameters(N, q, df, dm0, db, c, minCallsR, minCallsMask, hashSeed, oid, sparse, fastFp, hashAlg); + } + else + { + return new NTRUEncryptionParameters(N, q, df1, df2, df3, dm0, db, c, minCallsR, minCallsMask, hashSeed, oid, sparse, fastFp, hashAlg); + } + } + + /** + * Returns the maximum length a plaintext message can be with this parameter set. + * + * @return the maximum length in bytes + */ + public int getMaxMessageLength() + { + return maxMsgLenBytes; + } + + /** + * Writes the parameter set to an output stream + * + * @param os an output stream + * @throws IOException + */ + public void writeTo(OutputStream os) + throws IOException + { + DataOutputStream dos = new DataOutputStream(os); + dos.writeInt(N); + dos.writeInt(q); + dos.writeInt(df); + dos.writeInt(df1); + dos.writeInt(df2); + dos.writeInt(df3); + dos.writeInt(db); + dos.writeInt(dm0); + dos.writeInt(c); + dos.writeInt(minCallsR); + dos.writeInt(minCallsMask); + dos.writeBoolean(hashSeed); + dos.write(oid); + dos.writeBoolean(sparse); + dos.writeBoolean(fastFp); + dos.write(polyType); + dos.writeUTF(hashAlg.getAlgorithmName()); + } + + + public int hashCode() + { + final int prime = 31; + int result = 1; + result = prime * result + N; + result = prime * result + bufferLenBits; + result = prime * result + bufferLenTrits; + result = prime * result + c; + result = prime * result + db; + result = prime * result + df; + result = prime * result + df1; + result = prime * result + df2; + result = prime * result + df3; + result = prime * result + dg; + result = prime * result + dm0; + result = prime * result + dr; + result = prime * result + dr1; + result = prime * result + dr2; + result = prime * result + dr3; + result = prime * result + (fastFp ? 1231 : 1237); + result = prime * result + ((hashAlg == null) ? 0 : hashAlg.getAlgorithmName().hashCode()); + result = prime * result + (hashSeed ? 1231 : 1237); + result = prime * result + llen; + result = prime * result + maxMsgLenBytes; + result = prime * result + minCallsMask; + result = prime * result + minCallsR; + result = prime * result + Arrays.hashCode(oid); + result = prime * result + pkLen; + result = prime * result + polyType; + result = prime * result + q; + result = prime * result + (sparse ? 1231 : 1237); + return result; + } + + public boolean equals(Object obj) + { + if (this == obj) + { + return true; + } + if (obj == null) + { + return false; + } + if (getClass() != obj.getClass()) + { + return false; + } + NTRUEncryptionParameters other = (NTRUEncryptionParameters)obj; + if (N != other.N) + { + return false; + } + if (bufferLenBits != other.bufferLenBits) + { + return false; + } + if (bufferLenTrits != other.bufferLenTrits) + { + return false; + } + if (c != other.c) + { + return false; + } + if (db != other.db) + { + return false; + } + if (df != other.df) + { + return false; + } + if (df1 != other.df1) + { + return false; + } + if (df2 != other.df2) + { + return false; + } + if (df3 != other.df3) + { + return false; + } + if (dg != other.dg) + { + return false; + } + if (dm0 != other.dm0) + { + return false; + } + if (dr != other.dr) + { + return false; + } + if (dr1 != other.dr1) + { + return false; + } + if (dr2 != other.dr2) + { + return false; + } + if (dr3 != other.dr3) + { + return false; + } + if (fastFp != other.fastFp) + { + return false; + } + if (hashAlg == null) + { + if (other.hashAlg != null) + { + return false; + } + } + else if (!hashAlg.getAlgorithmName().equals(other.hashAlg.getAlgorithmName())) + { + return false; + } + if (hashSeed != other.hashSeed) + { + return false; + } + if (llen != other.llen) + { + return false; + } + if (maxMsgLenBytes != other.maxMsgLenBytes) + { + return false; + } + if (minCallsMask != other.minCallsMask) + { + return false; + } + if (minCallsR != other.minCallsR) + { + return false; + } + if (!Arrays.equals(oid, other.oid)) + { + return false; + } + if (pkLen != other.pkLen) + { + return false; + } + if (polyType != other.polyType) + { + return false; + } + if (q != other.q) + { + return false; + } + if (sparse != other.sparse) + { + return false; + } + return true; + } + + public String toString() + { + StringBuilder output = new StringBuilder("EncryptionParameters(N=" + N + " q=" + q); + if (polyType == NTRUParameters.TERNARY_POLYNOMIAL_TYPE_SIMPLE) + { + output.append(" polyType=SIMPLE df=" + df); + } + else + { + output.append(" polyType=PRODUCT df1=" + df1 + " df2=" + df2 + " df3=" + df3); + } + output.append(" dm0=" + dm0 + " db=" + db + " c=" + c + " minCallsR=" + minCallsR + " minCallsMask=" + minCallsMask + + " hashSeed=" + hashSeed + " hashAlg=" + hashAlg + " oid=" + Arrays.toString(oid) + " sparse=" + sparse + ")"); + return output.toString(); + } +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionPrivateKeyParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionPrivateKeyParameters.java new file mode 100644 index 00000000..d1ee858e --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionPrivateKeyParameters.java @@ -0,0 +1,199 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import java.io.ByteArrayInputStream; +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; + +import org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.Polynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.ProductFormPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.SparseTernaryPolynomial; + +/** + * A NtruEncrypt private key is essentially a polynomial named <code>f</code> + * which takes different forms depending on whether product-form polynomials are used, + * and on <code>fastP</code><br/> + * The inverse of <code>f</code> modulo <code>p</code> is precomputed on initialization. + */ +public class NTRUEncryptionPrivateKeyParameters + extends NTRUEncryptionKeyParameters +{ + public Polynomial t; + public IntegerPolynomial fp; + public IntegerPolynomial h; + + /** + * Constructs a new private key from a polynomial + * + * @param h the public polynomial for the key. + * @param t the polynomial which determines the key: if <code>fastFp=true</code>, <code>f=1+3t</code>; otherwise, <code>f=t</code> + * @param fp the inverse of <code>f</code> + * @param params the NtruEncrypt parameters to use + */ + public NTRUEncryptionPrivateKeyParameters(IntegerPolynomial h, Polynomial t, IntegerPolynomial fp, NTRUEncryptionParameters params) + { + super(true, params); + + this.h = h; + this.t = t; + this.fp = fp; + } + + /** + * Converts a byte array to a polynomial <code>f</code> and constructs a new private key + * + * @param b an encoded polynomial + * @param params the NtruEncrypt parameters to use + * @see #getEncoded() + */ + public NTRUEncryptionPrivateKeyParameters(byte[] b, NTRUEncryptionParameters params) + throws IOException + { + this(new ByteArrayInputStream(b), params); + } + + /** + * Reads a polynomial <code>f</code> from an input stream and constructs a new private key + * + * @param is an input stream + * @param params the NtruEncrypt parameters to use + * @see #writeTo(OutputStream) + */ + public NTRUEncryptionPrivateKeyParameters(InputStream is, NTRUEncryptionParameters params) + throws IOException + { + super(true, params); + + if (params.polyType == NTRUParameters.TERNARY_POLYNOMIAL_TYPE_PRODUCT) + { + int N = params.N; + int df1 = params.df1; + int df2 = params.df2; + int df3Ones = params.df3; + int df3NegOnes = params.fastFp ? params.df3 : params.df3 - 1; + h = IntegerPolynomial.fromBinary(is, params.N, params.q); + t = ProductFormPolynomial.fromBinary(is, N, df1, df2, df3Ones, df3NegOnes); + } + else + { + h = IntegerPolynomial.fromBinary(is, params.N, params.q); + IntegerPolynomial fInt = IntegerPolynomial.fromBinary3Tight(is, params.N); + t = params.sparse ? new SparseTernaryPolynomial(fInt) : new DenseTernaryPolynomial(fInt); + } + + init(); + } + + /** + * Initializes <code>fp</code> from t. + */ + private void init() + { + if (params.fastFp) + { + fp = new IntegerPolynomial(params.N); + fp.coeffs[0] = 1; + } + else + { + fp = t.toIntegerPolynomial().invertF3(); + } + } + + /** + * Converts the key to a byte array + * + * @return the encoded key + * @see #NTRUEncryptionPrivateKeyParameters(byte[], NTRUEncryptionParameters) + */ + public byte[] getEncoded() + { + byte[] hBytes = h.toBinary(params.q); + byte[] tBytes; + + if (t instanceof ProductFormPolynomial) + { + tBytes = ((ProductFormPolynomial)t).toBinary(); + } + else + { + tBytes = t.toIntegerPolynomial().toBinary3Tight(); + } + + byte[] res = new byte[hBytes.length + tBytes.length]; + + System.arraycopy(hBytes, 0, res, 0, hBytes.length); + System.arraycopy(tBytes, 0, res, hBytes.length, tBytes.length); + + return res; + } + + /** + * Writes the key to an output stream + * + * @param os an output stream + * @throws IOException + * @see #NTRUEncryptionPrivateKeyParameters(InputStream, NTRUEncryptionParameters) + */ + public void writeTo(OutputStream os) + throws IOException + { + os.write(getEncoded()); + } + + public int hashCode() + { + final int prime = 31; + int result = 1; + result = prime * result + ((params == null) ? 0 : params.hashCode()); + result = prime * result + ((t == null) ? 0 : t.hashCode()); + result = prime * result + ((h == null) ? 0 : h.hashCode()); + return result; + } + + public boolean equals(Object obj) + { + if (this == obj) + { + return true; + } + if (obj == null) + { + return false; + } + if (!(obj instanceof NTRUEncryptionPrivateKeyParameters)) + { + return false; + } + NTRUEncryptionPrivateKeyParameters other = (NTRUEncryptionPrivateKeyParameters)obj; + if (params == null) + { + if (other.params != null) + { + return false; + } + } + else if (!params.equals(other.params)) + { + return false; + } + if (t == null) + { + if (other.t != null) + { + return false; + } + } + else if (!t.equals(other.t)) + { + return false; + } + if (!h.equals(other.h)) + { + return false; + } + return true; + } +}
\ No newline at end of file diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionPublicKeyParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionPublicKeyParameters.java new file mode 100644 index 00000000..0aa03573 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEncryptionPublicKeyParameters.java @@ -0,0 +1,131 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; + +import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; + +/** + * A NtruEncrypt public key is essentially a polynomial named <code>h</code>. + */ +public class NTRUEncryptionPublicKeyParameters + extends NTRUEncryptionKeyParameters +{ + public IntegerPolynomial h; + + /** + * Constructs a new public key from a polynomial + * + * @param h the polynomial <code>h</code> which determines the key + * @param params the NtruEncrypt parameters to use + */ + public NTRUEncryptionPublicKeyParameters(IntegerPolynomial h, NTRUEncryptionParameters params) + { + super(false, params); + + this.h = h; + } + + /** + * Converts a byte array to a polynomial <code>h</code> and constructs a new public key + * + * @param b an encoded polynomial + * @param params the NtruEncrypt parameters to use + * @see #getEncoded() + */ + public NTRUEncryptionPublicKeyParameters(byte[] b, NTRUEncryptionParameters params) + { + super(false, params); + + h = IntegerPolynomial.fromBinary(b, params.N, params.q); + } + + /** + * Reads a polynomial <code>h</code> from an input stream and constructs a new public key + * + * @param is an input stream + * @param params the NtruEncrypt parameters to use + * @see #writeTo(OutputStream) + */ + public NTRUEncryptionPublicKeyParameters(InputStream is, NTRUEncryptionParameters params) + throws IOException + { + super(false, params); + + h = IntegerPolynomial.fromBinary(is, params.N, params.q); + } + + /** + * Converts the key to a byte array + * + * @return the encoded key + * @see #NTRUEncryptionPublicKeyParameters(byte[], NTRUEncryptionParameters) + */ + public byte[] getEncoded() + { + return h.toBinary(params.q); + } + + /** + * Writes the key to an output stream + * + * @param os an output stream + * @throws IOException + * @see #NTRUEncryptionPublicKeyParameters(InputStream, NTRUEncryptionParameters) + */ + public void writeTo(OutputStream os) + throws IOException + { + os.write(getEncoded()); + } + + public int hashCode() + { + final int prime = 31; + int result = 1; + result = prime * result + ((h == null) ? 0 : h.hashCode()); + result = prime * result + ((params == null) ? 0 : params.hashCode()); + return result; + } + + public boolean equals(Object obj) + { + if (this == obj) + { + return true; + } + if (obj == null) + { + return false; + } + if (!(obj instanceof NTRUEncryptionPublicKeyParameters)) + { + return false; + } + NTRUEncryptionPublicKeyParameters other = (NTRUEncryptionPublicKeyParameters)obj; + if (h == null) + { + if (other.h != null) + { + return false; + } + } + else if (!h.equals(other.h)) + { + return false; + } + if (params == null) + { + if (other.params != null) + { + return false; + } + } + else if (!params.equals(other.params)) + { + return false; + } + return true; + } +}
\ No newline at end of file diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEngine.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEngine.java new file mode 100644 index 00000000..1fb6a1de --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUEngine.java @@ -0,0 +1,495 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import java.security.SecureRandom; + +import org.bouncycastle.crypto.AsymmetricBlockCipher; +import org.bouncycastle.crypto.CipherParameters; +import org.bouncycastle.crypto.DataLengthException; +import org.bouncycastle.crypto.Digest; +import org.bouncycastle.crypto.InvalidCipherTextException; +import org.bouncycastle.crypto.params.ParametersWithRandom; +import org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.Polynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.ProductFormPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.SparseTernaryPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.TernaryPolynomial; +import org.bouncycastle.util.Arrays; + +/** + * Encrypts, decrypts data and generates key pairs.<br/> + * The parameter p is hardcoded to 3. + */ +public class NTRUEngine + implements AsymmetricBlockCipher +{ + private boolean forEncryption; + private NTRUEncryptionParameters params; + private NTRUEncryptionPublicKeyParameters pubKey; + private NTRUEncryptionPrivateKeyParameters privKey; + private SecureRandom random; + + /** + * Constructs a new instance with a set of encryption parameters. + * + */ + public NTRUEngine() + { + } + + public void init(boolean forEncryption, CipherParameters parameters) + { + this.forEncryption = forEncryption; + if (forEncryption) + { + if (parameters instanceof ParametersWithRandom) + { + ParametersWithRandom p = (ParametersWithRandom)parameters; + + this.random = p.getRandom(); + this.pubKey = (NTRUEncryptionPublicKeyParameters)p.getParameters(); + } + else + { + this.random = new SecureRandom(); + this.pubKey = (NTRUEncryptionPublicKeyParameters)parameters; + } + + this.params = pubKey.getParameters(); + } + else + { + this.privKey = (NTRUEncryptionPrivateKeyParameters)parameters; + this.params = privKey.getParameters(); + } + } + + public int getInputBlockSize() + { + return params.maxMsgLenBytes; + } + + public int getOutputBlockSize() + { + return ((params.N * log2(params.q)) + 7) / 8; + } + + public byte[] processBlock(byte[] in, int inOff, int len) + throws InvalidCipherTextException + { + byte[] tmp = new byte[len]; + + System.arraycopy(in, inOff, tmp, 0, len); + + if (forEncryption) + { + return encrypt(tmp, pubKey); + } + else + { + return decrypt(tmp, privKey); + } + } + + /** + * Encrypts a message.<br/> + * See P1363.1 section 9.2.2. + * + * @param m The message to encrypt + * @param pubKey the public key to encrypt the message with + * @return the encrypted message + */ + private byte[] encrypt(byte[] m, NTRUEncryptionPublicKeyParameters pubKey) + { + IntegerPolynomial pub = pubKey.h; + int N = params.N; + int q = params.q; + + int maxLenBytes = params.maxMsgLenBytes; + int db = params.db; + int bufferLenBits = params.bufferLenBits; + int dm0 = params.dm0; + int pkLen = params.pkLen; + int minCallsMask = params.minCallsMask; + boolean hashSeed = params.hashSeed; + byte[] oid = params.oid; + + int l = m.length; + if (maxLenBytes > 255) + { + throw new IllegalArgumentException("llen values bigger than 1 are not supported"); + } + if (l > maxLenBytes) + { + throw new DataLengthException("Message too long: " + l + ">" + maxLenBytes); + } + + while (true) + { + // M = b|octL|m|p0 + byte[] b = new byte[db / 8]; + random.nextBytes(b); + byte[] p0 = new byte[maxLenBytes + 1 - l]; + byte[] M = new byte[bufferLenBits / 8]; + + System.arraycopy(b, 0, M, 0, b.length); + M[b.length] = (byte)l; + System.arraycopy(m, 0, M, b.length + 1, m.length); + System.arraycopy(p0, 0, M, b.length + 1 + m.length, p0.length); + + IntegerPolynomial mTrin = IntegerPolynomial.fromBinary3Sves(M, N); + + // sData = OID|m|b|hTrunc + byte[] bh = pub.toBinary(q); + byte[] hTrunc = copyOf(bh, pkLen / 8); + byte[] sData = buildSData(oid, m, l, b, hTrunc); + + Polynomial r = generateBlindingPoly(sData, M); + IntegerPolynomial R = r.mult(pub, q); + IntegerPolynomial R4 = (IntegerPolynomial)R.clone(); + R4.modPositive(4); + byte[] oR4 = R4.toBinary(4); + IntegerPolynomial mask = MGF(oR4, N, minCallsMask, hashSeed); + mTrin.add(mask); + mTrin.mod3(); + + if (mTrin.count(-1) < dm0) + { + continue; + } + if (mTrin.count(0) < dm0) + { + continue; + } + if (mTrin.count(1) < dm0) + { + continue; + } + + R.add(mTrin, q); + R.ensurePositive(q); + return R.toBinary(q); + } + } + + private byte[] buildSData(byte[] oid, byte[] m, int l, byte[] b, byte[] hTrunc) + { + byte[] sData = new byte[oid.length + l + b.length + hTrunc.length]; + + System.arraycopy(oid, 0, sData, 0, oid.length); + System.arraycopy(m, 0, sData, oid.length, m.length); + System.arraycopy(b, 0, sData, oid.length + m.length, b.length); + System.arraycopy(hTrunc, 0, sData, oid.length + m.length + b.length, hTrunc.length); + return sData; + } + + protected IntegerPolynomial encrypt(IntegerPolynomial m, TernaryPolynomial r, IntegerPolynomial pubKey) + { + IntegerPolynomial e = r.mult(pubKey, params.q); + e.add(m, params.q); + e.ensurePositive(params.q); + return e; + } + + /** + * Deterministically generates a blinding polynomial from a seed and a message representative. + * + * @param seed + * @param M message representative + * @return a blinding polynomial + */ + private Polynomial generateBlindingPoly(byte[] seed, byte[] M) + { + IndexGenerator ig = new IndexGenerator(seed, params); + + if (params.polyType == NTRUParameters.TERNARY_POLYNOMIAL_TYPE_PRODUCT) + { + SparseTernaryPolynomial r1 = new SparseTernaryPolynomial(generateBlindingCoeffs(ig, params.dr1)); + SparseTernaryPolynomial r2 = new SparseTernaryPolynomial(generateBlindingCoeffs(ig, params.dr2)); + SparseTernaryPolynomial r3 = new SparseTernaryPolynomial(generateBlindingCoeffs(ig, params.dr3)); + return new ProductFormPolynomial(r1, r2, r3); + } + else + { + int dr = params.dr; + boolean sparse = params.sparse; + int[] r = generateBlindingCoeffs(ig, dr); + if (sparse) + { + return new SparseTernaryPolynomial(r); + } + else + { + return new DenseTernaryPolynomial(r); + } + } + } + + /** + * Generates an <code>int</code> array containing <code>dr</code> elements equal to <code>1</code> + * and <code>dr</code> elements equal to <code>-1</code> using an index generator. + * + * @param ig an index generator + * @param dr number of ones / negative ones + * @return an array containing numbers between <code>-1</code> and <code>1</code> + */ + private int[] generateBlindingCoeffs(IndexGenerator ig, int dr) + { + int N = params.N; + + int[] r = new int[N]; + for (int coeff = -1; coeff <= 1; coeff += 2) + { + int t = 0; + while (t < dr) + { + int i = ig.nextIndex(); + if (r[i] == 0) + { + r[i] = coeff; + t++; + } + } + } + + return r; + } + + /** + * An implementation of MGF-TP-1 from P1363.1 section 8.4.1.1. + * + * @param seed + * @param N + * @param minCallsR + * @param hashSeed whether to hash the seed + * @return + */ + private IntegerPolynomial MGF(byte[] seed, int N, int minCallsR, boolean hashSeed) + { + Digest hashAlg = params.hashAlg; + int hashLen = hashAlg.getDigestSize(); + byte[] buf = new byte[minCallsR * hashLen]; + byte[] Z = hashSeed ? calcHash(hashAlg, seed) : seed; + int counter = 0; + while (counter < minCallsR) + { + hashAlg.update(Z, 0, Z.length); + putInt(hashAlg, counter); + + byte[] hash = calcHash(hashAlg); + System.arraycopy(hash, 0, buf, counter * hashLen, hashLen); + counter++; + } + + IntegerPolynomial i = new IntegerPolynomial(N); + while (true) + { + int cur = 0; + for (int index = 0; index != buf.length; index++) + { + int O = (int)buf[index] & 0xFF; + if (O >= 243) // 243 = 3^5 + { + continue; + } + + for (int terIdx = 0; terIdx < 4; terIdx++) + { + int rem3 = O % 3; + i.coeffs[cur] = rem3 - 1; + cur++; + if (cur == N) + { + return i; + } + O = (O - rem3) / 3; + } + + i.coeffs[cur] = O - 1; + cur++; + if (cur == N) + { + return i; + } + } + + if (cur >= N) + { + return i; + } + + hashAlg.update(Z, 0, Z.length); + putInt(hashAlg, counter); + + byte[] hash = calcHash(hashAlg); + + buf = hash; + + counter++; + } + } + + private void putInt(Digest hashAlg, int counter) + { + hashAlg.update((byte)(counter >> 24)); + hashAlg.update((byte)(counter >> 16)); + hashAlg.update((byte)(counter >> 8)); + hashAlg.update((byte)counter); + } + + private byte[] calcHash(Digest hashAlg) + { + byte[] tmp = new byte[hashAlg.getDigestSize()]; + + hashAlg.doFinal(tmp, 0); + + return tmp; + } + + private byte[] calcHash(Digest hashAlg, byte[] input) + { + byte[] tmp = new byte[hashAlg.getDigestSize()]; + + hashAlg.update(input, 0, input.length); + hashAlg.doFinal(tmp, 0); + + return tmp; + } + /** + * Decrypts a message.<br/> + * See P1363.1 section 9.2.3. + * + * @param data The message to decrypt + * @param privKey the corresponding private key + * @return the decrypted message + * @throws InvalidCipherTextException if the encrypted data is invalid, or <code>maxLenBytes</code> is greater than 255 + */ + private byte[] decrypt(byte[] data, NTRUEncryptionPrivateKeyParameters privKey) + throws InvalidCipherTextException + { + Polynomial priv_t = privKey.t; + IntegerPolynomial priv_fp = privKey.fp; + IntegerPolynomial pub = privKey.h; + int N = params.N; + int q = params.q; + int db = params.db; + int maxMsgLenBytes = params.maxMsgLenBytes; + int dm0 = params.dm0; + int pkLen = params.pkLen; + int minCallsMask = params.minCallsMask; + boolean hashSeed = params.hashSeed; + byte[] oid = params.oid; + + if (maxMsgLenBytes > 255) + { + throw new DataLengthException("maxMsgLenBytes values bigger than 255 are not supported"); + } + + int bLen = db / 8; + + IntegerPolynomial e = IntegerPolynomial.fromBinary(data, N, q); + IntegerPolynomial ci = decrypt(e, priv_t, priv_fp); + + if (ci.count(-1) < dm0) + { + throw new InvalidCipherTextException("Less than dm0 coefficients equal -1"); + } + if (ci.count(0) < dm0) + { + throw new InvalidCipherTextException("Less than dm0 coefficients equal 0"); + } + if (ci.count(1) < dm0) + { + throw new InvalidCipherTextException("Less than dm0 coefficients equal 1"); + } + + IntegerPolynomial cR = (IntegerPolynomial)e.clone(); + cR.sub(ci); + cR.modPositive(q); + IntegerPolynomial cR4 = (IntegerPolynomial)cR.clone(); + cR4.modPositive(4); + byte[] coR4 = cR4.toBinary(4); + IntegerPolynomial mask = MGF(coR4, N, minCallsMask, hashSeed); + IntegerPolynomial cMTrin = ci; + cMTrin.sub(mask); + cMTrin.mod3(); + byte[] cM = cMTrin.toBinary3Sves(); + + byte[] cb = new byte[bLen]; + System.arraycopy(cM, 0, cb, 0, bLen); + int cl = cM[bLen] & 0xFF; // llen=1, so read one byte + if (cl > maxMsgLenBytes) + { + throw new InvalidCipherTextException("Message too long: " + cl + ">" + maxMsgLenBytes); + } + byte[] cm = new byte[cl]; + System.arraycopy(cM, bLen + 1, cm, 0, cl); + byte[] p0 = new byte[cM.length - (bLen + 1 + cl)]; + System.arraycopy(cM, bLen + 1 + cl, p0, 0, p0.length); + if (!Arrays.areEqual(p0, new byte[p0.length])) + { + throw new InvalidCipherTextException("The message is not followed by zeroes"); + } + + // sData = OID|m|b|hTrunc + byte[] bh = pub.toBinary(q); + byte[] hTrunc = copyOf(bh, pkLen / 8); + byte[] sData = buildSData(oid, cm, cl, cb, hTrunc); + + Polynomial cr = generateBlindingPoly(sData, cm); + IntegerPolynomial cRPrime = cr.mult(pub); + cRPrime.modPositive(q); + if (!cRPrime.equals(cR)) + { + throw new InvalidCipherTextException("Invalid message encoding"); + } + + return cm; + } + + /** + * @param e + * @param priv_t a polynomial such that if <code>fastFp=true</code>, <code>f=1+3*priv_t</code>; otherwise, <code>f=priv_t</code> + * @param priv_fp + * @return + */ + protected IntegerPolynomial decrypt(IntegerPolynomial e, Polynomial priv_t, IntegerPolynomial priv_fp) + { + IntegerPolynomial a; + if (params.fastFp) + { + a = priv_t.mult(e, params.q); + a.mult(3); + a.add(e); + } + else + { + a = priv_t.mult(e, params.q); + } + a.center0(params.q); + a.mod3(); + + IntegerPolynomial c = params.fastFp ? a : new DenseTernaryPolynomial(a).mult(priv_fp, 3); + c.center0(3); + return c; + } + + private byte[] copyOf(byte[] src, int len) + { + byte[] tmp = new byte[len]; + + System.arraycopy(src, 0, tmp, 0, len < src.length ? len : src.length); + + return tmp; + } + + private int log2(int value) + { + if (value == 2048) + { + return 11; + } + + throw new IllegalStateException("log2 not fully implemented"); + } +}
\ No newline at end of file diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUParameters.java new file mode 100644 index 00000000..158c0386 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUParameters.java @@ -0,0 +1,7 @@ +package org.bouncycastle.pqc.crypto.ntru; + +public class NTRUParameters +{ + public static final int TERNARY_POLYNOMIAL_TYPE_SIMPLE = 0; + public static final int TERNARY_POLYNOMIAL_TYPE_PRODUCT = 1; +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigner.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigner.java new file mode 100644 index 00000000..0b8a0788 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigner.java @@ -0,0 +1,259 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import java.nio.ByteBuffer; + +import org.bouncycastle.crypto.CipherParameters; +import org.bouncycastle.crypto.Digest; +import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.Polynomial; + +/** + * Signs, verifies data and generates key pairs. + */ +public class NTRUSigner +{ + private NTRUSigningParameters params; + private Digest hashAlg; + private NTRUSigningPrivateKeyParameters signingKeyPair; + private NTRUSigningPublicKeyParameters verificationKey; + + /** + * Constructs a new instance with a set of signature parameters. + * + * @param params signature parameters + */ + public NTRUSigner(NTRUSigningParameters params) + { + this.params = params; + } + + /** + * Resets the engine for signing a message. + * + * @param forSigning + * @param params + */ + public void init(boolean forSigning, CipherParameters params) + { + if (forSigning) + { + this.signingKeyPair = (NTRUSigningPrivateKeyParameters)params; + } + else + { + this.verificationKey = (NTRUSigningPublicKeyParameters)params; + } + hashAlg = this.params.hashAlg; + hashAlg.reset(); + } + + /** + * Adds data to sign or verify. + * + * @param b data + */ + public void update(byte b) + { + if (hashAlg == null) + { + throw new IllegalStateException("Call initSign or initVerify first!"); + } + + hashAlg.update(b); + } + + /** + * Adds data to sign or verify. + * + * @param m data + * @param off offset + * @param length number of bytes + */ + public void update(byte[] m, int off, int length) + { + if (hashAlg == null) + { + throw new IllegalStateException("Call initSign or initVerify first!"); + } + + hashAlg.update(m, off, length); + } + + /** + * Adds data to sign and computes a signature over this data and any data previously added via {@link #update(byte[], int, int)}. + * + * @return a signature + * @throws IllegalStateException if <code>initSign</code> was not called + */ + public byte[] generateSignature() + { + if (hashAlg == null || signingKeyPair == null) + { + throw new IllegalStateException("Call initSign first!"); + } + + byte[] msgHash = new byte[hashAlg.getDigestSize()]; + + hashAlg.doFinal(msgHash, 0); + return signHash(msgHash, signingKeyPair); + } + + private byte[] signHash(byte[] msgHash, NTRUSigningPrivateKeyParameters kp) + { + int r = 0; + IntegerPolynomial s; + IntegerPolynomial i; + + NTRUSigningPublicKeyParameters kPub = kp.getPublicKey(); + do + { + r++; + if (r > params.signFailTolerance) + { + throw new IllegalStateException("Signing failed: too many retries (max=" + params.signFailTolerance + ")"); + } + i = createMsgRep(msgHash, r); + s = sign(i, kp); + } + while (!verify(i, s, kPub.h)); + + byte[] rawSig = s.toBinary(params.q); + ByteBuffer sbuf = ByteBuffer.allocate(rawSig.length + 4); + sbuf.put(rawSig); + sbuf.putInt(r); + return sbuf.array(); + } + + private IntegerPolynomial sign(IntegerPolynomial i, NTRUSigningPrivateKeyParameters kp) + { + int N = params.N; + int q = params.q; + int perturbationBases = params.B; + + NTRUSigningPrivateKeyParameters kPriv = kp; + NTRUSigningPublicKeyParameters kPub = kp.getPublicKey(); + + IntegerPolynomial s = new IntegerPolynomial(N); + int iLoop = perturbationBases; + while (iLoop >= 1) + { + Polynomial f = kPriv.getBasis(iLoop).f; + Polynomial fPrime = kPriv.getBasis(iLoop).fPrime; + + IntegerPolynomial y = f.mult(i); + y.div(q); + y = fPrime.mult(y); + + IntegerPolynomial x = fPrime.mult(i); + x.div(q); + x = f.mult(x); + + IntegerPolynomial si = y; + si.sub(x); + s.add(si); + + IntegerPolynomial hi = (IntegerPolynomial)kPriv.getBasis(iLoop).h.clone(); + if (iLoop > 1) + { + hi.sub(kPriv.getBasis(iLoop - 1).h); + } + else + { + hi.sub(kPub.h); + } + i = si.mult(hi, q); + + iLoop--; + } + + Polynomial f = kPriv.getBasis(0).f; + Polynomial fPrime = kPriv.getBasis(0).fPrime; + + IntegerPolynomial y = f.mult(i); + y.div(q); + y = fPrime.mult(y); + + IntegerPolynomial x = fPrime.mult(i); + x.div(q); + x = f.mult(x); + + y.sub(x); + s.add(y); + s.modPositive(q); + return s; + } + + /** + * Verifies a signature for any data previously added via {@link #update(byte[], int, int)}. + * + * @param sig a signature + * @return whether the signature is valid + * @throws IllegalStateException if <code>initVerify</code> was not called + */ + public boolean verifySignature(byte[] sig) + { + if (hashAlg == null || verificationKey == null) + { + throw new IllegalStateException("Call initVerify first!"); + } + + byte[] msgHash = new byte[hashAlg.getDigestSize()]; + + hashAlg.doFinal(msgHash, 0); + + return verifyHash(msgHash, sig, verificationKey); + } + + private boolean verifyHash(byte[] msgHash, byte[] sig, NTRUSigningPublicKeyParameters pub) + { + ByteBuffer sbuf = ByteBuffer.wrap(sig); + byte[] rawSig = new byte[sig.length - 4]; + sbuf.get(rawSig); + IntegerPolynomial s = IntegerPolynomial.fromBinary(rawSig, params.N, params.q); + int r = sbuf.getInt(); + return verify(createMsgRep(msgHash, r), s, pub.h); + } + + private boolean verify(IntegerPolynomial i, IntegerPolynomial s, IntegerPolynomial h) + { + int q = params.q; + double normBoundSq = params.normBoundSq; + double betaSq = params.betaSq; + + IntegerPolynomial t = h.mult(s, q); + t.sub(i); + long centeredNormSq = (long)(s.centeredNormSq(q) + betaSq * t.centeredNormSq(q)); + return centeredNormSq <= normBoundSq; + } + + protected IntegerPolynomial createMsgRep(byte[] msgHash, int r) + { + int N = params.N; + int q = params.q; + + int c = 31 - Integer.numberOfLeadingZeros(q); + int B = (c + 7) / 8; + IntegerPolynomial i = new IntegerPolynomial(N); + + ByteBuffer cbuf = ByteBuffer.allocate(msgHash.length + 4); + cbuf.put(msgHash); + cbuf.putInt(r); + NTRUSignerPrng prng = new NTRUSignerPrng(cbuf.array(), params.hashAlg); + + for (int t = 0; t < N; t++) + { + byte[] o = prng.nextBytes(B); + int hi = o[o.length - 1]; + hi >>= 8 * B - c; + hi <<= 8 * B - c; + o[o.length - 1] = (byte)hi; + + ByteBuffer obuf = ByteBuffer.allocate(4); + obuf.put(o); + obuf.rewind(); + // reverse byte order so it matches the endianness of java ints + i.coeffs[t] = Integer.reverseBytes(obuf.getInt()); + } + return i; + } +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSignerPrng.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSignerPrng.java new file mode 100644 index 00000000..77ed63a2 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSignerPrng.java @@ -0,0 +1,64 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import java.nio.ByteBuffer; + +import org.bouncycastle.crypto.Digest; + +/** + * An implementation of the deterministic pseudo-random generator in EESS section 3.7.3.1 + */ +public class NTRUSignerPrng +{ + private int counter; + private byte[] seed; + private Digest hashAlg; + + /** + * Constructs a new PRNG and seeds it with a byte array. + * + * @param seed a seed + * @param hashAlg the hash algorithm to use + */ + NTRUSignerPrng(byte[] seed, Digest hashAlg) + { + counter = 0; + this.seed = seed; + this.hashAlg = hashAlg; + } + + /** + * Returns <code>n</code> random bytes + * + * @param n number of bytes to return + * @return the next <code>n</code> random bytes + */ + byte[] nextBytes(int n) + { + ByteBuffer buf = ByteBuffer.allocate(n); + + while (buf.hasRemaining()) + { + ByteBuffer cbuf = ByteBuffer.allocate(seed.length + 4); + cbuf.put(seed); + cbuf.putInt(counter); + byte[] array = cbuf.array(); + byte[] hash = new byte[hashAlg.getDigestSize()]; + + hashAlg.update(array, 0, array.length); + + hashAlg.doFinal(hash, 0); + + if (buf.remaining() < hash.length) + { + buf.put(hash, 0, buf.remaining()); + } + else + { + buf.put(hash); + } + counter++; + } + + return buf.array(); + } +}
\ No newline at end of file diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningKeyGenerationParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningKeyGenerationParameters.java new file mode 100644 index 00000000..1398e2b6 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningKeyGenerationParameters.java @@ -0,0 +1,407 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; +import java.security.SecureRandom; +import java.text.DecimalFormat; + +import org.bouncycastle.crypto.Digest; +import org.bouncycastle.crypto.KeyGenerationParameters; +import org.bouncycastle.crypto.digests.SHA256Digest; +import org.bouncycastle.crypto.digests.SHA512Digest; + +/** + * A set of parameters for NtruSign. Several predefined parameter sets are available and new ones can be created as well. + */ +public class NTRUSigningKeyGenerationParameters + extends KeyGenerationParameters + implements Cloneable +{ + public static final int BASIS_TYPE_STANDARD = 0; + public static final int BASIS_TYPE_TRANSPOSE = 1; + + public static final int KEY_GEN_ALG_RESULTANT = 0; + public static final int KEY_GEN_ALG_FLOAT = 1; + + /** + * Gives 128 bits of security + */ + public static final NTRUSigningKeyGenerationParameters APR2011_439 = new NTRUSigningKeyGenerationParameters(439, 2048, 146, 1, BASIS_TYPE_TRANSPOSE, 0.165, 400, 280, false, true, KEY_GEN_ALG_RESULTANT, new SHA256Digest()); + + /** + * Like <code>APR2011_439</code>, this parameter set gives 128 bits of security but uses product-form polynomials + */ + public static final NTRUSigningKeyGenerationParameters APR2011_439_PROD = new NTRUSigningKeyGenerationParameters(439, 2048, 9, 8, 5, 1, BASIS_TYPE_TRANSPOSE, 0.165, 400, 280, false, true, KEY_GEN_ALG_RESULTANT, new SHA256Digest()); + + /** + * Gives 256 bits of security + */ + public static final NTRUSigningKeyGenerationParameters APR2011_743 = new NTRUSigningKeyGenerationParameters(743, 2048, 248, 1, BASIS_TYPE_TRANSPOSE, 0.127, 405, 360, true, false, KEY_GEN_ALG_RESULTANT, new SHA512Digest()); + + /** + * Like <code>APR2011_439</code>, this parameter set gives 256 bits of security but uses product-form polynomials + */ + public static final NTRUSigningKeyGenerationParameters APR2011_743_PROD = new NTRUSigningKeyGenerationParameters(743, 2048, 11, 11, 15, 1, BASIS_TYPE_TRANSPOSE, 0.127, 405, 360, true, false, KEY_GEN_ALG_RESULTANT, new SHA512Digest()); + + /** + * Generates key pairs quickly. Use for testing only. + */ + public static final NTRUSigningKeyGenerationParameters TEST157 = new NTRUSigningKeyGenerationParameters(157, 256, 29, 1, BASIS_TYPE_TRANSPOSE, 0.38, 200, 80, false, false, KEY_GEN_ALG_RESULTANT, new SHA256Digest()); + /** + * Generates key pairs quickly. Use for testing only. + */ + public static final NTRUSigningKeyGenerationParameters TEST157_PROD = new NTRUSigningKeyGenerationParameters(157, 256, 5, 5, 8, 1, BASIS_TYPE_TRANSPOSE, 0.38, 200, 80, false, false, KEY_GEN_ALG_RESULTANT, new SHA256Digest()); + + + public int N; + public int q; + public int d, d1, d2, d3, B; + double beta; + public double betaSq; + double normBound; + public double normBoundSq; + public int signFailTolerance = 100; + double keyNormBound; + public double keyNormBoundSq; + public boolean primeCheck; // true if N and 2N+1 are prime + public int basisType; + int bitsF = 6; // max #bits needed to encode one coefficient of the polynomial F + public boolean sparse; // whether to treat ternary polynomials as sparsely populated + public int keyGenAlg; + public Digest hashAlg; + public int polyType; + + /** + * Constructs a parameter set that uses ternary private keys (i.e. </code>polyType=SIMPLE</code>). + * + * @param N number of polynomial coefficients + * @param q modulus + * @param d number of -1's in the private polynomials <code>f</code> and <code>g</code> + * @param B number of perturbations + * @param basisType whether to use the standard or transpose lattice + * @param beta balancing factor for the transpose lattice + * @param normBound maximum norm for valid signatures + * @param keyNormBound maximum norm for the ploynomials <code>F</code> and <code>G</code> + * @param primeCheck whether <code>2N+1</code> is prime + * @param sparse whether to treat ternary polynomials as sparsely populated ({@link org.bouncycastle.pqc.math.ntru.polynomial.SparseTernaryPolynomial} vs {@link org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial}) + * @param keyGenAlg <code>RESULTANT</code> produces better bases, <code>FLOAT</code> is slightly faster. <code>RESULTANT</code> follows the EESS standard while <code>FLOAT</code> is described in Hoffstein et al: An Introduction to Mathematical Cryptography. + * @param hashAlg a valid identifier for a <code>java.security.MessageDigest</code> instance such as <code>SHA-256</code>. The <code>MessageDigest</code> must support the <code>getDigestLength()</code> method. + */ + public NTRUSigningKeyGenerationParameters(int N, int q, int d, int B, int basisType, double beta, double normBound, double keyNormBound, boolean primeCheck, boolean sparse, int keyGenAlg, Digest hashAlg) + { + super(new SecureRandom(), N); + this.N = N; + this.q = q; + this.d = d; + this.B = B; + this.basisType = basisType; + this.beta = beta; + this.normBound = normBound; + this.keyNormBound = keyNormBound; + this.primeCheck = primeCheck; + this.sparse = sparse; + this.keyGenAlg = keyGenAlg; + this.hashAlg = hashAlg; + polyType = NTRUParameters.TERNARY_POLYNOMIAL_TYPE_SIMPLE; + init(); + } + + /** + * Constructs a parameter set that uses product-form private keys (i.e. </code>polyType=PRODUCT</code>). + * + * @param N number of polynomial coefficients + * @param q modulus + * @param d1 number of -1's in the private polynomials <code>f</code> and <code>g</code> + * @param d2 number of -1's in the private polynomials <code>f</code> and <code>g</code> + * @param d3 number of -1's in the private polynomials <code>f</code> and <code>g</code> + * @param B number of perturbations + * @param basisType whether to use the standard or transpose lattice + * @param beta balancing factor for the transpose lattice + * @param normBound maximum norm for valid signatures + * @param keyNormBound maximum norm for the ploynomials <code>F</code> and <code>G</code> + * @param primeCheck whether <code>2N+1</code> is prime + * @param sparse whether to treat ternary polynomials as sparsely populated ({@link org.bouncycastle.pqc.math.ntru.polynomial.SparseTernaryPolynomial} vs {@link org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial}) + * @param keyGenAlg <code>RESULTANT</code> produces better bases, <code>FLOAT</code> is slightly faster. <code>RESULTANT</code> follows the EESS standard while <code>FLOAT</code> is described in Hoffstein et al: An Introduction to Mathematical Cryptography. + * @param hashAlg a valid identifier for a <code>java.security.MessageDigest</code> instance such as <code>SHA-256</code>. The <code>MessageDigest</code> must support the <code>getDigestLength()</code> method. + */ + public NTRUSigningKeyGenerationParameters(int N, int q, int d1, int d2, int d3, int B, int basisType, double beta, double normBound, double keyNormBound, boolean primeCheck, boolean sparse, int keyGenAlg, Digest hashAlg) + { + super(new SecureRandom(), N); + this.N = N; + this.q = q; + this.d1 = d1; + this.d2 = d2; + this.d3 = d3; + this.B = B; + this.basisType = basisType; + this.beta = beta; + this.normBound = normBound; + this.keyNormBound = keyNormBound; + this.primeCheck = primeCheck; + this.sparse = sparse; + this.keyGenAlg = keyGenAlg; + this.hashAlg = hashAlg; + polyType = NTRUParameters.TERNARY_POLYNOMIAL_TYPE_PRODUCT; + init(); + } + + private void init() + { + betaSq = beta * beta; + normBoundSq = normBound * normBound; + keyNormBoundSq = keyNormBound * keyNormBound; + } + + /** + * Reads a parameter set from an input stream. + * + * @param is an input stream + * @throws java.io.IOException + */ + public NTRUSigningKeyGenerationParameters(InputStream is) + throws IOException + { + super(new SecureRandom(), 0); // TODO: + DataInputStream dis = new DataInputStream(is); + N = dis.readInt(); + q = dis.readInt(); + d = dis.readInt(); + d1 = dis.readInt(); + d2 = dis.readInt(); + d3 = dis.readInt(); + B = dis.readInt(); + basisType = dis.readInt(); + beta = dis.readDouble(); + normBound = dis.readDouble(); + keyNormBound = dis.readDouble(); + signFailTolerance = dis.readInt(); + primeCheck = dis.readBoolean(); + sparse = dis.readBoolean(); + bitsF = dis.readInt(); + keyGenAlg = dis.read(); + String alg = dis.readUTF(); + if ("SHA-512".equals(alg)) + { + hashAlg = new SHA512Digest(); + } + else if ("SHA-256".equals(alg)) + { + hashAlg = new SHA256Digest(); + } + polyType = dis.read(); + init(); + } + + /** + * Writes the parameter set to an output stream + * + * @param os an output stream + * @throws java.io.IOException + */ + public void writeTo(OutputStream os) + throws IOException + { + DataOutputStream dos = new DataOutputStream(os); + dos.writeInt(N); + dos.writeInt(q); + dos.writeInt(d); + dos.writeInt(d1); + dos.writeInt(d2); + dos.writeInt(d3); + dos.writeInt(B); + dos.writeInt(basisType); + dos.writeDouble(beta); + dos.writeDouble(normBound); + dos.writeDouble(keyNormBound); + dos.writeInt(signFailTolerance); + dos.writeBoolean(primeCheck); + dos.writeBoolean(sparse); + dos.writeInt(bitsF); + dos.write(keyGenAlg); + dos.writeUTF(hashAlg.getAlgorithmName()); + dos.write(polyType); + } + + public NTRUSigningParameters getSigningParameters() + { + return new NTRUSigningParameters(N, q, d, B, beta, normBound, hashAlg); + } + + public NTRUSigningKeyGenerationParameters clone() + { + if (polyType == NTRUParameters.TERNARY_POLYNOMIAL_TYPE_SIMPLE) + { + return new NTRUSigningKeyGenerationParameters(N, q, d, B, basisType, beta, normBound, keyNormBound, primeCheck, sparse, keyGenAlg, hashAlg); + } + else + { + return new NTRUSigningKeyGenerationParameters(N, q, d1, d2, d3, B, basisType, beta, normBound, keyNormBound, primeCheck, sparse, keyGenAlg, hashAlg); + } + } + + public int hashCode() + { + final int prime = 31; + int result = 1; + result = prime * result + B; + result = prime * result + N; + result = prime * result + basisType; + long temp; + temp = Double.doubleToLongBits(beta); + result = prime * result + (int)(temp ^ (temp >>> 32)); + temp = Double.doubleToLongBits(betaSq); + result = prime * result + (int)(temp ^ (temp >>> 32)); + result = prime * result + bitsF; + result = prime * result + d; + result = prime * result + d1; + result = prime * result + d2; + result = prime * result + d3; + result = prime * result + ((hashAlg == null) ? 0 : hashAlg.getAlgorithmName().hashCode()); + result = prime * result + keyGenAlg; + temp = Double.doubleToLongBits(keyNormBound); + result = prime * result + (int)(temp ^ (temp >>> 32)); + temp = Double.doubleToLongBits(keyNormBoundSq); + result = prime * result + (int)(temp ^ (temp >>> 32)); + temp = Double.doubleToLongBits(normBound); + result = prime * result + (int)(temp ^ (temp >>> 32)); + temp = Double.doubleToLongBits(normBoundSq); + result = prime * result + (int)(temp ^ (temp >>> 32)); + result = prime * result + polyType; + result = prime * result + (primeCheck ? 1231 : 1237); + result = prime * result + q; + result = prime * result + signFailTolerance; + result = prime * result + (sparse ? 1231 : 1237); + return result; + } + + public boolean equals(Object obj) + { + if (this == obj) + { + return true; + } + if (obj == null) + { + return false; + } + if (!(obj instanceof NTRUSigningKeyGenerationParameters)) + { + return false; + } + NTRUSigningKeyGenerationParameters other = (NTRUSigningKeyGenerationParameters)obj; + if (B != other.B) + { + return false; + } + if (N != other.N) + { + return false; + } + if (basisType != other.basisType) + { + return false; + } + if (Double.doubleToLongBits(beta) != Double.doubleToLongBits(other.beta)) + { + return false; + } + if (Double.doubleToLongBits(betaSq) != Double.doubleToLongBits(other.betaSq)) + { + return false; + } + if (bitsF != other.bitsF) + { + return false; + } + if (d != other.d) + { + return false; + } + if (d1 != other.d1) + { + return false; + } + if (d2 != other.d2) + { + return false; + } + if (d3 != other.d3) + { + return false; + } + if (hashAlg == null) + { + if (other.hashAlg != null) + { + return false; + } + } + else if (!hashAlg.getAlgorithmName().equals(other.hashAlg.getAlgorithmName())) + { + return false; + } + if (keyGenAlg != other.keyGenAlg) + { + return false; + } + if (Double.doubleToLongBits(keyNormBound) != Double.doubleToLongBits(other.keyNormBound)) + { + return false; + } + if (Double.doubleToLongBits(keyNormBoundSq) != Double.doubleToLongBits(other.keyNormBoundSq)) + { + return false; + } + if (Double.doubleToLongBits(normBound) != Double.doubleToLongBits(other.normBound)) + { + return false; + } + if (Double.doubleToLongBits(normBoundSq) != Double.doubleToLongBits(other.normBoundSq)) + { + return false; + } + if (polyType != other.polyType) + { + return false; + } + if (primeCheck != other.primeCheck) + { + return false; + } + if (q != other.q) + { + return false; + } + if (signFailTolerance != other.signFailTolerance) + { + return false; + } + if (sparse != other.sparse) + { + return false; + } + return true; + } + + public String toString() + { + DecimalFormat format = new DecimalFormat("0.00"); + + StringBuilder output = new StringBuilder("SignatureParameters(N=" + N + " q=" + q); + if (polyType == NTRUParameters.TERNARY_POLYNOMIAL_TYPE_SIMPLE) + { + output.append(" polyType=SIMPLE d=" + d); + } + else + { + output.append(" polyType=PRODUCT d1=" + d1 + " d2=" + d2 + " d3=" + d3); + } + output.append(" B=" + B + " basisType=" + basisType + " beta=" + format.format(beta) + + " normBound=" + format.format(normBound) + " keyNormBound=" + format.format(keyNormBound) + + " prime=" + primeCheck + " sparse=" + sparse + " keyGenAlg=" + keyGenAlg + " hashAlg=" + hashAlg + ")"); + return output.toString(); + } +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningKeyPairGenerator.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningKeyPairGenerator.java new file mode 100644 index 00000000..1471509a --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningKeyPairGenerator.java @@ -0,0 +1,357 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import java.math.BigDecimal; +import java.math.BigInteger; +import java.security.SecureRandom; +import java.util.ArrayList; +import java.util.List; +import java.util.concurrent.Callable; +import java.util.concurrent.ExecutorService; +import java.util.concurrent.Executors; +import java.util.concurrent.Future; + +import org.bouncycastle.crypto.AsymmetricCipherKeyPair; +import org.bouncycastle.crypto.AsymmetricCipherKeyPairGenerator; +import org.bouncycastle.crypto.KeyGenerationParameters; +import org.bouncycastle.pqc.math.ntru.euclid.BigIntEuclidean; +import org.bouncycastle.pqc.math.ntru.polynomial.BigDecimalPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.BigIntPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.Polynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.ProductFormPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.Resultant; + +import static java.math.BigInteger.ONE; +import static java.math.BigInteger.ZERO; + +public class NTRUSigningKeyPairGenerator + implements AsymmetricCipherKeyPairGenerator +{ + private NTRUSigningKeyGenerationParameters params; + + public void init(KeyGenerationParameters param) + { + this.params = (NTRUSigningKeyGenerationParameters)param; + } + + /** + * Generates a new signature key pair. Starts <code>B+1</code> threads. + * + * @return a key pair + */ + public AsymmetricCipherKeyPair generateKeyPair() + { + NTRUSigningPublicKeyParameters pub = null; + ExecutorService executor = Executors.newCachedThreadPool(); + List<Future<NTRUSigningPrivateKeyParameters.Basis>> bases = new ArrayList<Future<NTRUSigningPrivateKeyParameters.Basis>>(); + for (int k = params.B; k >= 0; k--) + { + bases.add(executor.submit(new BasisGenerationTask())); + } + executor.shutdown(); + + List<NTRUSigningPrivateKeyParameters.Basis> basises = new ArrayList<NTRUSigningPrivateKeyParameters.Basis>(); + + for (int k = params.B; k >= 0; k--) + { + Future<NTRUSigningPrivateKeyParameters.Basis> basis = bases.get(k); + try + { + basises.add(basis.get()); + if (k == params.B) + { + pub = new NTRUSigningPublicKeyParameters(basis.get().h, params.getSigningParameters()); + } + } + catch (Exception e) + { + throw new IllegalStateException(e); + } + } + NTRUSigningPrivateKeyParameters priv = new NTRUSigningPrivateKeyParameters(basises, pub); + AsymmetricCipherKeyPair kp = new AsymmetricCipherKeyPair(pub, priv); + return kp; + } + + /** + * Generates a new signature key pair. Runs in a single thread. + * + * @return a key pair + */ + public AsymmetricCipherKeyPair generateKeyPairSingleThread() + { + List<NTRUSigningPrivateKeyParameters.Basis> basises = new ArrayList<NTRUSigningPrivateKeyParameters.Basis>(); + NTRUSigningPublicKeyParameters pub = null; + for (int k = params.B; k >= 0; k--) + { + NTRUSigningPrivateKeyParameters.Basis basis = generateBoundedBasis(); + basises.add(basis); + if (k == 0) + { + pub = new NTRUSigningPublicKeyParameters(basis.h, params.getSigningParameters()); + } + } + NTRUSigningPrivateKeyParameters priv = new NTRUSigningPrivateKeyParameters(basises, pub); + return new AsymmetricCipherKeyPair(pub, priv); + } + + + /** + * Implementation of the optional steps 20 through 26 in EESS1v2.pdf, section 3.5.1.1. + * This doesn't seem to have much of an effect and sometimes actually increases the + * norm of F, but on average it slightly reduces the norm.<br/> + * This method changes <code>F</code> and <code>g</code> but leaves <code>f</code> and + * <code>g</code> unchanged. + * + * @param f + * @param g + * @param F + * @param G + * @param N + */ + private void minimizeFG(IntegerPolynomial f, IntegerPolynomial g, IntegerPolynomial F, IntegerPolynomial G, int N) + { + int E = 0; + for (int j = 0; j < N; j++) + { + E += 2 * N * (f.coeffs[j] * f.coeffs[j] + g.coeffs[j] * g.coeffs[j]); + } + + // [f(1)+g(1)]^2 = 4 + E -= 4; + + IntegerPolynomial u = (IntegerPolynomial)f.clone(); + IntegerPolynomial v = (IntegerPolynomial)g.clone(); + int j = 0; + int k = 0; + int maxAdjustment = N; + while (k < maxAdjustment && j < N) + { + int D = 0; + int i = 0; + while (i < N) + { + int D1 = F.coeffs[i] * f.coeffs[i]; + int D2 = G.coeffs[i] * g.coeffs[i]; + int D3 = 4 * N * (D1 + D2); + D += D3; + i++; + } + // f(1)+g(1) = 2 + int D1 = 4 * (F.sumCoeffs() + G.sumCoeffs()); + D -= D1; + + if (D > E) + { + F.sub(u); + G.sub(v); + k++; + j = 0; + } + else if (D < -E) + { + F.add(u); + G.add(v); + k++; + j = 0; + } + j++; + u.rotate1(); + v.rotate1(); + } + } + + /** + * Creates a NTRUSigner basis consisting of polynomials <code>f, g, F, G, h</code>.<br/> + * If <code>KeyGenAlg=FLOAT</code>, the basis may not be valid and this method must be rerun if that is the case.<br/> + * + * @see #generateBoundedBasis() + */ + private FGBasis generateBasis() + { + int N = params.N; + int q = params.q; + int d = params.d; + int d1 = params.d1; + int d2 = params.d2; + int d3 = params.d3; + int basisType = params.basisType; + + Polynomial f; + IntegerPolynomial fInt; + Polynomial g; + IntegerPolynomial gInt; + IntegerPolynomial fq; + Resultant rf; + Resultant rg; + BigIntEuclidean r; + + int _2n1 = 2 * N + 1; + boolean primeCheck = params.primeCheck; + + do + { + do + { + f = params.polyType== NTRUParameters.TERNARY_POLYNOMIAL_TYPE_SIMPLE ? DenseTernaryPolynomial.generateRandom(N, d + 1, d, new SecureRandom()) : ProductFormPolynomial.generateRandom(N, d1, d2, d3 + 1, d3, new SecureRandom()); + fInt = f.toIntegerPolynomial(); + } + while (primeCheck && fInt.resultant(_2n1).res.equals(ZERO)); + fq = fInt.invertFq(q); + } + while (fq == null); + rf = fInt.resultant(); + + do + { + do + { + do + { + g = params.polyType == NTRUParameters.TERNARY_POLYNOMIAL_TYPE_SIMPLE ? DenseTernaryPolynomial.generateRandom(N, d + 1, d, new SecureRandom()) : ProductFormPolynomial.generateRandom(N, d1, d2, d3 + 1, d3, new SecureRandom()); + gInt = g.toIntegerPolynomial(); + } + while (primeCheck && gInt.resultant(_2n1).res.equals(ZERO)); + } + while (gInt.invertFq(q) == null); + rg = gInt.resultant(); + r = BigIntEuclidean.calculate(rf.res, rg.res); + } + while (!r.gcd.equals(ONE)); + + BigIntPolynomial A = (BigIntPolynomial)rf.rho.clone(); + A.mult(r.x.multiply(BigInteger.valueOf(q))); + BigIntPolynomial B = (BigIntPolynomial)rg.rho.clone(); + B.mult(r.y.multiply(BigInteger.valueOf(-q))); + + BigIntPolynomial C; + if (params.keyGenAlg == NTRUSigningKeyGenerationParameters.KEY_GEN_ALG_RESULTANT) + { + int[] fRevCoeffs = new int[N]; + int[] gRevCoeffs = new int[N]; + fRevCoeffs[0] = fInt.coeffs[0]; + gRevCoeffs[0] = gInt.coeffs[0]; + for (int i = 1; i < N; i++) + { + fRevCoeffs[i] = fInt.coeffs[N - i]; + gRevCoeffs[i] = gInt.coeffs[N - i]; + } + IntegerPolynomial fRev = new IntegerPolynomial(fRevCoeffs); + IntegerPolynomial gRev = new IntegerPolynomial(gRevCoeffs); + + IntegerPolynomial t = f.mult(fRev); + t.add(g.mult(gRev)); + Resultant rt = t.resultant(); + C = fRev.mult(B); // fRev.mult(B) is actually faster than new SparseTernaryPolynomial(fRev).mult(B), possibly due to cache locality? + C.add(gRev.mult(A)); + C = C.mult(rt.rho); + C.div(rt.res); + } + else + { // KeyGenAlg.FLOAT + // calculate ceil(log10(N)) + int log10N = 0; + for (int i = 1; i < N; i *= 10) + { + log10N++; + } + + // * Cdec needs to be accurate to 1 decimal place so it can be correctly rounded; + // * fInv loses up to (#digits of longest coeff of B) places in fInv.mult(B); + // * multiplying fInv by B also multiplies the rounding error by a factor of N; + // so make #decimal places of fInv the sum of the above. + BigDecimalPolynomial fInv = rf.rho.div(new BigDecimal(rf.res), B.getMaxCoeffLength() + 1 + log10N); + BigDecimalPolynomial gInv = rg.rho.div(new BigDecimal(rg.res), A.getMaxCoeffLength() + 1 + log10N); + + BigDecimalPolynomial Cdec = fInv.mult(B); + Cdec.add(gInv.mult(A)); + Cdec.halve(); + C = Cdec.round(); + } + + BigIntPolynomial F = (BigIntPolynomial)B.clone(); + F.sub(f.mult(C)); + BigIntPolynomial G = (BigIntPolynomial)A.clone(); + G.sub(g.mult(C)); + + IntegerPolynomial FInt = new IntegerPolynomial(F); + IntegerPolynomial GInt = new IntegerPolynomial(G); + minimizeFG(fInt, gInt, FInt, GInt, N); + + Polynomial fPrime; + IntegerPolynomial h; + if (basisType == NTRUSigningKeyGenerationParameters.BASIS_TYPE_STANDARD) + { + fPrime = FInt; + h = g.mult(fq, q); + } + else + { + fPrime = g; + h = FInt.mult(fq, q); + } + h.modPositive(q); + + return new FGBasis(f, fPrime, h, FInt, GInt, params); + } + + /** + * Creates a basis such that <code>|F| < keyNormBound</code> and <code>|G| < keyNormBound</code> + * + * @return a NTRUSigner basis + */ + public NTRUSigningPrivateKeyParameters.Basis generateBoundedBasis() + { + while (true) + { + FGBasis basis = generateBasis(); + if (basis.isNormOk()) + { + return basis; + } + } + } + + private class BasisGenerationTask + implements Callable<NTRUSigningPrivateKeyParameters.Basis> + { + + + public NTRUSigningPrivateKeyParameters.Basis call() + throws Exception + { + return generateBoundedBasis(); + } + } + + /** + * A subclass of Basis that additionally contains the polynomials <code>F</code> and <code>G</code>. + */ + public class FGBasis + extends NTRUSigningPrivateKeyParameters.Basis + { + public IntegerPolynomial F; + public IntegerPolynomial G; + + FGBasis(Polynomial f, Polynomial fPrime, IntegerPolynomial h, IntegerPolynomial F, IntegerPolynomial G, NTRUSigningKeyGenerationParameters params) + { + super(f, fPrime, h, params); + this.F = F; + this.G = G; + } + + /** + * Returns <code>true</code> if the norms of the polynomials <code>F</code> and <code>G</code> + * are within {@link NTRUSigningKeyGenerationParameters#keyNormBound}. + * + * @return + */ + boolean isNormOk() + { + double keyNormBoundSq = params.keyNormBoundSq; + int q = params.q; + return (F.centeredNormSq(q) < keyNormBoundSq && G.centeredNormSq(q) < keyNormBoundSq); + } + } +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningParameters.java new file mode 100644 index 00000000..bf70cafb --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningParameters.java @@ -0,0 +1,269 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; +import java.text.DecimalFormat; + +import org.bouncycastle.crypto.Digest; +import org.bouncycastle.crypto.digests.SHA256Digest; +import org.bouncycastle.crypto.digests.SHA512Digest; + +/** + * A set of parameters for NtruSign. Several predefined parameter sets are available and new ones can be created as well. + */ +public class NTRUSigningParameters + implements Cloneable +{ + public int N; + public int q; + public int d, d1, d2, d3, B; + double beta; + public double betaSq; + double normBound; + public double normBoundSq; + public int signFailTolerance = 100; + int bitsF = 6; // max #bits needed to encode one coefficient of the polynomial F + public Digest hashAlg; + + /** + * Constructs a parameter set that uses ternary private keys (i.e. </code>polyType=SIMPLE</code>). + * + * @param N number of polynomial coefficients + * @param q modulus + * @param d number of -1's in the private polynomials <code>f</code> and <code>g</code> + * @param B number of perturbations + * @param beta balancing factor for the transpose lattice + * @param normBound maximum norm for valid signatures + * @param hashAlg a valid identifier for a <code>java.security.MessageDigest</code> instance such as <code>SHA-256</code>. The <code>MessageDigest</code> must support the <code>getDigestLength()</code> method. + */ + public NTRUSigningParameters(int N, int q, int d, int B, double beta, double normBound, Digest hashAlg) + { + this.N = N; + this.q = q; + this.d = d; + this.B = B; + this.beta = beta; + this.normBound = normBound; + this.hashAlg = hashAlg; + init(); + } + + /** + * Constructs a parameter set that uses product-form private keys (i.e. </code>polyType=PRODUCT</code>). + * + * @param N number of polynomial coefficients + * @param q modulus + * @param d1 number of -1's in the private polynomials <code>f</code> and <code>g</code> + * @param d2 number of -1's in the private polynomials <code>f</code> and <code>g</code> + * @param d3 number of -1's in the private polynomials <code>f</code> and <code>g</code> + * @param B number of perturbations + * @param beta balancing factor for the transpose lattice + * @param normBound maximum norm for valid signatures + * @param keyNormBound maximum norm for the ploynomials <code>F</code> and <code>G</code> + * @param hashAlg a valid identifier for a <code>java.security.MessageDigest</code> instance such as <code>SHA-256</code>. The <code>MessageDigest</code> must support the <code>getDigestLength()</code> method. + */ + public NTRUSigningParameters(int N, int q, int d1, int d2, int d3, int B, double beta, double normBound, double keyNormBound, Digest hashAlg) + { + this.N = N; + this.q = q; + this.d1 = d1; + this.d2 = d2; + this.d3 = d3; + this.B = B; + this.beta = beta; + this.normBound = normBound; + this.hashAlg = hashAlg; + init(); + } + + private void init() + { + betaSq = beta * beta; + normBoundSq = normBound * normBound; + } + + /** + * Reads a parameter set from an input stream. + * + * @param is an input stream + * @throws IOException + */ + public NTRUSigningParameters(InputStream is) + throws IOException + { + DataInputStream dis = new DataInputStream(is); + N = dis.readInt(); + q = dis.readInt(); + d = dis.readInt(); + d1 = dis.readInt(); + d2 = dis.readInt(); + d3 = dis.readInt(); + B = dis.readInt(); + beta = dis.readDouble(); + normBound = dis.readDouble(); + signFailTolerance = dis.readInt(); + bitsF = dis.readInt(); + String alg = dis.readUTF(); + if ("SHA-512".equals(alg)) + { + hashAlg = new SHA512Digest(); + } + else if ("SHA-256".equals(alg)) + { + hashAlg = new SHA256Digest(); + } + init(); + } + + /** + * Writes the parameter set to an output stream + * + * @param os an output stream + * @throws IOException + */ + public void writeTo(OutputStream os) + throws IOException + { + DataOutputStream dos = new DataOutputStream(os); + dos.writeInt(N); + dos.writeInt(q); + dos.writeInt(d); + dos.writeInt(d1); + dos.writeInt(d2); + dos.writeInt(d3); + dos.writeInt(B); + dos.writeDouble(beta); + dos.writeDouble(normBound); + dos.writeInt(signFailTolerance); + dos.writeInt(bitsF); + dos.writeUTF(hashAlg.getAlgorithmName()); + } + + public NTRUSigningParameters clone() + { + return new NTRUSigningParameters(N, q, d, B, beta, normBound, hashAlg); + } + + public int hashCode() + { + final int prime = 31; + int result = 1; + result = prime * result + B; + result = prime * result + N; + long temp; + temp = Double.doubleToLongBits(beta); + result = prime * result + (int)(temp ^ (temp >>> 32)); + temp = Double.doubleToLongBits(betaSq); + result = prime * result + (int)(temp ^ (temp >>> 32)); + result = prime * result + bitsF; + result = prime * result + d; + result = prime * result + d1; + result = prime * result + d2; + result = prime * result + d3; + result = prime * result + ((hashAlg == null) ? 0 : hashAlg.getAlgorithmName().hashCode()); + temp = Double.doubleToLongBits(normBound); + result = prime * result + (int)(temp ^ (temp >>> 32)); + temp = Double.doubleToLongBits(normBoundSq); + result = prime * result + (int)(temp ^ (temp >>> 32)); + result = prime * result + q; + result = prime * result + signFailTolerance; + return result; + } + + public boolean equals(Object obj) + { + if (this == obj) + { + return true; + } + if (obj == null) + { + return false; + } + if (!(obj instanceof NTRUSigningParameters)) + { + return false; + } + NTRUSigningParameters other = (NTRUSigningParameters)obj; + if (B != other.B) + { + return false; + } + if (N != other.N) + { + return false; + } + if (Double.doubleToLongBits(beta) != Double.doubleToLongBits(other.beta)) + { + return false; + } + if (Double.doubleToLongBits(betaSq) != Double.doubleToLongBits(other.betaSq)) + { + return false; + } + if (bitsF != other.bitsF) + { + return false; + } + if (d != other.d) + { + return false; + } + if (d1 != other.d1) + { + return false; + } + if (d2 != other.d2) + { + return false; + } + if (d3 != other.d3) + { + return false; + } + if (hashAlg == null) + { + if (other.hashAlg != null) + { + return false; + } + } + else if (!hashAlg.getAlgorithmName().equals(other.hashAlg.getAlgorithmName())) + { + return false; + } + if (Double.doubleToLongBits(normBound) != Double.doubleToLongBits(other.normBound)) + { + return false; + } + if (Double.doubleToLongBits(normBoundSq) != Double.doubleToLongBits(other.normBoundSq)) + { + return false; + } + if (q != other.q) + { + return false; + } + if (signFailTolerance != other.signFailTolerance) + { + return false; + } + + return true; + } + + public String toString() + { + DecimalFormat format = new DecimalFormat("0.00"); + + StringBuilder output = new StringBuilder("SignatureParameters(N=" + N + " q=" + q); + + output.append(" B=" + B + " beta=" + format.format(beta) + + " normBound=" + format.format(normBound) + + " hashAlg=" + hashAlg + ")"); + return output.toString(); + } +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningPrivateKeyParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningPrivateKeyParameters.java new file mode 100644 index 00000000..515f3562 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningPrivateKeyParameters.java @@ -0,0 +1,385 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import java.io.ByteArrayInputStream; +import java.io.ByteArrayOutputStream; +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; +import java.util.ArrayList; +import java.util.List; + +import org.bouncycastle.crypto.params.AsymmetricKeyParameter; +import org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.Polynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.ProductFormPolynomial; +import org.bouncycastle.pqc.math.ntru.polynomial.SparseTernaryPolynomial; + +/** + * A NtruSign private key comprises one or more {@link NTRUSigningPrivateKeyParameters.Basis} of three polynomials each, + * except the zeroth basis for which <code>h</code> is undefined. + */ +public class NTRUSigningPrivateKeyParameters + extends AsymmetricKeyParameter +{ + private List<Basis> bases; + private NTRUSigningPublicKeyParameters publicKey; + + /** + * Constructs a new private key from a byte array + * + * @param b an encoded private key + * @param params the NtruSign parameters to use + */ + public NTRUSigningPrivateKeyParameters(byte[] b, NTRUSigningKeyGenerationParameters params) + throws IOException + { + this(new ByteArrayInputStream(b), params); + } + + /** + * Constructs a new private key from an input stream + * + * @param is an input stream + * @param params the NtruSign parameters to use + */ + public NTRUSigningPrivateKeyParameters(InputStream is, NTRUSigningKeyGenerationParameters params) + throws IOException + { + super(true); + bases = new ArrayList<Basis>(); + for (int i = 0; i <= params.B; i++) + // include a public key h[i] in all bases except for the first one + { + add(new Basis(is, params, i != 0)); + } + publicKey = new NTRUSigningPublicKeyParameters(is, params.getSigningParameters()); + } + + public NTRUSigningPrivateKeyParameters(List<Basis> bases, NTRUSigningPublicKeyParameters publicKey) + { + super(true); + this.bases = new ArrayList<Basis>(bases); + this.publicKey = publicKey; + } + + /** + * Adds a basis to the key. + * + * @param b a NtruSign basis + */ + private void add(Basis b) + { + bases.add(b); + } + + /** + * Returns the <code>i</code>-th basis + * + * @param i the index + * @return the basis at index <code>i</code> + */ + public Basis getBasis(int i) + { + return bases.get(i); + } + + public NTRUSigningPublicKeyParameters getPublicKey() + { + return publicKey; + } + + /** + * Converts the key to a byte array + * + * @return the encoded key + */ + public byte[] getEncoded() + throws IOException + { + ByteArrayOutputStream os = new ByteArrayOutputStream(); + for (int i = 0; i < bases.size(); i++) + { + // all bases except for the first one contain a public key + bases.get(i).encode(os, i != 0); + } + + os.write(publicKey.getEncoded()); + + return os.toByteArray(); + } + + /** + * Writes the key to an output stream + * + * @param os an output stream + * @throws IOException + */ + public void writeTo(OutputStream os) + throws IOException + { + os.write(getEncoded()); + } + + @Override + public int hashCode() + { + final int prime = 31; + int result = 1; + result = prime * result + ((bases == null) ? 0 : bases.hashCode()); + for (Basis basis : bases) + { + result += basis.hashCode(); + } + return result; + } + + @Override + public boolean equals(Object obj) + { + if (this == obj) + { + return true; + } + if (obj == null) + { + return false; + } + if (getClass() != obj.getClass()) + { + return false; + } + NTRUSigningPrivateKeyParameters other = (NTRUSigningPrivateKeyParameters)obj; + if (bases == null) + { + if (other.bases != null) + { + return false; + } + } + if (bases.size() != other.bases.size()) + { + return false; + } + for (int i = 0; i < bases.size(); i++) + { + Basis basis1 = bases.get(i); + Basis basis2 = other.bases.get(i); + if (!basis1.f.equals(basis2.f)) + { + return false; + } + if (!basis1.fPrime.equals(basis2.fPrime)) + { + return false; + } + if (i != 0 && !basis1.h.equals(basis2.h)) // don't compare h for the 0th basis + { + return false; + } + if (!basis1.params.equals(basis2.params)) + { + return false; + } + } + return true; + } + + /** + * A NtruSign basis. Contains three polynomials <code>f, f', h</code>. + */ + public static class Basis + { + public Polynomial f; + public Polynomial fPrime; + public IntegerPolynomial h; + NTRUSigningKeyGenerationParameters params; + + /** + * Constructs a new basis from polynomials <code>f, f', h</code>. + * + * @param f + * @param fPrime + * @param h + * @param params NtruSign parameters + */ + protected Basis(Polynomial f, Polynomial fPrime, IntegerPolynomial h, NTRUSigningKeyGenerationParameters params) + { + this.f = f; + this.fPrime = fPrime; + this.h = h; + this.params = params; + } + + /** + * Reads a basis from an input stream and constructs a new basis. + * + * @param is an input stream + * @param params NtruSign parameters + * @param include_h whether to read the polynomial <code>h</code> (<code>true</code>) or only <code>f</code> and <code>f'</code> (<code>false</code>) + */ + Basis(InputStream is, NTRUSigningKeyGenerationParameters params, boolean include_h) + throws IOException + { + int N = params.N; + int q = params.q; + int d1 = params.d1; + int d2 = params.d2; + int d3 = params.d3; + boolean sparse = params.sparse; + this.params = params; + + if (params.polyType == NTRUParameters.TERNARY_POLYNOMIAL_TYPE_PRODUCT) + { + f = ProductFormPolynomial.fromBinary(is, N, d1, d2, d3 + 1, d3); + } + else + { + IntegerPolynomial fInt = IntegerPolynomial.fromBinary3Tight(is, N); + f = sparse ? new SparseTernaryPolynomial(fInt) : new DenseTernaryPolynomial(fInt); + } + + if (params.basisType == NTRUSigningKeyGenerationParameters.BASIS_TYPE_STANDARD) + { + IntegerPolynomial fPrimeInt = IntegerPolynomial.fromBinary(is, N, q); + for (int i = 0; i < fPrimeInt.coeffs.length; i++) + { + fPrimeInt.coeffs[i] -= q / 2; + } + fPrime = fPrimeInt; + } + else if (params.polyType == NTRUParameters.TERNARY_POLYNOMIAL_TYPE_PRODUCT) + { + fPrime = ProductFormPolynomial.fromBinary(is, N, d1, d2, d3 + 1, d3); + } + else + { + fPrime = IntegerPolynomial.fromBinary3Tight(is, N); + } + + if (include_h) + { + h = IntegerPolynomial.fromBinary(is, N, q); + } + } + + /** + * Writes the basis to an output stream + * + * @param os an output stream + * @param include_h whether to write the polynomial <code>h</code> (<code>true</code>) or only <code>f</code> and <code>f'</code> (<code>false</code>) + * @throws IOException + */ + void encode(OutputStream os, boolean include_h) + throws IOException + { + int q = params.q; + + os.write(getEncoded(f)); + if (params.basisType == NTRUSigningKeyGenerationParameters.BASIS_TYPE_STANDARD) + { + IntegerPolynomial fPrimeInt = fPrime.toIntegerPolynomial(); + for (int i = 0; i < fPrimeInt.coeffs.length; i++) + { + fPrimeInt.coeffs[i] += q / 2; + } + os.write(fPrimeInt.toBinary(q)); + } + else + { + os.write(getEncoded(fPrime)); + } + if (include_h) + { + os.write(h.toBinary(q)); + } + } + + private byte[] getEncoded(Polynomial p) + { + if (p instanceof ProductFormPolynomial) + { + return ((ProductFormPolynomial)p).toBinary(); + } + else + { + return p.toIntegerPolynomial().toBinary3Tight(); + } + } + + @Override + public int hashCode() + { + final int prime = 31; + int result = 1; + result = prime * result + ((f == null) ? 0 : f.hashCode()); + result = prime * result + ((fPrime == null) ? 0 : fPrime.hashCode()); + result = prime * result + ((h == null) ? 0 : h.hashCode()); + result = prime * result + ((params == null) ? 0 : params.hashCode()); + return result; + } + + @Override + public boolean equals(Object obj) + { + if (this == obj) + { + return true; + } + if (obj == null) + { + return false; + } + if (!(obj instanceof Basis)) + { + return false; + } + Basis other = (Basis)obj; + if (f == null) + { + if (other.f != null) + { + return false; + } + } + else if (!f.equals(other.f)) + { + return false; + } + if (fPrime == null) + { + if (other.fPrime != null) + { + return false; + } + } + else if (!fPrime.equals(other.fPrime)) + { + return false; + } + if (h == null) + { + if (other.h != null) + { + return false; + } + } + else if (!h.equals(other.h)) + { + return false; + } + if (params == null) + { + if (other.params != null) + { + return false; + } + } + else if (!params.equals(other.params)) + { + return false; + } + return true; + } + } +}
\ No newline at end of file diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningPublicKeyParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningPublicKeyParameters.java new file mode 100644 index 00000000..be51d0af --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/ntru/NTRUSigningPublicKeyParameters.java @@ -0,0 +1,132 @@ +package org.bouncycastle.pqc.crypto.ntru; + +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; + +import org.bouncycastle.crypto.params.AsymmetricKeyParameter; +import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; + +/** + * A NtruSign public key is essentially a polynomial named <code>h</code>. + */ +public class NTRUSigningPublicKeyParameters + extends AsymmetricKeyParameter +{ + private NTRUSigningParameters params; + public IntegerPolynomial h; + + /** + * Constructs a new public key from a polynomial + * + * @param h the polynomial <code>h</code> which determines the key + * @param params the NtruSign parameters to use + */ + public NTRUSigningPublicKeyParameters(IntegerPolynomial h, NTRUSigningParameters params) + { + super(false); + this.h = h; + this.params = params; + } + + /** + * Converts a byte array to a polynomial <code>h</code> and constructs a new public key + * + * @param b an encoded polynomial + * @param params the NtruSign parameters to use + */ + public NTRUSigningPublicKeyParameters(byte[] b, NTRUSigningParameters params) + { + super(false); + h = IntegerPolynomial.fromBinary(b, params.N, params.q); + this.params = params; + } + + /** + * Reads a polynomial <code>h</code> from an input stream and constructs a new public key + * + * @param is an input stream + * @param params the NtruSign parameters to use + */ + public NTRUSigningPublicKeyParameters(InputStream is, NTRUSigningParameters params) + throws IOException + { + super(false); + h = IntegerPolynomial.fromBinary(is, params.N, params.q); + this.params = params; + } + + + /** + * Converts the key to a byte array + * + * @return the encoded key + */ + public byte[] getEncoded() + { + return h.toBinary(params.q); + } + + /** + * Writes the key to an output stream + * + * @param os an output stream + * @throws IOException + */ + public void writeTo(OutputStream os) + throws IOException + { + os.write(getEncoded()); + } + + @Override + public int hashCode() + { + final int prime = 31; + int result = 1; + result = prime * result + ((h == null) ? 0 : h.hashCode()); + result = prime * result + ((params == null) ? 0 : params.hashCode()); + return result; + } + + @Override + public boolean equals(Object obj) + { + if (this == obj) + { + return true; + } + if (obj == null) + { + return false; + } + if (getClass() != obj.getClass()) + { + return false; + } + NTRUSigningPublicKeyParameters other = (NTRUSigningPublicKeyParameters)obj; + if (h == null) + { + if (other.h != null) + { + return false; + } + } + else if (!h.equals(other.h)) + { + return false; + } + if (params == null) + { + if (other.params != null) + { + return false; + } + } + else if (!params.equals(other.params)) + { + return false; + } + return true; + } +}
\ No newline at end of file |