Problem with Linear Transformation method in Cipher program

[Christina Arsenault]

We have to write a cipher program for an assignment. Here's the code for it, it has been documented. The input we are using is {10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160}. The output is meant to be {127,178,145,50,74,59,90,63,36,168,182,106,211,94,8,188} after two rounds. We are not getting the right output and we have determined that the flaw in our program occurs in the linear transformation method (lines 179-213). We've been looking at this program for hours and are having problems finding an error. If someone could take a look at it, we would love them forever!

Here's the code:

 /** COMP2611, Assignment 2 - Implementing the SuperCipher
 * By Vanessa Astle and Christina Arsenault
 * October 23, 2007
 **/
 

class SuperCipher 
{
private int numRounds;

private int[] block;

private int[][] subkeys;

public static final int[] sbox = {99,124,119,123,242,107,111,197,48,1,103,43,254,215,171,118,
202,130,201,125,250,89,71,240,173,212,162,175,156,164,114,192,
183,253,147,38,54,63,247,204,52,165,229,241,113,216,49,21,
  4,199,35,195,24,150,5,154,7,18,128,226,235,39,178,117,
  9,131,44,26,27,110,90,160,82,59,214,179,41,227,47,132,
 83,209,0,237,32,252,177,91,106,203,190,57,74,76,88,207,
208,239,170,251,67,77,51,133,69,249,2,127,80,60,159,168,
 81,163,64,143,146,157,56,245,188,182,218,33,16,255,243,210,
205,12,19,236,95,151,68,23,196,167,126,61,100,93,25,115,
 96,129,79,220,34,42,144,136,70,238,184,20,222,94,11,219,
224,50,58,10,73,6,36,92,194,211,172,98,145,149,228,121,
231,200,55,109,141,213,78,169,108,86,244,234,101,122,174,8,
186,120,37,46,28,166,180,198,232,221,116,31,75,189,139,138,
112,62,181,102,72,3,246,14,97,53,87,185,134,193,29,158,
225,248,152,17,105,217,142,148,155,30,135,233,206,85,40,223,
140,161,137,13,191,230,66,104,65,153,45,15,176,84,187,22};

public static final int[][] LT32 = {{0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,1,0,1,1},
 {1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0},
 {0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0},
 {0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0},
 {0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0},
 {0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0},
 {0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1},
 {1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
 {1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0},
 {0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0},
{0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0},
{0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0},
{0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
{0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0},
 {0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0},
 {0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0},
 {0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0},
 {0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1},
{0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0},
 {0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0},
 {0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0},
 {0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0},
 {0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0},
 {0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0}};
public SuperCipher(int numRounds)
{
if(numRounds<=0)
this.numRounds = 1;
else
this.numRounds = numRounds;

block = new int[16];

subkeys = new int[numRounds][16];
}

private String convertDecToBin(int num)
{
String result = "";
while(num > 0)
{
int bit = num%2;
result = Integer.toString(bit) + result;
num/=2;
}

while(result.length() < 8)
result = "0" + result;

return result;
}

private int convertBinToDec(String input)
{
int sum = 0;
if((input.length() > 31) || (input == null))
return -1;
int powerOf2 = 1;
for(int i=input.length()-1; i>=0; i--)
{
if(input.charAt(i) == '1')
sum = sum+powerOf2;
else if (input.charAt(i) != '0')
return -1;
powerOf2=powerOf2*2;
}
return sum;
}

private void mixSubkey(int currRound)
{
/** This method mixes the subkey for the round indexed by currRound with 
 *  the 128-bit vector stored in block, and places the result back in block. 
 *  The value passed to currRound must be in the range 0...(numRounds - 1).
 *  If not, mixSubkey leaves block unchanged.
 */ 
for(int i = 0; i < 16; i++)
{
block[i] = block[i]^subkeys[currRound][i];
}

/*System.out.println("mixSubkey");
for(int i = 0; i<block.length; i++)
{
System.out.println(block[i]);
}*/
}

private void substitute()
{
/** This method performs substitution on block, and places the result 
 *  back in block.
 */
for(int i = 0; i < 16; i++)
{
block[i] = sbox[block[i]];
}

/*System.out.println("subsitute");
for(int i = 0; i<block.length; i++)
{
System.out.println(block[i]);
}*/
}

private void shuffleBytes()
{
/** This method applies the first part of the linear transformation to block,
 *  and places the result back in block.
 */
int[] temp = new int[16];
for(int i = 0; i < 16; i++)
temp[i] = block[i];

block[0]=temp[0];
block[1]=temp[5];
block[2]=temp[10];
block[3]=temp[15];
block[4]=temp[4];
block[5]=temp[9];
block[6]=temp[14];
block[7]=temp[3];
block[8]=temp[8];
block[9]=temp[13];
block[10]=temp[2];
block[11]=temp[7];
block[12]=temp[12];
block[13]=temp[1];
block[14]=temp[6];
block[15]=temp[11];

/*System.out.println("shuffleBytes");

for(int i = 0; i<block.length; i++)
{
System.out.println(block[i]);
}*/
}

private void linTrans32()
{
/** This method applies the second part of the linear transformation to 
 *  block, and places the result back in block.
 */
String product = "";
for(int i = 0; i < 16; i+=4)
{
String s = convertDecToBin(block[i]) + convertDecToBin(block[i+1]) 
+ convertDecToBin(block[i+2]) + convertDecToBin(block[i+3]);

for(int j = 0; j < 32; j++)
{
int sum = 0;
for (int k = 0; k < 32; k++)
{
sum+=(Integer.parseInt(String.valueOf(s.charAt(k))) * LT32[k][j]);
}
product = product + Integer.toString(sum%2);
}
}
int n = 0;
for(int m = 0; m < 128; m+=8)
{
block[n] = convertBinToDec(product.substring(m,m+7));
n++;
}

System.out.println("linTrans32");

for(int i = 0; i<block.length; i++)
{
System.out.println(block[i]);
}
}

private void encryptOneRound(int currRound)
{
/** This method processes the 128-bit vector stored in block through the
 *  entire round indexed by currRound, and places the result back in 
 *  block. If currRound is not in the range 0...(numRounds-1), then block
 *  is unchanged.
 */
mixSubkey(currRound);
substitute();
shuffleBytes();
linTrans32();
}

public void fillSubkeys(int[] masterKey)
{
/** This method takes the master key, which is stored as an array of int
 *  values in the range 0...255, generates all the subkeys, and stores them
 *  in the field subkeys. The length of the master key can vary. 
 */
for(int i = 0; i< numRounds; i+=2)
{
for (int j = 0; j<16; j++)
{
subkeys[i][j] = convertBinToDec("01010101");
subkeys[i+1][j] = convertBinToDec("10101010");

/*System.out.println("fillSubkeys");
System.out.println(subkeys[i][j]);
System.out.println(subkeys[i+1][j]);
*/}

}

}

public int[] encrypt(int[] plaintext)
{
/** This method takes a plaintext, represented as an array of 16 int
 *  values in the range 0...255, copies it into block, and then encrypts
 *  it by calling encryptOneRound once for each round of the cipher. 
 *  The resulting ciphertext (which will end up in block) should be copied
 *  into a new array, and a reference to this array should be returned. 
 *  If plaintext is not an array of length 16, or if it contains values 
 *  not in the range 0...255, return null.
 */
if(plaintext.length != 16)
return null;

for(int i = 0; i < 16; i++)
if(plaintext[i] < 0 || plaintext[i] > 255)
return null;
for(int i = 0; i < 16; i++)
{
block[i] = plaintext[i];
}

fillSubkeys(new int[0]);

while(numRounds > 0)
{
numRounds--;
encryptOneRound(numRounds);
}

int[] ciphertext = new int[16];
for(int i = 0; i < 16; i++)
{
ciphertext[i] = block[i];
}

return ciphertext;
}

public static void main(String[] args)
{
int[] plain = {10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160};
int[] cipher = new SuperCipher(2).encrypt(plain);
for(int i = 0; i < cipher.length; i++)
System.out.println(cipher[i]);
}
}
   

[marc weber]

Originally posted by Christina Arsenault:
... We are not getting the right output and we have determined that the flaw in our program occurs in the linear transformation method (lines 179-213)...

How are you testing this method?

In other words, what exactly is the "second part of the linear transformation" supposed to do?
[ October 23, 2007: Message edited by: marc weber ]