METHOD OF LINEAR TRANSFORMATION (VARIANTS)

Abstract

The invention relates to the field of computer engineering and cryptography and, in particular, to methods for implementing linear transformations which operate with a specified speed and require minimum amount of memory, for further usage in devices for cryptographic protection of data.

The technical result relates to enabling to select inter-related parameters (performance and required amount of memory) for a particular computing system when implementing a high-dimensional linear transformation.

The use of the present method allows to reduce the amount of consumed memory at a given word size of processors employed.

To this end, based on a specified linear transformation, a modified linear shift register of Galois-type or Fibonacci-type is generated according to the rules provided in the disclosed method, and the usage thereof enables to obtain the indicated technical result.

Claims

1. A method of linear transformation of a message S represented in a binary form, the method comprising: setting a word size W of a processor of a computing system equal to an integer power of 2; setting an available amount of memory of the computing system of M bits; setting a size s of the message S, where s is multiple of W; setting a value n of a number of bits of a linear feedback shift register (LFSR) according to a Galois configuration, so that $n=\frac{W}{2^N}$  is met, where Nε0, 1, 2, . . . ; generating the LFSR according to the Galois configuration with the following parameters: an internal primitive polynomial $f\left(x\right)=x^n\oplus \underset{i=0}{\overset{n-1}{.Math.}}.Math.a_i.Math.x^i,.Math.a_i\in \mathrm{GF}\left(2\right)$ an external polynomial $h\left(y\right)=y^m\oplus \underset{i=0}{\overset{m-1}{.Math.}}.Math.h_i.Math.y^i,.Math.\mathrm{where}.Math..Math.m=\frac{s}{n}$  is a number of stages of the LFSR, wherein h.sub.iεGF(2.sup.n), an initial state of the stages of the LFSR, q.sub.i, forms a data vector
X=(q.sub.m−1,q.sub.m−2, . . . ,q.sub.2,q.sub.1,q.sub.0), wherein q.sub.iεGF(2.sup.n), 0≦i≦m−1 an output state of the stages of the LFSR, q′.sub.i, for one operating cycle, forms a vector
Y=(q′.sub.m−1,q′.sub.m−2, . . . ,q′.sub.2,q′.sub.1,q′.sub.0), wherein q′.sub.iεGF(2.sup.n), 0≦i≦m−1, where q′.sub.i=h.sub.i.Math.q.sub.m−1⊕q.sub.i−1, for 1≦i≦m−1, q′.sub.0=h.sub.0.Math.q.sub.m−1 defining all divisors of the number m as values p.sub.0, p.sub.1, . . . , p.sub.d, while p.sub.0<p.sub.1< . . . p.sub.d; selecting a maximum possible divisor p from $p\le \frac{M}{\mathrm{sn}};$ modifying the LFSR by performing the following actions: computing R matrices H.sub.r, where r=(R−1), . . . , 0, with a size of n×k rows, each having a length of n×k bits, by performing the following actions: computing
k=p, computing $R=\frac{m}{k},$ where R is a number of matrices H; computing
j=m−k; computing
t=0; (A1) if j≦m−1 is not met, then going to step A3; computing
l=0, (A2) if l<n is not met, then computing
j=j+1,
t=t+1, going to step A1; setting an initial state of the LFSR $X=\left(q_{m-1},\mathrm{.Math.}.Math.,q_1,q_0\right),.Math.q_i=\{\begin{array}{c}0,0\le i\le j-1.Math..Math.\mathrm{or}.Math..Math.j+1\le i\le m-1\\ 2^l,i=j,\end{array},0\le i\le m-1,.Math.\mathrm{where}.Math..Math.q_i\in \mathrm{GF}\left(2^n\right);$ computing, after k cycles for each initial state, a new state of the LFSR
Y=(q′.sub.m−1, . . . ,q′.sub.1,q′.sub.0), where q′.sub.iεGF(2.sup.n), 0≦i≦m−1; computing t-th values for all matrices H.sub.i, i=r−1 . . . 0 by concatenating k values of stages q′
H.sub.r,t=q′.sub.kr+k−1∥ . . . ∥q′.sub.kr, wherein 0≦r≦R−1 computing l=l+1, going to step A2: (A3) recording, into stages of the modified LFSR, blocks of the original message S, where an initial state of the stages of the modified LFSR, q.sub.i, forms the vector
X′=(Q.sub.R−1, . . . ,Q.sub.1,Q.sub.0), where Q.sub.r=q.sub.kr+k−1∥ . . . ∥q.sub.kr, wherein 0≦r≦R−1; performing R operating cycles of the modified LFSR by performing, in each cycle the following actions: computing an output state of the stages of the modified LFSR, Q′.sub.i, for one cycle, thereby forming a vector
Y′=(Q′.sub.R−1, . . . ,Q′.sub.1,Q′.sub.0), each value Q′.sub.i of said vector being computed by the formula
Q′.sub.i=f(H.sub.i)⊕Q.sub.i−1 for each i=R−1, . . . , 1, wherein Q′.sub.0=f(H.sub.0), where $f\left(H_r\right)=\stackrel{W-1}{\underset{j=0}{\oplus }}.Math.Z_{R-1,j}.Math.H_{r,j},$ where z.sub.R−1,j is a value of a j-th bit of vector Q.sub.R−1, wherein r=R−1, . . . , 0, j=0, 1, . . . , W−1, z.sub.R−1,jεGF(2); obtaining, after the R operating cycles of the LFSR, a linear transformation of the blocks s of the message S; reading out, from the stages of the modified LFSR, blocks s of a linearly transformed message S; combining the blocks and obtaining the linearly transformed message S.

2. A method of linear transformation of a message S represented in a binary form, the method comprising: setting a word size W of a processor of a computing system equal to an integer power of 2; setting an available amount of memory of the computing system of M bits; setting a size s of the message S, where s is multiple of W; setting a value n of a number of bits of a linear feedback shift register (LFSR) according to a Fibonacci configuration, so that $n=\frac{W}{2^N}$  is met, where Nε0, 1, 2, . . . , generating the LFSR according to the Fibonacci configuration with the following parameters: an internal primitive polynomial $f\left(x\right)=x^n\oplus \underset{i=0}{\overset{n-1}{.Math.}}.Math.a_i.Math.x^i,.Math.a_i\in \mathrm{GF}\left(2\right)$ an external polynomial $h\left(y\right)=y^m\oplus \underset{i=0}{\overset{m-1}{.Math.}}.Math.h_i.Math.y^i,.Math.\mathrm{where}.Math..Math.m=\frac{s}{n}$  is a number of stages in the LFSR, wherein h.sub.iεGF(2.sup.n), an initial state of the stages of the LFSR, q.sub.i, forms a vector
X=(q.sub.m−1,q.sub.m−2, . . . ,q.sub.2,q.sub.1,q.sub.0), wherein q.sub.iεGF(2.sup.n), 0≦i≦m−1 an output state of the stages of the LFSR, q′.sub.i, one cycle, forms a vector
Y=(q′.sub.m−1,q′.sub.m−2, . . . ,q′.sub.2,q′.sub.1,q′.sub.0), wherein q′.sub.iεGF(2.sup.n), 0≦i≦m−1, where q′.sub.i=q.sub.i+1, for each i=0, . . . , m−2 $q_{m-1}^{\prime }=\stackrel{m-1}{\underset{i=0}{\oplus }}.Math.h_i.Math.q_i$ defining all divisors of the number m as values p.sub.0, p.sub.1, . . . , p.sub.d, where p.sub.0<p.sub.1< . . . p.sub.d; selecting a maximum possible divisor p from $p\le \frac{M}{\mathrm{sn}};$ modifying the LFSR by performing the following actions: a computing R matrices H.sub.r, where r=(R−1), . . . , 0, with a size of n×k rows, each having a length of n×k bits, by performing the following actions: computing
k=p, computing $R=\frac{m}{k},$ where R is a number of matrices H.sub.r; computing
r=0; (A5) if r<R is not met, then going to step A7; computing
j=0, (A6) if j<k is not met, then computing
r=r+1, going to step A5; computing
l=0, if l<n is not met, then computing
j=j+1, going to step A6; setting an initial state of the LFSR
X=(q.sub.m−1,q.sub.m−2, . . . ,q.sub.1,q.sub.0), where q.sub.i, q′.sub.iεGF (2.sup.n), 0≦i≦m−1 $q_i=\{\begin{array}{c}{2}^l,i=\mathrm{rk}+j,\\ 0,\mathrm{otherwise}\end{array},0\le i\le m-1,$ computing, after k operating cycles for each initial state, a new state of the LFSR
Y=(q′.sub.m−1,q′.sub.m−2, . . . ,q′.sub.1,q′.sub.0), computing a (jk+l)-th value for a matrix H.sub.r by concatenating k values of stages q′.sub.m−1, q′.sub.m−2, . . . , q′.sub.m−k
H.sub.r,jk+l=q′.sub.m−1∥ . . . ∥q′.sub.m−k, computing
l=l+1, going to step A6; (A7) recording, into stages of a modified LFSR, blocks s of the original message S, where an initial state of the stages of the modified LFSR, q.sub.i, forms a vector
X′=(Q.sub.R−1, . . . ,Q.sub.1,Q.sub.0), where Q.sub.r=q.sub.kr+k−1∥ . . . ∥q.sub.kr, and also 0≦r≦R−1; performing R cycles of the modified LFSR by performing at each cycle the following actions: computing an output state of the stages of the modified LFSR Q′.sub.i for one cycle, thereby forming the vector
Y′=(Q′.sub.R−1, . . . ,Q′.sub.1,Q′.sub.0), each value Q′.sub.i, of said vector being computed by the formula
Q′.sub.i=Q.sub.i+1 for each i=0, . . . , R−2, and a value Q′.sub.m−1 is computed from $Q_{R-1}^{\prime }=\stackrel{R-1}{\underset{r=0}{\oplus }}.Math.f\left(H_r\right),.Math.\mathrm{where}.Math..Math.f\left(H_r\right)=\stackrel{W-1}{\underset{j=0}{\oplus }}.Math.Z_{r,j}.Math.H_{r,j},$ where z.sub.r,j is a value of a j-th bit of a vector Q.sub.r, wherein r=R−1, . . . , 1, 0, j=0, 1, . . . , W−1, z.sub.r,jεGF(2); obtaining, after the R cycles of the LFSR, a linear transformation of the blocks s of the message S; reading out, from the stages of the modified LFSR, blocks s of a linearly transformed message S; combining the blocks and obtaining the linearly transformed message S.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0201] FIG. 1 shows a workflow of a Galois-type linear feedback shift register in the forward direction.

[0202] FIG. 2 shows a workflow of the Galois-type linear feedback shift register in the reverse direction.

[0203] FIG. 3 shows a workflow of a Fibonacci-type linear feedback shift register in the forward direction.

[0204] FIG. 4 shows a workflow of the Fibonacci linear feedback shift register in the reverse direction.

[0205] FIG. 5 shows a workflow of a modified Galois-type linear feedback shift register.

[0206] FIG. 6 shows a flow chart of an algorithm for computing feedback function tables of the modified Galois-type linear feedback shift register.

[0207] FIG. 7 shows a workflow of a modified Fibonacci-type linear feedback shift register.

[0208] FIG. 8 shows a flow chart of an algorithm for computing feedback function tables of the Fibonacci-type modified linear feedback shift register.

[0209] FIG. 9 shows a schematic diagram of a Galois-type linear feedback shift register for a forward linear transformation, illustrating an embodiment of the method.

[0210] FIG. 10 shows a schematic diagram of a Galois-type linear feedback shift register for a reverse linear transformation, illustrating an embodiment of the method.

[0211] FIG. 11 shows a workflow of a modified Galois-type linear feedback shift register for a forward linear transformation, illustrating an embodiment of the method.

[0212] FIG. 12 shows a workflow of a modified 16-bit Galois-type linear feedback shift register for a forward linear transformation, illustrating an embodiment of the method.

[0213] FIG. 13 shows a workflow of a modified 32-bit Galois-type linear feedback shift register for a forward linear transformation, illustrating an embodiment of the method.

[0214] FIG. 14 shows a workflow of a modified 64-bit Galois-type linear feedback shift register for a forward linear transformation, illustrating an embodiment of a method.

DESCRIPTION OF EMBODIMENTS OF THE INVENTION

[0215] An exemplary implementation of the present method using a modified Galois-type LFSR will be described hereinbelow.

[0216] The present method can be implemented in an application for a computing system, and a computer with one processor that has the word size of 8-bit and higher and operates under control of an operating system (for example, Microsoft Windows 7) can serve as such a computing system.

[0217] The application for implementing operation of a Galois (or Fibonacci)-type LFSR can be developed by an artisan skilled in the field of programming based on the knowledge of conventional principles and structures of a LFSR of an appropriate type and the steps of the method provided hereby.

[0218] For the sake of convenience in analysis and synthesis, the description of the invention considers a linear transformation L with specific parameters typical to a large class of cryptographic algorithms: [0219] an initial linear transformation L:V.sub.128V.sub.128; [0220] a composite field GF((2.sup.8).sup.16) (m=16, n=8); [0221] an internal primitive polynomial

f(x)=x.sup.8⊕x.sup.7⊕x.sup.6⊕x⊕1 [0222] for generating the field GF(2.sup.8); [0223] an external irreducible polynomial h(y) for generating the composite field GE((2.sup.8).sup.16)

h(j)=y.sup.16+148y.sup.15+32y.sup.14+133y.sup.13+16y.sup.12+194y.sup.11+192y.sup.10+y.sup.9++251y.sup.8+y.sup.7+192y.sup.6+194y.sup.5+16y.sup.4+133y.sup.3+32y.sup.2+148y+1,

[0224] where

[0225] (h.sub.15, h.sub.14, . . . , h.sub.0)=(148, 32, 133, 16, 194, 192, 1, 251, 1, 192, 194, 16, 133, 32, 148, 1) h.sub.iεGF(2.sup.8)

[0226] FIG. 9 and FIG. 10 show a LFSR configuration for the forward transformation L and a LFSR configuration for a reverse transformation L.sup.−1, respectively.

[0227] A useful property for a linear transformation has been recently discovered in cryptography: if any sequence of symbols is recorded into stages of a LFSR and the register is “shifted” left 16 times, then check code symbols with the maximum distance will remain in the register (MDS-code): C(32, 16, 17) [6]. The minimum distance between any code words of this code is 17. If such a code is taken as a linear transformation of a block cipher, then it will have the maximum dispersion property (d=17).

[0228] The operating sequence for one cycle of the LFSR is the following: [0229] an initial state—a vector X=(q.sub.15, q.sub.14, . . . , q.sub.2, q.sub.1, q.sub.0), where q.sub.iεGF(2.sup.8), 0≦i≦15. The vector X has 16 coordinates disposed from left to right in 16 stages of the LFSR, starting from the coordinate with the index i=15; [0230] in operation of a Galois LFSR only the value q.sub.15 in the highest stage is involved in obtaining the feedback function value; [0231] an output state—a vector Y=(q′.sub.15, q′.sub.14, . . . , q′.sub.2, q′.sub.1, q′.sub.0), where q′.sub.iεGF(2.sup.8), 0≦i≦15. Vales q′.sub.i for each i=15, . . . , 1 are computed as

q′.sub.i=h.sub.i.Math.q.sub.15⊕q.sub.i−1,

[0232] while q.sub.0=h.sub.0.Math.q.sub.15

[0233] The linear transformation L of the original data vector

X=(q.sub.15,q.sub.14, . . . ,q.sub.2,q.sub.1,q.sub.0)

will refer herein to 16 operating cycles of the LFSR.

[0234] The transformation results in a new state of the register at the m-th cycle, which can be written down as

Y=(q′.sub.15,q′.sub.14, . . . ,q′.sub.2,q′.sub.1,q′.sub.0),

[0235] where q′.sub.iεGF(2.sup.8), 0≦i≦15 are values of stages of the LFSR.

[0236] The reverse transformation L.sup.−1 takes 16 operating cycles of the LFSR in the reverse direction.

[0237] Let us denote some divisor of the number m=16 as k (the selection thereof is defined by the available processor word W and available amount of memory M).

[0238] The essence of the present way of implementing on an appropriate platform depends on the value k and is based on applying the superposition principle when considering the effect of each bit of the current state of the LFSR on the subsequent state, in accordance with the fact that for each k there is a way to implement the transformation L at an (nk)-bit processor.

[0239] The following cases will be discussed hereinbelow.

[0240] Computation case 1: k=1. This case considers the way of implementing the transformation L at 8-bit processors (n.Math.k=8.Math.1=8). For this case the following steps are performed: [0241] computing a number r of required computable tables

[00032]$H_j,j=15,\mathrm{.Math.}.Math.,0$$r=\frac{m}{k}=\frac{16}{1}=16$ [0242] computing 16 tables H.sub.j, j=15, . . . , 0, each having nk=8.Math.1=8 elements, where the elements are 8-bit numbers (elements of the field GF(2.sup.8)), by performing the following steps: [0243] computing a respective state of the LFSR (FIG. 1) after k=1 operating cycles for each initial state

[00033]$X=\left(q_{m-1},q_{m-2},\mathrm{.Math.}.Math.,q_2,q_1,q_0\right)=\left(q_{15},\underset{\underset{15.Math..Math.\mathrm{times}}{}}{0,\mathrm{.Math.}.Math.,0}\right)$

[0244] for all q.sub.15=2.sup.l, l=0, . . . , 7, i.e. the effect of each bit of the number q.sub.15 on the state of the LFSR (FIG. 1) after k=1 operating cycles is considered; the result is nk=8 states; [0245] forming an array A of nk=8 obtained states in such a way that its last row corresponds to the state at j=m−k=16−1=15 and l=0, and the penultimate road corresponds to the state at j=m−k=16−1=15 and l=1, and so on. As a result of doing so, the array A has nk=8 rows and m=16 columns. The first column of the array A corresponds to values of the stage q.sub.15, the second one—to q.sub.14, and so on (Table 1): [0246] when k=1, the tables H.sub.j, j=15, . . . , 0 are equal to each column of the array A in accordance with indices.

TABLE-US-00001 TABLE 1 Results of LFSR operation after one cycle Initial states States of LFSR q.sub.15, . . . , q.sub.0 H15 H14 H13 H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1 H0 2.sup.7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 E5 6D B2 D7 6E AD 80 DE 80 AD 6E D7 B2 6D E5 80 2.sup.6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 93 D7 59 8A 37 B7 40 6F 40 B7 37 8A 59 D7 93 40 2.sup.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 A8 8A CD 45 FA BA 20 D6 20 BA FA 45 CD 8A A8 20 2.sup.4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 54 45 87 C3 7D 5D 10 6B 10 5D 7D C3 87 45 54 10 2.sup.3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 2A C3 A2 80 DF CF 08 D4 08 CF DF 80 A2 C3 2A 08 2.sup.2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 15 80 51 40 8E 86 04 6A 04 86 8E 40 51 80 15 04 2.sup.1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 EB 40 C9 20 47 43 02 35 02 43 47 20 C9 40 EB 02 2.sup.0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 94 20 85 10 C2 C0 01 FB 01 C0 C2 10 85 20 94 01 [0247] generating an extended LFSR configuration (FIG. 5) which has r=16 stages, each having a value representing a 8-bit number; [0248] denoting a state of the extended LFSR as (Q.sub.15, Q.sub.14, . . . , Q.sub.2, Q.sub.1, Q.sub.0), where Q.sub.iεGF(2.sup.8), i=15, 14, . . . , 0; [0249] determining a value f(H.sub.j) of the feedback function for each H.sub.j by the formula

[00034]$\begin{array}{cc}f\left(H_j\right)=\stackrel{7}{\underset{u=0}{\oplus }}.Math.w_{15,u}.Math.H_{j,u},& \\ \mathrm{where}& \\ j=15,\mathrm{.Math.}.Math.,1,0,& \\ w_{15,u}\in \mathrm{GF}\left(2\right)& \end{array}$ [0250] u=0, 1, . . . , 7-bits of the stage Q.sub.15 of the extended LFSR.

[0251] This means that if the u-th bit of the stage Q.sub.15 equals unity, then the respective row H.sub.j,u participates in the process of deriving the feedback function value. [0252] The forward linear transformation L comprises r=16 cycles of the extended LFSR; [0253] The 16 cycles of the extended. LFSR require

[00035]$r.Math.n.Math.k=\frac{m}{k}.Math.n.Math.k=m.Math.n=16.Math.8=128$

“true-false” check operations for all bits of the stage Q.sub.15 and

[00036]$r.Math.r.Math.n.Math.k=\frac{m}{k}.Math.\frac{m}{k}.Math.n.Math.k=\frac{m^2.Math.n}{k}=\frac{{16}^2.Math.8}{1}=2048$

modulo-2 addition operations for two n×k-bit numbers and Q.sub.l and H.sub.l,j, where l=0, 1, . . . , r−1 and j=0, 1, . . . , nk.

[0254] The required amount of memory is

[00037]$r.Math.\left(n.Math.k\right).Math.\left(n.Math.k\right)=\frac{m}{k}.Math.{\left(n.Math.k\right)}^2=m.Math.n^2.Math.k=16.Math.8^2.Math.1=1024$

bits=128 bytes for storing 16 tables H.sub.j, j=15, . . . , 0.

[0255] The order of implementing the reverse linear transformation L.sup.−1 at 8-bit processors is performed similarly, using the LFSR (FIG. 2) for computing 16 tables H.sub.j, j=15, . . . , 0. Due to symmetry of the external irreducible polynomial h(y) for the discussed linear transformation, the same 16 tables H.sub.j, j=15, . . . , 0 can be used both for the forward transformation and for the transformation reverse thereto.

[0256] Computation case 2: k=2. In this case a method of implementing the transformation L at 16-bit processors is considered. The method comprises the following steps: [0257] Computing a number r of required computable tables H.sub.j, j=7, . . . , 0

[00038]$r=\frac{m}{k}=\frac{16}{2}=8$ [0258] computing r=8 tables, H.sub.j, j=7, . . . , 0, each having nk=8.Math.2=16 elements, where the elements are 16-bit numbers, by performing the following steps: [0259] computing a respective state of the LFSR (FIG. 1) after k=2 operating cycles for each initial state

[00039]$X=\left(q_{m-1},q_{m-2},\mathrm{.Math.}.Math.,q_2,q_1,q_0\right)=\left(q_{15},q_{14},\underset{\underset{14.Math..Math.\mathrm{times}}{}}{0,\mathrm{.Math.}.Math.,0}\right)$ [0260] for all

q.sub.j=2.sup.l, j=14,15 l=0, . . . , 7, [0261] beginning from the stage at the position j=m−5=16−2=14, i.e. the effect of each bit of the number q.sub.15∥q.sub.14 on the state of the LFSR is considered (FIG. 1) after k=2 cycles. nk=16 states are obtained as a result: [0262] generating an array A of nk=16 obtained states such that its last row corresponds to the state at j=m−k=16−2=14 and l=0, and its penultimate row corresponds to the state at j=m−k=16−2=14 and l=1, and so on, and the first row of the array A corresponds to the state at j=m−1=16−1=15 and l=n−1=8−1=7. As a result of doing so, the array A has nk=16 rows and m=16 columns; [0263] forming r=8 tables H.sub.j, j=7, . . . 0, beginning from the value j=(r−1)=8−1=7, by concatenating k=2 values in adjacent columns of the array A, beginning from its first column, wherein the numbering in performed in such a way that, e.g. for the table H.sub.7, the value in the first row of the first column after the concatenation corresponds to H.sub.7,15, while the value in the last row of the same column corresponds to H.sub.7,0 (Table 2).

TABLE-US-00002 TABLE 2 States of LFSR after two operating cycles Initial states States of LFSR after concatenation of two adjacent stages No q.sub.15, . . . , q.sub.0 H.sub.7 H6 H5 H4 H3 H2 H1 H0 15 2.sup.7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 3222 2526 4266 3B76 4888 38FA 9F75 DFE5 14 2.sup.6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 1911 F313 2133 FC3B 2444 1C7D AEDB 8E93 13 2.sup.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 EDE9 98E8 F1F8 7EFC 1222 0EDF 578C 47A8 12 2.sup.4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 9795 4C74 997C 3F7E 0911 078E CA46 C254 11 2.sup.3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 AAAB 263A AD3E FE3F E5E9 E247 6523 612A 10 2.sup.2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 55B4 131D B71F 7FFE 9395 71C2 D3F0 D115 9 2.sup.1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 CB5A E8EF BAEE DE7F A8AB D961 8878 89EB 8 2.sup.0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 842D 7496 5D77 6FDE 54B4 8DD1 443C A594 7 0, 2.sup.7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 E56D B2D7 6EAD 80DE 80AD 6ED7 B26D E580 6 0, 2.sup.6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 93D7 598A 37B7 406F 40B7 378A 59D7 9340 5 0, 2.sup.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 A88A CD45 FABA 20D6 20BA FA45 CD8A A820 4 0, 2.sup.4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 5445 87C3 7D5D 106B 105D 7DC3 8745 5410 3 0, 2.sup.3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 2AC3 A280 DFCF 08D4 08CF DF80 A2C3 2A08 2 0, 2.sup.2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 1580 5140 8E86 046A 0486 8E40 5180 1504 1 0, 2.sup.1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 EB40 C920 4743 0235 0243 4720 C940 EB02 0 0, 2.sup.0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 9420 8510 C2C0 01FB 01C0 C210 8520 9401 [0264] generating an extended configuration of the LFSR, where the extended LFSR has r=8 stages, each having a value representing a 16-bit number; [0265] a state of the extended LFSR can be represented as

(Q.sub.7,Q.sub.6, . . . ,Q.sub.2,Q.sub.1,Q.sub.0) [0266] determining a value f(H.sub.j) of the feedback function for each H.sub.j by the formula

[00040]$\begin{array}{cc}f\left(H_j\right)=\stackrel{15}{\underset{u=0}{\oplus }}.Math.w_{7,u}.Math.H_{j,u},& \\ \mathrm{where}& \\ j=7,\mathrm{.Math.}.Math.,1,0,& \\ w_{7,u}\in \mathrm{GF}\left(2\right)& \end{array}$ [0267] u=0, 1, . . . , 15-bits of the stage Q.sub.7 of the extended LFSR.

[0268] This means that, if the ii-th bit of the stage Q.sub.15 equals unity, then the respective row H.sub.j,u participates in the process of deriving the feedback function value.

[0269] The forward linear transformation L comprises r=8 operating cycles of the extended LFSR, where the 8 operating cycles of the extended LFSR require

[00041]$r.Math.n.Math.k=\frac{m}{k}.Math.n.Math.k=m.Math.n=16.Math.8=128$

“true-false” check operations

[0270] and

[00042]$r.Math.r.Math.n.Math.k=\frac{m}{k}.Math.\frac{m}{k}.Math.n.Math.k=\frac{m^2.Math.n}{k}=\frac{{16}^2.Math.8}{2}=1024$

modulo-2 addition operations of two 16-bit numbers.

[0271] The required amount of memory is

[00043]$r.Math.\left(n.Math.k\right).Math.\left(n.Math.k\right)=\frac{m}{k}.Math.{\left(n.Math.k\right)}^2=m.Math.n^2.Math.k=16.Math.8^2.Math.2=2048$

bits=256 bytes for storing 8 tables H.sub.j, j=7, . . . , 0.

[0272] FIG. 12 shows the obtained resulting configuration.

[0273] The order of implementing the reverse linear transformation L.sup.−1 at 16-bit processors is performed similarly with the use of the LFSR (FIG. 2) to form 8 tables H.sub.j, j=7, . . . , 0. Due to symmetry of the external irreducible polynomial h(y) for the discussed linear transformation, the same 8 tables H.sub.j, j=7, . . . , 0 can be used to implement both the forward transformation and the transformation reverse thereto.

[0274] Similarly, at k=4 and k=8, the forward linear transformation L and the one reverse thereto can be implemented at 32 and 64-bit processors (FIGS. 13 and 14, respectively).

[0275] Table 3 shows the results of calculations of numerical values typical to preforming the present method using the Galois-type LFSR.

TABLE-US-00003 TABLE 3 Results of calculations of numerical values typical to preforming the present method using the Galois LFSR Word size Number of Amount of Number of Required of the required required modulo-2 number of processor “true/false” memory, additions of two processor used checks bytes memory stages cycles 8 128 128 2048 16 16 128 256 1024 8 32 128 512 512 4 64 128 1024 256 2

[0276] Comparative analysis of values presented in Table 3 shows that the present method makes it possible to select inter-related parameters of the computing system.

[0277] For example, if a 8-bit processor is available, then implementation of the specified linear transformation will require the minimum memory amount of 128 bytes and 16 shift operations for sixteen bytes.

[0278] If a more powerful 64-bit processor is available, then implementation of the specified linear transformation will require 1024 bytes of memory and only 2 shift operations for two 64-bit words.

[0279] As a result, the use of the present method also offers additional opportunities to developers in designing an application program or a hardware unit of a computing system that implements the linear transformation, and taking into account the requirements emerging in practice.

REFERENCES CITED

[0280] 1. EA 1514174. [0281] 2. U.S. Pat. No. 5,946,473 [0282] 3. Nicolay Borisenko, Nguyen Van Long, Alexey Bulygin, Algorithm design software and hardware implementation of large size linear mapping. 2nd Workshop on Current Trends in Cryptology (CTC pt 2013) Jun. 23-25, 2013, Ekaterinburg, Russia. Pre-proceedings, pp. 192-205: [0283] 4. Mikhail Borodin, Andrey Rybkin, Alexey Urivskiy. High-Speed Software Implementation of the Prospective 128-bit Block Cipher and Streebog Hash-Function, 3rd Workshop on Current Trends in Cryptology (CTCrypt 2014) June 5-6, 2014, Moscow, Russia. Pre-proceedings, pp. 189-197; [0284] 5. Kuzmin A. S., Nechaev A. A., Linear recurring sequences over Galois rings, Algebra and Logic, 3:2 (1995), pp. 169-189; [0285] 6. Couselo E., Gonzalez S., Markov V. T., Nechaev A. Recursive MDS-codes and recursively differentiable quasigroups. Discrete Mathematics, Volume 10, Issue 2, 1998, pp. 3-29.