Journal of Cryptologic Research
 
引用检索 快速检索 DOI 高级检索
在线期刊
   » 最新录用
   » 网络预发表
   » 当期目录
   » 过刊浏览
   » 按栏目浏览
   » 综述文章
   » 摘要点击排行
   » 全文下载排行
  作者在线投稿
   » 作者投稿/查稿
   » 投稿须知
   » 模版下载
   » 版权协议
  专家在线审稿
   » 审稿登录
   » 审稿政策
   » 自荐为审稿人
密码学报  
  密码学报--2017, 4 (3)   Published: 2017-06-30
选择 | 合并摘要
专栏序言

“密码函数”专栏序言 Hot!

张卫国
密码学报. 2017, 4 (3): 0-0.
全文: HTML (1 KB)  PDF (108 KB)  ( 289 )
摘要 ( 225 )

密码函数专栏序言

布尔函数是对称密码中的本质性存在”, 它是对称密码的灵魂”.

世界上的许多现象都可表现出两种状态, 比如海潮的起与落, 电路的开与关, 搏击的攻与防等等. 我国传统道家哲学把这种相依且相反的二元现象辩证地抽象为”, 认为宇宙间任何事物都有阴阳两个方面, 由阴阳互补互动而体现出宇宙秩序. 遗憾的是, 这种阴阳哲学没有数学化地发展成科学, 而是局限地模糊在玄学层面. 在西方近代以来, 发展出处理二元问题的布尔符号逻辑(布尔函数), 成为一门数学, 并在工程中得到广泛应用.

布尔函数能在工程中被成功应用, 不得不提到两个人: 一个是乔治·布尔(George Boole, 1815-1864), 另一个是克劳德·艾尔伍德·香农(Claude Elwood Shannon, 1916-2001). 布尔分别在1847年和1854年发表论著《The Mathematical Analysis of Logic》和《An Investigation into the Laws of Thought, 创建了布尔代数. 布尔代数奠定了用逻辑思维的方式, 而不是形象思维的方式, 处理二元逻辑问题的数学基础. 1938, 香农在他的硕士论文《A Symbolic Analysis of Relay and Switching Circuits》中, 科学严谨地论述了如何使用布尔代数对开关电路进行设计和分析, 为布尔函数在数字电路系统(包括密码系统)中的实际应用奠定了基础.

香农另一了不起的工作是在1949年发表了论文《Communication Theory of Secrecy Systems, 从信息论的角度为对称密码(包括流密码和分组密码)的设计和分析指明了方向. 在这一先驱性的论文中, 香农提出了扩散”(diffusion)混淆”(confusion)两个设计原则, 至今仍是指导我们设计对称密码和Hash函数的主要原则. 这篇论文具有里程碑意义, 迈出了有史以来对称密码科学化进程中最重要的一步.

1976年分组密码和公钥密码出现之前, 流密码是占统治地位的加解密方式. 早在一百年前(1917), 布尔逻辑结构就在Vernam流密码中出现. 布尔函数在流密码中真正被理性地作为研究对象始于它在线性反馈移位寄存器(LFSR)中的应用. 1960年代末, Berlekamp-Massey算法的提出, 使人们意识到提高密钥流序列线性复杂度的重要性. 1970年代开始, 人们开始考虑在多个LFSR之间引入乘法运算, 用非线性组合模式来提高生成序列的线性复杂度; 后来又出现基于LFSR滤波模式的序列生成器. 决定基于LFSR的流密码安全强度的核心部件是系统中的非线性组合布尔逻辑和非线性滤波布尔逻辑结构, 它们就是狭义上的流密码中的密码函数.

1980年代中期, 出现了针对基于LFSR的流密码的相关分析, 这对密码函数设计提出新的要求, 要求用于流密码中的密码函数具有相关免疫性质. 在同一时期, 我国学者肖国镇(1934-2016)把频谱技术用于密码函数的分析, 提出相关免疫函数的频谱化定理(Xiao-Massey定理), 通过频谱简洁地刻画了相关免疫函数的特征. 这一定理对密码函数的设计和分析具有重要的指导意义.

利用频谱技术还可以研究密码函数的另一重要指标(性质): 非线性度. 密码函数的非线性度被定义为密码函数和所有仿射函数汉明距离的最小值. 非线性度这一指标的提出, 受到了香农1949年论文中相似系统”(Similar Systems)思想的启发. 我们如何度量一个东西有多呢?那就是看这个东西有多大程度上不像我们认为的的东西. 在布尔函数之间, 这种不像是用汉明距离来度量的. 对特定密码指标的研究本质上是对特定条件下01分布的研究, 当在特定条件下的01严重失衡时, 就成为被利用的密码学缺陷. 非线性度是度量对称密码抵抗线性逼近攻击能力的指标, 在流密码和分组密码中都很重要.

不同密码学指标之间往往存在着制约关系, 比如非线性度和相关免疫性就是相互冲突的两个密码指标, 平衡的相关免疫函数(弹性函数)的非线性度的紧上界至今仍是悬而未决的难题(10000个科学难题·信息科学卷, 科学出版社, 2011). 如何实现多种密码学指标的优化折中, 是密码函数设计中的核心难题.

密码分析技术直接地促进和引导了密码函数设计理论的发展. 对流密码和分组密码的分析(攻击)本质上都是利用了密码中布尔逻辑(函数)结构或性质上的缺陷. 比如, 用布尔函数的高阶差分来降低代数次数以实现对流密码的立方攻击; 分组密码攻击所用的区分器与布尔函数的基本性质密切相关等. 值得一提的是, 我国学者曾肯成(1927-2004)等人早在1987-1990年间, 就在美密会等国际会议上发表了一系列有关密码分析的重要论文; 近十年来, 我国学者在流密码和分组密码分析方面取得一些进展, 这些论文对分析和设计对称密码具有重要参考价值. 限于篇幅, 这里不一一列举. 此外, 在密码算法的工程实现及防护上, 密码部件硬件快速实现需要的对合性质, 以及硬件防护的布尔掩码、域分解等技术均依赖布尔函数的各种性质来达成.

1990年代是研究密码函数的重要十年, 我国学者在这一研究方向上取得了一系列重要进展. 比较有代表性的成果是丁存生和肖国镇提出的流密码的稳定性理论”(The Stability Theory of Stream Ciphers, Springer, 1991)和冯登国的博士学位论文《频谱理论及其在通信保密技术中的应用》. 2000年之后的几年里, 密码函数的研究陷入低潮, 直到代数攻击(包括快速代数攻击)的出现. 和相关攻击一样, 代数攻击也是利用了基于LFSR的流密码本身固有的缺陷. 这种缺陷可以通过精心设计密码函数得到弥补, 为了抵抗代数攻击, 密码学家又提出新的密码指标——代数免疫(包括快速代数免疫). 代数攻击出现后, 密码函数又作为热门课题被研究了十年. 研究的问题从最初的如何设计具有最优代数免疫阶的布尔函数, 到后来如何同时兼顾非线性度、平衡性、弹性、代数次数等密码指标. 我国学者特别是青年学者在这一研究方向上有很多值得一提的成果, 读者可参考本期综述论文《布尔函数的(快速)代数免疫性质研究进展》.

基于LFSR的流密码是被研究的较为充分的密码, 如何利用非线性密码函数掩盖系统中线性部分(LFSR部分)是保证这类密码安全性的主要任务. 近十年中出现的流密码, 都在避免出现纯线性的部分, 在系统中融入各种非线性元素, 但其生成序列的伪随机性(安全性)比较难以从理论的角度解释清楚. 无论流密码采用什么样的形式结构, 其中非线性部件中的运算仍然还是布尔逻辑运算.

相对于公钥密码学而言, 流密码学的科学化发展还有很长的路要走. 无论如何发展, 布尔函数都将扮演重要角色.

布尔函数的密码价值还表现在它在分组密码中的存在”. S盒作为分组密码的非线性模块, 可以看做是一个多输出布尔函数, 是密码函数研究的重要对象. 为了抵抗针对分组密码的线性攻击和差分攻击, 需要S盒具有高非线性度和低差分均匀度. 如何构造同时具有高非线性度和低差分均匀度的均衡(包括置换)S, 是研究用于分组密码中的密码函数(S)主要考虑的问题. 当然, S盒还要具有简洁的结构, 以便于实现. 这一研究方向上最具挑战性的公开难题是APN问题”: 在n为不小于8的偶数时, 是否存在GF(2^n)上的APN置换?

布尔函数在Hash函数、秘密共享、量子密码等领域也有应用. 作为布尔函数最具前景的一个研究方向, 是对用于非线性反馈移位寄存器(NFSR)的反馈函数的研究. 这些场合的布尔函数都可以看做是广义的密码函数.

在本期密码学报密码函数专栏, 我们刊登4篇论文, 希望对从事这一研究方向的同行有参考价值.

1篇论文题目是布尔函数的(快速)代数免疫性质研究进展”. 布尔函数的代数免疫性质和快速代数免疫性质分别衡量了基于LFSR的流密码抵抗代数攻击和快速代数攻击的能力. 这一课题已研究了十多年, 仍有很多问题没有弄清楚. 该论文较全面地总结了近十余年来国内外学者在构造具有优良代数免疫性质(包括快速代数免疫性质)且兼顾其他密码学性质相关方面的主要研究进展.

2篇论文题目是旋转对称布尔函数研究综述”. 旋转对称布尔函数具有规则简洁的结构, 使之便于采用代数工具进行研究, 也便于硬件实现. 更值得一提的是, 旋转对称布尔函数可以具有优良的密码学性质. 例如, 早在1983PattersonWiedemann就发现了覆盖半径是16276[215,16] RM, 实际上就是找到了非线性度是1627615元旋转对称布尔函数. 旋转对称布尔函数除了可以具有高非线性度, 还可以是弹性函数, 可以具有优良的代数免疫性质. 本文对旋转对称布尔函数, 特别是旋转对称bent函数和旋转对称半bent函数的研究现状, 进行了较全面的总结; 对高非线性度旋转对称布尔函数的搜索、旋转对称布尔函数代数结构和密码学性质之间的关系等研究问题也有较好的介绍.

3篇论文题目是有限域上置换多项式的几种构造”. 置换是密码函数的一种重要性质, 具有简单代数形式的置换多项式在分组密码中具有应用价值. 本文构造了有限域的偶次扩域上几类置换二项式, 并由此得到新的完全置换单项式, 丰富了已有结果. 此外, 给出了两类与迹函数有关的多项式置换, 推广了已知的相关构造.

4篇论文题目是具有高维输出的半bent弹性S盒的构造”. bent函数是一种非线性度几乎最优的密码函数, 可以同时具有弹性和高非线性度. 但对多输出半bent弹性S盒而言, 输出维数很难提高. 前人曾构造出半bent弹性S, 但输出维数都不超过输入维数的1/4. 本文给出的这种方案, 在输入维数比较大时, 输出维数可大于输入维数的1/4. 随着输入维数的增大, 这一比例有继续变大的趋势.

值得一提的是, 在这4篇论文末尾都列出了值得进一步研究的问题供读者思考.

 

专栏编委: 张卫国

学术论文

基于分组的理性秘密共享方案 Hot!

李梦慧, 田有亮
密码学报. 2017, 4 (3): 209-217. ;  doi: 10.13868/j.cnki.jcr.000175
全文: HTML (1 KB)  PDF (420 KB)  ( 288 )
摘要 ( 224 )

理性秘密共享是博弈论与秘密共享相结合的新兴研究方向, 它拓展了博弈理论和传统秘密共享的应用领域, 已成为密码学的研究热点. 但是多数研究者在构造出理性秘密共享方案的同时忽略了方案的效率问题. 理性秘密共享方案的通信轮数是影响方案效率的主要因素. 现有的多数方案为了实现均衡等需求都采用未知轮数, 即不让理性参与者知道当前重构轮是测试轮还是真秘密所在的轮, 此方法造成通信复杂度较高, 导致方案效率低下, 这在一定的程度上会增加额外的通信开销. 针对上述问题, 基于不完全信息动态博弈模型, 研究门限理性秘密共享方案的完美贝叶斯均衡问题. 利用椭圆曲线上双线性对的随机函数设计一个知识承诺方案, 该方案为可验证的, 以此来检验分发者和参与者的欺骗问题. 结合``均匀分组''思想使理性参与者以组为单位进行通信,可降低方案的通信复杂度, 进而构造出两轮理性秘密共享方案. 分析证明本方案具有可验证性, 能够实现秘密重构博弈的完美贝叶斯均衡. 并从轮复杂度、通信类型和前提假设三个方面与现有的典型方案进行对比, 表明本方案不仅满足安全性需求且执行效率更高.

针对LBlock算法BBC编码方式的功耗分析与防护 Hot!

关明扬, 于国瑞, 向贻锡, 谈兆年, 张国双, 王安
密码学报. 2017, 4 (3): 218-228. ;  doi: 10.13868/j.cnki.jcr.000176
全文: HTML (1 KB)  PDF (3499 KB)  ( 126 )
摘要 ( 169 )

本随着无线射频识别芯片和无线传感网络等微型计算设备的快速发展, 轻量级分组密码得到广泛应用, 其安全性也越来越受到重视. 功耗分析攻击是一种常见的侧信道分析技术, 给密码芯片产品带来巨大的威胁. 本文选取我国自主知识产权的LBlock密码算法作为研究对象, 以智能IC卡作为实验平台, 探讨了LBlock密码算法的平衡比特编码方式(BBC)的安全性, 发现其在对抗功耗分析攻击方面仍存在缺陷. 首先, 通过分析BBC编码方式下的LBlock密码算法, 找到有效的攻击位置, 然后通过采集该位置的能量迹依据汉明重量模型构造模板, 运用模板攻击逐步将密钥恢复出来. 通过实验验证了本文提出的模板攻击方法的有效性. 此外, 本文提出了一种关于LBlock密码算法的针对侧信道攻击的掩码级防护方法, 并通过实验证明了此方法确实能有效抵抗一阶功耗分析攻击, 然后通过程序大小、内存占用和加密时间这三个指标来对未加掩码和加掩码两种方式进行对比, 结果是各项指标均在合理范围之内.

一种基于LWE问题的布尔电路同态加密方案 Hot!

姬晨, 蔡斌, 向宏, 丁津泰, 桑军
密码学报. 2017, 4 (3): 229-240. ;  doi: 10.13868/j.cnki.jcr.000177
全文: HTML (1 KB)  PDF (824 KB)  ( 224 )
摘要 ( 174 )

传统密码学能保护数据在存储和传输中的安全性, 但密文信息持有者不能直接对密文数据进行计算. 2009年第一个全同态加密方案的诞生, 使得对密文的直接计算成为可能. 本文在GSW全同态加密方案的基础上, 重新设计密钥生成、加密、解密、同态操作等函数, 提出了一种基于布尔电路的改进同态加密方案. 改进方案的同态加法和同态乘法对应矩阵加法和矩阵乘法, 不会造成密文维度扩张. 通过设计转换密钥生成函数、维度归约函数和模数转换函数, 本文给出了针对该方案的维度模数规约方法和相应的正确性分析. 同时, 本文还对提出的同态加密方案的正确性和安全性进行了理论分析. 分析表明, 改进方案的安全性依赖于LWE问题, 具有抵抗选择明文攻击的能力. 与GSW方案相比, 改进方案辅以Peikert 等人提出的快速bootstrapping方法, 可以更加自然地转变为全同态加密方案. 此外, 本文给出了改进方案的参数选择规则, 开发软件实现了该方案和与、或、与非等同态计算电路门, 给出了主要参数和计算时间, 为全同态加密技术的进一步应用做出了铺垫.

字符串模式匹配的安全多方计算 Hot!

亢佳, 李顺东, 杨晓艺
密码学报. 2017, 4 (3): 241-252. ;  doi: 10.13868/j.cnki.jcr.000178
全文: HTML (1 KB)  PDF (1018 KB)  ( 180 )
摘要 ( 147 )

安全多方计算是近年来国际密码学界研究的热点问题之一, 是信息社会隐私保护的核心技术. 很多研究者已经对其进行了深入研究, 并提出了各种各样的具有实际应用背景的安全多方计算问题以及它们的解决方案. 本文研究字符串模式匹配的安全多方计算问题. 保密地判断字符串模式匹配问题是安全多方计算的一个重要组成部分, 在信息检索、信息过滤、入侵检测、病毒检测、计算生物学等方面有重要的意义, 同时在拍卖, 招标等其他商业领域也有广泛的应用前景. 为了保密地判断两个字符串是否模式匹配, 本文首先借助Goldwasser-Micali 异或同态加密算法设计了判断两个字符串是否相等的协议; 然后基于BMH算法提出了高效的字符串模式匹配协议; 最后将字符串模式匹配问题转化成集合成员判定问题, 设计了保密性更好, 计算复杂性和通信复杂性更低的新协议. 利用模拟范例对以上协议做出了安全性分析, 并证明了协议是正确的. 同时给出了以上协议计算复杂性和通信复杂性的理论分析, 通过真实数据集实验验证了以上协议的高效性.

基于理想格的在线/离线签名方案 Hot!

向新银
密码学报. 2017, 4 (3): 253-261. ;  doi: 10.13868/j.cnki.jcr.000179
全文: HTML (1 KB)  PDF (365 KB)  ( 209 )
摘要 ( 124 )

由于传统的公钥密码学的构造需要较为复杂的计算量, 这大多超出了资源受限和轻量级设备(如无线传感网, 移动自组网等)的计算能力. 随着移动互联网的快速发展, 大量的轻量级设备被广泛的使用, 并执行一些复杂的任务, 这需要有更高安全性和低通信开销的轻量级密码付之于应用, 使得设备达到可接受的安全标准. 在线/离线签名方案可以很好的实现以上目标, 即在使用消息之前, 首先离线阶段预先做大量的复杂计算;然后在线阶段只进行少量的计算, 提高了签名的速度. 这种密码体制非常适合计算能力受到较大限制的轻量级设备. 然而, 一旦量子时代的到来, 基于传统的数论问题的密码学方案将面临较大安全性威胁, 其方案也将不再安全. 本文结合Ducas等人方案和变色龙哈希函数, 提出了一个基于理想格的在线/离线签名方案. 新方案主要依赖于环和代数格的交换性能, 并没有增加私钥长度和签名长度, 且提高了签名的速度. 分析表明, 该方案在R-SIS假设下具有选择消息攻击的存在不可伪造性.

专栏综述

布尔函数的(快速) 代数免疫性质研究进展 Hot!

唐灯
密码学报. 2017, 4 (3): 262-272. ;  doi: 10.13868/j.cnki.jcr.000180
全文: HTML (1 KB)  PDF (371 KB)  ( 205 )
摘要 ( 148 )

布尔函数是流密码算法中伪随机密钥流序列生成器的核心部件之一. 为了抵抗已知的密码攻击手段, 基于线性反馈移位寄存器的流密码算法中所使用的非线性布尔函数必须兼具可证明的能够抵抗已知密码攻击的性能. 在2003年之前, 为了避免密码系统遭受基于统计分析的概率攻击, 布尔函数应满足平衡性; 为了抵抗最佳仿射逼近和快速相关攻击, 布尔函数应具有高的非线性度; 为了抵抗Berlekamp-Massey算法攻击和Rønjom-Helleseth 攻击, 布尔函数应具高的代数次数; 为了减少布尔函数的输出比特与输入变量分量之间的统计相关性, 为密码系统提供扩散特性, 布尔函数应具有良好的自相关性质; 为了抵抗分别征服攻击和相关攻击, 应用于组合模式中的布尔函数还应当满足高阶弹性. 2003年, Courtois和Meier在欧洲密码学年会上将代数攻击应用于基于线性反馈移位寄存器的流密码算法, 同年, Courtois在国际密码学年会上提出快速代数攻击方法. 为了抵抗代数和快速代数攻击, 布尔函数应分别具有高的代数免疫度和良好的快速代数免疫度. 本文总结了近十余年来国内外学者在构造最优代数免疫布尔函数相关方面的主要研究进展.

旋转对称布尔函数研究综述 Hot!

高光普
密码学报. 2017, 4 (3): 273-290. ;  doi: 10.13868/j.cnki.jcr.000181
全文: HTML (1 KB)  PDF (375 KB)  ( 208 )
摘要 ( 115 )

布尔函数是许多密码系统的核心部件, 其密码学性质的优劣决定着整个密码系统的安全性.因此研究和构造满足各种密码学性质的布尔函数是密码学研究领域的热点问题.旋转对称(Rotation Symmetric)函数也称幂等函数, 是一类输出值在输入的循环移位下保持不变的布尔函数, 具有结构简单、运算速度快、资源利用率高等优点, 目前已被应用于分组密码S 盒和压缩函数的设计中.本文综述了旋转对称函数的研究成果, 具体包括: 密码学性质优良的旋转对称布尔函数的搜索、旋转对称bent和semi-bent函数的构造、有限域上幂等函数的性质、代数免疫最优的旋转对称布尔函数的构造、线性结构特征、汉明重量和非线性度计算以及仿射等价性.其中重点归纳了近年来利用线性子空间构造旋转对称bent 和semi-bent函数的构造方法, 介绍了计算低次旋转对称布尔函数汉明重量以及非线性度的递归方法, 提出了若干值得研究的公开问题.

专栏论文

有限域上置换多项式的几种构造 Hot!

查正邦, 胡磊
密码学报. 2017, 4 (3): 291-298. ;  doi: 10.13868/j.cnki.jcr.000182
全文: HTML (1 KB)  PDF (369 KB)  ( 222 )
摘要 ( 133 )

置换多项式在代数学、组合学、数论、编码理论、密码学等领域中均有广泛而又重要的应用. 近年来, 置换多项式的研究取得一系列进展, 研究者先后提出Akbary-Ghioca-Wang法则、分段构造法、交换构造法等方法来构造和证明置换. 有限域上的置换多项式因其简单的代数形式和优良的密码性质, 在密码算法设计中备受关注. 在特征为2的偶次扩域上寻求同时具有低差分均匀度、高非线性度、高代数次数等密码性质的代数形式简单的置换成为学者们研究的热点. 本文介绍了置换多项式的相关应用和研究背景, 给出了一些基本概念和预备知识. 研究了有限域$F_{p^n}$ 上形如$x^{(p^n-1)/d+1}+ax$的二项式的置换属性, 给出了该二项式是置换的充要条件. 在此基础上, 构造出四类二项式置换, 并利用Dickson 多项式和线性多项式理论予以证明. 列举了上述二项式置换在特征为2和3的有限域上的相关实例, 并由此得到一些完全置换单项式. 根据迹函数的性质, 通过引入新的参数构造出两类具有特定指数的多项式置换, 上述多项式置换推广了一个已知的结果.

具有高维输出的半bent 弹性S 盒的构造 Hot!

杨婷婷, 李路阳
密码学报. 2017, 4 (3): 299-306. ;  doi: 10.13868/j.cnki.jcr.000183
全文: HTML (1 KB)  PDF (456 KB)  ( 141 )
摘要 ( 97 )

在流密码的设计与分析中, 如何构造具有高非线性度的弹性S盒是一个重要的研究课题.  通常情况下, 一个性质良好的S盒需要满足以下指标: 高非线性度、弹性、高代数次数等.  但是这些指标又在不同程度上存在着相互制约关系.  寻找对这些指标进行折中优化的方法, 是构造高非线性度弹性S盒亟需解决的关键问题.  特别是非线性度和弹性, 作为衡量用于流密码中S盒安全性最重要的两个指标, 对其研究具有重大的意义.  本文提出了一种具有高维输出的半bent弹性S盒的构造方法. 设输入维数为$n$, 当$n=2k+1$为奇数时,利用映射$F_2^k\rightarrow F_2^{k+1}$, 分别通过$2^k$个不同的$k+1$ 元线性函数来构造S盒的分量函数. 类似的, 当$n=2k$为偶数时, 利用映射$F_2^{k-1}\rightarrow F_2^{k+1}$, 通过$2^{k-1}$个$k+1$元线性函数来构造S盒的分量函数. 证明了这种方法所构造出来的S 盒的非线性度都达到几乎最优, 并且与已有结果相比, 在保证相同弹性阶的情况下, 其输出维数也更高.

版权所有 © 密码学报
技术支持: 北京玛格泰克科技发展有限公司