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 */ 435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public static byte[] asUnsignedByteArray(int length, BigInteger value) 4470c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom { 4570c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom byte[] bytes = value.toByteArray(); 465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (bytes.length == length) 4770c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom { 485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return bytes; 4970c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom } 5070c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom 515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int start = bytes[0] == 0 ? 1 : 0; 525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int count = bytes.length - start; 5370c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom 545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (count > length) 555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root throw new IllegalArgumentException("standard length exceeded for value"); 5770c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom } 585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root byte[] tmp = new byte[length]; 605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root System.arraycopy(bytes, start, tmp, tmp.length - count, count); 615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return tmp; 6270c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom } 6370c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom 6470c8287138e69a98c2f950036f9f703ee37228c8Brian Carlstrom /** 65c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom * Return a random BigInteger not less than 'min' and not greater than 'max' 66c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom * 67c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom * @param min the least value that may be generated 68c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom * @param max the greatest value that may be generated 69c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom * @param random the source of randomness 70c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom * @return a random BigInteger value in the range [min,max] 71c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom */ 72c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom public static BigInteger createRandomInRange( 73c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom BigInteger min, 74c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom BigInteger max, 75c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom SecureRandom random) 76c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 77c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom int cmp = min.compareTo(max); 78c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom if (cmp >= 0) 79c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 80c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom if (cmp > 0) 81c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 82c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom throw new IllegalArgumentException("'min' may not be greater than 'max'"); 83c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 84c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 85c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom return min; 86c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 87c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 88c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom if (min.bitLength() > max.bitLength() / 2) 89c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 90c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom return createRandomInRange(ZERO, max.subtract(min), random).add(min); 91c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 92c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 93c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom for (int i = 0; i < MAX_ITERATIONS; ++i) 94c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 95c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom BigInteger x = new BigInteger(max.bitLength(), random); 96c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom if (x.compareTo(min) >= 0 && x.compareTo(max) <= 0) 97c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 98c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom return x; 99c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 100c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 101c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 102c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom // fall back to a faster (restricted) method 103c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom return new BigInteger(max.subtract(min).bitLength() - 1, random).add(min); 104c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 1055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 1065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public static BigInteger fromUnsignedByteArray(byte[] buf) 1075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 1085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new BigInteger(1, buf); 1095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 1105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 1115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public static BigInteger fromUnsignedByteArray(byte[] buf, int off, int length) 1125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 1135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root byte[] mag = buf; 1145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (off != 0 || length != buf.length) 1155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 1165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root mag = new byte[length]; 1175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root System.arraycopy(buf, off, mag, 0, length); 1185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 1195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new BigInteger(1, mag); 1205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 121b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam} 122