三类广义Feistel结构的中间相遇攻击

作     者：邓元豪 

作者单位：战略支援部队信息工程大学 

学位级别：硕士

导师姓名：金晨辉

授予年度：2018年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：分组密码 密码分析 中间相遇攻击 Type-1 Type-2 Type-3 Feistel 

摘      要：Feistel结构由IBM公司的Horst Feistel和Don Coppersmith在1973年设计Lucifer算法时提出,因其具有轮函数选择灵活和加解密相似性等优点,而得到广泛应用。在Feistel结构的基础上,又发展出多种Feistel结构的衍生结构,如三类广义Feistel结构(Type-1型、Type-2型和Type-3型)、收缩Feistel结构和扩张Feistel结构等,这些Feistel结构的衍生结构为密码设计者提供了许多新的思路,同时也引起了研究者的广泛兴趣。Guo等人对Feistel结构、嵌套SP结构的Feistel结构、收缩Feistel结构和扩张Feistel结构进行了研究并给出了通用密钥恢复方案。但是,对于三类广义Feistel结构,目前只有区分攻击的研究,尚未有学者给出对三类广义Feistel结构的密钥恢复攻击。本文利用中间相遇攻击的方法,在选择明文攻击条件下,首次给出了Type-1型、Type-2型和Type-3型广义Feistel结构的通用密钥恢复方案。主要的研究内容及创新点如下:1.给出了对分组规模为n的d分支Type-1型广义结构的5d-3轮的中间相遇攻击。我们通过利用该结构的特殊性及截断差分特征,给出了该结构的3d-1轮中间相遇区分器。接着通过在区分器头部添加d轮,在区分器尾部添加d-2轮,我们以2(7)d-1(8)n d)的时间复杂度、2(7)d-1(8)n d)的存储复杂度和的2选择明文量给出了Type-1型广义Feistel结构的5d-3轮密钥恢复攻击。该攻击结果是现有已知的对Type-1型广义Feistel结构最好的密钥恢复攻击。2.给出了对分组规模为n的d分支Type-2型广义结构d(10)3轮的中间相遇攻击。我们通过利用该结构的特殊性及截断差分特征,给出了该结构的d(10)2轮中间相遇区分器。接着通过在区分器头部添加1轮,我们以2(7)d-1(8)n d)的时间复杂度、2(7)d-1(8)n d)的存储复杂度和的2选择明文量给出了Type-2型广义Feistel结构的d(10)3轮密钥恢复攻击。该攻击结果是现有已知的对Type-2型广义Feistel结构最好的密钥恢复攻击。3.给出了对分组规模为n的d分支Type-3型广义Feistel结构的d(10)2轮密钥恢复攻击。我们通过利用一个特殊的截断差分特征,构造了一个d(10)1轮区分器。接着通过在区分器头部添加1轮,我们给出了Type-3型广义Feistel结构的d(10)2轮密钥恢复攻击,恢复了第一圈全部d-1个轮函数的子密钥。攻击的数据复杂度为2个选择明文,存储复杂度为2d个分组,每个分组n比特,时间复杂度为2次加密。该攻击结果是已知的对Type-3型广义Feistel结构最好的密钥恢复攻击结果。