This paper deals with block and stream ciphers as the structures analogous to those of digital filters. A cipher implemented in the form of the canonical structure of the digital filter is considered. This cipher has a reversibility property when the points of transforms corresponding to the coefficients of the forward and backward branches of the filter are interchanged. In this implementation, for the block ciphers input block is the initial state of the filter, subkeys are the filtered input sequences of the filter's samples and the output block is the end-state of the filter. For the stream ciphers, the key is the initial state of the filter and gamma is the filter's output for the zero input sequence. Finally, an example of the stream cipher implemented in the form of the structure of the second-order infinite impulse response filter is presented. For hardware implementation, this stream cipher has the ultimate speed performance.
Cryptography is one the most important areas in
modern communications, not least because it
applies to pervasive computing and the Internet
of Things [1, 2]. There are conflicting
requirements when it comes to modern ciphers
[3, 4]. On the one hand, they should be robust
enough against any attempts to crack them,
while on the other hand—they are supposed to
be fast when it comes to encoding and decoding
operations to secure required data transmission
rates [5]. There are many studies aimed at
resolving this contradiction [
Surprisingly enough, there is an analogy between operations performed during these procedures and those carried out in digital filters. This paper draws the parallel between the two and determines that using an implementation of the coding and decoding operations embedded in the structure of the corresponding recursive digital filter permits achieving the ultimate speed that is of one tact encoding.
Traditionally, it is accepted to present block cipher structures as a sequence of operations. For example, an Advanced Encryption Standard (AES) cipher round is depicted in the form of a series of four consecutive operations, as shown in Fig. 1: • SubBytes (state). • ShiftRows (state). • MixColumns (state).
• AddRoundKey (state). There are a lot of various objects with the same structural features that are analogous to the operation of division by a polynomial. For example, analogs of division by a polynomial are the following elements: • Integrator. • Filter with Infinite Impulse Response (IIR). • Self-synchronizing scrambler. • Encoder in the gaming mode with Cipher
Feedback (CFB).
On the other hand, among the objects that are analogous to polynomial multiplication, one can name the following: • Differentiator. • Filter with Finite Impulse Response (FIR). • Self-synchronizing descrambler. • Decoder in the CFB mode.
Some filters combine the operations of the polynomial multiplication and division. For example, decimating the Cascaded IntegralComb (CIC) filter performs first polynomial division and then polynomial multiplication.
Another example is an interpolating CIC filter, which first performs polynomial multiplication and after that—polynomial division.
There are plenty of examples that show that encoding operations can be presented as an IIR filtering process. In particular, the iterative block cipher type of Substitution-Permutation Networks (SPN), which belongs to a wellknown AES standard, can be implemented with the help of the IIR filter structure with polynomial division. Fig. 2 illustrates the firstorder IIR filter structure with transfer function as follows:
H (z) =
1 A(z) =
1 1 − a1z −1 (1) for the adder. The filter is fed with signal samples x, while the resulting samples y are formed at the output.
The operation block diagram of the SPN cipher, which is suitable for implementation in the form of the filter, is shown in Fig. 3. Let us consider its elements. In Fig. 3, R is a parallel register, which stores current values of B bits of the cipher; S and M represent round function (substitution and permutation, correspondingly); and + denotes adder (modulo-two addition).
If one compares the operation block diagram in Fig. 3 with the structure of the firstorder IIR filter in Fig. 2, it is easy to see that the multiplier by -a1 in Fig. 2 is replaced by the functional transformer in Fig. 3 that implements the round function; the input in Fig. 3, equivalent to the input of the filter in Fig. 2, is fed with subkeys x. The initial state of the operation block diagram in Fig. 3 is the input data block to be encoded; the state of the operation block diagram in Fig. 3 after several steps represents the resulting encoded block, while output y of the operations block diagram in Fig. 3 is not used.
Fig. 4 illustrates the structure of the secondorder IIR filter with the following transfer function: (2) In (1), Z–1 represents a one-sample delay element (usually parallel register), -a1 denotes the multiplier by -a1 coefficient, and + stands In this case, the input is not represented by the signal x, but rather by the state of the delay elements R and L, both the right and the left parts, each with the size В/2, of the input block with the size В, while х is just the sequence of the subkeys. Filter output y is not used. The results of the transform are the states of the delay elements after filtration of the r samples (rounds number) of the input vector х. For example in the State Standard of Ukraine, №28147 input В constitutes 64 digits, registers R and L have 32 digits, S is eight 4digit tables and М represents cyclic shift. Subkeys are 32 integer samples each with 32 digits. Addition operation with subkeys is performed at a somewhat different point (not after the delay in the register R, but rather before it); the position of this point does not influence the cipher properties. The operations are non-linear and are performed in the different rings with powers 1, 4, and 32, which makes this filter non-linear.
Let us consider another such IIR filter with two unity coefficients ai = 1 and aj = 1 while the other coefficients equal zeros.
Such a filter will have one pole, situated on the unity circle in the z-plane, and will be unstable so that its pulse response does not subside. Filter implementation in the form of the delay line, the input of which is fed with the sum of the signals at the taps i and j will just represent the generator with the no-zero initial state of the delay line. Fairly quickly, such a generator (under usual integer arithmetic without saturation) will break out of the linear mode and will overflow by the module of the bit depth. If i = 24 and j = 55, then it turns into a version of delayed Fibonacci filters, which is widely used in cryptography (pairs of taps i and j might be different, the period of maximum length is given by only some of the pairs).
For synchronous stream cipher, as a rule, key х (subkeys) at the initial stage forms the state of the registers, and then input х assumes zero value and the sequence of the cipher states is determined by the functions а, while functions b determine the output values of y, which is used as a gamma of the cipher. In particular, when the bit depth equals unity, and the coefficients amount to “0” or “1”, one arrives at the classical structure of the Linear Feedback Shift Register (LFSR).
If this structure is used as a stream cipher, of which input х during encoding will be plaintext, and output y will represent ciphertext, then for decoding operation it is necessary to interchange coefficients а and b: in other words, interchange numerator and denominator.
All this allows one to come to a very simple but at the same time promising conclusion: block and stream ciphers can be presented structurally by similar schemes, which in turn are in many respects similar to classical structures of the digital filters.
The transfer function of the recursive digital filter looks as follows:
H ( z) =
B( z) A( z) =
M m=0 bm z −m
N 1 − n=1 an z −n (3) where bm is the coefficients of the nonrecursive filter section, an—coefficients of the recursive section, and z–t is the signal’s delay for t samples.
Under the conditions N = M and b0 = 1, the reverse filter is feasible and can be obtained by interchanging denominator: in nominator and H −1( z) = A(z) =
B(z)
N a z−n n=1 n 1 − mM=1 bm z−m which from the output sequence of the forward filter restores its input one.
Filter’s difference equation can be presented in the following form:
y(k) = x(k) − nN=1anDn (k −1) +nN=1bnDn (k −1) (5) where yk is the output sample of the filter, xk is the input sample of the filter, Dn() is the value of the signal at the n-th tap of the delay line, which is determined as follows:
Dn (k ) = Dn−1(k −1) n = N ,...,2 and
D1(k ) = x(k ) − nN=1 an Dn (k −1) .
The Canonical Structure of the Filter (CSF), corresponding to the equations (4)–(7), can be presented in the form shown in Fig. 6. The reversibility property of such a structure (restoration of the input signal from the output one) under commutation of the coefficients an and bn is preserved, even if the addition operation is replaced by any commutative operation, and multiplication—by any functional transformation, including irreversible one.
CSF allows designing the cipher in which encoding and decoding schemes differ by the interchange of the transfer points for an and bn.
If one fixes the size of the internal state of the cipher (for example, 128 bits), then the filter order N and cipher width B (bit depth of the delay line registers) can be scalable. This scalability holds up for N = 1 and B = 128 as well as up to N = 128 and B = 1. For example, if one sets the element to be encoded as a bite of (4) (6) (7) data, then one gets the cipher with N = 16 and B = 8.
In this case, in a certain sense, N appears as an analog of the number of block cipher rounds, while the transforms an and bn are analogs of the round functions.
And, if for B = 1, the functions are set by the simple substitutions: input values, inverse values of the input, constant “0” and constant “1” (this leads to classical stream ciphers with single digit-depth registers), for B = 8 the most reasonable seems to be random permutations 8×8, set by the table; for B = 128, the problem requires a special consideration.
Let us consider a specific version of the CSF cipher with N = 1 and B = 128, for which encoding and decoding schemes are presented in Fig.7. In Fig. 7, D1 is a delay element in the form of a 128-digit parallel register; and a1 and b1 are functional transforms, approximated to fixed random substitutions with the size 128×128. Addition operations are presented by 128digit modulo-two adders.
Transform dependence on the key can be introduced either into the initial state (as in stream ciphers), or into functional transforms, for example. For the case presented in Fig. 8, the 256-bit-long key is split into two halves: K1 and K2, which are added on modulo-two addition with the inputs and outputs of the functional transformers a1 and b1 by the Even– Mansour cipher [6]. Functional transformers a1 and b1 can be implemented in the form of “wide” S-blocks, comprising each, for instance, 16 tables of fixed random substitutions S0—S15 with the size 8×128. Concatenation of the 16 inputs of these blocks forms the 128-bit input of the transform, while the modulo-two addition of all 16 128-bit table inputs creates the output of the transform. The structure of such a functional transformer is shown in Fig. 9. Any selection of the S-blocks is most likely not required because the combinational power of such a block is very large (2 power around 500000) and the probability of getting a randomly “bad” block is negligibly small. Such Sblocks for encoding N*B bits are used once, while in SPN ciphers one S-block is used repeatedly a hundred times for encoding one block of data, which requires a very strict approach to its formation. Of course, memory volume for the realization of “wide” S-blocks is rather significant—128 Кbite for a certain example, but currently such a volume is a fairly available resource.
A supposed advantage of CSF class ciphers appears to be monotonous scalability on N and B, which in addition to cipher adaptation to the particular tasks allows one to research reduced versions of the ciphers. In addition, hardware implementation of the cipher permits reducing the encoding time of B bits to one tact encoding.
In [7], it is considered a stream cipher named “Krip” with the structure of 2nd order IIR filter that comprises functional transforms φ and ψ, which correspond to a and b coefficients in the filter structure.
As the transform φ, round function of the
cipher “Kalyna” with a block length of 256 bits
is used, and as a transform ψ is a round
function of the same cipher with a block length
of 512 bits [
Fig. 10 demonstrates the diagram of the “Krip” cipher in the encoding mode. As the key, initial states of the cipher S1 and S2 with a total length of 512 bits are used, while vector X is a plaintext and vector Y is a ciphertext.
While encoding with the help of the transform starting from S1, S2, a gamma vector is formed that is summed with the vector of the plaintext X to obtain the vector of the ciphertext Y. Plaintext vector X is used for forming a new value of the state S1, while the previous value of S1 is transferred into S2.
During decoding, from S1, S2 with the help of the transform, a gamma vector is formed, which is added to the vector of the ciphertext Y to obtain the vector of the plaintext X. Plaintext vector X is then used for forming a new value of the state S1, while the previous value of S1 is transferred into S2. Such a stream cipher with the hardware implementation in the form of the secondorder IIR filter wields maximum speed performance by encoding input vector in just one tact of operation.
Encoding and decoding operations can be presented as filtering processes in IIR filters.
This is true for both block ciphers and stream ciphers. This allows one to come to a very clear and promising conclusion: block and stream ciphers can be represented structurally by similar schemes, which in turn are in many respects similar to classical structures of the IIR filters.
The example of the stream cipher with the hardware implementation in the structure of the 2nd order IIR filter secures maximum speed performance, which allows encoding input vector in just one tact of operation.