Attempting to produce linear approximation table. Values in output are incorrect

Question

Here is a code given in c language, and the s box table is {0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8, 0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7};, when we run this code we get the wrong output. We should get the linear approximation table from this code. I think the error that I get is here at the sbox output part.

#include <stdio.h>
#include <stdlib.h>
typedef unsigned short int UINT16; 

UINT16  sbox_table[16] =  {0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8, 0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7}; 

int lin_appr_table[16][16];


void construct_lin_appr_table()
{
    UINT16 i, j, k;

    UINT16 X, Y, x;
    UINT16 X_xor, Y_xor;
    int counter;

    for (i=0 ; i<16 ; i++)//sbox input
    {
        
        for (j=0 ; j<16 ; j++)//sbox output
        {
            X=i;
            Y=j;
            
            counter=0;
            for (k=0;k<16;k++)
            {
              X_xor=X&k;
              Y_xor=Y&sbox_table[k];
              
              if(X_xor^Y_xor==0) counter++;
              
             
            }
            
            lin_appr_table[i][j]=counter-8;
            
            //Write the code that makes up the table

        }

    }

    //Write the code that printed the table on the screen
    
    
    for (i=0 ; i<16 ; i++)//sbox input
    {
        for (j=0 ; j<16 ; j++)//sbox output
        {
            printf("% d ", lin_appr_table[i][j]);
        }
        printf("\n");
    }
}  

int main()
{
    construct_lin_appr_table();
    
    getch();
    return 0;
}

Expected output:

Watch out for operator precedence in `if(X_xor^Y_xor==0)`. Did you mean `if((X_xor^Y_xor)==0)`? — Weather Vane, Dec 16 '20 at 20:44
Is `X_xor=X&k` supposed to be `X_xor = X & (1 << k)`? Just a guess. — Weather Vane, Dec 16 '20 at 21:01
Can you edit the post here to show what expected output is? (I see you almost posted that as answer, but it would be good to have here.) — ryyker, Dec 16 '20 at 21:12
Pictures, although not always appropriate are not forbidden when information cannot be conveyed in another way. Post a picture if you have to. — ryyker, Dec 16 '20 at 21:32
...and this table is the result specifically for the inputs values of: `sbox_table[16] = {0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8, 0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7};` ? — ryyker, Dec 16 '20 at 22:23
the purpose of this is: the code above does not give us this expected table, the purpose is to find the errors within the code in order to take this table (expected table) as output. — Anonymouse, Dec 16 '20 at 22:28
Well, that clears it up. This is not a C problem, rather it is a or algorithm problem. I suggest posting this question on [cryptography stack exchange](https://crypto.stackexchange.com/). There will likely be more relevant expertise there. — ryyker, Dec 16 '20 at 22:54
Possible [ref](http://www.cs.bc.edu/~straubin/crypto2017/heys.pdf). — chux - Reinstate Monica, Dec 17 '20 at 00:05

ryyker · Answer 1 · 2020-12-16T21:37:34.753

2

Suggest the following two changes to produce table below:

      //if(X_xor^Y_xor==0) counter++;
      if((X_xor^Y_xor)==0) counter++;

Note: for above statement, turning warnings on should result in something similar to:

36, 19    warning: ^ has lower precedence than ==; == will be evaluated first

      //X_xor=X&k;
      X_xor = X & (1 << k); //credit to Weather Vane in comments

result in following table:

Asides: As a rule it is also a good idea to initialize your variables during declaration, and always before use. eg:

int lin_appr_table[16][16] = {{0}};//initializes all locations to 0

And when able, choose to use portable over non-portable code:

    getchar(); //portable
    //getch(); //not portable

edited Dec 16 '20 at 21:37

answered Dec 16 '20 at 20:50

ryyker

22,849
3
43
87

when i made that change i get another table. – Anonymouse Dec 16 '20 at 20:56
If you are referring the `^` change, then yes, that would result in different values. Are you saying it is preferred to evaluate `Y_xor==0` first? ( i.e.: `X_xor^(Y_xor==0)` ) as the intended evaluation? – ryyker Dec 16 '20 at 21:01
can i get an mail or something else to discuss there about this problem – Anonymouse Dec 16 '20 at 21:12
@S.Nesimi - no. unfortunately that will not work. Just post the expected output somewhere below the code section in the original post, and add additional explanation there as well about the correct algorithm – ryyker Dec 16 '20 at 21:16

chux - Reinstate Monica · Accepted Answer · 2020-12-17T03:45:57.523

Key code change: see //if ((X_xor ^ Y_xor) == 0).

#include <stdio.h>
#include <stdlib.h>
typedef unsigned short int UINT16;

const UINT16 sbox_table[16] = {0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8, 0x3, 0xA,
    0x6, 0xC, 0x5, 0x9, 0x0, 0x7};

int lin_appr_table[16][16];

// There exist various hacks to quickly count the ones in an integer.
// This is just a simple loop.
unsigned count1(unsigned i) {
  unsigned count = 0;
  while (i) {
    count += i & 1;
    i >>= 1;
  }
  return count;
}

void construct_lin_appr_table() {
  UINT16 i, j, k;
  UINT16 X, Y; //, x;
  UINT16 X_xor, Y_xor;
  int counter;

  for (i = 0; i < 16; i++) {
    for (j = 0; j < 16; j++) {
      X = i;
      Y = j;

      counter = 0;
      for (k = 0; k < 16; k++) {
        X_xor = X & k;
        Y_xor = Y & sbox_table[k];

        //if ((X_xor ^ Y_xor) == 0)
        //if ((count1(X_xor) - count1(Y_xor)) % 2 == 0)
        if ((count1(X_xor ^ Y_xor) & 1) == 0)
          counter++;
      }
      lin_appr_table[i][j] = counter - 16 / 2;
    }
  }

  for (i = 0; i < 16; i++) {
    for (j = 0; j < 16; j++) {
      printf("% d ", lin_appr_table[i][j]);
    }
    printf("\n");
  }
}

int main() {
  construct_lin_appr_table();
  return 0;
}

Output

 8  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0 -2 -2  0  0 -2  6  2  2  0  0  2  2  0  0 
 0  0 -2 -2  0  0 -2 -2  0  0  2  2  0  0 -6  2 
 0  0  0  0  0  0  0  0  2 -6 -2 -2  2  2 -2 -2 
 0  2  0 -2 -2 -4 -2  0  0 -2  0  2  2 -4  2  0 
 0 -2 -2  0 -2  0  4  2 -2  0 -4  2  0 -2 -2  0 
 0  2 -2  4  2  0  0  2  0 -2  2  4 -2  0  0 -2 
 0 -2  0  2  2 -4  2  0 -2  0  2  0  4  2  0  2 
 0  0  0  0  0  0  0  0 -2  2  2 -2  2 -2 -2 -6 
 0  0 -2 -2  0  0 -2 -2 -4  0 -2  2  0  4  2 -2 
 0  4 -2  2 -4  0  2 -2  2  2  0  0  2  2  0  0 
 0  4  0 -4  4  0  4  0  0  0  0  0  0  0  0  0 
 0 -2  4 -2 -2  0  2  0  2  0  2  4  0  2  0 -2 
 0  2  2  0 -2  4  0  2 -4 -2  2  0  2  0  0  2 
 0  2  2  0 -2 -4  0  2 -2  0  0 -2 -4  2 -2  0 
 0 -2 -4 -2 -2  0  2  0  0 -2  4 -2 -2  0  2  0

Ref

See How to count the number of set bits in a 32-bit integer? for a faster count1().

it is working. thanks a lot for helping me. i really appreciate that. — Anonymouse, Dec 17 '20 at 10:41

Attempting to produce linear approximation table. Values in output are incorrect

2 Answers2