布尔函数在现代密码学中的应用毕业论文(编辑修改稿)

布尔函数在现代密码学中的应用毕业论文(编辑修改稿)内容摘要：

密方式和实现形式的不同，我们将密码体制分为流密码和分组密码。 分组密码 分组密码则是将明文消息序列 12, ,..., ,...km m m 分成等长的消息组 （ 12, ,..., nm m m ）， 12( ,..., ),...nnmm 在密钥控制下按固定的算法 kE 一组组进行加密。 加密后输出的等长密文组 1 1 2( , ... , ) , ( , ... , ) , ...m m ny y y y 序列密码 序列密码也称为流密码（ Stream Cipher） [9]， 具有实现简单、加解密速度快、几乎没用 错误传播 的 特点， 所以其 在专用或机密机构中 有很大的 优势， 其 应用领域 主要 包括无线通信、外交通信。 只有一次一密的 密码体制 是 不可能被破译的，这一结论于 1949 年 已被香农（ Shannon）证明 ，这 极大的支持了流密码的研究 ，序列密码方案 的研究过程便 是 对 一次一密系统的尝试，或者说 “一次一密 ”的密码只 是序列密码的 入门。 如果序列密码所使用的 密钥并非伪 随机方式 产生 的、 并 与消息流长度相同， 那么 此时的序列密码 即 一次一密的 密码体制。 若 我们能产生某种 随机 序列（ 密钥 流） ，其 由密钥 来 确定， 那么 用这样的序列 则 可进行加密， 也就是 将密钥、明文表示成二进制，对应地进行加密 ,加解密时一次 性 处理明文中的 若干个 比特。 分组密码和序列密码是实现密码体制的两种基本方式，要实现密码体制，不可缺少的一个重要工具就是布尔函数（亦即该课题要研究的重点）。 布尔函数在序列密码中的地位显得极为特殊而且重要。 所以密码学研究的始终，一直伴随着对布尔函数的研究。 布尔函数的基本知识 布尔函数的定义 定义 [10] 设 1x ， 2x 是布尔代数中的任意数，则有 1x  2x  121 , , 10, xx 当 同 时 为 时其 他 天津科技大学 2020 届本科生毕业论文 6 1x  2x  120 , , 01, xx 当 同 时 为 时其 他 若用“  ”、“  ”表示 2F 上的加、乘运算； 1,0 看做 2F 上的元素，则有 1x  2x  1x  2x 1x  2x  1x  2x  1x  2x 1x  1x  1 因此布尔代数中的运算可用 2F 上的函数来表示。 在本文中，我们用 nF2 表示在有限域 2F = }1,0{ 上的所有 n 元组中的集合的元素。 然后，一个 n 元布尔函数被定义为一个从 nF2 到 2F 的映射。 所有 n 元布尔函数的集合表示为 nB。 自然地，我们将 2F 上的函数称作布尔函数。 一般地我们定义如下映射： )(xf ： nF2  2F 为 n 元布尔函数，其中 2F 为二元域， nF2 为 2F 的 n 元向量空间， x nF2 ，记为 f。 为了方便，我们用普通加、乘记号分别表示 2F 上的“  ”、“  ”。 如 1x  2x 记为21 xx ， 1x  2x 记为 21xx ；但有时仍用 1x 记 1x  1。 布尔函数的表示 为方便布尔函数的研究和应用，不同情况下将采用不同的表达方式。 本节将简要介绍几种布尔函数的表示方法。 真值表 定义 任何 n 元布尔函数可以被表示为一个 n2 长度的二进制向量，这就是所谓的真值表： ))11,1()0,0,1()0,0,0(( ，，，  ffff , （ 221） 也称为 )(xf 的函数值向量，记为 f [4]。 1在真值表中的个数称被为 f 的汉明重量，记为 ()wf 或 fw ，如果它的真值表有相等数目的 1和 0，我们说 f 是平衡的，这意味着若， ()wf = 12n ，此时则称 )(xf 为平衡布尔函数。 小项表示 定义 对任意给定的 ix ， ic  2F ，约定 1ix ix ， ii xx 0 于是   时，当 时，当iiiici cx cxx i 01 设 ),...,( 1 nccc ， ),...( 1 nxxx 则有 ncc xxx ...21 21   nnnn ccxx ccxx ...)...(,0 ...)...(,11111当当 （ 222） 天津科技大学 2020 届本科生毕业论文 7 为简便，今后亦记 ncc xxx ...21 21 cx 于是 )(xf 120 )(nicxxf （ 223） 称为 )(xf 的小项表示 [10]。 小项表示其实就是布尔代数表达式，亦即逻辑表达式[10]。 多项式表示 我们知道线性空间 nF2 是同构的有限域 nF2 ，那么在 210()n iiif x a x中，任意 n元布尔函数 nBf 都可以唯一 表示为二元域 2F 上的一个单变量多项式 [11]： ......)( 2112110  xxxxxf nn   ,...... 21,...2,111 nnnn xxxxxa   nnjjk jjjjk kk xxaaa .. .1,10 1 11 . . .. . . （ 224） 其中， 0a ， i ， 212 Fan  ， 22 )( ii aa  nF2 ， 221  ni。 这就是所谓的代数范式（ ANF）。 )( xf 的代数次数记为 )(fdef ，它是具有非零系数的最高阶项的变量的个数。 若 0)( xf ，则定义 0)( fdef ；若 1)( fdef ，则称 )(xf 为仿射函数；当 00a 时，仿射函数被称为线性函数；若 2)( fdef ，则称 )(xf 为非线性函数 [11]。 Walsh 谱表示 设 1( ,..., )nx x x ， 1( ,..., )nw w w 2nF ， x 与 w 的点积定义为 xw 11 ... nnx w x w   2F 则 n 元布尔函数 ()fx的 Walsh 变换定义为 210( ) 2 ( 1 ) ( )nn w xf xS w f x （ 225） 其逆变换为 210( ) ( )( 1)n wxfxf x S w （ 226） )(wSf （ w nF2 ）称为 )(xf 的 Walsh 谱。 此式亦即 )(xf 的 Walsh 谱表示。 因为 Walsh 变换可逆，因而布尔函数的 Walsh 谱唯一。 迹函数 在有限域上的布尔函数的迹函数 22: FFtr n  表示为 天津科技大学 2020 届本科生毕业论文 8 1 20()tnttr x x （ 227） 迹函数在 2F 上是线性的。 矩阵表示 定义 设 )(xf 是一个 n 元布尔函数， nFx 2。 若 1)( xf ，则称 x 为 )(xf的一个特征向量，记 )(xf 的全体特征向量的集合为 D ， }.1)(|{ 2nFaafaD  wD 将 D 中的 w 个向量按字典顺序从大到小排列，记第 i 个向量 iw ， wi1 ，则称0,1 矩阵 wnwwnnccccccccc.....................212222111211 为 )(xf 的特征矩阵，记为 fC ，或简记为 C [11]。 由于布尔函数的特征矩阵具有唯一性，因而可以将布尔函数的某些问题转化为矩阵问题加以研究。 布尔函数也可以通过投影空间的特征函数和状态 图等表示。 布尔函数的研究方法 布尔函数有不同的表示方法 [10]，而不同的表示方法在不同的研究中有其各自的优势，所以我们要根据不同的表示方法采用不同的研究方法，以便更好地展开研究，目前主流的研究方法有以下几种。 代数分析方法 任何可以表示为多项式形式的函数都可以使用代数方法进行分析，显然，布尔函数也不例外。 从代数的角度，分析布尔函数主要采用多项式表示和小项表示。 频谱方法 频谱分析作为研究布尔函数的一个重要工具，通过其可以分析布尔函数的谱特性。 矩阵方法 布尔函数最直观的表示方法就是矩阵表示，在定序意义下，重量为 w 的 n 元布尔函数之集和 2F 上 nw )21( nw 矩阵之间是一一 对应的。 重量分析方法 对任意两个布尔函数 ),...,()( 1 nxxfxf  和 ),...,()( 1 nxxgxg  ，定义 )(xf 和天津科技大学 2020 届本科生毕业论文 9 )(xg 的距离为 )( gfw  记为 ),( gfd ，即 ),( gfd  )( gfw  对和函数的重量有如下关系式： )( gfw   )(fw  )(gw )(2 fgw （ 231） 重量分析方法是通过分析布尔函数的重量特征来研究布尔函数的方法，这种方法简单易懂，很适合工程应用。 以上研究方法因为其特点不同 ，适用于不同的研究场景和领域。 天津科技大学 2020 届本科生毕业论文 10 3 布尔函数的密码学性质 布尔函数在不同领域有着不同的应用，因而衍生出了不同的函数类。 人们对不同种类的布尔函数的研究归结为对布尔函数某种性质的研究。 本章着重介绍布尔函数的一些重要性质。 布尔函数的 Walsh 变换及其性质 两种 Walsh 变换 在 节中已经介绍过布尔函数的 Walsh 谱表示和 Walsh 变换对研究布尔函数的重要性。 本节首先讨论 Walsh 变换及其性质。 如无特别声明， )(xf 均指 n元布尔函数。 已知 210( ) ( )( 1)n wxfxf x S w 若记 ( ) ( 1)wxwQx （ 311） 则当 w 取遍 nF2 （或 120  nw ）时，就得到一个函数系 [11]： )(xQw ， w  nF2 （ 312） 此函数系是一个正交函数系，即满足 )(xQu )(xQv   vu vun,0 ,2 该函数系（ 311）称为 Walsh 函数系。 显然，对给定的 x ， w ，有 )(xQw  )(wQx。 210( ) ( )( 1)n wxfxf x S w可以看作 )(xf 在 Walsh 函数系下的展开式。 )(wSf 是展开式的系数，即 Walsh 谱。 )(xf 还有另外一种展开式： )(xf  )()(2121 120 )( xQwS ww fn （ 313） 其中 )()1(21)( 12 0 )()( xQwS ww xfnf n  （ 314） 为了区别，将 )(wSf 称为 )(xf 的第一种 Walsh 谱或线性谱，而将 )()( wSf 称为 )(xf天津科技大学 2020 届本科生毕业论文 11 的第二种 Walsh 谱或循环谱。 定理 )(wSf 与 )()( wSf 的关系如下： )()( wSf    0),(21 0),(2 wxS wwSff （ 315） Walsh 变换的性质 Walsh 变换有如下性质： 性质 1（平稳性） 若 )(xf 在 w 的谱值为 )(wSf ，则 )( axf  在 w 的谱值为 )(),( wSawQ f （ 316） 性质 2（线性姓） 若 )(xf 在 w 的谱值为 )(wSf ， 若 )(xg 在 w 的谱值为 )(wSg ，则 )()( xbgxaf  在 w 的谱值为 )()( wbSwaS gf  （ 317） 性质 3（ Plancheral 公式） )(2)0()(12 0 2 fwSxS nfw fn   （ 318） 此性质又称为初值定理。 性质 4（ Parseval 公式） 1)(12 0 )(2  xSnw f （ 319） 此即能量守恒定理。 布尔函数的线性性 定义 如果 ),...,( 1 nxxf  )),...,(,...,( 11 nbnbn xxlxxg  则称 n 元布尔函数是部分线性的，其中    n bni iinbn xcxxl 11 ), . . . ,( ； 1,2  bFc ni。 定义 设 )(xf 是 n 元布尔函数， nFa 2 ，称 a 为 )(xf 的一个线性结构，则对任意 nFx 2 ， )()( xfaxf  为常数。 若 0)()(  xfaxf ，称 a 为 ()fx的不变线性结构。 若 1)()(  xfaxf ，称 a 为 ()fx的恒变线性结构。 记 E {全体线性结构 }，则 E 是 nF2 的一个线性子空间，若该子空间的维数为正，即 0Dim ，则称 )(xf 是一个线性结构函数 [10]。 天津科技大学 2020 届本科生毕业论文 12 记 }0)()(|{0  xfaxfEaE }1)()(|{1  xfaxfEaE 则有如下性质： ① 10 EE  , 10 EEE  ； ② 00,0 EE 是 E 的子空间； ③ 若 1E ，则 101 , EaEaE  ； ④ 设 rE 20  ，若 1E ，则 rE 21  ， 12 rE。 若 12  qE ，则称 q 为 )(xf 的线性结构维数，此时有如下两种情况： ① 110 2||||  qEE ； ② ,20 qE  01E ，即 1E 为空集。 设 )(xf 是线性结构函数，若 }0{0E ，则称 )(xf 为 I 型线性结构函数；若}0{0E ，这时必有 11E ，则称 )(xf 是一个 II 型线性结构函数。 定义 设 )(xf ),...,( 1 nxxf ，若 ix 的取值不影响 )(xf 的取值，则称 )(xf与 ix 无关。 该性质称为与变元无关性，最初称 与变元无关性为退化，定义如下： 定义 设 )(xf ),...,( 1 nxxf ，若存在 nF2上的 kn )( nk 矩阵 D ,使得 ),...,()(),...,( 11 kn yygxDgxx。