一种码字表加解密方法
专利名称：一种码字表加解密方法
技术领域：
该发明技术主要应用在“信息安全技术”和“数据存贮与管理”等领域
背景技术：
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日
发明者龙冬阳 申请人:龙冬阳
技术领域：
该发明技术主要应用在“信息安全技术”和“数据存贮与管理”等领域
背景技术：
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日
发明者龙冬阳 申请人:龙冬阳
最新回复(0)