矩陣在信息編碼中的應(yīng)用

熊允發(fā)

(中國人民公安大學(xué)信息技術(shù)與網(wǎng)絡(luò)安全學(xué)院， 北京 100038)

矩陣在信息編碼中的應(yīng)用

熊允發(fā)

(中國人民公安大學(xué)信息技術(shù)與網(wǎng)絡(luò)安全學(xué)院， 北京 100038)

矩陣是高等代數(shù)的基本概念之一，是線性代數(shù)的核心內(nèi)容。它借助于幾何概念分析純代數(shù)問題，是基礎(chǔ)學(xué)科中求解線性方程組的理論工具。隨著科技的進(jìn)步與發(fā)展，矩陣在物理學(xué)、計(jì)算機(jī)科學(xué)、數(shù)學(xué)建模、密碼學(xué)以及統(tǒng)計(jì)分析學(xué)等應(yīng)用數(shù)學(xué)類學(xué)科中都作為重要工具發(fā)揮著越來越廣泛的作用。本文通過論述矩陣在密碼學(xué)方面應(yīng)用的系列特性，簡要分析并掌握信息編碼的加密、解密技術(shù)和思想，從而提高對于公安網(wǎng)絡(luò)安全與執(zhí)法工作的能力。

矩陣； 信息編碼； 密碼學(xué)應(yīng)用

0 引言

矩陣是高等代數(shù)的基本概念之一，也是線性代數(shù)的核心內(nèi)容。作為基礎(chǔ)學(xué)科中的重要理論工具和計(jì)算工具，它能夠通過極其簡單的形式和靈活的表達(dá)方法，為解決較為復(fù)雜的問題提供好的思路，在諸如數(shù)字圖像處理、計(jì)算機(jī)圖形學(xué)、計(jì)算幾何學(xué)、人工智能、網(wǎng)絡(luò)通信、信息編碼以及一般的算法設(shè)計(jì)和分析等方面都發(fā)揮著重要的作用[1]。本文從客觀實(shí)際出發(fā)，在介紹矩陣以及逆矩陣概念的基礎(chǔ)上，簡要闡述矩陣在信息編碼方面的基本原理，重點(diǎn)介紹矩陣在信息編碼以及它在加密、解密過程中的應(yīng)用，以期對廣大讀者有所裨益。

1 矩陣的基本性質(zhì)

1.1 矩陣

由m×n個(gè)數(shù)aij(i=1,2,…,m;j=1,2,…,n)排列成的一個(gè)m行n列的矩形陣表，稱為一個(gè)m×n矩陣。記為

其中aij稱為矩陣第i行第j列的元素。通常用大寫字母A、B、C、……表示矩陣。為了標(biāo)明矩陣的行數(shù)m和列數(shù)n，我們可用(aij)m×n來表示矩陣，或簡記為Am×n。

矩陣特性：

(1) 矩陣只是一種數(shù)的矩形陣表，且行數(shù)可以不等于列數(shù)。它與行列式截然不同，它不代表一個(gè)數(shù)或函數(shù)，也無表達(dá)式可言。如果行數(shù)和列數(shù)相等且都等于n，則稱其為n階矩陣或n階方陣。

(2) 矩陣A與B相等的條件：其一，兩矩陣須有相同的行數(shù)與列數(shù)；其二，每一個(gè)對應(yīng)位置上的元素都對應(yīng)相等。若A=B，A=(aij)m×n，B=(bij)m×n，則aij=bij。

1.2 逆矩陣

(1) 定義：對于n階矩陣A，如果存在n階矩陣B，使得AB=BA=I，那么，矩陣A稱為可逆矩陣。而B稱為A的可逆矩陣，記為B=A-1，且這樣的逆矩陣B是唯一的。n階矩陣A可逆的充要條件是|A|≠0。

(2) 性質(zhì)：

a.若A可逆，則A-1亦可逆，

且 (A-1)-1=A；

b.若A可逆，數(shù)λ≠0，則λA可逆，

c.若A、B為同階矩陣且均可逆，則AB也可逆，且(AB)-1=B-1A-1；

d.若A可逆，則AT亦可逆，

且 (AT)-1=(A-1)T；

e.若A、B為同階矩陣且AB=I，那么必有BA=I，即A、B互為對方的逆。

(3) 求逆矩陣的基本方法：

b.利用初等變換求逆矩陣：

所謂初等變換是指對矩陣施以下列3種變換：

①交換矩陣的兩行(列)；

②以一個(gè)非零的數(shù)k乘矩陣的某一行(列)；

③把矩陣的某一行(列)的k倍加于另一行(列)上。

利用初等變換求逆矩陣的具體方法為：作一個(gè)n×2n的矩陣(A|I)，然后對此矩陣施以行的初等變換，使子塊A化為I，則同時(shí)子塊I即化為A-1。

解：

2 矩陣在編碼中的作用

2.1 幾個(gè)基本概念的闡述

密碼：密碼學(xué)中將信息代碼稱之為密碼。

明文：尚未換成密碼的文字信息稱之為明文。

密文：由密碼表示的信息稱之為密文。

編碼：將明文加上密碼加密成密文發(fā)送出去，即是信息從一種形式或格式轉(zhuǎn)換為另一種形式的過程。在計(jì)算機(jī)硬件中，編碼是指用代碼來表示各組數(shù)據(jù)資料，使其成為可利用計(jì)算機(jī)進(jìn)行處理和分析的信息。用預(yù)先規(guī)定的方法將文字、數(shù)字或其他對象編成數(shù)碼，或?qū)⑿畔ⅰ?shù)據(jù)轉(zhuǎn)換成規(guī)定的電脈沖信號。

譯碼：將密文通過密碼解密成明文，即是利用譯碼表把文字譯成一組組數(shù)碼或用譯碼表將代表某一項(xiàng)信息的一系列信號譯成文字的過程稱之為譯碼。譯碼是編碼的逆過程，是指利用譯碼表把文字譯成一組組數(shù)碼或用譯碼表將代表某一項(xiàng)信息的一系列信號譯成文字的過程。

這幾個(gè)概念之間的關(guān)系，由圖1所示。

圖1 幾個(gè)概念之間的關(guān)系

2.2 矩陣在編碼中的應(yīng)用

通過對以上密碼學(xué)中幾個(gè)基本概念的描述，我們可清楚地看到，在密碼學(xué)中，從明文到密文再轉(zhuǎn)化成明文的過程，實(shí)際上就是加密與解密的過程，而加密和解密分別是由加密密鑰和解密密鑰來控制的。其本質(zhì)就是利用某種信息或工具在已知與未知的兩者間創(chuàng)建一種具有特定關(guān)系的映射。說的更直接些，該過程就是利用可逆矩陣以及矩陣的乘法等的重要性質(zhì)來做一個(gè)簡單的運(yùn)算而已，其中的密鑰就是可逆矩陣。

目前利用矩陣進(jìn)行密碼編譯的典型實(shí)例很多，算法各異，既可以將字符用數(shù)字替代也可以將字符用ASCII替代。

比如，現(xiàn)在常用的較為簡單的密碼有棋盤密碼、移位(Caesar)密碼、維吉尼亞(Vigenere)密碼、普萊費(fèi)爾(Playfair)密碼等，但這些密碼的加密方式簡單，極易被破譯，安全性能低等，在這里我們就不一一介紹了。根據(jù)實(shí)際工作的現(xiàn)狀與需求，本文主要是重點(diǎn)來介紹一下希爾(Hill)密碼的加密與解密的全過程以及需要注意的事項(xiàng)。

1929 年，希爾( Hill) 通過矩陣?yán)碚搶鬏斝畔⑦M(jìn)行加密處理，提出了在密碼學(xué)史上有重要地位的希爾加密與解密算法。其具體解題步驟如下：

第1步：讓26個(gè)英文字母與26個(gè)阿拉伯?dāng)?shù)字之間形成一一對應(yīng)關(guān)系，另外用0表示空格。如下圖

ABCDEFG1234567HIJKLMN891011121314OPQRSTU15161718192021VWXYZ2223242526

第2步：將信息中的單詞的字母從左到右，每n個(gè)(通常是3個(gè)或4個(gè))字符分為一組，最后不足n個(gè)字符的用空格補(bǔ)上。于是各個(gè)分量就可以形成一個(gè)簡單的編碼矩陣B(注意：該矩陣列向量的維數(shù)要與開始分組的字符個(gè)數(shù)一致)。

第3步：確定加密矩陣A。這是一個(gè)階數(shù)等于每組字符個(gè)數(shù)的可逆矩陣，可任選擇，當(dāng)然，一定要求它的可逆矩陣簡單且便于運(yùn)算，否則計(jì)算量很大，不劃算。

第4步：用加密矩陣A左乘編碼矩陣B，得到密文矩陣C。即AB=C

第5步：用加密矩陣的逆矩陣A-1左乘以密文矩陣，即可得到譯碼矩陣。即A-1AB=A-1C[4]

第6步：將譯碼矩陣對應(yīng)回英文字符即可得到原來的信息。

根據(jù)矩陣的運(yùn)算性質(zhì)，經(jīng)過前面的兩次左乘矩陣后，其實(shí)矩陣沒變，因此，編碼矩陣和譯碼矩陣應(yīng)為同一矩陣。我們不妨用下面兩個(gè)例子來具體地說明一下：

例3(用3個(gè)字符分組)假設(shè)要發(fā)送“Crandall”(矩陣編碼)這個(gè)信息。

②現(xiàn)任取一個(gè)三階的可逆矩陣

解密是加密的逆過程，這里要用到矩陣A的逆矩陣A-1，這個(gè)可逆矩陣A-1稱為“解密密鑰”。

③用初等變換的方法求得

④利用A-1左乘以密文矩陣，就可以得到譯碼矩陣了。也就是從密文中解出明文了。

⑤最后將譯碼矩陣?yán)米帜概c數(shù)字的關(guān)系對照表，對應(yīng)回英文字符，即可得到最初的消息“Crandall”(矩陣編碼)。

例4(用4個(gè)字符分組)假設(shè)要發(fā)送“Steganography”(信息隱藏技術(shù))這個(gè)信息。

②現(xiàn)任取一個(gè)4階的可逆矩陣

解密是加密的逆過程，這里要用到矩陣A的逆矩陣A-1，這個(gè)可逆矩陣A-1稱為“解密密鑰”。

③ 利用初等變換的方法求得，A-1=

⑤將譯碼矩陣對應(yīng)回英文字符，即可得到最初的消息“Steganography”(信息隱藏技術(shù))。

通過以上兩個(gè)具體的例子，我們不難看出：3階或4階逆矩陣(密鑰矩陣)的選取，一定要保證信息傳遞的安全性和解密過程的便捷性，既不能太麻煩，也不能太抽象，一定要反映問題的實(shí)質(zhì)，并且一定要以取整數(shù)為宜，求逆矩陣時(shí)不宜太復(fù)雜。

當(dāng)然，若每5個(gè)字符分組，甚至n個(gè)字符也是可以的。只不過此時(shí)的可逆矩陣即加密密鑰就要選5階矩陣或n階矩陣了。

3 結(jié)束語

本文簡要介紹了有關(guān)矩陣的基本概念、性質(zhì)及其它在信息編碼中的運(yùn)用，并且列舉了利用“希爾加密與解密算法”的兩個(gè)案例。希望通過此文的講解，能使大家在今后的學(xué)習(xí)中，對矩陣的基本內(nèi)容和構(gòu)造方法產(chǎn)生較為深刻的認(rèn)識，并將其抽象的理論體系與實(shí)際應(yīng)用有機(jī)地結(jié)合起來，從而發(fā)揮更大的效益。

[1] 李排昌，左萍. 線性代數(shù)(修訂版)[M]. 北京：中國人民公安大學(xué)出版社，2009：45，53，62.

[2] 趙樹嫄.線性代數(shù)(第三版)[M]. 北京：中國人民大學(xué)出版社，2003: 78.

[3] 魏戰(zhàn)線.線性代數(shù)(工程數(shù)學(xué))[M]. 遼寧：遼寧大學(xué)出版社，2008: 65.

[4] 劉吉佑，徐誠浩.線性代數(shù)(經(jīng)管類)[M]. 武漢：武漢大學(xué)出版社，2006: 40.

[5] 施光燕.線性代數(shù)講稿[M]. 遼寧：大連理工大學(xué)出版社，2004: 29.

(責(zé)任編輯 于瑞華)

熊允發(fā) (1963—)， 男， 湖北仙桃人， 教授。 研究方向?yàn)榫仃嚪治雠c應(yīng)用。

O151.2