Java BigInteger 内存不足，可能来自长转换

Question

我正在尝试将此 KeeLoq 算法从 C 语言转换为 Java，但我的解密方法似乎对 Java 的 BigInteger 使用了太多内存。我想知道是否存在适用于 Java 的 BigInteger 的等效操作。

index 和 bitVal 变量的原始计算在下面注释掉了。

我用作示例的原始源代码可以在这里找到: https://github.com/franksmicro/Arduino/blob/master/libraries/Keeloq/Keeloq.cpp

如有任何帮助，我们将不胜感激。

package keeloq;

/**
 *
 * @author 
 */
import java.math.BigInteger;

public class KeeLoq {

    BigInteger _keyHigh, _keyLow, keyHigh, keyLow;
    int KeeLoq_code = 0x3A5C742E;
    BigInteger KeeLoq_NLF = new BigInteger(Integer.toString(KeeLoq_code));

    public KeeLoq() {
    }

    public KeeLoq(BigInteger keyHigh, BigInteger keyLow) {
        _keyHigh = keyHigh;
        _keyLow = keyLow;
    }

    public BigInteger bitRead(BigInteger x, int n) {
        BigInteger temp = x.shiftRight(n);
        return temp;
    }

    public BigInteger multiplyBig(BigInteger x, BigInteger n) {
        BigInteger temp = x.multiply(n);
        return temp;
    }

    public BigInteger Encrypt(BigInteger data) {
        BigInteger x = data;
        int keyBitNo;
        long index;
        long position1, position2, position3, position4, position5;
        BigInteger keyBitVal, bitVal;
        BigInteger b1, b2, b3, b4, b5;

        for (int r = 0; r < 528; r++) {
            keyBitNo = r & 63;
            if (keyBitNo < 32) {
                keyBitVal = bitRead(_keyLow, keyBitNo);
            } else {
                keyBitVal = bitRead(_keyHigh, keyBitNo - 32);
            }

            position1 = bitRead(x, 1).longValue() * 1;
            position2 = bitRead(x, 9).longValue() * 2;
            position3 = bitRead(x, 20).longValue() * 4;
            position4 = bitRead(x, 26).longValue() * 8;
            position5 = bitRead(x, 31).longValue() * 16;

            index = position1 + position2 + position3 + position4 + position5;
            System.out.println("the encrypted index is " + index);

            b1 = bitRead(x, 0);
            b2 = bitRead(x, 16);
            int intIndex = (int) index;
            b3 = bitRead(KeeLoq_NLF, intIndex);
            b4 = keyBitVal;

            bitVal = b1.xor(b2).xor(b3).xor(b4);
            BigInteger tempx = x.shiftRight(1);
            x = tempx.xor(bitVal);
                        //bitVal = bitRead(x,0) ^ bitRead(x, 16) ^ bitRead(KeeLoq_NLF,index) ^ keyBitVal;
            //x = (x>>1) ^ bitVal<<31;
        }
        return x;
    }

    BigInteger Decrypt(BigInteger data) {
        BigInteger x = data;
        int keyBitNo;
        long index;
        long position1, position2, position3, position4, position5;
        BigInteger keyBitVal, bitVal;
        BigInteger b1, b2, b3, b4, b5;

        for (int r = 0; r < 528; r++) {
            keyBitNo = (15 - r) & 63;
            if (keyBitNo < 32) {
                keyBitVal = bitRead(_keyLow, keyBitNo);
            } else {
                keyBitVal = bitRead(_keyHigh, keyBitNo - 32);
            }

            position1 = bitRead(x, 0).longValue() * 1;
            position2 = bitRead(x, 8).longValue() * 2;
            position3 = bitRead(x, 19).longValue() * 4;
            position4 = bitRead(x, 25).longValue() * 8;
            position5 = bitRead(x, 30).longValue() * 16;

            index = position1 + position2 + position3 + position4 + position5;

            System.out.println("The Decrypted index is " + index);

            b1 = bitRead(x, 31);
            b2 = bitRead(x, 15);
            int intIndex = (int) index;
            b3 = bitRead(KeeLoq_NLF, intIndex);
            b4 = keyBitVal;

            bitVal = b1.xor(b2).xor(b3).xor(b4);
            BigInteger tempx = x.shiftLeft(1);
            x = tempx.xor(bitVal);


            //index = 1 * bitRead(x,0) + 2 * bitRead(x,8) + 4 * bitRead(x,19) + 8 * bitRead(x,25) + 16 * bitRead(x,30);
            // bitVal = bitRead(x,31) ^ bitRead(x, 15) ^ bitRead(KeeLoq_NLF,index) ^ keyBitVal;
            //   x = (x<<1) ^ bitVal;


        }
        return x;
    }

    public static void main(String[] args) {
        BigInteger highKey = new BigInteger(Integer.toString(66));
        BigInteger lowKey = new BigInteger(Integer.toString(35));
        KeeLoq KeeLoq_file = new KeeLoq(highKey, lowKey);
        System.out.println("The KeeLoq Code is " + KeeLoq_file.KeeLoq_code);
        BigInteger EncryptedBigInt = KeeLoq_file.Encrypt(KeeLoq_file.KeeLoq_NLF);
        System.out.println("The Encrypted BigIntegerValue is " + EncryptedBigInt);
        System.out.println("The Encrypted integer value is " + EncryptedBigInt.intValue());
        BigInteger DecryptedBigInt = KeeLoq_file.Decrypt(EncryptedBigInt);
        System.out.println("The Decrypted BigIntegerValue is " + DecryptedBigInt);
        System.out.println("The Decrypted integer value is " + DecryptedBigInt.intValue());
    }

}

Answer 1

编辑:我想我明白了! (或至少其中的一部分)

问题至少部分在这一行:(一开始弄错了行，抱歉)

 int intIndex = (int) index;

当 index 足够大时，(int) index 将溢出到一个很大的负值。猜猜当您将其传递给 bitRead() 时会发生什么？

现在，为什么这个溢出发生在 Decrypt() 中而不是 Encrypt() 中，我不确定......我会在稍后查看再休息一下，但希望这是一个开始。

您可以通过使用 -Xmx 标志运行程序来增加可用内存空间。例如，要使用最大 4 GB 的内存运行，您将使用 -Xmx4G

在 Eclipse 中，这可以通过右键单击文件进行设置，转到属性 --> 运行/调试设置 --> 单击启动配置 --> 编辑 --> 参数选项卡 --> VM 参数--> 输入标志。

如果您使用 Java 的 BigInteger 类内存不足，我不确定使用任何其他任意精度库是否可以让您在数字实际变得那么大的情况下走得很远。