本文实践了指纹识别生物特征识别研究论文A Fuzzy Vault Scheme的算法部分。原文请查看以下链接：
Juels, A. & Sudan, M. Des Codes Crypt (2006) 38: 237. doi:10.1007/s10623-005-6343-z
准备知识：
1.有限域/伽罗华域(Galois Field，GF)
2.RS编码和纠错算法RS(Reed-Solomon)码
3.多项式构建和重构
4.模糊保险箱Fuzzy Vault
5.Talk is cheap,show me the code
1.有限域/伽罗华域(Galois Field，GF)
RS(Reed-Solomon)码在伽罗华域(Galois Field，GF)中运算的，因此在介绍RS码之前先简要介绍一下伽罗华域。
CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2) = GF(2)中的元素或称符号。GF(2)表示域中有256个元素，除0，1之外的254个元素由本原多项式P(x)生成。本原多项式的特性是
得到的余式等于0。CD-ROM用来构造GF(2)域的
是
(13－1)
而GF(2)域中的本原元素为
α = (0 0 0 0 0 0 1 0)
下面以一个较简单例子说明域的构造。
[例13.1] 构造GF(2)域的本原多项式假定为
α定义为 = 0的根，即
α＋α＋1 = 0
和 α = α＋1
GF(2)中的元素可计算如下：
0 | mod(α＋α＋1) = 0 |
α | mod(α＋α＋1) = α = 1 |
α | mod(α＋α＋1) = α |
α | mod(α＋α＋1) = α |
α | mod(α＋α＋1) = α＋1 |
α | mod(α＋α＋1) = α＋α |
α | mod(α＋α＋1) = α＋α＋1 |
α | mod(α＋α＋1) = α＋1 |
α | mod(α＋α＋1) = α |
α | mod(α＋α＋1) = α |
…… |
用二进制数表示域元素得到表13-01所示的对照表
表13-01 GF(2)域中与二进制代码对照表,
GF(2)域元素 | 二进制对代码 |
0 | (000) |
α | (001) |
α | (010) |
α | (100) |
α | (011) |
α | (110) |
α | (111) |
α | (101) |
这样一来就建立了GF(2)域中的元素与3位二进制数之间的一一对应关系。用同样的方法可建立GF(2)域中的256个元素与8位二进制数之间的一一对应关系。在纠错编码运算过程中，加、减、乘和除的运算是在伽罗华域中进行。现仍以GF(2)域中运算为例：
加法例：α＋α = 001＋011
= 010 = α
减法例：与加法相同
乘法例：α·α = α
= α
除法例：α/α = α
α/α = α
= α
= α
取对数：log(α) = 5
这些运算的结果仍然在GF(2)域中。
2.RS编码和纠错算法RS(Reed-Solomon)码
RS的编码就是计算信息码符多项式除以校验码生成多项式
之后的余数。
在介绍之前需要说明一些符号。在GF(2)域中，符号(n，k)RS的含义如下：
m | 表示符号的大小，如m = 8表示符号由8位二进制数组成 |
n | 表示码块长度， |
k | 表示码块中的信息长度 |
K=n－k = 2t | 表示校验码的符号数 |
t | 表示能够纠正的错误数目 |
例如，(28，24)RS码表示码块长度共28个符号，其中信息代码的长度为24，检验码有4个检验符号。在这个由28个符号组成的码块中，可以纠正在这个码块中出现的2个分散的或者2个连续的符号错误，但不能纠正3个或者3个以上的符号错误。
对一个信息码符多项式，RS校验码生成多项式的一般形式为
(13－2)
式中，m是偏移量，通常取K = 0或K = 1，而(n-k)≥2t (t为要校正的错误符号数)。
下面用两个例子来说明RS码的编码原理。
[例13.2] 设在GF(2)域中的元素对应表如表13-01所示。假设(6，4)RS码中的4个信息符号为m、m、m和m，信息码符多项式为
(13－3)
并假设RS校验码的2个符号为Q和Q，的剩余多项式
为
这个多项式的阶次比的阶次少一阶。
如果K = 1，t = 1，由式(13－2)导出的RS校验码生成多项式就为
=
(13－4)
根据多项式的运算，由式(13－3)和式(13－4)可以得到
mx＋mx＋mx＋mx＋Qx＋Q = (x－α)(x－α)Q(x)
当用x = α和x = α代入上式时，得到下面的方程组，
经过整理可以得到用矩阵表示的(6，4)RS码的校验方程：
求解方程组就可得到校验符号：
在读出时的校正子可按下式计算：
[例13.3] 在例13.2中，如果K = 0，t = 1，由式(13－2)导出的RS校验码生成多项式就为
=
(13－5)
根据多项式的运算，由(13－3)和(13－5)可以得到下面的方程组：
方程中的α也可看成符号的位置，此处i = 0，1，…，5。
求解方程组可以得到RS校验码的2个符号为Q和Q，
(13－6)
假定m为下列值：
信息符号 | m = α = 001 m = α = 101 m = α = 011 m = α = 100 |
校验符号 | Q = α = 101 Q = α = 110 |
校正子 | s = 0 s = 0 |
代入(13－6)式可求得校验符号：
Q = α = 101
Q = α = 110
13.2.3 RS码的纠错算法
RS码的错误纠正过程分三步： (1)计算校正子(syndrome)，(2)计算错误位置，(3)计算错误值。现以例13.3为例介绍RS码的纠错算法。
校正子使用下面的方程组来计算：
为简单起见，假定存入光盘的信息符号m、m、m、m和由此产生的检验符号Q、Q均为0，读出的符号为m′、m′、m′、m′、Q′和Q′。
如果计算得到的s和s不全为0，则说明有差错，但不知道有多少个错，也不知道错在什么位置和错误值。如果只有一个错误，则问题比较简单。假设错误的位置为α，错误值为m，那么可通过求解下面的方程组：
得知错误的位置和错误值。
如果计算得到s = α和s = α，可求得α = α和m = α，说明m出了错，它的错误值是α。校正后的m = m′＋m ，本例中m=0。
如果计算得到s = 0，而s≠0，那基本可断定至少有两个错误，当然出现两个以上的错误不一定都是s = 0和s≠0。如果出现两个错误，而又能设法找到出错的位置，那么这两个错误也可以纠正。如已知两个错误和
的位置
和
，那么求解方程组：
就可知道这两个错误值。
CD-ROM中的错误校正编码CIRC和里德-索洛蒙乘积码(Reed Solomon Product－likeCode，RSPC)就是采用上述方法导出的。
3.多项式构建和重构
4.模糊保险箱Fuzzy Vault
5.Talk is cheap,show me the code
clear all;
addpath('./src/');
addpath('./src/recover/');
addpath('./src/reconstruct/');
%##########################加锁过程####################################
% work over GF(2^16): 在Galois 2^16 有限域工作
FIELD = 16;
% degree of polynomial 多项式多少次方
DEGREE = 35;
% number of chaff points to generate:
NUM_CHAFFS = 30;
% define tolerance for adequate length-checks RS纠错码的纠错度
TOLERANCE = 2;
key='1234567890';%要使用绑定的key 10bit
n=length(key)+TOLERANCE; k=length(key); % Codeword and message word lengths
msgKey = gf(double(key),FIELD); % e.g. gf(key,16) 密钥 生成gf数组 Galois field array GF Create a Galois field array.
msgKeyRS = rsenc(msgKey,n,k);%key生成RS码 以及多项式
points=[ 3 4 5 6 7 8 9 10 11 12 13 14];%points 我们12个点 点的个数是key长度+2 看你码字长度
ply = gf(msgKeyRS,FIELD);
X = gf(points',FIELD);
Y = evaluate(X,ply,FIELD);
mprojection = [ X Y ];
% ===== C. Mix up the projected points with chaff points: =====
chaffs = gf(zeros(NUM_CHAFFS,2),FIELD);% initialize set of chaff points to zeros:
MINDIST=1;%最小距离为1
for count=1:NUM_CHAFFS % ===== 2.1. keep generating random points until we generate 'numChaffs' =====
% ===== 2.2. generate a random point (a,b) in the field =====
%rndmPt = gf(randi((2^FIELD - 1),1,2),FIELD);%randi((2^FIELD - 1),1,2) ans= 37026 41963
rndmPt = gf(randi((2^FIELD - 1),1,2),FIELD);%randi((2^FIELD - 1),1,2) ans= 37026 41963
% ===== 2.3. check to make sure that it can be added ===== -- FIX
% if (a,b) is > minDist away from any point of `points`, add it
%if (computeDist(points,rndmPt,FIELD) > MINDIST)
chaffs(count,:) = rndmPt;
%end
end
% ===== 2.4. remove zeros from chaff point set ===== -- FIX
%chaffs( ~any(chaffs,2), : ) = [];
% ===== 2.5. sort points and merge chaffs with points 至此我们得到保险箱=====
%保险箱由vault 映射点We refer to the set R and 以及the parameter triple (k; t; r) together as a fuzzy v ault, denoted by VA
vault = sortrowsGF([ chaffs ; mprojection ],FIELD);
打开锁，拿到我们的 key
%##########################解锁过程####################################
testpoints=[ 3 4 5 6 7 8 9 10 11 12 13 19];%points 我们12个点 点的个数是key长度+2 看你码字长度 指纹细节点 解锁
testpoints = gf(testpoints',FIELD); % e.g. gf(key,16)
% 解锁做的就是
%1 找出和vault最接近的点
% 2.获取我们应该用的解锁数据
% 3.解锁 获取多项式参数 然后RS解码
% define shorthands:
vaultLength = size(vault,1);
numPts = size(testpoints,1);
% ===== 1. Sort vault based on distance to closest query point: =====
% define column vector of distances:
dists = zeros(vaultLength,1);
overlapointscount=0;
vaultOverlapping= zeros(1,1);
for idx=1:vaultLength
dists(idx) = computeDist1D(testpoints,vault(idx,1),FIELD);
if (dists(idx)<1)
overlapointscount=overlapointscount+1;
vaultOverlapping(overlapointscount)=idx;
end
end
decodeFactor=decodePolynomial(vault(vaultOverlapping,:),FIELD,length(testpoints)-1);%解多项式
fieldKey = rsdec(decodeFactor,n,k);%解码
% initialize `key` as empty string:
key = '';
% convert each coefficient into a string and append to key:
for idx=1:(length(fieldKey))
% convert each coefficient into char and append:
key = strcat(key,fieldToAscii(fieldKey(idx),FIELD));
end
key运行截图