A Constructive Method of Algebraic Attack with Less Keystream Bits

この論文にアクセスする

この論文をさがす

著者

    • ZHANG Xiaoyan
    • The Shanghai Key Lab of Intelligent Information Processing, School of Computer Science, Fudan University
    • WANG Qichun
    • The Shanghai Key Lab of Intelligent Information Processing, School of Computer Science, Fudan University
    • WANG Bin
    • The Shanghai Key Lab of Intelligent Information Processing, School of Computer Science, Fudan University
    • KAN Haibin
    • The Shanghai Key Lab of Intelligent Information Processing, School of Computer Science, Fudan University

抄録

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 Gröbner Basis. The simplest method, linearization, treats each monomial of different degrees as a new variable, and consists of $\\sum_{i=1}^{d}{n \\choose i}$ variables (the degree of the system of equations is denoted by <i>d</i>). Thus it needs at least $\\sum_{i=1}^{d}{n \\choose i}$ 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.

収録刊行物

  • IEICE transactions on fundamentals of electronics, communications and computer sciences

    IEICE transactions on fundamentals of electronics, communications and computer sciences 94(10), 2059-2062, 2011-10-01

    一般社団法人 電子情報通信学会

参考文献:  23件中 1-23件 を表示

各種コード

  • NII論文ID(NAID)
    10030191376
  • NII書誌ID(NCID)
    AA10826239
  • 本文言語コード
    ENG
  • 資料種別
    SHO
  • ISSN
    09168508
  • データ提供元
    CJP書誌  J-STAGE 
ページトップへ