On mathematical models of key mixing for iterative block encryption algorithms
For a binary symmetric iterative block encryption algorithm A with r rounds, the following notation is used: k is a key of A, k E V = [GF(2)]<sup>Z</sup>; x - x1x2... x<sub>n</sub> is an information block, x E V^; q is a round key, q E УЛ; ф^, q) is the round function; q» is an i-th round key, i E {1, 2,..., r}; фqi : K, ^ Vn is the i-th round substitution, ф<sub>щ</sub>(x) = ф^^); Ф<sub>р</sub> = ф<sub>9р</sub> ·... · ф<sub>91</sub> is the p-round substitution, p E {1,..., r}; p is the minimal p (if exists) such that every bit in k is an essential argument for the function Ф<sub>р</sub>; p(qj), the exponent of q^ and p(k), the exponent of k, are the least p (if exist) such that every coordinate function of Ф<sub>р</sub> essentially depends on each bit in q» and k respectively; A is a Boolean matrix (aj)<sub>n</sub>xn, where aj = 1 iff j-th coordinate function of ф^^) essentially depends on xj, i E {1,...,n}; matrix A<sup>4</sup>(/*) is obtained from A* by removing rows with the numbers which aren't in a set I, 0 = I С {1,..., n}; I*-exp A is the (local) I*-exponent of A, that is, the least integer 7 (if exists) such that, for any t ^ 7, the matrix A<sup>4</sup>(/*) consists of positive integers; B<sub>q</sub>. is the set of numbers of coordinates in k which q» essentially depends on. Let B<sub>qi</sub> П B<sub>qj</sub> = 0 for all i, j E {1,...,p}, i = j. Then the following statements are true: 1) if Ф<sub>г</sub>(x, k) depends on each bit of k, then p(k) = p(1) + (p - 1) and p(q») = p(1) + (i - 1), i = 1,...,p; 2) if {1,...,/} = B<sub>qi</sub> U... U B<sub>qp</sub>, n = A, and h and h' are any substitutions on V\, then p(k) ^ I*-exp A + (p - 1) for I = {1,..., n} in case ф^^) = h(x ф q) and for I = {1} in case ф^, q) = h'((x + q)mod 2<sup>Л</sup>). As a consequence, if A is the Feistel algorithm, where x = x'x'', |x'| = |x''| = n/2, and ф^, q) = (x'', x' ф - (x'', q)), then p(k) ^ I*-exp A + (p - 1) for I = {n/2 + 1,..., n} in case ^(x", q) = h(x" ф q) and for I = {n/2 + 1} in case ^(x",q) = fc'((x" + q) mod 2<sup>Л</sup>). Particularly, p(k) ^ 10 for GOST 28147-89.