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

《一种基于Petri网的分组密码体制的分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一种基于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

2、={y

3、(yS∪T)∧((y,x)F)}和x˙={y

4、(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’,则记作例子2Petri网理论记R(M0)为Petri网PN的从M0可达的所有状态集

5、合,则称R(M0)为Petri网PN的可达状态集合2Petri网理论—代数分析方法PN的一个状态M可以用一个非负整数的m维向量表示(M(i)=M(pi)),仍记作M.例子2Petri网理论—代数分析方法2Petri网理论—代数分析方法2Petri网理论—代数分析方法2Petri网理论—代数分析方法定理1设A为N=(S,T;F)的关联矩阵,N为唯一可达向量网,当且仅当A是一个行满秩矩阵,即r(A)=

6、T

7、.网N是结构有界网的充分必要条件是,存在m(M=

8、S

9、)维非负整数向量y,使得Ay≤0,其中A是网N的关联矩阵.推论1网N=(S,T;F)为一个结构无界的唯

10、一可达向量网的充分必要条件是:(1)N的关联矩阵A的秩等于

11、T

12、.(2)不存在

13、S

14、维非负整数向量y,使得Ay≤0.2Petri网原理—图论分析方法例子2Petri网原理例1图1给出一个无界Petri网图1一个无界的唯一向量网系统返回2Petri网原理通过这个部分有向图可以看出：（1）RG

15、7(Σ)中没有有向回路。（2）若从M0到某个Mi有多条有向路，那么这些有向路的长度都是相同的。而且尽管不同的路径对应的变迁序列不同，但它们出现数是相同的。图2Σ的部分可达标识图RG

16、7(Σ)返回3向量的全序化定义7向量的对角线序3向量的全序化定理23向量的全序化定义6非

17、负整数向量的赋值序3向量的全序化4密钥与加解密算法系统参数4密钥与加解密算法构造方法4密钥与加解密算法密钥本密码体制把密钥分成两部分：秘密传送部分和公开传送部分。秘密传送部分包括包括一个结构无界的唯一可达向量网N=(S,T;F)或者说是一个

18、T

19、行

20、S

21、列的(1,0,-1)-矩阵，该矩阵满足推论2.1中的两个条件，以及对网N的库所的一组

22、S

23、维赋值As={P1,P2,…,P

24、S

25、}，其中素数Pi对应库所si(i=1,2,…,

26、S

27、)。公开传送部分为3个整数：As(M0),l1,l2,其中As(M0)为根据

28、S

29、元赋值As计算出来的初始标识M0的赋值。一般地

30、有0≤l1

31、S

32、维赋值As={P1,P2,…,P

33、S

34、}。(3)初始标识M0，M0应该选择使得(N,M0)为一个无界Petri网。(4)明文x∈(0+1)n(即设x是一个n位(0,1)-码)，分组长度k(不妨设n=km)。输出：AS(M0),l1,l2,y。其中y∈(0+1)n是明文x对应的密文。4密钥与加解密算法算法步骤4密钥与加解密算法解密算法在解密算法中，把网结构N，对网N的库所赋值AS以及接收到的作为输入。初始标识M0和分组长度k在算法执行过程中求出。输出结果是明文x。4密钥

35、与加解密算法例2图1给出一个无界Petri网图1一个无界的唯一向量网系统4密钥与加解密算法选取k=4,M0=(101000),则网N的步伐可达标识图如图1所示。选取SR(M0)=R(M0)

36、[1,7]求出这16个标识向量的赋值，并按照赋值大小顺序进行排序可以得到下面的序号/标识对照表4密钥与加解密算法序号标识序号标识序号标识序号标识0000M10100M81000M111100M140001M60101M121001M151101M130010M20110M91010M51110M70011M30111M41011M101111M164密钥与加解密算法从图

37、2的部分可达标识图，对每个MI可以写出对应的可达向量VI。把它们按