SIMON类算法轮函数的差分性质分析

摘要

SIMON类算法是美国国家安全局于2013年提出的一类轻量级分组密码算法,该类算法是典型的Feistel结构.其轮函数F(x)采用按位与运算、循环移位运算和异或运算.在密码分析中,分析算法抵抗差分分析的能力对密码算法的安全性评估来说十分必要,然而对SIMON类算法轮函数的差分性质的系统研究还相对较少.本文通过分析轮函数F(x)的差分性质,彻底解决了轮函数的差分分布规律,证明了对于任意给定的输入差分,其差分转移概率只能为0和2-r(1＜r＜n),通过对输出差分的比特进行分类,解决了非零差分转移概率对应输出差分的取值形式、具体取值及计数问题.并在此基础上给出了时间复杂度为O(2n n3),存储复杂度为O(2n)的差分分布表的快速计算算法,同时还给出了固定输入差分条件下,差分转移概率为0时输出差分应满足的充要条件,为SIMON类算法的差分分析提供了理论指导和借鉴.