基于圆锥曲线密码的密钥恢复方案研究

闫鸿滨，沈建涛

（南通职业大学 电子工程系，南通 226007）

基于圆锥曲线密码的密钥恢复方案研究

闫鸿滨，沈建涛

（南通职业大学 电子工程系，南通 226007）

0 引言

随着网络的应用与发展，网络安全问题日益突出。数据加密是确保计算机网络安全的一种重要的机制，其安全性取决于对密钥的保护，加密过的密钥以文件的形式保存在只有用户有权访问的地方。若用户忘记口令、误删密钥文件或者存放密钥的磁盘发生介质损坏等情况时，用户可能无法再进行正常的信息处理和交换，给用户带来了许多不便和损失。互联网上许多服务提供了类似的密钥(口令)恢复功能[1]，这些系统一般在用户发出口令恢复请求后，先使用用户注册时设置的私密性问题对用户进行身份验证，再为用户找回丢失的口令或重新为用户分配新口令。这类系统存在的突出问题：一是系统完全掌握用户的口令，用户的口令对于系统而言不具任何私密性；二是有的系统将用户口令经过某种单向函数处理后保存，一旦用户丢失口令，则只能重新分配口令，无法取得原有口令。

机遇以上问题，下文设计一种基于圆锥曲线公钥密码体制的安全性，结合门限的灵活性的密钥恢复方案，克服了传统密钥恢复服务的缺点。

1 预备知识

在介绍新方案之前，先简单介绍一下圆锥曲线密码体制[2]。

设FP，为P元有限域，P为奇素数，FP*为FP的乘群。不妨设：

考虑仿射平面A2(FP)上的圆锥曲线：

显然，x=0时得原点0(0,0)。若x≠0，令y=xtmodp，将y带入曲线方程得：

在FP中，若a≠t2，则由式(3)得：

其中，a,b∈FP*，()-1为FP*中元的乘法逆元，对t∈FP，t2≠a用p(t)表示C(FP)上有式(4)确定的点(x,y)，原点O记为P(∞)，令：

则P:H→C(FP)是一一对应映射。C(FP)中点的⊕运算定义为：

1）对任意p(t)∈C(FP)，其中t∈H，均有

2）设p(t1)，p(t2)∈C(FP)其中t1，t2∈H，且t1，t2≠∞，定义

易知t3∈H，且运算⊕是可交换的

3）对p(t)∈C(FP)，有负元

对于p(t1)，p(t2)，p(t3)∈C(FP)，容易验证：

明文的嵌入：

所谓明文嵌入问题，是指将原始明文m变换为C(FP)中的点p(m)，这里m∈H*，H*=H{∞}，将p(m)称为明码，它由明文m编码而得。

对于m∈H*，计算xm=b(a-m2)-1modp，ym=bm(a-m2)-1modp，a,b∈FP*，则有pm=(xm,ym)

译码算法：计算m=ymxm-1modp。由明文的嵌入过程容易证明译码算法的正确性。

我们将上述Fp中的运算改为Zn中的模N运算[4～6]，这里N=pq，p，q是两个大素数。设ϕ(N)=|C(FP)| |C(FP)|，则ϕ(N)p(t)=p(∞)(modN)这里p(t)=(xt,yt)

其中( )-1表示模N的逆元（这在(a-t2,N)=1时存在）。任选e使得：

由Euclid算法求出d使得

于是圆锥曲线密码体制的一种形式为：

公钥：e，N以及a,b∈ZN，(ab,N)=1

密钥：d，p，q。

明文：n∈ZN，(n,N)=1

密文：s∈ZN，加密算法为

1）计算ep(N)=p(s)(modN)，这里

注意，在假设大整数N不能分解时，模N的逆元存在（下同）。

知道密钥时的解密算法为：

（1）计算dp(s)=dep(n)=p(n)(modN)

2 动态密钥恢复协议

本方案用到的系统参数：N=pq，p，q是两个大素数，Zn为相应的有限域，h(x)为Zn上的单向函数。H={H1,H2,…,Hn}为系统中的n个密钥托管者的集合，Г为H上的一个单调接入结构，Г0={A1,A2,…,At}是Г的基。密钥分发者D首先把H以及A1,A2,…,At依次向所有密钥共享者公布[3,7]。

密钥分配：1）分发者D任意选取n∈ZN，(n,N)=1 ，并计算ep(n)=p(s)(modN)，由p(s)=(xs,ys)计算ys=s(modN)，n作为D的主密钥。

2）分发者D随机地选取n个互不相同的元素s1,s2,…,sn∈Zn，且si≠1mod(N-1)(i=1,2,…,n)，并将si通过安全信道秘密地发送给Hi，作为Hi拥有的子密钥。

3）分发者D随机地选取Zn上的n-1次多项式F(x)=a0+a1x+…+an-1xn-1，使得F(0)=s，且F(x)保密。

4）分发者D随机地选取α∈Zn，并计算xi=h(α+si)mod N

di=F(Ii)－h(α+si)mod N

yi=h(xi) mod p；i=1,2,…,n。

其中xi为Hi的屏蔽子密钥，si为Hi的秘密子密钥。Ii为Hi的身份表示符号（公开），然后D公开参数α以及有序数组(y1,y2,…,yn)与(d1,d2,…,dn)。

5）分发者D对每一个最小合格子集Ai=｛Hi1,Hi2,…,Hik｝，D由（Ii1,F(Ii1)），（Ii2,F(Ii2)）,…,（Iik，F(Iik)）及（0，s）共k+1个点用Lagrange插值公式确定出一个k次多项式：

并计算出Fi(α)，公开Fi(α)，i=1,2,…,t。

份额的验证算法在恢复密钥时，可以用来检测提供虚假份额的恶意参与者。

用户D获得s后，可以通过dp(s)=deP(n)=P(n))mod N)和P(n)=(xn,yn)，由式xn-1yn=n(mod N)就可以得到丢失的主密钥。

3 性能分析

1）协议的安全性是以圆锥曲线密码体制的安全性和单项函数的安全性为基础的。

2）由于在恢复密钥时，每个托管代理提交的是其屏蔽子密钥，xi=h(α+si)mod p。根据单向函数不可求逆的特性，其他人无法通过xi求出Hi的子密钥si，即每个托管代理的子密钥并没有因为通信密钥的恢复而被公开，从而可以继续使用。

3）同样，任何人也无法通过公开信息α及有序数组（y1,y2,…,yn）与（d1,d2,…,dn）来获取托管代理的屏蔽子密钥及秘密子密钥。

另外，当某个成员提供他的屏蔽子密钥后，可以通过验证等式yi=h(xi) mod p是否成立，来判断该成员提供的份额是否有效，从而可以检验恶意参与者。

4 结束语

文中综合应用单向函数，圆锥曲线密码算法，门限原理，提出了一种密钥恢复方案，较好地解决了密钥管理中的密钥共享和恢复的难题，该方案不仅适用于对用户密钥、口令进行保存以及恢复，还可用以对其他私密信息进行类似处理，具有一定的通用性。

[1]魏家好,侯整风.基于(r,n)门限的密钥恢复方案[J].计算机技术与发展,2006,16(10):134-136.

[2]王标.圆锥曲线及其在公钥密码体制中的应用[D].成都:四川大学,2006.

[3]闫鸿滨,袁丁,等.一种新的广义动态密钥托管方案[J].铁道学报,2006,28(5):104-107.

[4]孙琦,张起帆,彭国华.Dickson多项式ge(x,l)/公钥密码体制的新算法[J].四川大学学报(自然科学版),2002,1:18-23.

[5]孙琦,张起帆,彭国华.计算群元整数倍的一种算法及其在公钥密码体制中的应用[A].密码学进展——ChinaCrypt'2002,第七届中国密码学学术会议论文集[c],电子工业出版社.

[6]K.Koyama,U.Maurer,T.Okamoto,and S.A.Vanstone,"New Public-Key Schemes Based on Elliptic Curves over the Ring Zn",Advances in Cryptology-CRYPTO'91,Lecture Notes in Computer Science1992(576):252-266.

[7]焦学磊.基于环Zn上圆锥曲线的数字签名方案[D].成都:成都理工大学,2008.

Research on the key recovery system based on conic curve cryptography

YAN Hong-bin, SHEN Jian-tao

密钥管理是网络安全中的关键问题，从技术上看，密钥管理包括密钥的产生、存储、分配、使用和销毁等一系列技术问题，密钥共享和恢复是其中最重要的问题。文中介绍了一种基于圆锥曲线公钥密码体系进行密钥恢复的新方案，该方案应用门限技术来恢复丢失的密钥或口令。与传统密钥的恢复方案相比，具有较好的易用性和安全性。

密钥管理；密钥共享；密钥恢复；协议

闫鸿滨（1969 -），男，山东济宁人，副教授，硕士研究生，研究方向为信息安全、密码学。

TN918

A

1009-0134(2011)5(上)-0065-03

10.3969/j.issn.1009-0134.2011.5(上).23

2010-11-17

国家自然科学基金项目（60773035）；四川省学术和技术带头人资助项目（08226056）；国家教育部留学回国人员择优项目