（概率论与数理统计专业论文）布尔函数中的正形置换.pdf

摘要 摘要 正形置换具有良好的密码学性质，在密码体制中特别是在分级密码的设计中有重要 的应用。文中在对正形置换的结构和性质的研究的基础上提出正形置换的正形平移的概 念，得出了正形置换的正形平移依然是正形置换的结论，并指出了它们与该正形置换的 平移等价类之间的关系。 如何构造正形置换是目前密码学研究的一个热点。本文介绍了当前的构造方法，给 出了几个构造正形置换的新方法。指出了一个非线性正形置换通过正形平移可以变成新 的非线性正形景换，说明了如何通过局部改变一个正形嚣换的输出值，使所得的置换依 然是一个正形置换，论述了一种由矿阶正形置换构造妒“正形置换的方法。由低阶的正 形置换通过一定的组合，可以递归的构造出任意高阶的正形置换。 关于正形置换在密码体制中的应用，本文介绍了利用正形置换强化分组密码，利用 正形置换构造密码安全函数的方法，给出了一个利用正形置换加强密码安全性的方案。 关键词：正形置换线性结构差分均匀度分组密码序列密码 a b s 仃a c t a b s t r a c t o 曲( h n o r p l l i cp e h m a t i o n sh a v eg o o dc h a r c t e r i s d c sa t 】dv e r yi i l l p o r t a n t 印p l i c a t i o n si i lc r y p t o s y s t e m s ，e s p e c i a l l yi 1 1 血ed e s i g no fb l o c kc i p h e ri nn l i sp 印e l w ep r e s e n tan o d o no fo r 山o m o r p h i c 订a 1 1 s 一 1 a t i o n ，b a s e do nt b es t l l d yo ft 1 1 ec o n s t m c t 【l r ea 1 1 dp r o p e n i e so fo r t h o m o r p h i cp e r r n u t a t i o n s ，锄dd r a w ac o n c l u s i o nt h a tt b em eo r t h o m o r p h i c 缸m s l a t i o n so fa no n h o m o i ：p h i cp e m l t a t i o na r es t i l lo r h o m o r _ p 1 1 i cp e r r n 柚t a t i o n s f u r t h e r m o r e ，w ep o i n to u tm er e l a t i o n s l l i po ft h e m 肌dt h ee q u i v a l e n c ec l a s so f 出e o r t h o m o r p h i cp e n 曲u t a t i o n i ti sah o t s p o ti nt h es t i l d yo f c u 甲t o g r a p h yn o wh o wt oc o n s 订u c to r m o m o i p h i cp e r i 柏u t a t i o n s i nm i s p 印e l w ei n 廿o d u c et b ep r e s e n tm e t l l o d so fc o n s 仃l l c t i n go r t h o m o i p 王l i cp 锄u t a d o n s m o r e o v e l w ei l l u s t r 旨t es o n en e wm e t h o d s f i r s t l y w ep o i md u tm a tt 1 1 eo r t h o m o r p h i ct r 8 i l s l a t i o n s0 fan o n l i n e a ron ：h o m o r _ p h i cp e r m u t a 石o nc a nb en e wn o n l i n e a ro n e s s e c o n d l y ，w es h o wt h a tb o wt oc h a i l g eo n eo r t h o m o r p h i c p e m u t a t i o np a r t l yi 玎t oa n o 抽e ro r t h o m o i p l l i cp e 姐u t a t i o n t h i r d l y ) w ee ) 单l a i l lt l l a th o wt og e ta no r t l l o m o 巾h i cp e r i n u t a 蛀o nw i t h2 ”州一d e 呈t e e 丹o mo n ew i t l l2 ”一d e 乒e e f i n a l l y ，w ep r d v em a tb yc o m b i n i n g s o m eo n h o m o r p h i cp e r m u t a t j o n s 丽m1 0 wd e g r e e ，o n ew i t ha na r b i 枷l y 撕g hd e 酽e ec a nb eo b t a i n e d a b o u tt h e 叩p l i c a t i o 璐o fo r m o m o r p h i cp e m l u t a t i o n s ，w ei n 打o d u c em em e t l l o do fs t r e n 群h e n i n g b l o c kc i p h e ra n dc o i l s m | c 血gb o o l e a n 铀c d o n sw i mp e m c tc d ，p t o g m p l l i cc b 砌c t e r i s 廿c s ，a 1 1 d 舀v ea s c h 锄eo f e n h a n c 曲gt l 】es e 砌t yo f ac i p h e r b yt h eu s eo f 0 吡o m o r p l l i cp e m u t a t i o n s k e yw o r d s ： o 柑1 0 m o r p h i cp 锄u t a t i o n l m e a rs t m c t u r ed i 断e t i a lu n i f o mb 1 0 c kc i p h e r s t r e a mc i d h e r i i ；厂9 6 8 6 6 7 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：、磊 f 孩 笈 细年r 月引日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 l 指导教师签名：学位论文作者签名： | 解密时间：年 月 日 各密级的最长保密年限及书写格式规定如下 内部墙年( 最长5 年，可少于5 年) 秘密1 0 年( 最长l o 年，可少于1 0 年) 一 机密2 0 年( 最长2 0 年，：可少于2 0 年) j j 二- i 二。= = j _ 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：、白泡饩 ；年r 月；日 第一章引言 第一章引言 1 1 正形置换的研究现状及发展趋势 正形置换【i 】( o n h o m o r p h j cp e u t a t i o n ) 由 l b m a i l n 于1 9 4 2 年引入，继而m h a l l 和 l j p a i g e 等人于1 9 4 7 年开始从抽象群论角度分析这种置换 2 ，但是真正公开的将正形置换 用于密码算法和保密系统设计的是1 9 9 5 年美国t e l e d y n e 电子技术公司的l o t l l i o pm i t t e n t h a l 博士。他的工作是具有开创性的 3 。 正形置换已经被证明具有有用的密码学性质 3 1 ，可用于构造s 盒。基于此种s 盒的 分组密码体制能够抵抗密码分析中最强有力的攻击方法一差分分析和线性分析。置换理 论在密码体制设计中有重要的应用，任何没有信息扩张的密码体制都可以看作置换的结 果。如常用的分组密码体制d e s 算法是明文在密码控制下的置换 4 1 ，公钥密码体制r s a 是一种多项式鼍换【扪。本质上是一个置换的分组密码的安全性主要取决于它所使用的置 换的好坏，特别是差分分析和线性密码分析的提出以及对d e s 密码体制的破译，迫使人 们设计更好的密码算法，寻找更好的置换源。 目前关于正形置换的研究尚处于初级阶段。国内冯登国、刘振华、吕述望、朱华安等 人也相继作了不少工作，主要的研究内容为正形置换的构造和计数，目前的构造方法可 分为：( 1 ) 正形拉丁方的截集构造，( 2 ) 有限域上的构造，( 3 ) 移位寄存器构造，( 4 ) 把正 形置换的判定转化为多输出布尔函数的平衡性的判定，并由此构造正形置换，( 5 ) 利用已 知的正形置换，通过级连迭代可构造出更多的正形置换。由于已知特征为2 的有限域上 正形置换与正形置换多项式之间存在着一一对应关系，可将特征为2 的有限域上正形置 换的研究转化为有限域上的正形置换多项式的研究。 目前关于线性正形置换的结构和计数问题已经得到解决，但关于正形置换的计数还 有待解决，从目前的结果来看，低阶的正形置换的数量已经是相当大的，所以高阶的正 形置换的精确计数是非常困难的。记有限域月上的正形置换的个数为岛，目前已知的结 果为j d l = o ，p 2 = 8 ，p 3 = 3 8 4 ，当，7 3 时，r 2 2 ”“”。咀利用计算机搜索得到的结果是 n = 2 4 4 7 4 4 1 9 2 。 正形置换的研究在密码学中有重要的意义，关于它的研究是近年来密码学研究的热 点之一。但关于正形置换的研究尚处于初级阶段，目前人们对正形置换的构造和计数问 题还没有完全解决，尚无成熟的构造正形置换的方法。 目前这个领域还有许多理论和实际问题需要继续研究和完善，还有许多问题等待解 第一章引言 决。这些问题主要包括：( 1 ) 正形置换特征的进一步刻画；( 2 ) 如何构造正形置换还需要 更一般的方法，尤其是非线性正形置换的有效构造；( 3 ) 如何将正形置换更有效的用于分 组密码算法中，正形置换的完善平衡性与s 盒的其他密码特性的关系，以及由正形置换 产生的s 盒的抗攻击能力等；( 4 ) 如何将正形置换有效的用于前反馈序列输出函数及单向 h a s h 算法的设计中。这些都是值得研究的问题，也代表了关于正形置换的研究的发展趋 势。 1 2 本文的主要结果和内容安排 本文主要目的是通过研究正形置换的结构和性质，给出正形置换的有效构造方法。 第一章是关于正形置换的性质的研究。目前正形置换的结构和性质并没有被人们完全了 解，因此对它的研究工作很有意义，可能得到新的发现只有对它的性质和结构充分了 解，才能有效的进行应用，并能够更有效的构造正形置换。第二章是正形置换的构造方 法的研究。正形置换有很好的密码学性质，并且在分组密码的设计中已经都到有效的应 用，怎样构造足够多的满足要求的正形置换，设计出高效的构造方法，这是一个密码设 计者应该掌握的。本文将从以下几个方面进行研究：( 1 ) 利用有限域和代数的方法，简单 有效的构造一系列正形置换；如何对一个正形置换进行变形，进而得到新的正形置换； ( 2 ) 由2 ”阶正形置换，如何构造2 ”1 阶正形置换；( 3 ) 利用已知的低阶的正形置换，如何 构造出高阶的正形置换。第三章是正形置换的应用方面的研究。讨论正形置换在分组密 码设计中的应用，以及如何利用正形置换来构造密码安全函数，如何利用正形置换来强 化序列密码等其它密码体制，并在其它方面做一些初步的探讨。 第二章简要的介绍了正形置换的基本知识和有关性质，以及它的密码特性。第三章 介绍了正形置换的构造方法，并在此基础上给出了几种新的构造方法，得到了较好的计 数下界。第四章介绍并探讨了正形置换在密码体制中的应用，给出了一个用正形置换强 化序列密码的方案。 2 第二章正形置换的性质 第二章正形置换的性质 2 1 正形置换的基础知识 2 1 1 正形置换的基本概念 记g f ( 2 ) 表示有限域 o ，1 ) ，设r 为g f ( 2 y 上的双射，即对任意的a g f ( 2 ) ”，有且仅有 唯一的j g f ( 2 ) n ，使得r ( z ) = 峨则称月为g f ( 2 ) ”上的布尔置换，简称为置换。 定义2 1 设r 为g f ( 2 ) ”上的一个置换，为g ，( 2 ) ”上的恒等置换。若r o 仍为g f ( 2 ) ” 上的一个置换，则称r 为g f ( 2 ) ”上的正形置换 r ( 功为正形置换的充要条件为r 0 ) ，r ( 砷ox 都是置换。 设r 为正形置换，s = 兄o j ，则s 也是正形置换，称s 为r 的补置换。记g f ( 2 ) ”上全 体正形置换的集合为d r 。 定义2 2 设月为g f ( 2 ) ”上的一个正形置换，若对任意的x ，_ y g ，( 2 ) ”有r oo 力= r ( x ) o 尺，则称r 为g f ( 2 ) ”上的一个线性正形置换。 易见，对线性正形置换足有尺( o ) = o 。 记g ，( 2 ) ”上全体线性正形置换的集合为三d p 。 定义2 3 设r 为线性正形蛊换，6 g f ( 2 ) ”令凰( 曲= r ( x ) o6 则称如是由6 确定的 仿射正形置换，用一o r 表示g f ( 2 ) ”上全体仿射正形置换的集合。 设j r 为正形置换，6 g ，( 2 ) ”凡( x ) = r ( 曲o6 ，称凰是与r 平移等价的正形置换。 定义2 4 设r 为正形置换，但非仿射正形置换，则称r 为非线性一 仿射) 正形置换 并记g f ( 2 ) ”上全体非线性正形置换的集合为工d r 。 定义2 5 设尺为g f ( 2 ) ”上的一个正形置换，r ) = y o ，r ( i ) = y 1 一，月( x 2 q ) = 憎 其中和。如= 如，z 1o ) ，1 = z 1 ，心一一1o 儿一一1 = 2 2 一l ，则称集合 为月的向量表示。 3 箜三童垩墅重垫塑焦亟 定义2 6 设r 为g f ( 2 ) 上的一个正形置换，则r 可表示为一些不相交的轮换之积 若( a 1 ，n 2 ，a e ) 为尺的轮换分解式中的一个因子，则称女为这个因子的轮换长度除不动 点以外，轮换因子最小的那些因子，称为j r 的最短轮换因子。 定义2 7 设r 为g f ( 2 ) ”上的一个正形置换，若月的圈结构为( ) ( x ”，x * ) ，其中 ：2 一一l ，f 0 ，k 2 n l ，则称r 为最大正形置换。记g ，( 2 ) ”上全体最大正形置换的 集合为 d 尸。 记g f ( 2 ) n 全体最大线性正形置换的集合为尬d r ，最大非线性正形置换的集合为 m n l o p n 。 定义2 8 一个2 ”阶正形拉丁方是一个 p ( f ，d = o 工而一个2 ”阶正形拉丁方的截集， 每行一个，每列一个，且两两不同。 2 m 2 m 方阵，它的第j 行第j 列的元素为 是从该拉丁方中选取的2 ”个元素的集合， 一个g f ( 2 r 上的正形置换就是2 “阶正形拉丁方的一个截集。这是正形置换的另一个 等价定义。 2 1 2 正形置换的性质 ( 1 ) 设r o r ，则置换r 的圈结构为( ) ( z 。，) ( x 。，。协c ) ) 且圈长均不为2 易知：若r l d 尸。，贝0 x j 0 = e 。 ( 2 ) m o p 打l = 2 ”i l 0 尸一1 。 ( 3 ) 设r 为置换，s ( x ) = 月( z ) o z ，则 ( a ) 尺d r 当且仅当s o r 。 ( b ) r 上o r 当且仅当s 三d 一。 ( c ) 尺爿d r 当且仅当s 爿o r 。 f d ) r 舭o r 当且仅当s d r 。 f e ) 月肘o r 与s d r 不一定等价。例如： r = ( o ) ( 1 ，8 ，1 2 ，11 ，5 ，1 0 ，2 ，1 4 ，1 5 ，1 3 ，6 ，3 ，9 ，4 ，7 ) s = ( o ) ( 1 ，9 ，1 3 ，1 1 ，1 4 ) ( 2 ，1 2 ，7 ，6 ，5 ，1 5 ) ( 3 ，1 0 ，8 ，4 ) ( 4 ) 若尺l o b ，则r 2 2 上d p 。，= o ，1 ，0 1 ，其中f 0 是2 模o r 战r ) 的方次数，d ，硼r ) 是尺在g f ( 2 ) ”上的对称群中的阶数。 ( 5 ) 若只 化。一，则存在正整数p ，使得s = s ( x ) o x = 舻。 ( 6 ) 若尺讹d j p 。，贝0 r 2 ，r 3 ，一，r 2 ”一2 l o b ，其中当( 7 ，2 ”一1 ) = l 时，r 7 舰d p ”。 ( 7 ) 若尺讹o r ，且r = ( 2 u ) ，则对任意的j = 1 ，2 ，2 ”一2 ，均有 ，x q j + 1 ) ， 都是g f ( 2 ) ”的基底。 4 第二章正形置换的性质 ( 8 ) 若r d 岛，贝0 r 一1 d j d 。 下面是一些重要的定理和结论： 1 ( 正形置换存在性定理【q ) 有限a b e l 群g 上存在正形置换当且仅当群g 的s y l o w 2 子 群不是循环群或者是平凡子群。 2r 为一个正形置换，设g r = ，如，2 0 ) ，( x 1 y 1 ，2 1 ) ，( h ，蛐_ h 劲一1 ) 】是r 的向量表 示，那么月为线性的当且仅当g r 在对应位模2 加下形成一个2 ”阶交换群，且蜘= e 3 g ，( 2 ) ”上正形置换尺为一仿射正形置换，当且仅当存在g f ( 2 ) ”上的，z 阶正形阵爿( 即 使彳。厶可逆的”阶可逆矩阵4 ) 及g f ( 2 ) ”中的向量口，使得月( 曲= 血o a 。 4 线性置换r 为正形置换，当且仅当月只有一个不动点。 5 设r 为一线性正形置换，且r 的最短轮换因子的轮换长度为则r 2 ，腰，月。1 仍为 线性正形置换。 6 设r 为正形置换， 为线性置换，则 _ 1 r 仍为正形置换。 7 6 f ( 2 ) ”上正形置换r 是最大正形置换月的特征多项式是g f ( 2 ) ”上的本原多项式。 由这个结论，设r 为最大线性正形置换， 为线性置换，则一只 仍为最大线性正形置 换。 在密码体制的设计中，置换的非线性是一个重要的衡量指标。下面给出非线性正形 置换的测试方法和差值非线性度。 设r ( x ) 为g f ( 2 ) ”上的非线性正形置换，定义( x ，力= 月( 曲o | r o r o y ) ，若n ( x ，y ) 在 所有x ，y 值均匀分布，则认为r ( x ) 是可以使用的非线性正形置换。 设r o r ，定义r 的差值非线性度为 1 三；：音【 ( x ，力g f ( 2 ) 2 ”i 尺( 砷o r ( ) ，) 月( 工o y ) j i 由定义，当月( e ) = p 时，l ：2 2 ”1 2 ”1 。 2 1 3 正形置换的完善平衡性 已知g ，( 2 ) 上不存在正形置换，所以当我们讨论g f ( 2 ) ”上的正形置换时，总是假设 h 2 。 g f ( 2 ) ”上的正形置换只是完善平衡置换吼即：对g ，( 2 ) ”的任意2 ”1 阶子群g ，均有 啤( g ) n g i = 岍( g ) n g l = 2 卜2 5 第二章正形置换的性质 。这里g 是g 在g f ( 2 ) ”中的补集。 也就是说，g f ( 2 ) ”上的正形置换将g f ( 2 r 的极大子群的元素的一半映射到它本身之 中，一半映射到它的补集中。 由正形置换的完善平衡性，有 p 0 g 啤0 ) g ) = j d 0 g k g f ( 2 ) ”) 若z 从g ，( 2 r 中均匀随机选取，则 1 尸0 g i 尺( 曲g ) ：p ( 工g 障g f ( 2 ) ”) = 妄 这里p ( ) 表示概率。 用信息论中的熵可以这样刻画： 。h ( z g ：月( z ) g ) = 一1 0 9 2 。p ( x g ：r ( x ) g ) = l ( 6 f f ) 也就是说，我们由该置换的输出的得不到输入是否属于某个极大子群的任何信息。 2 2 正形置换的结构特点 将一个正形置换的输出作有规律的改变，所得到的置换仍然是正形置换。 下面介绍相关的概念 13 。 定义：设r ( 力是g f ( 2 ) ”上的置换，对给定的a g f ( 2 ) ”，对任意的x g f ( 2 ) ”若 r ( 司o r o a ) = 常数，则称口为尺( x ) 的线性结构。 定义：设r ( x ) 为g f ( 2 ) ”上的置换，称 嘴。口量) g 尸( 2 ) “i r o ) 。j r ( 埔口) = 卢 口o 为月( x ) 的差分均匀性或差分均匀度，记为6 ( 彤或如。 称2 ”2 ”阶矩阵a 为置换r ( x ) 的差分分布矩阵，如果 a ( r ) = 山o o 1 0 1 其中，如= | l x g f ( 2 ) ”i r ( 曲o r 0 0 d f ) = 岛l = o ，1 ，2 ”一1 。嘶，岛分别是j 的二进 制表示。 6 第二章正形置换的性质 最大的2 u ( f o o ) 即为差分均匀度。 2 ”一l 易见，差分分布矩阵中的元素满足：2 i 如，= 2 ”。 j = 0 设口g f ( 2 ) n ，d ：( 口。口1 。h ) ，令6 ：莹d ，2 f ，则映射：妒：a 一6 是g f ( 2 ) ，t 到g f ( 2 ，t ) 的 j - 0 同构。为方便记，将a 6 视为等同。 2 2 1 正形置换的正形平移 2 ”一1 ，其中r ( f ) ：f ：。，1 - 一，2 。一1 简记为r 娩”一- j 0 0 ，h _ 一，z 2 q ) 设t 为g ，( 2 ) ”上的一个置换，f = ( f ( o ) ，t ( 1 ) ，丁( 2 ”一1 ) ) 。 定义2 9 设r d 只，尺= ，x h ，硒一1 ) ，若g f ( 2 ) ”上置换的f 满足r ( f ) = 6 0 f ，2 o ，1 ，一，2 ”一l ，6 g f ( 2 r 为常数，则称凰= ( * ( o ) ，j ，( 1 ) ，坼一1 ) ) 是r 的正形平移。 定理2 1 一个正形置换的正形平移仍然是正形置换。 证明：设j r g f ( 2 ) ”，胄= ( 。o ，z l ，。2 u ) ，f 为g f ( 2 ) “上置换且满足“f ) = 6 0 f ，k o ，1 ，2 一一l ，6 g f ( 2 ) 一为常数。因为t 为置换，所以r 的正形平移凰= ( h 0 1 ，1 ) ，嘲2 q ) ) 为g f ( 2 ) ”上的置换，由正形置换的定义，只需要证明凰o ，= ( 并( o ) o o ，* ( 1 ) o l ，瓢2 q ) o ( 2 ”一1 ) ) 为g f ( 2 ) 一也是置换即可。因为( 。o o o ，z l o l ，x 2 u o ( 2 ”一1 ) ) 为r 的补置换，故它的 任一个排列方式也构成一个置换，即( 。州o ) o r ( o ) ，* ( 1 ) o t ( 1 ) ，h 2 q ) o ( 2 ”一1 ) ) 是置换。它在 g ，( 2 ) n 上加上一个常数后还是置换：( h o ) o f ( o ) 0 6 ，h 1 1 0 “1 ) 0 6 ，啊2 u ) o ( 2 ”一1 ) 0 6 ) 而f ( f ) = 6 0 f ，f o ，l ，一，2 ”一1 ，即“f ) 0 6 = f ，所以上式变为o o o o ，j lol ，。2 ho ( 2 ”一1 ) ) 也就是说，( 如o o ，。lol ，靶h 毋( 2 ”一1 ) ) 为一个置换，即凰o 是置换。# 在上述定理中，令6 = l ，2 ，2 2 ，2 ”1 得到如下推论： 推论2 1 若r = z h 一，。2 叫) 为正形置换，则( z l ，如，均，。2 ，娩h 娩一2 ) ( 相邻的两 个元素交换位置) ，沁，妁，抽，x 1 ，z 2 q ，娩一，q ，靶q ) ( 相邻的四个元素前两个与后两个 交换位置) ，( 。! “，。2 h ，。，“蜘，h 一。川一1 ) ( 所有元素前面2 ”1 个与后面2 ”1 个 交换位置) 仍然是正形置换。 推论2 2 若r = ，乩，x 2 h ) 为正形置换，则将如，x l ，砌一l 反序排列所到得到 的置换q ，砌_ 2 ，扎蜘) 仍然是正形置换。 定理2 1 说明，一个正形置换与满足一定条件的置换的乘积仍然是一个正形置换。更 进一步，所有满足定理2 1 中的条件的置换构成对称群s 。的一个子群。定理2 1 还反映了 7 o 协 = r 足 没 第二章正形置换的性质 正形置换与正形拉丁方在结构上存在着一定的联系。一个2 ”阶正形拉丁方如下 o1 l o 23 32 2 ”一2 2 ”一l 2 ”一1 2 ”一2 2 ”一1 2 ”一22 ”一32 ”一4 - l0 且具有如下递推关系： 伽。2 ” 而定理2 1 中的置换t 正好是2 ”阶正形拉丁方中的某一行或某一列。也就是说，设正形置 换r = ( 蜘，乩砌一1 ) ，将排列，乩，比q ) 按照2 ”阶正形拉丁方的某一行或某一列改 变排列顺序，所得到的置换仍然是一个正形置换。 设r o b ，记集合伊= 如i6 g f ( 矽1 ，它为由定理2 1 得到的所有正形置换，易见 i 俨i = 2 ”。我们称伊为正形置换五的正形平移类，并且称凰为r 的由b 确定的正形平移 ( 6 g f ( 2 ) ) 。设r o r ，记集合= 如= 月。啪g f ( 2 ) ” ，易见m 8 l = 伊= 2 ”。集合爿8 为r 的平移等价类当r 为线性正形置换时，一8 即为由r 确定的所有仿射正形置换。 2 2 2 正形平移类与等价类的关系 集合c 8 和集合，与正形置换r 的线性结构有一定的联系。令r ) 的全体结构之集 为易见，= 0 l 的充要条件是靠c 掣。关于正形平移类伊和平移等价类俨之间 的关系，有如下的结论。 定理2 2 设月。则i c “n 俨l = i i 。 证明：设月= ( 。o 。l ，叫) ，t 为g f ( 2 ) ”上的置换，满足“0 0 一6 ，扣o ，l ，2 ”一1 ，6 g f ( 2 ) “为常数，凰= ( 。“0 1 ，研1 ) ，研2 q ) ) 伊。 若如伊n 爿“，即凰= 尺。口，d g f ( 2 ) ”为常数，有h o ) = 蜘。口，吼1 ) = x l o d ，啊! q ) = j 2 qo 口，上式表明r ( t ( j ) ) o r ( i ) = d f = o 1 ，2 “一1 ，而r ( j ) = j o6 ，所以r ( i o b ) o 尺( j ) = & ，故 b 为r 的线性结构，即6 ，所以l 伊n 一8 l i i 。 下证i 掣n 4 8 l i | _ 设6 即对任意的f g f ( 2 ) ”，只o o6 ) o 月( i ) = d 为常数，令 丁( 订= fo6 ，则可得岛= ( 。“o ) ，啊1 ) ，* p 1 ) ) c 8 ，且如= 尺。以故凰c 。n ，所以 l ( ，n 4 尺j i u 片。 综上l 伊n j = i i 。# 8 第二章正形置换的性质 推论23 设r 为线性正形置换，则c “= 4 “。 由这个推论可以知道，线性正形置换的正形平移是仿射正形置换。 推论2 4 设r 为非线性正形置换，则c 8 ；若靠 2 ”，则l c 8n 爿。i = 1 ，即c 8 中除了 r 本身以外，没有与r 平移等价的正形置换。 定理2 3 设r d r ，a ) 为r 的差分分布矩阵，则r 的正形平移的差分分布矩阵与 a 职) 相同。 证明：设r = ，j l ，2 u ) ，t 为g f ( 2 ) ”上的置换，满足t ( f ) = c o f ，- o ，1 ，2 ”一1 c g f ( 2 r 为常数，爱。= ( h o ) ，h 1 ) ，! 叫1 ) 是r 的一个正形平移。 易见，v 口g f ( 2 ) ”，盖。0 。c ) = h 删= = r ( 口) ，矗。( 口) = h 。) = 工疵= r ( 口oc ) 爿! 撑 现在考虑a 中任意的一个元素西，而= g f ( 2 ) ”l 尺( j ) o 尺0 0 1 ) = 川，由上面的论 述，有 而= i 协g f ( 2 ) ”l 盖。( x 。c ) 。五。0 0c o f ) = 力l = b ，g f ( 2 ) ”i 袁。c 0 0 矗。c v o f ) = ， i = j 玎 这就表明，兵。的差分分布矩阵a ( 袁。) 和a 是相同的。# 推论25 设月d r ，疋为r 的一个正形平移，则靠= 魄，即差分均匀度不变。在定理 2 3 的证明中，若r 为非线性正形置换，则其差分分布矩阵a 中必有元素 “( f o ，j o ) 满足o 知 2 ”，那么r 的正形置换丸的差分分布矩阵a 溶。) 中元素动满足ocb 2 ”， 即疋也是非线性正形置换，这样就得到： 定理2 4 非线性正形置换的正形平移仍然是非线性正形置换。 因为对每个正形置换r ，必有不动点为。的正形置换与之平移等价，故在分析正形置 换的性质的时候，可只考虑不动点为。的正形置换有关g ，( 2 ) 4 上的正形置换的统计表 明，g f ( 2 ) 4 上的绝大多数的非线性正形置换满足i c 8 n 一8 i = 1 。由定理21 有，由r 构造 的与r 不平移等价的非线性正形置换的个数为2 ”一1 。 9 第三章正形置换的构造和计数 第三章正形置换的构造和计数 3 1 正形置换的构造方法 近年来很多人在正形置换构造的方面做了大量的研究。目前已知的构造方法有正形 拉丁方的截集构造、有限域上的构造和移位寄存器构造等。文献 9 把正形置换的判定转 化为多输出布尔函数的平衡性的判定。文献 2 1 利用已知的正形置换，通过级联迭代可 构造出更多的正形置换。 3 1 1 线性正形置换的构造方法 l m i t t e n t h a l 博士在文献 3 中讨论了线性正形置换的生成方法。 设r ( 曲为g f ( 2 ) ”上的正形置换，且不动点为o ，则方程s ( x ) = r o x 可表示为 000 = 0 固 0 x 2 = 2 2 0 z 3 2 句 x n l o x n = z n 而f 0工h + l = z 月+ 反过来，选择 n 砘，物，) 是g f ( 2 ) ”上的线性无关集，选择适当的而，使得 托，奶，一，h ， 南+ l 和 z 2 ，如，乙+ 1 ) 都是g f ( 2 ) ”上的线性无关集，将上面的过程中的第2 行到n + l 行 两两模2 加，这样正好得到2 ”行，这样就构造了一个g f ( 2 ) 一上的正形置换。 在上面的构造方法中，选择h + 1 时，使用一个线性方程翰+ 1 = 八z h x 2 ，奶，h ) 如果 要构造一个最大线性正形置换，则该方程应该为一个g h 2 ) ”上的m 序列的极小生成多项 式，它是n 次本原多项式。关于最大线性正形置换的构造，有如下所述的代数构造方法 设一，l ，将g f ( 2 ) ”看作是一个有限域，记为凡一，并记f ；。为该域的乘法群，则由有 限域的知识知道，e 。= i l f 墨2 ”一l 其中口为凡”中的一个本原元，一。1 = 1 ，则 第三章正形置换的构造和计数 有n n = o ，1 ，口，矿，舻”2j ，必存在l s 2 ”一2 ，使得e o ，l ，1 + 矿o ，进一步可设 1 + 矿= ，矿g o ，l 】，则r ( 曲= x 为凡”上的线性置换，且s = x + r ( 功= x + 矿= 舻z ， 也就是说，s ( 曲= x + r 仍是f 2 。上的线性置换，即r ( x ) 是一个线性正形置换。因为 月( 一) = “，1 ，2 一一l ，所以r 有最长的圈结构，即r 0 ) 是最大线性置换。 综上所述，就得到了最大线性置换的一种构造方法： 任意选取a 为凡一中的一个本原元，选取正整数s 满足o s 月l 。当n l ls 月2 时，我们约定 0 1 ) = o ，并定义，1 0 1 ) of 2 0 2 ) 如下： 0 1 ) o 凡( ) = 1 0 1 ) o 正l ( 工2 ) 2 ( 工1 ) o 五2 ( 托) ，正。l 扛1 ) o 正。( 托) ，正r l + j ) 2 ) ，一正一2 ( 娩) ) = ( ，i i ( z 1 ) o 压l ( 娩) ， 2 0 1 ) o 正2 ( 托) ，一， 。( 工1 ) o 正。，( 上2 ) ， 啦“1 ) o 五n ：( 啦) ) 是g f ( 2 ) 州扣2 上 的函数。在下面的定理中与此相同。 定理3 3 设，l ( x 1 ) = 】0 】) ， 2 ( 。1 ) ，五m ( x 1 ) ) ，几0 2 ) = ( 正l ( 2 ) ，正2 幢) ，正。：) ) ， r ( x ，) = 1 ) ，工2 ( x ，) ，一，厶，( ) ) 分别是g f ( 2 ) ，g f ( 2 ) ”，g f ( 2 ) “，上的布尔置换，其中 蜥g f ( 2 ) “，ls f s j 设一= ( “) 为g f ( 2 ) 上的s 阶可逆矩阵，且满足：u 1 ，ss 当 ，7 j 唧时，叼= o ，1 f 5 ，则有f o i ，匏，j 。) = ( f l ( 1 ) ，f 2 ) ，b ) m 为g f ( 2 ) 7 上的 布尔置换，= n l + ”2 + 协 由这个定理，我们可以得到任意高阶的布尔置换，同时也得到大量的多元平衡函数。 然而，定理中的方法并不能推广来构造正形置换，将定理中的布尔置换换成正行置换， 所得的结论是错误的。 正形置换的一种等价的定义是： 定义3 3 设，( x ) = 昕( 功，正( 曲，五) 为g f ( 2 ，上的布尔置换，若满足，o ( z ) = ( ( x ) o 札五( x ) o x 2 ，五( x ) o z 。) 也是g f ( 2 y 上的布尔置换，则称f ( 对为g f ( 2 r 上的正形 置换。 下面我们探讨一种用低阶的正形置换构造高阶的正形置换的方法。 定理3 4 设 1 ) = 饥l p l ) ， 2o ，1 ) ， 。，0 1 ) ) ，r ) = l 魄) ，正2 ) ，厶：c v 2 ) ) ， r 饥) = 坼1 钒) ，五2 慨) ，厶，帆) ) 分别是g f ( 2 ) ，g f ( 2 ) ”，g f ( 2 ) “上的正形置换，其中 n g f ( 2 ) m ，1 f 只令，= ”1 + 2 + + j 设爿为g ，( 2 ) 上的，阶方阵，且满足： 4 ： e ，4 1 2 0 e ”2 oo o0 4 l b 1 1爿1 5 4 2 0 1 ) 一2 s e n 。一i m s _ i s o e n 。 其中e “为”，阶单位矩阵，l f 兰s i 一止为任意的阶矩阵， 1 ，s l ，j + ls 女5 1 6 第三章正形置换的构造和计数 则有f 0 1 ，姐，- ，儿) = 4 l ( y 1 ) ， 2o j l ) ， 工2 帆) ，厶：帆) ) 7 为g ，( 2 ) 7 上的正形置换， ， n 。0 1 ) ，正1 2 ) ，正2 ( 心) ，一，正。：o ) 一，五1 0 0 ) 这里“r ”表示转置。 证明：不妨把f l ，- v 2 ，乃) 简记为4 ( f 1 1 ) ，几魄) ，只帆) ) 7 ，设局= 叫，以，止) 噩= 研，蛭，j ) g f ( 2 ) 7 ，有f ) = f 0 砭) ，则由矩阵爿的结构，必须有：， 足以) ，：一1 0 0 1 ) o 彳。一】h r 0 0 ) 7 b 睇) ，( ) 只一l 以一1 ) 。爿。一l h 凡醒) 7 ，( + + ) 因为r 是置换，故由( + ) 式得y ! = 一，于是由( ”) 式有只一1 ( y ：一) = r l o 一，) ，而凡一l 是置 换，故y ：一l = 一】；同理可得：y ：一2 = 一一，y 1 - 砖，即丑= 施，这样我们证明了f 为单 射，从而，为g f ( 2 ) 7 上的置换。同理可证f o ，为g f ( 2 ) 7 上的正形置换证毕。 在上述定理中，若f l ( y 1 ) ，而魄) ，凡饥) 都是线性正形置换，则构造出来的正形置 换也是线性正形置换。若其中有一个是非线性正形置换，则所得的正形置换就是非线性 正形置换。利用构造出来的高阶正形置换，来继续构造更高阶的正形置换，可以使得定 理中的爿不至于太大。 更进一步，我们有如下定理： 定理3 5 设f 1 0 1 ) = ( ，i 1 0 ，1 ) ， 2 1 ) ， 。( ) j 1 ) ) ，凡o j 2 ) = l o ，2 ) ，五2 0 ，2 ) ，正。o ，2 ) ) ， 帆) = 仉1 帆) ，正2 慨) ，厶。帆) ) 分别是g f ( 2 ) ，g f ( 2 ) ”，g ，( 2 ) “上的正形置换，其中 y i g f ( 2 ) m ，1 f 蔓j ，令，= n l + ”2 + + 马( 0 i ，坛，矗加) 是关于乃+ 1 + 2 ，y 。的 任意的多输出布尔函数， l ，s 一1 ，嘞为任意的 。维行向量，则有f 0 1 妮，儿) = ( ( v 1 ) ，2 魄) ，b 帆) ) o ( 凰，如，凤“) 为g f ( 2 ) 7 上的正形置换。 本定理证明类似定理3 4 ，证明过程省略 因为g f ( 2 ) 上的m 元布尔函数的个数为2 2 卅个，故由定理35 可以构造出g 以2 ) 7 上的 正形置换的个数至少为 f il o r i 2 ”1 。2 鬯+ + + 珊+ + 仉一l 。2 船+ 如 挑选合适的低阶正形置换f l ，n ，b 和布尔函数爿，趣，风一l ，就可以由定理 3 6 构造出满足一定要求的高阶线性正形置换或者非线性正形置换。 3 2 5 小结 一 通过对正形置换的深入研究，我们得到了四种构造正形置换的新方法，利用正形置 换的正形平移，我们可以调整一个正形置换的输出值，而不改变其差分均匀性或者非线 性性；通过一系列的局部改变一个正形置换的输出值的操作，我们可以把一个线性正形 1 7 第三章正形置换的构造和计数 置换变成一个非线性正形置换，或者逐步调整差分均匀度及非线性度，使之满足使用的 要求；也可以简便易行的从一个2 一阶正形置换构造出一个2 * ，阶正形置换；利用低阶的 正形置换，可以构造出任意高阶的线性或者非线性正形置换。 1 8 第四章正形置换的应用 第四章正形置换的应用 正形置换在密码体制中有很好的应用，既可以强化分组密码，也可以用来构造高安 全性的密码函数。正形置换还可以应用在序列密码及前馈网络等密码体制的设计中。如 何把正形置换应用在协曲函数即杂凑算法中，仍然是个值得探讨的问题。 4 1 正形置换与分组密码 一个分组长度为n 的分组密码，本质上体现为g f ( 2 ) ”上的一组置换，因此可以通过 对置换的研究来度量和构造高安全性的分组密码。若干研究表明，精心设计的正形置换 可以作为分组密码的核心单元代换盒( s 盒) 。对于s 盒的设计有许多的设计要求，其中最 基本最重要的要求是抗差分分析和线性分析，因此，研究正性置换的构造及其度量对于 分组密码算法的设计具有重要意义。以往出现的不少分组密码体制虽然有某种满意的对 称结构，但是往往很难用