细胞自动机演示文稿——密码学.ppt

细胞自动机在密码学中的应用 0引言 当前IT行业高速发展 我国网民的数量已达到四亿多 电脑进入了千家万户 随之产生的信息安全问题愈演愈烈 数据在网络上的传输过程中极易被窃取 而产生用于信息被盗事件 损害广大网民的切身利益 在商业界 国家之间则更是如此 关系到巨大的民族利益和国家安全 目前各国都在寻求适合本国的自主密码体制 美国 英国等西方国家的安全机构每年都投人大量的财力研究自主密码体制 以保证国家和社会的信息安全 中国政府也已经意识到信息安全的重要性 规定商用密码产品 特别是涉及国家安全与社会稳定的密码产品 必须依靠自主研究 使用具有自主知识产权的密码体制 因此 十分有必要开展信息安全加密方面的研究 1可逆细胞自动机原理 1 1细胞自动机基本概念细胞自动机是空间 时间和状态都离散的动力系统 细胞自动机在空间上是由一维 二维或三维的规则结构组成 每个细胞根据局部的 相同的规则进行同步更新 细胞自身的状态由其本身和其邻居的状态共同决定 常见细胞自动机模型 1 2可逆细胞自动机 可逆细胞自动机 RCA 是这样一类细胞自动机 它的全局函数F决定的每一次状态转移是一一映射的 也就是具有这样的性质 对某一个初始配置 一个细胞自动机A采用规则作用若干次后 能找到另一个细胞自动机B 对A作用后的结果作用同样多次后 能够回退到初始配置 A和B也就是一对可逆细胞自动机 规则240和170在循环边界条件下是一对可逆CA 于是给定数串0110010100011001 先用规则240对其进行五个时步的演变 然后再用规则170对演变后的状态进行五次作用比较 最终的状态为0110010100011001 也就是又回到了最初时的配置 而且每一步都是相对于规则240的反演变 具体过程由如下图表所示 图3用规则240对初始设置进行5次迭代 图4用规则170对初始设置进行5次迭代 2公钥密码模型 2 1公钥构造用四个一维4状态1 2半径的可逆细胞自动机作为私钥 将这几个一维可逆细胞自动机通过某种运算 产生一个二维Moore型邻居不可逆细胞自动机 这个二维细胞自动机就是公钥 可以使用这个二维细胞自动机来加密 而使用构造这个二维细胞自动机的4个一维细胞自动机的逆细胞自动机即私钥来解密 具体公式如下 公钥 CAM CA1 CA2 CA3 CA4私钥 CA1 CA2 CA3 CA4加密 F P CAM C解密 G C CA4 CA3 CA2 CA1 P 这里F和G分别为加解密函数 P代表明文 C为密文 CA4 CA3 CA2 CA1 分别为CA1 CA2 CA3 CA4 的可逆细胞自动机 对一个3 3的细胞空间局部 并非所有单元 依次自上而下使用CA1 自左至右使用CA2 自上而下使用CA3 自右至左使用CA4 进而得到一个二维Moore型邻居的细胞自动机状态转移表 并把它作为公钥加密 解密时则使用相反的顺序用各自的一维可逆细胞自动机即私钥分别对密文作用如表3 A1 A2 A3 A4 图5加密过程图 表3各私钥转换表 2 2加密和解密过程 图6加密流程图 2 2 1加密 2 2 2解密 图7解密流程图 3仿真实验 举例说明该加密算法模型 以简单的规则半径r l 4状态S 0 1 2 3 的4个一维可逆细胞自动机CA1 CA2 CA3 CA4 为私钥 由它们构造出的二维Moore型不可逆细胞自动机A为公钥 对明文分组232101320313203201223222331020 分组后利用上一节中构造的加密模型流程对数据进行加密和解密 结果和过程如下表2 表3 表2密文结果 表3密文逐步解密过程 4结束语 本文研究了基于细胞自动机的公钥密码体制 该加密模型以n个一维可逆细胞自动机为私钥 由它们构造出的二维不可逆的Moore型细胞自动机为公钥对数据进行加密 该算法实现简单 由于细胞自动机是时间 空间和状态均离散的动力学系统 其