Package org.bouncycastle.util

Class BigIntegers

  • public final class BigIntegers
extends java.lang.Object
    BigInteger utilities.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static class  BigIntegers.Cache  

    • Field Summary

      Fields 
      Modifier and Type Field Description
      static java.math.BigInteger ONE  
      static java.math.BigInteger TWO  
      static java.math.BigInteger ZERO  

    • Constructor Summary

      Constructors 
      Constructor Description
      BigIntegers()  

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static boolean areSecretValuesEqual​(int maxLen, java.math.BigInteger a, java.math.BigInteger b)
      Compare two non-negative values for equality without an early exit.
      static byte[] asUnsignedByteArray​(int length, java.math.BigInteger value)
      Return the passed in value as an unsigned byte array of the specified length, padded with leading zeros as necessary..
      static byte[] asUnsignedByteArray​(java.math.BigInteger value)
      Return the passed in value as an unsigned byte array.
      static void asUnsignedByteArray​(java.math.BigInteger value, byte[] buf, int off, int len)
      Write the passed in value as unsigned bytes to the specified buffer range, padded with leading zeros as necessary.
      static byte byteValueExact​(java.math.BigInteger x)  
      static java.math.BigInteger createBlindedExponent​(java.math.BigInteger exponent, java.math.BigInteger groupOrder, java.security.SecureRandom random)
      Return a private exponent randomised for use in a variable-time modular exponentiation.
      static java.math.BigInteger createRandomBigInteger​(int bitLength, java.security.SecureRandom random)
      Return a positive BigInteger in the range of 0 to 2**bitLength - 1.
      static java.math.BigInteger createRandomInRange​(java.math.BigInteger min, java.math.BigInteger max, java.security.SecureRandom random)
      Return a random BigInteger not less than 'min' and not greater than 'max'
      static java.math.BigInteger createRandomPrime​(int bitLength, int certainty, java.security.SecureRandom random)
      Return a prime number candidate of the specified bit length.
      static java.math.BigInteger fromUnsignedByteArray​(byte[] buf)  
      static java.math.BigInteger fromUnsignedByteArray​(byte[] buf, int off, int length)  
      static int getUnsignedByteLength​(java.math.BigInteger n)  
      static boolean hasAnySmallFactors​(java.math.BigInteger x)  
      static int intValueExact​(java.math.BigInteger x)  
      static long longValueExact​(java.math.BigInteger x)  
      static java.math.BigInteger modAdd​(java.math.BigInteger M, java.math.BigInteger X, java.math.BigInteger Y)
      Return (X + Y) mod M for X and Y already in the range [0, M).
      static java.math.BigInteger modMult​(java.math.BigInteger M, java.math.BigInteger X, java.math.BigInteger Y)
      Return (X * Y) mod M for an odd M and X, Y already in the range [0, M), by Montgomery multiplication over a fixed number of words.
      static java.math.BigInteger modOddInverse​(java.math.BigInteger M, java.math.BigInteger X)  
      static java.math.BigInteger modOddInverseVar​(java.math.BigInteger M, java.math.BigInteger X)  
      static boolean modOddIsCoprime​(java.math.BigInteger M, java.math.BigInteger X)  
      static boolean modOddIsCoprimeVar​(java.math.BigInteger M, java.math.BigInteger X)  
      static java.math.BigInteger modSubtract​(java.math.BigInteger M, java.math.BigInteger X, java.math.BigInteger Y)
      Return (X - Y) mod M for X and Y already in the range [0, M).
      static short shortValueExact​(java.math.BigInteger x)  
      static void writeUnsignedByteArray​(java.io.OutputStream out, java.math.BigInteger n)  

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • ZERO

        public static final java.math.BigInteger ZERO

      • ONE

        public static final java.math.BigInteger ONE

      • TWO

        public static final java.math.BigInteger TWO

    • Constructor Detail

      • BigIntegers

        public BigIntegers()

    • Method Detail

      • asUnsignedByteArray

        public static byte[] asUnsignedByteArray​(java.math.BigInteger value)
        Return the passed in value as an unsigned byte array.
        Parameters:
        value - the value to be converted.
        Returns:
        a byte array without a leading zero byte if present in the signed encoding.

      • asUnsignedByteArray

        public static byte[] asUnsignedByteArray​(int length,
                                         java.math.BigInteger value)
        Return the passed in value as an unsigned byte array of the specified length, padded with leading zeros as necessary..
        Parameters:
        length - the fixed length of the result
        value - the value to be converted.
        Returns:
        a byte array padded to a fixed length with leading zeros.

      • asUnsignedByteArray

        public static void asUnsignedByteArray​(java.math.BigInteger value,
                                       byte[] buf,
                                       int off,
                                       int len)
        Write the passed in value as unsigned bytes to the specified buffer range, padded with leading zeros as necessary.
        Parameters:
        value - the value to be converted.
        buf - the buffer to which the value is written.
        off - the start offset in array buf at which the data is written.
        len - the fixed length of data written (possibly padded with leading zeros).

      • createRandomInRange

        public static java.math.BigInteger createRandomInRange​(java.math.BigInteger min,
                                                       java.math.BigInteger max,
                                                       java.security.SecureRandom random)
        Return a random BigInteger not less than 'min' and not greater than 'max'
        Parameters:
        min - the least value that may be generated
        max - the greatest value that may be generated
        random - the source of randomness
        Returns:
        a random BigInteger value in the range [min,max]

      • fromUnsignedByteArray

        public static java.math.BigInteger fromUnsignedByteArray​(byte[] buf)

      • fromUnsignedByteArray

        public static java.math.BigInteger fromUnsignedByteArray​(byte[] buf,
                                                         int off,
                                                         int length)

      • byteValueExact

        public static byte byteValueExact​(java.math.BigInteger x)

      • shortValueExact

        public static short shortValueExact​(java.math.BigInteger x)

      • intValueExact

        public static int intValueExact​(java.math.BigInteger x)

      • longValueExact

        public static long longValueExact​(java.math.BigInteger x)

      • areSecretValuesEqual

        public static boolean areSecretValuesEqual​(int maxLen,
                                           java.math.BigInteger a,
                                           java.math.BigInteger b)
        Compare two non-negative values for equality without an early exit. Both are laid out as unsigned big-endian byte arrays of the fixed public length maxLen before the comparison, so the comparison itself is length-uniform.

        Fixed-width encoding drops the two's-complement sign byte that BigInteger.toByteArray() prepends when the most-significant bit is set: without that, two values could serialise to different lengths (e.g. 256 vs 257 bytes for a 2048-bit value) purely according to that high bit, and the variable-time comparison would leak it. This is not perfectly constant-time - java.math.BigInteger has no constant-time serialisation, so the underlying toByteArray() still runs in time proportional to each value's magnitude - but the comparison no longer differs in length on the value's high bit. Intended for secret key material (RSA d and the CRT factors, DSA/DH/ElGamal/GOST x, EC d), which are all non-negative; the temporary unsigned encodings holding that secret material are zeroed before returning.

        Both arguments must be non-null and non-negative; a negative value does not produce a meaningful result (and may throw IllegalArgumentException), and a null value throws NullPointerException.

        Parameters:
        maxLen - the public unsigned byte length both values are encoded to (e.g. from a group order or modulus).
        a - the first value, non-null and non-negative.
        b - the second value, non-null and non-negative.
        Returns:
        true if a and b are numerically equal, false otherwise.

      • hasAnySmallFactors

        public static boolean hasAnySmallFactors​(java.math.BigInteger x)

      • modAdd

        public static java.math.BigInteger modAdd​(java.math.BigInteger M,
                                          java.math.BigInteger X,
                                          java.math.BigInteger Y)
        Return (X + Y) mod M for X and Y already in the range [0, M). The sum is formed at a fixed width and reduced by subtracting M unconditionally and then keeping or discarding the result with a mask, so neither the running time nor the memory access pattern depends on the values.

        Use this rather than X.add(Y).mod(M) when either operand is secret. A reduction short-circuits when the value it is given is already less than the modulus, so a sum that crosses the top of M is distinguishable from one that does not. Where the other operand is public that difference is a threshold predicate on the secret one, and a public operand the caller does not control turns repeated observations into a search over the secret.

        Parameters:
        M - the modulus, which must be positive.
        X - a value in the range [0, M).
        Y - a value in the range [0, M).
        Returns:
        (X + Y) mod M.

      • modSubtract

        public static java.math.BigInteger modSubtract​(java.math.BigInteger M,
                                               java.math.BigInteger X,
                                               java.math.BigInteger Y)
        Return (X - Y) mod M for X and Y already in the range [0, M). The difference is formed at a fixed width and brought back into range by adding M unconditionally and then keeping or discarding the result with a mask, so neither the running time nor the memory access pattern depends on the values.

        Use this rather than X.subtract(Y).mod(M) when either operand is secret. A negative value costs the reduction more work than a non-negative one, so whether the difference underflowed is distinguishable, and that is a comparison between the two operands - which, where one of them is public, is a threshold predicate on the secret one.

        Parameters:
        M - the modulus, which must be positive.
        X - a value in the range [0, M).
        Y - a value in the range [0, M).
        Returns:
        (X - Y) mod M.

      • modMult

        public static java.math.BigInteger modMult​(java.math.BigInteger M,
                                           java.math.BigInteger X,
                                           java.math.BigInteger Y)
        Return (X * Y) mod M for an odd M and X, Y already in the range [0, M), by Montgomery multiplication over a fixed number of words. Every loop runs a value-independent number of times and no index depends on the operands.

        Use this rather than X.multiply(Y).mod(M) when either operand is secret. The product is up to twice the width of M, so the reduction is a real division rather than the single conditional subtraction modAdd(BigInteger, BigInteger, BigInteger) needs, and how much work it does depends on the quotient - which is to say on the operands.

        The quantities derived from M alone (R squared mod M, where R is 2 raised to the width of M rounded up to a word boundary, and the reduction multiplier) are computed with BigInteger, since M is the public modulus, and retained from one call to the next - callers run whole chains of order arithmetic against one group order. Whether a call reuses them depends only on the modulus.

        Parameters:
        M - the modulus, which must be odd and positive.
        X - a value in the range [0, M).
        Y - a value in the range [0, M).
        Returns:
        (X * Y) mod M.

      • modOddInverse

        public static java.math.BigInteger modOddInverse​(java.math.BigInteger M,
                                                 java.math.BigInteger X)

      • modOddInverseVar

        public static java.math.BigInteger modOddInverseVar​(java.math.BigInteger M,
                                                    java.math.BigInteger X)

      • modOddIsCoprime

        public static boolean modOddIsCoprime​(java.math.BigInteger M,
                                      java.math.BigInteger X)

      • modOddIsCoprimeVar

        public static boolean modOddIsCoprimeVar​(java.math.BigInteger M,
                                         java.math.BigInteger X)

      • getUnsignedByteLength

        public static int getUnsignedByteLength​(java.math.BigInteger n)

      • createRandomBigInteger

        public static java.math.BigInteger createRandomBigInteger​(int bitLength,
                                                          java.security.SecureRandom random)
        Return a positive BigInteger in the range of 0 to 2**bitLength - 1.
        Parameters:
        bitLength - maximum bit length for the generated BigInteger.
        random - a source of randomness.
        Returns:
        a positive BigInteger

      • createBlindedExponent

        public static java.math.BigInteger createBlindedExponent​(java.math.BigInteger exponent,
                                                         java.math.BigInteger groupOrder,
                                                         java.security.SecureRandom random)
        Return a private exponent randomised for use in a variable-time modular exponentiation.

        BigInteger.modPow(BigInteger, BigInteger) carries no constant-time guarantee and its running time varies with the exponent, so where an exponent carries long-term secret material and the base is chosen by a peer, the exponent should be randomised before each use. This returns exponent + c * groupOrder for a small random c, which does not change the result of the exponentiation because basegroupOrder = 1.

        The caller owns that premise, and it is the easy thing to get wrong. The order must be one the base actually has:

        • Pass the subgroup order q only when the base is known to lie in that subgroup - a domain generator g chosen with gq = 1, or a peer value that has been verified with vq = 1.
        • Pass p-1 for a caller- or peer-supplied base that has only been range-checked. Any value coprime to a prime p satisfies basep-1 = 1 by Fermat, so this always holds.
        • Pass phi(n) for a composite modulus, which only the private-key holder can do.
        Passing q for a base outside the order-q subgroup silently returns the wrong answer for an odd multiple - for a safe prime that is roughly half of the range-valid bases - and no known-answer test will catch it, since the randomisation is otherwise result-preserving.

        What this does and does not buy. The multiple is small - between 128 and 255 times groupOrder, drawn from seven random bits - so it lengthens the exponent by exactly eight bits rather than doubling the work, and every call raises a different exponent of the same length. That is aimed squarely at what BigInteger.modPow(BigInteger, BigInteger) leaks about the exponent it is handed: the bit length and the bit pattern, which drive the number of squarings and multiplications. After blinding, no single operation is performed on the private exponent itself, so an adversary reading one trace - or a handful - no longer reads its bits.

        It is not, however, a constant-time exponentiation, and it is not a substitute for one. Two limits are worth being explicit about:

        • Seven bits give only 128 distinct blinded exponents for a given exponent and order. An adversary who can measure many operations under the same long-term exponent can average over that space, which is small enough to enumerate. This raises the cost of a repeated-measurement attack; it does not remove it. Where an exponent is long lived and the operation can be triggered and timed at will - static-static agreement, or signing on demand - treat that as the residual risk, and prefer a primitive with a real constant-time guarantee if one exists for the algorithm.
        • Only the exponent is randomised. The base and the modulus reach modPow unchanged, so any leakage that depends on them - the windowing table modPow builds from the base, for one - is unaffected. That is the right trade for the protocols this is used in, where the base is a public or peer-supplied value and the exponent is the secret, but it is not a general side-channel defence for the exponentiation.
        Parameters:
        exponent - the private exponent to randomise.
        groupOrder - an order the base is raised to giving 1 - see above.
        random - a source of randomness.
        Returns:
        exponent plus a random multiple of groupOrder.

      • createRandomPrime

        public static java.math.BigInteger createRandomPrime​(int bitLength,
                                                     int certainty,
                                                     java.security.SecureRandom random)
        Return a prime number candidate of the specified bit length.
        Parameters:
        bitLength - bit length for the generated BigInteger.
        random - a source of randomness.
        Returns:
        a positive BigInteger of numBits length

      • writeUnsignedByteArray

        public static void writeUnsignedByteArray​(java.io.OutputStream out,
                                          java.math.BigInteger n)
                                   throws java.io.IOException
        Throws:
        java.io.IOException