一种新型基于身份密钥隔离的签名方案

刘易+彭长根

【 摘 要 】 密钥隔离方案能够在一定程度上解决基于身份的密码系统中密钥分发中心权限过于集中的问题。基于支持多外围设备的身份密钥隔离签名方案和Hess签名方案，提出了一种新的基于身份密钥隔离数字签名方案；进一步针对密钥隔离、强密钥隔离和密钥更新的安全性进行了分析；最后，通过与支持多外围设备的身份密钥隔离签名方案和Hess签名方案进行效率分析与比较，该方案验算次数少、签名长度短、速度快，更适用于资源受限的智能手机中。

【 关键词 】 密钥隔离；数字签名；密钥隔离安全性；效率分析

A New Identity- Based Key-Insulated Signature Scheme

Liu Yi 1，2，3 Peng Chang-geng 2，3

[1. College of Computer Science &Technology， Guizhou University GuizhouGuiyang 550025；

2. Guizhou Provincial Key Laboratory of Public Big Data （GuiZhou University）， GuizhouGuiyang 550025；

3. Institute of Cryptography & Data Security， Guizhou University GuizhouGuiyang 550025]

【 Abstract 】 Key-Insulated scheme can solve key distribution center permissions concentration problems based on identity cryptographic system in a way.This paper propose a new Identity-Based Key-Insulated digital signature scheme on the basis of supporting more peripheral Identity-Based Key-Insulated signature scheme and Hess signature scheme； and Key-Insulated，strong Key-Insulated and the key update security were analyzed； Finally， the scheme compared efficiency with supporting more peripheral Identity-Based Key-Insulated signature scheme and Hess signature scheme，the scheme is checking fewer，shorter length of signature，faster，more applicable in resource constrained smart phones.

【 Keywords 】 key-Insulated； digital signature； key-Insulated security； efficiency analysis

1 引言

Diffie和Hellman[1]最早在《New Direction in Cryptography》中提出了数字签名的概念。1978年，Rivest、Shamir和Adleman[2] 第一个提出了基于大整數分解困难性的RSA数字签名方案。次年，Shamir又提出了秘密共享方案[3]。基于身份密码体系的概念和模型于1984年由Shamir首次提出[4]，此时数字签名被正式分为三类：带印章的数字签名、带影子的数字签名及使用Hash函数的数字签名。密钥隔离机制的思想最早是在Eurocrypt02上由Dodis等 [5]提出的，随后Dodis等在PKC03上给出了一个构造密钥隔离数字签名方案的通用方法，而且提出了一个具体的密钥隔离数字签名方案[6]。Hess提出一种高效可证明安全的基于身份数字签名方案[7]。2014年杜瑞颖等[8]提出了一个无证书密钥隔离签名方案，这种方案解决了基于身份密钥隔离签名方案中存在的密钥托管问题。2015年，学者秦志光等[9]对国内外密钥隔离密码系统的研究进展进行了综述，并从方案性能、安全模型及安全性等方面进行了对比分析。2016年寻甜甜[10]提出了一种密钥隔离的无证书聚合的概念与模型，实现对签名者密钥的定时更新。相比于传统基于证书的密码体制，基于身份的密码体制近年来在密码学中更受关注。在该体制中，任何一对用户都可以进行安全的通讯，签名公钥其实就是用户的身份信息，如身份、邮件地址等。基于身份的签名体制是一种特殊的数字签名体制，其避免了繁杂的证书管理，因此有着广泛的应用前景。

针对密钥泄露的问题，本文结合了支持多外围设备的基于身份的密钥隔离签名方案与Hess签名方案，提出了一种适用于智能手机的基于身份的密钥隔离数字签名具体方案，通过其他智能手机的协助来完成用户的密钥更新，这在一定程度上提高了系统的密钥泄露容忍度，且保证了系统的前向与后向安全，同时方案的签名长度短，由此提高了签名效率。

2 相关知识

在这里将介绍基于身份的密钥隔离签名方案[11]与标准模型下基于身份的强密钥隔离签名方案[12]的定义、困难性假设、非交互的离散对数等式知识证明协议等概念。

定义1：P为强素数，t是正整数，c0，c1，...，ct-1，a1，...，at为常数，假设一个线性反馈移位寄存器序列（Ni），定义为一个t阶齐次线性递归方程（HLFSR）：

N0 =c0 ，N1 =c1 ，...，Nt-1 =ct-1

Ni+t +a1 Ni+t-1 +...+aiNi =0 其中 i?0（1）

对t阶齐次线性递归方程（HLFSR），定义一个辅助函数和特征方程，它们分别为：

xt + a1xt-1 +......+at =0，f（x）=xt + a1xt-1 +......+at

定理：假设HLFSR方程（Ni）用（1）定义，辅助函数的根为a1 ，...，al，根的重数分别为m1 ，m2 ，...，ml，m1 +m2 +...+ml =t。Ni =P1（i）α1i +P2（i）α2i +...+Pl（i）αli ，Pi（i）是一个最大次数为ml -1的多项式，当辅助等式只有一个重数是t的根α时，及（x-α）t =0，那么Ni =N（i）αi，N（i）表示为A0+A1i+...+At-1 it-1（2），其中N（i）是一个次数最多为t-1的多项式。

2.1 基于身份的密钥隔离签名方案的定义

在基于身份的密钥隔离签名方案当中，是由六个算法构成，这六个算法描述如下：IBKIS=（Setup，Extract，HelperUpt，UserUpt，Sign，Verify）：

（1）系统建立算法Setup（k，N）： 当安全参数和时间片段总数的输入分别为k和N，则算法输出系统公开参数param和相应的系统主密钥msk。

（2） 私钥提取算法Extract（msk，param，ID）：当输入用户身份信息ID、系统主密钥msk及系统公开参数param时，则算法为用户ID生成初始私钥TKID，0和协助器密钥HKID。

（3） 协助器密钥更新算法HelperUpt（param，t，t'，ID，HKID）：当输入系统公开参数param、用户身份信息ID、协助器密钥HKID及时间片段参数t和t'，则算法生成UIID，t，t'，UIID，t，t'将作为用户ID的临时私钥时间片段t更新到t'所需的更新信息。

（4） 私钥更新算法UserUpt（param，t，t'，ID，UIID，t，t'，TKID，t）： 当输入系统公开参数param、时间片段参数t和t'、用户身份信息ID、临时私钥TKID，t、以及更新信息UIID，t，t'，则算法输出时间片段t'的临时私钥TKID，t'，并将TKID，t和UIID，t，t'删除。

（5） 签名算法Sign（param，t，M，TKID，t）：当输入系统公开参数param、消息M、用户身份信息ID、时间片段参数t和对应的临时私钥TKID，t，则算法输出签名（t，σ）。

（6） 签名验证算法Verify（param，（t，σ），M，ID）：当输入系统公开参数param、签名（t，σ）、消息M和身份信息ID，则算法输出为1（当签名有效时）或为0（签名无效时）。

2.2 基于身份的强密钥隔离签名方案在标准模型下的定义

（1）Setup：给定一个安全参数k，PKG首先选择α∈Zq*，g2∈G1且令g1 =gα ，然后选择u'和m'生成两个向量、，L1与L2表示为两个函数，主密钥msk=g2α ，则公开参数param=（G1，G2，e，q，g，g1，g2，u'，m'，，，H1，H2，L1，L2）。

（2）Extract：给定身份信息ID，PKG随机选取一个协助器密钥HKID∈{0，1}k，其中kID，0 =FHK（0 || ID）。如果输入F的长度小于k，在最前面进行添加0以满足长度要求；PKG随机选择r∈Zq*和初始密钥TSKID，0。

（3） UpdH：給定身份信息ID、两个时间片段t1和t2、协助器生成kID，t和kID，t、则通过返回协助器更新私钥UKID，t，t。

（4）UpdS ：给定时间片段t1、协助器更新私钥UKID，t，t、这两个时间片段内的临时私钥TSKID，t和TSKID，t，得到时间片段t内的临时私钥TSKID，t。

（5）Sign ：在时间片段t内，通过签名者ID对应的临时签名私钥TSKID，t，为消息m生成签名σ。

（6）Verify ：签名σ、身份信息ID与消息m，验证者是否接受此签名取决于σ=（t，g2α ·L1（U'ID）r ·L1（U'ID，t ） ·L2（Mm ），g，g，g）是否成立。

2.3 困难性假设

假设G是一个加法群，则有：

（1） 离散对数困难问题：给定两个P，Q∈G，要找出一个正整数n∈Zq*，使之满足Q=nP是困难的。

（2）CDH问题：对于a，b∈Zq*，P∈G，给定（P，aP，bP），计算abP是困难的。

2.4 非交互的离散对数等式知识证明协议

设G是q阶乘法群，g与h是它的两个生成元，证明者P利用α∈Zq*来满足α=log gG =log hH，证明者P要让验证者V相信他确实知道秘密信息α，但不泄露α的值。

3 一种新型基于身份的密钥隔离数字签名方案实现

本节首先通过形式化定义一些系统参数，然后设计一个新型基于身份密钥隔离数字具体签名方案。

3.1 形式化定义

参数设置：1n表示系统安全参数、t和t'表示任意两个不同的时间片段、n表示智能手机的个数、签名者的身份信息用ID表示，SPKi表示第i（i=1，2，...，n）个智能手机的密钥、UKID，t表示身份信息为ID的签名者在第t个时间片段内的签名私钥、MID表示第i（i=1，2，...，n）个智能手机的密钥演化信息，这n个中任意k个智能手机均由差值多项式计算出系统的密钥演化信息MIDID，t，t'，且协助签名者实现临时签名私钥的更新。

一中新型基于身份的密钥隔离数字签名方案由六个多项式算法组成，这些算法分别表示为（Setup，Extract，HelperUpt，UserUpt，Sign，Verify），以下对这些算法进行详细描述。

（1） 系统初始建立算法Setup（1n）：输入系统安全参数1n，输出系统公开参数param和主密钥mask。

（2） 初始私钥生成算法Extract（mask，param，ID）：输入系统公开参数param、主密钥mask以及签名者的身份信息ID，输出签名者的初始签名私钥UKID，0及智能手机的密钥SPK。

（3） 智能手机密钥更新算法HelperUpt（param，t，t'，ID，SPK）： 输入系统公开参数param、任意两个时间片段t和t'、签名者的身份信息ID及智能手机密钥SPK，输出密钥演化信息MIDID，t，t'，该密钥演化信息MIDID，t，t'协助签名者将其临时签名私钥由时间片段t更新到时间片段t'。

（4） 临时签名私钥更新算法UserUpt（param，t，t'，ID，MIDID，t，t'，UKID，t）：输入系统公开参数param，任意两个时间片段t和t'、签名者的身份信息ID、时间片段t内的临时签名私钥UKID，t及密钥演化信息MIDID，t，t'，输出时间片段t'内的临时签名私钥UKID，t'，然后把UKID，t和MIDID，t，t'删除。

（5） 签名算法Sign（param，t，M，UKID，t）：输入系统公开参数param、时间片段t、消息M及时间片段t内的签名者临时签名私钥UKID，t，输出签名者在时间片段t内对消息M的签名（t，ID，U，V）。

（6） 对应签名的验证算法Verify（param，（t，ID，U，V）M，ID）：输入系统公开参数param、签名（t，ID，U，V）、消息M及签名者的身份信息ID，如果签名（t，ID，U，V）是签名者在时间片段t内对消息M的有效签名，则算法最终输出1，否则算法输出0。

3.2 具体方案

3.2.1系统初始建立算法

算法通过执行如下步骤生成系统公开参数param以及系统主密钥mask，参数param是公开，而系统主密钥mask由PKG秘密保存。

（1） 设一个加法群G和一个乘法群GT ，而且它们的阶都是素数p，同时设群G的两个生成元分别为P与P'及一个双线性映射e：G×G→GT 。

（2） 选取四个单向的哈希函数：H1：{0，1}*→G，H2：{0，1}*→G，H3：{0，1}*×GT →Zp*，H：{0，1}*→G。

（3） 随机选取一个整数s∈Zp* ，并令系统公钥Ppub=s·P，用户公钥Upub=s-1·UKID，t 。

（4） 算法输出系统主密钥及系统公开参数：系统主密钥为mask=s，而系统公开参数为param=（G，GT，e，p，P，P'，Ppub ，H1，H2，H3）。

3.2.2 私钥生成算法

输入系统主密钥mask，签名者身份信息ID∈（0，1）*及系统公开参数param，PKG为签名者生成初始私钥和智能手机密钥的步骤有几个。

（1） 随机选取一个SPK∈Zp*，然后构造一个齐次线性递归序列，选择两个强素数m、n，使得N=mn，选择一个与φ（N）互素的整数c，计算d，使得cd=1modφ（N），计算I0 =gd modN并公布（c，N）。n个参与者选择自己的秘密Si，计算Ii =gSi modN后发送给PKG，PKG计算SPKi=IidmodN，SPKi≠SPKj，且当i≠j时。

（2）N0 =SPK1 ，N1 =SPK2 ，...，Nt-1 =SPKt

Ni+t +a1 Ni+t-1 +...+aiNi =0mod P，其中i?0。计算Ni（t?i?n+1），计算Yi=Ii-Ni （t?i?n）和r=SPK-Nn+1，公开（I0 ，I1 ，...，In ，r，Yt+1 ，...，Yn ）。第j个参与者对第i个参与者进行验证，第i个子密钥为SPKi =I0Si modN，假设第i个参与者提供的份额为SPKi'，则第j个参与者计算（SPKi' ）c modN=Ii'。如果Ii'=Ii，则没有欺骗，否则有欺骗。

（3） 由LID=SPK·H（ID）·P和QID，0 =s·H1（ID）+SPK·H（ID）·H2（ID，LID，0）计算出LID和QID，t ；同时令初始私钥UKID，0 =（QID，0 ，LID ）。

（4）该算法最终将会输出签名者的初始私钥UKID，0以及第i个智能手机的密钥SPKi =（SPK（i）·H（ID），LID），同时算法还会向所有的智能手机广播一个对SPKi的承诺hi =SPK（i）·H（ID）·P'以验证密钥的正确性。

3.2.3 第i个智能手机的密钥更新算法

当智能手机在收到签名者的私钥更新请求之后，第i个智能手机就会执行这个密钥更新算法，得到自己持有的部分密鑰更新信息。输入系统公开参数param，时间片t和t'及第i个智能手机的密钥SPKi ，算法最终将会输出第i个智能手机持有的部分密钥更新信息MID=SPKi ·H（ID）·（H2（ID，LID，t'）-H2（ID，LID，t））。

3.2.4 签名者执行的临时签名私钥更新算法

在某个特定的时间片段内，签名者执行的临时签名私钥更新算法为五个步骤，执行完毕后，签名者的临时签名私钥将会从时间片段更新到时间片段t'。

（1） 首先将时间片段t内的临时签名私钥UKID，t按照UKID，t =（QID，t ，LID ）进行分解。

（2） 使用非交互的离散对数等式知识证明协议，第i个智能手机向签名者验证自己所提供的部分密钥更新信息MID是正确的。由3.2.2与3.2.3可以知道，第i个智能手机知道一个对SPKi的承诺hi =SPK（i）·H（ID）·P'以及部分密钥更新信息MID=SPKi ·H（ID）·（H2（ID，LID，t'）-H2（ID，LID，t））。由离散对数的零知识证明可知，第i个智能手机在知道SPK（i）的前提下，很容易就能够计算出下列等式成立log=log，所以也就可以验证第i个智能手机输出的部分密钥更新信息MID为正确。

（3）n個智能手机中任意k个均可插值得到完整的密钥演化信息MID，且完整的密钥演化信息MID=C（x）·Smod p；其中，n个智能手机中任意k个智能手机组成的一个群体用B表示，插值系数多项式为C（x）=mod p，Si =MID。

（4） 计算QID，t' =QID，t +MID，并将时间片段t'的签名者临时私钥更新为UKID，t' =（QID，t' ，LID ）。

（5） 输出时间片段t'的临时私钥UKID，t' ，并将UKID，t和MID删除。

3.2.5 签名算法

在时间片段t内，签名者利用该时间片段内签名者的临时私钥UKID，t，按如下步骤对消息M进行签名。

（1） 随机选取k∈Zq*，计算r=e（P，P'）k；

（2） 计算V=H3（M，r）；

（3） 计算U=kP'+V·UKID，t，则对消息M的签名是（t，ID，U，V），且签名属于GT ×Zq*。

3.2.6 对应签名的验证算法

输入系统公开参数param、签名（t，ID，U，V）、签名者身份信息ID及消息M，验证者按如下步骤验证签名的有效性。

（1） 用户的公钥Upub =s-1·UKID，t；

（2） 计算r=e（U，P）e（Upub ，Ppub ）V，验证：当且仅当V=H3（M，r）时验证者认为此签名正确。

4 新型的基于身份的密钥隔离签名方案分析

本节对所设计方案的安全性和效率分别进行分析。

4.1 安全分析

一个良好的方案满足三个安全性。

（1）（k，N）密钥隔离安全性：在群G上的CDH问题是难解的，从而所有智能手机的部分密钥都是在安全的前提下，当攻击者没有截取到超过k个时间片段内用户的签名私钥，攻击者将不能伪造用户的签名。在这种情形下，该方案满足了密钥隔离安全性。

（2） 强密钥隔离安全性：在本方案中，用户签名私钥是由时间片段t时的临时签名私钥及其他智能手机的密钥共同参与计算得到的，即使攻击者是截取到其他智能手机的密钥或者时间片段t内的临时签名私钥中的任意一个，都不能伪造用户在时间片段t'内的签名私钥。通过多重保护，该方案具有强密钥隔离安全性。

（3） 安全密钥更新：如果签名者在将临时私钥从UKID，t更新到UKID，t'时，攻击者截获了时间片段t内的临时私钥UKID，t及密钥更新信息MID，那么除时间片段t及t'之外的时间片段系统还是安全的，从而系统密钥更新足够安全。

正确性：e（U，P）=e（kP'+V·UKID，t ，P）

=e（kP'，P）e（V·UKID，t ，P）

=e（P，P'）k e（UKID，t ，P）V

=r·e（sUpub ，P）V

=r·e（Upub ，Ppub ）V

则可验证：r=e（U，P）e（Upub ，-Ppub ）V

=r·e（Upub ，Ppub ）V·e（Upub ，-Ppub ）V=r

4.2 效率分析

在效率分析当中，我们从强密钥隔离、安全密钥更新、时间片段数目及是否满足前向后向安全的性能上将本方案与其他签名方案进行具体对比分析，结果如表1所示。

我们还从签名、验证、可证明安全及签名长度这四方面将本方案与其他签名方案进行具体对比分析，结果如表2所示。

5 结束语

数字签名作为信息安全的一项重要技术，已经在许多领域得到运用。而随着越来越多的密码算法被应用到不安全的环境密钥泄露在所难免。本文提出了一个基于身份的密钥隔离签名方案，该方案通过多个智能手机的协助，签名者的签名私钥做到随时间变化，保证了签名的前向和向后安全性，使得攻击者伪造签名者签名的机会大大减少，从而降低了应用于安全较低的设备中基于身份密码系统密钥泄露风险，提高了系统对密钥泄露所造成危害的容忍度。同时该方案采用高效的签名算法，能够满足于签名者在智能手机端的频繁更新私钥后进行签名的要求，一定程度上解决了密钥泄露与密钥管理的问题，并且方案在保证前向与后向安全的前提下，只需要很少的计算资源、存储资源和通信资源，因此适用于智能手机等资源受限的环境中。

参考文献

[1] Diffie W and Hellman M. New Direction in Cryptography[J]. IEEE Transactions on Information Theory.1976，IT-22（6）： 644-654.

[2] Rivest R， Shamir A and Adleman L. A method for obtaining digital signatures and public key cryptosystems[J]. Communications of ACM，1978，21（2）： 120-126.

[3] SHAMIR A. How to share a secret[J]. Communications of ACM，1979，22（11）： 612-613.

[4] Shamir A. Identity-Based Cryptosystems and Signature Schemes[J]. Lecture Notes in Computer Science，1995，21（2）：47-53.

[5] Dodis Y， Katz，Xu and Yung M. key-insulated public-key cryptosystems[C].In Advances in Cryptology-Eurocrypt 02， LNCS 2332，Springer-Verlag，2002，pp. 65-82.

[6] Yevgeniy Dodis， Jonathan Katz， Shouhuai Xu. Strong Key-Insulated Signature Schemes[J]. Lecture Notes in Computer Science，2002，2567（2567）：130-144.

[7] Hess F.Efficient Identity Based Signature Schemes Based on Pairings[J].Selected Areas in Cryptography. Springer Berlin Heidelberg，2003：310-324.

[8] 杜瑞颖， 刘亚斌， 刘建东， 等. 无证书密钥隔离签名方案[J]. 山东大学学报，2014，49（9）： 24-28.

[9] 秦志光， 刘京京， 赵洋， 等. 密钥隔离密码系统研究现状[J].计算机学报， 2015，38（4）： 759-774.

[10] 尋甜甜，于佳，杨光洋，等.密钥隔离的无证书聚合签名[J]. 电子学报，2016，44（5）： 1111-1116.

[11] 元振杨，陈建华，吴黎兵.具有后向安全的认证密钥协商协议[J]. 小型微型计算机系统，2016，37（7）： 1398-1401.

[12] 翁健， 陈克非，刘胜利，等. 标准模型下基于身份的强密钥隔离签名[J]. 软件学报，2008，19（6）： 1555-1564.

基金项目：

1. 国家自然科学基金（61662009，61262073，61363068）；

2. 贵州省教育厅青年科技人才成长项目（黔教合KY字[2016]169）；

3. 贵州省科技基金计划项目（黔科合基础[2016]1023）。

作者简介：

刘易（1991-），女，汉族，贵州贵阳人，毕业于贵州大学，硕士学位；主要研究方向和关注领域：密码学、信息安全、大数据隐私保护。

彭长根（1963-），男，汉族，贵州锦屏人，毕业于贵州大学，博士学位，教授，博士生导师；主要研究方向和关注领域：密码学、信息安全、大数据隐私保护。