基于希爾密碼的秘密共享方案

（銅陵職業(yè)技術(shù)學(xué)院，安徽銅陵244000；云南大學(xué)，云南昆明650091）

一、秘密共享相關(guān)知識(shí)

秘密共享是在一組確定的成員之間分配和共享一定的數(shù)據(jù)信息，該數(shù)據(jù)信息只有在先前確定的授權(quán)用戶共同參與下才能得到還原。

秘密共享方法基本上可以分為兩條主線：一是采用不同的數(shù)學(xué)方法，二是應(yīng)對(duì)不同的實(shí)際問(wèn)題需求，本文研究的是后者。

在現(xiàn)實(shí)問(wèn)題中，有些場(chǎng)合需要秘密份額可以重復(fù)使用的情況下在同一組參與者中共享一個(gè)秘密。本文通過(guò)引入希爾密碼體制，設(shè)計(jì)基于希爾密碼的秘密共享方案。

二、希爾密碼相關(guān)知識(shí)

（一）希爾密碼

希爾密碼是一種基于矩陣原理的替換密碼，由Letter S.Hill在1929年研發(fā)。每個(gè)字母由26進(jìn)制數(shù)字替換：如a=0，b=1，c=2，…。一串字母組成的m維向量，與一個(gè)m×m 的矩陣相乘后將得出的數(shù)值模26，值得注意的是這里用作加密的矩陣（即秘鑰）必須是可逆的，不然就不能解密。其實(shí)，只需要秘鑰矩陣的行列式值與26互質(zhì)即可。

（二）構(gòu)造希爾密碼體制

取一個(gè)矩陣A（保密），要求A可逆，且A的行列式與26互質(zhì)，取字母表，這里用原始字母表（a=0，b=1，…，z=25）。

根據(jù)上述參數(shù)，構(gòu)造希爾密碼體制如下：

加密矩陣：A

明文：P轉(zhuǎn)化為小于26的數(shù)字序列

密文：C轉(zhuǎn)化為小于26的數(shù)字序列

加密算法：C=PA

解密算法：P=CA-1

（三）希爾密碼加解密舉例

1.加密（由C=PA）

（1）定義字母表

（2）定義一個(gè)矩陣A（必須存在逆矩陣）作為加密秘鑰，例如：

（3）取加密明文，如明文為：I agree.

圖1

（4）將需要加密的明文數(shù)字化為其對(duì)應(yīng)的字母表里的數(shù)字（這里不需要區(qū)分大小寫(xiě)）。

（5）將轉(zhuǎn)換后的明文數(shù)字序列按照秘鑰矩陣的階數(shù)進(jìn)行分組，如：

（6）每組數(shù)字序列和秘鑰矩陣行矩陣的乘法運(yùn)算，結(jié)果即為密文矩陣，如：

（7）將密文矩陣根據(jù)字母表轉(zhuǎn)化為對(duì)應(yīng)的字母（在此要記錄下數(shù)字在矩陣中的位置），從而得到密文字符串，如：上例的密文字符串為：I a m r e u.

2.解密（由P=CA-1）

（1）在26進(jìn)制中，求出加密秘鑰的逆矩陣，如：

（2）將密文字符串轉(zhuǎn)化為數(shù)字序列并按照加密過(guò)程中的記錄的位置進(jìn)行分組，如

（3）每組數(shù)字序列和秘鑰矩陣的逆矩陣做乘法運(yùn)算，如：

（4）將明文矩陣對(duì)應(yīng)的數(shù)字序列根據(jù)先前記錄的腳碼和字母表轉(zhuǎn)化為字母序列，如：I a g r e e .

（5）根據(jù)英文組合的常識(shí)，得知明文為：I agree.

三、構(gòu)造基于希爾密碼的秘密共享方案

（一）系統(tǒng)初始化及系統(tǒng)參數(shù)

設(shè)U=（w1，w2，wn）是參與者集合，秘密分發(fā)者記為M，秘密計(jì)算者記為D（這里D是一臺(tái)安全的計(jì)算機(jī)，用來(lái)完成恢復(fù)秘密的工作），利用逆矩陣加密第一步要將加密的明文數(shù)字化，并取數(shù)字化后的明文作為明文塊。

（二）秘密分發(fā)算法

1.隨機(jī)取一個(gè)矩陣A（存在逆矩陣并保密）作為密鑰矩陣；2.根據(jù)圖1將明文字母轉(zhuǎn)換為對(duì)應(yīng)的字母表數(shù)字；3 將轉(zhuǎn)換后的明文數(shù)字序列按照密鑰矩陣的階數(shù)進(jìn)行分組；4.根據(jù)矩陣的乘法運(yùn)算法則，每組轉(zhuǎn)換后的明文數(shù)字序列和秘鑰矩陣進(jìn)行矩陣的乘法運(yùn)算（如：矩陣乘以矩陣），結(jié)果即為密文數(shù)字序列；5.將密文數(shù)字序列根據(jù)圖1轉(zhuǎn)化為對(duì)應(yīng)的字母，即為密文字符串，并用腳碼標(biāo)注其在密文數(shù)字序列中的位置，將其發(fā)給參與者，作為參與者的密碼。

（三）秘密重構(gòu)算法

1.每個(gè)合作的參與者輸入自己的密碼（密碼正確能重構(gòu)，否則不能重構(gòu)；2.秘密計(jì)算者D將收到的密文轉(zhuǎn)換為相應(yīng)的數(shù)字序列；3.秘密計(jì)算者D 計(jì)算出加密矩陣的逆矩陣；4.秘密計(jì)算者D 用密文分組矩陣乘以逆矩陣，結(jié)果即為明文矩陣；5.將明文矩陣按照給定的字母表轉(zhuǎn)換為明文字符串（如果不是預(yù)先設(shè)定的明文字符串，說(shuō)明參與者輸入密碼錯(cuò)誤）

四、安全性分析與討論

本文設(shè)計(jì)的基于希爾密碼的秘密共享方案，其安全性是基于希爾密碼的安全性。

（一）由于希爾密碼采用矩陣運(yùn)算加密，在給定的明文相同的條件下，加密過(guò)程中也可能出現(xiàn)不同的密文，因此，可以很好地抵御字母頻率的攻擊。

（二）如果是一個(gè)非授權(quán)用戶，存在以下三種情況：

1.若不知道參與者的密碼，則簽名時(shí)不能通過(guò)；2.若不知道參與者密碼所在密文數(shù)字序列中的位置，則簽名時(shí)不能通過(guò)；3.秘密分發(fā)者可以根據(jù)需要定期隨意變化字母表中字母代表數(shù)字的位置，增加安全性。