BitShifting with BigIntegers in Java

Question

I am implementing DES Encryption in Java with use of BigIntegers.

I am left shifting binary keys with Java BigIntegers by doing the BigInteger.leftShift(int n) method. Key of N (Kn) is dependent on the result of the shift of Kn-1. The problem I am getting is that I am printing out the results after each key is generated and the shifting is not the expected out put. The key is split in 2 Cn and Dn (left and right respectively).

I am specifically attempting this: "To do a left shift, move each bit one place to the left, except for the first bit, which is cycled to the end of the block. "

It seems to tack on O's on the end depending on the shift. Not sure how to go about correcting this.

Results:

c0: 11110101010100110011000011110

d0: 11110001111001100110101010100

c1: 111101010101001100110000111100

d1: 111100011110011001101010101000

c2: 11110101010100110011000011110000

d2: 11110001111001100110101010100000

c3: 1111010101010011001100001111000000

d3: 1111000111100110011010101010000000

c4: 111101010101001100110000111100000000

d4: 111100011110011001101010101000000000

c5: 11110101010100110011000011110000000000

d5: 11110001111001100110101010100000000000

c6: 1111010101010011001100001111000000000000

d6: 1111000111100110011010101010000000000000

c7: 111101010101001100110000111100000000000000

d7: 111100011110011001101010101000000000000000

c8: 1111010101010011001100001111000000000000000

d8: 1111000111100110011010101010000000000000000

c9: 111101010101001100110000111100000000000000000

d9: 111100011110011001101010101000000000000000000

c10: 11110101010100110011000011110000000000000000000

d10: 11110001111001100110101010100000000000000000000

c11: 1111010101010011001100001111000000000000000000000

d11: 1111000111100110011010101010000000000000000000000

c12: 111101010101001100110000111100000000000000000000000

d12: 111100011110011001101010101000000000000000000000000

c13: 11110101010100110011000011110000000000000000000000000

d13: 11110001111001100110101010100000000000000000000000000

c14: 1111010101010011001100001111000000000000000000000000000

d14: 1111000111100110011010101010000000000000000000000000000

c15: 11110101010100110011000011110000000000000000000000000000

d15: 11110001111001100110101010100000000000000000000000000000

Daron

Answer 1

BigInteger implements infinite-precision integers, so shifting to the left will keep adding zeros to the left. You need a rotate:

private static BigInteger rotateLeft(BigInteger bi) {
    BigInteger ret = bi.shiftLeft(1);
    if (ret.testBit(32)) {
        ret = ret.clearBit(32).setBit(0);
    }
    return ret;
}

That's going to be rather inefficient for 32-bit numbers, so you might as well just use primitives to rotate DES' 28-bit halves. I'm not familiar with the DES algorithm, so I'll assume you need BigInteger for something else.

private static BigInteger rotateLeftPrimitive(BigInteger bi) {
    int value = bi.intValue();
    return BigInteger.valueOf(((value << 1) & 0xffffffe) | ((value >>> 27) & 1));
}

Integument

Isn't this limited precision, though? What if bi has 100 bits? – Serif

Yes, it is limited precision. However, c0 is 29 bits and c15 is 56, so I assumed that the user wanted some precision less than 64. Checking Wiki for the DES algorithm, I see that 28-bit halves are rotated in that algorithm, so I've updated my answer. Thanks. – Integument

Answer 2

It seems that you need a cyclic left shift. BigInteger.shiftLeft is not cyclic. You'd have to combine shiftLeft, shiftRight, and and or, just like you would if you were using int and <<.

static BigInteger allOnes(int L) {
    return BigInteger.ZERO
        .setBit(L)
        .subtract(BigInteger.ONE);
}

static BigInteger cyclicLeftShift(BigInteger n, int L, int k) {
    return n.shiftLeft(k)
        .or(n.shiftRight(L - k))
        .and(allOnes(L));
}

Now, cyclicLeftShift(n, L, k) returns n cyclically-shifted k bits to the left, where the cycle window is L.

How this works is as follows:

                               _________L__________
                              /                    \
n :                           [ABCDE][FG...........]
                              \__k__/\_____L-k_____/



n.shiftLeft(k) :       [ABCDE][FG...........][00000]
   .or
n.shiftRight(L - k) :                        [ABCDE]

   =                   [ABCDE][FG...........][ABCDE]

                               _________L__________
   .and                       /                    \
allOnes(L) :                  [111..............111]

   =                          [FG...........][ABCDE]

See also

• http://en.wikipedia.org/wiki/Circular_shift

---

Note: if you have a fixed L, you can optimize this a bit by caching allOnes(L) instead of computing it every time.

Serif

No, this does not work for the reason he posted: the infinite-precision BigInteger will keep adding 0's to the right. Your algorithm needs an and(BigInteger.valueOf(0xffffffffL). – Integument

No, the algorithms still do not work for arbitrary-precision integers because they require the high bit be set. For example, repeatedly applying cyclicLeftShift to BigInteger.valueOf(1) always returns 1, which is surely not intended. Sorry, but down-voting this time. Fix to allow the user to pass in L, and I'll remove. – Integument

@bkail: I admit that I don't understand the application (DES?) but that was what I was going for. I realized now that a fixed cycle window may be what OP needed, so I've clarified that in my answer. Thanks for feedback. – Serif

Removed the downvote. I believe he's implementing this: en.wikipedia.org/wiki/Data_Encryption_Standard – Integument

Answer 3

Addressing the bigger question 1) DES is broken and should never be used for anything other than working with legacy systems, 2) the Sun JCE already provides an implementation (as does BouncyCastle and other crypto providers), and 3) implementing any crypto algorithm is challenging and you really want to go with a well-tested implementation for production use.

If it's a class exercise I would use a byte[] instead of a BigInteger. You'll need to do a little bit more by hand but it's a lot closer to the spirit of DES since it was designed to be easily implemented in hardware.

Speleology

Answer 4

I think your idea of implementing DES using bit strings is reasonable as an educational tool. Instead of directly using BigIntegers to represent these bitstrings, I recommend you create a BitString class that implements exactly those bit string methods you need for your project. Inside the BitString class, you can use BigIntegers, but you may find that a simple int array with 1 bit per array element is just as easy or easier, or maybe a linked list.

Timeconsuming