Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Disclaimer: School work.

I am trying to implement Groestl through Java, and have got stuck on the MixBytes section which can be found here section 3.4.5 page 11. As per the description of matrix multiplication, following was my first naive attempt to do it in matrix multiplication way.

public static final byte[][] B = new byte[][]{
{(byte)0x02, (byte)0x02, (byte)0x03, (byte)0x04, (byte)0x05, (byte)0x03, (byte)0x05, (byte)0x07},
{(byte)0x07, (byte)0x02, (byte)0x02, (byte)0x03, (byte)0x04, (byte)0x05, (byte)0x03, (byte)0x05},
{(byte)0x05, (byte)0x07, (byte)0x02, (byte)0x02, (byte)0x03, (byte)0x04, (byte)0x05, (byte)0x03},
{(byte)0x03, (byte)0x05, (byte)0x07, (byte)0x02, (byte)0x02, (byte)0x03, (byte)0x04, (byte)0x05},
{(byte)0x05, (byte)0x03, (byte)0x05, (byte)0x07, (byte)0x02, (byte)0x02, (byte)0x03, (byte)0x04},
{(byte)0x04, (byte)0x05, (byte)0x03, (byte)0x05, (byte)0x07, (byte)0x02, (byte)0x02, (byte)0x03},
{(byte)0x03, (byte)0x04, (byte)0x05, (byte)0x03, (byte)0x05, (byte)0x07, (byte)0x02, (byte)0x02}, 
{(byte)0x02, (byte)0x03, (byte)0x04, (byte)0x05, (byte)0x03, (byte)0x05, (byte)0x07, (byte)0x02}
};

  public byte[][] mixBytes( byte[][] msg, int columns )
  {
    byte[][] mixed_msg = new byte[8][columns];
    for( int i = 0; i < 8; i++ )
    {
      for( int j = 0; j < columns; j++ ) {
        mixed_msg[i][j] = 0x00;
      }
    }
    for( int i = 0; i < 8; i++ )
    {
      for( int j = 0; j < columns; j++ )
      {
        for( int k = 0; k < 8; k++ ) {
          mixed_msg[i][j] = ( byte )(mixed_msg[i][j] ^ (B[i][k] & msg[k][j]));
        }
      }
    }
    return mixed_msg;
  }

However, it seems I have mixed up the understanding of what the mix bytes actually does. The following is the C code reference implementation.

#define mul1(b) ((u8)(b))
#define mul2(b) ((u8)((b)>>7?((b)<<1)^0x1b:((b)<<1)))
#define mul3(b) (mul2(b)^mul1(b))
#define mul4(b) mul2(mul2(b))
#define mul5(b) (mul4(b)^mul1(b))
#define mul6(b) (mul4(b)^mul2(b))
#define mul7(b) (mul4(b)^mul2(b)^mul1(b))

void MixBytes(u8 x[ROWS][COLS1024], int columns) {
  int i, j;
  u8 temp[ROWS];
  for (i = 0; i < columns; i++) {
    for (j = 0; j < ROWS; j++) {
      temp[j] = 
  mul2(x[(j+0)%ROWS][i])^
  mul2(x[(j+1)%ROWS][i])^
  mul3(x[(j+2)%ROWS][i])^
  mul4(x[(j+3)%ROWS][i])^
  mul5(x[(j+4)%ROWS][i])^
  mul3(x[(j+5)%ROWS][i])^
  mul5(x[(j+6)%ROWS][i])^
  mul7(x[(j+7)%ROWS][i]);
    }
    for (j = 0; j < ROWS; j++) {
      x[j][i] = temp[j];
    }
  }
}

I am trying to understand how the code is mapping with the description given in 3.4.5 in the specification document, but am unable to. Just to see my understanding of the reference implementation, I tried implementing the same thing with Java as following.

// Credits: Shift helper functions as from the reference C implementation.  
// Soeren S. Thomsen and Krystian Matusiewicz
public byte mul1( byte b ) { return b ;}
public byte mul2( byte b ) { return ( byte )((0 == (b>>7))?((b)<<1)^0x1b:((b)<<1)); }
public byte mul3( byte b ) { return ( byte )(mul2(b) ^ mul1(b)); }
public byte mul4( byte b ) { return ( byte )(mul2( mul2( b ))); }
public byte mul5( byte b ) { return ( byte )(mul4(b) ^ mul1(b)); }
public byte mul6( byte b ) { return ( byte )(mul4(b) ^ mul2(b)); }
public byte mul7( byte b ) { return ( byte )(mul4(b) ^ mul2(b) ^ mul1(b)); }

public byte[][] mixBytes( byte[][] msg, int columns )
{
  byte temp[] = new byte[8];
  for( int i = 0; i < columns; i++ ) 
  {
    for (int j = 0; j < 8; j++) 
    {
      temp[j] = ( byte )(mul2(msg[(j + 0) % 8][i]) ^ mul2(msg[(j + 1) % 8][i]) ^ 
        mul3(msg[(j + 2) % 8][i]) ^ mul4(msg[(j + 3) % 8][i]) ^ 
        mul5(msg[(j + 4) % 8][i]) ^ mul3(msg[(j + 5) % 8][i]) ^
        mul5(msg[(j + 6) % 8][i]) ^ mul7(msg[(j + 7) % 8][i]));
    }
    for( int j = 0; j < 8; j++ ) {
      msg[j][i] = temp[j];
    }
  }
  return msg;
}

But this does not give the same result as the C one, so I am not sure what the algorithm is being implemented here (or my understanding of C and Java is really poor).

Any pointers like an example of just how one of the cells in the result matrix is being calculated would help me to write the implementation.

share|improve this question
1  
You have the test in mul2 reversed. As an aside, the unsigned right shift in Java is >>>, not >> as in C, but in the context that makes not difference. Try public byte mul2( byte b ) { return ( byte )((0 != (b>>>7))?((b)<<1)^0x1b:((b)<<1)); }. Ah, and this is just test code, not intended for actual use, right? Because the C code you start from is not intended for actual use, and Java is a dubious choice for low-level crypto. –  fgrieu Mar 18 at 15:40
    
No this is just school work code. My advisor requires a GUI on top of experiments, so went with Java instead of QT C++. Thanks for tip of unsigned right shift. However I still do not exactly understand what the code is doing, I mean in mathematical operation that the things carries out. My naive implementation of matrix multiplication should have worked if I read the specification correctly, so it is a problem in my understanding of the algorithm, that I need help with. –  Soham Mar 18 at 20:55
    
My only functional change is replacing == with != to match the C code. Each mulz is performing multiplication by constant z (that is, the functional equivalent of z additions) in $\operatorname{GF}(2^8)$ with reduction polynomial $x^8+x^4+x^3+x+1$ (that comes from 0x1b). –  fgrieu Mar 18 at 21:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.