基于Simon量子算法的密钥认证分析研究

陈 璇

(天津天狮学院，天津 300000)

0 引言

随着近几年移动互联信息技术的飞速发展，数据安全逐渐成为人们广泛关注的问题，如何保障信息安全问题已成为行业关注的焦点[1-2].在威胁信息安全的诸多因素中，量子计算引中的Shor算法[3]，可以实现在多项式时间内寻找有限群里一个元素的阶，被重点应用于大整数分解和离散对数计算领域，Simon量子算法和Grover量子算法也均对现有密码算法的安全构成了挑战.Simon算法能够以O(n)次查询实现特殊函数周期的获取，并在一定程度上启发了Shor算法的发现[4].

在物联网数据安全方面，许多方式都会干扰加密，造成加密过程出现错误，泄露状态信息，而利用这些状态信息获取密钥的攻击方式被称为“故障分析”.因此针对“故障分析”的密钥认证就成为了安全通信的重要环节.密钥认证可在通信节点之间建立共享会话密钥，实现安全通信.已有学者在此方面做出了相关研究，其中，王彩芬等[5]提出了一种改进的三因素相互认证与密钥协商方案，采用增强存储在智能卡中的相关参数的安全性，使用混沌映射计算迪菲一赫尔曼问题，修复了内部特权攻击的安全漏洞，保护了公共信道上敏感医疗记录信息数据.该方法能够抵抗各类安全攻击，且效率较高，但该方法存在的局限之一就是在使用混沌映射时，计算方式较冗长，易导致数据冗余造成认证准确率较低的现象；王伟松等[6]提出一个新的多因子认证协议来修复身份认证协议易遭受用户冒充攻击的安全漏洞.使用扩展混沌映射，采用动态身份保护用户匿名性，并利用三次握手技术实现了异步认证.该方法可以抵抗冒充攻击，拒绝服务攻击，能够保护用户匿名性和身份唯一性.在实际网络环境中，攻击手段是多样的，但该方法仅针对于一种攻击手段进行了研究，存在一定局限性.

在此基础上，本文提出一种基于Simon量子算法的密钥认证分析研究，在对Simon量子算法的运算方式及密钥设计进行原理进行分析的基础上，结合Hadamard变换，运用Simon量子算法对密钥周期进行计算，实现提升密钥认证分析过程中询问程序安全性的目的，实验结果表明所提方法在准确认证概率、认证耗时和抗攻击性方面均有良好表现，具有一定的研究价值.

1 Simon量子算法

近年来，随着量子计算的不断进步，量子技术被广泛应用到密码算法的安全性分析中，运用量子技术对密码算法进行分析更是成为了一个热门的研究方向[7].Simon算法有多种不同的加密方案，不同的分组长度、密钥长度、值长度以及轮数，使其可以适应不同的应用环境.现有常见的加密方案如表1所示，其中，定义该算法的分组长度为2a比特，密钥长度为ab比特.

表1 Simon量子算法分组方式

Simon量子算法的第x轮迭代结构如图1所示.

图1 Simon量子算法迭代流程图

从图1中可知，其中Zx和Yx分别表示对应的左右分支，kx则表示第x轮的密钥，那么Zx+1和Yx+1分别表示x+1对应的左右分支，Sx表示循环移位.那么由此推断，可以将轮函数表示为：

f(Zx)=(Zx<<<1)&(Zx<<<8)⊕(Zx<<<2)

(1)

其中，<<<表示循环位移，&表示比特与运算，⊕表示比特异或运算，根据公式(1)，第x轮到加密函数可以表示为：

(2)

密钥设计：在对明文进行加密计算时，密钥的组成是由每一轮的子密钥组成的，这里我们假设主密钥为{K0，K1，…，Kx-1}，那么每一轮的密钥就可以表示为{k0，k1，…，kx-1}，根据上文对Simon量子算法分组方式的分析可得，不同密钥长度ab，对应的密钥设计方法也不同，

当x=0，1，…，a-1时，kx=Kx；

当x=a，a+1，…，x-1时，根据a值的不同，可以分为以下几种情况：

(3)

其中，λ=2a-4，pi表示固定的常数序列.以此为基础，对不同轮数密钥按照轮密钥和主密钥进行分级认证.

2 基于Simon量子算法的密钥认证分析

2.1 密钥周期求解

在得到Simon量子算法对密钥的设计组成及基本原则的基础上，利用Simon最密钥周期进行求解实际上是指在假定周期T{0，1}内，对于密钥函数求解任意x∈{0，1}a，使其都存在f(x)=f(x+T)，在此条件下，求解周期T.

Simon量子算法对密钥周期的计算主要可以总结为以下5个步骤：

首先将2a个量子布特量子态初始化，并利用Hadamard变换，将其应用至第一个密钥寄存器中：

(4)

对第二个密钥寄存器进行量子Oracle访问：

(5)

完成对第二个密钥寄存器测量后，第一个密钥寄存器即出现坍塌，坍塌结果为：

(6)

对坍塌后的第一个密钥寄存器进行Hadmard变换，变化后可得：

(7)

能够实现YT=1时，Y的幅度为0，那么就可以得出，此时可以满足YT=0.

当重复上述过程，最终基本可以得到(a-1)个不相关但均与T相交的向量，此时就可以通过对线性方程进行求解，得出T的值.这样的计算方式与传统方法相比，可以在计算复杂度上实现大幅降低，为密钥认证分析过程节省时间.

另外一个需要注意的问题是，在对密钥进行认证分析过程中，往往很难得到完全满足Simon量子算法的解[8-9]，也就是说，Simon量子算法求解需要满足基本的二对一的条件，即同一个函数对应两个原像，而两个原像满足其中间存在固定周期T，而在引用Simon量子算法进行密钥认证分析时，会出现存在其他干扰t的现象，这时会有f(x)=f(x⨁t)，其中t≠T且t≠0，这种情况下称t为布尔函数的碰撞[10].因此t存在的概率也对Simon量子算法能否计算出密钥的周期有很大影响.

在此基础上，实现了对密钥周期的计算，这在降低密钥认证计算时间的同时，也将降低其在密钥认证询问阶段的对话时间.

2.2 密钥认证分析

上文对基于Simon量子算法密钥周期计算方法进行了阐述，对于密钥认证分析主要是针对攻击进行准确识别，在认证阶段对输入密钥的正确性进行判断.在上述基础上，本节以6轮密钥为例，对6轮Feistel结构密钥认证分析方法进行研究.

在对6轮密钥进行认证时，假设Zn，Yn分别为每一轮的输入，f为轮函数，kn为轮密钥，任取3个非零常数c0，c1，d0∈{0，1}0.5a，将(c0，d0)和(c1，d0)分别作为输入值.

对密钥进行认证的过程包括两个阶段，即初始化阶段和密钥认证.在初始化阶段首先将第三方的输入值(c0，d0)和(c1，d0)生成对应的映射e：c0×c1→cT.之后，将随机选择Zn，Yn∈c1和s∈Zn，Yn.将s作为主密钥.并令s1{0，1}→c0、s2{0，1}→{0，1}、s3{0，1}→c0、s4{0，1}→{0，1}、s5{0，1}→c0、s6{0，1}→{0，1}.

当一个输入密钥申请认证的用户U，ID∈{0，1}加入时，安全信道将接受参与者发送给的密钥信息.

在接收到密钥信息后，进入到密钥认证阶段，在该阶会形成一个会话密钥，并将量子布特量子态初化，用户参与者首先进入询问阶段.在这个阶段，要完成对密钥认证申请者U随机询问，按照如下方式进行问答.

ID信息询问.收到该询问后，认证机制首先在已有的密钥列表中进行查找，如果用户输入的密钥及ID信息在列表里，则返回认证结束阶段，认为密钥符合认证要求，否则，系统返回会话密钥阶段，并将用户输入的密钥信息进行储存.

Execute询问.收到Execute询问后，认证机制按照其自有协议规则生成相应的结果，并将结果返回至密钥认证申请用户U，并保存至第一个密钥寄存器.

Send询问.在收到Send后，认证机制按照协议规则生成相应的结果，并返回给密钥认证申请用户U，并保存至第二个密钥寄存器，并计算YnT=1时，T不为0的值.

Corrupt询问.收到Corrupt(U)后，返回参与者U的私钥，并保存至Hadmard变换后的第一个密钥寄存器.

Reveal询问.收到Reveal后，查找Execute询问或Send询问所对应的语句，并返回由其生成的对应于该语句的密钥设置信息，完成对6轮kn的认证分析.

挑战请求(Challenge request)阶段：假设密钥认证申请用户U匿名性发起认证挑战，认证机制将做如下回应.

挑战询问阶段：在这个阶段，密钥认证申请用户U随机进行询问，系统根据一般询问阶段的应答方式逐一进行回应.假设密钥认证申请用户U从未对认证系统进行Corrupt询问，且密钥认证申请用户U输出的密钥猜测值sa.如果s=sa，则表明密钥认证申请用户U的猜测是正确的.而如果密钥认证申请用户U可以猜出sa，则认证系统即可解决DBDH(Decisional Bilinear Diffie-Hellman)问题，而这在实际上是无法实现的，因此密钥认证的安全性得以保障.

至此，密钥认证结束.

3 实验测试

3.1 实验条件

为了验证基于Simon量子算法的密钥认证的有效性，采用MATLAB软件搭建了一个密钥认证仿真测试环境.实验所用系统CPU Inter Core i7-9700 K，6.0 GHz，内存为16 GB，采用文献[5]和文献[6]中所提方法作为对比.实验数据Simon 64/128轮数为44，主密钥设置为ABCDEF010203040506070809ABCDEF.密钥管理一般分为卫星密钥管理、临近空间密钥管理以及地面网络密钥管理，如图2所示.

图2 密钥管理

在图2密钥管理环境中，选取地面网络密钥管理中心的100组密钥进行认证，其中故障个数分别设置为20，40，60，80，100个.通过不同故障的密钥分别进行20次测试，实验结果取平均值，分别记录三种方法准确认证密钥的次数以及耗费时间.

3.2 实验结果与分析

3.2.1 认证准确性测试

图3为三种方法对密钥进行认证的情况.密钥认证的准确率是信息的发送方和接收方，用一个密钥去加密和解密数据的准确程度，其通过公式(8)计算可得：

图3 不同方法密钥认证准确情况

(8)

其中，M为密钥认证的准确率，a为故障数量，m为密钥总数.密钥认证的准确率越高，证明该方法的密钥认证效果越好.

从图3中可以看出，三种方法密钥认证的准确率均随着故障数量的增加而逐渐降低，但对比文献[5]和文献[6]方法，本文方法下降趋势较为平缓，且始终保持在90%以上的识别准确率，这主要是因为本文方法采用Simon算法对密钥寄存器进行转换，提高了对每一轮密钥的认证效果.

3.2.2 认证耗时测试

图4为不同方法准确认证密钥所需要消耗的时间.认证密钥所需要的消耗时间N与单个密钥时间认证时长与密钥总数m有关.其计算公式为：

图4 不同方法密钥认证耗时情况

N=mt

(9)

其中，t为单个密钥时间认证时长.

从图4中可知，随着故障数量的增加，三种方法的计算耗时均呈现出逐渐上升的趋势，在故障数量为40个以内时，时间的增量相对较为平缓，但当故障数量增加至40个以上后，文献[5]和文献[6]方法的耗时均出现剧烈上升，而本文所提方法的上升趋势虽然较比自身也有上升趋势，但对比另外两种方法仍有较大优势，且全程耗时始终稳定在10 s以内.这主要是因为对密钥周期的计算降低对申请认证的密钥信息的核查时间，减少了大量冗余计算，且应用Simon量子算法后的询问程序实现了对无效密钥的快速认证.

3.2.3 认证安全性测试

为了对所提方法的安全性进行测试，对密钥认证进行不同攻击，此次实验选用在密钥认证过程中常见的立方攻击、线性分析攻击、不可能差分分析攻击、差分分析攻击4种攻击方式，分别攻击6、12、14、16轮，在此条件下分析密钥认证情况，具体结果如表2所示.其中立方攻击是基于高阶差分理论的新型代数攻击方法，该方法适用于输出比特能够表示成关于明文变置和密钥变量的低次多元方程；线性分析攻击是常用密码分析手段之一，属于已知明文攻击方法，它通过寻找明文和密文之间的一个“有效”的线性逼近表达式，将分组密码与随机置换区分开，并在此基础上进行密钥恢复攻击；不可能差分分析攻击是指利用两个明文的差对应的输出差不可能是某些值的特点求解密钥的攻击方法.差分分析攻击是指通过比较分析有特定区别的明文在通过加密后的变化传播情况来攻击密码算法的.

表2 面对不同攻击时所提方法的安全性

从表2中可以看出，当分别采用不同时间和空间复杂度的立方攻击、线性分析攻击、不可能差分分析攻击、差分分析攻击对密钥认证的不同轮数进行干扰时，所提方法准确实现密钥认证的概率始终保持在80%以上，这表明在面临攻击时，所提方法具有较高的安全性，可以在一定程度上实现信息的安全性.

4 结论

提出基于Simon量子算法的密钥认证分析研究，通过对Simon量子算法对密钥的设计以及分类情况，结合多轮密钥对应的不同子密钥在寄存器上的转换，完成对密钥周期的计算，在此基础上，将其计算结果引入对待认证密钥的询问程序中，一方面提高密钥认证的安全性，另一方面也可以实现减少密钥认证计算时间的目的.实验结果表明，文中方法的密钥准确认证概率保持在90%以上，整体运算耗时保持在10 s以内，在不同类型的攻击手段下仍能保持80%以上的密钥认证准确率，具有较好的安全保障性能.由于条件限制，研究尚有不足，可在之后的研究中进一步探索：

1)密钥认证实验部分仅以Simon 64/128版本的密钥为例进行实验，存在较大局限性，可以从更多密码种类进行测试，发现其可以存在的问题；

2)对于Simon量子算法的应用是从对密钥进行认证的角度进行利用的，在之后的研究中，可从对密钥进行攻击的角度，反向对密钥认证分析方法进行研究.