（概率论与数理统计专业论文）aont的性质及其在分组密码中的应用.pdf

摘要摘要本文从信息论的角度简单介绍了a o n t ( a uo rn o t l l i n g a 皿s f o r m ) 的定义，在域f q ( g = 矿，p 为素数，n 为正整数，主要是二元域) 中分别讨论了线性a o n t 、一般a o n t 及两者之间的联系，并给出了构造简洁实用a o n t 的方法最初m v e s t 提出a o n t 的目的是在加密过程中作为一种预处理手段，结合一般加密模式，来使得该密码受到的非法攻击( 如穷尽密钥搜索) 更加困难a o n t 所具有的性质保证了它可以用于任何其他的加密体制，本文我们主要限定在二元域和分组密码体制中讨论其性质及应用因此，为了更好的发挥a o n t 的独特性质，我们把a o n t 和分组密码的一些工作模式结合起来进行研究。在首先简单介绍了分组密码的几个工作模式，并仔细分析了硒v t 给出的实例“包变换”所具有的一些特点后，为了避免。包变换”所带来的安全及运行速度方面的不足，我们将a o n t放在普通加密模式之后并结合单向陷门函数构造了一个新的加密模式，该模式在加密时能比。包变换”更安全快速地运行，而且在明文信息较短时更为安全可靠。关键词a o n t线性变换一般变换包变换工作模式a b s t r a c ta b s t r a c tt h i sp a p e ri n t r o d u c e dt h ed e 丘n i t i o no fa o n t ( a 0 rn o t h i n g7 n a n s f o r m s ) i nb r i e ff d 0 mt h ep o i n to “n f o r m a t i o nt h e o r y ，d i s c l l s s e dt h eu n e a ra o n t ，t h eg e n e r a la o n ta n dt h er e l a t i o no ft 帕t r a n s f o r m si t lt h e 丘e l df q 国= 矿，pi sap r i i n en u m b e r ，i sap o s i t i v ei n t e g e r ) ，a n dg 孙，eam e t h o do fc o n s c r u c t i n gs i m p l ea n dp r a c t i c a la o n t a tf i r s tm v e s ts u g g e s t e dl l s i n ga o n ta sap r e p o c e s 8 i n gs t 印f o re n c r y p t i n gd a t aw i t hab i o c kc i p h e r ，印p i y i n gw i t hg e n e r a ie c r y p t i o nm o d et os i o w d o w nt h eb r u t ef o r c ea t t a c l 【s 埘t h o u te 赋e n d i n gt h ek e yl e n 昏h t h ep r o p e r t yo fa o n tm a d et h a ti tc 0 脚db eu s e df o ra n yo t h e re n c r y p t j o ns y s t e m t h e r e f o r e ，i no u rt e ) 吐w ep u ta o n tt o g e t h e r 丽t ht h ee n c r y p t i o nm o d eo ft h eb l o c kc i p h e r f i r s t l y w ei n t r o d u c e ds e v e r a lm o d e so fo p e r a t i o no nb l o c l 【c i p h e r a f t e ra n a l y z i n gt h ec h a r a c t e r i s t i c s e so f”p a 出l g et r a n s f o 咖a t i o n ，w es u g g e s t e d 印p l y i n ga na o n t 世e re n c r y p t i o n t h e nw ep m p o s e dan e wm o d eo fu s i n ga o n ti nae n c r y p t i o n l o d ew h i c hi s o t i c e a b l yf a s t e rt h a nm v e s t sp a c k a g et r a n s f o r ma n dc o u l dp r o 、r i d eac u s t o ms e c u r i t yg a i ne v e nf o rs h o r tm e s s a g e s k e yw o r d sa o n t1 i n e a rt m n s f o r i l l sg e n e r a lt r a i l s f 0 瑚sp a c k a g et r a n s _f o r m se c r ) 巾t i o m o d e2南开大学学位论文版权使用授权书本人完全了解南开大学关于收集、保存、使用学位论文的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，开采用影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供卒学位论文伞文或者部分的阅览服务；学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版；在4 i 以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术活动。学位论文作者龋啷勇蜘6 年歹月专1 日经指导教师同意，本学位论文属于保密，在年解密后适用奉授权书。指导教师签名：学位论文作者签名：解密时间：年月h各密级的最长保密年限及书写格式规定如下一。| ；内部_ 6 篝( 辱长5 年，可少于5 复)l “= 秘密1 0 年( 蕞长1 0 年可少手1 0 年)机密舶年( 最长船年，可少于2 0 年)一一南开大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。学位论文作者签名：南再删年歹月弓) 日第一章引言第一章引言1 - 1 背景介绍在对一个密码体制进行攻击的各种方法中，最基本的一种攻击方法是穷尽密钥搜索，即攻击者通过尝试所有各种可能的密钥来解密截获的密文，直到解密得到的明文成文或与已知的明文样本相对应。为了使得穷尽密钥搜索变得非常困难，尉v e s t在【1 5 】提出了a o n t 变换( a u _ o r - n o t h i n gt r a n 8 f o r m ) 的概念，其最原始的动机就是想设计一种方法，通过在对明文信息加密之前先对明文信息进行预处理，来增加敌人穷尽密钥搜索的难度于是他首先提出了一种加密模式是“强不可分的”概念定义1 1 强不可分性r j 亡r 口珊哂n o n s 印o m 6 f e ，?假设一种分组密码的加密模式把如下s 个分组的明文信息序列变换成t 个分组的密文序列m 1 ，m 2 ，一，矾c 1 ，c 2 ，。，q我们说这个加密模式是强不可分的，如果不解密所有t 个密文分组。那么想确定任何一个明文分组 k ( 或任一特定的明文分组m t 的任何信息) 是不可能的。为了满足这种强不可分性，m v e s t 同时在【1 5 中描述了一种加密模式如下：用a o n t 变换( a u - o r n o t h i n gn a n s f o r m ) 将明文信息序列变换成伪信息序列第一章引言用一般的带给定密钥k 的加密模式对伪信息序列进行加密得到密文序列。1 ，c 2 ，c 。为了使这种加密模式在实际运用中切实可行，这里a o n t 变换必须满足如下定义；定义1 2 一个变换，被称作a d z 】变换( a f f _ d r - 0 玑m g n 加r m ) ，如果该变换精明文信息序列m 1 ，m 2 ，一，映射到伪信息序列m ：，m ：，一，吃，( s s ) ；变换，是可逆的，即给定伪信息序列，可得到原始明文信息序列。变换，及其逆变换，。都是可快速计算的( 即都是在多项式时间内可计算的) ；如果任何一个伪信息块不确定，则确定任一明文信息块在计算上都是不可行的很显然，这种a o n t 模式是强不可分的加密模式。当然这里a o n t 置换，必须达到真正的随机化效果，以使得不能通过选择明文攻击来得到一个已知的伪信息块，而且即使存在_ 个能计算第一个伪信息块的特定函数9 ，9 也不能与上述定义的最后一条矛盾在这里需要指出的是a o n t 变换本身并不属于系统的加密部分，因为它与密钥信息并不发生任何联系，它仅仅是一个基于自身独特性质的可逆预处理过程。在a o n t 加密模式中，真正的加密部分是对经过a o n t 产生的伪信息分组序列进行的加密操作，在实际应用过程中，一个a o n t 变换是一个固定且公开的变换，任何人都可以用这个变换将明文信息转换成伪信息，或是给定伪信息，可用其逆变换得到明文信息正是运用a o n t 这种独特高效的性质，我们可以在不增加密钥长度的现有加密设备的基础上，极大地增加非法攻击者的破解难度假设将a o n t 运用于分组加密系统，一次a o n t 变换包含的分组数目是t ，那么攻击者进行穷尽密钥搜索时所花的时间就和t 有很大的关系，这等价于不改变现有加密设备而增加了密钥的长度例如，在本文第三章给出的设计方案中可以看出，如果我们用普通的4 0 b i t 密钥长度c b g d e s 模式结合a o n t 加密8 m b y t e 信息，那么攻击者就得解密8 m b y t e密文才能测试一个候选密钥是否正确，这和普通的c b c 模式相比，工作量扩大了一百万倍，对攻击者来说也就是相当于密钥长度是6 0 b i t 而不是4 0 b i t 了。2第一章引言1 2a o n t 应用简介在f 9 1 中给出的结论就很生动的说明了a o n t 的一个重要应用，在该文章里主要是为了使固定分组长度的加密方案更加高效，通过应用a o n t ，我们不用对整个明文信息分组逐块逐块的加密，而只需对经过a o n t 输出的部分分组加密而已，这就极大地减少了加密解密操作过程的工程量当a o n t 被用在公钥加密系统时( 如r s a 【1 6 】) ，和传统的那种加密方式( 先生成一个随机的对称密钥，再用公钥对j 而加密得到k ，然后再用凰对明文信息进行加密) 相比，这种方式能在通讯方面进行极大的简化a o n t 另一个特别有效的领域是在需要进行密钥分离的加密体制中的运用在该体制中，包含密钥信息的那部分是独立的，与整个密钥系统是分开的，而且加上带宽和传输的限制我们无法将整个明文信息( 包括安全的部分和不安全的部分)_ 起发送出去f l l j 这种体制的一个恰当的例子就是密钥被储存在一张智能卡中，持卡人希望通过这张卡上的密钥来加密和解密比较大的文件通过运用a o n t ，我们可以完全消除掉主系统中的加密元件部分，而将所需进行的加密操作限制在智能卡中，主系统运用a o n t 将明文信息进行转换，并将生成的伪信息分组中的一个分组块传送给智能卡，智能卡将对该块进行加密，并将加密后的块返回到主系统中，作为a o n t 的输出分组块这样，主系统中a o n t 的输出分组中就有一个分组是被加密过的了，如果这个被加密的分组是安全的，那么整个信息就是安全的除此以外，正如f 3 】中所指出的，我们可以用a o n t 来进行信息的互相交换假设“c e 和b o b 想交换他们所持有的秘密信息，一个可能的问题就是两方的秘密信息长度不同，这里a o n t 就可以作为一种补充，来使双方的长度相同以上我们对提出a o n t 的背景、字面上的定义、文字上的基本性质、以及a o n t在现实生活中的一些应用进行了简单的说明下面我们主要从信息论的角度来准确定义a o n t 以及在此基础上严密的讨论其性质，并在a o n t 的这些性质的基础上设计了一个新的加密模式来增加信息传输的安全性1 3 内容及主要结果本文主要介绍了a o n t ( a 1 1 - o r _ n o t h i n gn a i l s f o r m ) 的定义、性质、构造方法，以及在实际中的运用在前言中介绍了a o n t 产生的背景以及运用a o n t 的环境及部分实例后，第二章主要从信息论的角度介绍了线性a o n t 、般a o n t 的定3第一章引言义、性质以及两者之间的联系，并在域日( g = 矿，p 为素数，n 为正整数) 中给出了a o n t 存在与不存在的条件，以及在给出简单实用线性a o n t 的构造方法的基础上，讨论了一般a o n t 的生成方法，这为后面实际中运用a o n t 打下了坚实的理论基础。在实际中运用a o n t 的较好环境是分组密码中的使用，因此，为了进一步发挥a o n t 的独特性质，我船把a o n t 和分组密码的工作模式结合起来进行研究。在第三章中我们首先简单介绍了分组密码( 主要是d e s 和a e s ) 所采用的五个工作模式：e c b ，c b c ，c f b ，o f b ，c t r 。然后介绍了俄 e 雠所给出的一个应用实例一“包变换”，在分析了包变换的优缺点后，我们给出了一个新的模式，该模式能比“包变换”更快速高效的运行，而且对较短明文的加密安全性更高。本文主要成果一是在第二章中给出了一般a o n t 的存在性结论，并给出了一个具体的构造u 2 ，6 时s = 2 的( s ， ) 一a o n t 方法，以及如何由低级的a o n t 来构造高级的复杂的a o n t 的原理及其证明；二是在第三章中给出了一个新的工作模式，该模式的运行比现行使用的a o n t 模式更加高效，且对短明文的加密安全性更高。4第二章a o n t 的概念及性质第二章a o n t 的概念及性质2 1a o n t 的定义首先我们简单的从字面上给出a o n t 的定义如下：定义2 1 设x 是一个有限集，s 是一个正整数，设曲：墨一kz = ( z 1 ，z 2 ，z 。) h 一可= ( 可1 ，s 2 ，一，可。)其中甄，玑x ，1 s 若满足下列性质，就定义为一个a o n t j西是一个双射如果s 个输出值鲍，鲍，如中的任何s 1 个固定，另外一个可以自由变动那么任何一个输入值甄( 1 t s ) 都不能完全确定我们用( s ，口) 一a o n t 来表示这样一个函数，其中u = lxi ，即x 中元素的个数上述定义可以用信息论中熵函数日的性质来重新加以阐述设托，恐，五，h ，k ，k 是取自x ( 有限集) 的随机变量，这里墨，码，墨不必要求相互独立或相同分布，那么这2 s 个随机变量如果满足下列条件就称为一个a o n t ：日( x l ，一，瓦l m ，- ，k ) = o ；h ( m ，kl x l ，墨) = o ；日( klm ，巧- 1 j b + 1 ，e ) = 日( 冠) 对所有的 ，j 满足1 i s ，1 j s ；下面我们开始介绍a o n t 中的线性变换、一般变换以及两者之间的联系。5第二章a o n t 的概念及性质2 2 线性变换的定义及性质基于前面给出的a o n t 的一些基本概念和常用符号，我们在这里给出线性a o n t 的定义以及一些基本的性质定义2 2 设f q 是一个q 阶的有限域，一个日上的a o n t 是线性的，如果每个叭是日上o l ，。2 ，o 。的线性函数。下面的定理给出了构造线性a o n t 的简单方法定理2 1 假设g 是一个素数幂，m 是e 上的s s 可逆矩阵，并且m 中任何元素都不为0 ，那么函数就是一个线性b 口) 一a d 丁。证明：因为= z m ，所以有z = m 因为m 中的每个元素都非零，所以每个。，( 1 t s ) 都依赖于所有s 个玑的值更明确地说，如果n 1 个玑固定，但剩下的值( 例如鼽。) 可以变化，那么由于9 。的变化，任何都能够取到岛中的任何可能值口这里我们可以利用哈达玛矩阵f 日n d o m o r dm 抓z ) 来构造线性a o n t 来加以说明。首先我们简单介绍一下哈达玛矩阵的定义及其基本性质。定义2 3 ( 哈达玛矩阵) 一个n 阶可逆矩阵日称被称为哈达玛矩阵，如果日满足以下两个条件：日中元素取自 1 ，一1 ) ；h 酽= r i 。其中元素的运算基于实数的四则运算定理2 2 如果h 是哈达玛矩阵，则n = 1 ，2 ，或n i0 ( m o d 4 ) 关于哈达玛矩阵的存在性目前有猜想，见注1 结合哈达玛矩阵的定义及其性质，我们有：推论2 1 假设p 2 是一个素数，sio ( m o d 4 ) ，s 1 ，且存在一个s 阶的哈达玛矩阵，则一定存在一个线性的( 8 ，p ) - 4 d t 。1 注：目前有猜想：哈达玛矩阵对所有的n ；o ( m 。d 4 ) 都存在；且目前为止满足n ；0 ( m o d 4 )的最小的不能确定是否存在哈达玛矩阵的数是n = 4 2 8 6m碍f 1=第二章a o n t 的概念及性质证明：设h 是一个s 阶的哈达玛矩阵，日= b 。也，1 ，一l ，且日- 口7 = s 厶。令m 灯；b ( m o d ( p ) ) ，且“ o ，m = ”“。令s + ；s ( m o d 0 ) ) ，则m m 7 = r l ，设c is 一1 m o d ( p ) ，则有m 一1 = c 胪。显然m 满足定理2 1 中的条件，故结论成立。口容易发现，定理2 1 可以应用于任何有限域( 除了易) ，例如m 是一个范德蒙矩阵。但执行这个变换需要进行大量的有限域上的运算，因而大大降低了其实际运用的可能性。下面我们在下述推论中给出一个可以快速实现线性a o n t 的方法。推论2 2 设g 2 是一个素数幂，s 是一个正整数，那么存在一个( s ，g ) 一a d r 证明：设g = 矿，其中p 是素数，是正整数入，a ( s 一1 ) m o 却，( s 一2 ) m o d p ( q 2 时可以做到) ，因为a ( s 一1 ) m d d p ，可以定义7 = ( s 一1 一a ) ，定义m 是下面这个对称矩阵1 一一y一，y一7 ，y77 777一，y 1 一一y，y7777容易证明m 是可逆的。事实上m 1 =100o101o010oo11111la因为a ( s 一2 ) m o d p ，所以7 1 。故m 满足定理2 1 的条件口2 3 一般a o n t 的定义及性质研究完线性a o n t 的性质并得到一些基本的结论之后我们来看看一般的a o n t7第二章a o n t 的概念及性质变换在给出一些存在性和不存在性的结论之前，我们先给出数组关于某一个集合无偏的概念。定义2 4 设x 是一个 阶的有限集，a 是x 上的数组，我们把a记为一个( ， ) 数组假设a 的所有列标号为1 ，2 ，g = 1 ，2 ，) ，d g 。定义a d 为删去a 中列号不属于d 的所有列后得到的数组。我们把a称作关于d 是无偏的，如果a d 的行向量包含每一个x 上的idl 维向量p 吲次。下面的结论给出了a o n t 与无偏数组的关系定理2 3 一个( s ，u ) 一a o t 等价于一个关于下面各列的集合无偏的( 矿，2 s ，p )数组： 1 ，2 ，s ) ， s + 1 ，s + 2 ，2 s ) ，0 u s + l ，s + 2 ，一，2 s s + j ，对所有l f s ，l j s 其证明过程是显然成立的，不再赘述。为了进一步研究无偏数组和a o n t 之间的关系，我先简单介绍一下正交阵列( o r 忱叼o n 0 2o r r 叫) 的定义定义2 5 一个正交阵列o a ( s ， ) 是一个关于其任何s 元子列集无偏的( 矿，口)数组由正交阵列的定义我们马上就可以得到下面的推论成立：推论2 3 若存在一个d a ( s ，2 s ， ) ，则存在一个( s ，u ) 一a o t 。当s = 2 时，该推论的逆可由定理2 3 得出故我们有推论2 4 存在一个d a ( 2 ，4 ，t ，) 当且仅当存在一个( 2 ，“) 一a d r 易知一个o a ( 2 ，4 ，) 等价于一对 阶正交拉丁方( m o l s ) ，而”阶正交拉丁方存在当且仅当 2 ，6 ，因此结合以上两个推论，我们可以得出如下的定理；定理2 4 存在一个( 2 ，u ) 一a 0 t 当且仅当 2 ，6 定理2 5 对于任何s 2 ，( s ，2 ) 一a d t 均不存在证明过程见f 18 1 2 4 利用一般变换的性质构造s = 2 ， 2 ，6 时的a o n t为了进一步确定s = 2 ， 2 ，6 时一般a o n t 的存在性，下面的定理证明了其8第二章a o n t 的概念及性质存在性并结合拉丁方的性质具体给出了构造s = 2 ，”2 ，6 时的a o n t 的方法定理2 6 设a l = ( ) a 2 = ( 6 玎) 为一对 阶m o l s ，令b =00o妒一110-。嵇1u 一1u l0口一lu 一1其中后两列分别由a l ，a 2 各列按顺序排列而成，则b 关于任何二元列子集是无偏的证明：我们记口d 表为b 中除去所有列标不属于d 的列后得到的数组，其中d l ，2 ，3 ，4 ) 显然，由b 的构造方法可以看出毋- ，2 ，的行中包含有限字母表x 上的每一个二元组，且均出现矿= 矿矿= 1 次故集合b 关于l ，2 无偏同样，由于4 z 、a 2 是拉丁方，每一列都是x 上所有元素的一个排列，因此，关于 1 ，3 ) ， 1 ，4 也是无偏的。另外由于a 1 和a 2 是一对m o l s ，故b 3 ，4 中的二元组各不相同且包含了x 上的所有二元组，b 关于f 3 ，4 ，是无偏的。下面我们证明b 关于 2 ，3 ) 、 2 ，4 ) 也是无偏的。以b 2 ，3 ，为例，它包含了u 2 个x 中的二元组，我们只需证明这u 2 个二元组各不相同即可为了方便描述，我们把b 1 拆分成 个子矩阵，分别记为b 恐孙，其中l u 则硗孙可表示为9第二章a o n t 的概念及性质其中第二列为a 1 中的第列假设存在两个相同的二元组( t ，j ) ，由b 中第二列的构造可知这两个相同的二元组必然分布在两个子矩阵中，设它们为b 置3 ) 和b 氍，3 ) 1 m u ，1 n 口且m n 则a l 中第 行m 列和第i 行n 列上的元素均为j ，而a 。为拉丁方，每一行上的各个元素都不重复，产生矛盾，因此b 2 ，3 ) 中的二元组各不相同b 关于 2 ，3 ) 无偏。同理，b 关于 2 ，4 ) 也是无偏的。2 5 线性变换和一般变换的关系口在前面几个小节中我们简单介绍了线性a o n t 和一般a o n t 的定义和基本性质，以及各自的构造方法，为了在实际应用中进一步简化一般a o n t 的生成方法，我们有必要考虑用简单的线性a o n t 和一般a o n t 来生成复杂的级数更高的a o n t 以满足不同情况下的需求。下面的定理给出了两者之间的联系定理2 7 设日是一个q 阶有限域，t 是正整数，妒1 ，妒2 ，。是日上的( t ，g ) 一a 0 t ，z 1 ，z 2 ，z 5 ；9 1 ，圹，一，圹瑶m 是日上s t 阶可逆矩阵，并且m 中任何元素都不为零。那么函数d( z 1 ，z 2 ，目巧。，z 5 ) 一( 1 ( 。1 ) ，也( 。2 ) ，- ，钆( z 3 ) ) ，一1是f g 上的一个输入为( z 1 ，矿) ，输出为( 9 1 ，8 ) 的( 耵，g ) 一a 0 t 证明：令z = ( 。i ，。；，z ；) ，y j = ( 斫，谢，钌) ，魂( z ) = ( 盔，一，乏) = 首先证明函数曲是一个双射。因为也是a o n t ，所以九是双射，即戤与旎是一一对应的另外，由于m 是一个日上的可逆矩阵，因此( 五，施，) 与( - ，g z ，玑) 也是一一对应，所以。毛与识一一对应故函数庐是双射。其次，由于也是a o n t ，则每个z 鲁( 1 m ) 都依赖于所有的z i ，又因为( 1 ，2 ，圹) = ( l ( z 1 ) ，也( 。2 ) ，九( z 8 ) ) m 一1 ，所以( z 1 ，z 2 ，z 5 ) = ( 1 ，2 ，5 ) m ，1 0第二章a o n t 的概念及性质即( 墨，霹，露，留，考，孝，一，z f ，苟，露)= ( ，i ，一，班，f ，g ；，一，谚，鲥，鹾，一，螗) m 因为m 中每个元素都非零，所以每个磊( 1 m t ，1 t s ) 都依赖于所有武个如( 1 t ，l i s ) 。更确切的说，若s t 一1 个粥都固定，但剩下的值例如蛾可以变化，那么由于娥的变化，任何z 毛都能够取到日中的任何可能值。口第三章a o n t 应用实例第三章a o n t 应用实例3 1 工作模式简介a o n t 最初的提出可以用作构造一种新的工作模式来代替以前d e s 和a e s在实际运用过程中的几种工作模式，而为了进一步加强加密体制的安全性和可实际操作性，我们将a o n t 变换与通常的工作模式结合起来使用，构造出了新的工作模式在介绍新的工作模式之前，我们将d e s 和a e s 所采用的几种工作模式先做一简单介绍。工作模式是一种算法，它刻画了如何利用分组密码提供信息安全服务1 9 8 0 年n b s ( 即现在的n i s t ) 公布了四种d e s 的工作模式，它们分别是e c b ，c b c ，c f b ，o f b 在a e s 即将诞生之际，2 0 0 0 年3 月n i s t 为a e s 公开征集保密模式，后来于2 0 0 1 年从1 5 种候选工作模式中选定了5 种工作模式，分别是e c b ，c b c ，c f b ，0 f b 和c t r ，前四种用法类似于3 d e s ，c t r 是一种新的工作模式，在特定的环境下它有一些值得注意的优点下面我们就工作模式的概念及五种工作模式的原理简单介绍如下f 2 0 1 。工作模式的评价指标分三个方面：安全性、性能、模式执行特点，具体如下：安= 垒性( s e c u r i t y )一攻击一对模式攻击需要的数据复杂度等一可证明安全性一在合理的假设下，是否有安全性的证明结果一和类似模式安全性的比较和现在用的模式( 比如c b g ) 的比较一随机性一输出的统计特性一合理的数学背景性能( p e r f o r m a n c e )一计算的有效性一空间需求第三章a o n t 应用实例一可并行性一预处理的问题模式执行特点( m o d e i m p l l 锄e n t a t i o d l a r a c t e r j s t i c s )一可提供的密码服务一灵活性一错误特性一模式本身抗错性一简单现在对下面工作模式的描述中出现的一些符号做一简单规定和介绍：e k ( x ) ：表示在密钥k 作用下加密算法对明文块x 的加密操作；d x ( y ) ：表示在密钥k 作用下解密算法对密文块y 的解密操作；p 1 ，p z ，p ”- ：表示明文，每个只是n 个比特，n 是所用分组密码的分组长度；c l ，c z ，c ”- ：表示加密后得到的密文，g 是每个密文分组；i o ，1 1 ，i i j ：表示某特定加密体制( 如d e s 或a e s ) 的输入分组；o o ，0 1 ，o 矿：表示某特定加密体制( 如d e s 或a e s ) 的输出分组；o ：异或，表示二元数组之间按比特的模2 加运算；初始向量( j y ) ：表示一个二进制向量。在0 f b 和c f b 模式中是最初的输入分组；在c b c 模式中是与第一个数据分组进行异或的随机分组；m s b 。( x ) ：指x 的最左边的个比特，即x 的最高让位( m o s ts i g n i ! 丘c a n tb i t s ( u ) ) ；l s b 。( x ) ：指x 的最右边的个比特，即x 的最低u 位( 1 e a s ts i g n i 丘c a n tb i t s ( u ) ) ；3 1 1e c b 模式( e l e c t r o n i cc o d e b o o km o d e )e c b 模式( 即电码本模式) 如图3 1 所定义在用e c b 模式加密时，明文块只= ( 只l ，如，忍) 直接作为d e s 的输入块，即厶= ( 厶- ，厶2 ，k ) = 只；五经过d e s 的加密操作e k ( 厶) 得到输出块0 t = ( d m ，0 。) ，在e c b 模式中 即是密文分组，即q = 0 t ；解密过程是上面的逆；只= 口k ( 0 i ) = d k ( g ) 1 3第三章a o n t 应用实例彝密过程囊幢过袁研支p 1 p 2 p 蟹久：夯组撕蟹每夯接班夯疆l密文( c 1 c 2 。翻)j爰_ 曼_ ，l ( c i c 2 j c i 弘l柠八分组l雠警务f 精出钍组l蠕墨1 n 嚏- p n )图3 1 ：e c b 模式示意图3 1 2c b c 模式( c i p h e rb l o c kc h a i n i n gm o d e )c b c 模式的定义如图3 2 ：c b c 加密模式的第一次输入厶= ro ，y 输出即为第一个密文分组块，其中初始向量y 的比特数与明文分组块的长度相同c b c 模式的加密过程可描述为：=pl0 ，y ；q = 昧m ) ；五= g l 国只；0 1 ) ；g = q = e k ( 五) ；0 1 ) ；解密过程可描述为：b = d k ( q ) oj y ；只= d ( g ) o g 一1 ；a 1 ) ；3 1 3c f b 模式( c i p h e r d b a c km o d e )c f b 模式的定义如图3 3 ：1 4第三章a o n t 应用实例云；卺蠢毽蓥密爱图3 2 ：c b c 模式示意图奄密爱程磐密嚣翟图3 3 ：c f b 模式示意图第三章a o n t 应用实例在c f b 模式中，进行加密操作时，首先要将明文按固定长度k ( 1 n )分成若干个数据单元p l ，p 2 ，只，；同时加解密过程中都需要用到同一个初始向量j y ，其长度为l ；对第一明文分组进行加密时d e s 的输入即是y ，即( 五l ，厶2 ，j l 。) = ( o ，一，o ，j ，一，n ，l ) 。其加密过程为：其解密过程为g 一1 ；l s b 。【( 厶一1 1 ) ；o 只】；0 1 )0 1 ) ；0 1 ) ；y ：0 ：q 一1 ； 1 ) ；l s b 。【( 五一l 1 )e k ) ；0 1 ) ；m s 鼠鼢) o g ；“1 )3 1 4o f b 模式( o u t p u tf e e d b a c km o d e )o f b 模式定义如图3 4 所示在0 f b 模式中，与c f b 模式相同，进行加密操作前，首先要将明文按固定长度( 1 札) 分成若干个数据单元日，最，只，；同时加解密过程中也都需要用到同一个初始向量j y ，其长度为l ；对第一明文分组进行加密时d e s 的输入即是j y ，即( 1 ， 2 ，五。) = ( o ，o ，j ，j 圪) 1 6n叭厶日皿五qg 日r q 只第三章a o n t 应用实例加密。述耱* 奢迂嚣其加密过程为其解密过程为图3 4 ：o f b 模式示意图日=五=d i =只=g ：o ；三s b 。 ( 五一i 1 )民) ；0 1 ) ；m s b b ( o “) ；0 1 ) ；只。只；0 1 ) ；1 1 = i vf 1 =五=0 i =只=只=o ；l s b 。【( 厶一l 1 )e k ( 厶) ； 1 ) ；m s 鼠( q i ) ；( i 1 ) ；gor ；0 1 ) ；第三章a o n t 应用实例3 1 5c t r ( c o u n t e rm o d e )c t r 模式最初是由d i 伍e 和h e l l m a n 于1 9 7 9 年提出，在2 0 0 1 年的征集过程中，c a h f o r n i a 大学的p h i m pr 0 9 a m l y 等人强烈推荐此模式为标准他们认为c t r有如下优点。有效( c t r 模式可以并行处理) ；预处理( 密码的运算独立于待加密的数据，因此，在某些环境中可以通过预处理提高速度) ；可证明安全性( 已有文献证明c t r 的安全界至少和c b c 一样好) ；简单( 加密过程和解密过程仅涉及密码算法的加密，因此密码算法的解密不用实现) ；适于任意长度的信息加密；当然c t r 也有自己的缺点：没有完整性没有错误扩散性对错误使用非常敏感( 如果在同一密钥下，有相同的计数值则将导致安全问题)在加密过程和解密过程中需要用到计数序列噩，疋，正“正，设明文为p 1 ，p 2 ，只一- ，只( 其中f 只f = l 岛f ：= f 只一- i = n ，f 只【= ) ，则c t r 模式的加密过程为：o i = 鼠伍) ，i = 1 ，2 ，t ；a = 只0 q ，i = 1 ，2 ，t 一1 ；g = r o m s b t 。( o t ) ；c t r 的解密过程为d f = 最汜) ，江1 ，2 ，旬只= g o q ，i = 1 ，2 ，t lb = o o m s 鼠( q ) ；1 8第三章a o n t 应用实例3 2 结合a o n t 构造新的加密模式3 2 1包变换( p a c k a g en m s f o r m )尉v e s t 提出a o n t 概念之后给出了一个基于a o n t 的设计方案j 包变换 ，该方案运行效率比较高，特别是当需要加密的的明文比较长的时候，而且该方案支持快速并行处理。下面是包变换的算法描述：将需要加密的明文信息进行分组为；m ，”k ，仉；为包变换分组密码随机选择密钥k ；如下计算输出信息序列m i ，喝， 略这里s = s + 1 ：一m ：= k o 昧，( i ) ，i = 1 ，2 ，s ；一 0 = k 7 0 危lo 九2o o k 其中风= e 硒( m i o i ) ) ，i = 1 ，2 ，s 这里k o 是固定的公开的密钥可以很容易从下面的计算过程看出这个包变换是可逆的：先计算堍= ( m t o t ) ) ，i = 1 ，2 ，s ；再计算出加密时随机选取的密钥k = ”，o l o 2 0 o k ；计算出明文m i = m l ，o f k ，( f ) ，i = l ，2 ，一，s ；这里需要指出的时k 必须从足够大的密钥空间里随机选取。而且又因为7暴露在最后一个伪信息分组里，所以k 不是秘密密钥，它不受包变换下一步的真正加密部分的限制这种包变换与c t r 模式的加密有些类似，不同之处在于这里的密钥是随机选取的而不是固定的而且最后一个伪信息分组是随机密钥k 7 和前面所有伪信息的一个杂凑，这保证了密文的安全性，增加了采取穷尽密钥搜索的攻击者的破解难度，采用该包变换的加密模式比一般的加密模式难度要增加s 倍又因为只要对密文做简单的修改( 如改变某密文块的顺序或伪造某一密文分组等等) 就会影响接受方对得到随机选取的密钥k 7 的计算，即只要一个伪信息块分组不确定，就无法计算出，也就无法计算出任何明文分组块了，即采用这种包变换的加密模式是强不可分的。1 9第三章a o n t 应用实例3 2 2一个结合a o n t 的新加密模式通过对础v e s t 给出的包变换方案进行分析我们发现该方案的安全性要依赖于明文信息的长度，这样要对该方案的安全性进行重大的改善和和提高就比较难实现了基于不可分加密模式的概念，我们结合a o n t 和传统的加密模式，设计了一种新的加密方案，该方案运行速度明显高于包变换，且对较短明文的加密也具有很好的安全性为了达到这个目标，我们建议在加密部分之后运用a o n t ，这样做的好处是可以通过使用简单的随机a o n t 来提高方案的运行速度本方案的具体过程见图3 5 ：图3 5 ：结合a o n t 的加密模式示意图本方案的实现主要分为三步：第一步将明文信息茹= ( z l ，现，) 采用常规的带一个随机选择的初始变量，矿的c b c 模式进行加密得到输出g = ( 帅，g l ，玑) ，其中珈= ，y ；第二步采用类似第二章推论2 3 所给出的线性a o n t 将g 变换为z = ，施，名)第三步是先利用一个单向函数将密钥k 生成一个伪随即常量刀，然后将耳与z = ( 动，动，磊) 的最后一个分组磊结合而将隐藏起来。第三章a o n t 应用实例这里我们采用的a o n t 母定义如下：( 珈，lg “+ 骘”，玑) h ( 徇，z 1其中五= 玑+ 玑一1 ，1 i s ；徇= 珈+ 弘喝是一g ( q 2 ) 阶有限域，a 日是一常数，且 1 。由第二章定理2 1 知此a o n t 是无条件安全的。其逆变换= 咖一1 ( z ) 可以用以下方式快速计算：如果s 是奇数，则计算珈= ( z 一a ( ( 一1 ) 。五) ) ( 1 一a ) ；f = 2如果s 是偶数，则计算珈= ( z l + 入( ( 一1 ) 五) ) ( 1 + 妁；t = 2 汁算玑= 苁一玑一1 ，i = l ，一，s 因为我们的工作环境一般都是在域f q 托= 2 ”) 上的，故该计算可以简化为：s计算珈= ( oa ( 五) ) ( 1 0 ) ；i = 2计算玑= 嚣。执一1 1 s 在该方案第三步中的伪随机常量7 是由我们定义的一个 阶单向函数厶： o ，1 ) “一 o ，1 ) n来生成的，这里凡畔) = k 1 = k 其中j 乙+ - ( 1 + 1 ) 是根据如下的循环来计算的：凰= 0 ；k 1 ：k ；墨= 8 托( 蚝一l o 恐一2 )可以看出，在收方拥有密钥k 的情况下计算= 疗1 ( z ) 是很简单的，而非法攻击者在不知道k 时计算单向函数z = ) 的逆就很困难了。如果想进一步增加非法破译者的难度，我们可以通过增加叫的大小来加以调节2 1第三章a o n t 应用实例3 2 3 上节中加密模式的性能及安全性分析首先需要指出的是该模式并不满足r i e s t 所定义的不可分性。因为如果把( 如，幻，磊) 当作密文，则攻击者并不需要同时破译所有的密文来得到一特定的明文分组，但本方案类似于不可分性的地方体现在方案中的单向陷门函数厶上，即攻击者要得到任何一指定的明文分组前，都必须先解密得到，即必须先执行2 次解密操作，而叫是可以调节的且是独立的自由变量。另一方面，本模式与尼”e s 亡给出的包变换模式以及与最初提出a o n t 时的运用方式不同，在本方案中，a o n t 部分是用在加密模式之后，而且单向陷门函数厶中利用密钥k 进行了2 次加密操作点k ，因此，本模式中的a o n t 与加密部分不是脱离的，而是紧密联系在一起的，这可能在某些方面增加了实际运用的复杂性( 如并行运算方面) ，但在不增加密钥长度的前提下本模式更好的增加了加密的安全性因为在加密部分之前对明文运用a o n t 的方案中，其且的就是希望得到伪随机性很好的加密输入分组，但明文由于格式的原因一般具有很好的统计特性，即不随机性，以及选用的a o n t 一般具有线性性，所以通过a o n t 转换得到的伪随机明文分组肯定会泄漏明文的一些信息，从而针对选择明文攻击而言有时并没有增加加密的安全性，而在本方案中，通过在加密部分之后使用a o n t ，加上( y o ，g ，玑) 是加密之后得到的信息分组，具有很强的随机性，对( g o ，g ，舶)使用a o n t 转换之后，以及用厶对岛进行隐藏之后，非法攻击者甚至不能得到密文( 蜘，玑，蜘) ，因此他不能直接采取一般的方法来攻击密文，z 1 ，磊) ，这很好的弥补了明文的统计特性所带来的安全方面的担忧。除此以外，本模式与包变换不同的地方在于，本模式的安全性不依赖于明文信息的长度，而是依赖于可自由调节的强度因子一自由变量”，这就使得本方案可以对很短的明文提供很好的安全保证第四章结束语第四章结束语本文从信息论的角度简单介绍了a o n t ( a “0 r d t t 叼n 帆s ，m ) 的定义，在域f 口( 口一矿，p 为素数，n 为正整数，主要是二元域) 中分别讨论了线性a o n t 、_ 般a o n t 及两者之间的联系。并给出了构造简洁实用a o n t 的方法，这些性质为实际中安全运用a o n t 提供了理论上的保证最初崩u e s t 提出a o n t 的目的是在加密过程中作为一种预处理手段，结合一般加密模式，来使得该密码受到的非法攻击( 如穷尽密钥搜索) 更加困难a o n t所具有的性质保证了它可以用于任何其他的加密体制，本文我们限定在分组密码体制中进行讨论因此，为了更好的发挥a o n t 的独特性质，我们把a o n t 和分组密码的一些工作模式结合起来进行研究我们首先简单介绍了分组密码的几个工作模式，在分析了砘u e 豇给出的运用a o n t 实例“包变换”所具有的一些特点后，为了避免包变换所带来的安全及运行速度方面的不足，我们决定将a o n t 放在普通加密模式之后并结合单向陷门函数构造了一个新的加密模式，该模式在加密时能比“包变换”更安全快速地运行，而且在明文信息较短时更为安全可靠类似地我们可以将a o n t 与其他的加密模式( 如e c b ，c f b ，o f b ) 结合起来构造类似的加密模式，而且该模式中的单向陷门函数也可以由其他的单向函数来代替，如基于分组密码的单向日a s 日函数等本文的讨论一是限定在域f g ( q = 矿，p 为素数，n 为正整数，主要是二元域)中，二是限定在分组密码体制中，实际上a o n t 所具有的独特性质也适用于其他的域以及其他的密码体制，但因为在实际中运用的最多是这两种情形，所以没有在这两种情形外展开讨论a o n t 在其他的一些情形下的讨论，特别是在其他加密体制( 如公钥密码等非对称密码体制