谈密码学中的门限方案

谈密码学中的门限方案

1基于拉格朗日插值利益的秘密共享秘密分割和秘密共享是秘密理论的重要研究内容。所谓秘密共享，是指分派者将秘密分割成若干个子秘密给予多个互相不信任的参与者共享，使得这些参与者只有在出示足够多个数或满足预先定义的资格子集合的子秘密后才能够恢复秘密。秘密共享最初由AdiShamir和GeorgeBlakley两人分别提出，并由GusSimmons做了更广泛的研究。文献提出了秘密共享的思想，文献中提到的对密钥的分割保护也是秘密共享的思想。本文实现了一个基于拉格朗日插值多项式的秘密共享方案。使用该方案，可以将任何信息（包括密钥）分割为若干份，必须同时具有其中的不少于特定多个部分合作才能合成原始信息。下面将先阐述秘密共享的思想，然后介绍拉格朗日插值原理，最后给出对该方案的实现及在加密卡上的实际应用。2门限方案将符合产市秘密共享：是指将要保密的信息分割为n个碎片，必须需要其中的不少于t个碎片才可以合成该保密信息。这样可以防止秘密因为一个或少量碎片泄露的原因而变得不安全。秘密共享的安全性基础是承认这n个碎片中，至少t个是可信任的。而门限方案能够实现更为复杂的秘密共享。影子：秘密分割后得到的碎片，每一部分称为一个影子“shadow”或共享“share”。伽罗瓦域：有限域GF(p）被称为伽罗瓦域。在该域上，非零元的加、减、乘、除均有定义。有一个加法单位元0和乘法单位元1。每一个非零数都有唯一的逆元。交换律、结合律和分配律在该域上均成立。3拉格朗日插值方案3.1基于拉格朗日程式的秘密共享算法构造文献介绍了一种基于拉格朗日多项式的秘密共享方案。方案介绍如下：选择一个素数p，使之比可能的影子数目和最大可能秘密都大。共享秘密时，须产生一个次数为m-1的任意多项式。如果打算形成一个（3,n）门限方案，则需要产生一个二次多项式：其中p是一个比所有系数都大的随机素数。系数a和b是随机选择的，他们是秘密的，在分发完影子之后就被丢弃。M是要分割的消息，p必须公开。影子通过计算该多项式在不同点上的值得到，即分别取n个不同的x代入上述多项式，可计算得到影子1到影子n。而对于上述多项式，由于p是公开的，即p已知，所以只有三个未知数a、b和消息M。而只需要一个三元方程组，即可求出该二次多项式的三个未知数。令F(x）=（ax2+bx+M)modp如下：x=1,F(x）=a+b+M=影子一x=2,F(x）=4a+2b+M=影子二x=3,F(x）=9a+3b+M=影子三解上述三元方程组可得到a,b和M，即仅通过3个影子就可恢复原来的信息M，而其余影子可以看作是多余的。对于基于拉格朗日多项式的秘密共享方案，如果要构造（m,n）门限，即如果要将秘密分割为n个影子，需要其中不少于m个影子才可以恢复秘密，那么需要构造m-1次多项式：根据该多项式构造原有信息M的公式为：其中C(i）=productof(X(j）/（X(i）-X(j））)forallj!=i,1≤i,j≤m,Y(i）为所用到的m个影子中的一个，X(i）为生成影子Y(i）所取的x的值。注意，上述多项式中，多项式的系数ai是随机取到的。3.2基于原始信息合成的函数对于一个（m,n）门限，该方案每次读入原始信息的8个bit，对每8个bit数据的高4个bit和低4bit数据，分别构造一个m-1次多项式，产生n个影子。所有这8个bit数据的第i个影子（1≤i≤n）合成原始信息的第i个影子。首先，实现了一个伽罗瓦域GF(24）上的加、乘和除运算。为了实现乘和除运算，定义了一个乘积表，一个倒数表。a与b乘运算采用查乘积表的方法快速实现，而a与b的除运算用a乘以b在GF(24）上的倒数（逆元）来实现，而a和b都是4bit的数，即a与b都不大于15。然后，实现了一个生成4bit随机数的函数，该函数返回一个整型的随机数，该随机数的前28bit为0，后4bit为不大于15的随机数。实现一个函数Process(intNibble,int*OutArray），该函数将4个bit的数据作为输入，生成m-1个随机数，构造一个m-1次多项式，按照上面提到的方法，求出这4个bit数据的n个影子，每个影子占用一个整型（32bit）的低4bit。并将这n个影子连在一起，在OutArray中输出。原始信息的合成，采用的方法是从原始信息的m个影子中，每次分别取出8bit数据，根据上面提到的方法，计算C[i]和Y[i]，逐次的恢复原始信息的8个bit数据，直到最后恢复完全的原始信息。我们实现一个函数FillNibbles(int*Nibbles,unsignedchar*ches,intRequired），用来根据m个影子中的相应的8个比特的数据得到多项式在x取不同值时的m个不同多项式值，存在Nibbles数组中。Ches中依次放着m个影子的8bit数据，Required恢复原始信息需要的最少影子数，即m。3.3秘密恢复方案秘密分割流程：每次从原始信息中读取一个字节的数据，做以下操作：(1）对该字节数据的高4bit，调用Process函数，生成这4bit数据的m个影子，放在HighNibbles这个整型数组中。(2）对该字节数据的低4bit，调用Process函数，生成这4bit数据的m个影子，放在LowNibbles这个整型数组中。(3）产生这一个字节数据的m个影子。将HighNibbles[i]（1≤i≤m）左移4位，与LowNibbles[i]（1≤i≤m）相加，得到原始信息这个字节的第i个影子。(4）将每次生成的第i个影子合成原始信息的第i个影子。秘密恢复流程：设需要m个影子来恢复原始信息，恢复方法如下：(1）分别从m个影子中读出8bit的影子数据。(2）构造多项式系数C[i]（0≤i≤m-1）。(3）调用FillNibbles得到Y[i]（0≤i≤m-1）。(4）由C[i]和Y[i]根据上面提到的思想，得到原始信息M的8bit数据。(5）将所有恢复得到的8bit数据合在一起，就恢复出原始信息M。本文对该方案采用C语言进行了实现，测试结果使用良好。可以将任意长度的原始数据分割为n个影子，n≤15。可以构造不同的门限，如（2,3）门限、（3,5）门限等。并且能利用最少门限值个影子恢复原始数据。4在加密卡上的应用程序中4.1dsp芯片指标的选取加密卡是插在计算机PCI插槽上的接口卡，主要由DSP数字信号处理芯片、随机数发生器、PCI接口芯片、读卡器等部件组成。可以实现数据加密解密、密钥管理、数据完整性验证、数字签名认证等功能。同时，与主机、外围设备和系统软件具有良好的接口，方便用户开发应用层软件。加密卡设计和实现的关键是选择一个合适的DSP数字信号处理芯片。在操作上，应该根据实际需求综合考虑DSP芯片各方面的指标，主要包括以下几个方面的因素：(1）运算速度：包括以下指标：指令周期、MAC时间、FFT执行时间、MIPS、MOPS、MFLOPS、BOPS等。(2)DSP芯片的价格、功耗、开发工具。(3)DSP芯片的硬件资源：如：片内RAM、ROM、总线接口、I/O接口等。(4)DSP芯片的运算精度：如TMS320系列的字长为16位。(5）其他：如供货情况、生命周期等。考虑到以上的因素，我们最终选用的是TI公司的TMS320C54X系列芯片。TMS320系列DSP芯片具有哈佛结构、流水线操作、专用的硬件乘法器、特殊的DSP指令和快速的指令周期等优点。而其中我们所选用的C54X系列DSP芯片运算速度快、价格低廉并且产品成熟。指令周期为10ns，主频已经达到100MHz以上，运算能力也能达到100MIPS以上，并且采用同一套指令系统，具有很好的向下兼容性，可以降低用户软件开发的成本。4.2使用sf33算法处理数据的秘密共享加密卡所实现的加密解密、数字签名和恢复、双机热备等功能，都依赖于密钥的安全性。所以，为防止因加密卡硬件损坏或卡内密钥等信息被非法删除，保证系统可靠性，将系统受到的影响降到最小，加密卡需要能够提供对卡内密钥进行备份和恢复的功能。我们所实现的就是基于拉格朗日插值多项式算法的秘密共享，采用（3,5）门限的方式实现，将密钥进行分割，以智能IC卡为信息载体，分发给多个备份管理员。当需要用到该密钥的时候，再由半数以上的管理员进行恢复。具体的实现步骤如下：备份卡内密钥：(1）用户提出备份卡内信息的申请；(2）半数以上的管理员口令验证通过；(3）密码卡生成用于加密卡内信息的随机对称密钥，可以采用SSF33算法，将卡内信息加密后输出给用户保存；(4）利用上面提到的秘密共享方案，将随机密钥分成5分，输出到5张IC卡中，作为密钥备份卡，分别由5位备份管理员掌握；(5）密码卡内将临时生成的随机密钥和共享密钥碎片销毁。恢复加密卡内密钥信息：(1）读取3张以上的密钥备份卡中的密钥碎片到卡内，利用上面所实现的秘密共享算法恢复密钥；(2）使用恢复出来的密钥，通过SSF33算法，解密输入的信息，并存放到卡内存储区；(3）删除卡内的临时密钥和共享密钥碎片。4.3网络系统评估4.3.1正确分析本方案的正确性主要依赖于拉格朗日插值多项式的正确性。这一点在上面3.1中已经进行了论述。4.3.2s14x系列dsp芯片介绍上述方案是通过TITMS320C54XDSP芯片实现的。C54X系列DSP芯片是一种具有特殊结构的微处理器。内部采用程序和数据分开的哈佛结构，具有专用的硬件乘法器，流水技术可使多个不同的操作并行执行，从而保证了快速的数据处理能力。4.3.3密钥的恢复—安全性分析对密钥的备份在一定程度上保证了系统的安全性，防止因人为或者系统本身出现问题而导致不安全。首先，对卡内信息进行加密采用国密办规定的SSF33算法，保证了算法的安全性。同时，密钥由加密卡随机生成，只是短时间内在加密卡内存在，用完后立即卡内销毁，不经过内存，杜绝了被外界攻击和强制获取的可能。其次，采用基于拉格朗日插值多项式的秘密共享的一种实现———（3,5）门限机制，将密钥掌握在5个互不交叉信任的管理员手中，而且必须由其中的不少于3个人同时交出手中的秘密碎片，才能将原来的密钥恢复。这样即使少数管理员无意或有意泄露手中的秘密碎片，系统的安全性和可靠性仍能得到保证。再次，秘密分割后的碎片，不是本机保存，也不是保存在任何一个管理员的机器上，而是直接从加密卡中导出至IC卡中，提高了安全性。4.3.4预动安全技术尽管具有以上一些安全保证，本方案还是存在一定的缺陷和漏洞。首先，在密钥备份和恢复之间的间隔如果是很长的话，那么攻击者可能会由足够的时间，发起不断的攻击，而最终获得恢复密钥所需要的秘密份额。在这一点上，Osreovsky和Yung提出了一种预动安全（ProactiveSecurity）秘密共享方案，对秘密碎片进