BitShifting with BigIntegers in Java

Question

I am using DES Encryption in Java using BigIntegers.

I transfer binary keys using Java BigIntegers by executing the BigInteger.leftShift (int n) method. The key N (Kn) depends on the result of the Kn-1 shift. The problem I get is that I print out the results after creating each key, and the offset is not expected. The key is divided into 2 Cn and Dn (left and right, respectively).

I specifically try to do this: "To make a left shift, move each bit one place to the left, except for the first bit, which will cyclically move to the end of the block."

It seems to be superimposed on O at the end depending on the shift. Not sure how to fix it.

Results:

c0: 11110101010100110011000011110

d0: 11110001111001100110101010100

c1: 11110101010101001100110000111100

d1: 111100011110011001101010101000

c2: 11110101010100110011000011110000

d2: 11110001111001100110101010100000

c3: 111101010101010011001100001111000000

d3: 1111000111100110011010101010000000

c4: 111101010101001100110000111100000000

d4: 111100011110011001101010101000000000

c5: 11110101010100110011000011110000000000

d5: 111100011110011001101010101000000000000000

c6: 1111010101010011001100001111000000000000

d6: 1111000111100110011010101010000000000000

c7: 11110101010101001100110000111100000000000000

d7: 1111000111100110011010101010000000000000000000

c8: 1111010101010011001100001111000000000000000

d8: 11110001111001100110101010100000000000000000000

c9: 11110101010101001100110000111100000000000000000

d9: 1111000111100110011010101010000000000000000000000

c10: 1111010101010100110011000011110000000000000000000

d10: 111100011110011001101010101000000000000000000000000

c11: 111101010101010011001100001111000000000000000000000

d11: 11110001111001100110101010100000000000000000000000000

c12: 11110101010101001100110000111100000000000000000000000000

d12: 1111000111100110011010101010000000000000000000000000000

c13: 1111010101010100110011000011110000000000000000000000000

d13: 111100011110011001101010101000000000000000000000000000000

c14: 111101010101010011001100001111000000000000000000000000000000

d14: 11110001111001100110101010100000000000000000000000000000000

c15: 11110101010101001100110000111100000000000000000000000000000000

d15: 111100011110011001101010101000000000000000000000000000000000

Answer 1

BigInteger implements infinite precision integers, so a left shift will continue to add zeros to the left. You need to rotate:

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

This will be pretty inefficient for 32-bit numbers, so you can just use the primitives to rotate the 28-bit DES partitions. I am not familiar with the DES algorithm, so I 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)); } 

Answer 2

It seems you need a cyclic left shift. BigInteger.shiftLeft not circular. You would need to combine shiftLeft , shiftRight , and and or , as 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 loop window is L

How it works:

  _________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 it a bit by caching allOnes(L) rather than calculating it every time.

Answer 3

The solution to the bigger question 1) DES is broken and should never be used for anything other than working with legacy systems, 2) Sun JCE already provides an implementation (like BouncyCastle and other crypto resources) and 3) introduces any crypto algorithm is complicated, and you really want to go with a proven implementation for use in production.

If this is a class exercise, I would use byte [] instead of BigInteger. You will need to do a little work, but it is much closer to the DES spirit, as it was designed so that it can be easily implemented in hardware.

Answer 4

I think your idea of ​​implementing DES using bit strings is a smart learning tool. Instead of directly using BigIntegers to represent these bitstrings, I recommend that you create a BitString class that implements exactly the bitstring methods that 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 as simple or lightweight, or possibly a linked list.