一个基于指纹特征的密钥保存与生成算法

张国伟， 游 林

（1.海南师范大学 数学与统计学院，海南 海口 571158；2.杭州电子科技大学 通信工程学院，浙江 杭州310018）

一个基于指纹特征的密钥保存与生成算法

张国伟1， 游 林2

（1.海南师范大学 数学与统计学院，海南 海口 571158；2.杭州电子科技大学 通信工程学院，浙江 杭州310018）

生物特征密码系统提供了生物特征与传统密码学的有机结合.生物特征密钥可在隐藏用户的生物特征信息的同时，安全实现密钥的生成、恢复以及认证的多重功能.本文提出了一个基于指纹特征的密码密钥保存与生成算法.实验结果表明，密钥的成功恢复率可达到91％左右，具有一定的实际应用意义.

指纹；生物特征；（t，n）门限；密钥生成

在密码体制中，密钥的安全保护是最关键的安全性问题.密码技术广泛应用于信息安全的诸多领域中，不论是对称密码系统还是公钥密码体制，其安全性均依赖于密钥或者私钥本身安全性.在密码系统中，密钥的安全性至关重要.为了防止密钥被突破而采取长度更长的强密钥来保证系统的安全性，但对于一般用户保管长密钥是不可能的，通常采用用户口令来加密保存用户的密钥［1-2］.但是口令容易受到字典式穷举猜测攻击，而生物特征的使用可以有效避免这种攻击［2］.

生物特征是用来识别个体的唯一的身份或者行为特征.理论上说，任何人的生理或行为特征均可以作为一个人的身份标志，因为它满足四个条件，即普遍性、可区分型、可再生性和可采集性［1，3-4］.基于生物特征的加密研究集中在密钥生成的问题上，即考虑如何将生物特征转换为一个唯一的密钥，该密钥不能由其他人体的生物特征中生成，更不能由冒名顶替者的生物特征中生成，这正是本文将要讨论的.

Zhang等人则提出了face hashing来保存信息，并利用Shamir密钥共享机制来恢复用户密钥［5］. Charles等人在文献［6］中提出的是一种称为指纹窖（Fingerprint Vault）的方案，它是将采集的指纹细节点坐标mi编码成某一有限域F中的元素，将密钥编码成F[x]中的一个多项式f（x）.多项式f（x）在指纹细节点处取得赋值，并将数对（mi，f（mi））与满足条件di≠f（ci）的随机伪装点（ci，di）一起存储.合法的用户可通过其指纹特征分离出足够多的数对（mi，f（mi）），进而重构多项式f（x），从而获取密钥.上述方法均不是直接地存储生物特征模块和密钥，而是存储一个由事先选定的密钥与生物特征绑定在一起产生的一个模块，或者可能还有某个参数，然后再输入生物特征图像就可以重构或恢复密钥.它们有一个根本无法解决的问题，那就是生物特征要求能够非常准确的抵御随机噪声的影响.Charles等人的方法实际上是基于Juels等人提出的模糊窖（Fuzzy Vault）方案［7］，并没有直接将指纹数据用做密码意义上的密钥，而是通过合法使用者的生物特征数据来安全地储存与恢复密钥.本文借鉴该算法，经过修改后用于生成基于指纹的加密密钥.

1 基于生物特征的密钥生成

大部分研究者主要开展基于生物特征的认证，该认证与基于生物特征的密钥生成有着根本的差异.前者是基于具有用户模板的分类器来区分已认证的用户和冒名顶替者；后者是将用户的生物特征转换为唯一密钥，该密钥不能从冒名顶替者的生物特征中生成.Chang等人［8］提出了了一种基于生物特征生成密钥的框架（见图1）.

图1 生物特征密钥生成概念图Fig.1 The concept map of biometric key generation

收集可信用户和其他用户的生物特征作为样本数据，进行一个用户的特征变换.因为可信用户变换过的特征在变幻特征空间是紧凑的，而其他用户，假定为冒名顶替者的特征要么分散，要么与可信用户的特征远离.因此，可信用户变换过的特征与冒名顶替者的特征是可区分的.然后，一个稳定的密钥生成机制用来生成一个稳定的加密密钥.根据可区分度，每个变换的特征可能贡献加密密钥生成信息的一到多位.所以，不仅生成了稳定的密钥，同时密钥也扩大了密钥空间以抵抗穷搜索攻击.可区分特征生成的目标是找到一个变换使得每个已变换的特征是可区分的，能够把可信用户与潜在的冒名顶替者区分开.

稳定密钥根据特征的可区分性生成稳定的密钥.对于一个特征，如果可信均值与全局均值的距离大于可信标准方差的k倍，则认为该特征是可区分的，否则基于Shamir的秘密共享方案抛弃该特征［9］.生物特征密钥系统将传统的密钥Key与生物特征Bio进行有机结合，生成安全性较高的生物特征密钥Bio-key.

2 指纹特征集合的生成

相对于人的其它生物特征来说，指纹特征数据提取技术的研究要成熟得多，并且取得了丰富的学术成果.与其它生物统计学特征相比，指纹特征更容易提取、预处理、更可信，且特征尺寸也很小，有利于数据的保存与处理.所以本文主要研究利用指纹特征来产生密码意义上的密钥.人的指纹特征有总体特征和局部特征两种类型［1，5］.在密钥生成研究中我们采用指纹的局部特征.局部特征是指在指纹拓扑图中的集中有效的特征，它是指纹密钥的最基本的依据.即便是两种指纹的总体特征相同，但是它们的局部特征却不可能完全相同.美国国家标准测量局NISTC（National Institute of Stardards and Testing）提出了一种指纹细节分类方式，将指纹特征分为四类：端点、分叉点、复合点和未定义特征，而最为重要的细节特征就是端点和分叉点［1］（见图2）.

而在密码编码中，需要在二进制向量空间中考虑，目的是更好地进行计算机识别与运算.设某类指纹特征的平均和标准差分别为mc和δc，则

设全局指纹特征和标准差分别为mg和δg，则

则指纹特征的二进制描述符可以定义为：

3 一种基于（t，n）门限的指纹密钥生成算法

本文研究利用指纹特征数据来产生可用于密码算法中的密钥.（t，w）门限方案是一种特殊的秘密共享方案，我们采用门限方法来构造利用指纹特征数据产生密码密钥的方案或算法.生物特征密钥的生成主要涉及到生物特征描述符B（i）与传统密钥Key的运算.为了保证系统生成安全性较高的生物特征密钥，采用（t，n）门限的算法.其主要的思想是将B（i）和Key分割为对等的n份影子，利用拉格朗日插值多项式的方法，使得其中的任意t份影子可以生成Bio-key，而小于t的任何影子无法生成密钥Bio-key.结合文献提出的算法，给出基于指纹特征的密钥生成算法和恢复算法.

定义1［10］设t和w是正整数，t≤ w，一个（t，w）门限方案是一种在w个参与者中分享一个密钥k的方法，使得任意t个参与者再给出它们的秘密份额后可以恢复密钥k，而任意t-1个参与者在给出他们的秘密份额后不能恢复密钥k.

选择一个素数p，使之比可能的影子数目和最大可能秘密都大.共享密钥时，需要产生一个次数为m-1的任意多项式.例如：如果打算形成一个（3，n）门限方案，则产生一个二次多项式，（ax2+bx+ M）mod p，其中p是一个比任何系数都大的随机素数.系数a，b伪随机选择，它们是秘密的，在分发完影子之后便丢弃.M是消息，素数必须公开.

影子通过计算多项式在几个不同点上的值得到：ki=F（xi），意思就是第一个影子就是多项式在x=1处的值，第二个影子就是多项式在x=2处的值，以此类推.

由于二次多项式有三个未知系数a，b和M，因此，任意3个影子都能用来建立3个方程.2个影子则不能，1个影子也不能，4或5个影子则是多余的.

例如，设M=11，构造（3，5）门限方案.

首先生成一个二次方程，F（x）=（5x2+6x+ 11）mod17，5个影子是：

为了从3个影子（比如k1，k2，k3）来重构M，需要解线性方程组：

解得a=5，b=6，M=11，这样就恢复了M.

这个共享方案对于较大的数也是很容易实现的.秘密共享的惊人方面是，如果系数随机选择，即便是有无限的计算能力的人也不能得到除消息的长度外的任何东西（消息长度每个人都知道）.这个方案像一次一密乱码本一样安全，任何想解开消息的穷举搜索的企图都可能是无效的.本算法经过改进用于指纹密钥生成的加密过程.

3.1 密钥生成算法

1）随机生成at-1，at-2，…，a1，r作为拉格朗日多项式的系数，构成GF（p）上的一个t-1次多项式f（x）=at-1xt-1+at-2xt-2+… +a1x+r∈RZp[x].随机生成一个密钥key，并将其分成n份子密钥，使得key=（key1，key2，…，keyn）并计算 ki=fi（keyi）mod p，其中i=1，2，…，n；

2）采用（n，k）汉明编码对子密钥ki编码得到码字Cki，将ki输入一个编码函数Encoder（），计算Encoder（ki）=Cki，其中i=1，2，…，n；

3）设认证阶段用户A的指纹特征数据为X，系统为其建立特征描述符B（i），从而得到（B1，B2，…，Bl）；

4）系统根据Encoder（ki）=Cki和用户指纹特征描述符B（i），计算 δi=Cki⊕Bi，其中i=1，2，…，n，⊕表示在GF（2l）上按位异或运算；

5）存储n个部分（δi，ki）作为生物特征密钥，

4 密钥生成实验与结果分析

由这个算法的过程可以看出：此生物特征密钥信息中没有包含明显的用户特征信息，可以有效的阻止用户生物信息的泄露，并且不能直接得到密钥，所以是安全可靠的.

3.2密钥恢复算法

1）设用户B提供生物特征数据X′，系统为其建立特征描述符B（i）′，得到（B1′，B2′，…，Bl′）；

2）计算Cki，其中Cki=δi⊕Bi′；

3）Cki为具有传输错误的编码，只要提供的B（i）′与B（i）的距离在一定的范围内，就可以用（n，k）Hamming码对Cki做解码，所以ki′=decode（Cki）.

生物特征密钥的生成算法和密钥恢复算法是两个互逆的算法，只有在用户的指纹特征的差异在系统的容忍度范围内，才可以进行有效地加密和解密操作.同时通过门限密码机制，对生物特征信息和生物特征密钥信息提供了安全性的保证.

由dc和dg的关系，在试验中选取了dg=0，dc= {-0.5，0，0.5}时，根据验证样本来重构用户的密钥.实验结果见图7.在dc=0.5时，密钥的恢复成功率更高，其中密钥成功恢复试验见图5，其是在图3试验条件下的密钥恢复实验结果，而冒名顶替者不能恢复合法密钥，如图6所示.可以看出，合法用户可以在系统的容忍度范围内恢复他的密钥.在采用100个指纹图像来试验时，可以达到91个成功恢复，成功率为91％.由此可以看出，选择合适的参数，密钥的恢复率完全可以达到预期设计目标.

5 结语

本文利用门限方案提出了基于指纹特征的密钥生成办法.利用指纹数据产生密钥，省却了密钥保存系统，既安全、快捷，又经济、实用.例如当你要对某一数字文件进行签名时，你只要输入你注册的（活体）指纹，相应的系统就可产生密钥而对文件进行数字签名，签名后的文件发送给对方.对方可通过CA获取你注册指纹的相应公钥来验证你的签名.如果这样的指纹生成密钥技术研究随着技术的进一步成熟，将非常适用在电子政务、电子商务中安全、经济、快速地实现信息加解密与签名认证.这个过程防止了对用户生物特征的攻击，同时也防止了密钥在服务器上的直接保存.用户的数据安全性完全是由用户的生物特征决定，用户的数据完全由自己保存，可以确定拥有密钥的就是用户本人.由实验结果可以看出，门限密钥生成方法与指纹系统的识别率有关系.生物特征提取识别上能够有更为精确可靠的算法来提高生物特征识别率，就可以使得指纹密钥的生成与恢复有更好的效果.当然，可以采用虹膜、人脸、掌纹等识别方法进行密钥生成与恢复，这些也是很有价值研究的内容.在编码上也可以采用RS编码等编码方法，其中引入椭圆密码与超椭圆密码算法也都是很好的借鉴，都是值得研究的内容.

［1］Maltoni D，Maio D，Jain A K，et al.Handbook of Fingerprint Recognition[M].Berlin：Springer Verlag，2003.

［2］Monrose F，Reiter MK，LI Q.Cryp tographic key generation froMvoice[C].IEEESymposiuMon Security and Privacy，2001：202-213.

［3］Soutar C，Tomko G J.Secure private key generation using a fingerprint[C].proc of Cardtech/Securetech Conference-

表2 “中国印”奥运会会徽的寓意Tab.2 The iMplication of the“Chinese marking”O lyMpic Games emblem

2010年上海世博会会微图案形似汉字“世”，并与数字“2010”巧妙组合，相得益彰，表达了中国人民举办一届属于世界的、多元文化融合的博览盛会的强烈愿望.会徽中三人合臂相拥的图形，形似美满幸福，相携同乐的三口之家；也可抽象概括为“你、我、他”的全人类，表达了世博会“理解、沟通、欢聚、合作”的理念，洋溢着崇尚和谐、聚合的中华民族精神，体现了2010年上海世博会以人为本的积极追求.

参考文献

［1］张舒予.视觉文化概论[M].南京：江苏人民出版社，2003：1-66.

［2］何平静.平面设计视觉语言符号元素研究 [J].艺术教育，2008（10）：114-115.

［3］刘芬.数字媒体设计[M].北京：清华大学出版社，1999：28-32.

［4］勒埭强.视觉传达设计实践[M].上海：上海文艺出版社，2005：19-34.

［5］郑斌.融合中国传统文化元素的产品创新设计研究[J].考试周刊，2008（7）：55-59.

［6］郭峰.中国传统文化元素在现代标志设计中的应用[J].河南工业大学学报：社会科学版，2006，2（2）：98-101.

［7］徐沛君，梁梅.中国印能否承载文化之重—2008年北京奥运会会微设计引发的讨论[J].美术观察，2003（9）：18-19.

责任编辑：毕和平

参考文献

［1］詹森，王辉丰.关于构造高阶幻方的新方法[J].海南师范大学学报：自然科学版，2009，22（3）：133-134.

［2］詹森，王辉丰.奇数阶对称完美幻方的构造方法[J].海南师范大学学报：自然科学版，2009，22（4）：396-398.

［3］王辉丰，詹森.关于构造三类奇数阶幻方的新方法 [J].海南师范大学学报：自然科学版，2010，23（1）：12-15.

［4］吴鹤龄.幻方及其他[M].北京：科学出版社，2004：50-80.

责任编辑：黄 澜

An AlgorithMfor Cryptographic Key Keeping and Generation Based on Fingerprint Features

ZHAN Guowei1，YOU Lin2
（1.College of Mathematics and Statistics，Hainan Normal University，Haikou 571158，China；2.School of Communication Engineering，Hangzhou Dianzi University，Zhejiang 310018，China）

The biometric cryptographic systeMcan provide the integration of biological features and the traditional cryptology.The use of biological keys can not only hide the user's biological feature information but also realize safe key generation，recovery and authentication.This paper proposes a scheme for secure key keeping and generation based on fingerprint features.The experimental results indicate that the success rate of the key recovery is about 91％，and it shows our algorithMis highly efficient and is of practical significance.

fingerprint；biometrics；threshold（t，n）；key generation

O 29；TP 309.7

A

1674-4942（2010）02-0147-05

2010-03-10

国家自然科学基金项目（60763009）；海南省教育厅高校科研项目（hjkj200616）