A Constructive Method of Algebraic Attack with Less Keystream Bits

Xiaoyan ZHANG, Qichun WANG, Bin WANG, Haibin KAN

Summary :

In algebraic attack on stream ciphers based on LFSRs, the secret key is found by solving an overdefined system of multivariate equations. There are many known algorithms from different point of view to solve the problem, such as linearization, relinearization, XL and Grobner Basis. The simplest method, linearization, treats each monomial of different degrees as a new variable, and consists of variables (the degree of the system of equations is denoted by d). Thus it needs at least equations, i.e. keystream bits to recover the secret key by Gaussian reduction or other. In this paper we firstly propose a concept, called equivalence of LFSRs. On the basis of it, we present a constructive method that can solve an overdefined system of multivariate equations with less keystream bits by extending the primitive polynomial.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E94-A No.10 pp.2059-2062
• Publication Date: 2011/10/01
• Online ISSN: 1745-1337
• DOI: 10.1587/transfun.E94.A.2059
• Type of Manuscript: LETTER
• Category: Cryptography and Information Security

Authors

Xiaoyan ZHANG
Qichun WANG
Bin WANG
Haibin KAN

Keyword

algebraic attack,  primitive polynomial,  linearization,  multivariate equations