086-一种基于亚群上离散对数问题的公钥密码方案new

《086-一种基于亚群上离散对数问题的公钥密码方案new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一种基于亚群上离散对数问题的公钥密码方案管海明中国电子设备系统工程公司通信研究所北京100039E-mail:ghm@263.net[3]摘要本文介绍了一种新的公开密钥密码编码方案可用于公开信道上的密钥分配信息加密其安全性基于亚群上的离散对数问题关键词亚群公钥密码体制密钥分配一引言[1]目前流行的公钥密码方案都以群为最基本的数学结构例如RSA采用由剩余类环中的原根组成的亚循环群上的求幂运算D-H采用有限域上的循环群的求幂运算ECC采用有限域上2元3次方程中的点组成的交换群的求幂运算群group是满足封闭性结合律有单位

2、元有逆元的二元运算结构半群[2]semi-group是满足封闭性结合律的二元运算结构而亚群groupoid则是只满足封闭性一条性质的二元运算结构对于设计公钥密码来说亚群是比群更好的代数结构首先亚群与群相比其外延更广泛形式更一般性质更复杂在抗数学分析方面有天然的优势由于可以不考虑结合律单位元素逆元素以及交换律分配律等约束条件使算法设计的灵活性和自由度大为增加其次当代数学对亚群的研究很不成熟而现有的在群环域上广泛使用的一大类数学分析手段和结果不能简单地推广到亚群进一步增加了密码分析的困难性[3]鉴于上述考虑本方案先构造一

3、类具有特殊性质的亚群并构造建立在亚群上的特殊的幂运算规则再运用构造的亚群及幂运算规则实现密钥分配协议和加解密协议[4]控制本方案的某些参数后也能实现数字签名但其安全性基于半群上的离散对数问题二基本原理1.构造亚群n以有限交换环构造有零因子亚群的方法是R代表有限交换环R表示R的n阶n向量的集合⊗表示定义在R上的二元运算c1=a"b1c2=a"b2C=A⊗B=............cn=a"bna"=f(a1,a2,…,an)A=[a1,a2,…,an]B=[b1,b2,…,bn]C=[c1,c2,…,c

4、n]nA,B,CRai,bi,ci,a"Rf(a1,a2,…,an)的构造方法是用环R中的不等于0的元随机构造d×n阶阵列Gd×nG=[(g)ij]d×n∈R由初始状态a1(0),a2(0),…,an(0)对于i=1,2,…,d依次计算a(i)=[g(a(i−1)+a(i−1))]ei1i,11na(i)=[g(a(i−1)+a(i))]ei2i,221............a(i)=[g(a(i−1)+a(i))]eini,nnn−1h得到a"=[a1(d)+a2(d)+…+an(d)]其中ndhe1e2…ed取

5、大于1的正整数n定义由集合R和二元运算⊗组成一个非结合非交换无单位元无逆元有零因子的亚群nS=R⊗R的实际可选范围很大如有限域整数剩余类环多项式环乃至由复杂的代数簇组成的多元多项式环选用较复杂的R可获得较强的抗数学分析能力但工程实现代价也会随之迅速增加从密码强度与工程代价两方面考虑作为R的最佳设计实例本方案提出并重点推荐选用多重模运算下的一元多项式环该环的构造方法如下首先构造整数剩余类环Zm然后以Zm中的元为系数以Zm为定义域以Zm为值域随机构造一个关于x的s次首1多项式u(x)ss-1u(x)=x+as-1x+…+

6、a1x+a0Modm我们用f’(x)表示Zm上的一般的整数多项式用+分别表示在双重模运算Modm,u(x)下的多项式加法和多项式乘法则由mu(x)可构造一个Zm上的多项式环R[u(x)]=#u(x)+#u(x)={f(x)

7、f(x)=f’(x)Modm,u(x)}xZm,deg(u(x))=s然后用R[u(x)]构造多项式环R[v(y)]以R[u(x)]中的元素为系数以R[u(x)]为定义域以R[u(x)]为值域随机构造一个关于y的k次首1多项式v(y)kk-1v(y)=y+bk-1y+…+b1y+b0Modm,u(

8、x)我们用f’(y)表示环R[u(x)]上的一般的多项式用+分别表示在三重模运算Modm,u(x),v(y)”下的多项式加法和多项式乘法则由mu(x)v(y)可构造一个R[u(x)]上的多项式环R[v(y)]=#v(y)+#v(y)={f(y)

9、f(y)=f’(y)Modm,u(x),v(y)}xZm,yR[u(x)],deg(u(x))=s,deg(v(y))=k再后用R[v(y)]构造多项式环R[w(z)]以R[v(y)]中的元素为系数以R[v(y)]为定义域以R[v(y)]为值域随机构造一个关于z的q次首1多项

10、式w(z)qq-1w(z)=z+cq-1z+…+c1z+c0Modm,u(x),v(y)我们用f’(z)表示环R[v(y)]上的一般的多项式用+分别表示在四重模运算Modm,u(x),v(y),w(z)”下的多项式加法和多项式乘法则由mu(x)v(y)w(z)可构造一个R[v(y)]上的多项式环R[w(z)]=#w(z)+#w(z)={f(z)