org.bouncycastle.util

Class BigIntegers

java.lang.Object

org.bouncycastle.util.BigIntegers

public final class BigIntegers
extends java.lang.Object

BigInteger utilities.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	BigIntegers.Cache

Field Summary

Fields

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

Constructor Summary

Constructors

Constructor and Description
BigIntegers()

Method Summary

Modifier and Type	Method and 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(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[]	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	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