我被要求为我的RSA加密算法创建512位整数类型.我从最简单的按位操作开始OR, AND, XOR, NOT
,然后使用提到的操作我实现了加法,减法等.不幸的是,经过多次测试,它在超过128位时非常慢.
当我发现具有RSA生成的站点时,我很惊讶它在几毫秒内使用明显的javascript生成密钥.如何改进算法以提高效率?或者更好的问题是:专业人士如何实现具有这种表现的如此大的类型.
这是我的代码:
public class BigInt { public static final int BYTE = 8; public static final int DEFAULT_SIZE = 128; public final static BigInt ZERO = new BigInt(0); public final static BigInt ONE = new BigInt(1); public final static BigInt TEN = new BigInt(10); private boolean[] number; private Endianness endianness = Endianness.BIG_ENDIAN; public BigInt() { number = new boolean[DEFAULT_SIZE]; } public BigInt(boolean[] number) { this.number = number; } public BigInt(int integerNumber) { this(); boolean isNegative = false; if (integerNumber < 0) { isNegative = true; integerNumber = Math.abs(integerNumber); } for (int i = number.length - 1; i >= 1 && integerNumber >= 1; i--) { number[i] = integerNumber % 2 == 1; integerNumber >>= 1; } if (isNegative) { number = new BigInt(number).not().add(ONE).number; } } public BigInt(String binaryString) throws InvalidBinaryStringException { this(); for (int i = binaryString.length() - 1, j = number.length - 1; i >= 0 && j >= 0; i--, j--) { if (binaryString.charAt(i) != '1' && binaryString.charAt(i) != '0') { throw new InvalidBinaryStringException(binaryString); } number[j] = (binaryString.charAt(i) - '0') == 1; } } public BigInt(BigInt copy) { this(); System.arraycopy(copy.number, 0, number, 0, copy.number.length); } public BigInt add(BigInt component) { BigInt a, b; BigInt x = new BigInt(this); BigInt y = new BigInt(component); do { a = x.and(y); b = x.xor(y); x = a.shiftLeft(1); y = b; } while (!a.equals(ZERO)); return b; } public BigInt sub(BigInt subtrahend) { return add(subtrahend.not().add(new BigInt(ONE))); } public BigInt mul(BigInt multiplier) { BigInt m = new BigInt(ONE), z = new BigInt(ZERO); BigInt x = new BigInt(this), y = new BigInt(multiplier); if (x.lessThen(ZERO)) { x = x.not().add(ONE); y = y.not().add(ONE); } while (x.greaterThenEqual(m) && !y.equals(ZERO)) { if (!x.and(m).equals(ZERO)) { z = y.add(z); } y = y.shiftLeft(1); m = m.shiftLeft(1); } return z; } public BigInt div(BigInt divisor) { BigInt mask = new BigInt(ONE); BigInt quotient = new BigInt(ZERO); BigInt numerator = new BigInt(this), denominator = new BigInt(divisor); if (numerator.lessThen(ZERO)) { numerator = numerator.not().add(ONE); } if (denominator.lessThen(ZERO)) { denominator = denominator.not().add(ONE); } while (denominator.lessThenEqual(numerator)) { // PROBLEM denominator = denominator.shiftLeft(1); mask = mask.shiftLeft(1); } while (mask.greaterThen(ONE)) { denominator = denominator.shiftRight(1); mask = mask.shiftRight(1); if (numerator.greaterThenEqual(denominator)) { numerator = numerator.sub(denominator); quotient = quotient.or(mask); } } if (number[0] != divisor.number[0]) { return quotient.not().add(ONE); } return quotient; } public BigInt mod(BigInt y) { // (x - y*(x/y)) BigInt x = new BigInt(this); BigInt right = x.div(y); BigInt mid = y.mul(right); return x.sub(mid); } //completly inefficient for numbers larger than 32 bit @Deprecated public BigInt div2(BigInt divisor) { BigInt c = new BigInt(ZERO), sign = new BigInt(ZERO); BigInt x = new BigInt(this), y = new BigInt(divisor); if (x.lessThen(ZERO)) { x = x.not().add(ONE); sign = sign.xor(ONE); } if (y.lessThen(ZERO)) { y = y.not().add(ONE); sign = sign.xor(ONE); } if (!y.equals(ZERO)) { while (x.greaterThenEqual(y)) { x = x.sub(y); c = c.add(ONE); } } if (!sign.equals(ZERO)) { c = c.not().add(ONE); } return c; } //doesn't work for big numbers close to maximum bit @Deprecated public BigInt mod2(BigInt mod) { BigInt y = new BigInt(this); BigInt x = new BigInt(mod); BigInt p = new BigInt(x); if (y.lessThen(ZERO)) { y = y.not().add(ONE); } if (p.lessThen(ZERO)) { p = p.not().add(ONE); x = x.not().add(ONE); } while (p.lessThen(y)) { //forever loop p = p.shiftLeft(1); } while (p.greaterThenEqual(x)) { if (y.greaterThenEqual(p)) { y = y.sub(p); } p = p.shiftRight(1); } if (number[0]) { y = y.not().add(ONE); } return y; } @Override public boolean equals(Object obj) { if (obj == null) return false; if (obj == this) return true; if (!(obj instanceof BigInt)) return false; BigInt bigInt = (BigInt) obj; for (int i = 0; i < bigInt.number.length; i++) { if (number[i] != bigInt.number[i]) { return false; } } if (!endianness.equals(bigInt.endianness)) { return false; } return true; } public boolean lessThen(BigInt num) { if (equals(num)) { return false; } if (number[0] && !num.number[0]) { return true; } else if (!number[0] && num.number[0]) { return false; } BigInt left = null, right = null; if (number[0]) { left = not().add(ONE); right = num.not().add(ONE); } else { left = this; right = num; } for (int i = 1; i < number.length; i++) { if (left.number[i] != right.number[i]) { if (number[0]) { return !(!left.number[i] && right.number[i]); } else { return !left.number[i] && right.number[i]; } } } return false; } public boolean lessThenEqual(BigInt num) { if (equals(num)) { return true; } return lessThen(num); } public boolean greaterThen(BigInt num) { return !lessThen(num); } public boolean greaterThenEqual(BigInt num) { if (equals(num)) { return true; } return greaterThen(num); } /** * BITWISE OPERATORS* */ //logical bitwise shift lefts public BigInt shiftLeft(int n) { //IT WORKS BECAUSE NEW OBJECT IS SET TO 0; BigInt shifted = new BigInt(); for (int i = 0; i < number.length - n; i++) { shifted.number[i] = number[i + n]; } return shifted; } //logical bitwise shift right public BigInt shiftRight(int n) { BigInt shifted = new BigInt(); for (int i = number.length - 1; i >= n; i--) { shifted.number[i] = number[i - n]; } boolean sign = number[0]; for (int i = 0; i < n; i++) { shifted.number[i] = sign; } return shifted; } //bitwise or | public BigInt or(BigInt num) { BigInt newInt = new BigInt(); for (int i = 0; i < number.length; i++) { newInt.number[i] = number[i] | num.number[i]; } return newInt; } //bitwise and & public BigInt and(BigInt num) { BigInt newInt = new BigInt(); for (int i = 0; i < number.length; i++) { newInt.number[i] = number[i] & num.number[i]; } return newInt; } //bitwise exclusive or ^ public BigInt xor(BigInt num) { BigInt newInt = new BigInt(); for (int i = 0; i < number.length; i++) { newInt.number[i] = number[i] ^ num.number[i]; } return newInt; } public BigInt not() { BigInt negate = new BigInt(); for (int i = 0; i < number.length; i++) { negate.number[i] = !number[i]; } return negate; } @Override public String toString() { /* StringBuilder binaryRepr = new StringBuilder(); for (byte b : number) { binaryRepr.append(b); }*/ String decRepr = ""; BigInt copy = new BigInt(this); if (copy.lessThen(ZERO)) { copy = copy.not().add(ONE); } while (copy.greaterThenEqual(ONE)) { BigInt rem = copy.mod(TEN); copy = copy.div(TEN); decRepr = String.valueOf(Integer.parseInt(getDecimalRemainder(rem), 2)) + decRepr; } if (number[0]) { return "-" + decRepr;// + binaryRepr.toString(); } return decRepr;// + binaryRepr.toString(); //return binaryRepr.toString(); } private String getDecimalRemainder(BigInt copy) { String decimalString = ""; for (int i = copy.number.length - 1; i >= copy.number.length - 4; i--) { decimalString = (copy.number[i] ? "1" : "0") + decimalString; } return decimalString; } public String toBinaryString() { StringBuilder binaryString = new StringBuilder(); boolean isFirstBit = false; for (boolean b: number) { if (b) { isFirstBit = true; } if (isFirstBit) { binaryString.append(b); } } return binaryString.toString(); } public static BigInt nextBigInt(BigInt min, BigInt max) { BigInt pseudo = new BigInt(); Random rnd = new Random(); for (int i = 2; i < pseudo.number.length; i++) { pseudo.number[i] = rnd.nextBoolean(); } return pseudo.mod(max).add(min); } public static void main(String[] args) { String big = ""; for(int i = 0; i < 126; i++) { big += "1"; } StopWatch stopWatch = new StopWatch(); System.out.println(new BigInt(big)); System.out.println(stopWatch.elapsedTime()); } }
Henry.. 6
而不是boolean[]
使用一个int[]
来保存你的数字位.这样,您可以更快地实现大多数操作,一次操作30位而不是1位.
您可以将数组元素0中的最低30位保留在数组元素1中的下30位,依此类推.使用这种结构实现逻辑运算(&,|,^)是很简单的.
对于算术运算,您必须跟踪进位.例如,在添加两个数组元素0之后,如果结果大于30位,则清除溢出位并将1添加到数组元素1的总和.
乘法可以通过使用long
:两个int
值的乘积总是适合a long
.使用手动乘以两个十进制数的方法.只需使用30位数字而不是数字0-9.
像karatsuba这样的更复杂的乘法方法不能为只有512位长的数字付出代价.
虽然实现和优化这些操作很有趣,但在实现中也很容易出现细微的错误.因此,如果您为生产代码执行此操作,请确保编写大量单元测试.使用经过良好测试的第三方实现可能更好,而不是自己做.
而不是boolean[]
使用一个int[]
来保存你的数字位.这样,您可以更快地实现大多数操作,一次操作30位而不是1位.
您可以将数组元素0中的最低30位保留在数组元素1中的下30位,依此类推.使用这种结构实现逻辑运算(&,|,^)是很简单的.
对于算术运算,您必须跟踪进位.例如,在添加两个数组元素0之后,如果结果大于30位,则清除溢出位并将1添加到数组元素1的总和.
乘法可以通过使用long
:两个int
值的乘积总是适合a long
.使用手动乘以两个十进制数的方法.只需使用30位数字而不是数字0-9.
像karatsuba这样的更复杂的乘法方法不能为只有512位长的数字付出代价.
虽然实现和优化这些操作很有趣,但在实现中也很容易出现细微的错误.因此,如果您为生产代码执行此操作,请确保编写大量单元测试.使用经过良好测试的第三方实现可能更好,而不是自己做.