__________________________________________________________________________________________________/ 2017年第4期|技
■ doi ：10.3969/j.issn.1671-1122.2017.04.008
术研究
一类抗量子计算的公钥密码算法研究
--------------------------游伟青，陈小明，齐健---------------------------(北京电子科技学院，北京100070)
摘要：密码技术是保障信息安全的核心技术，密码体制的安全依赖于密钥，管理密钥是 一大难题。利用密钥协商技术能够实现密钥分配的任务，保障用户安全建立共享密钥。目前应 用的密钥协商技术安全性设计大都建立在有限域下离散对数问题上，该问题在量子计算机上已 经有成熟的攻击方法，在量子计算机成功研制之前需要探索能够抵抗量子攻击的密钥交换技术。经典公钥密码系统的弱点随着量子技术的快速发展表现越来越突出。文章分析了 RSA算法的安 全性设计，介绍了一种经典的量子算法对经典公钥密码算法的攻击方法及其工作原理，总结了 成熟的量子计算攻击特性，指出了寻找抵抗量子攻击的必要性及能够抵抗量子攻击的公钥密码 实现平台要求。文章提出了一种强化的随机函数构造方法，给出了一种辫群上改进的密钥交换 协议算法，并从设计安全性与实现效率两个方面对改进后的算法进行了相对全面的分析。
关键词：量子计算；量子攻击；辫群；密钥交换；Shor算法中图分类号：TP393.08
文献标识码：
A 文章编号：1671-1122 (2017) 03-0053-08
中文引用格式：游伟青，陈小明，齐健.一类抗量子计算的公钥密码算法研究[J].信息网络安全，2017 (4):53-60.
英文引用格式：YOU Weiqing, CHEN Xiaoming, QI Jian. Research on a Kind of Anti-quantum Computing Public Key Gryptosystem[J]. Netinfo Security, 2017(4):53—60.
Research on a Kind of Anti-quantum Computing
Public Key Cryptosystem
YOU Weiqing, CHEN Xiaoming, QI Jian
{Beijing Electronic Science & Technology Institute, Beijing 100070, China)
Abstract: Cryptography is the core technology of information security. Password system security depends on the key, and manage key is a big problem. The key agreement technology can be used to achieve the task of key distribution, and to ensure the safety of users to establish a shared key. At present, the security design of the key agreement technology is mostly based on the discrete logarithm problem in a finite field. The problem has a mature attack method on the quantum computer. Before the quantum computer is successfully developed, it needs to explore the key that can resist the quantum attack exchange technology. The weakness of the classical public key cryptosystem is becoming more and more prominent in the face of the rapid development of quantum technology. This paper analyzes the security of RSA algorithm，and introduces the method and principle of typical quantum algorithm to attack the classical public key cryptography algorithm. At the same time, this paper summarizes the characteristics of mature quantum computing attack, and points out the necessity of finding the resistance to quantum attack and the requirement of the public key cryptography to resist the quantum attack. This paper proposes a more random and an improved key exchange protocol algorithm. At last, this paper analyses the advantages of the algorithm from design security and implementation efficiency.
Key words: quantum computation; quantum attack; graid group; key exchange; Shor algorithm
收稿日期：2017-3-1
基金项目：国家重点研发计划[SQ2016YFGX110124]作者简介：游伟青（1994_)，男，安徽，硕士研究生，主要研究方向为密码算法设计与分析、代数学；陈小明（1964—)，男，湖南，教授，博士， 主要研究方向为密码学与信息安全、理论计算机科学；齐健（1992—)，男，安徽，硕士研究生，主要研究方向为信息安全与密码应用。通信作者：游伟青894572560@qq.com
nCtinfo security
技术研究
2017年第4期''
0引言
公钥密码典型的代表为RSA、EIGamal、椭圆曲线上 的Menezes-Vanstone密码体制。公钥密码设计的安全性假 设常基于一个复杂的计算难题，但随着信息技术的快速 发展和密码分析研究的不断进步，这些密码的安全性也受 到了挑战。文献[1]提出的Shor算法证明了其可在多项式 时间内完成对大整数分解和求解离散对数问题，从而对 RSA产生了严重的威胁。此后，Shor算法得到长足的发展， 2003年，PR00Sra等人将Shor算法推广到了椭圆曲线上， 得到了求解椭圆曲线上的离散对数问题（ECDLP)的量子 算法。当然，这些算法需要在量子计算机上运行才能达到 预期的效果。近几年量子技术发展迅速，也意味着对现有 的公钥密码系统产生的威胁日益加重，寻找能抵抗量子计 算的密码尤为重要。
现阶段较为成熟的量子计算的特点是在多项式时间内 完成对基于有限可交换的群、环、域上设计的难解问题的 计算。根据LEE[3]等人的相关理论，可以尝试通过经典算 法在不同平台上的实现去寻找抵抗量子攻击的密码算法，
这就不得不提到代数中非交换结构的典型代表—辫群。
辫群因其无限性和非交换性而使其在密码设计上占有一席 之地。目前量子技术飞速发展，人们迫切需要寻找一些可
以抵抗量子攻击的密码算法，最新的研究表明辫群上的一 些密码算法对抵抗现有的量子计算是可靠的，且已经有许 多优秀的成果，如基于非交换群的同态密码、基于辫群的 密码等。根据DIFFIE和HELLMAN (后文简称DH) [4]提 出的密钥交换算法，ASHEL[5‘6^
人将其在辫群上实现，并
给出一种AAG密钥交换协议算法，该算法可以有效抵抗量 子计算的攻击。
本文详细论述了 Shor算法对HSA的威胁，指出以Shor 算法为典型代表的量子算法对传统密码系统的威胁，并进 一步介绍辫群的基本理论，对辫群上与密码系统相关的定 理给出详细的证明。本文论证了在辫群上实现的DH密钥 交换协议不能抵抗量子攻击，而AAG算法可以抵抗量子攻 击。本文对AAG算法进行了详细研究，给出一种改进的密 钥交换算法，算法所需计算空间与计算时间与原算法相比 明显缩短，但其安全性与原算法完全等价。
54
1辫群基础1.1辫群的基本定义
辫群是由若干条弦互相缠绕所生成的一种群，各条弦 之间可以用不同的方式进行无限次缠绕，每一种缠绕方式 抽象成辫群空间里的元素，由此可见辫群是一种无限的代 数结构。将若干条弦按从小到大编号，自左向右排列，左 边弦穿过右边弦为正辫子，反之为逆辫子。例如，若第i 条弦穿过第7条弦记为&则第7条弦穿过第f条弦记为 V，'为生成元。辫子之间的乘法即为辫子间的相互缠绕， 按照此规律生成复杂的辫群。弦的条数《是刻画辫群的唯 一参数，它由单位元及《-1个生成元按上述的 乘法生成。下面给出辫群的相关数学定义。
定义1 n-辫群 生成的群，如果还满足 则称 定义2字集合 元及其逆组成的一个字母表，它的任意一个序列是辫群 中的一个字（word)。 在辫群中，每一个字都有一个唯一的值，通常称为 辫子。由定义1可知，辫群中的字还拥有一些特殊的数 学运算，这决定了相同辫子有不同的字表现形式。例如, 2x8=4x4=16, 2x8与4x4相当于两个字的表现形式，16 为字的值，也就是辫子。后文中将讲述任何一个字都可以 唯一地表示成一种标准形式，即字的标准型。 如果一个辫子中不含任何逆元，则称其为正辫子，所 有的正辫子组成一个半群，记为5„+。 定义3共辄设;c,7是辫群S„中的元素，若存在疋S„ 使则称文与7共扼。 1.2基础辫子 设足是一个辫群，基础辫子用符号A „表示，则其递归定义为： A=1 = ^n-\\Xn-\\Xn-2 ''，Xl从几何上看，它是一个特殊的辫子,《条辫子相互缠绕, 但任意两条辫子有且仅有一次缠绕，在不至于混淆的情况 下简记为A〇基础辫子有许多非常好的性质。 引理1 :^=么;《„_,证明（数学归纳法）： 当 m=2 时，显然有 aA2= A2x„_;,0 =A*从-1 …'+2\\+1^-1〇«-1 易-2 …A) 由基础辫子递归定义可知印尸^,卜-_/|奋2，则Ak+lx,=\\lxl_1(xlxk_1-■ -x^x^xpc^x^-■ a〇由 归 纳 设 知 ~ +1 易 =&+1( V 假 如 … x，贝U ^ + 职 士 … a) =Xk^\\-Ak+\\所以当《=龢1时也成立，由数学归纳法知引理得证。®Ji 1 An2xi=xiAn2yx,GBn证明： K2 Xi = KiK、、=K(Xn-An)=(Kxn-i)K =0*A )A„ =xAn2 定理得证。 推论1对于辫群尽中任何一个字w,都有A„2w=wA„2。 推论2辫群坎中任何一个字W都可与它的基础辫子 的偶次幂交换。 定义4x整 除 ，若az^GS/，则称JC整除少， 记做X矣少。矣是辫群式+上的一个偏序关系。 定理 2 若d 矣 A1，则 3A,D2Gfi„+, M As=A^=^iV7]。 定义5简单辫子将子集{5G5„: A、5 < As}£fi„记作 [r,札则将[0,1]区间的辫子称为简单辫子。根据A的构造 易知[0,1]区间的辫子均为正辫子，显然，当且仅当rE[0.1] (以A)时，正辫子r是简单辫子。1.3辫子的标准型 由字与辫子的关系可知，辫子是字的值，字是辫子 的表现形式。如果将群中每一个字都唯一地表示成一种形 式，则称这种形式为标准型，标准型的引入可以帮助判别 每个辫子是否相等。分析一些学者的研究发现，现在已 有多种可用的标准型[7_9]，本文介绍由GARSIDE™提出 的左标准型。 n Ctinfo security / 2017年第4期 技术研究 定义6 xaj将与少的最大公约数记作;《/\\>>。^3 对于辫群戽和定义在它上面的整除关系矣，有剛： 1) <5„,矣，a,v> 是一个格（Lattice),即对任意两个 辩子存在唯一■的最大公约数（Greastest Common Divisor,GCD)),记为XAy,也存在唯一的最小公倍辫子(Least Common Multiple, LCM),记为 xyy。 2)每 个Artin生成子是基础辫子A的一 个因子。 3) 简单辫子的集合S是有限的，并且叫=«!。4) 自同构性， 8„,x：⑷ 阶 为 2, 并且相对于偏序关系矣是保序的，即当且仅当 啦矣咖)。特别地，r对于凡+和S均是封闭的，即正辫子 (简单辫子)在映射T作用下的像仍然是正辫子（简单辫子)。 根据Garside定理間，每个辫子蛛均可写成JC= A、 其4UGZJG5：,并且Am不能整除7，户蜗其中， SjG5\\{e，A}。iS—步，如果要求每个 ■满足 则少的这种表示是唯一的。此时，便将A A 称为 辫子xe坎的左规范型，或者简称规范型。给定辫子x的 左 规 范 型 后 ，将基础辫子的指数灸称为x的下 确界（Infimum),记为/»/(外将整数r称为JC的规范长度 (Canonical Length),记为/en⑷，并且将整数灸+a•称为的 上确界（Supermum),记为似户⑷。从几何角度讲，这相当 于将各条带子之间的交叉点尽可能向左、向上推移，并且 保证在每个因子中，任意两条带子之间最多只相交一次。 显然，此时有A*在x矣并且灸和奸/•分别是满足此 条件的最大的和最小的A：+/%这也是称它们分别为下确 界和上确界的理由。 推论 3 V*：GS„+，办GS:使得砂=A\">GZ〇证明： 由定理3可知,VxE5„+都可表示成标准型x=AW =Arsls2---sn ； 当r>0时，x为正辫子，则由文献[7]中命题1可知 3yGB^,s.t.xy=A ； 当？*<0时，J是简单辫子，有J矣A,由文献[7]中命 题 1 可知 3£>Gfi„VUZ)=A ; 故对于任意的《奋-r-1,有《>0,且户4”£>&8二 55 nCtinfo security 技术研究 2017年第4期'' 得证。2量子计算与公钥密码 近几年，计算机硬件和信息技术的快速发展给人们的 生活带来了巨大的变革。小到个人，大到国家与国际贸易 都离不开信息技术，信息技术是一把双刃剑，在给社会带 来进步的同时也出现很多漏洞，填补漏洞的核心技术是密 码技术，因此密码的安全性不言而喻。确保密码的安全是 一切通信安全和现代化、信息化的根本保障。 1976年DIFFIE和HELLMAN[4]提出的公钥密码体 制开创了密码学的新纪元。在公钥密码中，RSA常常被 认为是最成功的公钥密码算法，广泛应用于各种信息系 统，至今中国的大部分银行应用的依旧是RSA密码算法。 1994年，美国贝尔实验室SH0R[1]提出了基于量子计算 模型的大整数分解算法，从而对RSA构成了严重的威胁。 现阶段仍然广泛使用RSA主要有两个原因，一是替代成 本大，可替代品少；另一个原因是当前的量子计算机研发 还不够成熟，没有一款真正意义上的量子计算机。可以 确定的是，量子计算机一旦问世，将轻易摧毁现有的一切 公钥密码系统。密码是信息系统安全的核心技术，不能 停滞不前，寻找抵抗量子计算攻击的密码算法尤为重要， 这也就意味着即使到了量子计算机时代，仍旧可以保证信 息系统的安全性。 2.1 RSA基本原理 RSA由3位伟大的科学家RI VEST、SHAMIR和 ADLEMAN发明，其命名也由3位科学家名字的首字母构成。 RSA的原理很简单，但这并不意味着他们的成就低，实际 上RSA的影响是空前的，不仅在美国，甚至广泛应用于全 世界。RSA与其他公钥密码算法相同，需要产生公开的公钥, 保留私钥，公开公钥后私钥的安全性不受影响，这依赖于 其设计公钥与私钥的难题。 RSA实现步骤如下： 1) 选取两个大素数A?,计算2) 选取一个数作为公开的加密密钥e,需要满l 56 这就产生了公钥对(e,和解密密钥rf。假设Alice拥 有公钥对(e, 和解密密钥公钥对(e，A〇公开，任何人 都可以获得。当Bob要给Alice发送秘密消息m B寸可先计 算c=me mod 并将c发送给Alice ;当Alice接收到这条 秘密消息c后，对其做解密变换c=/w Vod凡 可以清楚地看出，该密码体制设计思路十分清晰明了, 想要破解该密码体制似乎并不是一件难事，只需要将公开 密钥对中的#拆分成两个素数就可以了。但实际上这是一 个很困难的问题，已有大量数学家、密码学家及相关知名 科学工作者花费很多时间尝试去解决这个问题，然而并不 能在有效的时间内去解决该问题，这也是RSA—直被应用 于各类安全系统的根本原因[11]。 2.2 Shor算法对RSA的攻击原理 量子计算机是一类遵循量子*学规律进行高速数学和 逻辑运算、存储及处理量子信息的物理装置。当某个装置 处理和计算的是量子信息，运行的是量子算法时，它就是 量子计算机。虽然现在还没有一台真正意义上的量子计算 机，但在传统计算机上实现量子算法已取得进步，相对传 统算法的速度提升了许多。随着量子计算机研究的进步, 量子算法对公钥密码的威胁日趋严重。针对RSA的攻击, 最有效的办法就是解决大整数分解问题。已经有许多算法 能够解决该问题，但需要耗费大量的时间，此时获取的秘 密已经没有任何意义。Shoi•算法则可以保证其在多项式时 间内完成大整数分解，即破解时间随着公钥长度的增长以 A:次方的速度增长，其中八为与公钥长度无关的常数。 下面简单介绍Shor算法的攻击原理。假设iV为公 开密钥，现在要解决的问题是要找到两个素数〜n2，使 得 1) 记及={«伙AT, (i, A〇=l},其中，（匕A〇表示f与最大公约数。利用欧几里德算法可以找到集合及中的所有 元素，从中随机抽取一个元素，记为?。 2) 选取由f确定的周期函数/闲=^ mod AT(实际Sh〇r算法攻击的关键之处就在求解该函数的周期上)，现 假定办)的周期为r已求得，即 mod札 t r r 3) 求解《i〇 f 令（P)2-l = (A-l)(P+l) = 0modAT， 因此容易得到》i = (?2 +H从而得到《2=她1。 由Shor算法攻击的3个步骤不难发现，其关键技术 #的 上 足在于如何确定周期函数/〇〇的周期r。这个算法在传统计 算机上计算所需要的步骤呈指数型增长，而在量子计算机 上则可以在多项式时间内完成。Shoi•算法的本质也在于此， 将大整数分解问题转化为在多项式时间内利用量子傅立叶 变换求解模#函数周期的问题。有关利用量子傅立叶变换 求解函数周期的方法在文献[12]中有详细说明，如果想更 详细地了解Shoi•算法可参考文献[1]〇 2.3抗量子计算的公钥密码体制 自公钥密码体制出现以来，一些学者陆续提出了许多优 秀的公钥密码，同时，针对这些密码系统的安全性也有许多 讨论。而最近的一些研究表明，当前这些被认为安全的公 钥密码算法在面对量子算法分析时，可能存在很大的被攻 破的危险。目前广泛使用的，也被认为是安全的密码体制其 安全性假设大都依赖于某个特定的数学上的计算难题。其 中，整数分解难题和离散对数难题以及它们的一些变体或 推广（如有限域上椭圆曲线的离散对数问题）仍然是最典型 的两类安全性假设，如RSA、EIGamal113]、椭圆曲线密码系 统ECC[14’15]、二次域理想类群上的密码系统岡等。 然而，量子算法需要在量子计算机上运行才能真正做 到破解这些经典的公钥密码系统，但是，一旦量子计算机 问世，带来的灾难将是毁灭性的。这也正说明了寻找在量 子计算机时代仍能够确保安全的密码的迫切性。总结现有 的典型的量子算法，主要是针对有限交换群（环、域)，尤 其是以数论上的难解问题进行攻击的。对于抵抗量子算法 攻击的问题，LEE[3]等人的观点是寻找不同的结构用以实 现经典密码算法，有可能起到抵抗量子算法攻击的作用。 实际上，由Shor算法为代表的量子计算原理可知，量 子计算机善于计算基于数论的难题，也擅长求解离散对数 问题。现代公钥密码学常常被称为基于NP问题设计的公钥 密码体制，如果用QNP定义量子世界里的NP问题，那么 QNP问题就是量子计算机不擅长的运算了，这样就能够保 证密码体制的安全，而辫群上的共扼搜索问题(》2是 中的两个辫子，且Wi与w2共辄，求 使 就 是量子计算机不擅长解决的数学难题。至于DNA密码等 这些非基于数学难题的密码还是处于初步发展阶段，不足 以直接作为抗量子密码系统的应用研究[17]〇 Shor算法的核心内容是量子傅立叶变换，其能够在多 n Ctinfo security / 2017年第4期 技术研究_ 项式时间内完成基于数论上大整数分解问题的求解，由 Shor算法推广也可以获得有限域下离散对数难题和椭圆曲 线上离散对数问题的求解。但这并不意味着量子计算是万 能的，其在量子傅立叶变换过程中对非交换结构、无线空 间是困难的，而基于辫群上的共轭搜索问题设计的公钥密 码系统，Shor算法及其推广无法在多项式时间内完成对其 求解。因此，基于辫群上共轭搜索问题设计的一些公钥密 码系统对抵抗量子计算攻击表现的十分有潜力。 基于辫群的公钥密码系统于2000年由K0P]等人提出， 因此也引发了对辫群研究的高潮，一些学者也提出了许多 新的观点和设计方案。研究辫群上抗量子攻击的密码算法 仅仅只是一个开始，以辫群为出发点，对一类基于非交换 群上公钥密码体制的研究赢得了许多好评，由此再次掀开 对基于公钥密码系统安全性的研究。辫群是一种典型的非 交换无限生成群，因为其非交换、无限的特性，可应对现 在迅速发展的针对有限的交换群（环、域）的量子算法。 此外，辫群是代数生成群的一种，区别于数论上的一些难 解问题。当然，现阶段还没有给出非常严谨的数学证明来 证明这些基于辫群的公钥密码系统能够抵抗所有的量子攻 击，但可以证明现有的量子算法对这类密码系统尚不构成 威胁。 3辫群上的密码算法 3.1 Diffie-Hellman密钥交换算法 Diffie-Hellman密钥交换算法（简称DH算法）由 DIFFIE和HELLMAN14]发明，该算法仅用于建立共享的对 称密钥。DH算法的安全性依赖于离散对数问题的计算难 题，其数学构造相对比较简单。 设定P为素数，并假定g是生成器，即对于任何的 xE{l,2,\"S/7-l}都存在指数《，使得JC=g\"m〇dA其中，素 数P和生成器g是公开的。 实际密钥交换过程中，Alice随机地选择秘密指数a, Bob随机地选择秘密指数Alice计算;mod 将结果 发送给Bob,而Bobi十算将结果; V发送个Alice。 然后 Alice 执行 s=/ mod_p=(gY m〇dp=/Vodp ;而 Bob 执行 fcx6 mod mod 户。显然有 ga6mod p 即 为Alice与Bob共享的秘密，其典型的用途是作为对称密钥。 57 2017年第4期'' 这就解决了对称密钥加密技术中如何安全地分发对称密钥 的问题。 3.2辫群上的DH算法 基于辫群的公钥密码系统能够有效对抗未来量子计算 机的分析。在提出辫群上的DH算法之前简单介绍一下辫 群的一类子群。 定义7左子群设尽是由；生成的一个辫群， 如果Km-1,由;生成的辫群是的一个子群，并 称这个子群为尽的左子群，记作^„〇 定义8右子群设是由;&生成的一个辫群， 如果f>l,由生成的辫群是的一个子群， 并称这个子群为式的右子群，记作 定理4设凡是一个辫群，且W 式，i?尽矣式，则 对于V*GZ式 及 有 砂 =)«,即左子群中的任意元与 右子群中任意元均可交换。 尽管辫群是一种非交换群，但只要选取合适的子群， 来自不同子群中的字便可以满足交换律，从而满足DH密 钥交换协议的构造条件。 从辫群見中随机产生的一个字s作为加密的公钥，在 左子群i尾中随机生成一个字作为Alice的私钥X,在右子 群及5„中随机生成一个字作为Bob的私钥y,由定理4可 知x与少可交换。 DH密钥交换协议执行过程如下： 1) Alice计算户mf1，雛户通过公共信道发送给Bob ;2) Bob计算产少吵-1,将值分通过公共信道发送给ABce ;3) Alice获得值《，计算<5=叫x_1 ;4) Bob 获得值;?，计算 r=;^y_1 ;因为I与7可交换，所以有叮=)«。因为 =(妙(破\\ r=聊_1=少 (xsx_1)少_1=(功s(■明_1,所以 5=ro 由此可见该过程使Alice和Bob获得了共同的秘密， 扣r,安全地分发了密钥，建立了共享的对称密钥。 3.3 Anshel-Anshel-Goldfeld ( AAG )算法 设是 辫群 ^ ■ 中 的 两 组 Artin生 成元，且 为 Alice的公钥，免也,•••,&)为Bob的 公钥，AAG算法执行过程如下： 1) Alice计算bM hjw,)，M是一个特殊的函其作用是返回(A,抑的任意一个排列，即随机选取 58 Artin生成元组(化，；^,•••，；>,)中元素组成一个字。首次生 成s后，排列不再改变^与排列方式保密。使用s对Bob 的公钥加密，计算的'=叫Csg21S_1,_\gr„=i^„S_1,并将 (9;,?m)通过公共信道发送给Bob。 2) Bob计算r=vqv\qr,),v是一个特殊的函数，其 作用是返回(丨必，…，心）的任意一个排列，即随机地选取 Artin生成元组r=v(^，g2,_\素组成一个字。首次 生成r后，排列不再改变,r与排列方式保密。使用r对 Alice 的公钥加密，计 算 r_1,并 将通过公共信道发送给Alice〇 3) 通过步骤1)、步骤2), Alice获得了信息并对公式（2)进行计算。 S = s_u(p; ,p”...，p;'T1 = s-(r-u(pl,p2,...,pl)-r-1y1 ............................. (2)= 5\"(r-5,-r\"1 )_1 4) 通过ill)、步骤2), Bob获得了信息⑷，心n), 并对公式（3)进行计算。 T = v{q[ ,q2 ,...,qm)-r-1 = s-v(q1,q2,...,qm)-s'Kr-1 =srj'V-1 由公式（2)和公式（3)可知， 由此可见，该过程使Alice和Bob获得了共同的秘密, 5=7；安全地分发了密钥，建立了共享的对称密钥。 3.4改进的AAG算法 本文对AAG算法进行深入研究之后，提出一种改进 的AAG算法，主要改进两个部分，第一部分是增强随机 函数保密性，提高私钥的安全；第二部分是对算法的步骤2) 和步骤3)进行改进，提高算法效率。 定义9私钥生成器设《是定义在辫群凡上的函数，它 的参数可以是任意多个辫子，当给定《函数辫子参数时，《 函数从辫子参数及其逆中随机生成一个长为A的序列，此 后“函数初始化完毕，完成一次密钥交换后自毁。本文称 «函数为私钥生成器。 在辫群圪上应用一般的随机数生成算法容易生成两 组辫子A,A,\" 及9i,W ,心，这两组辫子分别作为Alice 和， Bob的公钥。Alice和Bob分别利用其公钥作为私钥生 成器的参数，使用私钥生成器《、v得到各自的私钥，私钥 数生成方式保密。首先使用随机算法逐个生成辫子作为输入, 再利用私钥生成器产生密钥，这一过程不仅在原有的辫群 空间上大大增加了密钥长度，还增加了私钥的随机性，从 而具有更强的保密性能。私钥生成器构造好之后，对A AG 算法进行改进，具体步骤如下： 1) Alice私钥 计 算 仍 ’=i^s_V=l，…，m 并将其发送给Bob。 2) Bob 生成私钥/*=v(的，)，计算 并将其发送给Alice。 3) 通过步骤1)、步骤2)后，Alice获得了信(Pi>2’，…，；0，并计算 ^咖’，；^，…，；^’).八 4) 通过步骤1 )、步骤2)后，Bob获得了信息«也’,\"•,&’)， T=r'-v(quq2,---,qm)〇因为 …，仍’)•■st 厂 (的…，心’)=!； 所以Alice和Bob获得共同的秘密值5。该算法与原算法 的密钥交换方式相同，应用的运算也相同，唯一改变的是 计算次序，由此可见算法的安全性完全等价。整个密钥交 换系统中，私钥生成器的安全决定了私钥的安全，私钥的 安全直接影响了整个密码系统的安全。改进的算法用文中 定义的私钥生成器代替原有随机函数，产生的私钥序列具 有更好的随机性，从而增强该体制的安全性。用户还可以 根据实际需要，使私钥生成器生成符合不同安全要求的私 钥，从而大大提高通信效率。 3.5改进的AAG算法与原AAG算法实现速率比较 本文算法中步骤2)发送的中间值为AAG算法中间值 的逆，但这一过程所需的运算资源相等，在计算共享密钥时, Alice直接减少了对私钥发生器的求逆过程。整个计算中， 这一过程所需的运算资源最大，Bob所需要的计算资源则 与原算法相同。这是因为在步骤1)、步骤2)中已经计算了 5和广的逆，最后Alice只需将得到的数据代人《函数即可， 而原AAG算法中需要再进行一次求逆运算。 在保密通信中，通信双方常常对效率要求不同。例如， Alice需要发送一条秘密消息给Bob,而Bob通常会急于 解密，及时获得消息，做出相应的反应，这时Bob如果 能减少一些运算资源，是一个相当不错的选择。Steven 大学设计的代数密码学源代码库中提供了辫群的基本实 现[18]，本文在此基础上将改进的AAG算法用C++语言 n Ctinfo security ______________________________ 2017年第4期 技术研究 在Linux环境下进行测试，用以对比两个算法的实际执行效率。 不妨取有2000条弦的辫群，算法实现效率的影响主 要有3个参数：/ ( Alice的公钥长度）、/« ( Bob的公钥长 度)、 (私钥生成器单个输入单元的长度)。下面对 这3个参数对算法实现效率的影响进行分析。 令/=20, /«=10,计算不同紿值下AAG算法与改 进的AAG算法的执行时间，如图1所示。 图1当f=20,«=10时不同length值下AAG算法与改进的AAG 算法的执行时间 由图1可以看出，当参数/和《固定，邮A值增加时， AAG算法执行时间总体呈现增长状态，且增长幅度较为明 显；改进后的AAG算法执行时间随着kngfA的增长基本 保持水平状态。由此可知，通过增加伙值来提高算法 安全性时，改进后的算法更加有效。 令/engfA=20, /«=10，计算不同Z值下AAG算法与改 进的AAG算法的执行时间，如图2所示。 -----AAG算 法 ------改进的AAG算法 1600000 -----------------------------------------------------------------------------------------------------------------1400000 -----------------------------------------------------------------------------------------------------/ 、 112800 0i 6040200 图2当ten班A=20, iw=10时不同/值下AAG算法与改进的 AAG算法的执行时间 由图2可以看出，作为算法的影响因素之一的Alice公 钥长度实际对算法时间效率影响并不大，改进后的算法与 改进前的算法没有发生太大的变化，时间趋势保持一致。 令/e«gfA=20, /=20,计算不同ffi值下AAG算法与改 进的AAG算法的执行时间，如图3所示。 59 息nCtinfo security 技术研究 2017年第4期'' -------AAG算法 -一織的AAG算法 JWUUW > 卜、I............ !r、、j 图3当/«!济A=20, f=20时不同1*1值下AAG算法与改进的 AAG算法的执行时间 由图3可以看出，当参数fen钟和/固定,/w值增加时， AAG算法执行时间快速增长，改进后的AAG算法执行时 间随着&叹认的增长基本保持水平状态。由此可知，通过 增加m值来提高算法安全性时，AAG算法执行时间将大 幅度提高，此时改进后的算法优势十分明显。 增加密钥长度无疑是提高密码系统安全性的一个最简 单最有效的方法，但往往是以牺牲昂贵的计算时间和空间 为代价的。如果希望通过提高密钥长度的方法来提高密码 系统的安全性，又要保证不能使用过多的计算资源和存储 空间，就必须对算法实行优化或改进。通过对影响密码算 法实现效率的3个参数的分析可知，当提高m和 值 时，算法密钥长度增加可以提高算法的安全性，而改进后 的算法却不会因为密钥长度的增加而导致算法执行时间快 速上升，这种改进虽然简约但对原算法来说没有任何的损 失，所以这种设计具有一定的应用价值。 4结束语 辫群是一种无限非交换生成群，研究辫群上的公钥密码 算法是研究无限非交贼数结构特性的重要途径。现有量子 计算攻击主要针对的是基于数论上难解问题或有限交獄数 结构的难题设计的密码系统，所以研究辫群上的公钥密码算 法具有重要意义[19]〇本文通过Sh〇r算法分析了量子计算对 现有公钥密钥的威胁，指出了设计在量子计算机时代仍能保 证信息系统安全的公钥密码系统的重要性。随后分析了基于 辫群共轭搜索问题的一些公钥密码算法抵抗量子算法攻击的 原理，并给出DH密钥交换协议在辫群上的实现。最后本文 提出了一种改进的A AG算法，严格证明其安全性，并进一步 通过实验验证改进后的算法运算速率明显提高。信息安全问 题常常会存在“木桶效应'所以要设计出抵抗量子攻击的密 码系统就要求系统的每一个部分都需要有抵抗量子攻击的性 60 能。接下来需要深人研究抗量子攻击的数字签名，以确保身 份认证在量子攻击的环境下也是安全的。•(责编潘海洋） 参考文献： [1] SHOR P W. Polynomial—time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computerff]. SIAM Journal on Computing archive, 1997, 26(5): 1484—1509. [2] PROOS J, ZALKA C. Shor* s Discrete Logarithm Quantum Algorithm for Elliptic Curvesp]. Quantum Information and Computation, 2003, 3(4): 317-344. [3] LEE E, LEE S J, HAHN S G. Pseudorandomness from Braid Groups [C]// Springer. 21st Annual International Cryptology Conference on Advances in Cryptology, August 19—23, 2001, Santa Barbara, CA, USA. Berlin: Springer, 2001: 486—502. [4] DIFFIE W, HELLMAN M E. New Directions in CryptographyQ]. IEEE Transactions on Information Theory, 1976, 22(6): 644—654. [5] ASHEL I, ANSHEL M, FISHER B, et al. New Key Agreement Protocols in Braid Group Cryptography[EB/OL]. https://www. researchgate.net/jmblication/221208306_New一Key 一A greement— Protocols一inJBraid一Group_Cryptography，2017—l—22. [6] ASHEL I, ANSHEL M, GOLDFELD D. An Algebraic Method for Public—key CryptographyQ]. Math. Research Letters, 2001, 6(3): 287—291.[7] KO K H, LEE S J, CHEON J H, et al. New Public-Key Cryptosystem Using Braid Groups[C]// Springer. 20th Annual International Cryptology Conference on Advances in Cryptology, August 20—24, 2000, Santa Barbara, California, USA. Berlin: Springer, 2000: 166—183. [8] BIRMAN J S, KO K H, LEE S J. A New Approach to the Word and Conjugacy Problems in the Braid GroupsQ]. Advances in Mathematics, 1998, 139(2): 322-353. [9] BIRMAN J S, KO K H, LEE S J. The Infimum, Si^reamim, and Gecxlesic Length of a Braid Conjugacy ClassQ]. Advances in Mathematics, 2000,164(1): 41—56.[10] GARSIDE F A. The Braid Group and Other Groups [J]. Quarterly Journal of Mathematics, 1969, 20(1): 235—254. [11] 王励成.基于辫群的密码方案的设计与分析[D].上海：上海交通 大学，2007. [12] 杜治国.量子计算与公钥密码[J].数学的实践与认识,2006,36(5): 173-176. [13] ELGAMAL T. A Public Key Cryptosystem and Signature Scheme Based on Discrete Logarithms [J]. IEEE Transactions on Information Theory, 1985, 31(4): 469-472. [14] 陈宇航，贾徽徽，姜丽莹，等.基于Grover算法的ECC扫描式 攻击〇].信息网络安全，2016 (2): 28-32. [15] KOBLITZ N. Elliptic Curve CryptosysternsQ]. Mathematics of Computation, 1987, 48(177): 203—209. [16] BUCHMANN J, WILLIAMS . C. A Key-exchange System Based on Imaginary Quadratic Fields[J]. Journal of Cryptology, 1988, 1(2): 107-118. [17] 贾徽徽，王潮，顾健，等.基于Grover量子中间相遇搜索算法 的ECC攻击错误bit的修正[J].信息网络安全，2016 ( 6 ) : 28-34. [18] MYASNIKOV A, USHAKOV A. Cryptography And Groups (CRAG) C++ Library[EB/OL]. http://web.stevens.edu/algebraic/ downloads.php, 2017—1—22. [19] 何光蓉，汪学明.一种新的基于HECC的Ad Hoc组密钥管理方案〇].信息网络安全，2016 (5): 58-63. 因篇幅问题不能全部显示，请点此查看更多更全内容