2. 综合业务网国家重点实验室(西安电子科技大学), 陕西 西安 710071
2. State Key Laboratory of Integrated Services Networks(Xidian University), Xi'an 710071, China
自量子计算机被提出以来, 量子计算机在最近几十年里已经成为世界各国战略竞争的焦点.各国研究人员对量子计算机的研究从未间断.与此同时, 研究人员也一直在寻找未知的算法, 这些算法可以应用于量子计算机, 并且利用量子计算机来解决当前传统计算机所不能解决的困难问题.这一类算法也被称为量子算法.例如, 目前已经提出解决RSA所基于的数学困难问题的量子算法[1].这预示着, 如果量子计算机研制成功, 将严重威胁目前网络数字通信中数据的安全性.因此, 与之对应的抗量子密码算法的研究成为目前密码学学者关注的一个热点, 目的是为将来量子计算机时代提供安全的密码算法.
多变量公钥密码体制、基于格的密码算法、基于编码问题的密码算法以及基于Hash的密码算法都是抗量子密码学的研究热点.多变量公钥密码体制作为抗量子密码算法的研究热点之一, 其主要优点体现在多变量公钥密码体制的计算效率高、功耗小, 可以应用于存储和计算能力有限的设备上.
最早的多变量公钥密码方案在1988年由Matsumoto等人提出, 即著名的Matsumoto-Imai(MI)[2]加密方案.这是多变量公钥密码发展史上一个具有里程碑意义的方案.1995年, Patarin利用线性化方程攻破了MI多变量加密方案, 并且Patarin等人在MI体制的基础上又提出了隐藏域方程(hidden field equation, 简称HFE)多变量公钥密码体制[3], HFE密码体制是将MI体制中的多变量单变元单项式方程变成单变元多项式方程.然而, HFE方案很快被Kipnis等人[4]攻破.随后, 更多的多变量加密方案和多变量签名方案相继被提出.
在随后的方案中, 密码学研究者主要通过以下几种方法来提出新方案:一种是通过寻找和设计新的、安全的中心映射来构造新的多变量公钥密码方案; 另一种方法是通过一定的手段对已有方案进行改进, 比如, 比较有名的改进多变量方案的方法有扰动方法、加方法、减方法; 亦或将已有的几个方案结合起来形成新的方案, 使之达到抵抗已知攻击的目的.随后出现的有名的多变量方案包括油醋(oil and vinegar, 简称OV)[5]、不平衡油醋(unbalanced oil and vinegar, 简称UOV)[6]多变量签名方案、SFLASH[7].在UOV的基础上, Ding等人[8]设计了彩虹(rainbow)签名方案.采用扰动方法、加方法、减方法对已有方案进行改进得到的方案有PMI(perturbed Matsumoto-Imai)[9], PMI+(perturbed Matsumoto-Imai-plus)[10]等.然而, 绝大多数多变量公钥密码方案已被证明是不安全的.目前, 新的安全的多变量方案有ZHFE(Zhuang-Zi hidden field equation)[11]、ABC(simple matrix encryption scheme)[12]、cubic-ABC(cubic simple matrix encryption scheme)[13]、SRP(square Rainbow plus)[14]方案. ZHFE方案是使用两个高阶的HFE多项式来构造中心映射.ABC, cubic-ABC方案是通过构造新的中心映射结构来设计多变量加密方案, 其优点是高效的加密和解密算法.SRP方案是Yasuda等人提出的一个新的多变量加密方案, SRP就是将Square加密方案、Rainbow签名方案以及Plus方法这3种多变量密码技术相结合而形成的一个多变量加密方案.这几个方案在目前来说是安全的, 它们的安全性还需进一步分析.
一方面, 密码学研究者不断设计更安全、更实用的多变量公钥加密、签名体制; 另一方面, 虽然与传统的公钥密码体制相比, 多变量公钥密码体制具有计算效率高的优点, 但同时, 它也存在密钥量大的缺点.因此, 对于多变量公钥密码体制的研究还体现在如何设计密钥量小的公钥密码方案, 使得多变量公钥密码方案密钥的存储空间尽可能地小.
Petzoldt等人提出了CyclicRainbow方案[15], 主要方法是在Rainbow的公钥麦考利矩阵中插入特殊的循环结构, 使得公钥大小降低了62%.更重要的是, CyclicRainbow的签名验证与Rainbow方案的签名验证相比, 可以减少30%的模乘运算, 这意味着可以提高签名验证效率.Petzoldt等人[16]在2013年的后量子密码会议上详细说明了采用循环公钥的UOV和Rainbow方案.2016年, Duong等人又将循环公钥的思想运用于SRP方案, 提出了CyclicSRP[17], 使得SRP的公钥大小降低了54%.同时, 在加密过程中减少了50%的模乘运算.更重要的是, 这样的结构并没有削弱原始SRP的安全性.文献[17]指出:通过这样的方法, 使得CyclicSRP成为第1个减小公钥大小的多变量公钥加密方案.这种特殊结构的SRP方案的公钥仅为ABC, ZHFE方案公钥的一半, 同时, 加密过程所需的时间也仅为其他方案的一半.
2015年, Shen等人[18]提出一个混合类型的多变量公钥签名RGB(red-green-blue)方案.RGB方案是在UOV方案的基础上提出的.RGB方案最大的特点就是它属于一个混合类型的多变量签名方案, 在其中心映射中, 消息值与其他变量可以更好地混合在一起, 因此, 该方案生成的签名难以伪造.RGB方案在选择合适参数的情况下, 可以抵抗已知的代数攻击.与其他方案(如UOV, Quartz, Rainbow, RSA-1024)相比, RGB方案在安全性和效率方面性能更佳.RGB适合于计算能力有限的设备, 例如RFID设备、掌上设备、无线传感器网络等.但是和其他多变量方案一样, RGB方案也存在公钥量大的缺点.
本文通过分析RGB方案的结构特性, 将循环公钥的方法与RGB混合多变量公钥密码方案相结合, 提出了本文方案.通过采用循环公钥的思想, 利用RGB中心映射系数矩阵和公钥系数矩阵的关系, 构造了CyclicRGB多变量混合签名方案.新方案CyclicRGB的公钥具有更加紧凑的结构, 从而降低RGB的公钥大小.进一步地, 利用公钥的特殊结构来提高RGB签名方案在进行签名验证时的效率.本文方案将更有利于RGB方案在低端设备上的应用.
本文第1节介绍多变量公钥签名方案, 包括UOV方案和RGB混合多变量签名方案.第2节在分析RGB混合多变量签名方案的基础上具体设计CyclicRGB混合多变量签名方案中的签名验证算法.同时介绍CyclicRGB签名方案, 并对方案的正确性予以证明.第3节对方案的安全性予以说明.第4节对RGB方案和CyclicRGB方案的公钥大小和验证签名的效率进行比较.第5节采用C++对RGB方案和CyclicRGB方案进行实现, 并对签名验证的实验结果进行比较.第6节总结全文.
1 RGB混合多变量签名方案介绍及其分析多变量公钥密码方案是后量子密码时代保证网络数字信息安全通信的重要手段之一.多变量公钥密码基于的数学困难问题是解有限域上多变量多项式方程组的困难性(MQ问题)以及IP(isomorphism of polynomial)问题.其基本思想是:选择有限域的一个可逆多变量多项式方程组F作为中心映射(这里的可逆是指可以通过某种方式较容易地求出前像值); 同时, 选择两个可逆仿射变换L1, L2来隐藏中心映射的结构.这种结构下, 多变量公钥密码方案的私钥为(F, L1, L2), 公钥为
使用多变量公钥密码方案对消息m的哈希值h=H(m)进行签名时, 使用私钥分别进行如下计算:
创建可逆的多变量二次系统的一种方法就是采用不平衡油醋方案(UOV).UOV方案由Kipnis等人[6]提出, UOV方案是对OV方案的扩展.UOV公钥形式为P=FoL.
假设K为有限域, o和v为两个正整数, 并且v > o, n=o+v.设整数集合为V={1, 2, ..., v}, O={v+1, v+2, ..., n}.在n个变量x1, x2, ..., xn中, 前v个变量x1, ..., xv称为醋变量, 后o个变量xv+1, ..., xn称为油变量.UOV中心映射是由o个多变量多项式方程构成的方程组F=(f(1)(x1, ..., xn), ..., f(o)(x1, ..., xn)), 其中, 每个多变量多项式方程形式如下:
$ {{f}^{(k)}}({{x}_{1}}, ..., {{x}_{n}})=\sum\limits_{i=1}^{v}{\sum\limits_{j=1}^{v}{{{a}_{ij}}{{x}_{i}}{{x}_{j}}+}}\sum\limits_{i=1}^{v}{\sum\limits_{j=1}^{o}{{{b}_{ij}}{{x}_{i}}{{x}_{v+j}}}}+\sum\limits_{i=1}^{o}{{{c}_{i}}{{x}_{v+i}}}+\sum\limits_{j=1}^{v}{{{d}_{j}}{{x}_{j}}}+e(k=1, ..., o). $ |
映射F=(f(1)(x1, ..., xn), ..., f(o)(x1, ..., xn))可以通过以下方式求逆:首先, 随机选择v个醋变量值x1, ..., xv, 将这v个值代入多变量多项式方程组, 得到关于o个变量xv+1, ..., xn的线性方程组; 通过高斯消元可以求出这o个变量的值, 如果无解, 则重新选择醋变量来求解线性方程组, 直至求得o个变量的值; 再将随机选择的v个醋变量的值和求得的o个油变量的值代入L的逆, 即得到消息的UOV签名.
1.2 RGB混合多变量签名方案的介绍及其分析 1.2.1 RGB多变量公钥签名方案Shen等人[18]在UOV方案的基础上提出一个混合多变量签名方案RGB.该方案中, 首先定义了一个特殊结构的多项式, 称为三色多项式(RGB多项式).与UOV方案相比, RGB多项式包括3种类型的变量, 并且每个RGB多变量多项式方程的二次项系数组成的相关对称矩阵的表示形式与比色法中的三色模型结构相似, 因此将这种特殊结构的多项式称为RGB多项式, 这就是RGB多项式名称的由来.
具体地, 设K是特征值为p的有限域, 并且阶为q=pk(k是一个正整数).RGB中有3类变量(分别标记为Red变量、Green变量、Blue变量), 设正整数r, g, b分别表示Red变量、Green变量、Blue变量的个数, 并且整数n=r+g+b.3类变量具体表示为Red变量x1, ..., xr, Green变量xr+1, ..., xr+g, Blue变量xr+g+1, ..., xn, 并且S1:Kr
$ \begin{align} {{f}^{(k)}}({{x}_{1}}, ..., {{x}_{n}})=\sum\limits_{i=1}^{r}{\sum\limits_{j=1}^{r}{A_{ij}^{(k)}{{x}_{i}}{{x}_{j}}+\sum\limits_{i=1}^{r}{\sum\limits_{j=1}^{g}{B_{ij}^{(k)}{{x}_{i}}{{x}_{r+j}}}}}}+\sum\limits_{i=1}^{r}{\sum\limits_{j=1}^{b}{C_{ij}^{(k)}{{x}_{i}}{{x}_{r+g+j}}}}+ \\ \sum\limits_{i=1}^{g}{\sum\limits_{j=1}^{b}{D_{ij}^{(k)}{{x}_{r+i}}{{x}_{r+g+j}}}}+ \\ \sum\limits_{i=1}^{b}{\sum\limits_{j=1}^{b}{E_{ij}^{(k)}{{x}_{r+g+i}}{{x}_{r+g+j}}+\sum\limits_{i=1}^{r}{G_{i}^{(k)}{{x}_{r}}}}}+\sum\limits_{i=1}^{g}{H_{i}^{(k)}{{x}_{r+i}}+\sum\limits_{i=1}^{b}{L_{i}^{(k)}{{x}_{r+g+i}}}+{{R}^{(k)}}}(k=1, ..., g), \\ \end{align} $ |
其中,
$ F\left( {{x}_{1}}, ..., {{x}_{n}} \right)=\left( {{f}^{(1)}}\left( {{x}_{1}}, ..., {{x}_{n}} \right), \ldots, {{f}^{(g)}}\left( {{x}_{1}}, ..., {{x}_{n}} \right) \right). $ |
RGB多变量签名方案由3种多项式时间的算法组成, 即密钥生成算法Kg、签名生成算法Sign以及签名验证算法Verify.
密钥生成算法Kg.
这一多项式时间算法主要是系统根据适当的安全参数为用户生成相应的RGB方案的公钥和私钥.RGB混合多变量方案的公钥为P=S3oFo(S1×S2), 对应的私钥为(S1, S2, S3, F).然后, 用户使用自己的私钥对消息进行签名.
签名生成算法Sign.
生成的签名为X
该算法输入签名者的私钥和待签名消息值M=(x1, ..., xr), 生成对应的消息签名.签名算法需要执行以下步骤, 生成消息的签名X=(xr+1, ..., xn).
(1) 计算
(2) 随机选择
$ \left\{ \begin{array}{*{35}{l}} {{f}^{(1)}}({{{{x}'}}_{1}},...,{{{{x}'}}_{r}},{{{{x}'}}_{r+1}},...,{{{{x}'}}_{r+g}},{{{{x}'}}_{r+g+1}},...,{{{{x}'}}_{n}})=0 \\ \vdots \\ {{f}^{(g)}}({{{{x}'}}_{1}},...,{{{{x}'}}_{r}},{{{{x}'}}_{r+1}},...,{{{{x}'}}_{r+g}},{{{{x}'}}_{r+g+1}},...,{{{{x}'}}_{n}})=0 \\ \end{array} \right.. $ |
对这个线性方程组采用高斯消元, 可以求得方程组的解, 从而求得g个变量
(3) 结合步骤(2)求得的g个变量
$ X=S_{2}^{-1}({X}')=S_{2}^{-1}({{{x}'}_{r+1}}, ..., {{{x}'}_{r+g}}, {{{x}'}_{r+g+1}}, ..., {{{x}'}_{n}})=({{x}_{r+1}}, ..., {{x}_{r+g}}, {{x}_{r+g+1}}, ..., {{x}_{n}}). $ |
最后, X即为消息M的签名值.
签名验证算法Verify.
对于签名的验证, 验证者为了验证签名是否有效, 执行签名验证算法Verify.验证者使用签名者的公钥对接收到的消息M以及消息的签名X进行验证:
$ P(M, X)=P({{x}_{1}}, ..., {{x}_{r}}, {{x}_{r+1}}, ..., {{x}_{r+g}}, {{x}_{r+g+1}}, ..., {{x}_{n}})\overset{?}{\mathop{=}}\, 0. $ |
如果上式成立, 则认为X是对消息M的合法签名, 并且验证算法返回1;否则, 签名无效, 输出
RGB方案是UOV方案的改进, 如果把RGB混合多变量多项式方程中的Red变量和Blue变量看作醋变量, 把Green变量看作油变量, RGB多变量多项式就是OV多项式.在这一部分, 我们简单分析RGB方案公钥结构、公钥大小以及签名验证的具体计算过程, 这些分析是进一步设计CyclicRGB方案的基础.
RGB方案的公钥是以下3部分的复合.
$ P={{S}_{3}}\circ F\circ ({{S}_{1}}\times {{S}_{2}}), $ |
其中,
$ P={{S}_{3}}\circ F\circ {{S}_{0}}. $ |
上述结构形式与多变量方案的一般模型相同, 接下来, 我们利用上述公钥组织结构中的符号做进一步的分析与设计.具体地, 可以将RGB多变量公钥的每个多项式表示成如下形式:
$ {{p}^{(k)}}({{x}_{1}}, ..., {{x}_{n}})=\sum\limits_{i=1}^{n}{\sum\limits_{j=i}^{n}{p_{ij}^{(k)}{{x}_{i}}{{x}_{j}}}}+\sum\limits_{i=1}^{n}{q_{i}^{(k)}{{x}_{r}}}+{{r}^{(k)}}(k=1, ..., g). $ |
RGB多变量签名方案的公钥由关于n(n=r+g+b)个变量的g个多变量多项式方程组成, 公钥的大小为
$ g\cdot \frac{(n+2)(n+1)}{2}. $ |
假设RGB多变量公钥的系数矩阵为Pm, 在验证消息M=(x1, ..., xr)和给定消息的签名X=(xr+1, ..., xr+g, xr+g+1, …, xn)是否有效时, 需要将消息值和签名值进行一定的运算, 然后将这些值代入RGB多变量公钥中进行验证.具体步骤如下.
● 首先, 计算向量值
● 然后, 将向量vec与签名者的公钥进行计算:
$ P(M, X)=Pm\times ve{{c}^{T}}=\left( \begin{matrix} Pm[1]\cdot ve{{c}^{T}} \\ Pm[2]\cdot ve{{c}^{T}} \\ \vdots \\ Pm[g]\cdot ve{{c}^{T}} \\ \end{matrix} \right), $ |
其中, Pm[i]是公钥系数矩阵的第i行向量.
● 最后, 根据上述公式的计算结果判定签名的有效性.
从上述分析可以看出, Rainbow方案的公钥与多变量公钥密码方案的一般模型相吻合.接下来对公钥方程
本节我们将描述如何构建具有部分循环公钥的RGB混合多变量公钥签名方案.下面我们分析在给定公钥方程组以及可逆仿射变换S3和S0的情况下, 可以确定中心映射F.
首先分析RGB方案中公钥和私钥的关系.通过第1.2.2节中的分析, RGB多变量公钥可以表示为3部分的复合运算:
$ P={{S}_{3}}\circ F\circ {{S}_{0}}. $ |
中心映射F是关于n个变量的g个二次方程组成的方程组.对于F中每个多变量二次方程, 假设Fm为该方程组的系数矩阵, 并且用FM[k](k=1, ..., g)表示方程组中对应第k个方程的系数矩阵, 假设
$ Qm=F\circ {{S}_{0}}=\left\{ \begin{array}{*{35}{l}} S_{0}^{T}\times FM[1]\times {{S}_{0}} \\ \vdots \\ S_{0}^{T}\times FM[g]\times {{S}_{0}} \\ \end{array} \right., $ |
其中, Qm为Q的系数矩阵, ×表示矩阵相乘,
Petzoldt等人在文献[15, 16]中指出:在给定可逆仿射变换S0和Q的情况下, Q和F的系数矩阵之间存在线性关系Qm=Fm×A(其中, 矩阵A是关于S0元素的一个矩阵).但是文献[15, 16]中没有给出具体的证明, 本文附录A将给出详细的说明.
公钥方程组为P=S3oFoS0=S3oQ, 公钥P的系数矩阵为可逆仿射变换S3与Q的系数矩阵的乘积:
$ Pm={{S}_{3}}\times Qm $ | (1) |
因此, 如果给定公钥方程组的系数矩阵以及可逆仿射变换S3和S0, 就可以通过下面的计算, 达到确定中心映射F的目的:
$ Qm=S_{3}^{-1}\times Pm, Fm=Qm\times {{A}^{-1}} $ | (2) |
首先, RGB公钥的每个多项式方程可以写成如下结构:
$ {{p}^{(k)}}({{x}_{1}}, ..., {{x}_{n}})=\sum\limits_{i=1}^{r}{\sum\limits_{j=i}^{n}{\alpha _{ij}^{(k)}{{x}_{i}}{{x}_{j}}}}+\sum\limits_{i=r+1}^{r+g}{\sum\limits_{j=i}^{n}{\beta _{ij}^{(k)}{{x}_{i}}{{x}_{j}}}}+\sum\limits_{i=r+g+1}^{n}{\sum\limits_{j=i}^{n}{\gamma _{ij}^{(k)}{{x}_{i}}{{x}_{j}}}}+ \\ \sum\limits_{i=1}^{n}{\eta _{i}^{(k)}{{x}_{r}}}+{{\lambda }^{(k)}}(k=1, ..., g), $ |
其中,
$ PM[k] = \left( {\begin{array}{*{20}{c}} {\alpha _{11}^{(k)}}&{\alpha _{12}^{(k)}}&{\alpha _{13}^{(k)}}&{\alpha _{14}^{(k)}}& \ldots &{\alpha _{1r}^{(k)}}&{\alpha _{1(r + 1)}^{(k)}}& \ldots &{\alpha _{1(r + g - 1)}^{(k)}}&{\alpha _{1(r + g)}^{(k)}}&{\alpha _{1(r + g + 1)}^{(k)}{}}& \ldots &{\alpha _{1n}^{(k)}}&{\eta _1^{(k)}}\\ 0&{\alpha _{22}^{(k)}}&{\alpha _{23}^{(k)}}&{\alpha _{24}^{(k)}}& \ldots &{\alpha _{2r}^{(k)}}&{\alpha _{2(r + 1)}^{(k)}}& \ldots &{\alpha _{2(r + g - 1)}^{(k)}}&{\alpha _{2(r + g)}^{(k)}}&{\alpha _{2(r + g + 1)}^{(k)}}& \ldots &{\alpha _{2n}^{(k)}}&{\eta _2^{(k)}}\\ 0&0&{\alpha _{33}^{(k)}}&{\alpha _{34}^{(k)}}& \ldots &{\alpha _{3r}^{(k)}}&{\alpha _{3(r + 1)}^{(k)}}& \ldots &{\alpha _{3(r + g - 1)}^{(k)}}&{{}\alpha _{3(r + g)}^{(k)}}&{\alpha _{3(r + g + 1)}^{(k)}}& \ldots &{\alpha _{3n}^{(k)}}&{\eta _3^{(k)}}\\ 0&0&0&{\alpha _{44}^{(k)}}& \ldots &{\alpha _{4r}^{(k)}}&{\alpha _{4(r + 1)}^{(k)}}& \ldots &{\alpha _{4(r + g - 1)}^{(k)}}&{\alpha _{4(r + g)}^{(k)}}&{\alpha _{4(r + g + 1)}^{(k)}}& \ldots &{\alpha _{4n}^{(k)}}&{\eta _4^{(k)}}\\ {}&{}& \vdots &{}& \ddots&\vdots &{}&{}&{}&{}&{}&{}& \vdots&\vdots \\ 0&0&0&0& \ldots &{\alpha _{rr}^{(k)}}&{\alpha _{r(r + 1)}^{(k)}}& \ldots &{\alpha _{r(r + g - 1)}^{(k)}}&{\alpha _{r(r + g)}^{(k)}}&{\alpha _{r(r + g + 1)}^{(k)}}& \ldots &{\alpha _{rn}^{(k)}{}}&{\eta _r^{(k)}}\\ 0&0&0&0& \ldots &0&{\beta _{(r + 1)(r + 1)}^{(k)}}& \ldots &{\beta _{(r + 1)(r + g - 1)}^{(k)}}&{\beta _{(r + 1)(r + g)}^{(k)}}&{\beta _{(r + 1)(r + g + 1)}^{(k)}}& \ldots &{\beta _{(r + 1)n}^{(k)}}&{\eta _{r + 1}^{(k)}}\\ {}&{}& \vdots &{}&{}&{}&{}&{}& \ddots &{}& \vdots &{}& \vdots&\vdots \\ 0&0&0&0& \ldots &0&0& \ldots &0&{\beta _{(r + g)(r + g)}^{(k)}}&{\beta _{(r + g)(r + g + 1)}^{(k)}}& \ldots &{\beta _{(r + g)n}^{(k)}}&{\eta _{r + g}^{(k)}}\\ 0&0&0&0& \ldots &0&0& \ldots &0&0&{\gamma _{(r + g + 1)(r + g + 1)}^{(k)}}& \ldots &{{}\gamma _{(r + g + 1)n}^{(k)}{}}&{\eta _{r + g + 1}^{(k)}}\\ {}&{}& \vdots &{}&{}&{}&{}&{}&{}&{}&{}& \ddots &{}& \vdots \\ 0&0&0&0& \ldots &0&0& \ldots &0&0&0& \ldots &{\gamma _{nn}^{(k)}}&{\eta _n^{(k)}}\\ 0&0&0&0& \ldots &0&0& \ldots &0&0&0& \ldots &0&{{\lambda ^{(k)}}} \end{array}} \right). $ |
消息M=(x1, ..., xr)和消息的签名为X=(xr+1, ..., xr+g, xr+g+1, …, xn), 定义由它们组成的扩展向量为
$ ver=\left( {{x}_{1}}, \ldots, {{x}_{r}}, {{x}_{r}}_{+1}, ..., {{x}_{r}}_{+g}, {{x}_{r}}_{+g+1}, \ldots, {{x}_{n}}, 1 \right). $ |
在验证RGB签名时, 可以用公钥方程的系数矩阵、扩展向量ver进行以下运算:
$ ver\cdot PM[k]\cdot ve{{r}^{T}}\overset{?}{\mathop{=}}\, 0(k=1, ..., g). $ |
如果采用上述形式对RGB方案进行签名验证, 我们就可以设计具有部分循环公钥的RGB多变量混合签名
方案.假设公钥方程P的系数矩阵表示为Pm=(V|U|W|C), Pm为
首先, 假设随机选择的向量v
$ V\left[k \right]={{D}^{k}}^{-1}\left( v \right), W\left[k \right]={{D}^{k}}^{-1}\left( w \right)\left( k=1, \ldots, g \right) $ | (3) |
其中,
在CyclicRGB中, 由于公钥方程中部分系数采用上述特殊结构生成, 使得CyclicRGB多变量公钥多项式方程组中相邻两个方程的系数存在特定关系, 具体如下:
$ \begin{matrix} \alpha _{ij}^{(k)}=\alpha _{i(j-1)}^{(k-1)}, i=1, ..., r, j=i+1, ..., n, k=2, ..., g, \\ \gamma _{ij}^{(k)}=\gamma _{i(j-1)}^{(k-1)}, i=r+g+1, ..., n, j=i+1, ..., n, k=2, ..., g. \\ \end{matrix} $ |
因此, 利用上述系数间的关系, 在验证消息签名时, RGB多变量公钥多项式方程中第k个方程的计算和第k-1个方程的计算存在以下关系:
$ \begin{align} &(ve{{r}_{1}}, ..., ve{{r}_{i}})\left( \begin{matrix} \alpha _{1j}^{(k)} \\ \alpha _{2j}^{(k)} \\ \vdots \\ \alpha _{ij}^{(k)} \\ \end{matrix} \right)=({{x}_{1}}, ..., {{x}_{i}})\left( \begin{matrix} \alpha _{1(j-1)}^{(k-1)} \\ \alpha _{2(j-1)}^{(k-1)} \\ \vdots \\ \alpha _{i(j-1)}^{(k-1)} \\ \end{matrix} \right)\rm{, }\begin{array}{*{35}{l}} i=1, ..., r \\ j=i+1, ...n \\ k=2, ..., g \\ \end{array}, \\ &(ve{{r}_{r+g+1}}, ..., ve{{r}_{r+g+i}})\left( \begin{matrix} \gamma _{(r+g+1)j}^{(k)} \\ \gamma _{(r+g+2)j}^{(k)} \\ \vdots \\ \gamma _{(r+g+i)j}^{(k)} \\ \end{matrix} \right)=({{x}_{r+g+1}}, ..., {{x}_{r+g+i}})\left( \begin{matrix} \gamma _{(r+g+1)(j-1)}^{(k-1)} \\ \gamma _{(r+g+2)(j-1)}^{(k-1)} \\ \vdots \\ \gamma _{(r+g+i)(j-1)}^{(k-1)} \\ \end{matrix} \right)\rm{, }\begin{array}{*{35}{l}} i=1, ..., b \\ j=i+1, ...n \\ k=2, ..., g \\ \end{array}. \\ \end{align} $ |
与此同时, 利用上述事实, 在给定消息值和签名值后, 我们可以设计CyclicRGB方案签名验证步骤来提高RGB多变量公钥签名的验证效率.下面给出验证签名算法.
1.首先, 将由消息值和签名值组成的扩展向量ver代入公钥方程组中的第1个多项式方程, 即计算ver×PM[1]×verT:先将扩展向量ver与第1个公钥方程的系数矩阵PM[1]相乘, 得到乘积ver·PM[1], 这部分的运算又可以具体地分为以下几部分的运算.
a) 我们假设用sumi表示ver与PM[1]中第i列相乘得到的结果, 那么ver分别与PM[1]中第n列、第n+1列相乘得到的结果分别为
$ \begin{matrix} su{{m}_{n}}=\sum\nolimits_{j=1}^{r}{\alpha _{jn}^{(1)}ve{{r}_{j}}}+\sum\nolimits_{j=r+1}^{r+g}{\beta _{jn}^{(1)}ve{{r}_{j}}}+\sum\nolimits_{j=r+g+1}^{n}{\gamma _{jn}^{(1)}ve{{r}_{j}}}, \\ su{{m}_{n+1}}=\sum\nolimits_{j=1}^{n}{\eta _{j}^{(1)}ve{{r}_{j}}}+{{\lambda }^{(1)}}. \\ \end{matrix} $ |
b) 将系数矩阵PM[1]中由特殊向量v, w生成的系数与扩展向量ver对应元素进行运算, 并保存运算结果.
首先, 系数矩阵PM[1]的第i列(1≤i≤n-1)的前r行元素分别与ver对应元素进行运算, 假设运算结果用col1i进行保存:
$ col{{1}_{i}}=\sum\nolimits_{j=1}^{\min (i, r)}{\alpha _{ji}^{(1)}ve{{r}_{j}}}. $ |
将这部分运算结果用col1i进行保存, 目的是利用第2个公钥方程系数矩阵中的系数
将系数矩阵PM[1]的第i列(r+g+1≤i≤n-1)中的第j行(r+g+1≤j≤i)元素分别与ver对应元素进行运算, 假设运算结果用col2i进行保存:
$ col{{2}_{i}}=\sum\nolimits_{j=r+g+1}^{i}{\gamma _{ji}^{(1)}ve{{r}_{j}}}. $ |
与保存col1i的目的类似, 保存第1个公钥方程在签名验证时的部分中间计算结果col2i, 也主要是利用第2个公钥方程的系数矩阵中的系数
c) 结合步骤b)中的计算结果, 求ver分别与系数矩阵PM[1]的前n-1列相乘得到的结果, 并将运算结果保存在sumi中.那么有:
● ver与系数矩阵PM[1]的第i列(其中, 1≤i≤r)运算结果:sumi=col1i;
●
ver与系数矩阵PM[1]的第i列(其中r+1≤i≤r+g)运算结果:
●
ver与系数矩阵PM[1]的第i列(其中, r+g+1≤i≤n-1)运算结果:
将上述步骤中的计算结果sumi(i=1, ..., n+1)与扩展向量ver的转置相乘, 得到消息值、签名值代入第1个公钥方程的计算结果h1:
$ {{h}_{1}}=ver\cdot PM[1]\cdot ve{{r}^{T}}=\sum\nolimits_{j=1}^{n+1}{su{{m}_{j}}ve{{r}_{j}}}. $ |
2.这一步中, 将消息和签名的扩展向量ver代入公钥方程组的其他多项式方程中进行计算.下面说明将ver代入第f(2≤f≤g)个公钥方程的计算流程.
a) 由于PM[f]中第n+1列不具有特殊结构, ver与第n+1列相乘的运算与步骤1中相同, 均为
$ su{{m}_{n+1}}=\sum\nolimits_{j=1}^{n}{\eta _{j}^{(f)}ve{{r}_{j}}}+{{\lambda }^{(f)}}. $ |
对于PM[f]中第n列, 有
$ \begin{matrix} (ve{{r}_{1}}, ..., ve{{r}_{r}})\left( \begin{matrix} \alpha _{1n}^{(f)} \\ \vdots \\ \alpha _{rn}^{(f)} \\ \end{matrix} \right)=(ve{{r}_{1}}, ..., ve{{r}_{r}})\left( \begin{matrix} \alpha _{1(n-1)}^{(f-1)} \\ \vdots \\ \alpha _{r(n-1)}^{(f-1)} \\ \end{matrix} \right)=col{{1}_{n-1}}, \\ (ve{{r}_{r+g+1}}, ..., ve{{r}_{n-1}})\left( \begin{matrix} \gamma _{(r+g+1)n}^{(f)} \\ \vdots \\ \gamma _{(n-1)n}^{(f)} \\ \end{matrix} \right)=(ve{{r}_{r+g+1}}, ..., ve{{r}_{n-1}})\left( \begin{matrix} \gamma _{(r+g+1)(n-1)}^{(f-1)} \\ \vdots \\ \gamma _{(n-1)(n-1)}^{(f-1)} \\ \end{matrix} \right)=col{{2}_{n-1}}, \\ su{{m}_{n}}=col{{1}_{n-1}}+\sum\nolimits_{j=r+1}^{r+g}{\beta _{jn}^{(f)}ve{{r}_{j}}}+col{{2}_{n-1}}+\gamma _{nn}^{(f)}ve{{r}_{n}}. \\ \end{matrix} $ |
b) 计算第f个公钥方程系数矩阵PM[f]中前n-1列与扩展向量ver相乘的结果.在计算的过程中, 利用上一个公钥方程计算时保存的结果col1i, col2i.同时, 对col1i, col2i的值进行更新.
具体地, 首先, 依次从第n-1列到第r+g+2列进行计算, 同样与步骤a)中类似, 由于公钥方程系数的特殊结构, 可以得到以下方程:
$ \begin{matrix} col{{1}_{i}}=col{{1}_{i-1}}, \\ col{{2}_{i}}=col{{2}_{i-1}}+\gamma _{ii}^{(f)}ve{{r}_{i}}, \\ su{{m}_{i}}=col{{1}_{i}}+col{{2}_{i}}+\sum\nolimits_{j=r+1}^{r+g}{\beta _{ji}^{(f)}ve{{r}_{j}}}(i=r+g+2, ..., n-1). \\ \end{matrix} $ |
对于第r+g+1列, col2r+g+1需进行新的计算求得
接下来, 将第r+g列~第r+1列分别与扩展向量ver相乘:
$ \begin{matrix} col{{1}_{i}}=col{{1}_{i-1}}, \\ su{{m}_{i}}=col{{1}_{i}}+\sum\nolimits_{j=r+1}^{i}{\beta _{ji}^{(f)}ve{{r}_{j}}}(i=r+1, ..., r+g). \\ \end{matrix} $ |
将第r列到第2列分别与扩展向量ver相乘, 有:
$ \begin{matrix} col{{1}_{i}}=col{{1}_{i-1}}+\alpha _{ii}^{(f)}ve{{r}_{i}}, \\ su{{m}_{i}}=col{{1}_{i}}(i=2, ..., r). \\ \end{matrix} $ |
最后, 对于第1列的计算有:
$ \begin{align} &col{{1}_{1}}=\alpha _{11}^{(f)}ve{{r}_{1}}, \\ &su{{m}_{1}}=col{{1}_{1}}. \\ \end{align} $ |
将上述步骤中计算结果sumi(i=1, ..., n+1)与扩展向量ver的转置相乘, 得到消息值、签名值代入第f个公钥方程的计算结果:
$ {{h}_{f}}=ver\cdot PM[f]\cdot ve{{r}^{T}}=\sum\nolimits_{j=1}^{n+1}{su{{m}_{j}}ve{{r}_{j}}}. $ |
3.最后, 验证这g个计算结果:
$ {{h}_{f}}=0, \forall f\in \left\{ 1, \ldots, g \right\}. $ |
如果上式成立, 则签名有效; 否则, 签名无效.
附录B的算法B1给出签名验证的伪代码, 对应上述验证流程.
2.3 CyclicRGB混合多变量签名方案在具体分析了CyclicRGB的签名验证之后, 我们就可以设计CyclicRGB混合多变量签名方案.CyclicRGB混合多变量签名方案由3种多项式时间算法组成, 分别为密钥生成算法、签名生成算法和签名验证算法.
密钥生成算法. (Key Generation):(pk, sk)
输入:安全参数λ.
输出:用户的公钥pk、私钥sk.
RGB公钥方程组中的每个方程的系数矩阵以及中心映射F的每个方程的系数矩阵都可以表示为(n+1)× (n+1)的上三角矩阵形式, 均为第2.2节中PM[k]矩阵表示形式.不同的是, 在中心映射F的每一个方程的系数矩阵中, 表示Green变量与Green变量乘积的二次项系数全部为0;相反地, 对应的公钥方程的系数矩阵中, 表示Green变量与Green变量乘积的二次项系数需要由私钥求得.
在密钥生成过程中, 首先生成公钥方程组系数矩阵中的二次项系数部分, 利用公钥方程组的系数矩阵与中心映射的系数矩阵的线性关系, 求得中心映射系数矩阵的二次项系数.当中心映射系数矩阵的二次项系数确定以后, 再为中心映射F随机选取一次项系数和常数项系数.最后, 由中心映射F和可逆仿射变换S0, S3确定最终公钥方程.具体密钥生成过程如下.
1. 随机选择两个向量v
2. 使用v, w, 按照公式(3)循环右移生成每个公钥方程系数矩阵中对应的二次项系数.即生成公钥系数矩阵Pm=(V|U|W|C)中的矩阵V和W.
3. 公钥系数矩阵中除了V和W表示二次项系数之外, U也表示二次项系数, 并且U表示Green变量分别与Green变量、Blue变量构成的二次项乘积的系数矩阵.对于这一部分系数, 我们将U中表示Green变量与Green变量组成的二次项的系数全部设置为0.公钥系数矩阵中的这一部分值最终由中心映射的一次项系数和常数项系数确定以后求得.
4. 另外, 为U中表示Green变量与Blue变量组成的二次项的系数随机选取值.
5. 通过上述步骤, 可以确定公钥方程组中二次项的系数, 即V, U, W.根据公钥方程组的系数矩阵与中心映射系数矩阵的线性关系, 通过公式(2)可以得到中心映射F的二次项系数.
6. 随机选择中心映射F的一次项系数以及常数项系数, 根据P=S3oFoS0求得公钥方程的系数矩阵Pm=
(V|U|W|C).CyclicRGB方案的公钥为pk=(v, U, w, C), 私钥sk=(S1, S2, S3, F).
7. 输出密钥对(pk, sk).
签名生成算法. (Signature Generation):X
该算法由签名者执行, 签名者根据自己的私钥(S1, S2, F)、消息值M=(x1, ..., xr).生成相应的消息签名X
1.计算
2.随机选择Blue变量
$ \left\{ \begin{array}{*{35}{l}} {{f}^{(1)}}({{{{x}'}}_{1}}, ..., {{{{x}'}}_{r}}, {{{{x}'}}_{r+1}}, ..., {{{{x}'}}_{r+g}}, {{{{x}'}}_{r+g+1}}, ..., {{{{x}'}}_{n}})=0 \\ \vdots \\ {{f}^{(g)}}({{{{x}'}}_{1}}, ..., {{{{x}'}}_{r}}, {{{{x}'}}_{r+1}}, ..., {{{{x}'}}_{r+g}}, {{{{x}'}}_{r+g+1}}, ..., {{{{x}'}}_{n}})=0 \\ \end{array} \right.. $ |
如果上述线性方程组无解, 则重复步骤(2)中的运算过程, 即重新选择Blue变量的值进行运算, 直到可以求出g个变量
3.将步骤2中随机选择的Blue变量
$ X=S_{2}^{-1}({X}')=S_{2}^{-1}({{{x}'}_{r+1}}, ..., {{{x}'}_{r+g}}, {{{x}'}_{r+g+1}}, ..., {{{x}'}_{n}})=({{x}_{r+1}}, ..., {{x}_{r+g}}, {{x}_{r+g+1}}, ..., {{x}_{n}}). $ |
最后, 运算结果X即对消息M的签名.
签名验证算法. (Signature Verification):{ACCEPT,
该算法由验证者执行, 来验证消息签名是否有效.
输入:验证者的公钥pk, 消息值M以及消息的签名X.
输出:如果签名有效, 返回ACCEPT; 否则签名无效, 返回
为了验证X=(xr+1, ..., xr+g, xr+g+1, …, xn)
$ pk\left( M, X \right)=pk\left( {{x}_{1}}, \ldots, {{x}_{r}}, {{x}_{r}}_{+1}, ..., {{x}_{r}}_{+g}, {{x}_{r}}_{+g+1}, \ldots, {{x}_{n}} \right)=0. $ |
若采用算法B1的验证结果为“ACCEPT”, 则消息签名合法, 算法返回1;否则, 消息的签名不合法, 算法返回
CyclicRGB混合签名方案的正确性可以通过下式加以证明.
$ \begin{align} &pk(M, X)=0\Leftrightarrow {{S}_{3}}\circ F\circ {{S}_{0}}(M, X)=0 \\ &\rm{ }\Leftrightarrow F({{S}_{1}}(M), {{S}_{2}}(X))=0 \\ &\rm{ }\Leftrightarrow F(\tilde{M}, {{S}_{2}}\circ S_{2}^{-1}({X}'))=0 \\ &\rm{ }\Leftrightarrow F(\tilde{M}, {X}')=0 \\ &\rm{ }\Leftrightarrow F({{{{x}'}}_{1}}, ..., {{{{x}'}}_{r}}, {{{{x}'}}_{r+1}}, ..., {{{{x}'}}_{r+g}}, {{{{x}'}}_{r+g+1}}, ..., {{{{x}'}}_{n}})=0. \\ \end{align} $ |
如果消息值和签名值合法, 上式一定成立.
3 安全性分析及参数的选择目前, 针对多变量公钥密码方案存在大量的攻击方法.这些攻击方法包括有强力搜索、直接攻击、最小秩攻击、高秩攻击、Patarin线性关系(线性化方程攻击)、差分攻击、分离“油”“醋”变量攻击、Rainbow Band Seperation攻击等.下面就CyclicRGB方案的安全性进行分析.
由于原始的RGB方案是UOV方案的改进, 本文方案CyclicRGB基于原始的RGB方案进行改进, 在降低RGB方案的公钥大小的同时, 提高签名验证效率.原始RGB方案与本文CyclicRGB方案都不是多层次结构的方案, 这就使得作用于Rainbow, CyclicRainbow等多层次复杂结构方案的攻击方法不能用来攻击RGB, CyclicRGB方案.这些攻击方法包括秩攻击、Rainbow Band Separation等攻击.
本文主要采用循环公钥的方法来降低RGB多变量混合签名方案的公钥量.与原方案RGB相比, 改进后的方案并没有降低原方案的安全性, 因此, 不能作用于RGB方案的攻击方法也不能作用于CyclicRGB方案.同时, 新方案的安全性也和RGB方案一样, 可以通过选择合适的参数来抵抗代数攻击.
3.1 穷举攻击穷举攻击可以作用于任何的密码方案.穷举攻击的方式有两种:一种是穷举密钥空间, 通过找到一个等价密钥确定该方法是否可行, 这种攻击方法的时间复杂度较高; 另一种是对明文直接攻击, 通过找到有效的明文的概率来确定这种穷举攻击方法是否可行.明文长度大于64比特的方案可以抵抗对明文的穷举攻击.因此, 当有限域选择GF(28)时, 在CyclicRGB中表示Red变量的个数r, 当r≥8时, 方案可以抵抗穷举攻击.
3.2 分离油、醋变量的攻击分离油醋攻击是Kipnis等人[19]在1998年对OV体制进行攻击时提出的攻击方法.文献[6]中指出:当醋变量个数多余油变量个数或者两者个数近似相等时, 油醋分离攻击方法的时间复杂度为q(v-o)-1×o4(其中, v, o分别为OV体制中醋变量的个数和油变量的个数).RGB, CyclicRGB多变量混合签名方案实质上是对UOV签名方案的改进, 前两者的中心映射结构与UOV方案相同.当将RGB, CyclicRGB方案中心映射中的Red变量和Blue变量看作醋变量、Green变量看作油变量时, 分离油醋攻击方法对于CyclicRGB方案的攻击复杂度为qr+b-g-1×o4.当有限域选择GF(28)时, 只要r+g-b≥14, CyclicRGB的安全级别就将大于2100.
3.3 Patarin线性关系攻击Patarin线性关系攻击最初是针对MI多变量公钥密码方案提出的, Patarin线性攻击方法是对公钥多项式方程进行等价变形, 试图使用足够多的明文和密文对得到关于明文变量和密文变量(或者公钥多项式)间的线性关系, 最后, 攻击者利用这个线性关系达到攻破方案的目的.但是文献[18]中指出, RGB方案的中心映射不是双射的.因此, 线性化方程的攻击方法不使用RGB; 同理, Patarin线性攻击也不适用于CyclicRGB.
4 CyclicRGB与RGB公钥大小及签名验证效率的比较RGB混合多变量签名方案的公钥大小为
$ g\frac{(n+1)(n+2)}{2}=g\times \frac{r(n+g+b+1)}{2}+g\times \frac{g(2b+g+1)}{2}+g\times \frac{b(b+1)}{2}+g\times (n+1) $ | (4) |
CyclicRGB混合多变量签名方案的公钥由向量v, w和矩阵U, C构成, 因此, CyclicRGB混合多变量签名方案的公钥大小为
$ \frac{r(n+g+b+1)}{2}+\frac{b(b+1)}{2}+g\left[\frac{g(2b+g+1)}{2}+n+1 \right]=\frac{r(n+g+b+1)}{2}+g\times \frac{g(2b+g+1)}{2}+\frac{b(b+1)}{2}+g\times (n+1) $ | (5) |
用公式(4)减去公式(5)得到
文献[18]对RGB方案各部分的时间复杂度进行了分析(包括公钥、私钥的生成, 签名的生成和验证), 其中包括有限域上的模加法和模乘法运算.但是, 有限域上模乘运算的时间复杂度高于有限域上模加法运算的时间复杂度, 因此, 下面我们主要分析算法中有限域上模乘运算的复杂度.CyclicRGB验证签名效率的提高主要通过第2.2节中签名验证算法得以体现, 附录B中算法B1即为CyclicRGB签名验证的伪代码.下面我们就附录B中算法B1伪代码中用到的模乘运算的个数进行分析.
● 算法B1第1行~第3行需要执行的模乘运算为
● 第4行~第6行需要执行的模乘运算为
● 第11行执行完第7行的循环体需要执行的模乘运算数为
● 第13行执行完第7行的循环体需要执行的模乘运算数为g(b-1);
● 第15行需要执行的模乘运算数为n;
● 第16行需要执行的模乘运算数为n;
● 第17行需要执行的模乘运算数为n+1;
● 从算法B1的第18行开始的循环语句:
➢ 第19行需要执行的模乘运算数为n;
➢ 第20行需要执行的模乘运算数为g+1;
➢ 执行第21行的for循环中, 第23行需要执行的模乘运算数为(b-2);
➢ 执行第21行的for循环中, 第24行需要执行的模乘运算数为g(b-2);
➢ 第27行需要执行的模乘运算数为1;
➢ 第28行需要执行的模乘运算数为g;
➢ 执行第29行的for循环中, 第31行总共执行的模乘运算数为
➢ 执行第33行的for循环中, 第34行总共执行的模乘运算数为r-1;
➢ 第37行需要执行的模乘运算数为1;
➢ 第39行需要执行的模乘运算数为n+1.
因此, CyclicRGB混合多变量签名方案的签名验证总共需要执行模乘运算为
$ \frac{n(n+5)}{2}+1+(g-1)\left[\frac{(2b+g)(g+1)}{2}+r+2n+1 \right]; $ |
RGB混合签名方案在签名验证时所需要执行的模乘运算数为
$ \frac{n(n+1)}{2}+g\times \frac{(n+1)(n+2)-2}{2}. $ |
如果有限域K选取GF(28), 并且选择参数(r, g, b)=(20, 24, 10), CyclicRGB混合多变量签名方案在签名验证时所需要的模乘运算仅为RGB签名方案模乘运算的45%.可以看出:CyclicRGB方案比RGB方案签名验证时需要执行的模乘运算数少, 验证签名时效率较高.
5 实验为了验证CyclicRGB签名方案的效率, 我们使用C++对RGB签名方案和CyclicRGB方案在两组参数情况下进行实现.实验结果见表 1.
实验对两种方案公钥大小、签名验证所消耗时间以及签名验证进行的有限域上的主要模运算时间进行统计.需要说明的是, 其中, CyclicRGB签名验证时间为两部分:括号中的时间主要为签密验证过程中有限域上模运算的总时间; 括号外的时间为整个签名验证的时间, 这个时间不仅包括签名验证过程中有限域上模运算的时间, 还包括使用循环公钥恢复公钥方程对应系数矩阵的时间.在参数相同的情况下, RGB与CyclicRGB所采用的消息、消息的长度以及得到的签名长度都是相同的.例如, 在参数取有限域GF(28), r=20, g=24, b=10的实验中, 消息的大小均为20B, 对消息的签名的大小也均为34B.不同的是, 在参数相同的情况下, 我们可以看到, CyclicRGB签名方案的验证效率高于RGB签名方案的验证效率.CyclicRGB方案与RGB方案相比, 采用部分循环公钥的方法来设计公钥时, CyclicRGB方案在签名验证时所需时间约为RGB方案签名验证时间的60%, 本文方案可以达到提高后者签名验证效率的目的.同时, CyclicRGB方案的公钥大小不超过RGB方案公钥大小的40%, 达到了降低公钥大小的目的.
6 结论在本文中, 我们采用循环公钥的方法对RGB方案进行改进, 设计了新的混合多变量签名方案——CyclicRGB方案, 并且具体设计了CyclicRGB签名验证算法.新的混合多变量签名方案在签名验证时所需要的时间为原始的RGB方案签名验证消耗时间的60%, 新方案的公钥大小也仅为RGB方案的40%.我们也采用C++对有限域GF(28)上不同参数情况下的两种方案的签名效率进行了实验比较.实验结果表明:CyclicRGB的签名方案在验证签名时, 可以在很大程度上提高签名验证的效率.
附录A下面证明:在已知多变量二次多项式方程Q和可逆仿射变换S0的情况下, Q和F的系数矩阵之间存在线性关系.由本文第2节可知,
$ Qm=F\circ {{S}_{0}}=\left\{ \begin{array}{*{35}{l}} S_{0}^{T}\times FM[1]\times {{S}_{0}} \\ \vdots \\ S_{0}^{T}\times FM[g]\times {{S}_{0}} \\ \end{array} \right., Q=F\circ {{S}_{0}}. $ |
这里假设
$ \begin{align} &QM[k]=\left( \begin{matrix} q_{11}^{(k)}, q_{12}^{(k)}, ..., q_{1n}^{(k)} \\ q_{21}^{(k)}, q_{22}^{(k)}, ..., q_{2n}^{(k)} \\ \vdots \\ q_{n1}^{(k)}, q_{n2}^{(k)}, ..., q_{nn}^{(k)} \\ \end{matrix} \right) \\ &={{\left( \begin{matrix} {{s}_{11}}, {{s}_{12}}, ..., {{s}_{1n}} \\ {{s}_{21}}, {{s}_{22}}, ..., {{s}_{2n}} \\ \vdots \\ {{s}_{n1}}, {{s}_{n2}}, ..., {{s}_{nn}} \\ \end{matrix} \right)}^{T}}\times \left( \begin{matrix} f_{11}^{(k)}, f_{12}^{(k)}, ..., f_{1n}^{(k)} \\ f_{21}^{(k)}, f_{22}^{(k)}, ..., f_{2n}^{(k)} \\ \vdots \\ f_{n1}^{(k)}, f_{n2}^{(k)}, ..., f_{nn}^{(k)} \\ \end{matrix} \right)\times \left( \begin{matrix} {{s}_{11}}, {{s}_{12}}, ..., {{s}_{1n}} \\ {{s}_{21}}, {{s}_{22}}, ..., {{s}_{2n}} \\ \vdots \\ {{s}_{n1}}, {{s}_{n2}}, ..., {{s}_{nn}} \\ \end{matrix} \right) \\ &=\left( \begin{matrix} {{s}_{11}}, {{s}_{21}}, ..., {{s}_{n1}} \\ {{s}_{12}}, {{s}_{22}}, ..., {{s}_{n2}} \\ \vdots \\ {{s}_{1n}}, {{s}_{2n}}, ..., {{s}_{nn}} \\ \end{matrix} \right)\times \left( \begin{matrix} f_{11}^{(k)}, f_{12}^{(k)}, ..., f_{1n}^{(k)} \\ f_{21}^{(k)}, f_{22}^{(k)}, ..., f_{2n}^{(k)} \\ \vdots \\ f_{n1}^{(k)}, f_{n2}^{(k)}, ..., f_{nn}^{(k)} \\ \end{matrix} \right)\times \left( \begin{matrix} {{s}_{11}}, {{s}_{12}}, ..., {{s}_{1n}} \\ {{s}_{21}}, {{s}_{22}}, ..., {{s}_{2n}} \\ \vdots \\ {{s}_{n1}}, {{s}_{n2}}, ..., {{s}_{nn}} \\ \end{matrix} \right). \\ \end{align} $ |
那么,
$ \begin{align} &q_{ij}^{(k)}=({{s}_{1i}}, {{s}_{2i}}, ..., {{s}_{ni}})\times \left( \begin{matrix} f_{11}^{(k)}, f_{12}^{(k)}, ..., f_{1n}^{(k)} \\ f_{21}^{(k)}, f_{22}^{(k)}, ..., f_{2n}^{(k)} \\ \vdots \\ f_{n1}^{(k)}, f_{n2}^{(k)}, ..., f_{nn}^{(k)} \\ \end{matrix} \right)\times \left( \begin{matrix} {{s}_{1j}} \\ {{s}_{2j}} \\ \vdots \\ {{s}_{nj}} \\ \end{matrix} \right) \\ &={{\left( \begin{matrix} {{s}_{1i}}f_{11}^{(k)}+{{s}_{2i}}f_{21}^{(k)}+...+{{s}_{ni}}f_{n1}^{(k)} \\ {{s}_{1i}}f_{12}^{(k)}+{{s}_{2i}}f_{22}^{(k)}+...+{{s}_{ni}}f_{n2}^{(k)} \\ \vdots \\ {{s}_{1i}}f_{1n}^{(k)}+{{s}_{2i}}f_{2n}^{(k)}+...+{{s}_{ni}}f_{nn}^{(k)} \\ \end{matrix} \right)}^{T}}\times \left( \begin{matrix} {{s}_{1j}} \\ {{s}_{2j}} \\ \vdots \\ {{s}_{nj}} \\ \end{matrix} \right) \\ &=({{s}_{1i}}{{s}_{1j}}f_{11}^{(k)}+{{s}_{2i}}{{s}_{1j}}f_{21}^{(k)}+...+{{s}_{ni}}{{s}_{1j}}f_{n1}^{(k)})+({{s}_{1i}}{{s}_{2j}}f_{12}^{(k)}+{{s}_{2i}}{{s}_{2j}}f_{22}^{(k)}+...+{{s}_{ni}}{{s}_{2j}}f_{n2}^{(k)})+...+ \\ &({{s}_{1i}}{{s}_{nj}}f_{1n}^{(k)}+{{s}_{2i}}{{s}_{nj}}f_{2n}^{(k)}+...+{{s}_{ni}}{{s}_{nj}}f_{nn}^{(k)}) \\ &=\sum\limits_{r=1}^{n}{\sum\limits_{c=1}^{n}{{{s}_{ri}}{{s}_{cj}}f_{rc}^{(k)}}} \\ &=(f_{11}^{(k)}, ..., f_{1n}^{(k)}, f_{21}^{(k)}, ..., f_{2n}^{(k)}, ..., f_{n1}^{(k)}, ..., f_{nn}^{(k)})\times {{({{s}_{1i}}{{s}_{1j}}, ..., {{s}_{1i}}{{s}_{nj}}, {{s}_{2i}}{{s}_{1j}}, ..., {{s}_{2i}}{{s}_{nj}}, ..., {{s}_{ni}}{{s}_{1j}}, ..., {{s}_{ni}}{{s}_{nj}})}^{T}}. \\ \end{align} $ |
因此, 可以得到如下关系:
$ \begin{align} &Qm=\left( \begin{matrix} q_{11}^{(1)}q_{12}^{(1)}...q_{1n}^{(1)}q_{21}^{(1)}...q_{2n}^{(1)}...q_{n1}^{(1)}...q_{nn}^{(1)} \\ \vdots \\ q_{11}^{(k)}q_{12}^{(k)}...q_{1n}^{(k)}q_{21}^{(k)}...q_{2n}^{(k)}...q_{n1}^{(k)}...q_{nn}^{(k)} \\ \end{matrix} \right) \\ &=\left( \begin{matrix} f_{11}^{(1)}f_{12}^{(1)}...f_{1n}^{(1)}f_{21}^{(1)}...f_{2n}^{(1)}...f_{n1}^{(1)}...f_{nn}^{(1)} \\ \vdots \\ f_{11}^{(k)}f_{12}^{(k)}...f_{1n}^{(k)}f_{21}^{(k)}...f_{2n}^{(k)}...f_{n1}^{(k)}...f_{nn}^{(k)} \\ \end{matrix} \right)\times \left( \begin{matrix} \begin{matrix} {{s}_{11}}{{s}_{11}}{{s}_{11}}{{s}_{12}}\cdots {{s}_{11}}{{s}_{1n}}{{s}_{12}}{{s}_{11}}\cdots {{s}_{12}}{{s}_{1n}}\cdots {{s}_{1n}}{{s}_{11}}\cdots {{s}_{1n}}{{s}_{1n}} \\ \vdots \vdots \vdots \vdots \vdots \vdots \vdots \rm{ } \\ \end{matrix} \\ \begin{matrix} {{s}_{11}}{{s}_{n1}}{{s}_{11}}{{s}_{n2}}\cdots {{s}_{11}}{{s}_{nn}}{{s}_{12}}{{s}_{n1}}\cdots {{s}_{12}}{{s}_{nn}}\cdots {{s}_{1n}}{{s}_{n1}}\cdots {{s}_{1n}}{{s}_{nn}} \\ {{s}_{21}}{{s}_{11}}{{s}_{21}}{{s}_{12}}\cdots {{s}_{21}}{{s}_{1n}}{{s}_{22}}{{s}_{11}}\cdots {{s}_{22}}{{s}_{1n}}\cdots {{s}_{2n}}{{s}_{11}}\cdots {{s}_{2n}}{{s}_{1n}} \\ \begin{matrix} \vdots \vdots \vdots \vdots \vdots \vdots \vdots \\ {{s}_{21}}{{s}_{n1}}{{s}_{21}}{{s}_{n2}}\cdots {{s}_{21}}{{s}_{nn}}{{s}_{22}}{{s}_{n1}}\cdots {{s}_{22}}{{s}_{nn}}\cdots {{s}_{2n}}{{s}_{n1}}\cdots {{s}_{2n}}{{s}_{nn}} \\ {{s}_{n1}}{{s}_{11}}{{s}_{n1}}{{s}_{12}}\cdots {{s}_{n1}}{{s}_{1n}}{{s}_{n2}}{{s}_{11}}\cdots {{s}_{n2}}{{s}_{1n}}\cdots {{s}_{nn}}{{s}_{11}}\cdots {{s}_{nn}}{{s}_{1n}} \\ \begin{matrix} \vdots \vdots \vdots \vdots \vdots \vdots \vdots \\ {{s}_{n1}}{{s}_{n1}}{{s}_{n1}}{{s}_{n2}}\cdots {{s}_{n1}}{{s}_{nn}}{{s}_{n2}}{{s}_{n1}}\cdots {{s}_{n2}}{{s}_{nn}}\cdots {{s}_{nn}}{{s}_{n1}}\cdots {{s}_{nn}}{{s}_{nn}} \\ \end{matrix} \\ \end{matrix} \\ \end{matrix} \\ \end{matrix} \right) \\ &=Fm\times A. \\ \end{align} $ |
多变量多项式方程组Q的系数矩阵和F的系数矩阵之间存在线性关系, 即Qm=Fm×A.这里, A为关于S0的元素的矩阵.
附录B● CyclicRGB签名验证算法
算法B1. CyclicRGB签名的验证.
1. for i=1 to n-1 //将扩展向量ver代入公钥方程组中第1个多项式方程计算
2.
3. end for
4. for i=r+g+1 to n-1
5.
6. end for
7. for i=1 to n-1
8. if i≤r
9. sumi=col1i
10. else if i≤r+g
11.
12. else
13.
14. end for
15.
16.
17.
18. for f=2 to g //将消息和签名的扩展向量ver代入公钥方程组中其余多项式方程计算
19.
20.
21. for i=n-1 to r+g+2
22. col1i=col1i-1
23.
24.
25. end for
26. col1r+g+1=col1r+g
27.
28.
29. for i=r+g to r+1
30. col1i=col1i-1
31.
32. end for
33. for i=r to 2
34.
35.
36. end for
37.
38. sum1=col11
39.
40. end for
41. if hf=0, ∀f
42. return “ACCEPT”
43. else
44. return “
45. end if
● 算法B1的工作流程
算法B1是将消息和签名构成的扩展向量ver代入循环结构公钥方程组的每个方程中进行计算的过程.其中, 第1行~第17行是将ver代入公钥方程组中第1个方程的运算过程, 即ver×Pm[1]×verT.sum保存ver×Pm[1]的计算结果.同时, 由于公钥方程组中方程系数矩阵PM[k]的α, γ部分分别由向量v, w循环右移生成, 因此在计算的过程中, 将这部分的计算结果保存在col1i, col2i中, 用于下一步ver×Pm[2]的计算.算法的第18行~第40行是将ver代入剩下的g-1个方程进行验证的过程.例如, 当f=2时, 对多变量公钥方程组中的第2个方程进行计算.在这一步计算过程中, 我们利用了上一步计算结果的col1i, col2i, 这样就可以节省一些模乘运算, 提高验证效率.计算过程中, 根据现有公钥方程系数矩阵对col1i, col2i值进行更新, 目的是用于下一个多项式方程的计算.CyclicRGB方案的签名验证就是通过这些值在第2个~第g个公钥方程计算的过程中的重复利用来降低签名验证的计算代价, 从而提高了签名验证效率.对于f=2, 算法第18行~第38行对应ver×Pm[2]的计算.第39行为公钥方程组中第2个方程的计算结果ver×Pm[2]×verT.当f=2到f=g循环全部结束时, CyclicRGB验证签名的计算结束.最后, 第41行~第45行判断签名的有效性, 并返回判断结果.
[1] |
Shor PW. Polynomial-Time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, 1999, 41(2): 303–332.
[doi:10.1137/S0036144598347011] |
[2] |
Matsumoto T, Imai H. Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In: Günther CG, ed. Proc. of the Workshop on the Theory and Application of of Cryptographic Techniques. Davos: Springer-Verlag, 1988. 419-453. [doi: 10.1007/3-540-45961-8_39] |
[3] |
Partarin J. Hidden field equations (HFE) and isomorphism of polynomial (IP): Two new families of asymmetric algorithms. In: Maurer U, ed. Proc. of the Advances in Cryptology-EUROCRYPT'96. LNCS 1070, Berlin, Heidelberg: Springer-Verlag, 1996. 33-48. [doi: 10.1007/3-540-68339-9_4] |
[4] |
Kipnis A, Shamir A. Cryptanalysis of the HFE public key cryptosystem by relinearization. In: Wiener M, ed. Proc. of the Advances in Cryptology-CRYPTO'99. Springer-Verlag, 1999. 19-30. [doi: 10.1007/3-540-48405-1_2] |
[5] |
Ding J, Gower JE, Schmidt DS. Oil-Vinegar signature schemes. In: Ding J, Gower JE, Schmidt DS, eds. Proc. of the Multivariate Public Key Cryptosystems, Vol. 25. Springer-Verlag, 2006. 63-97. [doi: 10.1007/978-0-387-36946-4_3] |
[6] |
Kipnis A, Patarin J, Goubin L. Unbalanced oil and vinegar signature schemes. In: Stern J, ed. Proc. of the Int'l Conf. on the Theory and Applications of Cryptographic Techniques. Prague: Springer-Verlag, 1999. 206-222. [doi: 10.1007/3-540-48910-X_15] |
[7] |
Patarin J, Courtois N, Goubin L. Flash, a fast multivariate signature algorithm. In: Naccache D, ed. Proc. of the Cryptographers' Track at the RSA Conf. San Francisco: Springer-Verlag. 2001. 298-307. [doi: 10.1007/3-540-45353-9_22] |
[8] |
Ding J, Schmidt D. Rainbow, a new multivariable polynomial signature scheme. In: Ioannidis J, ed. Proc. of the Int'l Conf. on Applied Cryptography and Network Security. New York: Springer-Verlag, 2005. 164-175. [doi: 10.1007/11496137_12] |
[9] |
Ding J. A new variant of the Matsumoto-Imai cryptosystem through perturbation. In: Bao F, ed. Proc. of the Int'l Workshop on Public Key Cryptography. Singapore: Springer-Verlag, 2004. 305-318. [doi: 10.1007/978-3-540-24632-9_22] |
[10] |
Ding J, Gower JE. Inoculating multivariate schemes against differential attacks. In: Yung M, ed. Proc. of the Int'l Workshop on Public Key Cryptography. New York: Springer-Verlag, 2006. 290-301. [doi: 10.1007/11745853_19] |
[11] |
Porras J, Baena J, Ding J. ZHFE, a new multivariate public key encryption scheme. In: Mosca M, ed. Proc. of the Int'l Workshop on Post-Quantum Cryptography. Waterloo: Springer Int'l Publishing, 2014. 229-245. [doi: 10.1007/978-3-319-11659-4_14] |
[12] |
Tao C, Diene A, Tang S, Ding J. Simple matrix scheme for encryption. Lecture Notes in Computer Science, 2013, 7932: 231–242.
[doi:10.1007/978-3-642-38616-9] |
[13] |
Ding J, Petzoldt A, Wang L. The cubic simple matrix encryption scheme. In: Mosca M, ed. Proc. of the Int'l Workshop on Post-Quantum Cryptography. Waterloo: Springer Int'l Publishing, 2014. 76-87. [doi: 10.1007/978-3-319-11659-4_5] |
[14] |
Yasuda T, Sakurai K. A multivariate encryption scheme with rainbow. In: Qing SH, ed. Proc. of the Int'l Conf. on Information and Communications Security. Beijing: Springer Int'l Publishing, 2015. 236-251. [doi: 10.1007/978-3-319-29814-6_19] |
[15] |
Petzoldt A, Bulygin S, Buchmann J. CyclicRainbow-A multivariate signature scheme with a partially cyclic public key. In: Gong G, ed. Proc. of the Int'l Conf. on Cryptology in India. Hyderabad: Springer-Verlag, 2010. 33-48. [doi: 10.1007/978-3-642-17401-8_4] |
[16] |
Petzoldt A, Bulygin S, Buchmann J. Fast verification for improved versions of the UOV and rainbow signature schemes. In: Gaborit P, ed. Proc. of the Int'l Workshop on Post-Quantum Cryptography. Limoges: Springer-Verlag, 2013. 188-202. [doi: 10.1007/978-3-642-38616-9_13] |
[17] |
Duong DH, Petzoldt A, Takagi T. Reducing the key size of the SRP encryption scheme. In: Liu JK, ed. Proc. of the Australasian Conf. on Information Security and Privacy. Melbourne: Springer Int'l Publishing, 2016. 427-434. [doi: 10.1007/978-3-319-40367-0_27] |
[18] |
Shen W, Tang S. RGB, a mixed multivariate signature scheme. The Computer Journal, 2016, 59(4): 439–451.
[doi:10.1093/comjnl/bxv056] |
[19] |
Kipnis A, Shamir A. Cryptanalysis of the oil and vinegar signature scheme. In: Krawczyk H, ed. Proc. of the Annual Int'l Cryptology Conf. Springer-Verlag, 1998. 257-266. [doi: 10.1007/BFb0055733] |