1b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallampackage org.bouncycastle.util; 2b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 3b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallamimport java.math.BigInteger; 4c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstromimport java.security.SecureRandom; 5b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 6b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam/** 7b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam * BigInteger utilities. 8b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam */ 9b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallampublic final class BigIntegers 10b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam{ 11c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom private static final int MAX_ITERATIONS = 1000; 12c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom private static final BigInteger ZERO = BigInteger.valueOf(0); 13c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 14b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam /** 15b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam * Return the passed in value as an unsigned byte array. 16b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam * 17b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam * @param value value to be converted. 18b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam * @return a byte array without a leading zero byte if present in the signed encoding. 19b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam */ 20b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam public static byte[] asUnsignedByteArray( 21b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam BigInteger value) 22b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 23b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam byte[] bytes = value.toByteArray(); 24b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 25b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam if (bytes[0] == 0) 26b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 27b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam byte[] tmp = new byte[bytes.length - 1]; 28b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 29b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam System.arraycopy(bytes, 1, tmp, 0, tmp.length); 30b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 31b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam return tmp; 32b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 33b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 34b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam return bytes; 35b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 36c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 37c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom /** 3870c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom * Return the passed in value as an unsigned byte array. 3970c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom * 4070c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom * @param value value to be converted. 4170c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom * @return a byte array without a leading zero byte if present in the signed encoding. 4270c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom */ 4370c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom public static byte[] asUnsignedByteArray( 4470c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom int length, 4570c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom BigInteger value) 4670c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom { 4770c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom byte[] bytes = value.toByteArray(); 4870c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom 4970c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom if (bytes[0] == 0) 5070c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom { 5170c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom if (bytes.length - 1 > length) 5270c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom { 5370c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom throw new IllegalArgumentException("standard length exceeded for value"); 5470c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom } 5570c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom 5670c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom byte[] tmp = new byte[length]; 5770c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom 5870c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom System.arraycopy(bytes, 1, tmp, tmp.length - (bytes.length - 1), bytes.length - 1); 5970c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom 6070c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom return tmp; 6170c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom } 6270c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom else 6370c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom { 6470c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom if (bytes.length == length) 6570c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom { 6670c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom return bytes; 6770c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom } 6870c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom 6970c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom if (bytes.length > length) 7070c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom { 7170c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom throw new IllegalArgumentException("standard length exceeded for value"); 7270c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom } 7370c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom 7470c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom byte[] tmp = new byte[length]; 7570c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom 7670c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom System.arraycopy(bytes, 0, tmp, tmp.length - bytes.length, bytes.length); 7770c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom 7870c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom return tmp; 7970c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom } 8070c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom } 8170c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom 8270c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom /** 83c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom * Return a random BigInteger not less than 'min' and not greater than 'max' 84c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom * 85c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom * @param min the least value that may be generated 86c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom * @param max the greatest value that may be generated 87c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom * @param random the source of randomness 88c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom * @return a random BigInteger value in the range [min,max] 89c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom */ 90c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom public static BigInteger createRandomInRange( 91c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom BigInteger min, 92c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom BigInteger max, 93c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom SecureRandom random) 94c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 95c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom int cmp = min.compareTo(max); 96c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom if (cmp >= 0) 97c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 98c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom if (cmp > 0) 99c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 100c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom throw new IllegalArgumentException("'min' may not be greater than 'max'"); 101c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 102c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 103c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom return min; 104c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 105c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 106c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom if (min.bitLength() > max.bitLength() / 2) 107c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 108c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom return createRandomInRange(ZERO, max.subtract(min), random).add(min); 109c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 110c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 111c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom for (int i = 0; i < MAX_ITERATIONS; ++i) 112c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 113c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom BigInteger x = new BigInteger(max.bitLength(), random); 114c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom if (x.compareTo(min) >= 0 && x.compareTo(max) <= 0) 115c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 116c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom return x; 117c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 118c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 119c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 120c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom // fall back to a faster (restricted) method 121c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom return new BigInteger(max.subtract(min).bitLength() - 1, random).add(min); 122c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 123b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam} 124