MARS-like Feistel 结构的量子攻击

钱 新, 尤启迪, 周 旋, 张 洋, 赵晓晶

1. 北京卫星信息工程研究所 信息科学工程技术中心, 北京 100086

2. 清华大学 计算机科学与技术系, 北京 100084

1 引言

Feistel 结构[1]自1973 年由Feistel 等人提出之后便成为了分组密码设计的主流整体结构. Feistel 结构具备相似的加解密操作, 轮函数的选择也较为灵活多变, 很多广泛应用的分组密码, 如DES、Camellia、FEAL、RC5 等都采用了Feistel 结构.

广义Feistel 结构(generized Feistel structure, GFS) 是对Feistel 结构的一般形式的推广, 可以随着分支数的增加以更小规模的轮函数实现更大的分组, 从而在设计轻量级分组密码时具备比Feistel 结构更大的优势, 更适用于资源受限的通信环境中. 在1989 年美密会上, Zheng 等人[2]总结了三类广义Feistel结构, 分别为Type-1 型、Type-2 型和Type-3 型广义Feistel. 随后Schneier 等人[3]将Feistel 结构推广到了非平衡Feistel 结构, 此后出现了各种各样的广义Feistel 结构以及相应代表性的分组密码, 包括CAST 256-like Feistel 结构(Type-1)[4], CLEFIA-like Feistel 结构(Type-2)[5], SMS4-like Feistel 结构[6], MARS-like Feistel 结构[7]. MARS-like Feistel 结构是在AES 候选密码MARS 分组密码的基础上定义的一种广义Feistel 结构. Moriai 等人[7]在2000 年给出了MARS-like 广义Feistel 结构的随机性证明, 并提出5 轮4 分支MARS-like Feistel 结构具有伪随机性, 8 轮4 分支MARS-like 结构具有超伪随机性; 当分支数为d时,d+1 轮MARS-like 结构具有伪随机性, 2d轮MARS-like 结构具有超伪随机性. 对于MARS-like 结构的密码性质研究主要集中在不可能差分分析. 目前最好的结果是, 当分支数(子块数)d为偶数时, 可以构造长为3d −1 轮的不可能差分特征, 而当d为奇数时, 可以构造任意长轮数的不可能差分特征.

随着量子理论的发展迅速, 量子信息科学的发展为密码学的发展也带来了一定挑战. 后量子密码成为了密码学……