diff options
Diffstat (limited to 'core/src/main/java/org/bouncycastle/pqc/crypto/rainbow')
11 files changed, 2228 insertions, 0 deletions
diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/Layer.java b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/Layer.java new file mode 100644 index 00000000..4c457ec5 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/Layer.java @@ -0,0 +1,322 @@ +package org.bouncycastle.pqc.crypto.rainbow; + +import java.security.SecureRandom; + +import org.bouncycastle.pqc.crypto.rainbow.util.GF2Field; +import org.bouncycastle.pqc.crypto.rainbow.util.RainbowUtil; +import org.bouncycastle.util.Arrays; + + +/** + * This class represents a layer of the Rainbow Oil- and Vinegar Map. Each Layer + * consists of oi polynomials with their coefficients, generated at random. + * <p/> + * To sign a document, we solve a LES (linear equation system) for each layer in + * order to find the oil variables of that layer and to be able to use the + * variables to compute the signature. This functionality is implemented in the + * RainbowSignature-class, by the aid of the private key. + * <p/> + * Each layer is a part of the private key. + * <p/> + * More information about the layer can be found in the paper of Jintai Ding, + * Dieter Schmidt: Rainbow, a New Multivariable Polynomial Signature Scheme. + * ACNS 2005: 164-175 (http://dx.doi.org/10.1007/11496137_12) + */ +public class Layer +{ + private int vi; // number of vinegars in this layer + private int viNext; // number of vinegars in next layer + private int oi; // number of oils in this layer + + /* + * k : index of polynomial + * + * i,j : indices of oil and vinegar variables + */ + private short[/* k */][/* i */][/* j */] coeff_alpha; + private short[/* k */][/* i */][/* j */] coeff_beta; + private short[/* k */][/* i */] coeff_gamma; + private short[/* k */] coeff_eta; + + /** + * Constructor + * + * @param vi number of vinegar variables of this layer + * @param viNext number of vinegar variables of next layer. It's the same as + * (num of oils) + (num of vinegars) of this layer. + * @param coeffAlpha alpha-coefficients in the polynomials of this layer + * @param coeffBeta beta-coefficients in the polynomials of this layer + * @param coeffGamma gamma-coefficients in the polynomials of this layer + * @param coeffEta eta-coefficients in the polynomials of this layer + */ + public Layer(byte vi, byte viNext, short[][][] coeffAlpha, + short[][][] coeffBeta, short[][] coeffGamma, short[] coeffEta) + { + this.vi = vi & 0xff; + this.viNext = viNext & 0xff; + this.oi = this.viNext - this.vi; + + // the secret coefficients of all polynomials in this layer + this.coeff_alpha = coeffAlpha; + this.coeff_beta = coeffBeta; + this.coeff_gamma = coeffGamma; + this.coeff_eta = coeffEta; + } + + /** + * This function generates the coefficients of all polynomials in this layer + * at random using random generator. + * + * @param sr the random generator which is to be used + */ + public Layer(int vi, int viNext, SecureRandom sr) + { + this.vi = vi; + this.viNext = viNext; + this.oi = viNext - vi; + + // the coefficients of all polynomials in this layer + this.coeff_alpha = new short[this.oi][this.oi][this.vi]; + this.coeff_beta = new short[this.oi][this.vi][this.vi]; + this.coeff_gamma = new short[this.oi][this.viNext]; + this.coeff_eta = new short[this.oi]; + + int numOfPoly = this.oi; // number of polynomials per layer + + // Alpha coeffs + for (int k = 0; k < numOfPoly; k++) + { + for (int i = 0; i < this.oi; i++) + { + for (int j = 0; j < this.vi; j++) + { + coeff_alpha[k][i][j] = (short)(sr.nextInt() & GF2Field.MASK); + } + } + } + // Beta coeffs + for (int k = 0; k < numOfPoly; k++) + { + for (int i = 0; i < this.vi; i++) + { + for (int j = 0; j < this.vi; j++) + { + coeff_beta[k][i][j] = (short)(sr.nextInt() & GF2Field.MASK); + } + } + } + // Gamma coeffs + for (int k = 0; k < numOfPoly; k++) + { + for (int i = 0; i < this.viNext; i++) + { + coeff_gamma[k][i] = (short)(sr.nextInt() & GF2Field.MASK); + } + } + // Eta + for (int k = 0; k < numOfPoly; k++) + { + coeff_eta[k] = (short)(sr.nextInt() & GF2Field.MASK); + } + } + + /** + * This method plugs in the vinegar variables into the polynomials of this + * layer and computes the coefficients of the Oil-variables as well as the + * free coefficient in each polynomial. + * <p/> + * It is needed for computing the Oil variables while signing. + * + * @param x vinegar variables of this layer that should be plugged into + * the polynomials. + * @return coeff the coefficients of Oil variables and the free coeff in the + * polynomials of this layer. + */ + public short[][] plugInVinegars(short[] x) + { + // temporary variable needed for the multiplication + short tmpMult = 0; + // coeff: 1st index = which polynomial, 2nd index=which variable + short[][] coeff = new short[oi][oi + 1]; // gets returned + // free coefficient per polynomial + short[] sum = new short[oi]; + + /* + * evaluate the beta-part of the polynomials (it contains no oil + * variables) + */ + for (int k = 0; k < oi; k++) + { + for (int i = 0; i < vi; i++) + { + for (int j = 0; j < vi; j++) + { + // tmp = beta * xi (plug in) + tmpMult = GF2Field.multElem(coeff_beta[k][i][j], x[i]); + // tmp = tmp * xj + tmpMult = GF2Field.multElem(tmpMult, x[j]); + // accumulate into the array for the free coefficients. + sum[k] = GF2Field.addElem(sum[k], tmpMult); + } + } + } + + /* evaluate the alpha-part (it contains oils) */ + for (int k = 0; k < oi; k++) + { + for (int i = 0; i < oi; i++) + { + for (int j = 0; j < vi; j++) + { + // alpha * xj (plug in) + tmpMult = GF2Field.multElem(coeff_alpha[k][i][j], x[j]); + // accumulate + coeff[k][i] = GF2Field.addElem(coeff[k][i], tmpMult); + } + } + } + /* evaluate the gama-part of the polynomial (containing no oils) */ + for (int k = 0; k < oi; k++) + { + for (int i = 0; i < vi; i++) + { + // gamma * xi (plug in) + tmpMult = GF2Field.multElem(coeff_gamma[k][i], x[i]); + // accumulate in the array for the free coefficients (per + // polynomial). + sum[k] = GF2Field.addElem(sum[k], tmpMult); + } + } + /* evaluate the gama-part of the polynomial (but containing oils) */ + for (int k = 0; k < oi; k++) + { + for (int i = vi; i < viNext; i++) + { // oils + // accumulate the coefficients of the oil variables (per + // polynomial). + coeff[k][i - vi] = GF2Field.addElem(coeff_gamma[k][i], + coeff[k][i - vi]); + } + } + /* evaluate the eta-part of the polynomial */ + for (int k = 0; k < oi; k++) + { + // accumulate in the array for the free coefficients per polynomial. + sum[k] = GF2Field.addElem(sum[k], coeff_eta[k]); + } + + /* put the free coefficients (sum) into the coeff-array as last column */ + for (int k = 0; k < oi; k++) + { + coeff[k][oi] = sum[k]; + } + return coeff; + } + + /** + * Getter for the number of vinegar variables of this layer. + * + * @return the number of vinegar variables of this layer. + */ + public int getVi() + { + return vi; + } + + /** + * Getter for the number of vinegar variables of the next layer. + * + * @return the number of vinegar variables of the next layer. + */ + public int getViNext() + { + return viNext; + } + + /** + * Getter for the number of Oil variables of this layer. + * + * @return the number of oil variables of this layer. + */ + public int getOi() + { + return oi; + } + + /** + * Getter for the alpha-coefficients of the polynomials in this layer. + * + * @return the coefficients of alpha-terms of this layer. + */ + public short[][][] getCoeffAlpha() + { + return coeff_alpha; + } + + /** + * Getter for the beta-coefficients of the polynomials in this layer. + * + * @return the coefficients of beta-terms of this layer. + */ + + public short[][][] getCoeffBeta() + { + return coeff_beta; + } + + /** + * Getter for the gamma-coefficients of the polynomials in this layer. + * + * @return the coefficients of gamma-terms of this layer + */ + public short[][] getCoeffGamma() + { + return coeff_gamma; + } + + /** + * Getter for the eta-coefficients of the polynomials in this layer. + * + * @return the coefficients eta of this layer + */ + public short[] getCoeffEta() + { + return coeff_eta; + } + + /** + * This function compares this Layer with another object. + * + * @param other the other object + * @return the result of the comparison + */ + public boolean equals(Object other) + { + if (other == null || !(other instanceof Layer)) + { + return false; + } + Layer otherLayer = (Layer)other; + + return vi == otherLayer.getVi() + && viNext == otherLayer.getViNext() + && oi == otherLayer.getOi() + && RainbowUtil.equals(coeff_alpha, otherLayer.getCoeffAlpha()) + && RainbowUtil.equals(coeff_beta, otherLayer.getCoeffBeta()) + && RainbowUtil.equals(coeff_gamma, otherLayer.getCoeffGamma()) + && RainbowUtil.equals(coeff_eta, otherLayer.getCoeffEta()); + } + + public int hashCode() + { + int hash = vi; + hash = hash * 37 + viNext; + hash = hash * 37 + oi; + hash = hash * 37 + Arrays.hashCode(coeff_alpha); + hash = hash * 37 + Arrays.hashCode(coeff_beta); + hash = hash * 37 + Arrays.hashCode(coeff_gamma); + hash = hash * 37 + Arrays.hashCode(coeff_eta); + + return hash; + } +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowKeyGenerationParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowKeyGenerationParameters.java new file mode 100644 index 00000000..b634f9cc --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowKeyGenerationParameters.java @@ -0,0 +1,26 @@ +package org.bouncycastle.pqc.crypto.rainbow; + +import java.security.SecureRandom; + +import org.bouncycastle.crypto.KeyGenerationParameters; + +public class RainbowKeyGenerationParameters + extends KeyGenerationParameters +{ + private RainbowParameters params; + + public RainbowKeyGenerationParameters( + SecureRandom random, + RainbowParameters params) + { + // TODO: key size? + super(random, params.getVi()[params.getVi().length - 1] - params.getVi()[0]); + this.params = params; + } + + public RainbowParameters getParameters() + { + return params; + } +} + diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowKeyPairGenerator.java b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowKeyPairGenerator.java new file mode 100644 index 00000000..e7fe0593 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowKeyPairGenerator.java @@ -0,0 +1,414 @@ +package org.bouncycastle.pqc.crypto.rainbow; + +import java.security.SecureRandom; + +import org.bouncycastle.crypto.AsymmetricCipherKeyPair; +import org.bouncycastle.crypto.AsymmetricCipherKeyPairGenerator; +import org.bouncycastle.crypto.KeyGenerationParameters; +import org.bouncycastle.pqc.crypto.rainbow.util.ComputeInField; +import org.bouncycastle.pqc.crypto.rainbow.util.GF2Field; + +/** + * This class implements AsymmetricCipherKeyPairGenerator. It is used + * as a generator for the private and public key of the Rainbow Signature + * Scheme. + * <p/> + * Detailed information about the key generation is to be found in the paper of + * Jintai Ding, Dieter Schmidt: Rainbow, a New Multivariable Polynomial + * Signature Scheme. ACNS 2005: 164-175 (http://dx.doi.org/10.1007/11496137_12) + */ +public class RainbowKeyPairGenerator + implements AsymmetricCipherKeyPairGenerator +{ + private boolean initialized = false; + private SecureRandom sr; + private RainbowKeyGenerationParameters rainbowParams; + + /* linear affine map L1: */ + private short[][] A1; // matrix of the lin. affine map L1(n-v1 x n-v1 matrix) + private short[][] A1inv; // inverted A1 + private short[] b1; // translation element of the lin.affine map L1 + + /* linear affine map L2: */ + private short[][] A2; // matrix of the lin. affine map (n x n matrix) + private short[][] A2inv; // inverted A2 + private short[] b2; // translation elemt of the lin.affine map L2 + + /* components of F: */ + private int numOfLayers; // u (number of sets S) + private Layer layers[]; // layers of polynomials of F + private int[] vi; // set of vinegar vars per layer. + + /* components of Public Key */ + private short[][] pub_quadratic; // quadratic(mixed) coefficients + private short[][] pub_singular; // singular coefficients + private short[] pub_scalar; // scalars + + // TODO + + /** + * The standard constructor tries to generate the Rainbow algorithm identifier + * with the corresponding OID. + * <p/> + */ + public RainbowKeyPairGenerator() + { + } + + + /** + * This function generates a Rainbow key pair. + * + * @return the generated key pair + */ + public AsymmetricCipherKeyPair genKeyPair() + { + RainbowPrivateKeyParameters privKey; + RainbowPublicKeyParameters pubKey; + + if (!initialized) + { + initializeDefault(); + } + + /* choose all coefficients at random */ + keygen(); + + /* now marshall them to PrivateKey */ + privKey = new RainbowPrivateKeyParameters(A1inv, b1, A2inv, b2, vi, layers); + + + /* marshall to PublicKey */ + pubKey = new RainbowPublicKeyParameters(vi[vi.length - 1] - vi[0], pub_quadratic, pub_singular, pub_scalar); + + return new AsymmetricCipherKeyPair(pubKey, privKey); + } + + // TODO + public void initialize( + KeyGenerationParameters param) + { + this.rainbowParams = (RainbowKeyGenerationParameters)param; + + // set source of randomness + this.sr = new SecureRandom(); + + // unmarshalling: + this.vi = this.rainbowParams.getParameters().getVi(); + this.numOfLayers = this.rainbowParams.getParameters().getNumOfLayers(); + + this.initialized = true; + } + + private void initializeDefault() + { + RainbowKeyGenerationParameters rbKGParams = new RainbowKeyGenerationParameters(new SecureRandom(), new RainbowParameters()); + initialize(rbKGParams); + } + + /** + * This function calls the functions for the random generation of the coefficients + * and the matrices needed for the private key and the method for computing the public key. + */ + private void keygen() + { + generateL1(); + generateL2(); + generateF(); + computePublicKey(); + } + + /** + * This function generates the invertible affine linear map L1 = A1*x + b1 + * <p/> + * The translation part b1, is stored in a separate array. The inverse of + * the matrix-part of L1 A1inv is also computed here. + * <p/> + * This linear map hides the output of the map F. It is on k^(n-v1). + */ + private void generateL1() + { + + // dimension = n-v1 = vi[last] - vi[first] + int dim = vi[vi.length - 1] - vi[0]; + this.A1 = new short[dim][dim]; + this.A1inv = null; + ComputeInField c = new ComputeInField(); + + /* generation of A1 at random */ + while (A1inv == null) + { + for (int i = 0; i < dim; i++) + { + for (int j = 0; j < dim; j++) + { + A1[i][j] = (short)(sr.nextInt() & GF2Field.MASK); + } + } + A1inv = c.inverse(A1); + } + + /* generation of the translation vector at random */ + b1 = new short[dim]; + for (int i = 0; i < dim; i++) + { + b1[i] = (short)(sr.nextInt() & GF2Field.MASK); + } + } + + /** + * This function generates the invertible affine linear map L2 = A2*x + b2 + * <p/> + * The translation part b2, is stored in a separate array. The inverse of + * the matrix-part of L2 A2inv is also computed here. + * <p/> + * This linear map hides the output of the map F. It is on k^(n). + */ + private void generateL2() + { + + // dimension = n = vi[last] + int dim = vi[vi.length - 1]; + this.A2 = new short[dim][dim]; + this.A2inv = null; + ComputeInField c = new ComputeInField(); + + /* generation of A2 at random */ + while (this.A2inv == null) + { + for (int i = 0; i < dim; i++) + { + for (int j = 0; j < dim; j++) + { // one col extra for b + A2[i][j] = (short)(sr.nextInt() & GF2Field.MASK); + } + } + this.A2inv = c.inverse(A2); + } + /* generation of the translation vector at random */ + b2 = new short[dim]; + for (int i = 0; i < dim; i++) + { + b2[i] = (short)(sr.nextInt() & GF2Field.MASK); + } + + } + + /** + * This function generates the private map F, which consists of u-1 layers. + * Each layer consists of oi polynomials where oi = vi[i+1]-vi[i]. + * <p/> + * The methods for the generation of the coefficients of these polynomials + * are called here. + */ + private void generateF() + { + + this.layers = new Layer[this.numOfLayers]; + for (int i = 0; i < this.numOfLayers; i++) + { + layers[i] = new Layer(this.vi[i], this.vi[i + 1], sr); + } + } + + /** + * This function computes the public key from the private key. + * <p/> + * The composition of F with L2 is computed, followed by applying L1 to the + * composition's result. The singular and scalar values constitute to the + * public key as is, the quadratic terms are compacted in + * <tt>compactPublicKey()</tt> + */ + private void computePublicKey() + { + + ComputeInField c = new ComputeInField(); + int rows = this.vi[this.vi.length - 1] - this.vi[0]; + int vars = this.vi[this.vi.length - 1]; + // Fpub + short[][][] coeff_quadratic_3dim = new short[rows][vars][vars]; + this.pub_singular = new short[rows][vars]; + this.pub_scalar = new short[rows]; + + // Coefficients of layers of Private Key F + short[][][] coeff_alpha; + short[][][] coeff_beta; + short[][] coeff_gamma; + short[] coeff_eta; + + // Needed for counters; + int oils = 0; + int vins = 0; + int crnt_row = 0; // current row (polynomial) + + short vect_tmp[] = new short[vars]; // vector tmp; + short sclr_tmp = 0; + + // Composition of F and L2: Insert L2 = A2*x+b2 in F + for (int l = 0; l < this.layers.length; l++) + { + // get coefficients of current layer + coeff_alpha = this.layers[l].getCoeffAlpha(); + coeff_beta = this.layers[l].getCoeffBeta(); + coeff_gamma = this.layers[l].getCoeffGamma(); + coeff_eta = this.layers[l].getCoeffEta(); + oils = coeff_alpha[0].length;// this.layers[l].getOi(); + vins = coeff_beta[0].length;// this.layers[l].getVi(); + // compute polynomials of layer + for (int p = 0; p < oils; p++) + { + // multiply alphas + for (int x1 = 0; x1 < oils; x1++) + { + for (int x2 = 0; x2 < vins; x2++) + { + // multiply polynomial1 with polynomial2 + vect_tmp = c.multVect(coeff_alpha[p][x1][x2], + this.A2[x1 + vins]); + coeff_quadratic_3dim[crnt_row + p] = c.addSquareMatrix( + coeff_quadratic_3dim[crnt_row + p], c + .multVects(vect_tmp, this.A2[x2])); + // mul poly1 with scalar2 + vect_tmp = c.multVect(this.b2[x2], vect_tmp); + this.pub_singular[crnt_row + p] = c.addVect(vect_tmp, + this.pub_singular[crnt_row + p]); + // mul scalar1 with poly2 + vect_tmp = c.multVect(coeff_alpha[p][x1][x2], + this.A2[x2]); + vect_tmp = c.multVect(b2[x1 + vins], vect_tmp); + this.pub_singular[crnt_row + p] = c.addVect(vect_tmp, + this.pub_singular[crnt_row + p]); + // mul scalar1 with scalar2 + sclr_tmp = GF2Field.multElem(coeff_alpha[p][x1][x2], + this.b2[x1 + vins]); + this.pub_scalar[crnt_row + p] = GF2Field.addElem( + this.pub_scalar[crnt_row + p], GF2Field + .multElem(sclr_tmp, this.b2[x2])); + } + } + // multiply betas + for (int x1 = 0; x1 < vins; x1++) + { + for (int x2 = 0; x2 < vins; x2++) + { + // multiply polynomial1 with polynomial2 + vect_tmp = c.multVect(coeff_beta[p][x1][x2], + this.A2[x1]); + coeff_quadratic_3dim[crnt_row + p] = c.addSquareMatrix( + coeff_quadratic_3dim[crnt_row + p], c + .multVects(vect_tmp, this.A2[x2])); + // mul poly1 with scalar2 + vect_tmp = c.multVect(this.b2[x2], vect_tmp); + this.pub_singular[crnt_row + p] = c.addVect(vect_tmp, + this.pub_singular[crnt_row + p]); + // mul scalar1 with poly2 + vect_tmp = c.multVect(coeff_beta[p][x1][x2], + this.A2[x2]); + vect_tmp = c.multVect(this.b2[x1], vect_tmp); + this.pub_singular[crnt_row + p] = c.addVect(vect_tmp, + this.pub_singular[crnt_row + p]); + // mul scalar1 with scalar2 + sclr_tmp = GF2Field.multElem(coeff_beta[p][x1][x2], + this.b2[x1]); + this.pub_scalar[crnt_row + p] = GF2Field.addElem( + this.pub_scalar[crnt_row + p], GF2Field + .multElem(sclr_tmp, this.b2[x2])); + } + } + // multiply gammas + for (int n = 0; n < vins + oils; n++) + { + // mul poly with scalar + vect_tmp = c.multVect(coeff_gamma[p][n], this.A2[n]); + this.pub_singular[crnt_row + p] = c.addVect(vect_tmp, + this.pub_singular[crnt_row + p]); + // mul scalar with scalar + this.pub_scalar[crnt_row + p] = GF2Field.addElem( + this.pub_scalar[crnt_row + p], GF2Field.multElem( + coeff_gamma[p][n], this.b2[n])); + } + // add eta + this.pub_scalar[crnt_row + p] = GF2Field.addElem( + this.pub_scalar[crnt_row + p], coeff_eta[p]); + } + crnt_row = crnt_row + oils; + } + + // Apply L1 = A1*x+b1 to composition of F and L2 + { + // temporary coefficient arrays + short[][][] tmp_c_quad = new short[rows][vars][vars]; + short[][] tmp_c_sing = new short[rows][vars]; + short[] tmp_c_scal = new short[rows]; + for (int r = 0; r < rows; r++) + { + for (int q = 0; q < A1.length; q++) + { + tmp_c_quad[r] = c.addSquareMatrix(tmp_c_quad[r], c + .multMatrix(A1[r][q], coeff_quadratic_3dim[q])); + tmp_c_sing[r] = c.addVect(tmp_c_sing[r], c.multVect( + A1[r][q], this.pub_singular[q])); + tmp_c_scal[r] = GF2Field.addElem(tmp_c_scal[r], GF2Field + .multElem(A1[r][q], this.pub_scalar[q])); + } + tmp_c_scal[r] = GF2Field.addElem(tmp_c_scal[r], b1[r]); + } + // set public key + coeff_quadratic_3dim = tmp_c_quad; + this.pub_singular = tmp_c_sing; + this.pub_scalar = tmp_c_scal; + } + compactPublicKey(coeff_quadratic_3dim); + } + + /** + * The quadratic (or mixed) terms of the public key are compacted from a n x + * n matrix per polynomial to an upper diagonal matrix stored in one integer + * array of n (n + 1) / 2 elements per polynomial. The ordering of elements + * is lexicographic and the result is updating <tt>this.pub_quadratic</tt>, + * which stores the quadratic elements of the public key. + * + * @param coeff_quadratic_to_compact 3-dimensional array containing a n x n Matrix for each of the + * n - v1 polynomials + */ + private void compactPublicKey(short[][][] coeff_quadratic_to_compact) + { + int polynomials = coeff_quadratic_to_compact.length; + int n = coeff_quadratic_to_compact[0].length; + int entries = n * (n + 1) / 2;// the small gauss + this.pub_quadratic = new short[polynomials][entries]; + int offset = 0; + + for (int p = 0; p < polynomials; p++) + { + offset = 0; + for (int x = 0; x < n; x++) + { + for (int y = x; y < n; y++) + { + if (y == x) + { + this.pub_quadratic[p][offset] = coeff_quadratic_to_compact[p][x][y]; + } + else + { + this.pub_quadratic[p][offset] = GF2Field.addElem( + coeff_quadratic_to_compact[p][x][y], + coeff_quadratic_to_compact[p][y][x]); + } + offset++; + } + } + } + } + + public void init(KeyGenerationParameters param) + { + this.initialize(param); + } + + public AsymmetricCipherKeyPair generateKeyPair() + { + return genKeyPair(); + } +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowKeyParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowKeyParameters.java new file mode 100644 index 00000000..9dec6853 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowKeyParameters.java @@ -0,0 +1,25 @@ +package org.bouncycastle.pqc.crypto.rainbow; + +import org.bouncycastle.crypto.params.AsymmetricKeyParameter; + +public class RainbowKeyParameters + extends AsymmetricKeyParameter +{ + private int docLength; + + public RainbowKeyParameters( + boolean isPrivate, + int docLength) + { + super(isPrivate); + this.docLength = docLength; + } + + /** + * @return the docLength + */ + public int getDocLength() + { + return this.docLength; + } +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowParameters.java new file mode 100644 index 00000000..147c55e9 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowParameters.java @@ -0,0 +1,111 @@ +package org.bouncycastle.pqc.crypto.rainbow; + +import org.bouncycastle.crypto.CipherParameters; + +public class RainbowParameters + implements CipherParameters +{ + + /** + * DEFAULT PARAMS + */ + /* + * Vi = vinegars per layer whereas n is vu (vu = 33 = n) such that + * + * v1 = 6; o1 = 12-6 = 6 + * + * v2 = 12; o2 = 17-12 = 5 + * + * v3 = 17; o3 = 22-17 = 5 + * + * v4 = 22; o4 = 33-22 = 11 + * + * v5 = 33; (o5 = 0) + */ + private final int[] DEFAULT_VI = {6, 12, 17, 22, 33}; + + private int[] vi;// set of vinegar vars per layer. + + /** + * Default Constructor The elements of the array containing the number of + * Vinegar variables in each layer are set to the default values here. + */ + public RainbowParameters() + { + this.vi = this.DEFAULT_VI; + } + + /** + * Constructor with parameters + * + * @param vi The elements of the array containing the number of Vinegar + * variables per layer are set to the values of the input array. + */ + public RainbowParameters(int[] vi) + { + this.vi = vi; + try + { + checkParams(); + } + catch (Exception e) + { + e.printStackTrace(); + } + } + + private void checkParams() + throws Exception + { + if (vi == null) + { + throw new Exception("no layers defined."); + } + if (vi.length > 1) + { + for (int i = 0; i < vi.length - 1; i++) + { + if (vi[i] >= vi[i + 1]) + { + throw new Exception( + "v[i] has to be smaller than v[i+1]"); + } + } + } + else + { + throw new Exception( + "Rainbow needs at least 1 layer, such that v1 < v2."); + } + } + + /** + * Getter for the number of layers + * + * @return the number of layers + */ + public int getNumOfLayers() + { + return this.vi.length - 1; + } + + /** + * Getter for the number of all the polynomials in Rainbow + * + * @return the number of the polynomials + */ + public int getDocLength() + { + return vi[vi.length - 1] - vi[0]; + } + + /** + * Getter for the array containing the number of Vinegar-variables per layer + * + * @return the numbers of vinegars per layer + */ + public int[] getVi() + { + return this.vi; + } +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowPrivateKeyParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowPrivateKeyParameters.java new file mode 100644 index 00000000..98768820 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowPrivateKeyParameters.java @@ -0,0 +1,117 @@ +package org.bouncycastle.pqc.crypto.rainbow; + +public class RainbowPrivateKeyParameters + extends RainbowKeyParameters +{ + /** + * Constructor + * + * @param A1inv the inverse of A1(the matrix part of the affine linear map L1) + * (n-v1 x n-v1 matrix) + * @param b1 translation vector, part of the linear affine map L1 + * @param A2inv the inverse of A2(the matrix part of the affine linear map L2) + * (n x n matrix) + * @param b2 translation vector, part of the linear affine map L2 + * @param vi the number of Vinegar-variables per layer + * @param layers the polynomials with their coefficients of private map F + */ + public RainbowPrivateKeyParameters(short[][] A1inv, short[] b1, + short[][] A2inv, short[] b2, int[] vi, Layer[] layers) + { + super(true, vi[vi.length - 1] - vi[0]); + + this.A1inv = A1inv; + this.b1 = b1; + this.A2inv = A2inv; + this.b2 = b2; + this.vi = vi; + this.layers = layers; + } + + /* + * invertible affine linear map L1 + */ + // the inverse of A1, (n-v1 x n-v1 matrix) + private short[][] A1inv; + + // translation vector of L1 + private short[] b1; + + /* + * invertible affine linear map L2 + */ + // the inverse of A2, (n x n matrix) + private short[][] A2inv; + + // translation vector of L2 + private short[] b2; + + /* + * components of F + */ + // the number of Vinegar-variables per layer. + private int[] vi; + + // contains the polynomials with their coefficients of private map F + private Layer[] layers; + + /** + * Getter for the translation part of the private quadratic map L1. + * + * @return b1 the translation part of L1 + */ + public short[] getB1() + { + return this.b1; + } + + /** + * Getter for the inverse matrix of A1. + * + * @return the A1inv inverse + */ + public short[][] getInvA1() + { + return this.A1inv; + } + + /** + * Getter for the translation part of the private quadratic map L2. + * + * @return b2 the translation part of L2 + */ + public short[] getB2() + { + return this.b2; + } + + /** + * Getter for the inverse matrix of A2 + * + * @return the A2inv + */ + public short[][] getInvA2() + { + return this.A2inv; + } + + /** + * Returns the layers contained in the private key + * + * @return layers + */ + public Layer[] getLayers() + { + return this.layers; + } + + /** + * /** Returns the array of vi-s + * + * @return the vi + */ + public int[] getVi() + { + return vi; + } +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowPublicKeyParameters.java b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowPublicKeyParameters.java new file mode 100644 index 00000000..6f3e46f2 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowPublicKeyParameters.java @@ -0,0 +1,53 @@ +package org.bouncycastle.pqc.crypto.rainbow; + +public class RainbowPublicKeyParameters + extends RainbowKeyParameters +{ + private short[][] coeffquadratic; + private short[][] coeffsingular; + private short[] coeffscalar; + + /** + * Constructor + * + * @param docLength + * @param coeffQuadratic + * @param coeffSingular + * @param coeffScalar + */ + public RainbowPublicKeyParameters(int docLength, + short[][] coeffQuadratic, short[][] coeffSingular, + short[] coeffScalar) + { + super(false, docLength); + + this.coeffquadratic = coeffQuadratic; + this.coeffsingular = coeffSingular; + this.coeffscalar = coeffScalar; + + } + + /** + * @return the coeffquadratic + */ + public short[][] getCoeffQuadratic() + { + return coeffquadratic; + } + + /** + * @return the coeffsingular + */ + public short[][] getCoeffSingular() + { + return coeffsingular; + } + + /** + * @return the coeffscalar + */ + public short[] getCoeffScalar() + { + return coeffscalar; + } +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowSigner.java b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowSigner.java new file mode 100644 index 00000000..b6014a54 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/RainbowSigner.java @@ -0,0 +1,301 @@ +package org.bouncycastle.pqc.crypto.rainbow; + +import java.security.SecureRandom; + +import org.bouncycastle.crypto.CipherParameters; +import org.bouncycastle.crypto.params.ParametersWithRandom; +import org.bouncycastle.pqc.crypto.MessageSigner; +import org.bouncycastle.pqc.crypto.rainbow.util.ComputeInField; +import org.bouncycastle.pqc.crypto.rainbow.util.GF2Field; + +/** + * It implements the sign and verify functions for the Rainbow Signature Scheme. + * Here the message, which has to be signed, is updated. The use of + * different hash functions is possible. + * <p/> + * Detailed information about the signature and the verify-method is to be found + * in the paper of Jintai Ding, Dieter Schmidt: Rainbow, a New Multivariable + * Polynomial Signature Scheme. ACNS 2005: 164-175 + * (http://dx.doi.org/10.1007/11496137_12) + */ +public class RainbowSigner + implements MessageSigner +{ + // Source of randomness + private SecureRandom random; + + // The length of a document that can be signed with the privKey + int signableDocumentLength; + + // Container for the oil and vinegar variables of all the layers + private short[] x; + + private ComputeInField cf = new ComputeInField(); + + RainbowKeyParameters key; + + public void init(boolean forSigning, + CipherParameters param) + { + if (forSigning) + { + if (param instanceof ParametersWithRandom) + { + ParametersWithRandom rParam = (ParametersWithRandom)param; + + this.random = rParam.getRandom(); + this.key = (RainbowPrivateKeyParameters)rParam.getParameters(); + + } + else + { + + this.random = new SecureRandom(); + this.key = (RainbowPrivateKeyParameters)param; + } + } + else + { + this.key = (RainbowPublicKeyParameters)param; + } + + this.signableDocumentLength = this.key.getDocLength(); + } + + + /** + * initial operations before solving the Linear equation system. + * + * @param layer the current layer for which a LES is to be solved. + * @param msg the message that should be signed. + * @return Y_ the modified document needed for solving LES, (Y_ = + * A1^{-1}*(Y-b1)) linear map L1 = A1 x + b1. + */ + private short[] initSign(Layer[] layer, short[] msg) + { + + /* preparation: Modifies the document with the inverse of L1 */ + // tmp = Y - b1: + short[] tmpVec = new short[msg.length]; + + tmpVec = cf.addVect(((RainbowPrivateKeyParameters)this.key).getB1(), msg); + + // Y_ = A1^{-1} * (Y - b1) : + short[] Y_ = cf.multiplyMatrix(((RainbowPrivateKeyParameters)this.key).getInvA1(), tmpVec); + + /* generates the vinegar vars of the first layer at random */ + for (int i = 0; i < layer[0].getVi(); i++) + { + x[i] = (short)random.nextInt(); + x[i] = (short)(x[i] & GF2Field.MASK); + } + + return Y_; + } + + /** + * This function signs the message that has been updated, making use of the + * private key. + * <p/> + * For computing the signature, L1 and L2 are needed, as well as LES should + * be solved for each layer in order to find the Oil-variables in the layer. + * <p/> + * The Vinegar-variables of the first layer are random generated. + * + * @param message the message + * @return the signature of the message. + */ + public byte[] generateSignature(byte[] message) + { + Layer[] layer = ((RainbowPrivateKeyParameters)this.key).getLayers(); + int numberOfLayers = layer.length; + + x = new short[((RainbowPrivateKeyParameters)this.key).getInvA2().length]; // all variables + + short[] Y_; // modified document + short[] y_i; // part of Y_ each polynomial + int counter; // index of the current part of the doc + + short[] solVec; // the solution of LES pro layer + short[] tmpVec; + + // the signature as an array of shorts: + short[] signature; + // the signature as a byte-array: + byte[] S = new byte[layer[numberOfLayers - 1].getViNext()]; + + short[] msgHashVals = makeMessageRepresentative(message); + + // shows if an exception is caught + boolean ok; + do + { + ok = true; + counter = 0; + try + { + Y_ = initSign(layer, msgHashVals); + + for (int i = 0; i < numberOfLayers; i++) + { + + y_i = new short[layer[i].getOi()]; + solVec = new short[layer[i].getOi()]; // solution of LES + + /* copy oi elements of Y_ into y_i */ + for (int k = 0; k < layer[i].getOi(); k++) + { + y_i[k] = Y_[counter]; + counter++; // current index of Y_ + } + + /* + * plug in the vars of the previous layer in order to get + * the vars of the current layer + */ + solVec = cf.solveEquation(layer[i].plugInVinegars(x), y_i); + + if (solVec == null) + { // LES is not solveable + throw new Exception("LES is not solveable!"); + } + + /* copy the new vars into the x-array */ + for (int j = 0; j < solVec.length; j++) + { + x[layer[i].getVi() + j] = solVec[j]; + } + } + + /* apply the inverse of L2: (signature = A2^{-1}*(b2+x)) */ + tmpVec = cf.addVect(((RainbowPrivateKeyParameters)this.key).getB2(), x); + signature = cf.multiplyMatrix(((RainbowPrivateKeyParameters)this.key).getInvA2(), tmpVec); + + /* cast signature from short[] to byte[] */ + for (int i = 0; i < S.length; i++) + { + S[i] = ((byte)signature[i]); + } + } + catch (Exception se) + { + // if one of the LESs was not solveable - sign again + ok = false; + } + } + while (!ok); + /* return the signature in bytes */ + return S; + } + + /** + * This function verifies the signature of the message that has been + * updated, with the aid of the public key. + * + * @param message the message + * @param signature the signature of the message + * @return true if the signature has been verified, false otherwise. + */ + public boolean verifySignature(byte[] message, byte[] signature) + { + short[] sigInt = new short[signature.length]; + short tmp; + + for (int i = 0; i < signature.length; i++) + { + tmp = (short)signature[i]; + tmp &= (short)0xff; + sigInt[i] = tmp; + } + + short[] msgHashVal = makeMessageRepresentative(message); + + // verify + short[] verificationResult = verifySignatureIntern(sigInt); + + // compare + boolean verified = true; + if (msgHashVal.length != verificationResult.length) + { + return false; + } + for (int i = 0; i < msgHashVal.length; i++) + { + verified = verified && msgHashVal[i] == verificationResult[i]; + } + + return verified; + } + + /** + * Signature verification using public key + * + * @param signature vector of dimension n + * @return document hash of length n - v1 + */ + private short[] verifySignatureIntern(short[] signature) + { + + short[][] coeff_quadratic = ((RainbowPublicKeyParameters)this.key).getCoeffQuadratic(); + short[][] coeff_singular = ((RainbowPublicKeyParameters)this.key).getCoeffSingular(); + short[] coeff_scalar = ((RainbowPublicKeyParameters)this.key).getCoeffScalar(); + + short[] rslt = new short[coeff_quadratic.length];// n - v1 + int n = coeff_singular[0].length; + int offset = 0; // array position + short tmp = 0; // for scalar + + for (int p = 0; p < coeff_quadratic.length; p++) + { // no of polynomials + offset = 0; + for (int x = 0; x < n; x++) + { + // calculate quadratic terms + for (int y = x; y < n; y++) + { + tmp = GF2Field.multElem(coeff_quadratic[p][offset], + GF2Field.multElem(signature[x], signature[y])); + rslt[p] = GF2Field.addElem(rslt[p], tmp); + offset++; + } + // calculate singular terms + tmp = GF2Field.multElem(coeff_singular[p][x], signature[x]); + rslt[p] = GF2Field.addElem(rslt[p], tmp); + } + // add scalar + rslt[p] = GF2Field.addElem(rslt[p], coeff_scalar[p]); + } + + return rslt; + } + + /** + * This function creates the representative of the message which gets signed + * or verified. + * + * @param message the message + * @return message representative + */ + private short[] makeMessageRepresentative(byte[] message) + { + // the message representative + short[] output = new short[this.signableDocumentLength]; + + int h = 0; + int i = 0; + do + { + if (i >= message.length) + { + break; + } + output[i] = (short)message[h]; + output[i] &= (short)0xff; + h++; + i++; + } + while (i < output.length); + + return output; + } +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/util/ComputeInField.java b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/util/ComputeInField.java new file mode 100644 index 00000000..9a1115da --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/util/ComputeInField.java @@ -0,0 +1,490 @@ +package org.bouncycastle.pqc.crypto.rainbow.util; + +/** + * This class offers different operations on matrices in field GF2^8. + * <p/> + * Implemented are functions: + * - finding inverse of a matrix + * - solving linear equation systems using the Gauss-Elimination method + * - basic operations like matrix multiplication, addition and so on. + */ + +public class ComputeInField +{ + + private short[][] A; // used by solveEquation and inverse + short[] x; + + /** + * Constructor with no parameters + */ + public ComputeInField() + { + } + + + /** + * This function finds a solution of the equation Bx = b. + * Exception is thrown if the linear equation system has no solution + * + * @param B this matrix is the left part of the + * equation (B in the equation above) + * @param b the right part of the equation + * (b in the equation above) + * @return x the solution of the equation if it is solvable + * null otherwise + * @throws RuntimeException if LES is not solvable + */ + public short[] solveEquation(short[][] B, short[] b) + { + try + { + + if (B.length != b.length) + { + throw new RuntimeException( + "The equation system is not solvable"); + } + + /** initialize **/ + // this matrix stores B and b from the equation B*x = b + // b is stored as the last column. + // B contains one column more than rows. + // In this column we store a free coefficient that should be later subtracted from b + A = new short[B.length][B.length + 1]; + // stores the solution of the LES + x = new short[B.length]; + + /** copy B into the global matrix A **/ + for (int i = 0; i < B.length; i++) + { // rows + for (int j = 0; j < B[0].length; j++) + { // cols + A[i][j] = B[i][j]; + } + } + + /** copy the vector b into the global A **/ + //the free coefficient, stored in the last column of A( A[i][b.length] + // is to be subtracted from b + for (int i = 0; i < b.length; i++) + { + A[i][b.length] = GF2Field.addElem(b[i], A[i][b.length]); + } + + /** call the methods for gauss elimination and backward substitution **/ + computeZerosUnder(false); // obtain zeros under the diagonal + substitute(); + + return x; + + } + catch (RuntimeException rte) + { + return null; // the LES is not solvable! + } + } + + /** + * This function computes the inverse of a given matrix using the Gauss- + * Elimination method. + * <p/> + * An exception is thrown if the matrix has no inverse + * + * @param coef the matrix which inverse matrix is needed + * @return inverse matrix of the input matrix. + * If the matrix is singular, null is returned. + * @throws RuntimeException if the given matrix is not invertible + */ + public short[][] inverse(short[][] coef) + { + try + { + /** Initialization: **/ + short factor; + short[][] inverse; + A = new short[coef.length][2 * coef.length]; + if (coef.length != coef[0].length) + { + throw new RuntimeException( + "The matrix is not invertible. Please choose another one!"); + } + + /** prepare: Copy coef and the identity matrix into the global A. **/ + for (int i = 0; i < coef.length; i++) + { + for (int j = 0; j < coef.length; j++) + { + //copy the input matrix coef into A + A[i][j] = coef[i][j]; + } + // copy the identity matrix into A. + for (int j = coef.length; j < 2 * coef.length; j++) + { + A[i][j] = 0; + } + A[i][i + A.length] = 1; + } + + /** Elimination operations to get the identity matrix from the left side of A. **/ + // modify A to get 0s under the diagonal. + computeZerosUnder(true); + + // modify A to get only 1s on the diagonal: A[i][j] =A[i][j]/A[i][i]. + for (int i = 0; i < A.length; i++) + { + factor = GF2Field.invElem(A[i][i]); + for (int j = i; j < 2 * A.length; j++) + { + A[i][j] = GF2Field.multElem(A[i][j], factor); + } + } + + //modify A to get only 0s above the diagonal. + computeZerosAbove(); + + // copy the result (the second half of A) in the matrix inverse. + inverse = new short[A.length][A.length]; + for (int i = 0; i < A.length; i++) + { + for (int j = A.length; j < 2 * A.length; j++) + { + inverse[i][j - A.length] = A[i][j]; + } + } + return inverse; + + } + catch (RuntimeException rte) + { + // The matrix is not invertible! A new one should be generated! + return null; + } + } + + /** + * Elimination under the diagonal. + * This function changes a matrix so that it contains only zeros under the + * diagonal(Ai,i) using only Gauss-Elimination operations. + * <p/> + * It is used in solveEquaton as well as in the function for + * finding an inverse of a matrix: {@link}inverse. Both of them use the + * Gauss-Elimination Method. + * <p/> + * The result is stored in the global matrix A + * + * @param usedForInverse This parameter shows if the function is used by the + * solveEquation-function or by the inverse-function and according + * to this creates matrices of different sizes. + * @throws RuntimeException in case a multiplicative inverse of 0 is needed + */ + private void computeZerosUnder(boolean usedForInverse) + throws RuntimeException + { + + //the number of columns in the global A where the tmp results are stored + int length; + short tmp = 0; + + //the function is used in inverse() - A should have 2 times more columns than rows + if (usedForInverse) + { + length = 2 * A.length; + } + //the function is used in solveEquation - A has 1 column more than rows + else + { + length = A.length + 1; + } + + //elimination operations to modify A so that that it contains only 0s under the diagonal + for (int k = 0; k < A.length - 1; k++) + { // the fixed row + for (int i = k + 1; i < A.length; i++) + { // rows + short factor1 = A[i][k]; + short factor2 = GF2Field.invElem(A[k][k]); + + //The element which multiplicative inverse is needed, is 0 + //in this case is the input matrix not invertible + if (factor2 == 0) + { + throw new RuntimeException("Matrix not invertible! We have to choose another one!"); + } + + for (int j = k; j < length; j++) + {// columns + // tmp=A[k,j] / A[k,k] + tmp = GF2Field.multElem(A[k][j], factor2); + // tmp = A[i,k] * A[k,j] / A[k,k] + tmp = GF2Field.multElem(factor1, tmp); + // A[i,j]=A[i,j]-A[i,k]/A[k,k]*A[k,j]; + A[i][j] = GF2Field.addElem(A[i][j], tmp); + } + } + } + } + + /** + * Elimination above the diagonal. + * This function changes a matrix so that it contains only zeros above the + * diagonal(Ai,i) using only Gauss-Elimination operations. + * <p/> + * It is used in the inverse-function + * The result is stored in the global matrix A + * + * @throws RuntimeException in case a multiplicative inverse of 0 is needed + */ + private void computeZerosAbove() + throws RuntimeException + { + short tmp = 0; + for (int k = A.length - 1; k > 0; k--) + { // the fixed row + for (int i = k - 1; i >= 0; i--) + { // rows + short factor1 = A[i][k]; + short factor2 = GF2Field.invElem(A[k][k]); + if (factor2 == 0) + { + throw new RuntimeException("The matrix is not invertible"); + } + for (int j = k; j < 2 * A.length; j++) + { // columns + // tmp = A[k,j] / A[k,k] + tmp = GF2Field.multElem(A[k][j], factor2); + // tmp = A[i,k] * A[k,j] / A[k,k] + tmp = GF2Field.multElem(factor1, tmp); + // A[i,j] = A[i,j] - A[i,k] / A[k,k] * A[k,j]; + A[i][j] = GF2Field.addElem(A[i][j], tmp); + } + } + } + } + + + /** + * This function uses backward substitution to find x + * of the linear equation system (LES) B*x = b, + * where A a triangle-matrix is (contains only zeros under the diagonal) + * and b is a vector + * <p/> + * If the multiplicative inverse of 0 is needed, an exception is thrown. + * In this case is the LES not solvable + * + * @throws RuntimeException in case a multiplicative inverse of 0 is needed + */ + private void substitute() + throws RuntimeException + { + + // for the temporary results of the operations in field + short tmp, temp; + + temp = GF2Field.invElem(A[A.length - 1][A.length - 1]); + if (temp == 0) + { + throw new RuntimeException("The equation system is not solvable"); + } + + /** backward substitution **/ + x[A.length - 1] = GF2Field.multElem(A[A.length - 1][A.length], temp); + for (int i = A.length - 2; i >= 0; i--) + { + tmp = A[i][A.length]; + for (int j = A.length - 1; j > i; j--) + { + temp = GF2Field.multElem(A[i][j], x[j]); + tmp = GF2Field.addElem(tmp, temp); + } + + temp = GF2Field.invElem(A[i][i]); + if (temp == 0) + { + throw new RuntimeException("Not solvable equation system"); + } + x[i] = GF2Field.multElem(tmp, temp); + } + } + + + /** + * This function multiplies two given matrices. + * If the given matrices cannot be multiplied due + * to different sizes, an exception is thrown. + * + * @param M1 -the 1st matrix + * @param M2 -the 2nd matrix + * @return A = M1*M2 + * @throws RuntimeException in case the given matrices cannot be multiplied + * due to different dimensions. + */ + public short[][] multiplyMatrix(short[][] M1, short[][] M2) + throws RuntimeException + { + + if (M1[0].length != M2.length) + { + throw new RuntimeException("Multiplication is not possible!"); + } + short tmp = 0; + A = new short[M1.length][M2[0].length]; + for (int i = 0; i < M1.length; i++) + { + for (int j = 0; j < M2.length; j++) + { + for (int k = 0; k < M2[0].length; k++) + { + tmp = GF2Field.multElem(M1[i][j], M2[j][k]); + A[i][k] = GF2Field.addElem(A[i][k], tmp); + } + } + } + return A; + } + + /** + * This function multiplies a given matrix with a one-dimensional array. + * <p/> + * An exception is thrown, if the number of columns in the matrix and + * the number of rows in the one-dim. array differ. + * + * @param M1 the matrix to be multiplied + * @param m the one-dimensional array to be multiplied + * @return M1*m + * @throws RuntimeException in case of dimension inconsistency + */ + public short[] multiplyMatrix(short[][] M1, short[] m) + throws RuntimeException + { + if (M1[0].length != m.length) + { + throw new RuntimeException("Multiplication is not possible!"); + } + short tmp = 0; + short[] B = new short[M1.length]; + for (int i = 0; i < M1.length; i++) + { + for (int j = 0; j < m.length; j++) + { + tmp = GF2Field.multElem(M1[i][j], m[j]); + B[i] = GF2Field.addElem(B[i], tmp); + } + } + return B; + } + + /** + * Addition of two vectors + * + * @param vector1 first summand, always of dim n + * @param vector2 second summand, always of dim n + * @return addition of vector1 and vector2 + * @throws RuntimeException in case the addition is impossible + * due to inconsistency in the dimensions + */ + public short[] addVect(short[] vector1, short[] vector2) + { + if (vector1.length != vector2.length) + { + throw new RuntimeException("Multiplication is not possible!"); + } + short rslt[] = new short[vector1.length]; + for (int n = 0; n < rslt.length; n++) + { + rslt[n] = GF2Field.addElem(vector1[n], vector2[n]); + } + return rslt; + } + + /** + * Multiplication of column vector with row vector + * + * @param vector1 column vector, always n x 1 + * @param vector2 row vector, always 1 x n + * @return resulting n x n matrix of multiplication + * @throws RuntimeException in case the multiplication is impossible due to + * inconsistency in the dimensions + */ + public short[][] multVects(short[] vector1, short[] vector2) + { + if (vector1.length != vector2.length) + { + throw new RuntimeException("Multiplication is not possible!"); + } + short rslt[][] = new short[vector1.length][vector2.length]; + for (int i = 0; i < vector1.length; i++) + { + for (int j = 0; j < vector2.length; j++) + { + rslt[i][j] = GF2Field.multElem(vector1[i], vector2[j]); + } + } + return rslt; + } + + /** + * Multiplies vector with scalar + * + * @param scalar galois element to multiply vector with + * @param vector vector to be multiplied + * @return vector multiplied with scalar + */ + public short[] multVect(short scalar, short[] vector) + { + short rslt[] = new short[vector.length]; + for (int n = 0; n < rslt.length; n++) + { + rslt[n] = GF2Field.multElem(scalar, vector[n]); + } + return rslt; + } + + /** + * Multiplies matrix with scalar + * + * @param scalar galois element to multiply matrix with + * @param matrix 2-dim n x n matrix to be multiplied + * @return matrix multiplied with scalar + */ + public short[][] multMatrix(short scalar, short[][] matrix) + { + short[][] rslt = new short[matrix.length][matrix[0].length]; + for (int i = 0; i < matrix.length; i++) + { + for (int j = 0; j < matrix[0].length; j++) + { + rslt[i][j] = GF2Field.multElem(scalar, matrix[i][j]); + } + } + return rslt; + } + + /** + * Adds the n x n matrices matrix1 and matrix2 + * + * @param matrix1 first summand + * @param matrix2 second summand + * @return addition of matrix1 and matrix2; both having the dimensions n x n + * @throws RuntimeException in case the addition is not possible because of + * different dimensions of the matrices + */ + public short[][] addSquareMatrix(short[][] matrix1, short[][] matrix2) + { + if (matrix1.length != matrix2.length || matrix1[0].length != matrix2[0].length) + { + throw new RuntimeException("Addition is not possible!"); + } + + short[][] rslt = new short[matrix1.length][matrix1.length];// + for (int i = 0; i < matrix1.length; i++) + { + for (int j = 0; j < matrix2.length; j++) + { + rslt[i][j] = GF2Field.addElem(matrix1[i][j], matrix2[i][j]); + } + } + return rslt; + } + +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/util/GF2Field.java b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/util/GF2Field.java new file mode 100644 index 00000000..7c286491 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/util/GF2Field.java @@ -0,0 +1,139 @@ +package org.bouncycastle.pqc.crypto.rainbow.util; + +/** + * This class provides the basic operations like addition, multiplication and + * finding the multiplicative inverse of an element in GF2^8. + * <p/> + * The operations are implemented using the irreducible polynomial + * 1+x^2+x^3+x^6+x^8 ( 1 0100 1101 = 0x14d ) + * <p/> + * This class makes use of lookup tables(exps and logs) for implementing the + * operations in order to increase the efficiency of Rainbow. + */ +public class GF2Field +{ + + public static final int MASK = 0xff; + + /* + * this lookup table is needed for multiplication and computing the + * multiplicative inverse + */ + static final short exps[] = {1, 2, 4, 8, 16, 32, 64, 128, 77, 154, 121, 242, + 169, 31, 62, 124, 248, 189, 55, 110, 220, 245, 167, 3, 6, 12, 24, + 48, 96, 192, 205, 215, 227, 139, 91, 182, 33, 66, 132, 69, 138, 89, + 178, 41, 82, 164, 5, 10, 20, 40, 80, 160, 13, 26, 52, 104, 208, + 237, 151, 99, 198, 193, 207, 211, 235, 155, 123, 246, 161, 15, 30, + 60, 120, 240, 173, 23, 46, 92, 184, 61, 122, 244, 165, 7, 14, 28, + 56, 112, 224, 141, 87, 174, 17, 34, 68, 136, 93, 186, 57, 114, 228, + 133, 71, 142, 81, 162, 9, 18, 36, 72, 144, 109, 218, 249, 191, 51, + 102, 204, 213, 231, 131, 75, 150, 97, 194, 201, 223, 243, 171, 27, + 54, 108, 216, 253, 183, 35, 70, 140, 85, 170, 25, 50, 100, 200, + 221, 247, 163, 11, 22, 44, 88, 176, 45, 90, 180, 37, 74, 148, 101, + 202, 217, 255, 179, 43, 86, 172, 21, 42, 84, 168, 29, 58, 116, 232, + 157, 119, 238, 145, 111, 222, 241, 175, 19, 38, 76, 152, 125, 250, + 185, 63, 126, 252, 181, 39, 78, 156, 117, 234, 153, 127, 254, 177, + 47, 94, 188, 53, 106, 212, 229, 135, 67, 134, 65, 130, 73, 146, + 105, 210, 233, 159, 115, 230, 129, 79, 158, 113, 226, 137, 95, 190, + 49, 98, 196, 197, 199, 195, 203, 219, 251, 187, 59, 118, 236, 149, + 103, 206, 209, 239, 147, 107, 214, 225, 143, 83, 166, 1}; + + /* + * this lookup table is needed for multiplication and computing the + * multiplicative inverse + */ + static final short logs[] = {0, 0, 1, 23, 2, 46, 24, 83, 3, 106, 47, 147, + 25, 52, 84, 69, 4, 92, 107, 182, 48, 166, 148, 75, 26, 140, 53, + 129, 85, 170, 70, 13, 5, 36, 93, 135, 108, 155, 183, 193, 49, 43, + 167, 163, 149, 152, 76, 202, 27, 230, 141, 115, 54, 205, 130, 18, + 86, 98, 171, 240, 71, 79, 14, 189, 6, 212, 37, 210, 94, 39, 136, + 102, 109, 214, 156, 121, 184, 8, 194, 223, 50, 104, 44, 253, 168, + 138, 164, 90, 150, 41, 153, 34, 77, 96, 203, 228, 28, 123, 231, 59, + 142, 158, 116, 244, 55, 216, 206, 249, 131, 111, 19, 178, 87, 225, + 99, 220, 172, 196, 241, 175, 72, 10, 80, 66, 15, 186, 190, 199, 7, + 222, 213, 120, 38, 101, 211, 209, 95, 227, 40, 33, 137, 89, 103, + 252, 110, 177, 215, 248, 157, 243, 122, 58, 185, 198, 9, 65, 195, + 174, 224, 219, 51, 68, 105, 146, 45, 82, 254, 22, 169, 12, 139, + 128, 165, 74, 91, 181, 151, 201, 42, 162, 154, 192, 35, 134, 78, + 188, 97, 239, 204, 17, 229, 114, 29, 61, 124, 235, 232, 233, 60, + 234, 143, 125, 159, 236, 117, 30, 245, 62, 56, 246, 217, 63, 207, + 118, 250, 31, 132, 160, 112, 237, 20, 144, 179, 126, 88, 251, 226, + 32, 100, 208, 221, 119, 173, 218, 197, 64, 242, 57, 176, 247, 73, + 180, 11, 127, 81, 21, 67, 145, 16, 113, 187, 238, 191, 133, 200, + 161}; + + /** + * This function calculates the sum of two elements as an operation in GF2^8 + * + * @param x the first element that is to be added + * @param y the second element that should be add + * @return the sum of the two elements x and y in GF2^8 + */ + public static short addElem(short x, short y) + { + return (short)(x ^ y); + } + + /** + * This function computes the multiplicative inverse of a given element in + * GF2^8 The 0 has no multiplicative inverse and in this case 0 is returned. + * + * @param x the element which multiplicative inverse is to be computed + * @return the multiplicative inverse of the given element, in case it + * exists or 0, otherwise + */ + public static short invElem(short x) + { + if (x == 0) + { + return 0; + } + return (exps[255 - logs[x]]); + } + + /** + * This function multiplies two elements in GF2^8. If one of the two + * elements is 0, 0 is returned. + * + * @param x the first element to be multiplied. + * @param y the second element to be multiplied. + * @return the product of the two input elements in GF2^8. + */ + public static short multElem(short x, short y) + { + if (x == 0 || y == 0) + { + return 0; + } + else + { + return (exps[(logs[x] + logs[y]) % 255]); + } + } + + /** + * This function returns the values of exps-lookup table which correspond to + * the input + * + * @param x the index in the lookup table exps + * @return exps-value, corresponding to the input + */ + public static short getExp(short x) + { + return exps[x]; + } + + /** + * This function returns the values of logs-lookup table which correspond to + * the input + * + * @param x the index in the lookup table logs + * @return logs-value, corresponding to the input + */ + public static short getLog(short x) + { + return logs[x]; + } + + +} diff --git a/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/util/RainbowUtil.java b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/util/RainbowUtil.java new file mode 100644 index 00000000..2b073b1b --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow/util/RainbowUtil.java @@ -0,0 +1,230 @@ +package org.bouncycastle.pqc.crypto.rainbow.util; + +/** + * This class is needed for the conversions while encoding and decoding, as well as for + * comparison between arrays of some dimensions + */ +public class RainbowUtil +{ + + /** + * This function converts an one-dimensional array of bytes into a + * one-dimensional array of int + * + * @param in the array to be converted + * @return out + * the one-dimensional int-array that corresponds the input + */ + public static int[] convertArraytoInt(byte[] in) + { + int[] out = new int[in.length]; + for (int i = 0; i < in.length; i++) + { + out[i] = in[i] & GF2Field.MASK; + } + return out; + } + + /** + * This function converts an one-dimensional array of bytes into a + * one-dimensional array of type short + * + * @param in the array to be converted + * @return out + * one-dimensional short-array that corresponds the input + */ + public static short[] convertArray(byte[] in) + { + short[] out = new short[in.length]; + for (int i = 0; i < in.length; i++) + { + out[i] = (short)(in[i] & GF2Field.MASK); + } + return out; + } + + /** + * This function converts a matrix of bytes into a matrix of type short + * + * @param in the matrix to be converted + * @return out + * short-matrix that corresponds the input + */ + public static short[][] convertArray(byte[][] in) + { + short[][] out = new short[in.length][in[0].length]; + for (int i = 0; i < in.length; i++) + { + for (int j = 0; j < in[0].length; j++) + { + out[i][j] = (short)(in[i][j] & GF2Field.MASK); + } + } + return out; + } + + /** + * This function converts a 3-dimensional array of bytes into a 3-dimensional array of type short + * + * @param in the array to be converted + * @return out + * short-array that corresponds the input + */ + public static short[][][] convertArray(byte[][][] in) + { + short[][][] out = new short[in.length][in[0].length][in[0][0].length]; + for (int i = 0; i < in.length; i++) + { + for (int j = 0; j < in[0].length; j++) + { + for (int k = 0; k < in[0][0].length; k++) + { + out[i][j][k] = (short)(in[i][j][k] & GF2Field.MASK); + } + } + } + return out; + } + + /** + * This function converts an array of type int into an array of type byte + * + * @param in the array to be converted + * @return out + * the byte-array that corresponds the input + */ + public static byte[] convertIntArray(int[] in) + { + byte[] out = new byte[in.length]; + for (int i = 0; i < in.length; i++) + { + out[i] = (byte)in[i]; + } + return out; + } + + + /** + * This function converts an array of type short into an array of type byte + * + * @param in the array to be converted + * @return out + * the byte-array that corresponds the input + */ + public static byte[] convertArray(short[] in) + { + byte[] out = new byte[in.length]; + for (int i = 0; i < in.length; i++) + { + out[i] = (byte)in[i]; + } + return out; + } + + /** + * This function converts a matrix of type short into a matrix of type byte + * + * @param in the matrix to be converted + * @return out + * the byte-matrix that corresponds the input + */ + public static byte[][] convertArray(short[][] in) + { + byte[][] out = new byte[in.length][in[0].length]; + for (int i = 0; i < in.length; i++) + { + for (int j = 0; j < in[0].length; j++) + { + out[i][j] = (byte)in[i][j]; + } + } + return out; + } + + /** + * This function converts a 3-dimensional array of type short into a 3-dimensional array of type byte + * + * @param in the array to be converted + * @return out + * the byte-array that corresponds the input + */ + public static byte[][][] convertArray(short[][][] in) + { + byte[][][] out = new byte[in.length][in[0].length][in[0][0].length]; + for (int i = 0; i < in.length; i++) + { + for (int j = 0; j < in[0].length; j++) + { + for (int k = 0; k < in[0][0].length; k++) + { + out[i][j][k] = (byte)in[i][j][k]; + } + } + } + return out; + } + + /** + * Compare two short arrays. No null checks are performed. + * + * @param left the first short array + * @param right the second short array + * @return the result of the comparison + */ + public static boolean equals(short[] left, short[] right) + { + if (left.length != right.length) + { + return false; + } + boolean result = true; + for (int i = left.length - 1; i >= 0; i--) + { + result &= left[i] == right[i]; + } + return result; + } + + /** + * Compare two two-dimensional short arrays. No null checks are performed. + * + * @param left the first short array + * @param right the second short array + * @return the result of the comparison + */ + public static boolean equals(short[][] left, short[][] right) + { + if (left.length != right.length) + { + return false; + } + boolean result = true; + for (int i = left.length - 1; i >= 0; i--) + { + result &= equals(left[i], right[i]); + } + return result; + } + + /** + * Compare two three-dimensional short arrays. No null checks are performed. + * + * @param left the first short array + * @param right the second short array + * @return the result of the comparison + */ + public static boolean equals(short[][][] left, short[][][] right) + { + if (left.length != right.length) + { + return false; + } + boolean result = true; + for (int i = left.length - 1; i >= 0; i--) + { + result &= equals(left[i], right[i]); + } + return result; + } + +} |