基于周期函数多阶段构造的量子密钥恢复方法、系统、介质及设备

本发明属于加密，尤其涉及基于周期函数多阶段构造的量子密钥恢复方法、系统、介质及设备。

背景技术：

1、本部分的陈述仅仅是提供了与本发明相关的背景技术信息，不必然构成在先技术。

2、量子计算对密码安全性的影响并不限于grover算法对穷举搜索的二次加速，simon算法能够在多项式时间内求解隐藏异或周期问题，kuwakado和morii（均为研究者的英文姓氏）利用这一性质对feistel和even-mansour结构提出了量子区分方法，后续研究又把周期函数用于fx结构、消息认证结构以及多种feistel变形的量子分析，这些结果说明，对称密码的量子安全性还取决于密码内部是否能够形成可由simon算法识别的周期函数。

3、周期函数不仅可以用于区分，还可以用于恢复密钥。实际密码常把公开函数与轮密钥异或组合成fk或kf轮函数。以为例，其隐藏周期就是密钥，x为输入变量。如果从多轮密码的明密文计算中构造出类似的密钥相关周期函数，恢复周期便可得到轮密钥、子密钥关系或可继续处理的密钥表达式。与仅说明目标结构不同于随机置换的周期区分器相比，密钥恢复还要求周期中确实保留密钥信息，并要求所构造函数能够通过实际的加密或解密接口计算。

4、现有周期函数构造大多依赖人工逐轮推导，现有研究建立了周期函数与截断差分之间的联系，提出了符号化自动搜索方法，但这些方法主要面向密钥无关的周期区分器，没有表示轮密钥及其在中间状态中的组合关系。crypto 2022中有学者提出了密钥相关周期函数自动化工具，通过枚举候选电路并测试周期，得到了五轮misty l-fk和五轮feistel-fk的多项式时间量子密钥恢复结果，该方法在小规模结构上有效，但候选电路数量随轮数、分支数和结构复杂度迅速增加，难以直接扩展到misty的其它密钥加入方式、广义feistel结构和skipjack类结构。

5、在复杂结构中，仅在某个内部状态发现周期形式还不够，该内部状态所需的未知量可能来自明文变量与轮密钥的混合运算，无法由攻击者控制；周期状态还可能位于密文接口之前，不能从实际密文中计算。即使某个表达式满足，也需要判断周期是否含有可恢复的密钥信息，以及直接simon或嵌套simon过程是否能够把该周期转换为具体子密钥。其中，g表示从目标密码的中间状态或输出分支构造并消去可直接计算公开项后得到的周期函数，x表示攻击者可控制的输入变量，s表示与x无关的非零密钥相关周期。

技术实现思路

1、为了解决上述背景技术中存在的技术问题，本发明提供基于周期函数多阶段构造的量子密钥恢复方法、系统、介质及设备，将多轮密码中的构造过程分为多个相互连接的阶段，并将密钥相关周期函数的代数条件、输入端实现条件和输出端可观测条件放入同一个模型，求解器只有在内部核心、轮密钥来源和密文等价函数同时成立时才返回结果，避免找到不能从真实输入产生或不能从密文计算的内部周期，从而自动构造可用于量子密钥恢复的周期函数。

2、为了实现上述目的，本发明采用如下技术方案：

3、本发明的第一个方面提供基于周期函数多阶段构造的量子密钥恢复方法，其包括：

4、对于目标密码，将周期函数构造分为多阶段，设置各阶段轮数，将各段轮展开为多操作组成的计算图，并为不同阶段设置结构状态、密钥辅助变量和可观测状态，加入边界条件，形成完整约束模型；

5、对于完整约束模型，通过求解器进行求解，从求解结果中还原内部周期核心、公开输入、密文后处理、周期表达式以及各节点的状态传播路线；

6、将还原结果代入目标密码的真实轮函数，验证输入端不含需要预先知道的未知密钥，输出函数能够由密文和公开函数计算，并验证周期函数的周期性后，进行量子密钥恢复。

7、进一步地，将周期函数构造分为三个阶段：内部周期核心搜索阶段、输入侧扩展阶段和输出侧扩展阶段；

8、在内部周期核心搜索阶段，选定轮内部结构，允许使用辅助未知量，搜索满足全形式或半形式的中间函数；

9、在输入侧扩展阶段，从内部周期核心搜索阶段的输入位置向密码输入接口回溯或反向扩展轮，检查每个辅助未知量是否能够由输入变量、公开函数和实际轮密钥唯一确定；

10、在输出侧扩展阶段，从密码输出接口向内部周期核心搜索阶段的周期输出位置反向搜索轮，判断能否由密文分支、公开函数和异或运算构造与内部周期函数等价的量；

11、其中，参数r1、r2和r3均为正整数，分别表示内部周期核心搜索阶段、输入侧扩展阶段和输出侧扩展阶段所覆盖的轮数，其取值由目标结构和搜索范围给定或枚举。

12、其中，三个阶段的约束条件在同一约束系统中同时求解，使内部周期核心、轮密钥来源和密文可观测性在同一候选中同时成立。

13、进一步地，所述输出侧扩展阶段使用两位可观测状态表示输出可构造性：

14、第一状态(1,1)表示分支能够直接从密文得到；

15、第二状态(0,1)表示分支与已知值相差一个与输入变量x无关的密钥常量，其中x表示攻击者可控制的输入变量，该分支能够用于构造等价周期函数；

16、第三状态(0,0)表示分支不能用于构造输出函数。

17、进一步地，所述多操作包括：

18、f操作，表示不含密钥的公开函数或其逆函数；

19、xor操作，表示两个同位宽分支之间的按位异或；

20、split操作，表示将一个状态复制到两个后继分支；

21、adk操作，表示当前分支与指定轮子密钥进行异或。

22、进一步地，所述split操作直接复制结构状态和密钥辅助变量；

23、所述xor操作对两个结构状态按位异或，并同步异或对应的密钥辅助变量；

24、所述adk操作按照xor规则将轮密钥符号加入结构状态并更新密钥辅助变量；

25、所述f操作按照预设的状态转换图进行结构状态传播。

26、进一步地，所述结构状态根据全形式和半形式定义，且用七位向量编码。

27、进一步地，所述边界条件包括：全形式、半形式、密钥传播、输入可构造性、输出可观测性和阶段边界条件。

28、本发明的第二个方面提供基于周期函数多阶段构造的量子密钥恢复系统，其包括：

29、模型生成模块，其被配置为：对于目标密码，将周期函数构造分为多阶段，设置各阶段轮数，将各段轮展开为多操作组成的计算图，并为不同阶段设置结构状态、密钥辅助变量和可观测状态，加入边界条件，形成完整约束模型；

30、求解模块，其被配置为：对于完整约束模型，通过求解器进行求解，从求解结果中还原内部周期核心、公开输入、密文后处理、周期表达式以及各节点的状态传播路线；

31、恢复模块，其被配置为：将还原结果代入目标密码的真实轮函数，验证输入端不含需要预先知道的未知密钥，输出函数能够由密文和公开函数计算，并验证周期函数的周期性后，进行量子密钥恢复。

32、本发明的第三个方面提供一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如上述所述的基于周期函数多阶段构造的量子密钥恢复方法中的步骤。

33、本发明的第四个方面提供一种计算机设备，包括计算机可读存储介质、处理器及存储在计算机可读存储介质上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现如上述所述的基于周期函数多阶段构造的量子密钥恢复方法中的步骤。

34、与现有技术相比，本发明的有益效果是：

35、本发明将多轮密码中的构造过程分为多个相互连接的阶段，并将密钥相关周期函数的代数条件、输入端实现条件和输出端可观测条件放入同一个模型，求解器只有在内部核心、轮密钥来源和密文等价函数同时成立时才返回结果，避免找到不能从真实输入产生或不能从密文计算的内部周期，从而自动构造可用于量子密钥恢复的周期函数。

36、本发明采用七位结构状态和独立的密钥辅助变量表示中间状态，结构状态用于快速判断全形式和半形式是否仍可形成，密钥辅助变量用于区分不同轮密钥组合和真实抵消，与直接枚举完整候选电路相比，可以在传播过程中剪除不满足周期形式的分支，减少复杂结构中的搜索量。