分形加密

http://www.paper.edu.cn 基于分形理论的密码算法 刘文涛，孙文生 北京邮电大学电信工程学院，北京(100876) E-mail: liuwentao3213@163.com 摘 要：在概括性介绍分形理论的基础上，对分形理论在密码学的应用进行了研究，提出了 分形密码算法。由于分形图形的不规则性，该算法用于数据加密，使非法用户很难破解，大 大增强了信息的安全性。 关键词：分形理论，密码学，算法。 1．引言 密码技术自古有之。目前，已经从外交和军事领域走向公开，且已发展成为一门结合数 学、计算机科学、电子与通信、微电子等技术的交叉学科，使用密码技术不仅可以保证信息 的机密性，而且可以保证信息的完整性和确定性，防止信息被篡改、伪造和假冒。 密码算法则是密码的核心，在保障信息安全上其重要性是不言而喻的。为此，世界各国 对密码算法的研制都高度重视，1977 年美国NIST提出数据加密 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 (DES)，出于政治原因和 技术原因，多种密码算法在世界各国相继出现，这些算法有：MARS、RC6、IDEA、MMB、 CS-Cipher、SKIPJACK等对称密码算法以及背包公钥算法、RSA、ECC、NTRU等非对称密 码算法[6]。 以上这些算法有些已经遭到了破译；有些安全强度不高；有些强度不明，还有待进一步 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 。本文在介绍分形理论的基础上，对分形图形在密码学的应用进行了深入的研究，提出 一种新的密码算法，重点分析了该算法的实现过程，并对其安全性作出说明。 2. 基于分形理论的密码算法 分形理论的发展可分为三个阶段。 第一阶段是从1827 年到1925 年。在此阶段， 数学家们构造并且研究了种种奇遇或病 态的集合及其图像， 而且试图对这类集合与经典集合的差别进行描述、分类和刻画， 其中 一些后来被认为是典型的分形。 第二阶段大致为1926 年到1975 年。在这半个世纪里， 人们对分形的性质作了深入的 研究， 特别是维数理论的研究已获得了丰富的成果。这一阶段系统、深入的研究深化了第 一阶段的思想， 不仅逐渐形成理论， 而且将研究范围扩大到了数学的许多分支之中。 第三阶段为1976 年至今， 这使分形在各个领域的应用取得全面发展， 并形成独立学 科的阶段， 由于分形几何极强的应用性， 它在物理相变理论、材料的结构与控制、力学中 的断裂、高分子链的聚合、自然图形的模拟、酶的生长等领域取得了令人瞩目的成果。在应 用学科和计算机图形的推动下， 分形的随机理论， 运动系统的吸引子理论与分形的局部结 - 1 - 构等方面也获得了较深入的研究结果。 2.1 一些著名的分形图形 2.1.1 康托尔集（Cantor set） 康托尔于1883 年首先提出来的一种一维空间中的自相似结构，如图1所示，取一直线段 （0，1），把它分为3 等分，然后去掉当中一段，对留下的每一段又三等分并去掉其中间一 段，如此不断地做下去，留下的所有线段就构成了所谓的康托尔集[1]。显然康托尔集构成了 一个无穷层次的自相似结构。 图 1 康托尔集 2.1.2 席尔宾斯基垫片（Sierpinski gasket） 取一个等边三角形，将其分割为 4 个大小相等的等边三角形并挖去其中间的一个，对 剩下的三个又各分为 4 个小的等边三角形并挖去中间的一个，如此分下去，最后所得到的 图案便构成一个无穷层次的自相似结构，如图 2 所示，称为席尔宾斯基垫片[1]或箭头图案。 2.1.3 席尔宾斯基地毯（Sierpinski carpet） 将一个正方形等分为 9 个小正方形并挖去中间的一个，如图 3 所示，把剩下的八个再 依次这么处理，如此做下去，最后得到一个无穷层次的自相似结构，称为席尔宾斯基地毯[1]。 图 2 席尔宾斯基垫片 图 3 席尔宾斯基地毯 2.1.4 大自然中的分形图 大自然中很多图形也具有奇特的自相似结构，图 4 为植物的叶子，图 5 为雪花。 - 2 - http://www.paper.edu.cn 图 4 植物的叶 图 5 雪花 2.2 分形维数 分形维数[2]是描述分形的重要参数，能够反映分形的基本特征，但由于侧重面不同，有 多种定义和计算方法。常见的有相似维数、豪斯道夫维数、容量维数、计盒维数等，它们有 各自不同的应用。以下介绍几种常见的定义。 2.2.1 相似维数Ds 一般来说， 如果某图形是由把原图缩小为 1 / r的相似的 N 个图形组成， 则有关系式 ， 成立， 其中指数 D 称为相似维数，D 可以是整数，也可以 是分数。相似维数通常被定义为具有严格自相似性的维数。 NrD = rNDs log/log= 2.2.2 容量维数Dc 容量维数是利用相同大小形状的小球或立方体包覆几何对象而定义的维数，由著名苏联 数学家科尔莫哥诺夫提出的。设一几何对象 S， 若用直径为ε的小球为标准去覆盖 S，所需 的小球的最小数量为 N (ε) ， 则 S 的容量维数为： )/1log( )(loglim 0 ε ε ε NDc → = 2.2.3 豪斯道夫(Hausdorff)维数DH 设一个整体S 划分为N 个大小和形态完全相同的小图形，每一个小图形的线度是原图 形的r倍， 则豪斯道夫维数为： /r)log(1 logN(r)D lim 0r H → = 豪斯道夫维数和容量维数都是基于包覆的，其不同点在于容量维数是用相同大小形状的 球或立方体去作包覆定义维数， 而豪斯道夫维数是用最有效的包覆来定义的维数。 - 3 - http://www.paper.edu.cn 2.2.4 信息维数Di 将空间作等分分割，然后根据进入这些子空间中点的概率来定义的维数，称为信息维数。 若考虑在豪斯道夫维数中每个覆盖S中所含分形集元素的多少，并设Pi 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示分形集的元素属 于覆盖S中的概率，则信息维数为： logε logpp D N 1i ii 0ε i lim ∑ − → = 在等概率的情况下， 信息维数等于豪斯道夫维数。 2.2.5 计盒维数Db 将用边长为1 /2n 的封闭正方盒子覆盖S， 若S 中包含的小方盒数量M( n) ，则计盒维 数为： 2nlog logM(n)D lim 0n b → = 除上述定义的几种分形维数外，还有谱维数、模糊维数、拓扑维数、广义维数、微分维 数、分配维数、质量维数、填充维数。 2.3 分形加密算法 分形理论是非线性科学研究中十分活跃的一个分支，它的研究对象是自然界和非线性系 统中出现的不光滑和不规则的几何形体。正是由于它的非线形，在密码学中就有了很好的用 处，正如我们所熟悉的des加密需要8个s盒来完成加密的非线形一样。现拿席尔宾斯基垫片 模型作为例子，对于其相似维数，r=2，N=3，Ds=log3/2，可见其维数已经不是我们常见的 整数。 席尔宾斯基垫片模型开始状态为一个三角形，第一步后有3个与开始状态相似的三角形， 第二步后有9个。。。第n-1步后有3的n-1次方。每个三角形有3条边，则一共有3的n次方个边。 那么我们定义n为分形的形成维数。 我们定义密钥的第1位为选择的模型，第2，3，4位为分形的维数，其余位数作为控制三 角形旋转的控制位。将其余位数化为二进制，0代表旋转1次，1代表旋转2次。 图 6 席尔宾斯基垫片模型 - 4 - http://www.paper.edu.cn 假设加密密钥为0x10034567，要加密的明文为0x12345678，那么密钥第一位为1，假设1 代表我们的模型是三角形。第2，3，4位为003，即维数为3，则用于加密的分形图形为图6 所示。 密钥后四位的二进制为0100 0101 0110 0111，密钥控制图形成过程为：将密钥二进制的 每一位按照从上到下从左到右的顺序放在顶角朝上的小三角形中，例如将图-6按照每个小三 角形的高的长度作为一个等级从上到下分为5级，第0级到第1级之间有一个顶角朝上的小三 角形，得到的值为0，第1级到第2级之间有两个三角形，由于在同一级则按照从左到右的顺 序，得到的值为10，第2级到第3级之间有两个顶角朝上的三角形，得到的值为00，第3级到 第4级之间有4个顶角朝上的三角形，得到的值为1010。形成的控制图如图7所示。 明文的二进制为0001 0010 0011 0100 0101 0110 0111 1000，它在席尔宾斯基垫片模型中 所处位置为图8所示，形成过程为：将明文二进制的每一位按照从上到下从左到右的顺序放 在顶角朝上的小三角形的三条边上。依然按照以上的规则将图6分为5级， 第0级和第1级之 间有两条边，得到的值为00，第1级上有一条边得到的值为0，第1级到第2级之间有4条边， 得到的值为1001，依此类推。以下从上到下从左到右的规则都与此相同，故不再详细说明。 图7 密钥控制图 图8 明文显示图 则明文经过密钥控制后在席尔宾斯基垫片模型中的位置如图9所示，控制规则为：在图7 中如果三角形中二进制数为0的则将该三角形顺时针旋转1次，如果为1则将该三角形顺时针 旋转2次。 图9 密文显示图 图10 密钥控制图 由上可知，每次加密能够加密的位数为维数的三次方（如果模型为1的话），明文中的位 数有可能不是其整数倍，则继续加密规则。继续加密时，密钥循环使用，如上次用到密钥的 前9位0100 0101 0，接下来使用密钥的后7位110 0111，和前2位01，依此循环使用密钥，则 - 5 - http://www.paper.edu.cn 密钥控制图如图10所示。 剩下明文在席尔宾斯基垫片模型中所处位置为图11所示，明文经过密钥控制后在席尔宾 斯基垫片模型中的位置如图12所示。 图 11 明文显示图 图 12 密文显示图 加密完成，密文按照从上到下从左到右的规则取出，得到的密文为，0000 0001 1100 1100 0010 1110 0110 1100即0x01cc2d6c。 解密的时候 0 代表三角形旋转 2 次，1 代表 1 次，因为三角形旋转三次就还原了，如果 是其他图形则作相应的改变。 3．安全性分析 该加密方法的安全性在于： 1）第1位选择图形，如果错误则无法解出。 2）第2、3、4位为维数，过多过少的维数都会解出错误。 3）旋转的次数是根据密钥变化改变而改变，很随机。 4）未用到任何数学算法，因此根据数学公式无法作为破解的工具。 5）由于很好的非线形以及无规则性，很好的保护加密明文。 6）只有穷举法才有机会攻击，而穷举法对所有的加密方法都有效。 4．结束语 本文成功的运用分形图形对数据进行加密，将分形运用到密码学中，得出一种新的加密 算法。详细的分析了该算法的实现过程，对信息安全分析提供了一个新的思路。不足之处在 于对算法的时间空间复杂度未作出过多的分析，有待进一步的研究。 参考文献 [1]王启文。分形理论。铜仁师范高等专科学校学报。2006 年 9 月第 8 卷第 5 期。 [2]刘莹，胡敏，余桂英等。江西科学。2006 年 4 月第 24 卷第 2 期。 [3]王美荣，金志琳。分形理论及其应用。荷泽师范专科学校学报。2004 年 11 月第 26 卷第 4 期。 [4]戴美凤。“分形理论初步”的教学切入点。镇江高等学报。2006 年 7 月第 19 卷第 3 期。 [5]孙洪军，赵丽红。分形理论的产生及其应用。辽宁工学院学报。2005 年 4 月第 25 卷第 2 期。 [6]秦志光。密码算法的现状和发展研究。中国科技 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 在线计算机应用。2004 年 2 月第 24 卷第 2 期。 - 6 - http://www.paper.edu.cn Cryptographic Algorithm Based on Fractal Theory Liu Wentao, Sun Wensheng School of Telecommunications Engineering, Beijing University of Posts and Telecommunications, BeiJing(100876) Abstract This paper introduces the basic fractal theory, and gives a cryptographic algorithm through researching the application of fractal theory on cryptography. It is very difficult to crack by unauthorized users because of irregular fractal graphics when the algorithm is used to encrypt, greatly enhancing the security of the information. Keywords: fractal theory, cryptography, algorithm - 7 - http://www.paper.edu.cn 基于分形理论的密码算法 1．引言 2. 基于分形理论的密码算法 2.1 一些著名的分形图形 2.1.1 康托尔集（Cantor set） 2.1.2 席尔宾斯基垫片（Sierpinski gasket） 2.1.3 席尔宾斯基地毯（Sierpinski carpet） 2.1.4 大自然中的分形图 2.2 分形维数 2.2.1 相似维数Ds 2.2.2 容量维数Dc 2.2.3 豪斯道夫(Hausdorff)维数DH 2.2.4 信息维数Di 2.2.5 计盒维数Db 2.3 分形加密算法 3．安全性分析 4．结束语 参考文献