A discrete logarithm-based approach to compute low-weight multiples of binary polynomials

详细信息    查看全文

• 作者：Pietro Peterlongo ; Massimiliano Sala ; ^{maxsalacodes@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Claudia Tinnirello ; ^{claudia.tinnirello@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：12Y05 ; 11T71 ; 11T55 ; 12E05 ; 68Q25
• 刊名：Finite Fields and Their Applications
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：38
• 期：Complete
• 页码：57-71
• 全文大小：373 K

文摘

Being able to compute efficiently a low-weight multiple of a given binary polynomial is often a key ingredient of correlation attacks to LFSR-based stream ciphers. The best known general purpose algorithm is based on the generalized birthday problem. We describe an alternative approach which is based on discrete logarithms and can take advantage of the structure of the polynomial. In some cases it has much lower memory complexity requirements with a comparable time complexity.