关于插值问题的讨论

关于插值问题的讨论

1关于线性域xk的子问题本文讨论了f（pn.1）中的插值问题（简化记录为问题q）及其应用。问题Q对于预先给定的n+1对离散数据(xi,yi),i=0,1,2,…,n;xi,yi∈GF(P),xi互不相同,寻找t阶多项式:Pt(x)=(a0+a1x+…+atxt)modp(1≤t≤n,p是素数),(1)使得对于任意的t+1个不同下标构成的集合{i0,i1,…,it}⊆{0,1,2,…,n},有Pt(xk)=yk,k=i0,i1,…,it.(2)可以注意到:t=n,xi,yi∈R,式(1)不进行mod运算时,上述问题为实数域插值问题,该问题由著名的Lagrange插值公式和Newton插值公式可得到解决;当t=n,xi,yi∈GF(P),式(1)进行mod运算时,上述问题为有限域上的插值问题.利用乘法逆元概念和中国剩余定理,1979年Shamir得到了Shamir-Lagrange插值公式,且成功解决了1≤t≤n-1时的秘密共享问题,该问题可视作Lagrange插值公式在密码学的应用.1989年Lash,Harm,Slee利用Newton插值公式设计了单钥匙一锁存取控制,但未见报道Newton插值公式被应用于信息隐藏中.本文给出了信息隐藏的一种数学描述,在第一节介绍了GF(P)中的乘法逆元概念及其求法,且给出了GF(Pn)上的Newton插值公式,在第二节中讨论范德蒙逆矩阵计算问题,且给出了本文所提插值问题有解的判断条件,最后一节讨论了本文研究结果在信息隐藏中的应用,且提供了算例.2cvd1定义1设n是一正整数,a是整数,如果用n去除a,得商为整数q,余数为整数r,则a=q*n+r,此时记r≡amodn.定义2对于整数x,若有整数y,使得x*y≡1modp,则称y是x的模p运算下的倒数,也称为乘法逆元,常记为y≡x-1modp.引理1设a∈{0,1,2,…,p-1}且gcd(a,p)=1,则a在模p运算下有乘法逆元.引理2(Fermat定理)若p是素数,a是正整数且gcd(a,p)=1,则ap-1≡1modp.引理3(Euler定理)若a和n互素,则aφ(n)≡1modn,φ(n)为数n的Euler函数,即φ(n)为小于n,且与n互素的所有正整数的个数.引理4对于整数a和b,一定存在整数x和y,使得ax+by=gcd(a,b).特别地,当gcd(a,b)=1时,x≡a-1modb.注定义2,引理2,3,4给出了求乘法逆元的方法.定义3对于给定的素数p和数据(xi,yi),i=0,1,2,…,n;xi,yi∈GF(P),递推定义均差如下:0阶均差f[xi]=f(xi),一阶均差f[xi,xj]=(f[xi]-f[xj])(xi-xj)-1,二阶均差f[xi,xj,xk]=(f[xi,xj]-f[xj,xk])(xi-xk)-1,………k-1阶均差f[xi1,xi2,…,xik]=(f[xi1,xi2,…,xik-1]-f[xi2,xi3,…,xik])(xi1-xik)-1,这里(xi-xj)-1是xi-xj在模p运算下的乘法逆元,f(xi)=yi.由上述均差定义和插值条件易得:定理1(Newton插值理论)对于给定的离散数据(xi,yi),i=0,1,2,…,n;xi,yi∈GF(P),设有多项式N(x)=(a0+a1(x-x0)+a2(x-x0)(x-x1)+…+an(x-x0)(x-x1)(x-xn-1))modp满足N(xi)≡f(xi)modp,这里f(xi)=yi(i=0,1,2,…,n),则系数为均差a0=f[x0],a1=f[x0,x1],…,an=f[x0,x1,…,xn].3基于lix的逆矩阵定义1对于方阵A=(aij),aij∈GF(P),若A可逆,且A-1=A*|A|A−1=A∗|A|,这里A*为A的伴随矩阵,|A|=detA,则称B=|A|-1A*modp为方阵A在模p运算下的逆矩阵,仍记为A-1.引理5对于预先给定的n+1对离散数据(xi,yi),i=0,1,2,…,n,xi互不相同,可唯一构造n次多项式f(x)=a0+a1x+a2x2+…+anxnmodp满足f(xi)=yi(i=0,1,2,…,n),且(a0,a1,…,an)T=A-1(y0,y1,…,yn)T.这里A是由互异数据x0,x1,…,xn构造的范德蒙矩阵A(x0,x1,…,xn),且记其逆矩阵为V=A-1=(vij).引理6对于预先给定的n+1对离散数据(xi,yi),i=0,1,2,…,n,xi互不相同,可唯一构造的n次多项式具有Lagrange形式f(x)=n∑i=0∑i=0nyili(x),这里li(x)=(x-x0)(x-x1)⋯(x-xi-1)(x-xi+1)⋯(x-xn)(xi-x0)(xi-x1)⋯(xi-xi-1)(xi-xi+1)⋯(xi-xn).li(x)=(x−x0)(x−x1)⋯(x−xi−1)(x−xi+1)⋯(x−xn)(xi−x0)(xi−x1)⋯(xi−xi−1)(xi−xi+1)⋯(xi−xn).注意到引理5中而引理6中,设li(x)=n∑j=0∑j=0ncjixi,且构造矩阵C=(cji),即由基1,x,x2,…,xn过渡到基l0(x),l1(x),…,ln(x)过渡矩阵为C,从而f(x)=(l0(x),l1(x),⋯,ln(x))(y0y1⋮yn)=(1,x,x2,⋯,xn)C(y0y1⋮yn).f(x)=(l0(x),l1(x),⋯,ln(x))⎛⎝⎜⎜⎜⎜y0y1⋮yn⎞⎠⎟⎟⎟⎟=(1,x,x2,⋯,xn)C⎛⎝⎜⎜⎜⎜y0y1⋮yn⎞⎠⎟⎟⎟⎟.由插值多项式唯一性知,范德蒙矩阵A的逆矩阵V=A-1=C,此时说明通过计算Lagrange基函数li(x)中xj项的系数cji可得范德蒙矩阵V的元素vij.于是整理Lagrange基函数li(x)中xj的系数有结论(详见文献):定理2对于预先给定的n+1对离散数据(xi,yi),i=0,1,2,…,n,xi互不相同,唯一构造n次多项式f(x)=n∑i=0∑i=0naixi=n∑i=0∑i=0nyili(x),若设li(x)=n∑i=0∑i=0ncjixi,则范德蒙逆矩阵元素为vij=cji=(-1)n-jσn-j(x0,x1,…,xi-1,xi+1,…,xn)(F′(xj))-1,这里σr(x1,x2,…,xm)=∑1<i1<i2<i3<⋯<ir∑1<i1<i2<i3<⋯<irxi1xi2…xir(r=0,1,2,…,m)表示字母x1,x2,…,xm的初等对称多项式,F(x)=n∏i=0∏i=0n(x-xi),F′(xj)=n∏i=0i≠j∏i=0i≠jn(xj-xi).又容易由引理5得到:定理3(问题Q有解的判断条件)对于预先给定的n+1对离散数据(xi,yi),i=0,1,2,…,n;xi,yi∈GF(P),xi互不相等.现有两个含t+1个不同下标的集合Ω1={i0,i1,…,it}⊆Ω,Ω2={j0,j1,…,jt}⊆Ω,这里Ω={0,1,2,…,n},那么两插值多项式完全相等的充要条件为p(i)t(i)t(x)=p(j)t(j)t(x)⇔A-1Ω1−1Ω1*(yi0,yi1,…,yit)T=A-1Ω2−1Ω2*(yj0,yj1,…,yjt)T,这里:p(i)t(i)t(x)是由Ω1对应的离散数据对(xik,yik),(k=0,1,2,…,t)唯一构造的t次多项式,p(j)t(j)t(x)是由Ω2对应的离散数据对(xjk,yjk),(k=0,1,2,…,t)唯一构造的t次多项式,AΩ1和AΩ2分别是由互异数据xi0,xi1,…,xik和xj0,xj1,…,xjk构造的范德蒙矩阵.4基于一定数量的秘密共享/秘密分割在导弹控制发射等重要场所的进入检验过程中,通常必须由两人或多人同时参与才能生效,这时需要将主密钥(或秘密)分成若干个子密钥交给多人掌管,且必须有一定数量掌管子密钥的人同时到场才能恢复这一主密钥.处理这一类秘密共享或秘密分割事情通常使用密码学中的(t,n)门限方案,即秘密S被分成n个部分信息,每一部分信息由一参与者持有,确保①由t个或多于t个参与者所持有的部分信息可重构S;②由少于t个参与者所持有的部分信息则无法重构S.可以注意到本文讨论的问题Q是(t,n)门限方案的一种数学描述,(t,n)门限方案常用于信息隐藏中.下面给出本文研究结果在密码学信息隐藏中的应用.一、生成解析点设(x0,y0),…,(xt-1,yt-1)是平面上t个点构成的点集,其中xi(i=0,…,t-1)均不相等,那么由插值理论知,存在唯一的t-1次多项式f(x)通过这t个点.若把秘密S取作多项式f(x)的若干特征信息,例取成函数值f(0),S派生的n个子秘密取作f(xi)(i=0,1,…,n-1),n≥t-1,那么利用其中任意t个子秘密可重构f(x),从而得到主秘密S,达到秘密分存或信息隐藏的目的.二、机数主秘密的解析通常组织者(庄家)根据参与者人数n选取一个大素数p,满足p≥n+1,在GF(P)-{0}上任取一个随机数作为主秘密S,任选一个t次多项式f(x)≡a0+a1x+…+atxtmodp,这里ai∈GF(P)-{0},i=0,1,2,…,t,满足f(x)的若干特征信息就是S,例取成函数值或向量值.不妨记n个参与者为P1,P2,…,Pn,IDi为Pi的身份识别码,庄家分配给参与者的子秘密为f(IDi).三、基于范德蒙逆矩阵的向量信息隐藏如果n个参与者中任意t个参与者pi0,pi1,…,pit-1(1≤i0<i1<…<it-1≤n)同时到场,要想得到主秘密S,可使用离散数据{(IDi,f(IDi))/i=i0,i1,…,it-1}构造出多项式f(x),得到预先约定的若干特征信息,从而得到主秘密S.应用一基于Newton插值公式实现的信息隐藏方案.方法:在上述操作过程中,由离散数据{(IDi,f(IDi))/i=i0,i1,…,it-1}构造出Newton插值多项式f(x)=f(ID0)+f[ID0,ID1](x-ID0)+f[ID0,ID1,ID2](x-ID2)(x-ID1)+…+f[ID0,ID1,…,IDt-1](x-ID0)(x-ID1)(x-ID2)…(x-IDt-2).可取函数值f(0)为主秘密S=f(0)=f(ID0)+f[ID0,ID1](-ID0)+…+f[ID0,ID1,…,IDt-1]*(-ID0)*(-ID1)*…*(-IDt-2).算例:在(3,5)门限方案中,设p=19,主秘密S=11,庄家选定的多项式为f(x)≡(7x2+2x+11)mod19.试完成:1)计算庄家分配给5个成员的子秘密f(1),f(2),f(3),f(4),f(5);2)5个成员中的3个人相应的ID号为2,3,5,现同时在场且提供所分配的子秘密为f(2),f(3),f(5),试由GF(P3)上Newton插值公式重构f(x),得主秘密即函数值f(0).解1)容易计算出庄家分配给5个成员的子密钥为f(1)=1,f(2)=5,f(3)=4,f(4)=17,f(5)=6.2)用Newton插值公式求主秘密,首先构造均差表:于是构造出Newton插值多项式:f(x)≡f+f(x-2)+f(x-2)(x-3)mod19≡7x2+2x+11mod19.或计算f(0)≡f+f(-2)+f(-2)(-3)mod19≡11mod19.所以主秘密为f(0)=11.应用二基于范德蒙逆矩阵实现的向量信息隐藏方案.方法:在上述操作过程中,由离散数据{(IDi,f(IDi))/i=i0,i1,…,it-1}构造出范德蒙矩阵A(ID0,ID1,…,IDt-1),且求其逆矩阵V,计算出向量S=VY,这里Y=(f(ID0),…,f(IDt-1))T,视向量S为主秘密.这里S是多项式f(x)=a0+a1x+a2x2+…+at-1xt-1对应的系数向量(a0,a1,…,at-1)T.算例:在(4,7)门限方案中,设p=17,庄家选定的多项式为f(x)=(13+10x+2x2+9x3)mod17,主秘密为向量S=(13,10,2,9)T,试完成:①计算庄家分配给7个成员的子秘密f(1),f(2),f(3),f(4),f(5),f(6),f(7);②现7个成员中有4个人同时在一起,相应的ID号为1,3,5,7,提供所分配的子秘密有f(1),f(3),f(5),f(7),试计算范德蒙逆矩阵,求出主秘密向量S.解①容易计算出庄家分配给7个成员的子秘密f(1)=0,f(2)=1,f(3)=15,f(4)=15,f(5)=14,f(6)=15,f(7)=4.②用范德蒙逆矩阵求主秘密.首先构造范德蒙矩阵,且求其逆,此时由ID号1,3,5,7构成的范德蒙矩阵为A=(1111133233155253177273)‚A-1=V=(vij).A=⎛⎝⎜⎜⎜⎜1111135713252721335373⎞⎠⎟⎟⎟⎟‚A−1=V=(vij).不妨记ID号分别为x0=1,x1=3,x2=5,x3=7,可以计算出g1=((x0-x1)(x0-x2)(x0-x3))-1mod17≡6,g2=((x1-x0)(x1-x2)(x1-x3))-1mod17≡16,g3=((x2-x0)(x2-x1)(x2-x3))-1mod17≡1,g4=((x3-x0)(x2-x1)(x2-x3))-1mod17≡11.从而根据定理2中式(2)计算出范德蒙逆矩阵元素如下:v11=-x1x2x3g1≡16mod17；v12=-x0x2x3g2≡1mod17；v13=-x0x1x3g3≡13mod17；v14=-x0x1x2g4≡5mod17；v21=(x1x2+x2x3+x1x3)g1≡2mod17；v22=(x0x2+x0x3+x2x3)g3≡4mod17；v23=(x0x1+x0x3+x1x3)g3≡14mod17；v24=(x0x1+x0x2+x1x2)g4≡15mod17；v31=-(x0+x1+x3)