一種碼字表加解密方法
2023-05-12 05:16:56 1
專利名稱：一種碼字表加解密方法
技術領域：
該發明技術主要應用在「信息安全技術」和「數據存貯與管理」等領域
背景技術：
1、碼字表 碼字表的用途非常的廣泛[17][18][19]，為許多教學和拼詞典類型的軟體中所需要。本論文研究的碼字表對象主要是針對應用於壓縮編碼和加密系統的碼字表。很多軟體使用大型資料庫來存儲碼字表，這些的碼字表需要龐大的管理系統。然而在壓縮編碼和加密系統中，碼字表的應用方式比教學軟體等中的簡單，不希望使用複雜的管理，只希望能夠在傳輸和存儲時有足夠的安全性並且只佔較小的存儲空間。
碼字表的生成過程基本如下1)考察需要使用的字符(或字符)集；2)尋找合適的編碼法(按照碼字表的使用目的)；3)按照使用的編碼法將所選字符集編碼，並加入所需信息，製成碼字表。碼字表的生成過程能夠幫助我們了解碼字表的組成要素，進而研究在它的存儲過程中，需要保存那些關鍵信息，能夠唯一表示此碼字表。
不難發現，碼字表需要編碼字符集、字符與碼字的對應關係以及碼字長度來標識。缺少了這些信息，碼字表的內容將被破壞。所以在本論文構造碼字表的存儲結構中，將會著重說明這些信息是怎樣被安置進新的結構中的。
在編碼表中，如果對每一待編碼的字符，編碼後的碼字長度一定，那麼我們可以用定長的空間來存儲，並且查找碼字時也可以直接使用現有的查找算法。而更一般的情況是用變長碼，如壓縮編碼的壓縮原理就是使經常使用的字符用短的二進位碼字表示，反之用長的碼字表示。變長碼如果用定長的空間來存儲將會浪費大量的空間，所以必須另闢蹊徑。
2、順序存儲 我們首先研究這樣一張碼字表，設 ∑1＝{A，B，C}∑2＝{a，b，c，d，e，f} 且∑1上的一編碼方案如圖1所示 如果要順序存儲此張碼字表(即依次存儲字符、碼字對)，並且能夠讓程序在讀入存儲的數據後自動識別它的內容，那麼要解決如下問題 1)區分被編碼字母與碼字 2)區別每個字母的碼字 3)能夠根據被編碼字母找到對應碼字 要達到這些目的，必須在存儲的數據中加入一些特定的字符，並在程序規定這些字符的含義。我們可以加入推倒符號，分隔符。例如，規定 ，符號用來分隔各個編碼 →符號前面是被編碼字符，後面為碼字 則表1可以表示為 A→abc，B→efcd，C→ffb 然而此碼字表存儲的為變長碼，如果要查找任一字母的編碼，無法用時間複雜度小的查找方法，因為對於每個字母的編碼所需要的存儲空間不相同，所以查找後面字母的編碼時，必須遍歷所有前面的數據，直到找到此字母開始的代換。
可以對簡單順序存儲作一定的修改，即令每個字母的代換集合存儲長度相同，這樣就可以以字母在字母表中的位置作為索引來查找。如表1的例子，所有編碼表示串的最大長度為6，則我們規定每個編碼都用6個字符表示，遇到空格或「，」表示此碼字結束，則它的存儲表示如下 A→abc，B→efcd，C→ffb_ 其中_表示空格符。
這樣的表示會佔用額外的存儲空間。若以lmax表示編碼中最長的碼字，
表示碼字的平均長度，n＝|∑1|為字母表元素的個數，則需要佔用的額外空間為 顯然，在最長的碼字比平均碼字長度大得多時，額外消耗的空間將隨字母表大小的增長線形遞增。
3、字典存儲法 由論文[20]，我們想到在文本中可以利用索引查找，即將順序存儲稍稍作些改變，把字母表的信息提取出來作為索引，而剩餘的所有編碼作為字典內容部分以供查找。在索引中除了存儲字母表，還需要存儲字母的編碼在字典中的起始位置，碼字的長度。仍以表4-1為例，索引和字典部分如下所示。
index＝(A，1，3)，(B，4，4)，(C，8，3) dinctionary＝abcefcadffb 那麼存儲的信息為index|dictionary。
使用它很簡單，例如，查找B的編碼時，首先在索引中查找到B對應的索引項，然後讀出它的編碼起始字符位置為4，長度為4，則從字典中的第四個字符開始讀一個長度為4的字符串efcd，即為B的編碼。
4、其他存儲法 除了以上兩種存儲方法外，還有使用樹型結構或者資料庫等方法來存儲碼字表的[21][22]。他們都是根據應用的特殊性決定的。例如霍夫曼編碼的樹型生成結構使得它可以使用樹型結構存儲。對於輸入法等其他大型查找軟體中使用的碼字表可以存儲在資料庫中管理。本論文中討論的存儲法與碼字表的一般形式相關，並希望不利用額外的資料庫軟體，所以不再對特殊的應用詳細說明。
發明內容
本發明提出了一種新的碼字表加解密的方法，其主要步驟包括 加密過程主要步驟包括 1)首先，對碼字表τ輸入字母表∑1和輸出字母表∑2中的元素排序，令其為∑1＝{a1，a2，...，an}，∑2＝{b1，b2，...，bi，！}，其中ai，bj為字符，「！」為結束符； 2)對於值域中的每個詞，先按它和字母表∑1中字母的對應關係進行排序，設為f(∑1)＝{w1，w2，...wn}，其中ai→wi。找出值域f(∑1)中最長的字wk，其長度表示為l，使用映射函數g∑2l作用於{w1，w2，...wn)，這樣，依照原來的順序的對應關係，形成一個新的集合其中，αi為ai對應的碼字wi的算術編碼，Г為碼字對應編碼的集合，Γ中每個元素都是區間_0，(|∑2|)l+1)上的一個數； 3)對Г中的數字進行處理，使這個集合對應一個數字，我們將Г變換成一個同餘方程組 x≡α1(modm1) x≡α2(modm2) ... x≡αn(modmn) 其中，x為碼字對應的數字，mi為模數； 4)利用中國剩餘定理可以計算得到唯一的整數x 其中Mi＝M/mi，si＝Mimodmi。
所述加密過程步驟2)中的映射函數g∑2l定義如下 1)求出區間總長度B＝(t+1)l+1，以及每個字符出現的概率n＝1/(t+1)，求出子區間B1＝B*n，並按順序將其分配給∑2中的bi和結束符「！」； 2)根據碼字wi的第一個字符確定下一個區間範圍； 3)將上一個步驟所得的區間範圍再按照概率再一次平分給bi和結束符號「！」； 4)再根據碼字wi的下一個字符確定下一個區間範圍； 5)將上一個步驟所得的區間範圍再按照概率再一次平分給bi和結束符「！」； 6)如此循環步驟4)、5)，直到碼字wi的所有字符都經歷過，那麼最後一次平分後，結束符「！」所佔的區間的第一個數即為碼子wi所對應的算術編碼αi。
所述加密過程步驟3)中模數mi的定義如下 找出值域f(∑1)中最長的詞wk，其長度表示為l，區間長度為B＝(t+1)l+1，那麼αk最大不會超過(t+1)l+1，並且Г所有其它元素的值也不會超過(t+1)l+1，取mi為大於(t+1)l+1的第i個最小的素數，這樣就可以保證x一定存在，即mi＝Pri((t+1)l+1)，其中Pri(a)表示大於a的第i個最小的素數。
所述解密過程主要步驟包括 1)計算出B＝(t+1)l+1，其中B為進行區間轉換映射到數字時的區間長度，t為集合∑2中字符的個數(不包含結束符)； 2)根據讀入的當前字母a，我們首先從字母表信息中獲得此字母的位置值i，計算大於B的第i個最小的素數mi； 3)求得αi＝xmodmi，αi正是a對應的碼字wi的算術編碼； 4)根據映射函數g∑2l，對αi這些進行區間轉換的逆運算後得到的字符串就是wi，用公式表示，由ai獲得它的編碼的函數為 也即 其中Pri(a)表示大於a的第i個最小的素數。
從上面的過程可以看到，僅僅有x和ai還不能計算得wi，函數計算中還需要∑2和f(∑1)中最長的詞wk的長度l。所以，實際上函數的形式為 Fx(∑1，∑2，l)＝C 如果要還原出整張碼字表，只要依次讀入∑1中的字符，對它作步驟1)-4)的處理，就可得到所有符號對應的碼字，即f(∑1)。現在存儲碼字表只需要存儲四元組(∑1，∑2，l，x)，而程序中讀入此四元組後，使用函數Fx的計算方法，就可以還原碼字表了。
本發明的有益效果為給定一個碼字表τ，即給定一個輸入字母表∑1，輸出字母表∑2和字母表∑2一個語言C，一個明文碼字表τ被加密成一個明文四元組(∑1，∑2，l，x)，其中l表示語言C中字的最大長度，x是我們加密的一個正整數。反之，關於上面得到的四元組(∑1，∑2，l，x)，其中，∑1輸入字母表，∑2輸出字母表和l表示輸出字母表∑2一個語言C中字的最大長度，x是一個正整數，則我們可以唯一地恢復與之相對應的碼字表τ，即把一個明文四元組(∑1，∑2，l，x)解密為一個明文碼字表τ，極大地提高了以「碼字表」作為對稱密碼體制中的密鑰的管理的安全性，也極大地減少了存儲碼字表時所佔用的空間。
圖1為碼字表示意圖； 圖2為映射函數g∑2l4次區間選擇示意圖； 圖3為利用映射函數g∑2l區間選擇逆過程。
具體實施例方式 下面結合附圖對本發明進行進一步闡述。
1、區間轉換法 在算術編碼中，每一條信息對應著一個區間[0，1)上一個子區間內的實數，當消息越長時，子區間就越短，這時需要的精度就更高，編碼自然越長。為了減少實現時的精度，Witten，Neal和Cleary設計了一個巧妙的辦法，在整數區間上作算術編碼，結果沒有影響。這裡借鑑整數算術編碼的思想，將一個字符串轉換成一個相應的整數。
對字母表∑(|∑|＝t)上的任一詞w，w出現的每個字母a∈∑可看作一個事件，並且事件的概率均為1/t，則一個長度為k的詞(時間序列)出現的概率為(1/t)k。所以，對∑上的每個詞，都可以作為一個概率與之長度相關事件序列。這個過程，很容易聯想到算術編碼。
不失一般性，設字母表為{a，b，c，d，e，f}，我們規定！為結束符，那麼一個長度為l的字符串(包含結束符)可能由7個字符(a，b，c，d，e，f，！)中的任何l個字符組成，那麼包括結束符在內，字符串的實際長度為l+1。我們的操作要在一個足夠大的區間上對字符串進行，這樣才能夠保證任何字符串都能夠映射到的子區間內至少有一個整數。設定字符串的長度最長不能超過3(根據不同的應用將會有不同的值)，那麼加上結束符後，實際要做4次選擇區間的過程。
由為保證每個字符串的編碼都能夠得到一個整數，所以操作區間為[0，2401)。每個符號可能出現的概率都相同為1/7，這樣對字符串bac的處理過程如圖2，則最後得到的區間為[363，364)，取363最為字符串bac的相應數值表達。
在後面時，將用此種方法把一個字母表上的字符串映射為一個數字。字符串為s，數字為α，此映射為g∑l，其中∑表示字符串所在的字母表，l表示最長字符串的長度。則 其還原的過程與此過程相似，對於數字為α，首先確定它在那個子區間內。將[0，2401)劃分為l+1個等長的子區間，假設α屬於第i個子區間，那麼字符串的第一個符號為碼字表∑中的第i個符號；將此子區間作為當前區間，繼續劃分，重複前面的步驟，直到當前的符號為結束符為止，此時獲得的字符串即為所求。
2、轉換函數 給定字母表∑1，∑2和字母表∑2一個語言C，即已知碼字表τ，如何把它轉換成一個四元組(∑1，∑2，l，x)，其中l表示語言C中字的最大長度，x是我們要轉換的正整數。反之，給定一個四元組(∑1，∑2，l，x)，我們如何轉換為一個碼字表τ。
我們設定|∑1|＝n，其中的每個字母對應於一個字其中集合C是字母表∑2一個語言。顯然，此對應關係可看作一個單射函數，函數的定義域為字母表∑1，而值域為C，此函數可表示為 f∑1→C 既對字母表∑1中的字母的編碼為 ai→wi 然而，對於任意碼字表來說，編碼對應的函數f是沒有任何規律的。也就是說，如果我們要表示此函數，不能用一個特性來表示它，只能用列舉法窮舉其表示的自變量和因變量對的集合。我們希望尋找其他途徑來表示這個函數，這裡我們將找到與此碼字表緊密相聯的一個數字，使用此數字就能夠通過對字母做一系列的計算而得到它所對應的編碼，使這個函數f轉變成為一個真正數學意義上的函數F。
如果我們用P來表示碼字表向數字x轉換的過程，根據上段文字的意思，P就應滿足以下關係式 x＝P(∑1，∑2，f) 然後由此數字構造出函數Fx，令其滿足 Fx(∑1)＝C 這樣，只要我們知道了x，對任何一個字母ai我們只需要計算Fx(ai)，結果即為ai的編碼。
下面我們將分別詳細敘述怎樣獲得這個數字x和構造函數Fx。P做的工作如下 1)首先，對字母表∑1和∑2中的元素排序(比如英語中26個字母本身就有固定的順序)，令其為 ∑1＝{a1，a2，...，an} ∑2＝{b1，b2，...，bt} 2)接著，對於值域中的每個碼字，我們也先按它和字母表∑1中字母的對應關係，對其排序為 f(∑1)＝{w1，w2，...wn} 其中，ai→ wi。
我們找出值域f(∑1)中最長的碼字wk，其長度表示為l。使用映射函數g∑2l作用於{w1，w2，...wn}，這樣，依照原來的順序的對應關係，形成一個新的集合 Γ中每個元素都是區間_0，(|∑2|+1)l+1)上的一個數。這並沒有達到我們的最終目的，我們所希望的是得到一個與函數f和字母表∑1相關的一個數字，而不僅僅是將f的值域轉換成數字的集合。那麼下面，我們將要利用上面的集合Γ得到x。在這裡我們將用到中國剩餘定理。
我們現在只對Г中的數字進行處理，使這個集合對應一個數字，而且可以根據一些信息可以將Г中的任何一個元素還原出來。這樣好比是把零散的筆記裝訂起來，並且可以通過清晰的索引來快速查找需要的部分。我們將Γ變換成一個同餘方程組 x≡α1(modm1) x≡α2(modm2) ... x≡αn(modmn) 模數mi的計算如下 我們找出值域f(∑1)中最長的碼字wk，其長度表示為l，|∑2|＝t。則在對wk進行區間轉換映射到數字時，區間長度為B＝(t+1)l+1，那麼αk最大不會超過(t+1)l+1，並且Γ所有其它元素的值也不會超過(t+1)l+1。取mi為大於(t+1)l+1的第i個最小的素數(這是十分容易的，因為mi並不大)，這樣就可以保證x一定存在，即 mi＝Pri((t+1)l+1) 其中Pri(a)表示大於a的第i個最小的素數。
再利用前面中國剩餘定理部分的證明可以計算得到唯一的x。
其中Mi＝M/mi，si＝Mimodmi。
現在，我們已經獲得了關於碼字表對應的數字x，剩下的工作就是構造函數Fx。從上面求x的過程中，我們看到過程 若要計算某個字符對應的碼字，則為上述過程的逆過程 1)計算出B＝(t+1)l+1 2)然後根據讀入的當前字母a，我們首先從字母表信息中獲得此字母的位置值i，計算大於B的第i個最小的素數mi。很明顯，這個素數就是同餘方程組中第i個模運算式的模數。
3)我們求得αi＝xmodmi。αi正是a對應的碼字wi的算術編碼 4)因為默認字母表∑2中所有字母的出現概率是相同的，只要知道字母表∑2的元素個數t，即知道了其概率為1/(t+1)，那麼根據這些進行區間轉換的逆運算後得到的字符串就是wi。
用公式表示，由ai獲得它的編碼的函數為 也即，其中Pri(a)表示大於a的第i個最小的素數。
從上面的過程可以看到，僅僅有x和ai還不能計算得wi，函數計算中還需要∑2和f(∑1)中最長的詞wk的長度l。所以，實際上函數的形式為 Fx(∑1，∑2，l)＝C 如果要還原出整張碼字表，只要依次讀入∑1中的字符，對它作步驟1～4的處理，就可得到所有符號對應的碼字，即f(∑1)。現在存儲碼字表只需要存儲四元組(∑1，∑2，l，x)，而程序中讀入此四元組後，使用函數Fx的計算方法，就可以還原碼字表了。
下面我們仍將使用圖1的例子來進一步說明此過程。
兩字母表中元素按照現實中字母表的順序排列不變設， ∑1＝{A，B，C} ∑2＝{a，b，c，d，e，f} ∑2的字母個數為t＝6，則字母表∑2中每個字母(包括結束符)代表的概率為1/7，對圖中的三個詞作區間轉換的過程如下 碼字中最大字符串長度為l＝4，所以 B＝(t+1)l+1＝75＝16807 其餘碼字處理過程類似，最後轉換的結果如下表所示。
表1碼字的對應整數 下面生成3個大於(t+1)l+1＝16807的三個不同的最小素數m1＝16811，m2＝16823，m3＝16829 建立同餘方程式
求得x為74711228178948411，那麼需要存儲的信息(∑1，∑2，l，x)為 ({A，B，C}，{a，b，c，d，e，f}，4，74711228178948411) 在還原碼字表時，即為利用上面的四元組求Fx(ai) 首先，生成3個大於(t+1)l+1＝16807的三個素數 m1＝16811，m2＝16823，m3＝16829 然後，用求模公式求得 將求得的{α1，α2，α3}用區間轉換法的逆過程還原出在∑2上的碼字，仍以A-＞abc為例，如圖3所示，逆過程如下 求得α1＝x(mod16811)＝483 其餘數字處理過程類似，最後編碼的結果如表2所示。
表2整數對應的碼字
權利要求
1.一種碼字表加解密的方法，其特徵在於，
加密過程主要步驟包括
1)首先，對碼字表τ字母表∑1和∑2中的元素排序，令其為
∑1＝{a1，a2，…，an}，∑2＝{b1，b2，…，bt，！}
其中ai為字符，bi為字符，「！」為結束符；
2)對於值域中的每個碼字wi，我們也先按它和字母表∑1中字母的對應關係，對其排序為
f(∑1)＝{w1，w2，..wn}
其中，ai→wi。找出值域f(∑1)中最長的碼字wk，其長度表示為l，使用映射函數g∑2l作用於{w1，w2，..wn}，這樣，依照原來的順序的對應關係，形成一個新的集合
其中，αi為a對應的碼字wi的算術編碼，Γ為碼字對應編碼的集合，Γ中每個元素都是區間_，(|∑2|)l+1上的一個數；
3)對Γ中的數字進行處理，使這個集合對應一個數字，我們將Γ變換成一個同餘方程組
x≡α1(modm1)
x≡α2(modm2)
...
x≡αn(modmn)
其中，x為碼字對應的數字，mi為模數；
4)利用中國剩餘定理可以計算得到唯一的x
其中，
所述解密過程主要步驟包括
1)計算出B＝(t+1)l+1，其中B為進行區間轉換映射到數字時的區間長度，t為集合∑2中字符的個數(不包含結束符)；
2)根據讀入的當前字母a，我們首先從字母表信息中獲得此字母的位置值i，計算大於B的第i個最小的素數mi；
3)求得αi＝xmodmi，αi正是α對應的碼字wi的算術編碼；
4)根據映射函數g∑2l，對αi這些進行區間轉換的逆運算後得到的字符串就是碼字wi，用公式表示，由ai獲得它的編碼的函數為
也即其中Pri(a)表示大於a的第i個最小的素數。
2.根據權利要求1所述的碼字表加解密的方法，其特徵在於，所述加密過程步驟2)中的映射函數g∑2l定義如下
1)求出區間總長度B＝(t+1)l+1，以及每個字符出現的概率n＝1/(t+1)，求出子區間B1＝B*n，並按順序將其分配給∑2中的字符bi和結束符「！」；
2)根據碼字wi的第一個字符確定下一個區間範圍；
3)將上一個步驟所得的區間範圍再按照概率再一次平分給字符bi和結束符號「！」；
4)再根據碼字wi的下一個字符確定下一個區間範圍；
5)將上一個步驟所得的區間範圍再按照概率再一次平分給字符bi和結束符號「！」；
6)如此循環步驟4)、5)，直到碼字wi的所有字符都經歷過，那麼最後一次平分後，結束符」！」所佔的區間的第一個數即為碼字wi所對應的算術編碼αi。
3.根據權利要求1所述的碼字表加解密的方法，其特徵在於，所述加密過程步驟3)中模數mi的定義如下
找出值域f(∑1)中最長的碼字wk，其長度表示為l，區間長度為B＝(t+1)l+1，那麼αk最大不會超過(t+1)l+1，並且Γ所有其它元素的值也不會超過(t+1)l+1，取mi為大於(t+1)l+1的第i個最小的素數，這樣就可以保證x一定存在，即
mi＝Pri((t+1)l+1)
其中Pr(a)表示大於a的第i個最小的素數。
全文摘要
本發明公開了一種碼字表的加解密的方法，它應用於信息安全技術領域。給定一個碼字表τ，即給定一個輸入字母表∑1，輸出字母表∑2和∑2上一個語言，明文碼字表τ被加密成明文四元組(∑1，∑2，l，x)，其中l表示語言中最長的字的長度，x是被加密的正整數。反之，依據上面的正整數x及相關的四元組(∑1，∑2，l，x)，則可唯一地恢復與之相對應的碼字表τ。本發明實現了將明文碼字表加密為一個正整數，則極大地提高了以「碼字表」作為對稱密碼體制中的密鑰的管理的安全性，也極大地減少了存儲碼字表時所佔用的空間。
文檔編號G09C1/00GK101149881SQ200710031028
公開日2008年3月26日 申請日期2007年10月24日 優先權日2007年10月24日
發明者龍冬陽 申請人:龍冬陽