有關(guān)Hill加密中三階矩陣的啞元選取

陳歡　陶長(zhǎng)健　黃郅　黃梓　李珂　黎瑩冰

在當(dāng)今擁有大數(shù)據(jù)的網(wǎng)絡(luò)環(huán)境中，對(duì)于數(shù)據(jù)與隱私進(jìn)行有效的保護(hù)與加密已然是重要的課題，本文對(duì)密碼的設(shè)計(jì)進(jìn)行探究，最終在加密與解密過(guò)程中針對(duì)Hill密碼體系的安全性進(jìn)行考量，綜合線性映射與矩陣?yán)碚?，通過(guò)討論啞元的位置、個(gè)[z3]?數(shù)這兩個(gè)不同的情況來(lái)討論設(shè)計(jì)密鑰的方法，最終分別針對(duì)啞元位于明文矩陣的任意一列、任意一列的末尾和啞元個(gè)數(shù)為2個(gè)及以上時(shí)提出了3種方案，以探究Hill密碼加密的安全性、穩(wěn)定性以及解密結(jié)論的準(zhǔn)確性。

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

在擁有大數(shù)據(jù)的新型網(wǎng)絡(luò)環(huán)境下，合理利用密碼，對(duì)數(shù)據(jù)與隱私進(jìn)行合理有效的保護(hù)已然成為一個(gè)重要的課題。密碼學(xué)中的Hill密碼的實(shí)現(xiàn)主要是利用了代數(shù)的取模、求余以及矩陣?yán)碚摚绠?dāng)明文為英文時(shí)，其算法可描述為：將26個(gè)英文字母和空格以一定規(guī)則排序，并對(duì)應(yīng)以整數(shù)0～26編碼，取編碼的基數(shù)mod=27，一種常見(jiàn)編碼規(guī)則見(jiàn)表1。

對(duì)照表1，將明文轉(zhuǎn)化成對(duì)應(yīng)矩陣形式，利用密鑰矩陣左乘明文矩陣，便可得到加密矩陣。將加密矩陣根據(jù)表1翻譯得到密文，而后傳遞給乙方。乙方利用密文對(duì)應(yīng)的解密矩陣左乘接收到的加密矩陣，再對(duì)照表1進(jìn)行翻譯，便可破譯得到原明文內(nèi)容。

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

1Hill密碼加密、解密過(guò)程及不足之處

下面通過(guò)一個(gè)詳細(xì)例子來(lái)對(duì)Hill密碼加密、解密過(guò)程進(jìn)行闡述。

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

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

通過(guò)查字母、空格編碼表將明文信息轉(zhuǎn)化為如下數(shù)字序列：

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

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

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

2啞元位置選取的改進(jìn)方案

當(dāng)明文矩陣只有一個(gè)啞元，且該啞元位于明文矩陣的任意一列末尾，若解密者解密時(shí)舍棄的字母與啞元位置一樣，解密時(shí)啞元的取值不影響解密結(jié)果。

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

S= nvsaiwrirkcrmi

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

對(duì)照表1翻譯并舍棄解密所得字符串的倒數(shù)第四個(gè)字符后得：

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

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

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

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

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

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

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

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

S=nvsaiwrirkcghn

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

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

當(dāng)啞元選取位置在第一行末段時(shí)，我們運(yùn)用上述加密、解密的方式同樣可以取得正確的信息，因此可以利用這一方案對(duì)Hill密碼的運(yùn)用進(jìn)行優(yōu)化。

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

下面通過(guò)一個(gè)例子經(jīng)行闡述，要傳遞的信息為（為空格）：

S=guang∪xi∪shi∪f(wàn)an（廣西師范）

查字母、空格編碼表將明文信息轉(zhuǎn)化為如下數(shù)字序列：

補(bǔ)上兩個(gè)啞元，轉(zhuǎn)化為一個(gè)3行6列的明文矩陣：

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

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

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

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

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

下面來(lái)證明一般性結(jié)論：當(dāng)密鑰矩陣取n+2階可逆矩陣，且滿足第1至n行的最后兩個(gè)元素為0，明文或者密文的啞元取表中的任意元素時(shí)，Hill加密解密成功。

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

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

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

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

3結(jié)語(yǔ)

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