Effective computation of cryptanalytic measures for stream cipher data by the Rissanen algorithmus

              Rev. Acad. Canar. Cienc., XIX (Núms. 1-2), 9-22 (2007) (publicado en septiembre de 2008)
EFFECTIVE COMPUTATION OF CRYPTANALYTIC
MEASURES FOR STREAM CIPHER DATA BY THE RISSANEN
ALGORITHMUS
Franz Pichler
Prof. Emeritus (Systems Theory)
Johannes Kepler University Linz
A-4040 Linz, Austria
E-mail: franz.pichler@jku.at
Abstract: The paper presents an application of the algebraic theory of linear systems realization as
originally established in mathematical systems theory by Rudolf Kalman to the problem of the
determination of the linear complexity profile of pseudo-random sequences as they appear in the
cryptanalyis of stream cipher systems. For the necessary effectiveness of the realization
computation the PQ- decomposition of Hankel matrices according to the method of Rissanen is
used. The proposed new method of cryptanalysis generalizes the Massey-Berlekamp algorithmus to
the case of multi-variable sequences over GF(q).
Resumen: El trabajo presenta una aplicación de la teoría algebraica de la realización de sistemas
lineales, tal como se estableció originalmente en la teoría matemática de sistemas por Rudolf
Kalman, al problema de la determinación del perfil de complejidad lineal de secuencias
seudoaleatorias como aparecen en el criptoanálisis de los sistemas cifrados en cadena. Para la
necesaria efectividad de la realización se usa la computación de la descomposición PQ de matrices
de Hankel, de acuerdo con el método de Rissanen. El nuevo método de criptoanálisis aquí
propuesto generaliza el algoritmo de Massey-Berlekamp para el caso de secuencias multivariable
sobre GF(q).
1 INTRODUCTION
An important problem in cryptanalysis is to determine for a given stream of data
S=S(O),S(l),S(2), .... an associated autonomous linear finite state machine ALFSM=(F,H) andan
initial state x(O) of it, such that ALFSM generates from x(O) the data stream S. A similar problem is
to determine from a given observed impulse response A= AO,AI,A2, .... the corresponding linear
system E=(F,G,H). In mathematical systems theory this problem is known as the "realization
problem". The mathematical basis for its solution is provided by the important work of Rudolf
Kalman by his "Algebraic Theory of Linear Systems" ([Kalman 1963], Kalman-Falb-Arbib
[1969]). A computational effective method for the computation of a mini mal realization using the
9
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
concept of Hankel matrices has been developed by Kalman and Ho ([Ho-Kalman 1966]. In
practica! cases of cryptanalytic investigations the observed stream cipher data have a finite length
S(M)= S(OJ,S(IJ,S(2), .. .,S(M-1). ln systems theory this compares to a impulse response A(M)=
Ao,A1,A2,. . .,AM-1 offinite length. ln this case we have the systems-theoretical problem of "partial
realization". A computational effective recursive method to solve the partial realization problem,
which applies even for very long data streams A(M) has been originally developed by Jonna
Rissanen ([Rissanen 197 I ]). The method works for ali linear systems .I:=(F, G,H) o ver a field K.
For the desired applications in_ the field of cryptology it is sufficient to assume that we deal with
linear systems overa finite field K=GF(q).
In this paper we give first an introduction to the algebraic theory of realization and to the Rissanen
method of partial realization. Then we show how the Rissanen method can be applied to measure
the cryptanalytic quality of sequences S(M) as they appear in stream cipher applications. This is
possible, since the solution ofthe partial realization problem gives also a solution ofthe associated
state identification problem. For scalar data streams S(M) such measures are provided by the
Massey-Berlekamp algorithm, which is well known in the field of cryptanalysis. Our method by
applying the "Rissanen algorithm" extends this results to multi-valued data streams S(M).
2 ALGEBRAIC THEORY OF LINEAR SYSTEMS REALIZATION
2.1 Linear automatafundamentals
Let a linear finite state machi ne LFSM over the finite fíe Id K =GF(q) be given by LFSM=(F, G,H)
with the state transition given by x(t+ 1) = F x(t) + G u(t) and associated output y(t) by
y(t) = H x(t). F, G and H denote here matrices of size nxn, nxm and p><n, respectively. x(t) denotes
the state at time t, u(t) and y(t) are the values of the input word u and the output word y at time t,
respectively. A LFSM is a linear time-invariant discrete time system with the time set T given by
the set No of natural numbers No= O, 1,2, ... . lt is convenient to write the input words and the output
words of a LFSM as time functions of the kind u: No -;K111 and y: No-+~ with finite support su ch
that there exists for each input function u and each output function y numbers ful and !vi ,such that
for ali r>lu/ and t>/y/ we ha ve u(t)=O and y(t)=O, respectively. For a given initial state x(O) and
input function u the linear finite state machine LFSM computes a related state trajectory x and
output function y as follows:
10
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
t-1
x(t)=F1x(O) + Lpt-i -1Gu(i) for t= 1,2, .. .ful (2.1)
i=O
and
y(t) = H x(t) for t=O, 1,2, .. ./u/-1 (2.2)
Let U and Y denote the set of ali input functions of LFSM and let Q denote its state set.
For our purpose it is convenient to define for a LFSM the function MQxU--7Y which assigns for
the initial state q=x(O) and input function u the related output function y=M(x(O),u). By linearity of
LFSM we have M(x(O),u) = M(x(O),O) + M(O,u). From the expression (2.1) and (2.2) we see that
t-1
M(x(O),O)(t) = F1x(O) , M(O,t)(O)=O and M(O,u)(t) = L HF-i _, Gu(i) for t=l ,2, .. .ful (2.3)
i=O
M(x(O),O) is called the zero-input response function of LFSM and M(O,u) is the zero- state response
fimction. The specific output function ai of LFSM which is the zero- state response function
M(O,ei), where ei denotes for i=l ,2, ... ,m the unit impulse input function, is called the ei-impulse
response function. The matrix-valued function a=(al,a2, ... ,am) which is generated as output of
LFSM by the different 1/0-experiments (ei,ai), i= 1,2, ... ,,m, is called the impulse responsefimction
of the LFSM.'l
2.2 FSM machine identification and FSM state identijication
Por our further discussion ofthe realization problem we repeat the following definitions from the
theory offinite state machines. A single 1/0 pair (u,y) of a finite state machine FSM is called a
single experiment, a set of single experiments is called a mu/tiple experiment. The problem to
determine for a given experiment the associated finite state machine FSM is called a machine
identification problem. The problem to determine from a given experiment the initial state ofthe
FSM which generates the experiment is called a state identifica/ion experiment.
The theory of finite state machines offers a number of approaches to sol ve problems of machine
identification and state identification.
•¡observe that we distinguish between the impulse response A =Ao,A 1,A2, ... as usually defined in systems theory and
the impulse response function a=a(O),a(J),a(2), ... as response of a linear system when started in the zero state by
performing a multiple experiment with the unit impulses. For the expression of a in terms of A we have a=O,Ao,A 1,A2, ...
11
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
lt is known that for the general case of finite state machines the computation of a solution in
machine identification or in state identification requires algorithm which have a complexity
depending exponentially on the size ofthe state set. For specific finite state machines, however,
such algorithms can have a feasible complexity. This is also the case for a linear finite state
machines LFSM.
2.3 The linear system realization problem
The realization problem in linear system theory is defined by the problem to determine for a given
impulse response function a=a(O),a(l),a(2), ... with a(t)=(al(t},a2(t), ... ,am(t)) an associated
minimal linear system (F, G,H). In our case the linear system is given by a LFSM with a state space
Q=K" ofminimal dimension n. Each value a(t) is a matrix over K=GF(q) ofsize pxm. In LFSM
theory the realization problem of linear system can be considered as a machi ne identification
problem with a multiple experiment which is given by the set {(el,al},(e2,a2), ... (em,am}}. Let us
now determine the values a(t) of the impulse response function a in terms ofLFSM=(F,G,H).
Since ai=M(O,ei) we get from (2.3) ai(O}=O for i= 1,2, ... ,m and therefore a(O)=O.
lf t>O we have ai(t) = HF 1- 1Gei for i=l ,2, ... ,m. For the matrix A(t) for t>O we get
a(t) = [ HF t-t Gel 1 HF i-t Ge2 I . . . 1 HF i-t Gem]
lf we represent G by its column vectors as G= [gI 1 g2 1 ... 1 gm] we have
a(t) = [HF 1-'g11 HF 1-'g2 l ... I HF 1- 1gm] or also
a(t) = HF t-t G . We see that the impulse response function a of a LFSM =(F, G,H) can be written as
a= (O, HG, HFG, HPG, HPG, .... ) (2.4)
With this result the linear system realization problem can now be defined in algebraic terms as the
problem to determine for an observed impulse response function a (or equivalently for a given
impulse response A ) matrices F,G,H ,where F has minimal size nxn, which ful fil the equation (2.4).
12
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
2.4 State ldentification and solution of the cryptanalytic problem
As pointed out in the introduction, state identification by experiments is an important problem in
cryptanalysis. In the following we will show, how the solution ofthe linear system realization
problem leads also to the so lution ofthe associated state identification problem. Since we are
interested to sol ve the identification problem as part of the cryptanalyis of stream ciphers, we can
assume that m= 1 such that the impulse response function a has values in K" .Let us assume that
LFSM =(F, G,H) is a linear realization of the impulse response function a=(O,a(J),a(2), ... ) . Then
the autonomous linear finite state machine ALFSM =(F,H) generates from state x(O) = Ge, where e
is the unit impulse input function e:No -? K which is given by e(O)= 1 and e(t)=O for t>O the
output sequence S with S(t)=a(t+ 1). This follows directly from the fact that a LFSM is time­invariant.
This result gives us the following procedure for the determination of a ALFSM and the initial state
x(O) which generates as output a given vector-valued output sequen ce S=S(O),S(l),S(2), ..... :
1. define a by a=(O,S(O),S(J),S(2), ... ) (2.5)
2. determine the linear realization LFSM =(F, G,H) of a
3. compute x(O) by x(O)=Ge
4. the ALFSM given by (F,H) generates from x(O) the output function S.
The result (2 .5) of our cryptanalytic problem shows how by the means of linear realization a
solution ofthe stated cryptanalytic problem, to determine an autonomous linear finite state machine
ALFSM and the associated initial state x(O), can be achieved. However, there is still the task to
show, how actually a linear realization (F,G,H) can be constructed and how effective a solution can
be computed. For this, generally speaking, the theory of linear realization as discussed in linear
system theory, is an important part. In university courses, however, the teaching of its algebraic
foundation, as originally developed by the work of Rudolf Kalman, is often neglected. For su ch
reasons, but also for the convenience ofthe reader, we give in the following a short introduction to
the algebraic theory oflinear systems realization. We restrict the presentation, however, to the case
of LFSM realization.
13
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
2.5 Abstrae! approach to dynamical system realiza/ion
Let/ :U~Y denote a function which assigns to ea ch input function u:Z ~K'" with finite support( Z
denotes the set of integers) the output function y: Z ~K" of equal length, /ul=ly/. As an example
the function f can be considered as an 1/0 function of a finite state machine FSM with a fixed initial
state. We assume that f is time-invariant in the following sense: Let u~t and y ~t denote the t­shifted
functions ofu andy which are given by u~t(r): = u(t+r) and y~t(r):=y(t+r). Then ifj(u)
=y we have for ali tEZ f(u~t) = y~t. Furthermore we assume that f is non-anticipatory, that
means that the values f(u)(t) are independent from the values u(t') for t'>t. In the theory offinite
state machines two input functions u and u* are called equivalen! to each other (u-u*) if for ali
vEU we ha ve f(uv) = f(u *v). Here uv and u *v denotes the concatenation of u and u* with v which is
given by uv(t) = u(t) for ali t with O 5 t </u/ and uv(t) = v(t-/ul) for ali t with /u/ 5 t . The relation
- on U is a equivalence relation. The quotient set U/- , the set of equivalence classes [ w] ,
consisting of ali input functions w' E U which are equivalent to wE U, can serve as the state set
Q(j) of a discrete time dynamical system J;(f) =(U, Y,Q(j), q;(j),/J(j)) which realizesf J;(f) can be
defined as follows: Because ofthe time-invariance offwe can assume that a input function w which
generates the initial state [w] has for ali t;:fJ the value O. Then the (global) state transition function
qJ(j) of I(j) can be detined by the function q;(j):No><Q(j)xU ~Q(j) with q;(j)(t, [ w ],u):=[ wuj[O,t}]
where u is a input function u:No~ K" and uj[O,t} denotes the restriction of u to the interval [O,t].
The output functionjJ(j):Q(f)~K" of I(j) is defined by JJ(j)(f w]):=f(w)(O). For u with /ul=J (u is
then basically a input letter u(O) of I(j), we get for qJ(j) the (local) next state transition function
f/j) :Q(j)xK'" ~(j) which is given by f/j)(f w],u(O)):=[ wu(O)].
2.6 linear state macltine realization
ln the case that the 110 functionf U~Y is linear, we are able to construct the state set Q(j) of I(j)
as the quotient space U/ker(j) ofthe linear space U ofinput functions modulo the kernel ker(j) of
the functionf Since U is a linear space, we can represen! any input function wu by wu = wO(u) +
O(w)u, where O(u) and w(O) denotes a zero- input function of length /O(u)/ and /w(O)I, respectively.
The equality [wO(u) + w(O)u] = [wO(u)] + [w(O)u] allows us to represent the next state transition
function flJ) by f/J)(f w ],u(O)) = [ wO] + [ u(O)]. If we denote by F(j), G(j) and H(j) the linear
operators which are given by F(j):Q(j) ~(j) with F(j)(f w ]):=[ wO], by G(j):K"' ~(j) with
14
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
G(/)(a):=[u(O)] and by H(/):Q(/)~K1' with H(/)([w]:=f(w)(O) we have for I(/) the representation as
a linear state machine by I(/) = ( F(/),G(/) ,H(/))
2. 7 Linear finite state machine realization
The next step is to make the necessary assumptions to assure that the state space Q(/) which is
given by Q(/) = Ulker(/) is finite dimensional. This is the case if any state q of Q(/) can be
represented by a linear combination of finite many states q l,q2, ... ,qn which forma basis for Q(/).
Let ul,u2, .. .,un denote a set of input functions which generate this basis; ql = [ul], q2 = [u2], ... ,qn
= [un]. Then any initial state q which is given by q = [u] can be represented by q = xlq I + x2q2 +
... +xnqn = xl[ul] + x2[u2] + ... +xn[un] = [ xlul + x2u2 + ... +xnun]. We see that any u with q =
[u] can be written as u = xlul + x2u2 + ... +xnun where ul,u2, ... ,un is a set ofinput functions
which generate a basis for Q(/)=Ulker(/).
For the determination of input functions ul,u2, ... ,un which have this property we proceed as
follows: Let e/,e2, ... ,em denote again the unit impulse input functions and Jet for k=O, 1,2, ... and
i=l,2, ... ,m .With eik we denote the k-shifted version of ei which is defined by eik(t):=ei(t+k) for
k=0,1, 2, .. . Since the functions eik forma basis for the input function u which generate the states (u]
of Q(/) it is evident that each state-generating input function u can be represented by a linear
combination of the functions eik. Therefor, to investigate ker(/) it is of interest to investigate the
valuesf(eik) restricted as functions defined on No . For k=O we have eik=ei andf(eJ = ai or for
(el,e2, ... em) we have (f(el)j(e2), ... j(em)) = (al,a2, ... ,am) =a where a is the impulse response
function a =( a(O),a(l),a(2), .. .). which was defined in section (2.1 ). For f(eik) we get the k-shifted
values of a which are given by (f(elk}j(e2k), ... j(emk)) =a ~k= ( a(k),a(k+ 1),a(k+ 2), ... ). For our
purpose it is sufficient to <leal with a finite length impulse response function which is given by
a(M)=(a(O),a(l),a(2), ... ,a(M-1)). The matrix h(N) over K which can be contructed by a(M) and is
defined by the block matrix
a(O)a(l)a(2)a(3) .. ..... ... ..... ... ........ a(N -1)
a(J)a(2)a(3)a(4) ..... .......... ........... a(N)
h(N) = (2.6)
a(N -1)a(N)a(N + 1) .... .. ............ a(M -1)
15
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
is called a Hankel matrix of order N. The (finite) Hankel matrix h(N) as given by (2.6) provides the
data for the determination ofthe dimension n ofthe state space Q(j) ofthe realization LFSM which
generates as impulse response from its zero state the output sequence a=(a(O),a(J),a(2), ...
.. ,a(M-1)).For the dimension n of Q(j) we have n = rank h(N). This can be seen as follows: lfwe
restrict the dimension of the input space U to dim U=N then any input function u has length N and
can be represented by a linear combination ofthe set of unit impulse input functions eik, with
i=l,2, ... ,m and k=0,1,2, ... ,N-1 where N= (M+ 1)12. Since for eik the valuesf(eik} are given by the
rows of h(N) the dimension K ofthe kernel space ker(j) is given by N minus the rank of h(N);
K= N - rank h(N). For the state space Q(j) =Ulker(j) we have dim Q(j) = dim U- dim ker(j) or
dim Q(j) = N- K or for rank h(N}=n we get dim Q(j)= N-(N-n) = n.
This result offers al so the computational means for the construction of a basis = = {~1,9, ~J, ... ,§¡}
ofthe state space Q(j)=K" of .E(/} as follows: As basis vectors ~¡ we choose the states ~i=[é'i]
where é'i are chosen from the set of unit impulse functions eik such that the set of rowsf(eik} of h(N)
consists of linear independent elements. In general there are severa! ways to choose the basis .5.
With the results of section 2.6 and the construction of a basis for the state space by means of the
function f and the Hankel matrix h(N) we are able to determine the linear operators F(j), G(j) and
H(f) of I(j) in matrix form. From section (2.6) we have the results
F(j)([w])= [wO] , G(j)(u(O))=[u(O)] ,H(f)([w])=f(w)(O) (2.7)
where wE U, u(O}EK"' ande = (e1,e2, ... ,em). Since we interpret [w] here as the state of I(j) at time O
the input value u(O) appears also at time O such that O(w) has to be considered as the empty word A
of length O, so that G(j)(u(O)) = [ u(O)] . As usual we use the notation I, F, G,H for I(j),F(f), G(j)
and H(j), respectively.
(1) Determination of F:
For the nxn matrix En= [[et] 1 [é1] I ... 1 [87]] constructed by the basis vectors ofthe state space
of Iwe have F[[e1] I [é1] l ... I [87]] = [[elO] I [é10] l .. .I [810]] . With basis =th e matrix En is the
unit matrix and we have the result
F=[[e10] I [t10] I ... I [810]] (2.8)
16
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
(2) Determination of G:
We take as input values to be processed by G the valu_es el(O),e2(0), ... ,em(O) and form the
m><m matrix Em= [ el (O) 1 e2(0) I ... I em(O)] . By (2. 7) we ha ve G[ el (O) 1 e2(0) I ... I em(O)]=
[ [e1] I [e2] l ... I [em]]. Since Em is a unit matrix we have as result
G=[ [el] I [e2] l ... I [em]].
(3) Determination of H:
(2.9)
For H we have from (2 .7) H({w]=f(w)(O). For the states [El],[C2], .. .,[tn] which form the basis of
the state space Q=K"' have H[[El] 1 [t2] I ... 1 [tn]] =[f(&l)(O) IJ(&2)(0) 1 ... IJ(tn)(O)]. Since
[[El] 1 [t2] I . .. 1 [tn]] is the unit matrix we have the result
H=[f(&l)(O) IJ(C2)(0) I ... IJ(tn)(O)]. (2.10)
With the resultas shown in (2.8)-(2.1 O) we are able to determine for a given impulse response
function a=(O,a(l),a(2), ... a(M-1) ( or equivalently for a given impulse response
A =(Ao,A l,A2, ... ,AM-1) ) of length Mofa multi-variable "blackbox" overa finite field K with m
"input ports" and p "output ports" by means of the Hankel-(block)matrix h(N) of size Na linear
finite state machi ne LFSM given by .I=(F, G,H) which generales A as its impulse response. The
realization I. is minimal,which means that the dimension n ofthe state space is minimal and its
states are controllable and observable. •¡
The approach of this chapter follows mainly the book on "System Theory" of Lo u is Padulo and
Michael A. Arbib [ Padulo-Arbib 1974, chapter 8-2]. Related work, with emphasis on general
systems aspects, has been published by the author [Pichler 1974],[Pichler 1976]. The fundamental
theory for this approach of solving the realization problem is dueto the research results in
mathematical systems theory by Rudolf E. Kalman [Kalman 1963],[Kalman-Falb-Arbib 1969].
Computational aspects ha ve been considered by Ho and Kalman [Ho-Kalman 1966] and J. Rissanen
[Rissanen 1971 ],[Rissanen-Kai lath 1972]. In the next chapter we discuss the contributions of J.
Rissanen for the effective computation ofrealizations.
*) the usual approach in systems theory is to make here use of the Hankel matrix H(N) of order N which is constructed
by the values Ao,A1,A2, .... ,AM-1 of the impulse response A. This is possible since by the time invariance ofLFSM we
have always rank h(N) = rank H(N). In the following we will also make use of H(N).
17
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
3. RISSANEN PQ-DECOMPOSITION OF HANKEL MATRICES
Jorma Rissanen introduced in his important papers [Rissanen l 971] and [Rissanen -Kailath 1972]
an effective method to decompose recursively step by step a sequence of Hankel matrices
H(J),H(2),H(3), ... which are generated by a associated sequence of impulse responses
A(J),A(2),A(3,. .. of increasing length M(J),M(2),M(3), ... If ata step k the Hankel matrix H(K) is
reached and the associated realization Ik ={Fk,Gk,Hk) is determined,the method ofRissanen allows
the computation of H(k+ 1) and Ik+I ={Fk+ !}, Gk+l},Hk+ !}} at step k+ 1 by keeping the results of
step k. At each step the Rissanen method provides a decomposition ofthe form H(n,N)=P(n)Q(n,m)
where H(n,N) consists of n linear independent scalar rows ofthe Hankel matrix H(N) and P(n) is a
lower triangular scalar matrix of dimension nxn. lf rank H{N)=rank H(N+ 1) the columns of P(n)
can be taken as basis vectors for the state space Q=K" ofthe associated realization. The matrices
F,G, and H ofthe realization can be effectively derived from P(n) and Q(n,m). The effectiveness of
the method of Rissanen for the computation of realizations is crucial for our further discussion, it is
outside ofthe scope ofthis paper to discuss it in greater detail . The reader is at advised to consult
the existing original publications. For the future a complete algorithmic description and a software
implementation of the Rissanen algorithmus for applications in the field of cryptanalysis is in
preparation.
4 CRYPTANALYTIC MEASURES FOR STREAM CIPHER DATA
Stream ciphers are based on pseudo random generators PRG which generate from a initial state x(O)
(which contains information on the cryptographic key in use) a key sequen ce S=S{OJ,S(I),S(2), .....
ln man y practica! cases of PRG' s the value set of the key sequence Sis given by the finite field
GF(2). However today in modem PRG's for fast secure data transmission also (GF(2)f and more
general K'1=(GF(q)f is of interest. Tn practica! applications only a finite part S(M)=
S{O),S{JJ,S(2), ... ,S(M-1) of length Mis available for cryptanalysis. The finite string S(M) can have
been derived from a successful "known plain text attack" or by a "chosen plain text attack" by
inversion ofthe mixing operation ofthe stream cipher system. Also the direct observation ofthe
key stream ofthe PRG is a possibility. For a derived sequence S there is the cryptanalytic problem
to determine a possible structure ofthe PRG and (or) the determination ofthe used key. By
technological reasons it can be assumed that the PRG ofthe stream cipher system can be modelled
18
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
by a autonomous finite state machine AFSM. By assuming a finite state machine model the
problem of finding the structure of the PRG and ( or) the key in use is seen as the problem of
machi ne identification and ( or) state identification as discussed in section (2.2).
The solution ofboth problems together with the problem ofthe determination ofthe cardinality of
the state set Q ofthe AFSM are seen in cryptanalysis as complexity measures for the key sequence
S. The measure which computes for a given sequence S the cardinality ofthe state set Q is known as
the Chaitin-Kolmogoroff complexity of S. For the general case of autonomous finite state machines
the implementations of such measures are computational difficult and practica! infeasible. However,
for specific classes of AFSM 's effective methods for the implementations ofthe measures might be
derived. One such class is given by the class of autonomous linear finite state machines ALFSM.
For the case of scalar-valued sequences S=s(OJ,s(i),s(2J,s(3), ... with s(iJEGF(2) or s(i)EGF(q) the
Massey- Berlekamp algorithmus provides an effective method to derive from a finite string S(M) of
S a autonomous linear feedback shift register ALFSR of mini mal length n(M) andan associated
initial state x(O) which generates S(M) form state x(O). The function L:No~No which computes for
a given scalar-valued sequence S for any string S(M) of it the minimal length n(M) ofthe realizing
ALFSR has been called in cryptanalysis the linear complexity profile of S. We see that the Massey­Berlekamp
algorithmus solves for the analysis of scalar stream cipher data the machine
identification problem, the state identification problem and also the linear complexity problem.
Our goal is, to solve such problems also for the case ofvector-valued stream cipher data S. The
principal approach which we take has been already outlined in chapter 1 ofthis paper. The technical
details for it are provided by the content of chapter 2 and chapter 3 of this paper. This gives us the
position to describe in the following the computational method, which we will cal! the "Rissanen
algorithmus" by its main steps
Rissanen algorithmus for the computation of cryptanalytic linear measures
Assume that a key sequence S=S(OJ,S(JJ, S(2), ... , where S(i)E GF(q/, has been observed. Then we
are able to perform for each finite string S(M) of length M the following two steps:
Step 1: we consider the string S(M)=S(OJ,S(l),S(2), ... ,S(M-1) as the impulse response A(M) of length
Mofa LFSM. The associated impulse response function a as response of a LFSM from the zero
state is then given by a=O,S(OJ,S(JJ,S(2), ... ,S(M-1). Application of the realization method of chapter 2
19
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
gives by means ofthe Hankel matrix H(N) ofrank n the associated linear finite state machine I by
I =(F,G,H) with state space Q=K' . The computation of I requires that H(N+ 1) has also rank n.
Step 2: by the result (2 .5) of chapter 2 the given string S(M)= S(OJ,S(IJ, S(2J, .. .,S(M-1) ofthe key
sequence S can be seen as the output word ofthe autonomous linear finite state machine
ALFSM =(F,H) with initial state x(O) which is given by x(O)=Ge ,where e is the (scalar) unit
impulse input function given by e(O)= 1 and e(t)=O far t>O.
lncreasing the length M of the key sequen ce S for M= 1,2, 3, 4, ... we reach by step 1 by recursion the
associated Hankel matrices H(l), H(2),H(3), ... and the associated LFSM's I(l), I(2), I (3), ... and
the associated sequence n(l), n(2), n(3), ... indicating the dimension of the associated state spaces
Q(l), Q(2), Q(3), .... ln the possession of the results of step 1 we determine by step 2 the associated
autonomous linear finite state machines (F(l),G(l)), (F(2) ,G(2)), (F(3),G(3)), ... and the associated
initial states x(J)(O), x(2)(0), x(3)(0), .... To have an effective method for the stepwise computation
of the realizations I(l), I(2), I(3), ... the Rissanen method of chapter 3 for establishing a PQ-decomposition
of the associated Hankel matrices has to be applied.
The Rissanen algorithmus, which is described above, allows even for very long observed key
streams S=S(O),S(J),S(2), ... the effective computation of linear cryptanalytic measures, such as
given by the procedures oflinear state machine identification, initial state identification and by
determination ofthe linear complexity profile. Since the key streams are allowed to have values in
the linear space J(P with p:?l the Rissanen algorithmus generalizes the cryptanalytic methods
provided by the Massey- Berlekamp algorithmus.
5 CONCLUDING REMARKS
The paper presents with the Rissanen algorithmus a new method for taking linear measures of
vector-valued data as they appear in stream ciphering. The theoretical basis for this method is
provided by the theory oflinear system realization as developed as part of mathematical systems
theory by Rudolf Kalman. For the practica! application in the context of cryptanalyis the Rissanen
method for recursive identification of linear systems has been provenas essential.
The result ofthis paper generalizes the method oflinearization as developed by Massey and
Berlekamp which was originally developed in the theory of BCH-codes [Massey 1967],
20
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
[Berlekamp 1968]. Jonckheere and Ma investigated the Massey-Berlekamp algorithmus from the
point of view of linear systems realization but did not <leal with the more general case of our paper
[Jonckheere-Ma 1989].0ur presentation made use of the framework of the classical theory of linear
finite state machines. A deeper structural knowledge about realizations could be achieved by
considering the R-module approach in the theory of algebraic linear systems as developed by
Kalman . Another goal could be the investigation of a possible direct effective computation of
realizations such that the structure of I:=(F, G,H) becomes a parallel coupling of linear feedback
shift registers. The matrix F is then required to have rational canonical form. As final remark we
express the hope that this paper has shown that the results of mathematical systems theory, as
developed mainly in the 60' s of the last century, are until toda y of importance for practica!
applications in current topics of engineering.
REFERENCES
[Massey 1967] Massey J.: Shift register synthesis and BCH decoding. IEEE Trans. on
lnformation Theory IT-15, 1967, 122-127.
[Berlekamp 1968] Berlekamp E.R. : Algebraic Coding Theory, McGraw Hill, New York 1968.
[Kalman 1963]
[Kalman 1969]
Kalman, R.E.: Mathematical description oflinear dynamical systems.
SlAM Joumal on Control, ( 1963), 152-192
Kalman, R.E. , P.L. Falb, M.A. Arbib : Topics in Mathematical Systems
Theory, chapter 1 O Algebraic theory of linear systerns,
McGraw Hill, New York 1969.
[Kalrnan-Ho 1966] Ho, B.L. and R.E. Kalman: Effective construction of linear state-variable
rnodels from input/output functions. Regelungstechnik,
Oldenbourg 1966, 545-548.
[Padulo-Arbib 1974] Padulo,L. and M. Arbib: Systern Theory: A Unified Approach to Continuous
and Discrete Systems. Hernisphere Publishing Corporation,
Washington D.C. 1974.
21
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
[Pichler 1974]
[Pichler 1976]
[Rissanen 1971]
Pichler,F. : Realisierung linearer Input-Output Prozesse 1: Diskrete Prozesse.
Technischer Bericht SYS-PED 1, Lehrkanzel für Systemtheorie,
Universitat Linz,Dezember 1974, (35 pages).
Pichler,F. : General Dynamical Systems: Construction and Realization.
In "Mathematical Systems Theory-Udine 1975"
Lecture Notes in Economics and Mathematical Systems,
Springer-Verlag Berlin 1976, 393- 408.
Rissanen J.: Recursive ldentification of Linear Systems
SIAM Joumal on Control, Vol 9,No 3 August 1971 , 420-430.
[Rissanen - Kailath 1972] Rissanen,J, and T. Kailath: Partial Realization ofRandom Systems
Automatica, Vol. 8, Pergamon Press 1972, 389-396.
[Jonckheere-Ma 1989] Jonckheere,E. and Chingwo Ma: A Simple Hankel lnterpretation
ofthe Massey- Berlekamp Algorithm. Linear Algebra and its
Applications, 125, Elsevier Science Publ. Co. 1989, 65-76.
22
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017