YAARX: Yet Another ARX Toolkit  0.1
 All Data Structures Files Functions Variables Macros Pages
Functions | Variables
xdp-add-diff-set.cc File Reference

Functions for working with sets of XOR differences w.r.t. addition: $\mathrm{xdp}^{+}(A,B \rightarrow C)$ (See also: xdp-add.cc). More...

#include "common.hh"
#include "adp-xor.hh"
#include "xdp-add.hh"
#include "max-xdp-add.hh"
#include "xdp-add-diff-set.hh"

Functions

uint64_t xdp_add_dset_size (diff_set_t da_set)
 
bool is_dset_equal (const diff_set_t da_set, const diff_set_t db_set)
 
void xdp_add_input_diff_to_output_dset (WORD_T da, WORD_T db, diff_set_t *dc_set)
 
void xdp_add_input_dset_to_output_dset (gsl_matrix *AA[2][2][2], const diff_set_t da_set, const diff_set_t db_set, diff_set_t *dc_set)
 
void xdp_add_input_dset_to_output_dset_i (uint32_t i, gsl_matrix *AA[2][2][2], const diff_set_t da_set, const diff_set_t db_set, diff_set_t *dc_set_in, double *r_in, diff_set_t *dc_set_max, double *r_max)
 
void xdp_add_input_dset_to_output_dset_rec (gsl_matrix *AA[2][2][2], const diff_set_t da_set, const diff_set_t db_set, diff_set_t *dc_set_max)
 
void xdp_add_dset_gen_diff_all (const diff_set_t dc_set, std::vector< WORD_T > *dc_set_all)
 
void xdp_add_dset_gen_diff_hamming_limit (const diff_set_t dc_set, const uint32_t hw_limit, std::vector< WORD_T > *dc_set_all)
 
void xdp_add_input_dsets_to_input_diffs (const diff_set_t da_set, const diff_set_t db_set, WORD_T da[2], WORD_T db[2])
 
void xdp_add_dset_alloc_matrices (gsl_matrix *A[2][2][2])
 
void xdp_add_dset_free_matrices (gsl_matrix *A[2][2][2])
 
void xdp_add_dset_gen_matrices (gsl_matrix *A[2][2][2])
 
void xdp_add_dset_print_matrices (gsl_matrix *A[2][2][2])
 
void xdp_add_dset_print_matrix (gsl_matrix *A)
 
void xdp_add_dset_print_vector (gsl_vector *C)
 
void xdp_add_dset_init_states (const uint32_t pos, gsl_vector *C, const diff_set_t da_set, const diff_set_t db_set, const diff_set_t dc_set)
 
void xdp_add_dset_alloc_matrices_all (gsl_matrix *A[3][3][3])
 
void xdp_add_dset_free_matrices_all (gsl_matrix *A[3][3][3])
 
void xdp_add_dset_print_matrices_all (gsl_matrix *A[3][3][3])
 
void xdp_add_dset_gen_matrices_all (gsl_matrix *AA[3][3][3], gsl_matrix *A[2][2][2])
 
void xdp_add_dset_gen_matrix (const uint32_t i, gsl_matrix *M, gsl_matrix *A[2][2][2], const diff_set_t da_set, const diff_set_t db_set, const diff_set_t dc_set)
 
void xdp_add_dset_final_states_norm (gsl_vector *L, bool b_da_msb_is_fixed, bool b_db_msb_is_fixed, bool b_dc_msb_is_fixed)
 
double xdp_add_dset (gsl_matrix *A[2][2][2], const uint32_t word_size, const diff_set_t da_set, const diff_set_t db_set, const diff_set_t dc_set)
 
double xdp_add_dset_all (gsl_matrix *AA[3][3][3], const uint32_t word_size, const diff_set_t da_set, const diff_set_t db_set, const diff_set_t dc_set)
 
void rmax_xdp_add_dset_i (const uint32_t k_init, const uint32_t k, const uint32_t n, double *r, double *p, diff_set_t *dc_set, gsl_matrix *A[3][3][3], gsl_vector *B[WORD_SIZE+1], gsl_vector *C_in, const diff_set_t da_set, const diff_set_t db_set, diff_set_t *dc_set_max, double *r_max, double *p_max, bool b_single_diff)
 
void rmax_xdp_add_dset_bounds (gsl_matrix *A[3][3][3], gsl_vector *B[WORD_SIZE+1], const diff_set_t da_set, const diff_set_t db_set, diff_set_t *dd_set_max)
 
double rmax_xdp_add_dset (gsl_matrix *A[3][3][3], const diff_set_t da_set, const diff_set_t db_set, diff_set_t *dc_set_max, bool b_single_diff)
 
double max_xdp_add_dset (const diff_set_t da_set, const diff_set_t db_set, diff_set_t *dc_set)
 
double xdp_add_dset_exper (gsl_matrix *A[2][2][2], const diff_set_t da_set, const diff_set_t db_set, const diff_set_t dc_set)
 
double max_xdp_add_dset_exper (gsl_matrix *A[2][2][2], const diff_set_t da_set, const diff_set_t db_set, diff_set_t *max_dc_set)
 
void xdp_add_dset_print_set (const diff_set_t da_set)
 
diff_set_t xor_dset (diff_set_t da_set_in, diff_set_t db_set_in)
 
diff_set_t lrot_dset (diff_set_t da_set, uint32_t rot_const)
 
bool is_inset (uint32_t da, diff_set_t da_set)
 

Variables

uint32_t XDP_ADD_DSET_ISTATES [XDP_ADD_DSET_NISTATES] = {0,3,5,6}
 

Detailed Description

Functions for working with sets of XOR differences w.r.t. addition: $\mathrm{xdp}^{+}(A,B \rightarrow C)$ (See also: xdp-add.cc).

Author
V.Velichkov, vesse.nosp@m.lin..nosp@m.velic.nosp@m.hkov.nosp@m.@uni..nosp@m.lu
Date
2012-2013

Function Documentation

bool is_dset_equal ( const diff_set_t  da_set,
const diff_set_t  db_set 
)

Check if two sets of XOR differences are equal.

Parameters
da_setset of XOR differences.
db_setset of XOR differences.
void rmax_xdp_add_dset_bounds ( gsl_matrix *  A[3][3][3],
gsl_vector *  B[WORD_SIZE+1],
const diff_set_t  da_set,
const diff_set_t  db_set,
diff_set_t *  dd_set_max 
)

Uses: rmax_xdp_add_dset_i . See also: max_xdp_add_bounds .

void rmax_xdp_add_dset_i ( const uint32_t  k_init,
const uint32_t  k,
const uint32_t  n,
double *  r,
double *  p,
diff_set_t *  dc_set,
gsl_matrix *  A[3][3][3],
gsl_vector *  B[WORD_SIZE+1],
gsl_vector *  C_in,
const diff_set_t  da_set,
const diff_set_t  db_set,
diff_set_t *  dc_set_max,
double *  r_max,
double *  p_max,
bool  b_single_diff 
)

max_xdp_add_i

double xdp_add_dset ( gsl_matrix *  A[2][2][2],
const uint32_t  word_size,
const diff_set_t  da_set,
const diff_set_t  db_set,
const diff_set_t  dc_set 
)

The XOR probability of ADD with respect to sets of XOR differences diff_set_t . This is probability with which input sets $A, B$ propagate to output set $C$: $\mathrm{xdp}^{+}(A, B \rightarrow C)$ .

Parameters
AAtransition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$, computed with xdp_add_dset_gen_matrix .
word_sizethe length of words in bits (cf. WORD_SIZE).
da_setset of input XOR differences $A$.
db_setset of input XOR differences $B$.
dc_setset of output XOR differences $C$.
Returns
$\mathrm{xdp}^{+}(A, B \rightarrow C)$.
double xdp_add_dset_all ( gsl_matrix *  AA[3][3][3],
const uint32_t  word_size,
const diff_set_t  da_set,
const diff_set_t  db_set,
const diff_set_t  dc_set 
)

The XOR probability of ADD with respect to sets of XOR differences diff_set_t output set $C$: $\mathrm{xdp}^{+}(A, B \rightarrow C)$ .

Note
Functionally the same as xdp_add_dset but uses all transition probability matrices precomputed in advance using xdp_add_dset_gen_matrices_all
Parameters
AAtransition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$, computed with xdp_add_dset_gen_matrices_all .
word_sizethe length of words in bits (cf. WORD_SIZE).
da_setset of input XOR differences $A$.
db_setset of input XOR differences $B$.
dc_setset of output XOR differences $C$.
Returns
$\mathrm{xdp}^{+}(A, B \rightarrow C)$.
void xdp_add_dset_alloc_matrices ( gsl_matrix *  A[2][2][2])

Allocate memory for the transition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.

Parameters
Atransition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.
See Also
xdp_add_dset_alloc_matrices .
void xdp_add_dset_alloc_matrices_all ( gsl_matrix *  A[3][3][3])

Allocate memory for all transition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.

Parameters
Aall transition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.
See Also
xdp_add_dset_alloc_matrices .
void xdp_add_dset_final_states_norm ( gsl_vector *  L,
bool  b_da_msb_is_fixed,
bool  b_db_msb_is_fixed,
bool  b_dc_msb_is_fixed 
)

Normalize the final states in XDP-ADD diff set since for the MSB the matrices A have different transition probabilities; L is the final row vector.

Parameters
Lfinal row vector of size XDP_ADD_DSET_MSIZE .
b_da_msb_is_fixedBoolean flag indicating if the MSB of the input set $A$ is FIXED .
b_db_msb_is_fixedBoolean flag indicating if the MSB of the input set $B$ is FIXED .
b_dc_msb_is_fixedBoolean flag indicating if the MSB of the output set $C$ is FIXED .
void xdp_add_dset_free_matrices ( gsl_matrix *  A[2][2][2])

Free memory reserved by a previous call to xdp_add_dset_alloc_matrices .

Parameters
Atransition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.
void xdp_add_dset_free_matrices_all ( gsl_matrix *  A[3][3][3])

Free memory reserved by a previous call to xdp_add_dset_alloc_matrices_all .

Parameters
Aall transition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.
void xdp_add_dset_gen_diff_all ( const diff_set_t  dc_set,
std::vector< WORD_T > *  dc_set_all 
)

Generate all XOR differences that belong to a given input set $C$.

Parameters
da_setset of input XOR differences in compact represenatation diff_set_t .
dc_set_alla vector of all XOR differences that compose $C$ in explicit form.
void xdp_add_dset_gen_diff_hamming_limit ( const diff_set_t  dc_set,
const uint32_t  hw_limit,
std::vector< WORD_T > *  dc_set_all 
)

Generate all XOR differences that belong to a given input set $C$ and have Hamming weight less than or equal to a pre-defined limit.

Parameters
da_setset of input XOR differences in compact represenatation diff_set_t .
dc_set_alla vector of all XOR differences that compose $C$ in explicit form.
hw_limitHamming weight limit
See Also
xdp_add_dset_gen_diff_all
void xdp_add_dset_gen_matrices ( gsl_matrix *  A[2][2][2])

Generate the transition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.

Parameters
Atransition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.
void xdp_add_dset_gen_matrices_all ( gsl_matrix *  AA[3][3][3],
gsl_matrix *  A[2][2][2] 
)

Generate all matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$. from all valid matrices for this position precomputed with xdp_add_dset_gen_matrices .

Parameters
AAall transition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.
Atransition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.
void xdp_add_dset_gen_matrix ( const uint32_t  i,
gsl_matrix *  M,
gsl_matrix *  A[2][2][2],
const diff_set_t  da_set,
const diff_set_t  db_set,
const diff_set_t  dc_set 
)

Generate the matrix for the i-th bit position, as the sum of all valid matrices for this position

Parameters
ibit postion: $0 \le i <$WORD_SIZE.
Mcomposite transition probability matrix compued as a sum of some matrices A depending on the values of the set st at this bit popsition: $A[i], B[i], C[i]$.
Atransition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.
da_setset of input XOR differences.
db_setset of input XOR differences.
dc_setset of output XOR differences.
void xdp_add_dset_init_states ( const uint32_t  pos,
gsl_vector *  C,
const diff_set_t  da_set,
const diff_set_t  db_set,
const diff_set_t  dc_set 
)

Initialize the states at position pos depending on the values of the sets at this position. pos can be 0 or (WORD_SIZE - 1). If it is 0, valid states are 0, 3, 5, 6 (cf. XDP_ADD_DSET_ISTATES), otherwise all states are valid.

Parameters
posbit position: 0 or (WORD_SIZE - 1).
Ccolumn vector of size XDP_ADD_DSET_MSIZE .
da_setset of input XOR differences.
db_setset of input XOR differences.
dc_set_inset of output XOR differences.
void xdp_add_dset_print_matrices ( gsl_matrix *  A[2][2][2])

Print all matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.

Parameters
Atransition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.
void xdp_add_dset_print_matrices_all ( gsl_matrix *  A[3][3][3])

Print all matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.

Parameters
Aall transition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.
void xdp_add_dset_print_matrix ( gsl_matrix *  A)

Print a single matrix for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.

Parameters
Atransition probability matrix for $\mathrm{xdp}^{+}(A, B \rightarrow C)$. .
void xdp_add_dset_print_vector ( gsl_vector *  C)

Print a vector for $\mathrm{xdp}^{+}(A, B \rightarrow C)$.

Parameters
Cvector of size XDP_ADD_DSET_MSIZE .
uint64_t xdp_add_dset_size ( diff_set_t  da_set)

Compute the number of XOR differencces in the set da_set .

Parameters
da_seta set of input differences.
Returns
Number of elements in da_set .
void xdp_add_input_diff_to_output_dset ( WORD_T  da,
WORD_T  db,
diff_set_t *  dc_set 
)

From two fixed input differences da and db to the ADD operation, compute a set of output differences C such that $\mathrm{xdp}^{+}(da, db \rightarrow C) \ge \mathrm{max}_{dc}\mathrm{xdp}^{+}(da, db \rightarrow dc)$. The algorithm is based on max_xdp_add_lm . It sets $dc[i]=$ STAR if $da[i] \neq db[i]$ and $dc[i] = da[i] = db[i]$ otherwise.

Parameters
dainput XOR difference.
dbinput XOR difference.
dc_setset of output XOR differences.
void xdp_add_input_dset_to_output_dset ( gsl_matrix *  AA[2][2][2],
const diff_set_t  da_set,
const diff_set_t  db_set,
diff_set_t *  dc_set 
)

From given sets of input XOR differences $A$ and $B$ compute a set of output differences $C$ by greedily bitwise maximizing the ratio: $r = p / s$ where $p = \mathrm{xdp}^{+}(A, B \rightarrow C)$ and $s$ is the size of the output set $C$.

Note
Does NOT find the actual maximum.
Parameters
AAtransition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$, computed with xdp_add_dset_gen_matrix .
da_setset of input XOR differences.
db_setset of input XOR differences.
dc_setset of output XOR differences.
void xdp_add_input_dset_to_output_dset_i ( uint32_t  i,
gsl_matrix *  AA[2][2][2],
const diff_set_t  da_set,
const diff_set_t  db_set,
diff_set_t *  dc_set_in,
double *  r_in,
diff_set_t *  dc_set_max,
double *  r_max 
)

From given sets of input XOR differences $A$ and $B$ compute a set of output differences $C$ that maximizes the ratio: $r = p / s$ where $p = \mathrm{xdp}^{+}(A, B \rightarrow C)$ and $s$ is the size of the output set $C$: $C : \mathrm{max}_{r}\mathrm{xdp}^{+}(A, B \rightarrow C)$.

Note
Finds the exact maximum, but is not efficient. A more efficient variant is rmax_xdp_add_dset_bounds .
Parameters
AAtransition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$, computed with xdp_add_dset_gen_matrix .
da_setset of input XOR differences.
db_setset of input XOR differences.
dc_set_inset of output XOR differences.
r_inratio $r = p / s = \mathrm{xdp}^{+}(A, B \rightarrow C) / \#C$.
dc_set_maxoutput set $C$ that maximizes $r$.
r_maxthe maximum ratio $r$.
See Also
xdp_add_input_dset_to_output_dset_rec, xdp_add_input_dset_to_output_dset .
void xdp_add_input_dset_to_output_dset_rec ( gsl_matrix *  AA[2][2][2],
const diff_set_t  da_set,
const diff_set_t  db_set,
diff_set_t *  dc_set_max 
)

Wrapper function for xdp_add_input_dset_to_output_dset_i .

Parameters
AAtransition probability matrices for $\mathrm{xdp}^{+}(A, B \rightarrow C)$, computed with xdp_add_dset_gen_matrix .
da_setset of input XOR differences.
db_setset of input XOR differences.
dc_set_maxoutput set $C$ that maximizes the ratio $r = p / s = \mathrm{xdp}^{+}(A, B \rightarrow C) / \#C$.
void xdp_add_input_dsets_to_input_diffs ( const diff_set_t  da_set,
const diff_set_t  db_set,
WORD_T  da[2],
WORD_T  db[2] 
)

From input sets $A$ and $B$ for $\mathrm{xdp}^{+}$, generate two pairs of input differences: $(da^0 \in A, db^0 \in B)$ and $(da^1 \in A, db^1 \in B)$ such that $da^{j}[i] = db^{j}[i] = j$ if $A[i] = B[i] =$STAR and $da^{j}[i] = A[i]$, $db^{j}[i] = B[i]$ otherwise; $j = 0, 1$.

Parameters
da_setset of input XOR differences.
db_setset of input XOR differences.
outputXOR differences $da^0, da^1$.
outputXOR differences $db^0, db^1$.

Variable Documentation

uint32_t XDP_ADD_DSET_ISTATES[XDP_ADD_DSET_NISTATES] = {0,3,5,6}

$da[0] ^ db[0] ^ dc[0] = 0 : (da[0],db[0],dc[0]) \in \{000, 011, 101, 110\}$.