一种基于辫群的密钥交换协议

2022-09-06 03:45权双燕

喀什大学学报 2022年3期

权双燕，张静

（1.陕西理工大学数学与计算机科学学院,陕西汉中 723000;2.东莞职业技术学院现代工程创新实践中心,广东东莞 523808）

0 引言

1993 年，Sidelnikov 等人提出在无限非交换群和半群上建立公钥密码系统的思想[1]，其主要解决如何应用困难问题隐藏因子.如，文献[2]提出了无限非交换群上基于分解问题的密钥交换协议;1947年，Artin提出了辫群的概念，它也是一种无限非交换群，其结构复杂，辫群的乘法和求逆等运算所需要时间和空间都很小.而且辫群上有许多难解的数学问题，如共轭搜索问题、分解问题、马尔科夫问题、根问题等.基于解决这些问题，2000 年Ko等人提出了辫群上基于共轭搜索问题的一种新的密码系统[3]，此后辫群引起了密码学家的关注并被广泛采用.随着量子算法和改进的分解算法的发展，只应用一个困难问题已经不能保证密码系统的安全性，为了提高安全性，同时使用几个困难问题成为一个流行的方法.2007 年Eligijus S 等人同时使用共轭搜索问题和离散对数问题在群上构建了一种密码协议，并阐明了同时使用两个困难问题足够保证密码交换协议的安全性[4].2013 年，Maggie Habeeb 等人第一次将群的半直积用到密码系统中，并提出了一种基于半直积运算的密码交换协议[5].

本文通过半直积的运算法则，在辫群上构建了基于离散对数问题和分解问题的密钥交换协议.因为目前在辫群上没有求解离散对数问题和分解问题的有效量子算法，并且同时在密钥协议中设置两个困难问题可大大提高密钥的安全性，所以本文的密码交换协议具有抗量子攻击性.为证明协议的安全性，本文通过代数攻击和穷尽搜索攻击分析，阐明了该密码协议的抗攻击性.同时，在理论上分析了该密码交换协议的时间复杂度和空间复杂度，数据显示本文的密码交换协议具有可行性.

1 准备知识

定义1 (半直积)(G,⋅)和(G′,∘)是两个半群,Aut(G)是G的自同构群，其二元运算是合成运算.ρ:G′→Aut(G)是一个自同构.G和G′的半直积是一个元素对集合

其中，g,g′∈G和h,h′∈G′,gρ(h′)表示g在自同构ρ(h′)下的像.

事实上，(Γ∗)是一个群，也是直积的扩群.如果(G,⋅)和(G′,∘)是无限群，那么(Γ∗)就是一个无限的非交换群.如果G′=Aut(G)，ρ=idG，那么

其中，ϕ∘ϕ′表示自同构的合成，并且先执行运算ϕ′.

Bij(G?)表示G→G上所有双射构成的集合.在本文的密钥交换协议中，只需要映射ϕ是双射，即ϕ∈Bij(G).在集合

其中ϕ∘ϕ′表示双射的合成运算，并定义(g,ϕ)m=(g,ϕ)m-1(g,ϕ)(m∈Z+).如果G是一个群，对于∀a,b∈G，让ϕ=ϕb(a)=b-1a，显然ϕb(a)是一个双射，并且.那么有

定义2 (中心化子)G是一个群，g∈G，那么集合

是g的中心化子.

事实上，CG(g)是G的子群，对于∀a∈CG(g)满足ag=ga.

其中，整数被称为辫指数，的元素被称为-辫.

辫群有不同的群表示，如Burau 表示、Garsides表示、Birman-Ko-Lee 表示.本文中的密钥交换协议用辫群的Elrifai-Morton 表示，每一个辫都有唯一的左标准型.

定理1[6]任意辫W∈，左标准型是唯一的，可表示为

因此，一个辫W=Δu A1A2…Ap能用一个多元组(u,π1,π2,…,πp)描述，置换辫Ai对应于置换πi，p被称为W的标准长度，用len(W)表示.在文献[6]中，对于用Artin 生成元生成的辫，作者提出了将辫化简为左标准型的算法.

2 密钥交换协议

该密钥交换协议基于辫群，所有的辫用左标准型表示，通过文献[6]中词的算法，一个辫可以表示成左标准型.对映射

Alice和Bob选择不同的参数b作为私钥，对辫群和辫g∈达成一致.密钥交换协议为公钥g.

Alice计算积

让B=h-(n-1)gn，B′=h-1B=h-ngn发送B′给Alice.

步骤3：Alice 计算.

3 安全性分析

本文的密钥交换协议的安全性依赖于辫群上的两个困难问题：分解问题和离散对数问题.A′和B′通过公共信道被发送，攻击者可以观察

寻找k-m，h-n，gm，gn等价于寻找k-m，h-n，gm-1，gn-1，所以通过三元组(g，A′)，B′ 寻找k-m，h-n，gm，gn是辫群上的分解问题，计算m和n，攻击者也必须解辫群上的离散对数问题.如果攻击者能从A′中算出k-m和gm，那么共享密钥K=k-mB′gm就能被得到.类似的，如果他能从B′中算出h-n和gn，那么共享密钥也能被得到.这里，仅考虑以上两种情况中的第一种.