一种基于Petri网的分组密码体制的分析

一种基于Petri网的分组密码体制的分析刘培顺算法提出者：吴哲辉山东科技大学信息科学与工程学院中国泰安提纲引言Petri网理论向量的全序化密钥与加(解)密算法算法性能及安全性分析改进措施1.引言通过Petri网的运行、整数素因子分解和合成以及对整数和非负整数向量的排序来确定一个2K元置换，从而构建一个分组长度为k位的分组密码该密码体制是一次一密的，分组长度k是可以改变的2Petri网理论—定义定义1三元式N=(S,T;F)称作网，当且仅当（1）S∪T≠,S∩T=（2）F(ST)∪(TS)（3）dom(F)∪cod(F)=S∪TxS∪T,称˙x={y|(yS∪T)∧((y,x)F)}和x˙={y|(yS∪T)∧((x,y)F)}分别称为x的前置集和后置集2Petri网理论—定义定义2四元式PN=(S,T;F,M0)称作Petri网,当且仅当(1)N=(S,T;F)是一个网(2)M:S→Z(非负整数集)为标识函数,其中M0是初始标识(初始状态)(3)引发规则:(3.1)变迁tT称为状态M下使能的,当且仅当s˙t:M(p)≥1,记作;(3.2)在M下是使能的变迁t可以引发状态变化,引发后得到后继标识M’,则记作.)(1)(1)()('....否则若若sMttssMttssMsM'[MtMtM[例子2Petri网理论记R(M0)为Petri网PN的从M0可达的所有状态集合,则称R(M0)为Petri网PN的可达状态集合11121121[,,,,,[:,1,,,,,kkiiiikMMMtttMtMTtkiMMMPN记作下是使能的在则称变迁序列使得如果中在2Petri网理论—代数分析方法PN的一个状态M可以用一个非负整数的m维向量表示(M(i)=M(pi)),仍记作M..011|,||,|,][....否则若若并且其中表示矩阵的结构可以用一个关联网一个iijiijijmnijttsttscTnSmcCPNPetri例子2Petri网理论—代数分析方法的状态方程网为则称如果PNPetriXCMMTMRMMMMT,'*,),(',,'[0.},,2,1{),/(#)(.)/(#,[:)(*,0的发射向量为发射序列则称向量令中出现的个数在为记若XnitiXttMMRMTi2Petri网理论—代数分析方法.,,),(,);,(,||,),;,(3000的可达向量称为向量网系统为一个唯一可达那么称方程满足状态维非负整数向量都有唯一的一个如果对的关联矩阵网为为一个网设定义MXXAMMXnMRMFTSNAnTMFTST.,),(,,);,(400为一个唯一可达向量网则称向量网系统都是一个唯一可达标识标识若对任意初始为一个网设定义NMNMFTSN2Petri网理论—代数分析方法).,0(,0,);,(,||,);,(5不变量的一个称为网时满足是非平凡的非负整数且当不变量的一个广义为网则称满足量维向如果非平凡的的关联矩阵为网为一个网设定义TNXXAXTNXXAXnFTSNAnTFTSNTT.);,(1不变量不存在广义且仅当当是一个唯一可达向量网网引理TNFTSN2Petri网理论—代数分析方法定理1设A为N=(S,T;F)的关联矩阵,N为唯一可达向量网,当且仅当A是一个行满秩矩阵,即r(A)=|T|.网N是结构有界网的充分必要条件是,存在m(M=|S|)维非负整数向量y,使得Ay≤0,其中A是网N的关联矩阵.推论1网N=(S,T;F)为一个结构无界的唯一可达向量网的充分必要条件是:(1)N的关联矩阵A的秩等于|T|.(2)不存在|S|维非负整数向量y,使得Ay≤0.2Petri网原理—图论分析方法2li21lll2ll02121ll0l000l0lll0l0Mt[Mt)M,M(I,TE:I}Mt[M:Tt|)M(RM,M|)M,M{(Ei)(|RGM),1,2,i(i||M[M0)(|RGM}l||M[M|)M(RM{|)M(Rl)I,E,|)M(R()(|RG)MF,T;S,7，当且仅当且级结点。的第为则称级结点，若的第称为其中级）部分可达标识图。的一个（称为图可达向量网系统，多级为一个无界的唯一（设定义例子2Petri网原理例1图1给出一个无界Petri网S1T1S2T4S5T2T3S3S4S6010010111100011000111001A.]101000[M,4n,6m),M,F;T,S(T00它的关联矩阵为：其中图1一个无界的唯一向量网系统返回2Petri网原理通过这个部分有向图可以看出：（1）RG|7(Σ)中没有有向回路。（2）若从M0到某个Mi有多条有向路，那么这些有向路的长度都是相同的。而且尽管不同的路径对应的变迁序列不同，但它们出现数是相同的。)101000(0M)011010(1M)100101(2M)002020(3M)010111(4M)001121(5M)110001(6M)000222(7M)101011(8M)020011(9M)100112(10M)011021(11M)200002(12M)010122(13M)002031(14M)110012(15M)001132(16Mt1t3t2t1t3t4t2t3t4t2t1t3t4t2t1t3t2t4t1t4t1t3t2t3图2Σ的部分可达标识图RG|7(Σ)返回3向量的全序化定义7向量的对角线序.VV),j(VjV1,j,,2,1i)i(ViV},n,,3,2{jVV)1(V1V)i(V)i(V)2(.VV,)i(V)i(V(1)V~V,VV~nV~2d121212d121n1i2n1i12d1n1i2n1i121d则）（但）（使得。若则）（时，若当则若定义为：对序上的对角线维非负整数向量集，为一个设3向量的全序化定理2种成立。两种情况必有且仅有一和时，当即对是一种全序关系上的对角线序维向量集12212121VVVVVV,V~V,V,V~dddn3向量的全序化定义6非负整数向量的赋值序.)(,)()(},,,{,)2(},,,{,,,,11)(212121个分量值的第是向量其中的一个赋值关于为对向量则称赋值维若给定一组维非负整数向量为一个设维赋值。为一组那么称时个素数，且为）设（iViVAVPVAPPPAmmVmPPPAPPjimPPPmmiiVimmmmmjim3向量的全序化立。必有且仅有一种情况成和则若当且仅当那么对维赋值。为一组维非负整数向量集为一个设定理)()()()()2()()()1(~,},,,{,~312212121212121VAVAVAVAVVVVVAVAVVVmPPPAmVmmmmmmmm4密钥与加解密算法系统参数1],[02100],[002|)(2}||[|)({|)(),;,(2121kllkllMRllMMMRMMRAMFTS中元素的个数满足的部分可达标识集的关联矩阵，是网系统，向量为一个无界的唯一可达设4密钥与加解密算法构造方法码的分组密码。），位（构建一个元置换，从而序就确定了一个排序。这两种不同的顺按对角线序并对这些非负整数向量即对应的可达向量个另一方面，可以求出每满足为集合个标识。记这些标识的前值的大小排序，并选出对这些赋值按整数的赋值可以求出每个的库所的一组赋值根据事先给定的对-102)()()()(},,,{)(2),(|)(},,,,{002210],[0||2121kXAMMXMSRMMAMAjiMMMMSRMAMRPPPAkiTiiijSiSksllSSk4密钥与加解密算法密钥本密码体制把密钥分成两部分：秘密传送部分和公开传送部分。秘密传送部分包括包括一个结构无界的唯一可达向量网N(S,T;F)或者说是一个|T|行|S|列的(1,0,-1)-矩阵，该矩阵满足推论2.1中的两个条件，以及对网N的库所的一组|S|维赋值A{P1,P2,…,P|S|}，其中素数Pi对应库所i(i1,2,…,|S|)。公开传送部分为3个整数：A(M0),l1,l2,其中A(M0)为根据|S|元赋值As计算出来的初始标识M0的赋值。一般地有0≤l1l2。||1)(00)(SjSMjsjPMA4密钥与加解密算法算法1加密算法输入：(1)网N的关联矩阵。(2)|S|维赋值A{P1,P2,…,P|S|}。(3)初始标识M0，M0应该选择使得(N,M0)为一个无界Petri网。(4)明文(01)n(即设x是一个n位(0,1)-码)，分组长度k(不妨设nkm)。输出：AS(M0),l1,l2,y。其中y(01)n是明文x对应的密文。4密钥与加解密算法算法步骤.,,),()(5.,.2)2(,,,,,,4)2(,,,,,,,,,3.},,,,{)(2,)(|)(2.2|)(|2,2|)(|,),(12100r21r21212212210||1)(],[01],[0102021212yllMAMAStepyxkrXXXMMMSteprXXXXXXXMStepMMMMSRPMAMRMStepMRlMRlMNStepsskkkiriiiikSjSMjsllkllkklkkj并输出计算译码为密文根据分组密码把明文的分组密码从而产生一个长度为元置换一个的对应关系确定根据标识及其可达向量和由设为据对角线序排序根把出对应的发生数向量根据部分可达标识图求对每个序的这里的标识是按赋值排组合个选出前并对它们排序求出赋值对每个使并选取使的部分可达标识图的变迁发生序列长度构造4密钥与加解密算法解密算法在解密算法中，把网结构N，对网N的库所赋值AS以及接收到的作为输入。初始标识M0和分组长度k在算法执行过程中求出。输出结果是明文x。yllMAS,,),(2104密钥与加解密算法例2图1给出一个无界Petri网S1T1S2T4S5T2T3S3S4S6010010111100011000111001A.]101000[M,4n,6m),M,F;T,S(T00它的关联矩阵为：其中图1一个无界的唯一向量网系统)3,2,13,7,11,5(6SA维赋值为4密钥与加解密算法选取k=4,M0=(101000),则网N的步伐可达标识图如图1所示。选取SR(M0)=R(M0)|[1,7]求出这16个标识向量的赋值，并按照赋值大小顺序进行排序可以得到下面的序号/标识对照表)101000(0M)011010(1M)100101(2M)002020(3M)010111(4M)001121(5M)110001(6M)000222(7M)101011(8M)020011(9M)100112(10M)011021(11M)200002(12M)010122(13M)002031(14M)110012(15M)001132(16Mt1t3t2t1t3t4t2t3t4t2t1t3t4t2t1t3t2t4t1t4t1t3t2t34密钥与加解密算法6552)(990)(1176)(5148)(225)(924)(1170)(726)(210)(6084)(165)(1092)(858)(196)(195)(154)(16151413121110987654321MAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMASSSSSSSSSSSSSSSS序号标识序号标识序号标识序号标识0000M10100M81000M111100M1