STREAM CIPHER CONNECTION POLYNOMIAL AND CRYPTANALYSIS

Abstract

In stream cipher design, linear feedback shift registers (LFSR) are very important role. LFSR output is dependent on connection polynomial that is used in LFSR design. We need to provide random key-stream so that for attacker it is hard to predict the key that we used for encryption. Shift registers are pillars to generate a long random sequence, this randomness increases if we used primitive polynomial as connection polynomial because it has maximum period. We are providing two primitive polynomial generation algorithms factorization and matrix based algorithm. Performance analysis of both factorization and matrix based algorithm for primitive polynomial generation that produce all degree-d primitive polynomials 'i' (2'-1)/d is existing, where 'v is the Euler's totient function. Factorization as well as matrix based algorithm both obtained each and every new degree-d primitive polynomial in polynomial time complexity 0 (k.d4.In r) and 0 (d4) time respectively with k number of distinct prime factors of maximum period 2d • 0 (d2) extra storage required for both algorithms. Comparative analysis of both algorithm with exhaustive algorithm is presented in terms of execution time and complexity. This report presents fast methods to find primitive polynomial using some properties related to irreducibility, square free polynomials and primitiveness. Massey algorithm used for recovering connection polynomial of LFSR is also present in report with an example.