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

1、提纲,引言 Petri网理论 向量的全序化 密钥与加(解)密算法 算法性能及安全性分析 改进措施,1.引言,通过Petri网的运行、整数素因子分解和合成以及对整数和非负整数向量的排序来确定一个2K元置换，从而构建一个分组长度为k位的分组密码 该密码体制是一次一密的，分组长度k是可以改变的,2 Petri网理论定义,定义1 三元式N=(S,T;F) 称作网，当且仅当 （1）ST,ST= （2）F (ST)(TS) （3）dom(F) cod(F)= ST x ST, 称 x= y | ( y ST ) ( y ,x ) F ) 和 x= y | ( y ST ) (x, y) F ) 分别称为x

2、的前置集和后置集,2 Petri网理论定义,定义2 四元式PN=(S,T;F,M0)称作Petri网,当且仅当 (1) N=(S,T;F)是一个网 (2) M:SZ(非负整数集)为标识函数,其中M0是初始标识(初始状态) (3)引发规则: (3.1)变迁tT称为状态M下使能的,当且仅当 st : M(p)1,记作; (3.2) 在M下是使能的变迁t可以引发状态变化,引发后得到后继标识M,则 记作,例子,2 Petri网理论,记R(M0)为Petri网PN 的从M0可达的所有状态集合,则称R(M0)为Petri网PN 的可达状态集合,2 Petri网理论代数分析方法,PN的一个状态M可以用一个非

3、负整数的m维向量表示(M(i)=M(pi),仍记作M.,例子,2 Petri网理论代数分析方法,2 Petri网理论代数分析方法,2 Petri网理论代数分析方法,2 Petri网理论代数分析方法,定理1 设A为N=(S,T;F)的关联矩阵,N为唯一可达向量网,当且仅当A是一个行满秩矩阵,即r(A)=|T|. 网N是结构有界网的充分必要条件是,存在m(M=|S|)维非负整数向量y,使得Ay0,其中A是网N的关联矩阵. 推论1 网N=(S,T;F)为一个结构无界的唯一可达向量网的充分必要条件是: (1)N的关联矩阵A的秩等于|T|. (2)不存在|S|维非负整数向量y,使得Ay0.,2Petri

4、 网原理图论分析方法,例子,2Petri 网原理,例1 图1给出一个无界Petri网,图1 一个无界的唯一向量网系统,返回,2Petri 网原理,通过这个部分有向图可以看出： （1） RG|7()中没有有向回路。 （2）若从M0到某个Mi有多条有向路，那么这些有向路的长度都是相同的。而且尽管不同的路径对应的变迁序列不同，但它们出现数是相同的。,图2 的部分可达标识图RG|7(),返回,3向量的全序化,定义7向量的对角线序,3向量的全序化,定理2,3向量的全序化,定义6 非负整数向量的赋值序,3向量的全序化,4 密钥与加解密算法,系统参数,4 密钥与加解密算法,构造方法,4 密钥与加解密算法,密

5、钥 本密码体制把密钥分成两部分：秘密传送部分和公开传送部分。秘密传送部分包括包括一个结构无界的唯一可达向量网N=(S,T;F)或者说是一个|T|行|S|列的(1,0,-1)-矩阵，该矩阵满足推论2.1中的两个条件，以及对网N的库所的一组|S|维赋值As=P1,P2,P|S| ，其中素数Pi对应库所si (i=1,2, ,|S|)。公开传送部分为3个整数：As(M0),l1,l2,其中As(M0)为根据|S|元赋值As计算出来 的初始标识M0的赋值 。一般地有0l1l2。,4 密钥与加解密算法,算法1 加密算法 输入： (1)网N的关联矩阵。 (2)|S|维赋值As=P1,P2,P|S|。 (3

6、)初始标识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 密钥与加解密算法,例2 图1给出一个无界Petri网,图1 一个无界的唯一向量网系统,4 密钥与加解密算法,选取k=4,M0=(101000), 则网N的

7、步伐可达标识图 如图1所示。 选取SR(M0)=R(M0)|1,7 求出这16 个标识向量的赋值，并按照赋值大小顺序进行排序可以得到下面的序号/标识对照表,4 密钥与加解密算法,4 密钥与加解密算法,从图2 的部分可达标识图，对每个MI 可以写出对应的可达向量VI。把它们按照对角线序排序，得到可达向量与标号对照表,4 密钥与加解密算法,4 密钥与加解密算法,5算法分析,加密算法复杂性及破解难度分析,5算法分析,分组长度分析 根据密文可以分析出分组长度的取值 密文长度|Y| 应该能被分组长度K整除,0010 0110 1100 1101 0011 1000 1100 1111 00100 110

8、11 00110 10011 10001 1001 111 001001 101100 110100 111000 110011 11 0010011 0110011 0100111 0001100 1111 00100110 11001101 00111000 11001111 0010011011001101 0011100011001111 00100110110011010011100011001111,5算法分析,分组过小在已知明文/密文对的情况下是不安全的 如果K取较大值则计算量比较大,00000000h: D0 CF 11 E0 A1 B1 1A E1 00 00 00 00 00 00 00 00 ; 邢.唷?. 00000010h: 00 00 00 00 00 00 00 00 3E 00 03 00 FE FF 09 00 ; .?. 00000020h: 06 00 00 00 00 00 00 00 00 00 00 00 0C 00 00 00 ; . 00000030h: 65 00 00 00 00 00 00 00 00