## Substitution block ciphers with functional keys G. P. Agibalov

Material type: ArticleSubject(s): блочные шифры | криптоанализ | булевы функции | биективные функции | существенные переменные | атака на основе открытых текстовGenre/Form: статьи в журналах Online resources: Click here to access online In: Прикладная дискретная математика № 38. С. 57-65Abstract: We define a substitution block cipher C with the plaintext and ciphertext blocks in Fn and with the keyspace Ks0,n(g) that is the set { / (x) : f (x) = n2(ga2(ni(xCTl))); a,a2 e F /;n1,n2 e Sn}, where s0 is an integer, 1 ^ s0 ^ n; g : F/ ^ F/ is a bijective vector function g(x) = g1(x)g2(x) ...gn(x) such that every its coordinate function gi(x) essentially depends on some si ^ s0 variables in the string x = x1x2 ... xn; Sn is the set of all permutations of the row (12. . . n); ni and ai are the permutation and negation operations, that is, (n = (i1i2 ... in)) ^ (n(a1a2 ... an) = ailai2 ... ain), (a = b1b2 ... bn) ^ ((a1a2 ... an)a = a11 a22... a^1) and, for a and b in F2, ab = a if b = 1 and ab = —a if b = 0. Like g, any key / in Ks0,n(g) is a bijection on Fn, / (x) = f 1(x )/2(x) . . . fn(x), and every its coordinate function fi(x) essentially depends on not more than so variables in x. The encryption of a plaintext block x and the decryption of a ciphertext block y on the key f are defined in C as follows: У = f(x) and x = f -1(y). Here, we suggest a known plaintext attack on C with the threat of discovering the key f that was used. Let P1 ,P2,. .., Pm be some blocks of a plaintext, C1, C2, ..., Cm be the corresponding blocks of a ciphertext, i.e., Ci = f (Pi) for l = 1,2,... ,m, and Pi = P11P12 . . .Pin, C = C11C12 . . .С. The object is to determine the coordinate function fi(x) of f for each i e {1,2,...,n}. The suggested attack consists of two steps, namely we first determine the essential variables xil, . . . , x is of fi(x) and then compute a Boolean function h(xil, . . . , x is) such that h(ail, ...,a is) = f i(a1, ..., an) for all n-tuples (a1a2 ... an) e Fn. For determining the essential variables of fi, we construct a Boolean matrix inf D(fi) with the set of rows inf D(fi), where D(fi) = {Pi ® Pj : Cu = Cji; l,j = 1, 2,..., m}, l = 1,...,m, i = 1,...,n, and infD(fi) is the subset of all the minimal vectors in D(fi). Then the numbers of essential variables for fi are the numbers of columns in the intersection of all covers of inf D(fi) with the cardinalities not more than s0, where a cover of a Boolean matrix M is defined as a subset C of its columns such that each row in M has ’1’ in a column in C. For computing h(xil,... ,x is), we first set h(Piil,. .., Piis) = Cii for l = 1,..., m and then, if hi is not yet completely determined on F2, we increase the number m of known blocks (Pi,Ci) of plain- and ciphertexts or extend hi on F2 in such a way that the vector function h = h1h2 ... hn with the completely defined coordinate functions is a bijection on Fn. We also describe some special known plaintext attacks on substitution block ciphers with keyspaces being subsets of Ks0,n(g).Библиогр.: 10 назв.

We define a substitution block cipher C with the plaintext and ciphertext blocks in Fn and with the keyspace Ks0,n(g) that is the set { / (x) : f (x) = n2(ga2(ni(xCTl))); a,a2 e F /;n1,n2 e Sn}, where s0 is an integer, 1 ^ s0 ^ n; g : F/ ^ F/ is a bijective vector function g(x) = g1(x)g2(x) ...gn(x) such that every its coordinate function gi(x) essentially depends on some si ^ s0 variables in the string x = x1x2 ... xn; Sn is the set of all permutations of the row (12. . . n); ni and ai are the permutation and negation operations, that is, (n = (i1i2 ... in)) ^ (n(a1a2 ... an) = ailai2 ... ain), (a = b1b2 ... bn) ^ ((a1a2 ... an)a = a11 a22... a^1) and, for a and b in F2, ab = a if b = 1 and ab = —a if b = 0. Like g, any key / in Ks0,n(g) is a bijection on Fn, / (x) = f 1(x )/2(x) . . . fn(x), and every its coordinate function fi(x) essentially depends on not more than so variables in x. The encryption of a plaintext block x and the decryption of a ciphertext block y on the key f are defined in C as follows: У = f(x) and x = f -1(y). Here, we suggest a known plaintext attack on C with the threat of discovering the key f that was used. Let P1 ,P2,. .., Pm be some blocks of a plaintext, C1, C2, ..., Cm be the corresponding blocks of a ciphertext, i.e., Ci = f (Pi) for l = 1,2,... ,m, and Pi = P11P12 . . .Pin, C = C11C12 . . .С. The object is to determine the coordinate function fi(x) of f for each i e {1,2,...,n}. The suggested attack consists of two steps, namely we first determine the essential variables xil, . . . , x is of fi(x) and then compute a Boolean function h(xil, . . . , x is) such that h(ail, ...,a is) = f i(a1, ..., an) for all n-tuples (a1a2 ... an) e Fn. For determining the essential variables of fi, we construct a Boolean matrix inf D(fi) with the set of rows inf D(fi), where D(fi) = {Pi ® Pj : Cu = Cji; l,j = 1, 2,..., m}, l = 1,...,m, i = 1,...,n, and infD(fi) is the subset of all the minimal vectors in D(fi). Then the numbers of essential variables for fi are the numbers of columns in the intersection of all covers of inf D(fi) with the cardinalities not more than s0, where a cover of a Boolean matrix M is defined as a subset C of its columns such that each row in M has ’1’ in a column in C. For computing h(xil,... ,x is), we first set h(Piil,. .., Piis) = Cii for l = 1,..., m and then, if hi is not yet completely determined on F2, we increase the number m of known blocks (Pi,Ci) of plain- and ciphertexts or extend hi on F2 in such a way that the vector function h = h1h2 ... hn with the completely defined coordinate functions is a bijection on Fn. We also describe some special known plaintext attacks on substitution block ciphers with keyspaces being subsets of Ks0,n(g).

There are no comments on this title.