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)]Z; x - x1x2... xn 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, фщ(x) = ф^^); Фр = ф9р ·... · ф91 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 Фр; 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 Фр essentially depends on each bit in q» and k respectively; A is a Boolean matrix (aj)nxn, where aj = 1 iff j-th coordinate function of ф^^) essentially depends on xj, i E {1,...,n}; matrix A4(/*) 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 A4(/*) consists of positive integers; Bq. is the set of numbers of coordinates in k which q» essentially depends on. Let Bqi П Bqj = 0 for all i, j E {1,...,p}, i = j. Then the following statements are true: 1) if Фг(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,...,/} = Bqi U... U Bqp, 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Л). 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Л). Particularly, p(k) ^ 10 for GOST 28147-89.