一种基于双曲线群算术的公钥密码体制及签名方法

技术领域

本发明属于公钥密码体制领域，尤其涉及一种基于双曲线群算术的公钥 密码体制及签名方法。

背景技术

现有主要技术有RSA公钥密码及签名(不足之处：密钥过长导致时间效 率低；模运算赤裸性；非随机性算法；明文的单一性；安全性无层次，限制 了其它功能算法的进一步开发)、椭圆曲线公钥密码及签名(由于一般椭圆 曲线群的阶难以获得，导致其应用受到极大限制，尽管其具备双曲线公钥密 码及签名的相似优势，但是，仍然处于理论研究阶段，尚未得到广泛应用， 并且，椭圆曲线群运算较双曲线群运算复杂，没有双曲线运算容易实现，这 增加了其运行成本，降低了时间效率)、ElGamal公钥密码及签名(不足之 处：模运算赤裸性；系统安全性仅基于离散对数的困难性；明文的单一性等)

公开密钥密码体制是现代密码学的最重要的发明和进展，现有的公钥密 码体制密钥过长，模运算赤裸性，明文的单一性、安全性无层次，密级无差 别性。

发明内容

本发明的目的在于提供一种基于双曲线群算术的公钥密码体制及签名方 法，旨在解决现有的公钥密码体制密钥过长，模运算赤裸性，明文的单一性、 安全性无层次，密级无差别性的问题。

本发明是这样实现的，一种基于双曲线群算术的公钥密码体制及签名方 法包括公钥密码算法、数字签名算法、区别保密等级算法。

进一步，所述的公钥密码算法包括四种基本算法；

算法一的具体方法为：

加密算法：

(1)将明文M编码映射到双曲线H_D(N)上的点M′＝(m₁,m₂)；

(2)计算M′^e≡C(modN)，其中C是密文且C＝(c₁,c₂)∈H_D(N)；

解密算法：

(1)C^d≡M′(modN)；

(2)对M′＝(m₁,m₂)解码还原明文M；

算法二的具体方法为：

加密算法：

(1)将明文M编码映射到模双曲线H(N)上，或有限域的双曲线上的点M′＝(m₁,m₂)；

(2)在[2,q-1]中随机选择一个整数r；

(3)计算C₁＝G^r，C₂＝M′P^r，形成密文C＝(C₁,C₂)；

解密算法：

(1)计算C₁^k；

(2)M′＝C₂C₁^-k；

(3)对M′＝(m₁,m₂)解码得到M；

算法三的具体方法为：

加密算法：

(1)将消息明文M变化成剩余系Z/Z_N上，或者基域GF(p)上的二元组 M＝(m₁,m₂)；

(2)在[2,q-1]中随机选择一个整数r；

(3)计算得到密文(C₀,c₁,c₂)，其中

C₀＝G^r,

Y＝(y₁,y₂)＝P^r

c₁＝y₁m₁(modN or p)

c₂＝y₂m₂(modN or p)

解密算法：

(1)计算Z＝(z₁,z₂)＝C₀^k；

(2)得到明文M＝(m₁,m₂)＝(c₁z₁^-1(modN or p),c₂z₂^-1(modN or p))；

算法四的具体方法为：

加密算法：

(1)将消息明文M变化成剩余系Z/Z_N上，或者基域GF(p)上的一维元 m；

(2)在[2,q-1]中随机选择一个整数r；

(3)计算得到密文(C₀,c₁)，其中

C₀＝G^r,

Y＝(y₁,y₂)＝P^r

c₁＝y₁m(modN or p)

解密算法：

(1)计算Z＝(z₁,z₂)＝C₀^k；

(2)得到一维元m＝c₁z₁^-1(modN or p)，还原成明文M。

进一步，所述的数字签名算法包括三种基本算法：

算法一的具体方法为：

签名过程：

用户A对已经编码到双曲线上的消息M∈H_D(N)进行签名，

(1)计算S_A＝M^d≡C(modN)，其中d是签名方A的私钥；

(2)将S_A附在消息M后作为用户A的签名；

签名验证：

(1)C^e≡M′(modN)，其中e是签名方A的公钥；

(2)M′与M比对，如果两者一致，相信签名确实为用户A所产生的， 否则拒绝确认该签名消息；

算法二的具体方法为：

加密消息并签名：

(1)用户A对消息m签名，S_A＝m^d≡m′(modN)；

(2)在[2,q-1]中随机选择一个整数r；

(3)计算C₁＝G^r，C₂＝M′P^r，其中M′＝(m,m′)，且形成密文C＝(C₁,C₂)；

解密及验证签名：

(1)计算C₁^k；

(2)M′＝C₂C₁^-k；

(3)对M′＝(m,m′)中m′做签名验证m″≡m′^e(modN)，如果m″和m一致， 签名获得确认；

算法三的具体方法为：

消息签名：

(1)选择一个随机数r满足1＜r＜q-1；

(2)计算C₁＝G^r＝(x,y)，且x＜q；

(3)计算s＝r^-1(h(M)+kx)(modq)，其中h(M)是对消息M进行散列压缩 得到的散列码；

(4)用户A将(s,x)作为消息M的数值签名，与M一起发送给接受方；

签名验证：

(1)s,x是否在[1,q-1]内，若不是则拒绝签名；

(2)计算u₁＝h(M)s^-1(modq)和u₂＝xs^-1(modq)；

(3)利用用户A的公钥P，计算$G^{u_1}{P}^{u_2}=G^{u_1+{\mathrm{ku}}_2}=G^{(h\left(M\right)+\mathrm{kx})s^{-1}}=G^r=(x^{\prime },y^{\prime }),$如果验证x＝x′，那么签名被证实。

进一步，所述的区别保密等级算法的具体方法为：

加密：

(1)用户A对高密级别的消息m₁加密，S_A＝m₁^e≡c₁(modN)；

(2)在[2,q-1]中随机选择一个整数r；

(3)计算C₁＝G^r，C₂＝M′P^r，其中M′＝(c₁,m₂)，且形成密文C＝(C₁,C₂)；

解密：

(1)计算C₁^k；

(2)M′＝C₂C₁^-k；

(3)对M′＝(c₁,m₂)中高级别密文c₁做进一步解密m₁≡c₁^d(modN)；

该算法可实现消息不是被消息直接接受者而是转发给另外的授权人。

效果汇总

本发明首先,双曲线算术理论:主要指类似这样的方程x²-Dy²≡r(modN)其 中r与N互质即最大公共因子gcd(r,N)＝1，这样的r有个，其中称为 欧拉函数,可利用模数N的标准分解计算出来；设N是不同素数的积，可证明: 对于每个这样r，方程x²-Dy²≡r(modN)解的个数均相等；若解数记为 #H(rmodN),那么#H(rmodN)＝#H(r′modN),r≠r′；

基于上述事实,将形如x²-Dy²≡r(modN)方程的解(x,y)全体组成一个集 合,记为H(Z^*/NZ^*)；它在乘法运算：

$\left(\begin{array}{c}(x,y)(x^{\prime },y^{\prime })=(x+y\sqrt{D})(x^{\prime }+y^{\prime }\sqrt{D})\\ =x^{\prime \prime }+y^{\prime \prime }\sqrt{D}=(x^{\prime \prime },y^{\prime \prime })\end{array}\right)$

意义下，形成有限群，称为双曲线群；它的阶数扩大为这是相对于RSA公钥体制和ElGamal公钥体制而言,它是基于Euler算术定理 和Fermat小定理，其群阶数仅为另外，双曲线群有丰富的子群结构， 如r取1时，方程x²-Dy²≡1(modN)的解集自身就是一个群(子群)，通常称为 双曲线单位群，它本身也有丰富的结构.

本发明主要利用双曲线群及其子群等,构造各种功能的公钥密码及签名 算法,

直接效果:1.扩大了明文或密文空间；2.丰富了加密消息的形式，如图文 并举，甚至加密其它形式信号等；3.便于现代技术实现；4.多重安全性；5. 模运算的隐蔽性；6.提高密码分析的强度；7.供选择的双曲线群模型多样性.

技术效果:通过算法设计实现1.公钥密码分离；2.密钥多级化；3.明文 和密文多级化；4.局部随机性；5.密钥长度控制；6.时间效率提高；

功能效果:1.实现消息按公钥密码算法安全通信、存储等；2.实现消息 签名和认证；3.实现消息的安全等级差别；4.实现不可否认签名、群签名盲 签名和共同见证等功能。

附图说明

图1是本发明实施例提供的双曲线公钥密码系统设计示意图；

图2是本发明实施例提供的双曲线公钥密码体制及其多密级实现的示意 图；

图3是本发明实施例提供的基于双曲线群的数字签名示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及 实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施 例仅仅用以解释本发明，并不用于限定本发明。

实施例一，如图1-图3所示，

基于双曲线群算术的公钥密码体制及签名技术概述：

1.系统设计的主要参数:N,D,G,q，|H_D(N)|，

(1)N是具有安全性的模数，它至少由两个不同的大素数乘积；

(2)D是双曲线的特征系数它使得模N双曲线具有大素数阶的点，或者 阶含有大素数因子的点(统称为基点)；

(3)G是模N双曲线H_D(N)或者有限域上的双曲线上的一个基点 (其阶数是个大素数q或含有大素数因子q)；

(4)H_D(N)也就是选定了特征系数D的模N双曲线群，|H_D(N)|表示其阶 (可计算得到)；

(5)是选定特征系数D的有限域上的双曲线群，表示其 阶。

2.预计算(e,d),(P,k)

(1)安全的密钥对(e,d)，这里e是公钥，d是私钥，它们满足 ed≡1(mod|H(N)|)，其中模数H(N)可以视为广义Euler函数；

(2)安全的密钥对(P,k)，这里P是公钥，k是私钥，它们满足G^k＝P， 其中整数k在[2,q-1]中随机选择.

3.保密参数

系统的保密参数：

(1)构成N的各个大素数因子保密的，在完成必要的计算后，可“销毁”；

(2)双曲线群的特征系数D由系统保存或者更换；

(3)选定特征系数D的模N双曲线群的阶|H_D(N)|.安全保存；

(4)选定特征系数D有限域上双曲线群的阶安全保存；

(5)双曲线基点的阶q(是一个大素数).安全保存

用户保密参数：

(1)用户的密钥对(e,d)中的d必须由用户安全保存或者系统代理保密；

(2)用户的密钥对(P,k)中的私钥k必须由用户安全保存或者系统代理保 密.

4.公开参数

系统参数：

(1)模数N；

(2)基点G.

局部参数：

(1)用户的密钥对(e,d)中的公钥e；

(2)用户的密钥对(P,k)中的公钥P；

本发明是这样实现的，一种基于双曲线群算术的公钥密码体制及签名方 法包括公钥密码算法、数字签名算法、区别保密等级算法。

进一步，所述的公钥密码算法包括四种基本算法；

算法一的具体方法为：

加密算法：

(1)将明文M编码映射到双曲线H_D(N)上的点M′＝(m₁,m₂)；

(2)计算M′^e≡C(modN)，其中C是密文且C＝(c₁,c₂)∈H_D(N)；

解密算法：

(1)C^d≡M′(modN)；

(2)对M′＝(m₁,m₂)解码还原明文M；

该算法的优点如下：

(1)双曲线公钥密码体制算法简捷，形式上酷似RSA，但是，实际上， 双曲线密码体制算法是针对双曲线的点，换言之，它是隐性模运算，而不 是象现行的RSA算法是显性模运算，因此，在同样规模的模数下，双曲 线密码系统安全性要更强，即密码分析要困难得多；

(2)双曲线公钥密码体制算法针对二维明文比现行RSA的可加密的数据 形式更丰富；

(3)双曲线群算术比椭圆曲线群算术的计算方便，因此，其密码体制较 后者容易实现；

(4)为了解决将明文编码映射到双曲线上的问题，可采用系统匹配方式， 或者选择算法二、三和算法四可方便地解决这个难题；

(5)密钥的长度也比传统RSA小，如必要时，密钥对(e,d)可采用 ed≡1(modq′)方式生成，其中q′是|H_D(N)|的一个素数因子，这样可提高加 解密的时间效率；

(6)双曲线群密码体制的具有层次安全性:系统安全性建立在大整数分 解的困难问题，而破译安全性建立在隐离散对数的困难问题之上，故具有双 重安全性。从这一点上看，又比安全性仅基于离散对数困难性的椭圆曲线密 码体制和ElGamal密码体制具有更高的系统安全性。

算法二的具体方法为：

加密算法：

(1)将明文M编码映射到模双曲线H(N)上，或有限域的双曲线上 的点M′＝(m₁,m₂)；

(2)在[2,q-1]中随机选择一个整数r；

(3)计算C₁＝G^r，C₂＝M′P^r，形成密文C＝(C₁,C₂)；

解密算法：

(1)计算C₁^k；

(2)M′＝C₂C₁^-k；

(3)对M′＝(m₁,m₂)解码得到M；

该算法的优点如下：

(1)实际上，该算法将明文编码映射到模双曲线或有限域的双曲线上的点 是不必要；

(2)该算法在离散对数困难性下，可实现一文一密；

(3)密钥对不直接依赖模数的大小，密钥长度比算法1短，时效性优；

(4)该算法可以在有限域上的双曲线中实现；

(5)该算法加密时，若添加自己的私钥便可实现消息签名功能。

算法三的具体方法为：

加密算法：

(1)将消息明文M变化成剩余系Z/Z_N上，或者基域GF(p)上的二元组 M＝(m₁,m₂)；

(2)在[2,q-1]中随机选择一个整数r；

(3)计算得到密文(C₀,c₁,c₂)，其中

C₀＝G^r,

Y＝(y₁,y₂)＝P^r

c₁＝y₁m₁(modN or p)

c₂＝y₂m₂(modN or p)

解密算法：

(1)计算Z＝(z₁,z₂)＝C₀^k；

(2)得到明文M＝(m₁,m₂)＝(c₁z₁^-1(modN or p),c₂z₂^-1(modN or p))；

算法四的具体方法为：

加密算法：

(1)将消息明文M变化成剩余系Z/Z_N上，或者基域GF(p)上的一维元 m；

(2)在[2,q-1]中随机选择一个整数r；

(3)计算得到密文(C₀,c₁)，其中

C₀＝G^r,

Y＝(y₁,y₂)＝P^r

c₁＝y₁m(modN or p)

解密算法：

(1)计算Z＝(z₁,z₂)＝C₀^k；

(2)得到一维元m＝c₁z₁^-1(modN or p)，还原成明文M。

进一步，所述的数字签名算法包括三种基本算法：

算法一的具体方法为：

签名过程：

用户A对已经编码到双曲线上的消息M∈H_D(N)进行签名，

(1)计算S_A＝M^d≡C(modN)，其中d是签名方A的私钥；

(2)将S_A附在消息M后作为用户A的签名；

签名验证：

(1)C^e≡M′(modN)，其中e是签名方A的公钥；

(2)M′与M比对，如果两者一致，相信签名确实为用户A所产生的，否 则拒绝确认该签名消息；

算法二的具体方法为：

加密消息并签名：

(1)用户A对消息m签名，S_A＝m^d≡m′(modN)；

(2)在[2,q-1]中随机选择一个整数r；

(3)计算C₁＝G^r，C₂＝M′P^r，其中M′＝(m,m′)，且形成密文C＝(C₁,C₂)；

解密及验证签名：

(1)计算C₁^k；

(2)M′＝C₂C₁^-k；

(3)对M′＝(m,m′)中m′做签名验证m″≡m′^e(modN)，如果m″和m一致，签 名获得确认；

算法三的具体方法为：

消息签名：

(1)选择一个随机数r满足1＜r＜q-1；

(2)计算C₁＝G^r＝(x,y)，且x＜q；

(3)计算s＝r^-1(h(M)+kx)(modq)，其中h(M)是对消息M进行散列压缩得到 的散列码；

(4)用户A将(s,x)作为消息M的数值签名，与M一起发送给接受方；

签名验证：

(1)s,x是否在[1,q-1]内，若不是则拒绝签名；

(2)计算u₁＝h(M)s^-1(modq)和u₂＝xs^-1(modq)；

(3)利用用户A的公钥P，计算$G^{u_1}{P}^{u_2}=G^{u_1+{\mathrm{ku}}_2}=G^{(h\left(M\right)+\mathrm{kx})s^{-1}}=G^r=(x^{\prime },y^{\prime }),$如 果验证x＝x′，那么签名被证实。

进一步，所述的区别保密等级算法的具体方法为：

加密：

(1)用户A对高密级别的消息m₁加密，S_A＝m₁^e≡c₁(modN)；

(2)在[2,q-1]中随机选择一个整数r；

(3)计算C₁＝G^r，C₂＝M′P^r，其中M′＝(c₁,m₂)，且形成密文C＝(C₁,C₂)；

解密：

(1)计算C₁^k；

(2)M′＝C₂C₁^-k；

(3)对M′＝(c₁,m₂)中高级别密文c₁做进一步解密m₁≡c₁^d(modN)；

该算法可实现消息不是被消息直接接受者而是转发给另外的授权人。

在最坏的情形下，若系统攻击者付出代价将模数N分解，可以停止使用 基于密钥对(e,d)的密码体制，但是，基于密钥对(P,k)的加密体制仍然是安全 的；反过来，也如此，即若系统攻击者付出代价发现了基点的阶q，则可停 止采用基于密钥(P,k)的密码体制，但是，基于密钥对(e,d)的密码体制仍然是 安全的。

本发明的基于双曲线群算术的公钥密码及签名算法，便于系统实现、具 有多重安全性、可实现安全等级加密、可针对多种数据形式包括文字和多媒 体进行加密、通信和存储等，克服了其它体制弱点和不足，如密钥过长，模 运算赤裸性，明文的单一性，安全性无层次，密级无差别性等等。

上述虽然结合附图对本发明的具体实施方式进行了描述，但并非对本发 明保护范围的限制，所属领域技术人员应该明白，在本发明的技术方案的基 础上，本领域技术人员不需要付出创造性的劳动即可做出的各种修改或变形 仍在本发明的保护范围之内。