有關Hill加密中三階矩陣的啞元選取

陳歡　陶長健　黃郅　黃梓　李珂　黎瑩冰

在當今擁有大數據的網絡環境中，對于數據與隱私進行有效的保護與加密已然是重要的課題，本文對密碼的設計進行探究，最終在加密與解密過程中針對Hill密碼體系的安全性進行考量，綜合線性映射與矩陣理論，通過討論啞元的位置、個[z3]?數這兩個不同的情況來討論設計密鑰的方法，最終分別針對啞元位于明文矩陣的任意一列、任意一列的末尾和啞元個數為2個及以上時提出了3種方案，以探究Hill密碼加密的安全性、穩定性以及解密結論的準確性。

Hill密碼 矩陣 加密與解密 啞元

Dummy Element Selection of Third Order Matrix in Hill Encryption

CHEN Huan?? TAO Zhangjian?? HUANG Zhi?? HUANG Zi?? LI Ke?? LI Yingbing

（Guangxi Normal University[z5]?， Guilin， Guangxi Zhuang Autonomous Region， 537000 China）

In?today's?network?environment?with?big?data，?effective?protection?and?encryption?of?data?and?privacy?has?become?an?important?topic.?This?paper?explores?the?design?of?cryptography，?and?finally?considers?the?security?of?Hill?cryptography?system?in?the?process?of?encryption?and?decryption，?integrating?linear?mapping?and?matrix?theory.?By?discussing?the?position?of?the?dummy，?the?number?of?the?two?different?situation?to?discuss?key?design?method，?finally?we?respectively?for?dummy?in?clear?any?column?of?the?matrix，?and?at?the?end?of?a?column?of?dummy?number?for?two?or?more?puts?forward?three?kinds?of?solutions，?to?explore?the?Hill?password?encryption?security，?stability?and?the?accuracy?of?the?decryption?conclusion.

Hill password; Matrix; Encryption and decryption; Dumb meta

在擁有大數據的新型網絡環境下，合理利用密碼，對數據與隱私進行合理有效的保護已然成為一個重要的課題。密碼學中的Hill密碼的實現主要是利用了代數的取模、求余以及矩陣理論，如當明文為英文時，其算法可描述為：將26個英文字母和空格以一定規則排序，并對應以整數0～26編碼，取編碼的基數mod=27，一種常見編碼規則見表1。

對照表1，將明文轉化成對應矩陣形式，利用密鑰矩陣左乘明文矩陣，便可得到加密矩陣。將加密矩陣根據表1翻譯得到密文，而后傳遞給乙方。乙方利用密文對應的解密矩陣左乘接收到的加密矩陣，再對照表1進行翻譯，便可破譯得到原明文內容。

本文參考了《Hill密碼體系中的加密矩陣與啞元》中密鑰矩陣的選取以及加密算法的改進方式，即：密鑰矩陣采用3階可逆下三角矩陣形式，明文或密文的啞元取表1中任意元素。在此基礎上，針對啞元不同的擺放位置對Hill加密、解密過程進行可行性探究。

1Hill密碼加密、解密過程及不足之處

下面通過一個詳細例子來對Hill密碼加密、解密過程進行闡述。

假設需要傳送的信息為（∪為空格）：

S=guangxi∪∪shida（廣西師大）

通過查字母、空格編碼表將明文信息轉化為如下數字序列：

乙方將收到的信息S3同樣按照3個數據為1列的方式轉化為矩陣D，在矩陣D最后一位補充一個啞元*，其中*可取0～26內任一整數值。用解密矩陣C左乘矩陣D后，可得到一組數字序列S4，對照表1進行翻譯，最終解出結果舍棄最后一位，可接收到準確的明文信息：

S4=guangxi∪∪shida（廣西師大）

對于上面的例子而言，盡管明文加密與密文解密過程以及結果是無差錯的，但是只在明文矩陣最末一位取啞元的方式過于簡單，從而使得明文容易被第三方破譯。因此為了提高加密、解密過程的安全性與復雜性，下文將會進行對啞元位置選取的多情況探討。

2啞元位置選取的改進方案

當明文矩陣只有一個啞元，且該啞元位于明文矩陣的任意一列末尾，若解密者解密時舍棄的字母與啞元位置一樣，解密時啞元的取值不影響解密結果。

在mod=27的意義下，得到具有15個字符的信息串，舍棄倒數第四個字符后的密文信息為：

S= nvsaiwrirkcrmi

將這段字符作為密文發送給乙方，乙方接收后將這一信息轉化為第四列最末尾含啞元的密文矩陣，再用解密矩陣C對密文進行解密，其中解密矩陣C為：

對照表1翻譯并舍棄解密所得字符串的倒數第四個字符后得：

S=guangxi∪∪shida（廣西師大）

與原明文信息S1對比，完全相同，解密成功。

再用同樣方式將啞元放置在明文矩陣第三、二、一列的最末端位置，按照上述方法進行加密、解密，最終均可得到準確的明文信息。因此在明文以3階矩陣形式表達的情況下，該啞元選取以及算法優化方案具有可行性。

當明文矩陣只有一個啞元（取0～26中任一整數），且該啞元位于明文矩陣的任意一行末尾時，若密文矩陣中啞元選取的數字為：密鑰矩陣左乘明文矩陣后所得乘積矩陣對應位置上的數字k，且乙方解密時舍棄的字母與啞元位置相對應，則解密結果不變。

以例1中明文的加密為例，若將啞元放到明文矩陣的第二行末端，可得到以下矩陣：

取*=k（k為0-26中的任一整數），左乘密鑰矩陣B：

密鑰矩陣左乘明文矩陣后得到的乘積矩陣P為：

將乘積后的矩陣在mod=27意義下翻譯，并忽略第二行末端對應字母，得傳輸給乙方的密文：

S=nvsaiwrirkcghn

乙方得到密文S6后，將信息轉化成第二行末尾含啞元的密文矩陣，啞元取k=17，再用解密矩陣C對其進行解密、翻譯，得到字符串后舍棄倒數第三個字母，可得準確的明文，即：

S=guangxi∪∪shida（廣西師大）

當啞元選取位置在第一行末段時，我們運用上述加密、解密的方式同樣可以取得正確的信息，因此可以利用這一方案對Hill密碼的運用進行優化。

密鑰矩陣選取n+2階可逆矩陣，且滿足第1至n行的最后兩個元素為0，明文或者密文矩陣最后一列末尾的2個啞元選取表中的任意元素。那么加密解密時，明文的加密信息或密文的解密信息就不受啞元選取的影響，啞元就可以任意取。

下面通過一個例子經行闡述，要傳遞的信息為（為空格）：

S=guang∪xi∪shi∪fan（廣西師范）

查字母、空格編碼表將明文信息轉化為如下數字序列：

補上兩個啞元，轉化為一個3行6列的明文矩陣：

在明文矩陣A中，啞元可以取字母、空格編碼表中的任意元素，假設取*=14，左乘密鑰矩陣：

在mod 27的意義下，得到具有18個字符的密文，舍棄密文最后兩個字符后的密文信息為：

對密文經行解密（解密矩陣左乘密文矩陣）。這時密文的啞元可任意選取字母、空格編碼表中的元素，舍棄解密所得字符串的最后兩個字符后的明文信息為：

與原明文信息S對比，完全相同，解密成功。

通過上述示例，可以得知當明文或者密文矩陣末尾有兩個啞元，且n+2階的密鑰矩陣1至n行末尾兩個元素都為0，啞元任意選取字母、空格編碼表的元素時，Hill加密解密能夠成功。

下面來證明一般性結論：當密鑰矩陣取n+2階可逆矩陣，且滿足第1至n行的最后兩個元素為0，明文或者密文的啞元取表中的任意元素時，Hill加密解密成功。

解密成功，故此方案可行。

同時還可以觀察到，有下三角矩陣恰巧符合方案1中假設的密鑰矩陣的特征，也是因此當使用下三角矩陣作為密鑰矩陣時Hill總能加密解密成功。

由上述證明已知，因最終解密獲取明文信息時需要去除掉密文中啞元相應位置譯出的信息，為排除啞元在解密過程中對翻譯明文信息造成的影響，當明文矩陣有2個啞元時，只需要保證n+2階的密鑰矩陣符合1至n行的最后兩個元素均為0，即可在最后的解密中獲得正確的明文信息。而這樣的規律也同樣適用于多個啞元的情況：

對于任意行數為m（其中m=m+k）的明文矩陣，當最后一列末尾的啞元個數為k個時，密鑰矩陣選取n+i階的可逆矩陣，且密鑰矩陣1至n行的最后k個元素均為0，即：

3結語

本文針對Hill密碼加密、解密過程中三階矩陣的啞元選取方案進行優化，在前輩們的基礎上提出了更新的解決方案，即3種啞元選取的方式，在最后一種方案里，將其形式擴展到了k個啞元的情況上，使得啞元選取的形式以及方案更為廣泛。