談密碼學(xué)中的門限方案

談密碼學(xué)中的門限方案

1基于拉格朗日插值利益的秘密共享秘密分割和秘密共享是秘密理論的重要研究內(nèi)容。所謂秘密共享，是指分派者將秘密分割成若干個子秘密給予多個互相不信任的參與者共享，使得這些參與者只有在出示足夠多個數(shù)或滿足預(yù)先定義的資格子集合的子秘密后才能夠恢復(fù)秘密。秘密共享最初由AdiShamir和GeorgeBlakley兩人分別提出，并由GusSimmons做了更廣泛的研究。文獻(xiàn)提出了秘密共享的思想，文獻(xiàn)中提到的對密鑰的分割保護(hù)也是秘密共享的思想。本文實現(xiàn)了一個基于拉格朗日插值多項式的秘密共享方案。使用該方案，可以將任何信息（包括密鑰）分割為若干份，必須同時具有其中的不少于特定多個部分合作才能合成原始信息。下面將先闡述秘密共享的思想，然后介紹拉格朗日插值原理，最后給出對該方案的實現(xiàn)及在加密卡上的實際應(yīng)用。2門限方案將符合產(chǎn)市秘密共享：是指將要保密的信息分割為n個碎片，必須需要其中的不少于t個碎片才可以合成該保密信息。這樣可以防止秘密因為一個或少量碎片泄露的原因而變得不安全。秘密共享的安全性基礎(chǔ)是承認(rèn)這n個碎片中，至少t個是可信任的。而門限方案能夠?qū)崿F(xiàn)更為復(fù)雜的秘密共享。影子：秘密分割后得到的碎片，每一部分稱為一個影子“shadow”或共享“share”。伽羅瓦域：有限域GF(p）被稱為伽羅瓦域。在該域上，非零元的加、減、乘、除均有定義。有一個加法單位元0和乘法單位元1。每一個非零數(shù)都有唯一的逆元。交換律、結(jié)合律和分配律在該域上均成立。3拉格朗日插值方案3.1基于拉格朗日程式的秘密共享算法構(gòu)造文獻(xiàn)介紹了一種基于拉格朗日多項式的秘密共享方案。方案介紹如下：選擇一個素數(shù)p，使之比可能的影子數(shù)目和最大可能秘密都大。共享秘密時，須產(chǎn)生一個次數(shù)為m-1的任意多項式。如果打算形成一個（3,n）門限方案，則需要產(chǎn)生一個二次多項式：其中p是一個比所有系數(shù)都大的隨機(jī)素數(shù)。系數(shù)a和b是隨機(jī)選擇的，他們是秘密的，在分發(fā)完影子之后就被丟棄。M是要分割的消息，p必須公開。影子通過計算該多項式在不同點上的值得到，即分別取n個不同的x代入上述多項式，可計算得到影子1到影子n。而對于上述多項式，由于p是公開的，即p已知，所以只有三個未知數(shù)a、b和消息M。而只需要一個三元方程組，即可求出該二次多項式的三個未知數(shù)。令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個影子就可恢復(fù)原來的信息M，而其余影子可以看作是多余的。對于基于拉格朗日多項式的秘密共享方案，如果要構(gòu)造（m,n）門限，即如果要將秘密分割為n個影子，需要其中不少于m個影子才可以恢復(fù)秘密，那么需要構(gòu)造m-1次多項式：根據(jù)該多項式構(gòu)造原有信息M的公式為：其中C(i）=productof(X(j）/（X(i）-X(j））)forallj!=i,1≤i,j≤m,Y(i）為所用到的m個影子中的一個，X(i）為生成影子Y(i）所取的x的值。注意，上述多項式中，多項式的系數(shù)ai是隨機(jī)取到的。3.2基于原始信息合成的函數(shù)對于一個（m,n）門限，該方案每次讀入原始信息的8個bit，對每8個bit數(shù)據(jù)的高4個bit和低4bit數(shù)據(jù)，分別構(gòu)造一個m-1次多項式，產(chǎn)生n個影子。所有這8個bit數(shù)據(jù)的第i個影子（1≤i≤n）合成原始信息的第i個影子。首先，實現(xiàn)了一個伽羅瓦域GF(24）上的加、乘和除運算。為了實現(xiàn)乘和除運算，定義了一個乘積表，一個倒數(shù)表。a與b乘運算采用查乘積表的方法快速實現(xiàn)，而a與b的除運算用a乘以b在GF(24）上的倒數(shù)（逆元）來實現(xiàn)，而a和b都是4bit的數(shù)，即a與b都不大于15。然后，實現(xiàn)了一個生成4bit隨機(jī)數(shù)的函數(shù)，該函數(shù)返回一個整型的隨機(jī)數(shù)，該隨機(jī)數(shù)的前28bit為0，后4bit為不大于15的隨機(jī)數(shù)。實現(xiàn)一個函數(shù)Process(intNibble,int*OutArray），該函數(shù)將4個bit的數(shù)據(jù)作為輸入，生成m-1個隨機(jī)數(shù)，構(gòu)造一個m-1次多項式，按照上面提到的方法，求出這4個bit數(shù)據(jù)的n個影子，每個影子占用一個整型（32bit）的低4bit。并將這n個影子連在一起，在OutArray中輸出。原始信息的合成，采用的方法是從原始信息的m個影子中，每次分別取出8bit數(shù)據(jù)，根據(jù)上面提到的方法，計算C[i]和Y[i]，逐次的恢復(fù)原始信息的8個bit數(shù)據(jù)，直到最后恢復(fù)完全的原始信息。我們實現(xiàn)一個函數(shù)FillNibbles(int*Nibbles,unsignedchar*ches,intRequired），用來根據(jù)m個影子中的相應(yīng)的8個比特的數(shù)據(jù)得到多項式在x取不同值時的m個不同多項式值，存在Nibbles數(shù)組中。Ches中依次放著m個影子的8bit數(shù)據(jù)，Required恢復(fù)原始信息需要的最少影子數(shù)，即m。3.3秘密恢復(fù)方案秘密分割流程：每次從原始信息中讀取一個字節(jié)的數(shù)據(jù)，做以下操作：(1）對該字節(jié)數(shù)據(jù)的高4bit，調(diào)用Process函數(shù)，生成這4bit數(shù)據(jù)的m個影子，放在HighNibbles這個整型數(shù)組中。(2）對該字節(jié)數(shù)據(jù)的低4bit，調(diào)用Process函數(shù)，生成這4bit數(shù)據(jù)的m個影子，放在LowNibbles這個整型數(shù)組中。(3）產(chǎn)生這一個字節(jié)數(shù)據(jù)的m個影子。將HighNibbles[i]（1≤i≤m）左移4位，與LowNibbles[i]（1≤i≤m）相加，得到原始信息這個字節(jié)的第i個影子。(4）將每次生成的第i個影子合成原始信息的第i個影子。秘密恢復(fù)流程：設(shè)需要m個影子來恢復(fù)原始信息，恢復(fù)方法如下：(1）分別從m個影子中讀出8bit的影子數(shù)據(jù)。(2）構(gòu)造多項式系數(shù)C[i]（0≤i≤m-1）。(3）調(diào)用FillNibbles得到Y(jié)[i]（0≤i≤m-1）。(4）由C[i]和Y[i]根據(jù)上面提到的思想，得到原始信息M的8bit數(shù)據(jù)。(5）將所有恢復(fù)得到的8bit數(shù)據(jù)合在一起，就恢復(fù)出原始信息M。本文對該方案采用C語言進(jìn)行了實現(xiàn)，測試結(jié)果使用良好?？梢詫⑷我忾L度的原始數(shù)據(jù)分割為n個影子，n≤15?？梢詷?gòu)造不同的門限，如（2,3）門限、（3,5）門限等。并且能利用最少門限值個影子恢復(fù)原始數(shù)據(jù)。4在加密卡上的應(yīng)用程序中4.1dsp芯片指標(biāo)的選取加密卡是插在計算機(jī)PCI插槽上的接口卡，主要由DSP數(shù)字信號處理芯片、隨機(jī)數(shù)發(fā)生器、PCI接口芯片、讀卡器等部件組成?？梢詫崿F(xiàn)數(shù)據(jù)加密解密、密鑰管理、數(shù)據(jù)完整性驗證、數(shù)字簽名認(rèn)證等功能。同時，與主機(jī)、外圍設(shè)備和系統(tǒng)軟件具有良好的接口，方便用戶開發(fā)應(yīng)用層軟件。加密卡設(shè)計和實現(xiàn)的關(guān)鍵是選擇一個合適的DSP數(shù)字信號處理芯片。在操作上，應(yīng)該根據(jù)實際需求綜合考慮DSP芯片各方面的指標(biāo)，主要包括以下幾個方面的因素：(1）運算速度：包括以下指標(biāo)：指令周期、MAC時間、FFT執(zhí)行時間、MIPS、MOPS、MFLOPS、BOPS等。(2)DSP芯片的價格、功耗、開發(fā)工具。(3)DSP芯片的硬件資源：如：片內(nèi)RAM、ROM、總線接口、I/O接口等。(4)DSP芯片的運算精度：如TMS320系列的字長為16位。(5）其他：如供貨情況、生命周期等?？紤]到以上的因素，我們最終選用的是TI公司的TMS320C54X系列芯片。TMS320系列DSP芯片具有哈佛結(jié)構(gòu)、流水線操作、專用的硬件乘法器、特殊的DSP指令和快速的指令周期等優(yōu)點。而其中我們所選用的C54X系列DSP芯片運算速度快、價格低廉并且產(chǎn)品成熟。指令周期為10ns，主頻已經(jīng)達(dá)到100MHz以上，運算能力也能達(dá)到100MIPS以上，并且采用同一套指令系統(tǒng)，具有很好的向下兼容性，可以降低用戶軟件開發(fā)的成本。4.2使用sf33算法處理數(shù)據(jù)的秘密共享加密卡所實現(xiàn)的加密解密、數(shù)字簽名和恢復(fù)、雙機(jī)熱備等功能，都依賴于密鑰的安全性。所以，為防止因加密卡硬件損壞或卡內(nèi)密鑰等信息被非法刪除，保證系統(tǒng)可靠性，將系統(tǒng)受到的影響降到最小，加密卡需要能夠提供對卡內(nèi)密鑰進(jìn)行備份和恢復(fù)的功能。我們所實現(xiàn)的就是基于拉格朗日插值多項式算法的秘密共享，采用（3,5）門限的方式實現(xiàn)，將密鑰進(jìn)行分割，以智能IC卡為信息載體，分發(fā)給多個備份管理員。當(dāng)需要用到該密鑰的時候，再由半數(shù)以上的管理員進(jìn)行恢復(fù)。具體的實現(xiàn)步驟如下：備份卡內(nèi)密鑰：(1）用戶提出備份卡內(nèi)信息的申請；(2）半數(shù)以上的管理員口令驗證通過；(3）密碼卡生成用于加密卡內(nèi)信息的隨機(jī)對稱密鑰，可以采用SSF33算法，將卡內(nèi)信息加密后輸出給用戶保存；(4）利用上面提到的秘密共享方案，將隨機(jī)密鑰分成5分，輸出到5張IC卡中，作為密鑰備份卡，分別由5位備份管理員掌握；(5）密碼卡內(nèi)將臨時生成的隨機(jī)密鑰和共享密鑰碎片銷毀?；謴?fù)加密卡內(nèi)密鑰信息：(1）讀取3張以上的密鑰備份卡中的密鑰碎片到卡內(nèi)，利用上面所實現(xiàn)的秘密共享算法恢復(fù)密鑰；(2）使用恢復(fù)出來的密鑰，通過SSF33算法，解密輸入的信息，并存放到卡內(nèi)存儲區(qū)；(3）刪除卡內(nèi)的臨時密鑰和共享密鑰碎片。4.3網(wǎng)絡(luò)系統(tǒng)評估4.3.1正確分析本方案的正確性主要依賴于拉格朗日插值多項式的正確性。這一點在上面3.1中已經(jīng)進(jìn)行了論述。4.3.2s14x系列dsp芯片介紹上述方案是通過TITMS320C54XDSP芯片實現(xiàn)的。C54X系列DSP芯片是一種具有特殊結(jié)構(gòu)的微處理器。內(nèi)部采用程序和數(shù)據(jù)分開的哈佛結(jié)構(gòu)，具有專用的硬件乘法器，流水技術(shù)可使多個不同的操作并行執(zhí)行，從而保證了快速的數(shù)據(jù)處理能力。4.3.3密鑰的恢復(fù)—安全性分析對密鑰的備份在一定程度上保證了系統(tǒng)的安全性，防止因人為或者系統(tǒng)本身出現(xiàn)問題而導(dǎo)致不安全。首先，對卡內(nèi)信息進(jìn)行加密采用國密辦規(guī)定的SSF33算法，保證了算法的安全性。同時，密鑰由加密卡隨機(jī)生成，只是短時間內(nèi)在加密卡內(nèi)存在，用完后立即卡內(nèi)銷毀，不經(jīng)過內(nèi)存，杜絕了被外界攻擊和強(qiáng)制獲取的可能。其次，采用基于拉格朗日插值多項式的秘密共享的一種實現(xiàn)———（3,5）門限機(jī)制，將密鑰掌握在5個互不交叉信任的管理員手中，而且必須由其中的不少于3個人同時交出手中的秘密碎片，才能將原來的密鑰恢復(fù)。這樣即使少數(shù)管理員無意或有意泄露手中的秘密碎片，系統(tǒng)的安全性和可靠性仍能得到保證。再次，秘密分割后的碎片，不是本機(jī)保存，也不是保存在任何一個管理員的機(jī)器上，而是直接從加密卡中導(dǎo)出至IC卡中，提高了安全性。4.3.4預(yù)動安全技術(shù)盡管具有以上一些安全保證，本方案還是存在一定的缺陷和漏洞。首先，在密鑰備份和恢復(fù)之間的間隔如果是很長的話，那么攻擊者可能會由足夠的時間，發(fā)起不斷的攻擊，而最終獲得恢復(fù)密鑰所需要的秘密份額。在這一點上，Osreovsky和Yung提出了一種預(yù)動安全（ProactiveSecurity）秘密共享方案，對秘密碎片進(jìn)