|
Mathematical Methods of Cryptography
On mathematical models of key mixing for iterative block encryption algorithms
D. A. Romankoa, V. M. Fomichevabcd a Financial University under the Government of the Russian Federation, Moscow
b National Engineering Physics Institute "MEPhI", Moscow
c Federal Research Center "Computer Science and Control" of Russian Academy of Sciences, Moscow
d "Security Code", Moscow
Abstract:
For a binary symmetric iterative block encryption algorithm $\mathcal A$ with $r$ rounds, the following notation is used: $k$ is a key of $\mathcal A$, $k\in V_l=[\operatorname{GF}(2)]^l$; $x=x_1x_2\dots x_n$ is an information block, $x\in V_n$; $q$ is a round key, $q\in V_\lambda$; $\phi(x,q)$ is the round function; $q_i$ is an $i$-th round key, $i\in\{1,2,\dots,r\}$; $\phi_{q_i}\colon V_n\to V_n$ is the $i$-th round substitution, $\phi_{q_i}(x)=\phi(x,q_i)$; $\Phi_p=\phi_{q_p}\cdot\dots\cdot\phi_{q_1}$ is the $p$-round substitution, $p\in\{1,\dots,r\}$; $\rho$ is the minimal $p$ (if exists) such that every bit in $k$ is an essential argument for the function $\Phi_p$; $p(q_i)$, the exponent of $q_i$, and $p(k)$, the exponent of $k$, are the least $p$ (if exist) such that every coordinate function of $\Phi_p$ essentially depends on each bit in $q_i$ and $k$ respectively; $A$ is a Boolean matrix $(a_{ij})_{n\times n}$, where $a_{ij}=1$ iff $j$-th coordinate function of $\phi(x,q)$ essentially depends on $x_i$, $i\in\{1,\dots,n\}$; matrix $A^t(I*)$ is obtained from $A^t$ by removing rows with the numbers which aren't in a set $I$, $\emptyset\neq I\subseteq\{1,\dots,n\}$; $I*$-$\exp A$ is the (local) $I*$-exponent of $A$, that is, the least integer $\gamma$ (if exists) such that, for any $t\geq\gamma$, the matrix $A^t(I*)$ consists of positive integers; $B_{q_i}$ is the set of numbers of coordinates in $k$ which $q_i$ essentially depends on. Let $B_{q_i}\cap B_{q_j}=\emptyset$ for all $i,j\in\{1,\dots,\rho\}$, $i\neq j$. Then the following statements are true: 1) if $\Phi_r(x,k)$ depends on each bit of $k$, then $p(k)=p(1)+(\rho-1)$ and $p(q_i)=p(1)+(i-1)$, $i=1,\dots,\rho$; 2) if $\{1,\dots,l\}=B_{q_1}\cup\dots\cup B_{q_\rho}$, $n=\lambda$, and $h$ and $h'$ are any substitutions on $V_\lambda$, then $p(k)\geq I*$-$\exp A+(\rho-1)$ for $I=\{1,\dots,n\}$ in case $\phi(x,q)=h(x\oplus q)$ and for $I=\{1\}$ in case $\phi(x,q)=h'((x+q)\mod2^\lambda)$. As a consequence, if $\mathcal A$ is the Feistel algorithm, where $x=x'x''$, $|x'|=|x''|=n/2$, and $\phi(x,q)=(x'',x'\oplus\psi(x'',q))$, then $p(k)\geq I*$-$\exp A+(\rho-1)$ for $I=\{n/2+1,\dots,n\}$ in case $\psi(x'',q)= h(x''\oplus q)$ and for $I=\{n/2+1\}$ in case $\psi(x'',q)=h'((x''+q)\mod2^\lambda)$. Particularly, $p(k)\geq10$ for GOST 28147-89.
Keywords:
iterative block encryption algorithm, local exponent, key exponent.
Citation:
D. A. Romanko, V. M. Fomichev, “On mathematical models of key mixing for iterative block encryption algorithms”, Prikl. Diskr. Mat. Suppl., 2017, no. 10, 93–96
Linking options:
https://www.mathnet.ru/eng/pdma358 https://www.mathnet.ru/eng/pdma/y2017/i10/p93
|
Statistics & downloads: |
Abstract page: | 161 | Full-text PDF : | 52 | References: | 30 |
|