2009 | OriginalPaper | Buchkapitel
Linear Complexity Measures for Multi-valued Cryptographic Data Streams by Application of the Rissanen Partial Realization Method
verfasst von : Franz Pichler
Erschienen in: Computer Aided Systems Theory - EUROCAST 2009
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Jorma Rissanen developed in his papers [1],[2] a method to compute recursively for a matrix-valued data stream S of finite length the associated minimal linear system
$\it \Sigma$
=(F,G,H) which has S as its impulse response. The method of Rissanen is based on the fundamental algebraic theory of linear systems realization as developed earlier by the fundamental research in mathematical systems theory by the work of Rudolf Kalman [3],[4],[5]. In our presentation we show how the Rissanen method of Hankel matrix decomposition can be applied to measure the linear complexity profile of vector-valued cryptographic data streams as it is applied in stream cipher testing. Our method generalizes the well known Massey-Berlekamp algorithm which is applied in testing scalar-valued data streams. For this reason we call it the “Rissanen algorithm”. Although the author has been familiar already for a long time with the realization theory of Kalman and contributed to the topic earlier [6], only recently the reported applicability in cryptographic testing of pseudorandom sequences has been found. The result presented here proves that results of mathematical systems theory and automata theory, which were developed nearly half a century ago by Rudolf Kalman, Jorma Rissanen, Michael Arbib and others are until today of scientific interest and can successfully be applied to solve engineering problem of todays interest. Jochinger [7] gives a report on the software implementation of the Rissanen Method of recursive Hankel matrix decomposition and the effective computation of partial linear systems, following [1] and [2]. A more detailed presentation of the topic discussed here, which includes also the discussion of the theory of linear systems realization, has been given earlier by Pichler [8].