（计算机软件与理论专业论文）快速有限阶burrowswheeler变换的加密方案设计与应用.pdf

中山大学硕士论文 快速有限阶b 1 l r m w s 踟1 0 e l e r 变换的加密方案设计及应用 1 1 论文背景 1 1 1 密码学背景 第1 章概述 随着人类进入信息化社会，传统的商务活动，事务处理以及政府服务等已经 越来越多的通过计算机和互联网。人们在享受“技术共享 、“信息共享”的同时， 也备受不安全的带来的隐患。网络信息的被泄露、篡改和假冒、交易抵赖、黑客 入侵、计算机犯罪、计算机病毒肆虐等，对网络信息构成严重威胁。如果信息安 全不能解决，信息社会就无法健康有序地发展。信息安全已成为人们在信息空间 中生存和发展的重要保证条件。 密码学【l 】是保证信息安全的重要手段。密码学的研究和应用已有几千年的历 史，但作为一门科学是2 0 世纪4 0 年代才开始的。目前密码学已经从外交，军事 领域走向商业领域，且发展成为一门集数学、计算机科学、电子与通信等技术于 一身的交叉学科。使用密码学技术不仅可以保证消息的秘密性，而且可以保证消 息的完整性和确定性，防止信息被篡改、伪装、假冒和抵赖。 密码学可分为以下两个领域，一为密码编码学，是指如何达到信息的秘密性； 另一种是密码分析学，是指如何破解密码系统。两者相互对立又相互统一，通过 密码分析手段来检测密码体制的安全强度，不断为信息提供更为安全的保障。随 着科技的发展，破解手段的推陈出新，计算机处理能力的加强，利用计算机的高 运算能力和新的攻击手段来分析攻击密码系统的成功率越来越大。如在1 9 7 7 年 被美国国家标准技术协会认可成为均衡加密算法的标准，d e s ( 数据加密标准) 【2 】 由于密钥长度较短，在2 0 世纪9 0 年代不断有学者尝试采用计算机进行强力搜索 密钥破解，已经有多次被破解的记录。事实上对于安全性要求较高的用户更愿意 采用加强型d e s ，又称3 d e s 进行加密。随着网络、手机、掌上电脑的发展， 这些小型设备需要的是，更少的代码，占用更少资源的加密算法。于是速度更快， 密钥长度可变，更高的对称分块密码体制a e s 【3 】作为d e s 的替代者成为了新的 数据加密标准。现在，a e s 只要使用1 2 8 位的密钥长度就能够提供足够的安全 中山大学硕士论文快速有限阶b 明舢s 、枷。d c r 变换的加密方案设计及应用 由于加密和压缩并未很好的融合，采用截然不同的算法，此种加密压缩体制无论 在实际性能方面还是在应用的广度方面都显不足。 基于b 、t 的压缩算法【4 】因其应用的广度和卓越的性能获得了广泛的应用。 我们在本文中探索b 、t 在加密领域的应用，已使用户在使用b 、t 来提高信息 有效存储的同时，又能确保信息安全，且与其它加密压缩策略相比，能够继续保 持b w t 带来的高压缩率，高时空效率和较高的应用范围。 在有限阶b w t ，即s t 逆变换过程中，我们需要知道源文本末尾字符信息 和结果文本，才能采用“由末尾字符为起点，不断寻找其前继 的方法来还原 整个源文本。利用这个性质使之应用于加密。根据密钥的每个字符，进行多次 s t 变换。对密钥中当前字符，添加到原文末尾，便进行一次s t 变换，然后仅仅 输出结果文本。原文的末尾信息( 也是密钥) 由秘密信道传输给接收方。如此， 攻击者因为无法得到原文尾字符信息而无法进行s t 逆变换还原，这是我们加密 方法的思路。接着，我们继续分析s t 一阶变换的性质，着重分析变换后的密文 结构和原文结构之间的关系，以及原文信息的打乱混淆特性，利用这些性质，最 终确立了一种较为合理的对称加密模型，避免了攻击者采用明文攻击和选择明文 攻击等。 本文主要工作是分析有限阶b 、t 一阶变换的性质，着重分析了b w t 变换 前后，原文结构的转换关系和混淆特性。利用这些性质，设计出一种与之对应的 加密模型，并探讨了加密前后原文信息是否进行了很好的混淆，从三个角度分析 了其安全性。本文还对该加密体制进行了算法优化，和用加密块链模式进行了代 码实现，为传输数据进行加密解密，以确保信息的机密性。 1 3 论文组织结构 论文的后续章节安排如下： 第2 章主要介绍了密码学相关理论。对称加密技术和非对称加密技术，以 及它们的异同。本文的加密体制是对称加密体制。 第3 章主要集中介绍了本文加密体制的算法核心正向和逆向b w t ，以及它 的变种，正向和逆向s t 。 3 中山大学硕士论文快速有限阶b l i n d w s - w h 耐凹变换的加密方案设计及应用 图2 1 典型密码系统 在发送方，首先将明文竹用加密器e 及加密密钥墨加密成密文c ， c = 瓦( 肘) 。接着将c 通过公开信道传送给接收方。在接收方处，通过解密器， 以及解密密钥如将传送过来的密文信息c ，解密还原为膨，膨= q ：( c ) 。 自从1 9 7 6 年d i m e 与h e l l m 肌两人共同提出了公开密钥概念以来，公开密 钥体制得到了迅速蓬勃发展，而且几乎成为现代密码学理论的研究主流。但是公 钥加密密码系统由于计算复杂，运算量高，使得在实际的应用中面临速度问题。 因此部分专家学者仍然致力于传统密码学理论研究，其研究主流是对称加密技 术。目前，获得广泛研究和现实应用的两种加密技术是对称密钥加密技术和非对 称密钥加密技术。 2 2 对称密钥加密技术 2 2 1 对称加密体制简介 对称加密技术，又称私钥加密，是采用同一个密钥进行数据加密和解密的。 在对称加密体制下，密钥就需要经过安全的密钥信道由发送方传给接收方。 对称加密体制的特点是无论加密还是解密都使用同一个密钥，这种加密技术 6 中山大学硕士论文快速有限阶b u n d 、s w h e c l c r 变换的加密方案设计及应用 2 3 非对称密钥加密技术 2 3 1 非对称加密体制简介 非对称加密体制，又称公钥加密。此加密体制加密和解密所使用的不是同一 个密钥，通常有两个密钥，称为“公钥 和“私钥 ，他们两个必须配对使用。 公钥加密的信息可以用私钥解开，私钥加密的信息也可以用公钥解开。 非对称密码体制将“公钥”对外公布，“私钥 则持有人自己保存。如此， 发送方用接收方的公钥进行加密，接收方用自己的私钥解密即可以，不需要建立 安全信道来传送密钥，这样很好的解决了密钥的传输安全问题。由于密钥为自己 保存，也不存在密钥管理的问题，简化了密钥的分发，降低了分发传送密钥的安 全风险。公钥加密的另一个优点是可以拥有数字签名等新功能。 中山大学硕士论文快速有限阶b l m o w s - 、枷i e r 变换的加密方案设计及应用 3 ) 椭圆曲线离散对数系统( e c c ) 1 9 8 5 年和1 9 8 7 年k 0 b l i t z 和m i l l c r 各自独立提出使用椭圆曲线作为公钥密 码体制的基础，并用有限域上的椭圆曲线实现了已存在的公钥密密码算法。由于 椭圆曲线上的离散对数计算要比有限域上的离散对数的计算更困难，而且它与 r s a 方法相比，安全性能更高，计算量小，处理速度快，宽带要求低。e c c 拥 有这些特点，有望能够取代r s a ，成为通用的公钥加密算法，因此广泛受到国 际的关注。 2 4 对称加密体制和非对称加密体制的比较 加密技术是保障信息安全而采取的主要安全措施。一方面对数据进行加密和 解密来保障信息的秘密性，保证用户的明文信息不被非法用户窃取；另一方面使 用加密技术来实施数字签名，进行身份认证，对信息进行完整性校验，保证信息 的真实、完整和防抵赖。 对称加密体制在加密和解密时采取同样的密钥，密钥由信息发送者和接收者 分别保存。随着用户的增加，密钥的需求量成倍增加，密钥的管理和分发安全得 不到保障。非对称加密体制可以抽象为陷门单向函数，由于计算复杂，运算量高， 其加密速度相比对称加密较慢。两种体制各有优缺点，两者的主要特性相比较见 表2 1 。 表2 1 对称加密体制和非对称加密体制的比较 特性对称加密非对称加密 密钥的数目单一密钥成对密钥 密钥的种类密钥是秘密的一个私有，一个公开 密钥管理 简单不容易管理需要数字证书和可靠第三者 相对速度 非常快 慢 用途用作大量资料的加密用作加密小文件和信息签名等 不太严格的保密应用 对称加密具有加密速度快效率高的特点，特别适用于不需要移动的数据。然 而，由于安全地发布密钥非常困难，单独使用传统加密方法来安全传输数据的代 中山大学硕士论文快速有限阶b u n _ o w s 、h i 竹变换的加密方案设计及应用 价是非常昂贵的。而非对称加密比较容易实现数字签名，密钥管理等功能，更不 需要进行密钥的传输或共享。在现实的电子商务中通常是结合非对称加密和对称 加密的各自优点，采取一种混合加密策略。在实际应用中使用公开密钥技术在通 信双方传送对称密钥，而采用对称加密技术来对实际传输的数据进行加解密。具 体可参考数字信封，安全套接层协议s s l f l 9 j 等。 1 2 中山大学硕士论文快速有限阶b u n _ o w s 、h i 竹变换的加密方案设计及应用 价是非常昂贵的。而非对称加密比较容易实现数字签名，密钥管理等功能，更不 需要进行密钥的传输或共享。在现实的电子商务中通常是结合非对称加密和对称 加密的各自优点，采取一种混合加密策略。在实际应用中使用公开密钥技术在通 信双方传送对称密钥，而采用对称加密技术来对实际传输的数据进行加解密。具 体可参考数字信封，安全套接层协议s s l f l 9 j 等。 1 2 中山大学硕士论文快速有限阶b u r 町粥w h l 盯变换的加密方案设计及应用 第3 章b w t 、s t 介绍 本章节重点介绍b 眦r o w s w h e e l e r 变换【4 1 的原理和步骤，以及s t 的提出，和 s t 的正向变换和逆变换。本文加密体制的核心正是基于s t 一阶变换。 3 1 符号及名词介绍 本小节列出在本文中将要用到的符号及一些名词的定义： s ：长度为刀的源文本，为由字符组成的一维行向量。s = 【五，屯，毛- ，$ 】，其中$ 代表大于或小于任何源文本字符的文本结束符。 膨：由源文本经过轮转后得到的以行字符矩阵。下一节中详细定义。 m ：将膨的所有行按照自定义顺序排序后得到的刀以矩阵。 膨：将膨的所有行根据前k 列按照自定义顺序排序后得到的刀，l 矩阵。 f ：一维万元行向量，为肘的第一列的转置。 最：一维以元行向量，为以的第一列的转置。 ：一维刀元行向量，为m 的最后一列的转置。 厶：一维n 元行向量，为磁的最后一列的转置。 伽蛾：源文本s 在m 或以中的行号。 p ：将中的每个元素映射到其在f 中的位置的一个行向量。 前继：s 中字符而一为字符薯的前继，字符$ 为字符而的前继( 循环定义) 。 后继：s 中字符而为字符五一。的后继，字符五为字符$ 的后继( 循环定义) 。 后阶上下文：s 中一个字符的后后个字符称作这个字符的尼阶上下文( 循环定义) 。 当| = 玎一l 时，也称为无限阶上下文，m 中的每一行的前，l 一1 个字符都是这行最 后一个字符的无限阶上下文。 前继列：4 列中的每一个字符都是b 列对应位置上的字符在源文本中的前继，则 彳列是口列的前继列。 1 3 中山大学硕士论文快速有限阶b 1 姗s w h o e l c r 变换的加密方案设计及应用 m ： m = 对m 所有行按字典次序进行无限阶排序( 其中$ 大于其他所有字符) 得到 膨= 我们得到矩阵m 的第一列的转置为f = i 口口6 66cc $ l ，最后一 列的转置为三= 【cc $6口66 口】，原文在膨中的伽蚝= 3 。所以s 的 b w t 变换的输出为伍，f 耐缸s ) = c $ 6 口66 口1 3 ) 。 分析b 、t ，我们有以下一些性质： 1 ) b w t 变换对原文信息进行了重排列，使得相同字符排列在一起概率和 原文相比得到了很大的提高。 这是由b w t 变换中的排序机制所决定的【2 0 1 。b w t 变换中的矩阵排序，使 得f 中相同字符排列在一起，而输出列三是f 的前继列。所以可以看成是对最后 一列的字符按照它们的无限阶上下文进行排序，这样的排序会将源文本中所有位 于相同字符串前的字符排列在一起。以英文中经常出现的单词m e 为例，当所有 的循环位移行排好序后，所有以h e 开头的行肯定都会排列在一起，而这些行很 大概率上都会以t 结尾，包括m e ，t l l e y 等。这样，三中的某个字段内就会高概 率的出现t ，中间夹杂一些英文中同样后带h e 的字母，例如s 。这样的性质对 $ 6 6 c 口6 c 口 口$ 6 6 c 口6 c c 口$ 6 6 c 口6 6 c 口$ 6 6 c 口 口6 c 4 $ 6 6 c c 口6 c 口$ 6 6 6 c 口6 c 口$ 6 6 6 c 口6 c 口$ c c $ 6 口6 6 口 6 6 口$ c 6 口c 6口c口6$c 6 电中 c 6 c 6 口6 口 口6口6$c 6 cc易c口口6$6 6 $ 6 c c 口口6 口口6 6 6 c c $ 中山大学硕士论文快速有限阶b u n _ o 、帱、枷l e r 变换的加密方案设计及应用 于所有单词都同样适用。因此b w t 变换能够提高源文本中相同字符排列在一起 的概率。 2 ) 矩阵m 的每一列的组成内容都相同，都是源文本的不同排列。其中第一 列的排序权重最大，所以，可以通过对进行排序得到。而且是f 的前继列， 即中每一个字符都是f 中对应位置字符在源文本中的前继。 在b w t 逆变换中，我们已知，原文在m 中行号，即是知道源文本最后 一个字符是什么。因此可以通过用找前继的方法，以源文本最后一个字符为起点， 来推出整个源文本。 其中涉及到当存在多个相同字符，如何选择正确前继的问题。当元素的前继 在，中有多个时，我们如何定位它在，中的正确位置，还原正确的前继。实际 上，b w t 排序机制决定了相同字符的相对顺序在f 列中和列中是一致的，这 是b w t 变换的固有属性。这在李舒雯的毕业论文快速有限阶b u n o w s w h e e l e r 变换的算法设计及应用中给予了一般化的证呀2 1 1 。 如上，有了b w t 这个固有属性，我们能够构造行向量尸，用以定位中任 意字符在f 中的正确位置，找到正确的前继。 b w t 逆变换具体步骤如下： 1 ) 通过对排序得到f 。 2 ) 遍历和f 构造个行向量p ，p 记录了三中的每个元素在f 中的下 标，且保持了相同字符之间的的相对次序不变，以便在源文本的恢复过程中，能 对当前已恢复的字符查找它的前继。 3 ) 从源文本的最后一个字符开始，对源文本进行恢复，源文本的最后一个 字符可以直接从三的第觑缸。位获得，然后通过向量p 得到这个字符在，中的位 置，那么三的对应位置上的字符便是这个字符在源文本中的前继了，这样就恢复 了倒数第二个字符，再通过将倒数第二个字符映射到f 中的正确位置，找其前继 来找倒数第三个字符，直到恢复出整个源文本。 以上面的例子仁，加缸s ) = 他c $ 6 口66 口1 3 ) 的输出为例，我们得 1 6 中山大学硕士论文 快速有限阶b 阴瓣w h l 留变换的加密方案设计及应用 知原文的尾字符为$ ，且行向量p 为【5 ，6 ，7 ，2 ，o ，3 ，4 ，l 】。对进行排序得到f ，容 易得到如下矩阵( 这里仅用到f 和的对应) ，其中f 为，的转置，z 为三的转 置。 f = z 图3 1 从尾字符找前继还原图 则从尾字符$ 找其前继来还原的顺序图为图3 1 。 b w t 逆变换的算法【钥如算法3 1 。 算法3 1b w t 逆变换 1 7 中山人学硕上论文快速有限阶b u 肿、】i ，s w h 。d 盯变换的加密方案设计及应用 3 2 2 踟t 变换及逆变换时空复杂度分析 对b w t 逆变换的算法进行分析可知，b w t 逆变换只需d ( ) 的时空复杂度。 然而b w t 正向变换中，由于进行无限阶上下文排序，从而造成了算法较高的时 间复杂度。如果采用通用排序方法例如快速排序，会达到最坏情况下 d 【2l o g ( ) ) 的时间复杂度，b w t 的较高的时间复杂度将很大程度上影响b w t 在各个领域应用的性能。 这一问题引发很多专家学者从不同方面来降低b w t 变换中的排序复杂度的 研究【l o 1 6 1 。其中最为成就的是s d 曲d l c r 在【1 0 ，1 4 】中提出了一种不同与以前所有 研究的方法，简称为s t ( s o r tt r a n s f o n l l ) 。它提出了有限阶上下文的概念，将 b w t 中的无限阶上下文排序操作改成了只对有限阶上下文排序，从根本上减少 了b 、t 的排序工作量来降低时空消耗。本文正是基于s t 变换基础上的一个加 密应用，下一节我们将详细介绍s t 变换。 3 3s t 变换及其逆变换介绍 3 3 1s t 变换原理介绍 s t 【1 0 ，1 4 】是b 、t 众多变种中较优的一个。它采用对源文本轮转矩阵m 进行 有限阶上下文( 后阶) ，即只对膨按照其前庀列进行排序，以此来减少b w t 中大 规模的排序操作造成的高时间复杂度。其中第一列排序权重最大，第二列其次， 第尼列最弱，当存在两行的七阶上下文相同时，它们的排列顺序由它们在m 中的 相对顺序决定。 读者可能要问，当s t 采用有限阶上下文排序后，会不会对b w t 变换后带 来的高压缩率带来影响呢? 文献 1 4 】中，作者分别采用4 阶的s t 和b w t ，再加 上相同的后续压缩处理算法处理，在标准压缩数据集c a l g 哪上进行了实验，结 果表明二者的压缩率是非常接近的。也有其它的实验表明当s t 的阶数增加过了 一定数值后，将不能再显著地增加压缩率。 s t 进行了七阶上下文排序后，我们仍然以磁的最后一列的转置厶和觑峨 作为输出。对3 2 1 小节中的例子s ：陆6 c 口6c 口$ 】进行2 阶s t 变换， l s 中山大学硕士论文快速有限阶b u r r o w s - w h 鲥盱变换的加密方案设计及应用 实时磁盘解压和由硬件实现解压【2 2 均应用中表现得尤为严重。 在文献【2 3 】中，n o n g 和z l l 锄g 提出了一种新的s t 逆变换方法，采用和 b w t 逆变换相同的矩阵方法来还原出整个源文本。在文中，作者提出了在多个 相同上下文的情况下，找其正确前继的方法，并且只需要采用数组便能进行源文 本还原，而不需基于哈希表。 新的s t 逆变换方法在源文本还原部分取得突破。在源文本还原部分采用了 和无限阶b 、7 l ，t 逆变换类似的矩阵方法，即从源文本的最后一个字符开始，以找 其前继的方法，对源文本进行恢复。源文本的最后一个字符可以直接从丘的第 切慨位获得，然后找以这个字符开头的k 阶上下文在膨：中行数，那么厶的对 应位置上的字符便是这个字符在源文本中的前继。 这里涉及到多个相同七阶上下文，如何取前继的问题。n o n g 和z l l a n g 给我 们提供的方法是：最列中，排除了e 对应在厶中的值为尾字符的那行，其余行 越靠后的位的起始字符越早被还原。这在文献【2 3 】中已给予了证明。 我们认为，s t 可以看作是b w i 的一般化。s t 对轮换矩阵进行后阶排序， b w t 是对轮换矩阵的无限阶排序。当有限阶七= n 时候，s t 就是b 岍。这里引 入“聚集”的概念，通过七阶s t 变换后，在疋中具有相同的后阶上下文被集中 到一起，成为一个“聚集”。b w t 采用无限阶排序，不存在两个相同的刀阶上下 文，即矩阵m 拥有，1 个聚集。 我们总结给出无限阶逆b w t 和有限阶逆b w t 的通用找前继的方法为：首 先选择正确的聚集，然后在聚集中，排除了厶中字符为尾字符的那行，选择越 靠后的行越先被还原。在选择正确的前继时，相同字符开始的聚集之间的相对顺 序和厶中保持不变1 8 】，因此可以分别构造数组丁和c 用来保存不同聚集的索引 和聚集内相同上下文的个数。当每次还原聚集中的一个上下文后，聚集的数量应 该减1 。 我们以如上的s t 二阶变换为例，得到的输出为 弛：，加缸s ) = c $ 6 口66 口1 3 ) 。我们先进行2 阶的上下文还原，并 把具有相同二阶上下文的行看成一个“聚集”，那么只被分割成多个七阶上下文 中山大学硕士论文 快速有限阶b u n d w s w h 。d c r 变换的加密方案设计及应用 不同的聚集。如图3 2 中的虚线表示： 必= 磊：蠢：j 运：警：j 蒗若一： f 图3 - 2 聚集分类圈 在蟛中根据二阶上下文的不同被分成6 个聚集。在e 中，以同一个字符开 头的聚集之间的相对顺序和厶和保持一致的，即同一个聚集中的开头字符在厶 中相对集中。如上图的以b 开始的聚集在互中和厶中是保持一致的。 在进行源文本还原时，我们从原文尾字符出发，找到其对应在厶中的前继 来还原。找到其前继后，我们首先定位其到最中相对应的“聚集”，在“聚集 内部，有多个相同的| | 阶上下文，我们选择排除了互对应在厶中的值为尾字符 的那行，越靠后的行越早被还原。 如此，还原出整个源文本s = 6 ，6 ，c ，口，6 ，c ，口，$ 】。 新的j j 阶s t 逆变换算法如3 2 。 2 l c c $ 6 口6 6 口 一“；w；一w露臻糍 中山大学硕二i 二论文快速有限阶b u r r o w s w h e c l 凹变换的加密方案设计及应用 3 3 2s t 变换及逆变换的时空复杂度分析 s t 变换引入有限阶的概念，对轮转矩阵m 采用其后阶上下文进行排序来代 替无限阶排序，从根本上降低了b w t 正向排序的时空消耗。而这种后阶上下文 排序可以通过基数排序法来实现【2 1 1 ，将时间复杂度降低到d ( 埘) 。n o n g 和z h a n g 在文献 2 4 】中继续对逆s t 变换的时间复杂度进行优化。目前逆s t 变换的时间 复杂度仅为d ( 1 0 9 ：( 尼) ) ，空间复杂度保持为d ( ) 。 对于新的逆s t 算法f 2 4 】分析可得知，源文本还原过程的时空复杂度仅为 d ( ) ，与无限阶b w t 逆变换的时空复杂度相同。但是前面的七阶上下文还原 过程，由于需要迭代七次，每次对，1 个元素进行赋值来构造一个后，z 的矩阵，因 此它的时空复杂度为d f 七) 。逆s t 变换包括上下文还原和源文本还原两个部分， 两个部分是串行的，所以整个逆s t 变换算法的时空复杂度会达到d ( 克叭。 中山大学硕士论文快速有限阶b u 玳 w 姗l 鲥盯变换的加密方案设计及应用 4 1 概述 第4 章基于s t 变换的数据加密 有限阶b w t ，又叫s t 变换，其核心在于引入“有限阶”的概念。它采用 对源文本轮转矩阵m 只进行有限阶上下文( 七阶) 进行排序来减少b w t 中大规 模的排序操作，从根本上解决b w t 无限阶正向变换中大规模的排序造成的较高 时空复杂度。但是由于s t 变换采用有限阶上下文进行排序，破坏了无限阶b w t 变换中“相同字符在f 和三中的相对次序保持不变 这个固有属性，使得s t 逆 变换无法简单地像逆向b w t 一样，通过构造向量p 来找到正确前继。在新的s t 逆变换算法【2 3 】中，对源文本还原有了很大突破，找出了如何正确找前继的方法， 那就是除了结束符为$ 的那行外，排在越靠后行的字符应该越早被还原，成 功的将逆向s t 算法的时空复杂度降低到d ( 克) ，这个为b w r 有限阶变换应用 于加密提供效率前提。 s t 对源文本进行了重排列，s t 变换是可逆的，这是我们将s t 应用于加密 领域的前提。在逆s t 变换中，我们需要知道源文本的尾字符在输出串中的位置， 以此得出尾字符，然后用“由末尾字符为起点，不断寻找其前继 的方法还原出 整个源文本。于是，我们考虑将随机产生密钥，将密钥的每一位添加于原文的末 尾，分别进行s t 变换，而输出仅为三的转置，并将密钥通过密钥信道进行传送。 攻击者只有同时拥有密钥和密文才能进行s t 逆变换。如果攻击者只有密文，便 无法获得原文的尾位信息，从而无法进行s t 逆变换。这是我们将s t 应用于加 密领域的思路。 4 2s t 一阶变换介绍及其性质 我们这里采用s t 一阶变换作为加密的算法核心，即在m 中只根据第一列进 行排序，得到膨。那么算法的时空复杂度为d ( ) 。我们知道数据在计算机内 存中都是以o 和1 表示的。考虑原串为o 和1 组成的位流，且假定优先级o ，即末 位不确定。 ( x ，】，) 为( 1 ，1 ) 时，由( x ，】，) 组合我们知，互中第一个1 的直接前继是1 ， 即原串的第一个1 的直接前继是1 ，得出原串的首位为l ，末位为l 。所以 原串特征为 1 ) o ，1 ) 1 ) ，即末位是1 。 ( x ，】，) 为( o ，o ) 时，推导证明同上。 ( x ，】r ) 为( 1 ，o ) 时，原串第一个。的前继为1 且第一个1 的前继为o ，出 现两种情况，一种为当原串的第一位为0 ，则最后一位为1 ，另一种是当原串 的首位为1 ，最后一位为o 。均满足此种组合。 原位串只有o 和1 两个位且曩中相同字符的相对次序和原文s 保持一致， 中山大学硕士论文快速有限阶b u n _ o w s w h e e l c r 变换的加密方案设计及应用 所以( x ，】，) 组合为( 1 ，o ) ，当且仅当原串的首位和尾位不相同，分别为。和1 。 性质4 ：当结果串( x ，】，) 组合为( 1 ，o ) 时，分别存在原串特征为 1 ) o ，1 ) o ) 和 q 0 ，1 ) 1 ) 的两个原文通过s t 一阶变换得到该结果串。我们称这两个原文为“共 轭 原文。 证明：s t 一阶变换是可逆的。存在两种原串特征，主要的问题是原串 尾位是从。还是从l 开始还原的问题。那么，我们只要证明当结果串( x ，】，) 组 合为( 1 ，o ) 时，无论从。还是从1 开始还原，都能够正确地还原出原文的所有 信息，就等于证明了原结论。 因为在墨中，第一个o 对应的前继是1 ，我们不妨假设尾位为o 开始还 原，那么o 和1 都能够走的到，所以全部得到还原。我们再假设尾位为1 开 始还原，因为至少有一个1 是o 的前继，又厶和墨中l 的数量相同，所以至 少有一个o 是l 的前继，所以从l 开始还原也能够将f 中的0 和l 都走通。 因此，结果串( x ，y ) 组合为( 1 ，o ) 时，分别从。和1 还原，我们将能够得 到两个分别不同的原文，即存在两个分别不同的原文通过s t 一阶变换得到 相同的结果。 我们仍然以输出结果厶= 【1 o o1o o1 1 】来论述。我们对之进 行重新排序得到墨，则构造叫如下： 叫= 我们不妨假设攻击者猜测原文末位为o ，那么还原箭头如图4 2 ，由最后 、，、， 工o 0 l 澎o l 1 似o o l 埘o l 1 0 o 0 0 1 1 l 1 中山大学硕士论文 快速有限阶b u m 稍、h a d 盯变换的加密方案设计及应用 一位o 开始还原。 图4 2 尾字符为o 还原图 根据图4 - 2 ， 我们得到特征为 1 ) o ，1 ) o ) 的原文： 【1 o o oll1 o 】。 假设攻击者猜测原文末位为1 时，那么还原的箭头如图4 3 所示。由最 后一位1 开始还原。 图4 3 尾字符为1 还原图 根据图4 - 3 ，我们得到特征为 0 ) 0 ，1 ) 1 ) 的原文：【o oo1ol1 1 】。 由此，我们证明了，当结果串的( x ，y ) 组合为( 1 ，o ) 时候，存在两个特征分别 为 1 ) o ，1 ) + 0 ) 和 o ) 0 ，1 ) 1 ) 的两个“共轭”原文通过s t 一阶变换得到相应结果 串。 中山大学硕士论文快速有限阶b u 咖w s w h i c r 变换的加密方案设计及应用 4 3s t 加密方案模型 s t 加密方案是以一阶s t 变换为核心算法，利用一阶s t 变换的特性，采用 同一密钥进行加密和解密的。它是一种对称加密策略，具有速度快效率高等特点。 s t 加密算法能达到以下四个要求：首先是提供高质量数据保护，复制数据 未经授权的泄漏和未被察觉的修改；其次是具有相当高的复杂性，使得破译的开 销超过可能获得的利益，同时便于理解和掌握；再次，s t 加密算法和所有的对 称加密算法一样，其体制的安全性不依赖于算法的保密，而仅以加密密钥的保密 为基础；最后，实现经济、运行有效，并且适用于多种完全不同的应用。 s t 加密方案主要利用了“解密需要用到原文的尾位信息 这一特点，我们 将密钥信息添加于原文末尾，使得攻击者无法知道原串末尾元素信息而无法逆变 换还原。而且利用了s t 一阶变换的性质3 ，构造原文转换后的( x ，】，) 组合为 ( 1 ，o ) ，使得攻击者无法根据( x ，】，) 组合信息而推出原文的特征，从而无法知道尾 位信息。利用s t 一阶变换的性质4 ，在密文( x ，y ) 组合为( 1 ，o ) 的情况下，攻击 者无论猜测尾位为o 或1 ，都能够还原成功，其中一个是真实的原文，另一个为 实际原文的“共轭 原文。 4 3 1 方案的具体步骤 s t 加密算法的入口参数有三个：k e y ，d a t a ，m o d e 。其中k e y 是s t 算法的 工作密钥，由伪随机数生成器生成，长度可以由用户自行选择和更改，特别是当 用户认为安全性不够高时，可以方便的增加密钥长度，提高其抗穷举攻击能力。 m o d e 是s t 算法的工作方式，具有加密和解密两种。d a t a 是位串输入块，长度 可以由用户自行定义，一般为8 个字节6 4 位。其经过s t 算法后输出长度和原 d a t a 相同，并无信息的冗余。 1 ) 如果m o d e 为加密 循环利用k b y 的每位，s t 算法对d a t a 进行加密，大概可分成三步： 第一步：s t 一阶加密原串的构造 当k e y 当前位为0 时，我们在明文d a t a 0 前加位1 ，在明文末位加位 0 ；当k b y 当前位为1 时，我们在明文前加位o ，末位后加位1 。如此变 中山大学硕士论文快速有限阶b u n u w s - w h a d e r 变换的加密方案设计及应用 成( 原文长度+ 2 ) 位的新原串d a t a l ，且k e y 位就是当前原串末位。 第二步：对新原串进行s t 一阶变换 对新原串d a t a l 进行一阶s t 变换，得到密文d a t a 2 。长度为( 原文 长度+ 2 ) 。 第三步：消除d a t 也中的冗余( x ，】，) 组合信息( 1 ，o ) 由第一步，根据我们在上一节性质3 证明的结论中，当原串首尾不 同时，密串中的( x ，y ) 组合肯定为( 1 ，o ) ，我们除去此冗余的固定的组合 信息，得到最终密文d a t a 3 ，长度和原文大小一致。 其利用密钥中的一位进行加密的步骤如图4 4 所示。 图4 - 4 密钥中一位进行加密的步骤 2 ) 如果m o d e 为解密 解密策略正好与加密过程相反，具体步骤如下： 第一步：s t 密文还原 由于我们在s t 加密后，消除了冗余位1 和o ，所以在s t 一阶逆变 3 1 中山大学硕士论文快速有限阶b u r m w s w h i 盯变换的加密方案设计及应用 根据加密算法和s t 变化的特性，我们可以利用s t 一阶变换性质3 知道e n c 2 中的首末位不同，为加密的时候添加的位，需要除去，以e n c 3 进行输出。 其中，利用密钥中的一位进行解密的步骤如图4 6 所示。 4 3 2 复杂度分析 图4 6密钥中一位进行解密的步骤图 在3 2 2 节中，我们介绍了s t 变换和逆s t 变换的时空复杂度均为d ( 埘) ， 其中七为阶数。这里采用s t 一阶变换，所以s t 算法的时空复杂度为d ( ) 。同 时，我们用密钥的每一位对原文进行加密，假设密钥长度为掰，所以整个加密体 制的复杂度为d ( 彪。 4 4s t 加密方案安全性分析 对称密码系统的安全性依赖于以下两个因素：第一，加密算法必须是足够强 3 3 中山大学硕士论文快速有限阶b u d w s 、枷l 盯变换的加密方案设计及应用 的，仅仅基于密文本身去解密信息在实践上是不可能的；第二，加密方法的安全 性依赖于密钥的秘密性，而不是算法的秘密性，因此，我们没有必要确保算法的 秘密性，而需要保证密钥的秘密性。我们这里研究密码系统的安全性的第一个因素，即核心加密算法必须足够 强，仅仅通过密文本身去解密信息在事件上是不可能的。因为其他如随机数生成器随机性能如何? 型堪疆黪唑寡缨力韵舒| 构储墒蚕强孰鲥鞭蘸善萍斟型冀 彳l 坍矿 招矗澎辣糯薹既2 i 蠢引刮凳搿耐i 耋：蓁；i 鬻缥舔镩羹缫扪 彰酗矍采召荜嫉翼薹；嬷蜷型些蹩鬻摧螅疆譬蝗臻； | ；艳诉防蹲溺i 审查珊篡一需逐冶譬珊婴孤到军鼬勤氧式瓠若e j 玉鞘 警崩赫勰裂羹i孺烂毳瑟期甏鋈懒骤氆这i篁藿毳衰蓓点砸萋阿赋变换是否对原文信息做了不规则的打乱混淆，从而攻击者不能通过某种内在的对 应、规律轻易地从密文转换为原文，或原文的部分信息。 s t 变换对原文进行了重排列，将原文所有0 的前继转换集中排列到结果串 的前面，将所有1 的前继转换集中排列到结果串的后面，有一定的打乱效果，下 面我们不妨以上面的例子s = 1o o o1 l1 o 】来看，假设原文的位。和 位1 的i n d e x 分别为1 ，2 ，3 ，4 。 经过st 一阶变换后，输出的结果为1o ol oo1 1 1 。容易发现， 位。相对于原文的i n d e x 为1 ，2 ，4 ，3 ；位1 相对于原文的i 1 1 d e x 为1 ，4 ，2 ，3 。 原文信息经过一次一阶s t 变换后，已经得到一定的混淆。 讨论2：我们在原文中添加( x ，y ) 组合，再消除它，看原文中的信息是否有 更好的混淆。 我们添加一个位0 和一个位1 来帮助我们对原文信息进行打乱，使得更无规 律可循 。 根据ke y 来添加首尾位。和1 ，然后进行s t 一阶变换，如此变换后的密文 的( x，y ) 组合为( 1 ，o ) ，最终并消除此组合，密文长度和原文长度保持不变。我们 不妨假 x 中山大学硕上论文 快速有限阶b u n d w s w h o c l e r 变换的加密方案设计及应用 根据加密方案，以及s t 特性，有以下结论： 当k e y 当前位为1 时，原串首位为o 时， oiol 原文其他位 l 1 ij1一 当k e y 当前位为o 时，原串首位为1 时， 1 l 1 l 原文其他位 l o 即k e y 位与原串首位不同时，( x ，y ) 组合中的( 1 ，o ) 不是我们预先添加的1 和o 。新添加的一位，被“伪装 在原文中替代了原文中的某一相同的位。而 原文中的被替代的那一位被当作( x ，y ) 组合中其中一位删除。 当k e y 当前位为l 时，原串首位为1 时， 。卫 当k e y 当前位为o 时，原串首位为o 时， 匝卫。 即k e y 位与原串首位相同时，我们在删除冗余度( x ，】，) 组合( 1 ，o ) 时，正是我 们预先添加的1 和o 。原文在( x ，y ) 组合帮组下进行了混淆。 我们这里作简单证明：我们这里不妨用石o ，n ，x 2 来分别表示新添入的首 位末位和原文的首位。在s t 一阶变换中，也有只有两个不同的上下文，分别 为。和1 ，而( x ，】r ) 组合对应的分别是原串中两个聚集的第一个元素的前继。我 们构造密文加密串时，需要在原串首尾添加不同位，即o 和1 。我们已知x 0 是 其中一个上下文的第一个元素，所以新添加的工2 肯定位于( x ，y ) 组合中。如果 石。和x l 不同，则石。也位于( x ，y ) 组合中。反之，原串中第一个异于x o 的前继 作为( x ，y ) 中的一个元素被删除。石o “伪装 成了那个位。 当k e y 位和原串首位不同的情况下，我们用新添入的位对原文中的一个相 中山大学硕士论文快速有限阶b 哪w s w h 鲥e r 变换的加密方案设计及应用 我们假设块大小为n 比特，为初始向量，是随机生成的和块大小一样的 n 比特流。每次会话加密时，都要使用一个新的随机，用此作为原文特殊 的c o 分组，和第1 个原文分组最进行异或，然后加密。同样，依次后续的输出 密文g 都将和第i + 1 个原文分组曩异或后再加密。 由于是每次会话随机生成的，的随机性使得密文第1 个分组g 随机化， 从而后面的密文g 都随机化，因此c b c 模式输出的将是m + 1 个随机密文分组。 可以通过安全信道和密钥一起传送，也可以看作是第一个密文分组，和 密文一起传送。 5 2s t 加密体制的c b c 模式实现 5 2 1 加密模块设计 分析加密策略，我们讨论当k e y 当前位和原串s 首位分别不同组合的时候， 探求原串s 和加密串d 之间的转换关系，以希望在转换的时候不用添加冗余位， 减少空间复杂度和算法实现难度。 当k e y 当前位为1 时，原文加密步骤如图5 - 2 ： 4 l x 中山大学硕士论文 快速有限阶b u n d w s 、h e d e r 变换的加密方案设计及应用 5 ) 对于如果假设有很多个o 或l 集中在一起，由于每次s t 变换之后，集 中的o 或1 的最后一个位将被与其不同的位扩散到其他地方去。如此，只要保证 了一定的密钥长度，原来集中的块将全部被打散。 6 ) 随着计算机计算能力的增强，我们通过增加密钥长度的方法，来提高原 串的随机性和防穷举攻击能力。每增加一位，都将进行多一次s t 一阶变换，多 一次的加密混淆，增加破解难度。 如此原文信息将很大的出现随机性和不可预测性，基于s t 变换的数据加密 将能够表现出良好的效率和加密强度。即使出现极少数特殊情况，也不会对数据 的安全造成隐患。 3 9 中山大学硕士论文快速有限阶b u r r o w s w h 鲥e r 变换的加密方案设计及应用 图5 - 2s t 加密体制密钥当前位为l 时的加密过程 根据我们每位的加密过程，分析不同组合，得到目标串的转换规律如下： 如果k e y 当前位为1 如果原串s 首位为o ，那么目标串d 为： 位o ( 放置第l 位) + 原串中第2 个位o 开始的所有位o 的直接前继+ 原串中第2 个位1 的所有位1 的直接前继+ 末位 如果原串s 首位为1 ，那么目标串d 为： 原串中所有位o 的直接前继+ 原串中第2 个位1 开始的所有位1 的直接 前继+ 末位 如果k e y 当前位为o 4 2 中山大学硕士论文 快速有限阶b u 兀d v 睁w h e d 玎变换的加密方案设计及应用 如果原串s 首位为0 ，那么目标串d 为： 原串第2 个位o 开始的所有位0 的直接前继+ 原串的末位+ 原串中所有位 1 的直接前继 如果原串s 首位为1 ，那么目标串d 为： 原串第2 个位o 开始的所有位o 的直接前继+ 末位+ 位l + 原串第2 个位1 开始的所有位1 的直接前继 我们构造数组昂来保存原串中所有位o 的直接前继，构造片来保存原串中所 有位1 的直接前继。 那么，当k e y 的当前位为1 ，原位串首位为0 时，用于加密的伪代码如图5 3 。 4 3 中山大学硕士论文快速有限阶b 1 i 玳嗍洲n e d e r 变换的加密方案设计及应用 我们在根据k e y 得到从原文尾位为o 或1 ，然后以尾位为起点，不断找前继， 还原出整个原串。假设我们输入的密串厶表示为d 数组，变量彻m b e 帕亿e f 0 来 保存厶中位o 的个数，而用删m b e 幻e 来保存厶中位1 的个数，值为 d 1 e i l 鲥如m b e 内亿e r 0 。用i n d e x o 来表示已经被还原的位o 在曩中的索引；用 i n d e x l 来表示已经被还原的位1 在e 中的索引。初始值i n d e x o 为 n u m b e 内亿e r o - 1 ，砌e x l 为d 1 e i l g i l l l 。当位o 的索引i n d e x 0 被还原到1 位置， 或位的索引i n d e x l 被还原到n 删曲e 内亿e f 0 1 位置，我们就需要还原其冗余的前 继信息( 1 ，o ) ，以添加冗余的前继，继续还原操作。 还原出结果后，我们需要除去首尾位，所以在还原过程中，e 被还原的第 一位和最后一位是不用保存的。 那么，当k c y 的当前位为o ，用于解密的伪代码如图5 5 。 4 5 中山大学硕士论文 快速有限阶b u 肿w s w h 鲥e r 变换的加密方案设计及应用 图5 5 当k e ) r 的当前位为o ，用于解密的伪代码 5 2 3 密钥、l v 的随机生成策略 随机数是密码学的一个重要组成部分。它们作为初始化向量，密钥的随机生 成等。但是如果攻击者可以推算出数字的序列( 通过了解使用的算法和随机的种 子值) ，那么此随机数生成是不安全的。 中