轻量级分组密码算法分析与基于诱骗态的实用量子密钥分发协议

摘要

密码学是信息安全的基础,一方面人们希望利用密码算法来保护通信的安全；另一方面为了各种目的,人们又希望在未经当事人授权的情况下获取秘密信息。这两种不同的需求衍生出密码学领域的两个主要研究方向,密码设计学与密码分析学。它们之间互相影响互相促进,带动了整个密码学的发展。密码分析技术的进步,会发现已有算法中存在的漏洞,促使密码设计者提出新的设计方法,避免已经发现的问题,反过来,新的设计方法又促使密码分析者不断改进分析技术。
　　 在本论文中,我们主要研究了轻量级分组算法的安全性分析技术。同时在量子密码理论研究方面,我们使用诱骗态的方法设计安全实用的量子密钥分发(QKD)协议。这两个方面的研究在当代密码学中都受到广泛的关注。
　　 一.轻量级密码算法分析
　　 轻量级分组密码仍然属于分组密码,与普通的分组密码相比,它的执行效率更高,消耗的计算资源更少,适合微型计算设备使用。20世纪90年代物联网概念兴起,无线射频技术和无线传感网络的应用深入到生活的方方面面,随之而来的安全问题成为重要的研究课题。因为物联网上使用的微型计算设备计算能力有限,所以很多轻量级分组密码算法应运而生,为物联网的安全保驾护航。轻量级分组密码算法在追求效率的同时还要保证安全性,对它的安全性评估就显得尤为重要,这是我们进行研究的初衷。
　　 分组密码算法用相同的密钥进行加密和解密运算,属于对称密码算法。本质上,分组密码算法是一种有限的带密钥的置换,将固定长度的明文转换为相同长度的密文。分组密码算法主要有两种设计结构:一种是Feistel网络结构。该结构每次只有一半的分组进入F函数,因此实现时它占用硬件资源较少,适合在计算能力受到限制的环境中使用,代表算法为DES[1]。DES是早期的分组加密标准,基于Feistel网络结构设计。20多年来它经历了各种攻击,对之后的密码算法产生了深远的影响。另一种是代替.置换网络(SPIN)结构,该结构的最大优点是能够从理论上给出最低差分特征概率和最佳线性逼近优势的界,即该结构对差分分析[2]和线性分析[3]是可证明安全的,代表算法AES[4]。AES基于SPN结构,分组长度为128比特,密钥长度可为128/192/256比特,是目前最流行的对称加密算法。
　　 现在的轻量级分组密码算法大都受到DES和AES设计原理的影响。例如A.Bogdanov等人在CHES2007上提出的轻量级分组算法PRESENT[5]。该算法共31轮,轮函数为代替-置换网络(SPN)结构。它的分组长度为64比特,密钥规模分为80比特和128比特两种,分别称为PRESENT-80和PRESENT-128。它借鉴了AES最终候选算法Serpent[7]的设计思路,与其它轻量级的分组算法相比,它的硬件执行效率更高,是轻量级分组算法中的佼佼者,受到人们的关注。轻量级分组密码算法MIBS[6]是M.Izadi等人在CANS2009上首次提出。该算法针对RFID标签设计,因此它的硬件资源使用很少,适合在计算资源受到限制的环境下使用。MIBS算法使用了Feistel的算法结构,共有32轮迭代运算,其分组长度为64比特,密钥长度为64比特和80比特。
　　 鉴于轻量级分组算法的使用环境计算资源较少,这一类型的算法力求寻找安全性与执行效率的最佳平衡点。然而当算法的执行效率提高时,算法的安全性就必然受到影响。在导师展涛教授和王小云教授的悉心指导下,我们对轻量级分组密码算法PRESENT和MIBS的安全性进行评估。
　　 主要研究成果如下:
　　 ·分组密码算法PRESENT的侧信道立方攻击
　　 我们利用侧信道攻击(Side Channel attack)和立方攻击(Cube At-tack)相结合的思想[8]对PRESENT进行了分析。分析过程中,只需要一个比特位置的信息,就可以恢复PRESENT全部密钥。首先利用立方测试技术[9](Cube Test)对最初若干轮的PRESENT进行了测试,发现了PRESENT算法的非随机性质。并在此基础上利用侧信道攻击获得一个比特位置的信息,可以恢复出PRESENT-80的全部密钥。根据我们的分析只要得到第3轮的中间变量的任一比特的信息就可以恢复密钥。特别是得到比特位置1,2,3的信息,恢复80比特的密钥只需要215次选择明文,232次PRESENT全算法加密即可。
　　 对于密码算法,任意输出比特可以看成明文和密钥的多元表达式。而在通常情况下,这些多元表达式非常复杂我们无法从中获得密钥信息。对于低次的多元表达式,立方攻击可以从中提取密钥的相关方程,从而恢复密钥。对于PRESENT算法,我们利用其自身性质,来寻找立方攻击所需的极大项和极大项等式,从而建立线性方程组恢复密钥。而非利用原始立方攻击中提出的随机游走的方法来寻找随机多项式的极大项[10]。以下是对分析有利的两个性质。
　　 -分组算法PRESENT的64比特明文变量和80比特密钥变量在第3轮之后首次混合在中间变量的一个比特的多项式中。
　　 -PRESENT的前3轮迭代运算中,其中间变量多项式的明文比特经过S盒变换不会出现抵消现象。
　　 根据上述性质,使用约减多项式对迭代函数寻找极大项和极大项等式。换言之,迭代函数的输出变量可以看做是输入变量和本轮子密钥的多元多项式,立方攻击主要关注的项是只含有一个密钥变量,其它均为明文变量的项。这样我们每轮只保留含有一个密钥变量的项和全是明文变量的项,从而控制了迭代过程中多项式的规模,同时得到仍然具有生成多项式的部分性质的约减多项式,进而完成我们的攻击。
　　 ·约减轮MIBS的差分分析
　　 M.Izadi在提出MIBS算法时,也对其安全性进行了简单的评估。评估中声称64比特的MIBS即能提供足够的安全性,且执行效率高。M.Izadi认为MIBS算法4轮差分特征的最高成功概率为2-15。通过对其S盒的输入输出差分分布的分析,我们发现实际上MIBS4轮差分特征的概率为2-12。
　　 我们找到了4个12轮的差分特征,并利用其中的3个差分特征恢复约减轮MIBS的密钥。对于我们的攻击,通过261.6对选择明文,恢复全部64比特的密钥,只需要建立216字节的计数器表,时间复杂度为225次加密运算,成功的概率是0.99。
　　 二.基于诱骗态的实用量子密钥分发协议
　　 密码设计始终是密码学家关注的焦点,新兴量子密钥分发协议为密码设计提供了新的途径,而它在理论上可证明是无条件安全的,更使得它成为密码设计的研究热点。量子密钥分发方案基于量子物理的基本原理,测不准原理。即使窃听者拥有量子计算机,量子密钥分发系统仍然可以产生安全的通信密钥。在产生密钥的过程中毋需量子计算机,甚至毋需量子存储器,唯一需要的仅是量子态制备,传送与测量。然而量子密钥分发系统的实验条件还无法达到理论要求,从而影响了量子密钥分发方案的实际安全性。我们的目的就是在现有技术条件下,提供实用化的理论,建立安全实用的量子密钥分发方案。
　　 1984年C.Bennett和G.Brassard提出了影响深远的BB84[11]量子密钥分发方案。通信双方Alice和Bob利用不同量子态代表经典2进制码(bit)。Alice通过量子通信信道发射不同制备基下的量子态,Bob随机选择测量基进行测量。在公共经典信道中公开制备基和测量基,Bob丢弃使用错误测量基得到的测量结果。然后在剩余测量记录中,随机抽取一部分与Alice对照,检验误码率。若误码率太大,则放弃这次通信。对剩余数据(raw key)通过纠错(error correction),隐私放大(privacy amplification),提炼出最终密钥(final key)。
　　 量子密钥分发协议严格的安全性证明最早由D.Mayers[12]于1996年给出,但是其证明非常复杂。1999年,P.Shor与J.Preskill[13]从纠缠态提纯出发给出了简化的证明。虽然已经证明BB84方案是无条件安全的,但是这并不意味着任何以该方案为基础的实验都是安全的。因为所进行的实验未必真正满足BB84安全性证明中所要求的前提条件,特别是单光子光源,现有实验只有非理想光源。Hwang[14]提出的诱骗态的方法(Decoy-state Method)。王向斌提出了实用的诱骗态方法,可以在没有单光子源的情况下,得到最终密钥。
　　 我的合作导师王向斌教授提出了考虑在现实的量子密钥分发过程中光源误差和统计涨落的安全性的影响。在他的悉心指导下,我们得到了存在光源误差和统计涨落的诱骗态方案和计算最终成码率的关键公式。这是国际上唯一的考虑光源误差和统计涨落的安全量子密钥分发理论。
　　 以下为我们的主要研究成果。
　　 ·存在光源误差和统计涨落的诱骗态量子密钥分发方案
　　 量子密钥分发已经在理论上和实验上受到广泛的关注和深入的研究。尽管理论上,量子密钥分发方案是无条件安全的,但是因为实际实验条件无法达到,削弱了它在实际应用中的安全性。特别是量子密钥分发协议要求的理想单光子源,在实际中都是使用非理想光源在损耗信道中进行密钥分发。因此协议会受到光子数分离攻击[15,16]。
　　 幸运的是ILM-GLLP[17,18]证明如果我们知道原始接收比特中多光子计数的上界(或者说单光子计数的下界),那么我们仍然可以从中提取出安全的最终密钥。但是如何计算单光子计数的下界是困难的,王向斌提出的实用的诱骗态方法[19]可以计算单光子计数的紧的下界。然后利用以下公式就可以计算最终成码率。

目录

文摘

英文文摘

插图索引

表格索引

第一章 引言和主要结果

1.1 密码设计简介

1.2 密码分析简介

1.3 量子密钥分发协议

1.4 主要结果和内容结构

第二章 分组密码的分析方法

2.1 搜索攻击

2.2 差分分析

2.3 不可能差分分析

2.4 线性分析

2.5 侧信道攻击

2.6 立方攻击

2.6.1 定义和相关性质

2.6.2 攻击过程

第三章 分组算法PRESENT的侧信道立方攻击

3.1 分组算法PRESENT

3.1.1 PRESENT算法简介

3.1.2 密钥生成算法

3.1.3 设计准则

3.1.4 研究进展

3.2 PRESENT的立方攻击

3.2.1 PRESENT的非随机性质

3.2.2 PRESENT的侧信道立方攻击

3.2.3 结论

第四章 约减轮的MIBS算法的差分分析

4.1 分组加密算法MIBS

4.1.1 MIBS算法描述

4.1.2 密钥生成算法

4.1.3 设计准则

4.2 MIBS的差分特征

4.2.1 搜索差分路线

4.2.2 13轮MIBS的差分分析

4.2.3 复杂度和成功率分析

4.3 结论

第五章 存在光源误差和统计涨落的诱骗态量子密钥分发方案

5.1 背景知识

5.2 我们的方法

5.2.1 虚拟协议

5.2.2 一些定义

5.2.3 重要的性质

5.3 主要结果

5.3.1 渐近结果

5.3.2 非渐近结果

5.4 光源误差

5.5 结论

5.6 附录

第六章 结论和研究计划

参考文献

致谢

个人简历

学位论文评阅及答辩情况表