独特码密码集生成方法
专利名称：独特码密码集生成方法
技术领域：
本发明涉及的是一种编码技术领域的方法，具体的说，涉及的是一种独特码密码集生成方法。
背景技术：
在工程中需要这样一种编码，它被自然界偶然产生的概率尽可能的小。对于满足这一条件的称之为独特码。独特码是一种应用在对于安全有极高要求的领域的密码，例如政府重要部门，银行保险系统、重要信息安保系统、医疗要害设备等。
以前对于独特码的研究主要是集中在其需具备的数学特征上。J.Arlin.Cooper的SANDIA REPORT(山地亚报告)《Mathematical Aspects ofUnique Signals Assessment》(独特码的数学评估)及Jacqueline D.Leyland的《Unique Signal Analysis and Synthesis Project》(独特码的分析与合成项目)中详细论述了独特码的数学要求。主要包括编码事件的种类、编码长度、码元对的分布、码串的重复、取反重复、镜像重复等问题。但是国内外现有的公开文献中只是探讨独特码的数学标准及归类方法，其生成一般使用传统的穷举法，生成的效率低，并且文献中找不到成熟的生成符合这些要求的编码集的方法。所以在已经使用独特码编码的场合，其编码没有形成完备的码集体系，这一点极大的限制了独特码的发展与使用。
发明内容
本发明的目的在于克服现有技术的不足，提供一种生成基于所设定数学标准的独特码的完备集的方法。本发明特点在于与具体的数学标准无关，可以生成任意编码类型及码长的码集，为独特码的大规模应用打下了基础。本发明生成的部分编码已通过编码固化技术转化为固定机械结构后批量生产微机械密码锁，应用于国防及电脑安全认证等领域。
本发明是通过以下技术方案实现的，本发明采用改进的穷举法快速生成符合所指定数学标准的特定码长编码的完全集合，由以下步骤组成(1)首先将数学标准分为两类①过程数学标准如果一串编码违反了一条此类标准，则由其组成的更长的码串也必定违反这条标准。例如编码中不含有长度超过6位的重复码串就是一条过程数学标准。因为显而易见如果一串编码中包含长度超过6位的重复码串则由其组成的编码也必定包含长度超过6位的重复码串。
②最终数学标准如果一串编码违反了一条此类标准，但由其组成的更长的码串也不一定违反这条标准。例如二元编码中事件a与b的数量相等就是一条最终数学标准。因为码串aaab违反了这条标准但由其组成的码串aaababbb却符合这条标准。
(2)其次对编码进行处理并生成码集①将编码的长度一分为二，并使两部分的长度尽可能的相等。重复这一过程直到编码的长度小于等于3，并记录下拆分过程中所需的码串长度，例如24位长的编码可被分成两部分12位长的编码，12位编码又可被分成两部分6位长的编码，6位编码最终被分成两部分3位长的编码，所需的码串长度为3，6，12，24；②穷举出①中所需最短编码的所有码串并记入集合Gi1、Gj1，其中i1、j1为码串长度。例如3位二元编码共有8种码串(aaa，aab，aba，baa，abb，bab，bba，bbb)；③穷举出Gi1、Gj1中所有码串所组合成的长度为i1+j1的码串，并判断其是否符合过程数学标准，将符合标准的记入新集合Gi2(i2＝i1+j1)，同样的方法可得Gj2；④重复步骤③，直到生成的码串长度等于所要求的长度；⑤用最终数学标准判断所生成的集合，将符合要求的编码记入集合Gn。Gn即为符合指定数学要求的特定码长编码的完全集。在此步中可以通过为设置的每条数学标准打分，记每个编码的总分Score=Σi=1nSi,]]>其中Si为编码在标准i上获得的分数，n为所设数学标准的总数。设置每个编码的总分必需小于等于的值Smin，当某一编码的总分Score≤Smin时其为符合要求的编码，反之则不符合要求，从而可以综合判断每一个编码。
使用本发明上述改进的穷举法有以下优点(1)判别的码串的数量较传统的穷举法大为减少。(2)可生成符合指定数学要求的特定码长的编码的完备集(可证明)。完备集的生成可以在独特码大规模使用时避免出现合格编码数量不够、编码性质相近等问题，为其广泛的应用奠定了基础。(3)此方法与具体的数学要求无关，使用前只需将所设定的数学要求分为两类即可。所以此方法也可以用于多元密码。
本发明采用二维表格法判别任意两组编码中重复、取反重复、镜像重复以及取反镜像重复的码串，较好的解决了独特码中码串判别这一难点，为生成高质量编码及完备集铺平了道路。其实现过程如下(1)建立一张二维表格，将所需比较的编码置于两根坐标轴上；(2)填充表格，对于个两坐标的事件相同的格子填1，不同的填0；(3)判别每一条斜线就能判别出重复、取反重复、镜像重复以及取反镜像重复的码串。
上述的二维表格法的判别方法如下(1)任何斜线中全部由1组成的部分是由两个重复的码串组成的，由0组成的序列是由两个取反重复的序列组成的。
(2)主对角线方向的斜线表示重复和取反重复的码串，副对角线方向的码串表示的是镜像重复及取反镜像重复的码串。
(3)判别表格中的每一条斜线就可以找出两串编码中所有重复、取反重复、镜像重复，取反镜像重复的码串。因为对于任意两串编码中重复的码串，例如码串A中的xi…xj与码串B中的xk…xl重复或取反重复则可以从点(i，k)到点(j，l)的斜线来判别。如果它们镜像重复或取反镜像重复则可以通过点(j，k)到(i，l)的斜线来判别。
(4)对于判别一串编码中自身中的重复问题，通过将编码和自己相比较，即将一串编码置于表格的两根坐标轴上，由于此时表格完全对称，所以只需判别主对角线方向除主对角线(主对角线此时全为1)外的一半表格及副对角线方向包含副对角线的一半表格即可判别出编码中自身存在的所有重复、取反重复、镜像重复，取反镜像重复的码串。
另外此判别方法也可用于多元编码，可将任何多元编码置于两坐标轴上标记表格中每一个单元格，其X，Y坐标为同一事件的标1，不同事件的标0，然后与二元编码同样判别。或者将多元编码展开为二元编码，例如四元编码(A，B，C，D)可展开为(aa，ab，ba，bb)然后即可用表格法判别。
本发明通过一种改进的穷举法可以较快的生成具有各种特定数学特性独特码完备码集，从而解决了独特码的大规模应用问题。而且，对于具体数学要求中的编码中重复、取反重复、镜像重复以及取反镜像重复的认定问题则通过一种二维表格码串比较方法较好的加以解决，使通过现有计算机快速便捷的生成UQS码集成为可能。本发明生成的密码与MEMS(微机电系统)技术制造的微机械密码锁相结合可以用于安全有着很高要求的领域，如用于政府重要部门，银行保险系统、重要信息安保系统、医疗要害设备等对于安全有着特殊要求的场合。
图1为用较短码串集合生成较长码串集合的流程图具体实现方式以下结合本发明的技术方案和附图提供实施例以下实施例通过前面所述的方法生成了24位二元独特码编码集。其实现共需以下几个步骤(1)设定所需码集的长度和其数学标准；此次生成的码集设置的数学标准为1)二元码、码长24位、编码中A，B事件数量相等。符合此标准记S1＝0，若违反此标准则记S1＝1；2)二位码元对的分布平均、即(aa，ab，ba，bb)4种码串中有任意3种的数量为6，另一种一种为5。符合此标准记S2＝0，若违反此标准则记S2＝1；3)无超过6位的重复与取反重复码串，例如ababab与ababab为重复码串，与bababa为取反重复码串。符合此标准记S3＝0，若违反此标准则记S3=Σi=6ni2×xi,]]>n为重复或取反重复码串的最大长度，i为重复或取反重复码串的长度，xi为长度为i的重复或取反重复码串的数量；
4)无超过9位的镜像重复与取反镜像重复码串，例如aaaabbbbb与bbbbbaaaa为镜像重复与aaaaabbbb为镜像取反重复。符合此标准记S4＝0，若违反此标准则记S4=Σi=9ni2×xi,]]>n为镜像重复或取反镜像重复码串的最大长度，i为镜像重复或取反镜像重复码串的长度，xi为长度为i的镜像重复或取反镜像重复码串的数量；5)单一事件组成的码串长度不超过5，例如含有aaaaaa的码串就违反了此标准。符合此标准记S5＝0，若违反此标准则记S5=Σi=5ni2×ai+Σi=5mi2×bi,]]>n为单一A事件组成的超过5的码串的最大长度，m为单一B事件组成的超过5的码串的最大长度，i单一事件组成的码串的长度，ai为长度为i的单一A事件组成的码串的数量，bi为长度为i的单一B事件组成的码串的数量；6)具有独立A事件(bab)与B事件(aba)。若码串包含两种独立事件记S6＝0，包含一种独立事件记S6＝1，不含独立事件记S6＝2；7)独立的aa码串的数量大于等于独立的aaa大于等于独立的aaaa、独立的bb码串的数量大于等于独立的bbb大于等于独立的bbbb。符合此标准记S7＝0，若违反此标准则记S7＝2；8)独立的a的数量不等于独立的b的数量、独立的aa的数量不等于独立的bb的数量、独立的aaa的数量不等于独立的bbb的数量、独立的aaaa的数量不等于独立的bbbb的数量。符合此标准记S8＝0，若违反此标准则记S8＝2；(2)将上述标准规类为过程数学标准或最终数学标准并设定其总分的最小值Smin；此次编码的标准中无超过6位的重复与取反重复码串、无超过9位的镜像重复与取反镜像重复码串、单一事件组成的码串长度不超过5属于过程数学标准。其它数学标准均属于最终数学标准。Smin设为1。每个编码的分数Score=Σi=18Si.]]>最终生成的编码必须满足条件Score≤Smin。
在此过程种有以下几点需要注意1)通过改变Si的计分方法可以获得对数学标准偏重不同编码。2)编码集中的编码都是设定为小于Smin的，所以Smin越小集合中的编码性能越好，但Smin如果过小会导致编码集的容量过小(集合中编码数量过少)所以需要综合考虑编码集中编码的数学性能问题和其容量问题。3)对于重复、取反重复、镜像重复以及取反镜像重复的码串的统计可采用前面所述的表格法方便的获得。
(3)采用改进的穷举法所述的5个步骤生成所需的编码集要生成24位二元编码，需要以下步骤(1)将24位长的编码分成两部分长为12位的编码，再将12位编码分成两部分6长为位的编码，6位编码最终分成两部分3位长的编码；(2)穷举三位长的二元码串(aaa，aab，aba，baa，abb，bab，bba，bbb)记入集合Gi1，Gj1(i1＝i2＝3)；(3)穷举出Gi1，Gj1中所有码串所组合成的长度为6的码串，并判断其是否符合过程数学标准，即S3，S4，S5＜1。将符合标准的记入新集合Gi2(i2＝i1+j1)，如图1；(4)重复步骤(3)，直到生成的码串长度i4＝24；(5)用最终数学标准判断所生成的集合Gi4，将符合要求的编码记入集合G24。G24即为符合指定数学要求的特定码长编码的完全集。
其中二元码串自身中某些部分的重复、取反重复、镜像重复、取反镜像重复码串使用如下方法(1)将要找出自身中某些部分的重复、取反重复、镜像重复、取反镜像重复码串中码同时置于表格的X轴和Y轴上；(2)标记表格中每一个单元格，其X，Y坐标为同一事件的标1，不同的标0；(3)如表3、表4所示，统计表格中打*号部分中的每一条斜线上全为0或1的序列的长度及数量就可判别出两组编码中重复、取反重复、镜像重复以及取反镜像重复的码串。
如表1所示，表示的是码串aaaabbb与bbaabbbb用表格法来判别其中重复、取反重复、镜像重复以及取反镜像重复的部分。例如其中点(1，8)到点(3，6)的斜线全由0组成表示aaaabb与aabbbb取反镜像重复。
如表2所示，表示的是码串1中的xi…xj与码串2中的xk…xl重复或取反重复则可以从点(i，k)到点(j，l)的斜线来判别，它们中的镜像重复或取反镜像重复则可以通过点(j，k)到(i，l)的斜线来判别。
表1 表2 表3表4 用上述方法生成独特码有如下优点(1)判别的码串的数量较传统的穷举法大为减少。
例如传统的穷举法生成任何数学要求的二元24位编码集都需要判别224(16777216)个编码，而使用此方法生成过程数学要求为1)编码中不含长度超过6的重复或取反重复码串。
2)编码中不含长度超过9的镜像重复或取反镜像重复码串。
3)编码中不含长度超过4的全为a或b事件组成的码串。
需要判别编码的个数为6位码串8×8＝64，58个符合标准12位码串58×58＝3364，1974个符合标准(程序运行的结果)24位1974×1974＝3896676总共64+3364+3896676＝3900104＜＜16777216由于运算数量的大大减少，使得通过现有计算机快速生成具有较大码长的编码成为可能。
(2)可生成符合指定数学要求的特定码长的编码的完备集。完备集的生成可以在独特码大规模使用时避免出现合格编码数量不够、编码性质相近等问题，为其广泛的应用奠定了基础。
(3)此方法与具体的数学要求无关，使用前只需将前所设定的数学要求修改就可以获得不同性质的编码。所以此方法也可以用于多元密码，从而是独特码应用于更广阔的范围。
本实施例生成的24位编码码集经过密码机械固化后已被批量制造成微机械密码锁用于国防系统与电脑安全认证系统。并且在政府重要部门，银行保险系统、重要信息安保系统、医疗要害设备等方面有着广泛的应用前景。
本发明可以快速的生成符合指定数学要求的特定长度的独特码编码完全集。应用表格法可以方便快速的解决编码中重复、取反重复、镜像重复以及取反镜像重复的码串的判别问题。并且改进后的穷举法的运算速度较传统的穷举法生成码集大大加快。解决了原先独特码缺少生成完备码集，以及生成方法繁琐等问题，为其大规模应用打下了基础。
权利要求
1.一种独特码密码集生成方法，其特征在于，具体步骤如下(1)首先将数学标准分为两类①过程数学标准，如果一串编码违反了一条此类标准，则由其组成的更长的码串也必定违反这条标准；②最终数学标准，如果一串编码违反了一条此类标准，但由其组成的更长的码串也不一定违反这条标准；(2)其次对编码进行处理并生成码集①将编码的长度一分为二，并使两部分的长度尽可能的相等，重复这一过程直到编码的长度小于等于3，并记录下拆分过程中所需的码串长度；②穷举出①中所需最短编码的所有码串并记入集合Gi1、Gj1，其中i1、j1为码串长度；③穷举出Gi1、Gj1中所有码串所组合成的长度为i1+j1的码串，并判断其是否符合过程数学标准，将符合标准的记入新集合Gi2，i2＝i1+j1，同理得Gj2；④重复步骤③，直到生成的码串长度等于所要求的长度；⑤用最终数学标准判断所生成的集合，将符合要求的编码记入集合Gn，Gn即为符合指定数学要求的特定码长编码的完全集。
2.根据权利要求1所述的独特码密码集生成方法，其特征是所述的⑤中，为设置的每条数学标准打分，每个编码的总分Score=Σi=1nSi,]]>其中Si为编码在标准i上获得的分数，n为所设数学标准的总数，设置每个编码的总分必需小于等于的值Smin，当某一编码的总分Score≤Smin时其为符合要求的编码，反之则不符合要求，从而综合判断每一个编码。
3.根据权利要求1所述的独特码密码集生成方法，其特征是采用二维表格法判别任意两组编码中重复、取反重复、镜像重复以及取反镜像重复的码串，具体如下(1)建立一张二维表格，将所需比较的编码置于两根坐标轴上；(2)填充表格，对于个两坐标的事件相同的格子填1，不同的填0；(3)判别每一条斜线就能判别出重复、取反重复、镜像重复以及取反镜像重复的码串。
4.根据权利要求3所述的独特码密码集生成方法，其特征是表格法的判别方法如下(1)任何斜线中全部由1组成的部分是由两个重复的码串组成的，由0组成的序列是由两个取反重复的序列组成的；(2)主对角线方向的斜线表示重复和取反重复的码串，副对角线方向的码串表示的是镜像重复及取反镜像重复的码串；(3)判别表格中的每一条斜线就能找出两串编码中所有重复、取反重复、镜像重复，取反镜像重复的码串；(4)通过将编码和自己相比较，即将一串编码置于表格的两根坐标轴上，由于此时表格完全对称，只需判别主对角线方向除主对角线外的一半表格及副对角线方向包含副对角线的一半表格，即能判别出编码中自身存在的所有重复、取反重复、镜像重复，取反镜像重复的码串。
全文摘要
一种独特码密码集生成方法，属于编码技术领域。本发明采用改进的穷举法快速生成符合所指定数学标准的特定码长编码的完全集合，首先将数学标准分为两类①过程数学标准；②最终数学标准；其次对编码进行处理并生成码集；采用二维表格法判别任意两组编码中重复、取反重复、镜像重复以及取反镜像重复的码串。本发明特点在于与具体的数学标准无关，可以生成任意编码类型及码长的码集，为独特码的大规模应用打下了基础。本发明锁生成的密码与MEMS(微机电系统)技术制造的微机械密码锁相结合可以用于安全有着很高要求的领域。
文档编号G09C1/00GK1818993SQ20061002450
公开日2006年8月16日 申请日期2006年3月9日 优先权日2006年3月9日
发明者陈文元, 谈顺毅, 张卫平, 李胜勇, 冯敏华 申请人:上海交通大学
技术领域：
本发明涉及的是一种编码技术领域的方法，具体的说，涉及的是一种独特码密码集生成方法。
背景技术：
在工程中需要这样一种编码，它被自然界偶然产生的概率尽可能的小。对于满足这一条件的称之为独特码。独特码是一种应用在对于安全有极高要求的领域的密码，例如政府重要部门，银行保险系统、重要信息安保系统、医疗要害设备等。
以前对于独特码的研究主要是集中在其需具备的数学特征上。J.Arlin.Cooper的SANDIA REPORT(山地亚报告)《Mathematical Aspects ofUnique Signals Assessment》(独特码的数学评估)及Jacqueline D.Leyland的《Unique Signal Analysis and Synthesis Project》(独特码的分析与合成项目)中详细论述了独特码的数学要求。主要包括编码事件的种类、编码长度、码元对的分布、码串的重复、取反重复、镜像重复等问题。但是国内外现有的公开文献中只是探讨独特码的数学标准及归类方法，其生成一般使用传统的穷举法，生成的效率低，并且文献中找不到成熟的生成符合这些要求的编码集的方法。所以在已经使用独特码编码的场合，其编码没有形成完备的码集体系，这一点极大的限制了独特码的发展与使用。
发明内容
本发明的目的在于克服现有技术的不足，提供一种生成基于所设定数学标准的独特码的完备集的方法。本发明特点在于与具体的数学标准无关，可以生成任意编码类型及码长的码集，为独特码的大规模应用打下了基础。本发明生成的部分编码已通过编码固化技术转化为固定机械结构后批量生产微机械密码锁，应用于国防及电脑安全认证等领域。
本发明是通过以下技术方案实现的，本发明采用改进的穷举法快速生成符合所指定数学标准的特定码长编码的完全集合，由以下步骤组成(1)首先将数学标准分为两类①过程数学标准如果一串编码违反了一条此类标准，则由其组成的更长的码串也必定违反这条标准。例如编码中不含有长度超过6位的重复码串就是一条过程数学标准。因为显而易见如果一串编码中包含长度超过6位的重复码串则由其组成的编码也必定包含长度超过6位的重复码串。
②最终数学标准如果一串编码违反了一条此类标准，但由其组成的更长的码串也不一定违反这条标准。例如二元编码中事件a与b的数量相等就是一条最终数学标准。因为码串aaab违反了这条标准但由其组成的码串aaababbb却符合这条标准。
(2)其次对编码进行处理并生成码集①将编码的长度一分为二，并使两部分的长度尽可能的相等。重复这一过程直到编码的长度小于等于3，并记录下拆分过程中所需的码串长度，例如24位长的编码可被分成两部分12位长的编码，12位编码又可被分成两部分6位长的编码，6位编码最终被分成两部分3位长的编码，所需的码串长度为3，6，12，24；②穷举出①中所需最短编码的所有码串并记入集合Gi1、Gj1，其中i1、j1为码串长度。例如3位二元编码共有8种码串(aaa，aab，aba，baa，abb，bab，bba，bbb)；③穷举出Gi1、Gj1中所有码串所组合成的长度为i1+j1的码串，并判断其是否符合过程数学标准，将符合标准的记入新集合Gi2(i2＝i1+j1)，同样的方法可得Gj2；④重复步骤③，直到生成的码串长度等于所要求的长度；⑤用最终数学标准判断所生成的集合，将符合要求的编码记入集合Gn。Gn即为符合指定数学要求的特定码长编码的完全集。在此步中可以通过为设置的每条数学标准打分，记每个编码的总分Score=Σi=1nSi,]]>其中Si为编码在标准i上获得的分数，n为所设数学标准的总数。设置每个编码的总分必需小于等于的值Smin，当某一编码的总分Score≤Smin时其为符合要求的编码，反之则不符合要求，从而可以综合判断每一个编码。
使用本发明上述改进的穷举法有以下优点(1)判别的码串的数量较传统的穷举法大为减少。(2)可生成符合指定数学要求的特定码长的编码的完备集(可证明)。完备集的生成可以在独特码大规模使用时避免出现合格编码数量不够、编码性质相近等问题，为其广泛的应用奠定了基础。(3)此方法与具体的数学要求无关，使用前只需将所设定的数学要求分为两类即可。所以此方法也可以用于多元密码。
本发明采用二维表格法判别任意两组编码中重复、取反重复、镜像重复以及取反镜像重复的码串，较好的解决了独特码中码串判别这一难点，为生成高质量编码及完备集铺平了道路。其实现过程如下(1)建立一张二维表格，将所需比较的编码置于两根坐标轴上；(2)填充表格，对于个两坐标的事件相同的格子填1，不同的填0；(3)判别每一条斜线就能判别出重复、取反重复、镜像重复以及取反镜像重复的码串。
上述的二维表格法的判别方法如下(1)任何斜线中全部由1组成的部分是由两个重复的码串组成的，由0组成的序列是由两个取反重复的序列组成的。
(2)主对角线方向的斜线表示重复和取反重复的码串，副对角线方向的码串表示的是镜像重复及取反镜像重复的码串。
(3)判别表格中的每一条斜线就可以找出两串编码中所有重复、取反重复、镜像重复，取反镜像重复的码串。因为对于任意两串编码中重复的码串，例如码串A中的xi…xj与码串B中的xk…xl重复或取反重复则可以从点(i，k)到点(j，l)的斜线来判别。如果它们镜像重复或取反镜像重复则可以通过点(j，k)到(i，l)的斜线来判别。
(4)对于判别一串编码中自身中的重复问题，通过将编码和自己相比较，即将一串编码置于表格的两根坐标轴上，由于此时表格完全对称，所以只需判别主对角线方向除主对角线(主对角线此时全为1)外的一半表格及副对角线方向包含副对角线的一半表格即可判别出编码中自身存在的所有重复、取反重复、镜像重复，取反镜像重复的码串。
另外此判别方法也可用于多元编码，可将任何多元编码置于两坐标轴上标记表格中每一个单元格，其X，Y坐标为同一事件的标1，不同事件的标0，然后与二元编码同样判别。或者将多元编码展开为二元编码，例如四元编码(A，B，C，D)可展开为(aa，ab，ba，bb)然后即可用表格法判别。
本发明通过一种改进的穷举法可以较快的生成具有各种特定数学特性独特码完备码集，从而解决了独特码的大规模应用问题。而且，对于具体数学要求中的编码中重复、取反重复、镜像重复以及取反镜像重复的认定问题则通过一种二维表格码串比较方法较好的加以解决，使通过现有计算机快速便捷的生成UQS码集成为可能。本发明生成的密码与MEMS(微机电系统)技术制造的微机械密码锁相结合可以用于安全有着很高要求的领域，如用于政府重要部门，银行保险系统、重要信息安保系统、医疗要害设备等对于安全有着特殊要求的场合。
图1为用较短码串集合生成较长码串集合的流程图具体实现方式以下结合本发明的技术方案和附图提供实施例以下实施例通过前面所述的方法生成了24位二元独特码编码集。其实现共需以下几个步骤(1)设定所需码集的长度和其数学标准；此次生成的码集设置的数学标准为1)二元码、码长24位、编码中A，B事件数量相等。符合此标准记S1＝0，若违反此标准则记S1＝1；2)二位码元对的分布平均、即(aa，ab，ba，bb)4种码串中有任意3种的数量为6，另一种一种为5。符合此标准记S2＝0，若违反此标准则记S2＝1；3)无超过6位的重复与取反重复码串，例如ababab与ababab为重复码串，与bababa为取反重复码串。符合此标准记S3＝0，若违反此标准则记S3=Σi=6ni2×xi,]]>n为重复或取反重复码串的最大长度，i为重复或取反重复码串的长度，xi为长度为i的重复或取反重复码串的数量；
4)无超过9位的镜像重复与取反镜像重复码串，例如aaaabbbbb与bbbbbaaaa为镜像重复与aaaaabbbb为镜像取反重复。符合此标准记S4＝0，若违反此标准则记S4=Σi=9ni2×xi,]]>n为镜像重复或取反镜像重复码串的最大长度，i为镜像重复或取反镜像重复码串的长度，xi为长度为i的镜像重复或取反镜像重复码串的数量；5)单一事件组成的码串长度不超过5，例如含有aaaaaa的码串就违反了此标准。符合此标准记S5＝0，若违反此标准则记S5=Σi=5ni2×ai+Σi=5mi2×bi,]]>n为单一A事件组成的超过5的码串的最大长度，m为单一B事件组成的超过5的码串的最大长度，i单一事件组成的码串的长度，ai为长度为i的单一A事件组成的码串的数量，bi为长度为i的单一B事件组成的码串的数量；6)具有独立A事件(bab)与B事件(aba)。若码串包含两种独立事件记S6＝0，包含一种独立事件记S6＝1，不含独立事件记S6＝2；7)独立的aa码串的数量大于等于独立的aaa大于等于独立的aaaa、独立的bb码串的数量大于等于独立的bbb大于等于独立的bbbb。符合此标准记S7＝0，若违反此标准则记S7＝2；8)独立的a的数量不等于独立的b的数量、独立的aa的数量不等于独立的bb的数量、独立的aaa的数量不等于独立的bbb的数量、独立的aaaa的数量不等于独立的bbbb的数量。符合此标准记S8＝0，若违反此标准则记S8＝2；(2)将上述标准规类为过程数学标准或最终数学标准并设定其总分的最小值Smin；此次编码的标准中无超过6位的重复与取反重复码串、无超过9位的镜像重复与取反镜像重复码串、单一事件组成的码串长度不超过5属于过程数学标准。其它数学标准均属于最终数学标准。Smin设为1。每个编码的分数Score=Σi=18Si.]]>最终生成的编码必须满足条件Score≤Smin。
在此过程种有以下几点需要注意1)通过改变Si的计分方法可以获得对数学标准偏重不同编码。2)编码集中的编码都是设定为小于Smin的，所以Smin越小集合中的编码性能越好，但Smin如果过小会导致编码集的容量过小(集合中编码数量过少)所以需要综合考虑编码集中编码的数学性能问题和其容量问题。3)对于重复、取反重复、镜像重复以及取反镜像重复的码串的统计可采用前面所述的表格法方便的获得。
(3)采用改进的穷举法所述的5个步骤生成所需的编码集要生成24位二元编码，需要以下步骤(1)将24位长的编码分成两部分长为12位的编码，再将12位编码分成两部分6长为位的编码，6位编码最终分成两部分3位长的编码；(2)穷举三位长的二元码串(aaa，aab，aba，baa，abb，bab，bba，bbb)记入集合Gi1，Gj1(i1＝i2＝3)；(3)穷举出Gi1，Gj1中所有码串所组合成的长度为6的码串，并判断其是否符合过程数学标准，即S3，S4，S5＜1。将符合标准的记入新集合Gi2(i2＝i1+j1)，如图1；(4)重复步骤(3)，直到生成的码串长度i4＝24；(5)用最终数学标准判断所生成的集合Gi4，将符合要求的编码记入集合G24。G24即为符合指定数学要求的特定码长编码的完全集。
其中二元码串自身中某些部分的重复、取反重复、镜像重复、取反镜像重复码串使用如下方法(1)将要找出自身中某些部分的重复、取反重复、镜像重复、取反镜像重复码串中码同时置于表格的X轴和Y轴上；(2)标记表格中每一个单元格，其X，Y坐标为同一事件的标1，不同的标0；(3)如表3、表4所示，统计表格中打*号部分中的每一条斜线上全为0或1的序列的长度及数量就可判别出两组编码中重复、取反重复、镜像重复以及取反镜像重复的码串。
如表1所示，表示的是码串aaaabbb与bbaabbbb用表格法来判别其中重复、取反重复、镜像重复以及取反镜像重复的部分。例如其中点(1，8)到点(3，6)的斜线全由0组成表示aaaabb与aabbbb取反镜像重复。
如表2所示，表示的是码串1中的xi…xj与码串2中的xk…xl重复或取反重复则可以从点(i，k)到点(j，l)的斜线来判别，它们中的镜像重复或取反镜像重复则可以通过点(j，k)到(i，l)的斜线来判别。
表1 表2 表3表4 用上述方法生成独特码有如下优点(1)判别的码串的数量较传统的穷举法大为减少。
例如传统的穷举法生成任何数学要求的二元24位编码集都需要判别224(16777216)个编码，而使用此方法生成过程数学要求为1)编码中不含长度超过6的重复或取反重复码串。
2)编码中不含长度超过9的镜像重复或取反镜像重复码串。
3)编码中不含长度超过4的全为a或b事件组成的码串。
需要判别编码的个数为6位码串8×8＝64，58个符合标准12位码串58×58＝3364，1974个符合标准(程序运行的结果)24位1974×1974＝3896676总共64+3364+3896676＝3900104＜＜16777216由于运算数量的大大减少，使得通过现有计算机快速生成具有较大码长的编码成为可能。
(2)可生成符合指定数学要求的特定码长的编码的完备集。完备集的生成可以在独特码大规模使用时避免出现合格编码数量不够、编码性质相近等问题，为其广泛的应用奠定了基础。
(3)此方法与具体的数学要求无关，使用前只需将前所设定的数学要求修改就可以获得不同性质的编码。所以此方法也可以用于多元密码，从而是独特码应用于更广阔的范围。
本实施例生成的24位编码码集经过密码机械固化后已被批量制造成微机械密码锁用于国防系统与电脑安全认证系统。并且在政府重要部门，银行保险系统、重要信息安保系统、医疗要害设备等方面有着广泛的应用前景。
本发明可以快速的生成符合指定数学要求的特定长度的独特码编码完全集。应用表格法可以方便快速的解决编码中重复、取反重复、镜像重复以及取反镜像重复的码串的判别问题。并且改进后的穷举法的运算速度较传统的穷举法生成码集大大加快。解决了原先独特码缺少生成完备码集，以及生成方法繁琐等问题，为其大规模应用打下了基础。
权利要求
1.一种独特码密码集生成方法，其特征在于，具体步骤如下(1)首先将数学标准分为两类①过程数学标准，如果一串编码违反了一条此类标准，则由其组成的更长的码串也必定违反这条标准；②最终数学标准，如果一串编码违反了一条此类标准，但由其组成的更长的码串也不一定违反这条标准；(2)其次对编码进行处理并生成码集①将编码的长度一分为二，并使两部分的长度尽可能的相等，重复这一过程直到编码的长度小于等于3，并记录下拆分过程中所需的码串长度；②穷举出①中所需最短编码的所有码串并记入集合Gi1、Gj1，其中i1、j1为码串长度；③穷举出Gi1、Gj1中所有码串所组合成的长度为i1+j1的码串，并判断其是否符合过程数学标准，将符合标准的记入新集合Gi2，i2＝i1+j1，同理得Gj2；④重复步骤③，直到生成的码串长度等于所要求的长度；⑤用最终数学标准判断所生成的集合，将符合要求的编码记入集合Gn，Gn即为符合指定数学要求的特定码长编码的完全集。
2.根据权利要求1所述的独特码密码集生成方法，其特征是所述的⑤中，为设置的每条数学标准打分，每个编码的总分Score=Σi=1nSi,]]>其中Si为编码在标准i上获得的分数，n为所设数学标准的总数，设置每个编码的总分必需小于等于的值Smin，当某一编码的总分Score≤Smin时其为符合要求的编码，反之则不符合要求，从而综合判断每一个编码。
3.根据权利要求1所述的独特码密码集生成方法，其特征是采用二维表格法判别任意两组编码中重复、取反重复、镜像重复以及取反镜像重复的码串，具体如下(1)建立一张二维表格，将所需比较的编码置于两根坐标轴上；(2)填充表格，对于个两坐标的事件相同的格子填1，不同的填0；(3)判别每一条斜线就能判别出重复、取反重复、镜像重复以及取反镜像重复的码串。
4.根据权利要求3所述的独特码密码集生成方法，其特征是表格法的判别方法如下(1)任何斜线中全部由1组成的部分是由两个重复的码串组成的，由0组成的序列是由两个取反重复的序列组成的；(2)主对角线方向的斜线表示重复和取反重复的码串，副对角线方向的码串表示的是镜像重复及取反镜像重复的码串；(3)判别表格中的每一条斜线就能找出两串编码中所有重复、取反重复、镜像重复，取反镜像重复的码串；(4)通过将编码和自己相比较，即将一串编码置于表格的两根坐标轴上，由于此时表格完全对称，只需判别主对角线方向除主对角线外的一半表格及副对角线方向包含副对角线的一半表格，即能判别出编码中自身存在的所有重复、取反重复、镜像重复，取反镜像重复的码串。
全文摘要
一种独特码密码集生成方法，属于编码技术领域。本发明采用改进的穷举法快速生成符合所指定数学标准的特定码长编码的完全集合，首先将数学标准分为两类①过程数学标准；②最终数学标准；其次对编码进行处理并生成码集；采用二维表格法判别任意两组编码中重复、取反重复、镜像重复以及取反镜像重复的码串。本发明特点在于与具体的数学标准无关，可以生成任意编码类型及码长的码集，为独特码的大规模应用打下了基础。本发明锁生成的密码与MEMS(微机电系统)技术制造的微机械密码锁相结合可以用于安全有着很高要求的领域。
文档编号G09C1/00GK1818993SQ20061002450
公开日2006年8月16日 申请日期2006年3月9日 优先权日2006年3月9日
发明者陈文元, 谈顺毅, 张卫平, 李胜勇, 冯敏华 申请人:上海交通大学
最新回复(0)