APP下载

改进的HFEM公钥密码方案在数字签名上的应用设计

2014-07-27赵永哲

东北师大学报(自然科学版) 2014年3期
关键词:数字签名私钥吉林大学

宋 严,赵永哲

(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

展开全文▼

猜你喜欢

数字签名私钥吉林大学
清扫机器人避障系统区块链私钥分片存储方法
比特币的安全性到底有多高
基于改进ECC 算法的网络信息私钥变换优化方法
采购与论证分离模式下的大型仪器设备购置论证思考与探索——以吉林大学为例
《吉林大学学报(理学版)》征稿简则
《吉林大学学报( 理学版) 》征稿简则
浅析计算机安全防护中数字签名技术的应用
吉林大学等二医院王金成教授简介
一种基于虚拟私钥的OpenSSL与CSP交互方案
基于数字签名的QR码水印认证系统