若干广义非平衡Feistel结构的量子分析研究

摘要

分组密码结构对密码算法的安全性有着非常重要的作用.随着量子计算的发展,以Simon算法、Grover算法等为代表的量子搜索算法,广泛应用于分组密码安全性研究领域,并产生了一定的威胁.本文首次研究了对5种广义非平衡Feistel结构的量子攻击,对n-cell结构构造了n+1轮量子区分器;对New Structure Ⅰ/Ⅲ/Ⅳ结构分别构造了6轮/9轮/5轮量子区分器;对FBC-like结构构造了3轮量子区分器,并利用Simon算法对这5种分组密码结构进行了量子区分攻击.进一步,将Simon算法和Grover算法相结合对n-cell结构、New Structure Ⅰ/Ⅲ/Ⅳ结构和FBC-like结构进行了量子密钥恢复攻击,并分析了攻击的时间复杂度.攻击r>n+1轮n-cell结构的时间复杂度为O(2^((r-n-1)k/2));攻击r>6/14/9轮New Structure Ⅰ/Ⅲ/Ⅳ结构的时间复杂度分别为O(2^((r-6)k/2))/O(2^([2k+(r-14)k]/2))/O(2^([2k+(r-9)k]/2));攻击r>5轮FBC-like结构的时间复杂度为O(2^([3k+(r-5)·2k]/2)).结果表明这些攻击的效果均优于使用Grover算法进行穷举攻击.