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

（銅陵職業技術學院，安徽銅陵244000；云南大學，云南昆明650091）

一、秘密共享相關知識

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

秘密共享方法基本上可以分為兩條主線：一是采用不同的數學方法，二是應對不同的實際問題需求，本文研究的是后者。

在現實問題中，有些場合需要秘密份額可以重復使用的情況下在同一組參與者中共享一個秘密。本文通過引入希爾密碼體制，設計基于希爾密碼的秘密共享方案。

二、希爾密碼相關知識

（一）希爾密碼

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

（二）構造希爾密碼體制

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

根據上述參數，構造希爾密碼體制如下：

加密矩陣：A

明文：P轉化為小于26的數字序列

密文：C轉化為小于26的數字序列

加密算法：C=PA

解密算法：P=CA-1

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

1.加密（由C=PA）

（1）定義字母表

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

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

圖1

（4）將需要加密的明文數字化為其對應的字母表里的數字（這里不需要區分大小寫）。

（5）將轉換后的明文數字序列按照秘鑰矩陣的階數進行分組，如：

（6）每組數字序列和秘鑰矩陣行矩陣的乘法運算，結果即為密文矩陣，如：

（7）將密文矩陣根據字母表轉化為對應的字母（在此要記錄下數字在矩陣中的位置），從而得到密文字符串，如：上例的密文字符串為：I a m r e u.

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

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

（2）將密文字符串轉化為數字序列并按照加密過程中的記錄的位置進行分組，如

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

（4）將明文矩陣對應的數字序列根據先前記錄的腳碼和字母表轉化為字母序列，如：I a g r e e .

（5）根據英文組合的常識，得知明文為：I agree.

三、構造基于希爾密碼的秘密共享方案

（一）系統初始化及系統參數

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

（二）秘密分發算法

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

（三）秘密重構算法

1.每個合作的參與者輸入自己的密碼（密碼正確能重構，否則不能重構；2.秘密計算者D將收到的密文轉換為相應的數字序列；3.秘密計算者D 計算出加密矩陣的逆矩陣；4.秘密計算者D 用密文分組矩陣乘以逆矩陣，結果即為明文矩陣；5.將明文矩陣按照給定的字母表轉換為明文字符串（如果不是預先設定的明文字符串，說明參與者輸入密碼錯誤）

四、安全性分析與討論

本文設計的基于希爾密碼的秘密共享方案，其安全性是基于希爾密碼的安全性。

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

（二）如果是一個非授權用戶，存在以下三種情況：

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