改进的HFEM公钥密码方案在数字签名上的应用设计
2014-07-27赵永哲
宋 严,赵永哲
(1.长春师范大学网络中心,吉林 长春 130032;2.吉林大学计算机科学与技术学院,吉林 长春 130012)
改进的HFEM公钥密码方案在数字签名上的应用设计
宋 严1,赵永哲2
(1.长春师范大学网络中心,吉林 长春 130032;2.吉林大学计算机科学与技术学院,吉林 长春 130012)
通过讨论HFEM公钥密码方案中解密的效率问题,提出了改进的HFEM公钥密码方案(I-HFEM).给出了I-HFEM方案的定义和算法,证明了I-HFEM方案的私钥尺寸以及解密开销都较原方案大为减少,并通过实例说明了I-HFEM方案在数字签名领域上应用的重要意义.
HFM公钥密码;HFEM;I-HFEM;签名方案;有限域上的遍历矩阵
HFEM公钥密码方案[1]在2009年申请了专利后,开始在数字签名领域使用.所谓HFEM,即隐藏有限域上遍历矩阵的公钥密码(Hidden Field Ergodic Matrices’ Public Key Cryptography),它是基于有限域上BMQ问题的难解性以及遍历矩阵的特性所实现的一种新的公钥密码方案.所谓BMQ问题,是指有限域上的二等分多变元二次方程组求解问题(Bisectional Multivariate Quadratic Equations Solving Problem).该问题已经被证明是一个NP完全问题.但原始的HFEM方案存在私钥尺寸较大以及解密效率较低的缺点,因此,本文对其进行了改进,改进后的方案记为I-HFEM(Improved HFEM).与HFEM方案相比,I-HFEM不仅减小了私钥尺寸,还大大提高了解密的效率.
1 背景理论
1.1 HFM-PKC方案设计
所谓HFM-PKC,即“隐藏域上矩阵的公钥密码[2](Hidden Field Matrices’ Public Key Cryptography)”是基于有限域上BMQ问题的困难性以及有限域上矩阵的性质所实现的一种公钥密码.HFM-PKC的实现需要满足如下条件的矩阵集合A和B:
(3) |VS(A)VS(B){0}|=(qn-1)2/(q-1);
(4) Rank(AB)=2n.
1.2HFEM的实现
HFEM公钥密码方案主要由密钥生成、加密、解密3个部分构成.
HFEM公钥密码方案密钥生成部分为其提供CA使用,为每个用户产生一对私钥和公钥,其实现方法如下:
(5) 由RB生成2n个Fq上的BMQ多项式
(6) 公钥为(Fq,ρ=[ρ1(x,y),…,ρ2n(x,y)],私钥为(B1M,B2,λ).
(4) 利用高斯消元法求出w的逆矩阵w-1∈〈Q2〉;
(6) 则(x,y)必与(α,β)等价,由此可还原出P=x⊗y=α⊗β.
由有限域上遍历矩阵的性质[3]可知(A=B1M,B=B2)满足条件(1)和(2).又由exp(Q1,M,Q2)=1和M∈R2(Q1,Q2),可知(A,b)亦满足条件(3)和(4).这样的(A,B)数量众多,所以HFEM方案是可行的.
1.3HFEM效率分析
2 I-HFEM的设计与实现
2.1 I-HFEM的设计思想
由前面对HFEM解密算法的效率分析,不难发现其开销主要由解密算法第2步的开销决定.所以应将优化的重点放在如何才能减少解密算法第2步的开销.在原HFM-PKC方案的基础上,对约束条件进行了精炼,新的约束条件变为[5]:
(3) |VS(A)VS(B){0}|=(qn-1)2/(q-1);
(4) Rank(AB)=2n.
如果存在众多满足上述约束条件的(A,B),则可实现改进的HFM-PKC方案.
密钥生成部分:
(3) 由RAB生成2n个Fq上的BMQ多项式ρk(x,y)=Rk[x⊗y](1≤k≤2n);
(4) 公钥为(Fq,ρ=[ρ1(x,y),…,ρ2n(x,y)],私钥为(A,B,λ).
解密部分:
(4) 利用高斯消元法求出w的逆矩阵w-1∈VS(B){0};
(6) 由(x,y)还原出明文P=x⊗y=α⊗β.
效率分析:
改进的HFM-PKC方案的私钥尺寸[6]为[(n3+6n2)log2q] B,比原来的(4n3log2q) B减少了将近3/4.更为重要的是,这使得解密算法的开销大大降低.下面对其详细分析:
2.2I-HFEM的实现
(ab)[r1,r2]=(a[r1,r2])b=(x1A1[r1,r2]+…+xnAn[r1,r2])(y1B1+…+ynBn)=T[r1,r2].
由此可得Fq上具有2n个变元和2n个方程的BMQ方程组E(A[r1,r2],B,T[r1,r2]):
由E(A[r1,r2],B,T[r1,r2])的构造,可知其恰好对应于E(A,B,T)中的第(r1-1)n+1至r1n以及第(r2-1)n+1至r2n这2n个方程,即E(A[r1,r2],B,T[r1,r2])为E(A,B,T)的“子方程组”.又由Rank(AB)=2n和相关定理可知,必存在i,j∈{1,…,n},且E(A[i,j],B,T[i,j])中的2n个方程彼此线性无关.所以E(A[i,j],B,T[i,j]必与E(A,B,T)等价,即二者同解.
令(A′=A[i,j]={A1[i,j],…,A[i,j]},B′=B),则(A′,B′)满足所有的新约束条件.由此可实现I-HFEM.
密钥生成部分:
(5) 如果Rank([AB])<2n,则转(4);
(7) 由RAB生成2n个Fq上的BMQ多项式ρk(x,y)=Rk[x⊗y](1≤k≤2n);
(8) 公钥为(Fq,ρ=[ρ1(x,y),…,ρ2n(x,y)],私钥为(A,B,λ).
解密部分:
(3) 如果T[1]≠0,则令k=1,否则令k=2;
(6) 由(x,y)还原出明文P=x⊗y=α⊗β.
2.3I-HFEM与HFEM的主要区别
3 基于I-HFEM的数字签名方案设计
设签名者Peggy的公钥和私钥分别为(Fq,ρ=[ρ1(x,y),…,ρ2n(x,y)]和(A,B,λ),则Peggy和验证者Vic可按如下方式对消息进行签名和验证签名.
签名为:
(5) (H,sm)即为Peggy对消息m的签名.
验证签名为:
(2) Vic用Peggy的公钥计算d″m=(ρ1(sm),…,ρ2n-t(sm));
表中无法被签名的消息摘要数量及所占比例
注:100次实验结果.
由表1可以看出如下规律:
[1] 赵永哲,赵博,裴士辉,等.HFEM公钥密码方案的设计与实现[J].通信学报,2011,32(6):24-31.
[2] 赵博,赵宏伟,苏晋璇,等.MPKC的中心映射与公钥形式[J].吉林大学学报:理学版,2012,50(4):719-725.
[3] 裴士辉,赵永哲,赵宏伟.基于遍历矩阵的公钥加密方案[J].电子学报,2010,38(8):1908-1913.
[4] 赵永哲,赵搏,裴士辉.有限域上遍历矩阵的特性研究[J].数学学报,2012,55(3):457-468.
[5] 袁哲,赵永哲,李光伟,等.利用有限域上遍历矩阵实现基于隐藏基的密钥交换[J].吉林大学学报:理学版,2009,47(04):783-789.
[6] 赵永哲,黄声烈,姜占华.GF(2k)上的遍历矩阵及其特性分析[J].小型微型计算机系统,2005,26(12):2135-2139.
[7] 赵永哲,姜占华,黄声烈.基于F2上遍历矩阵的Sham ir三次传递协议的实现[J].小型微型计算机系统,2006,27(6):986-991.
[8] 孙永雄,赵永哲,杨永健,等.基于遍历矩阵的单向(陷门)函数的构造方案[J].吉林大学学报:信息科学版,2006,24(5):555-560.
[9] 赵永哲,裴士辉,王洪军,等.利用有限域上的遍历矩阵构造动态加密器[J].小型微型计算机系统,2007,28(11):2010-2014.
Abstract:This paper explores the decipherment efficiency in the HFEM public key cryptography plan,puts forward the improved HFEM public key cryptography plan (I-HFEM),gives the definition and algorithm,proves that the private key size of I-HFEM plan and the decipherment cost will have a great reduction than the original one,and illustrates that I-HFEM plan has very important applied significance in the field of digital signature.
Keywords:HFEM public key cryptography;HFEM;I-HFEM;signature plan;ergodic matrices over the finite field
(责任编辑:石绍庆)
The application design of improved HFEM public key cryptography plan on signature
SONG Yan1,ZHAO Yong-zhe2
(1.Center of Network,Changchun Normal University,Changchun 130032,China;2.School of Computer Science and Technology,Jilin University,Changchun 130012,China)
1000-1832(2014)03-0069-06
10.11672/dbsdzk2014-03-014
2013-07-11
“十一五”国家密码发展基金资助项目(2006L014J00002);吉林省教育厅科学技术研究项目(吉教科合字[2008]第346号).
宋严(1982—),男,硕士,实验师;赵永哲(1961—),男,硕士,教授,主要从事密码学和信息安全研究.
TN 915.08 [学科代码] 520·1060
A