YAARX: Yet Another ARX Toolkit  0.1
 All Data Structures Files Functions Variables Macros Pages
Functions
max-xdp-add.hh File Reference

Header file for max-xdp-add.cc. More...

Go to the source code of this file.

Functions

void max_xdp_add_i (const int i, const uint32_t k, const uint32_t n, double *p, WORD_T *dd, gsl_matrix *A[2][2][2], gsl_vector *B[WORD_SIZE+1], gsl_vector *C, const WORD_T da, const WORD_T db, WORD_T *dd_max, double *p_max, uint32_t A_size)
 
void max_xdp_add_bounds (gsl_matrix *A[2][2][2], gsl_vector *B[WORD_SIZE+1], const WORD_T da, const WORD_T db, WORD_T *dd_max, uint32_t A_size)
 
double max_xdp_add (gsl_matrix *A[2][2][2], const WORD_T da, const WORD_T db, WORD_T *dd_max)
 
double max_xdp_add_exper (gsl_matrix *A[2][2][2], const WORD_T da, const WORD_T db, WORD_T *dc_max)
 
double max_xdp_add_lm (WORD_T da, WORD_T db, WORD_T *dc_ret)
 

Detailed Description

Header file for max-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

double max_xdp_add ( gsl_matrix *  A[2][2][2],
const WORD_T  da,
const WORD_T  db,
WORD_T *  dd_max 
)

Compute the maximum differential probability over all output differences: $\mathrm{max}_{dc}~\mathrm{xdp}^{+}(da,db \rightarrow dc)$. Complexity c: $O(n) \le c \le O(2^n)$.

Parameters
Atransition probability matrices.
dafirst input difference.
dbsecond input difference.
dd_maxmaximum probability output difference.
Returns
$\mathrm{max}_{dc}~\mathrm{xdp}^{+}(da,db \rightarrow dc)$.
See Also
max_xdp_add, max_xdp_add_i, max_adp_xor
void max_xdp_add_bounds ( gsl_matrix *  A[2][2][2],
gsl_vector *  B[WORD_SIZE+1],
const WORD_T  da,
const WORD_T  db,
WORD_T *  dd_max,
uint32_t  A_size 
)

Compute an array of bounds that can be used in the computation of the maximum differential probability.

Parameters
Atransition probability matrices.
Barray of size A_size rows by (n + 1) columns containing upper bounds on the maximum probabilities of all j bit differentials $n \ge j \ge 1$ beginning from any state i: A_size $> i \ge 0$.
dafirst input difference.
dbsecond input difference.
dd_maxmaximum probability output difference.
A_sizesize of the square transition probability matrices (equivalently, the number of states of the S-function).
See Also
max_xdp_add_i, max_adp_xor_bounds
double max_xdp_add_exper ( gsl_matrix *  A[2][2][2],
const WORD_T  da,
const WORD_T  db,
WORD_T *  dc_max 
)

Compute the maximum differential probability by exhaustive search over all output differences. Complexity: $O(2^n)$.

Parameters
Atransition probability matrices.
dafirst input difference.
dbsecond input difference.
dc_maxmaximum probability output difference.
Returns
$\mathrm{max}_{dc}~\mathrm{xdp}^{+}(da,db \rightarrow dc)$.
See Also
max_xdp_add
void max_xdp_add_i ( const int  i,
const uint32_t  k,
const uint32_t  n,
double *  p,
WORD_T *  dd,
gsl_matrix *  A[2][2][2],
gsl_vector *  B[WORD_SIZE+1],
gsl_vector *  C,
const WORD_T  da,
const WORD_T  db,
WORD_T *  dd_max,
double *  p_max,
uint32_t  A_size 
)

Compute an upper bound $B[k][i]$ on the maximum probability of the differential $(da[n-1:k], db[n-1:k] \rightarrow dc[n-1:k])$ starting from initial state i of the S-function i.e. $\mathrm{dp}(da[n-1:k],db[n-1:k] \rightarrow dc[n-1:k]) = L A_{n-1} A_{n-2} \ldots A_{k} C^{i}_{k-1}$, given the upper bounds $B[k][i]$ on the probabilities of the differentials $(da[n-1:j], db[n-1:j] \rightarrow dc[n-1:j])$ for $j = k+1, k+2, \ldots, n-1$, where $L = [1~1~\ldots~1]$ is a row vector of size A_size and $C^{i}_{k-1}$ is a unit column vector of size A_size with 1 at position $i$ and $C^{i}_{-1} = C$.

Parameters
iindex of the state of the S-function: A_size $> i \ge 0$.
kcurrent bit position: $ n > k \ge 0$.
nword size.
pthe estimated probability at bit position k.
ddoutput difference.
Atransition probability matrices.
Barray of size A_size rows by (n + 1) columns containing upper bounds on the maximum probabilities of all j bit differentials $n \ge j \ge 1$ beginning from any state i: A_size $> i \ge 0$.
Cunit row vector of size A_size rows, initialized with 1 at state index i.
dafirst input difference.
dbsecond input difference.
dd_maxmaximum probability output difference.
p_maxthe maximum probability.
A_sizesize of the square transition probability matrices (equivalently, the number of states of the S-function).
See Also
max_adp_xor_i
double max_xdp_add_lm ( WORD_T  da,
WORD_T  db,
WORD_T *  dc_ret 
)

The maximum differential probability over all output differences: in linear time as proposed in [Lipmaa, Moriai, FSE 2001]: $\mathrm{max}_{dc}~\mathrm{xdp}^{+}(da,db \rightarrow dc)$. Complexity c: $O(n)$.

Parameters
dafirst input difference.
dbsecond input difference.
dc_retmaximum probability output difference.
Returns
$\mathrm{max}_{dc}~\mathrm{xdp}^{+}(da,db \rightarrow dc)$.
See Also
max_xdp_add