一种快速求解密码S盒差分均匀度下界的新方法

摘要：

密码S盒是对称密码算法的核心部件,其代数性质通常决定着密码算法整体的安全强度.密码S盒的差分均匀度是度量其抵御差分密码分析的能力.对于n比特输入及n比特输出的密码S盒,传统求解其差分均匀度的方法需要大约O(23n)次运算;而当n较大时(比如n＞15),因搜索空间较大,从而导致花销时间太长(甚至计算不可行)等问题.如何快速判定(大状态)密码S盒的差分均匀度是目前的研究难点之一.本文基于密码S盒的循环差分特性,提出了 一种求解其差分均匀度下界的新方法:通过统计循环差分对出现的次数,快速评估其解存在的个数,并由此给出密码S盒差分均匀度的下界.该方法所需的时间复杂度仅为O(2")次运算.实验结果证实:对于4比特、5比特、7比特、8比特、9比特及多个16比特的S盒,利用该求解算法捕获的差分均匀度下界与真实的差分均匀度值是完全一致的.特别地,针对PRESENT、Keccak、MISTY-7、AES、MISTY-9、NBC及其变体使用的密码S盒,该方法求解其差分均匀度下界时所花销的时间均比传统算法节省82％以上.该方法为进一步评估大状态密码S盒的代数性质提供全新的思路.

关键词：对称密码、差分攻击、密码S盒、差分均匀度、时间复杂度

所属期刊栏目：44

分类号：TP309(计算技术、计算机技术)

资助基金：国家自然科学基金;广西自然科学基金项目;教育部重点实验室基金

在线出版日期：2023-05-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：1081-1086