Class BigIntegers

java.lang.Object
org.bouncycastle.util.BigIntegers
public final class BigIntegers extends Object
BigInteger utilities.

  • Field Details

  • Constructor Details

    • BigIntegers

      public BigIntegers()

  • Method Details

    • asUnsignedByteArray

      public static byte[] asUnsignedByteArray(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, 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(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 BigInteger createRandomInRange(BigInteger min, BigInteger max, 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 BigInteger fromUnsignedByteArray(byte[] buf)

    • fromUnsignedByteArray

      public static BigInteger fromUnsignedByteArray(byte[] buf, int off, int length)

    • byteValueExact

      public static byte byteValueExact(BigInteger x)

    • shortValueExact

      public static short shortValueExact(BigInteger x)

    • intValueExact

      public static int intValueExact(BigInteger x)

    • longValueExact

      public static long longValueExact(BigInteger x)

    • areSecretValuesEqual

      public static boolean areSecretValuesEqual(int maxLen, BigInteger a, 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(BigInteger x)

    • modAdd

      public static BigInteger modAdd(BigInteger M, BigInteger X, 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.

    • modMult

      public static BigInteger modMult(BigInteger M, BigInteger X, 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 BigInteger modOddInverse(BigInteger M, BigInteger X)

    • modOddInverseVar

      public static BigInteger modOddInverseVar(BigInteger M, BigInteger X)

    • modOddIsCoprime

      public static boolean modOddIsCoprime(BigInteger M, BigInteger X)

    • modOddIsCoprimeVar

      public static boolean modOddIsCoprimeVar(BigInteger M, BigInteger X)

    • getUnsignedByteLength

      public static int getUnsignedByteLength(BigInteger n)

    • createRandomBigInteger

      public static BigInteger createRandomBigInteger(int bitLength, 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 BigInteger createBlindedExponent(BigInteger exponent, BigInteger groupOrder, 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 BigInteger createRandomPrime(int bitLength, int certainty, 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(OutputStream out, BigInteger n) throws IOException
      Throws:
      IOException