完全非线性函数的原像分布特征

完全非线性函数的原像分布特征 () 文章编号 :1001 - 2486 200903 - 0132 - 04 Ξ 完全非线性函数的原像分布特征 1 1 ,2 3 强,李超,冯克勤李 ( 1. 国防科技大学 理学院 ,湖南 长沙 410073 ; 2. 东南大学 移动通信国家重点实验室 ,江苏 南京 210096 ; )3. 清华大学 数学科学系 , 北京 100084 摘 要 :完全非线性函数在密码设计与 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 中具有十分重要的作用 。利用代数数论的方法 ,研究一般有 限 Abel 群上完全非线性函数的原像分布特征 ,给出了一般有限 Abel 群上完全非线性函数存在的一个必要条 件 ,证明了某些群上不存在完全非线性函数 ,得到了素数域上完全非线性函数的原像分布 。 关键词 :完全非线性函数 ;原像分布 ;理想分解 ;素域 中图分类号 : TN91811 文献标识码 :A Properties of Preimage Distributions of Perfect Nonlinear Functions 1 1 ,2 3L I Qiang,L I Chao,FENG Ke2qin (1 . College of Science , National Univ. of Defense Technology , Changsha 410073 , China ; 2 . State Key Lab of Mobile Communication , Southeast Univ. , Nanjing 210096 , China ; )3 . Department of Mathematical Science , Tsinghua Univ. , Beijing 100084 , China Abstract : Perfect nonlinear functions are widely used in the design and analyses of cryptosystem. Based on the method of algebraic number theory , the properties of preimage distributions of perfect nonlinear functions over finite abelian group are studied. Necessary conditions for the existence of perfect nonlinear functions over finite abelian group are presented , which proves that there are no perfect nonlinear functions for some abelian groups. Finally , the preimage distributions of perfect nonlinear functions over some prime fields are presented. Key words :perfect nonlinear functions ;preimage distributions ;idea factorization ;prime field 1 - 3 高度非线性函数在序列密码 、分组密码 、纠错编码和 Hash 函数的设计与分析中具有重要应用。完全非线性函数是一类重要的高度非线性函数 ,近年来 , 其研究内容集中在新函数的构造和等价分类 、 3 - 4 完全非线性函数在编码密码学中应用等问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。2004 年 , C. Carlet 和 C. Ding 讨论了一般 Abel 群上完 3 全非线性函数的原像分布问题, 给出了完全非线性函数原像分布的不定方程组 。2007 年 , 李超等利 5 用初等数论的技巧 , 研究了从 n 阶 Abel 群到 3 阶 、4 阶 Abel 群的完全非线性函数的原像分布。本文 利用代数数论中素理想分解理论 ,给出完全非线性函数存在的一个必要条件 ,证明了某些特殊群上不存 在完全非线性函数 , 得到了素数域上完全非线性函数的原像分布 。 1 完全非线性函数的原像分布特征 ( ) ( ) 设 A ,?和 B ,?分别是 n 和 m 阶有限 Abel 群 , 为讨论方便 , 群中的运算用乘法 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示。 定义 1 设 f 是从 n 阶 Abel 群 A 到 m 阶 Abel 群 B 的函数 ,令 - 1 ( ) ( ) x ?A : f axf x= bP= max max f 0 ?a ?A b ?Bn 则称 P为函数 f 的非线性度 。f 1 差分密码攻击表明 , P的值越小 ,则函数 f 的非线性度就越高 ,由 P定义可知 P? 。f f f m Ξ 收稿日期 :2008 - 11 - 30() ( ) 基金项目 :国家自然科学基金资助项目60803156;东南大学移动通信国家重点实验室开放基金资助项目W200805 () 作者简介 :李强1979 —,男 ,博士生。 1 定义 2 设 f 是从 n 阶 Abel 群 A 到 m 阶 Abel 群 B 的函数 ,如果 P= ,则称 f 是完全非线性函f m 数。[ 2 ] 引理 1 设 f 是从 n 阶 Abel 群 A 到 m 阶 Abel 群 B 的完全非线性函数 ,则有 m n 。[ 6 ]l 引理 2(ξ ) () 设 K = Q ,其中 m 为正整数 , m ?3 , m ?2 mod 4,则对每个素数 p ,记 m = pm,′其m ξ 中 l ?0 , p Π| m。′则 p 在代数整数环 O = Z []中素理想分解式为K m e )( pO= P PK 1g l f φ( ) φ( ) ) ( 其中 , e = p, g = m′Πf , f 是 p 模 m的阶′ ,满足 p?1 mod m′的最小正整数 f 。 引理 3设 f 是 从 n 阶 Abel 群 A 到 m 阶 Abel 群 B 的 完 全 非 线 性 函 数 , m n , 令 k=b ( ) ( ) ( ) x ?A : f x= b Π b ?B ,则对任意 1 ?d ?B , f 的原像分布 k| b ?B 满足 : b ( ) n n - 1 2= n + kb ?m b ?B n - 1 n ()1 kk= b bd ?m b ?B k=n b ? b ?B( )( )- 1 - 1 - 1 - 1 ( ) ( )证明 令 F = f a= k?b , F= f a′k?b , 则 F 和 F 均为群代数= b b ?????′A a a ?Ab ?Bb ?B ( ) Z B 中的元素 。由于 f 是从 A 到 B 的完全非线性函数 , 故 ( - 1)- 1- 1 ( ) ( ) ( ) ( ) F ?F= f af a′= f af ac ??a , a?′A a , c ?A- 1- 1 ( ) ( ) ( ) ( ) = f af a+f af ac ??a a , c ?A , c ?1A ( ( )) n n - 1 n n n - 1( ) )( = n ?1+ n - 1B =n + ?1 + B - 1 B B B m m m ()2 ( ) b ? Z B 。另一方面 , 其中 ,1和 1分别为 A 和 B 中的单位元 , B =A B ? b ?B ( - 1)- 12 = k k bb′= k ?1 +k k ?dF ?Fb B b bd b b′ ???b , b?′B b ?Bb , d ?B , d ?1B 2 ( ) ()= k?1 +k k ?d3 b B b bd ??? b ?B1 ?d ?B b ?B () () 比较式 2,有 和式 3 ( ) n n - 1 2 k= n +b ?m b ?B ( ) n n - 1 kk= b bd ?m b ?B 又显然有 k= n ,因此引理得证 。b ? b ?B( )( ) vn vn+ 1 p p ( ) 定理 1 记 vnp 在正整数 n 的分解式中的阶数 , 即 p Π n 。f 是从 n |为素因子 n , 但 pp ( ) 阶 Abel 群 A 到 m 阶 Abel 群 B 的完全非线性函数 ,这里 m n ,若 p 为 n 的素因子 ,并且 vn, 为奇数 p ξ则 pO 在整环 Z []中具有如下分解形式 : K m l )( pO = VV ?K ^ ^ χ( )χ 证明 用 B 表示群 B 的特征群 , 由于 B 是 m 阶 Abel 群 , 故对每一个 ?B 和每一个 b ?B ,b ^ i ( ) ξ( )χχ α为 m 次单位根 , 即 b= 。于是对每一个 ?B 和每一个 F = k ?b ? Z B , 记 = χ m b ? B b ? χ( ) F, 则 χ( ) χ( ( ) ) χ( ( ) ) χ( ) ξα = F= f a= f a= kb? Z []χbm ??? a ?Aa ?Ab ?B - 1 - 1 αχ( ) χ( ) χ( ) χ( ) χ( ) () () α 并且= FF= FF = F?F ,由式 2和式 3可知χχ 2 χ n, = 1 αα()4 =χχ χ n , ?1 () ααξχ 当 ?1 ,则由式 4有 n = ,这表示理想 nO 在 Z []中具有共轭的分解形式 nO= UU? ,其中χχ K m K αα( ) ξ U = O , U =?O ,从而若 p 为 n 的素因子 ,并且 vn为奇数 , 则 pO在整环 Z []中具有如下分解χχK K p K m l ) ( 形式 pO = VV?。定理得证 。 K e ξ( 由引理 2 ,得到 pO 在 Z []中的分解式为 pO= P K m K 1) P,而由定理 1 ,当 f 是从 n 阶 Abel 群 Ag l ( ) ( ) 到 m 阶 Abel 群 B 上的完全非线性函数时 ,如果 p n ,并且 vn, 则有 pO = VV?。比较这两 为奇数 p K e ( ) 种分解 ,不难发现 , pO= PP中素理想及其共轭总是成对出现的。根据这一点 ,我们讨论了 mK 1g = 3 ,4 ,5 时 , 不同 n 值条件下完全非线性函数的存在性问题 。表 1 列出了当 n ?200 时 , 不存在从 n 阶 Abel 群到 3 ,4 或 5 阶 Abel 群完全非线性函数的部分 n 值 。 表 1 m = 3 ,4 ,5 , n ?200 时 ,不存在完全非线性函数的 n 的部分取值 Tab. 1 Values of n that when m equals 3 ,4 ,5 , there does not exit any perfect nonlinear functions form abelian group of order n to abelian group of order m m n 3 6 15 24 30 33 51 66 87 102 123 141 159 165 174 177 4 12 24 28 56 76 84 92 96 108 124 152 168 172 184 188 5 10 15 30 35 40 65 70 85 105 115 130 135 160 170 185 2 素数域上完全非线性函数的原像分布 l 下面考虑当 p 为奇素数 , n = p时 ,设 f 是从 n 阶 Abel 群 A 到 p 阶 Abel 群 B 的完全非线性函数 ,则 ^ l χ () αχ ααξξξα 对任意的 ?B ,?1 ,由式 4可知= n = p,其中,?Z [] , O= Z [] , K = Q [] 。由引χχ χ χ p k p p p - 1 ξΡ 理 2 可知 , pO 在 Z []中分解为 pO = 。K p K lαα χ χ ( ) p - 1 2 (α) ( ) ξ() 当 l 为偶数时 ,有 O= P,于是可知 O= 1,即 为 Z [] 中的代数整数 ,且其所χK K p lΠ2 lΠ2 p p αα χ χ λ (ξξλ) 有共轭元的绝对值为 1 ,于是 为的共轭 ,即 = ?0 ??p - 1,所以当 l 为偶数时 ,有p p lΠ2 lΠ2 p p λlΠ2 ξα ()λ = ?p 5 , 0 ??p - 1χ p l( ) p - 1 s 3 2 (α) ) ( = p 当 l 为奇数时 ,令 l = 2 s + 1 ,则 O= Pp O,其中χK K p , p ?1 mod 43 p = p ?3 mod 4 i p , 又 p - 1 p , p ?1 mod 4x x( )ξ = p ?p p ?3 mod 4 x = 1 i p , p - 1 x 3x ( )ξ p因此= ,于是 p ?p x = 1 p - 1 l - 1 x λ x 2λ ()α ( )ξ ξ 6 , = ?p 0 ?? p - 1χp p ?p x = 1 l 现在讨论素数域上的情形。假设 g 是从 F到其自身的完全非线性函数 , p 为奇素数 , q = p ,q l - 1 p p 3 ( ) ( ( ) ) ( ) ( ) x 为 F到 F上的迹函数 。对任意 a ?F, f x Tr ag x + Tr x= Trx= x + x + = 是F ΠF q p q q p 从 F到 F的完全非线性函数 。我们确定函数 f 的原像分布。q p l ( ) ( ( ) ) 定理 2 设 g 是从 F到其自身的完全非线性函数 , q = p ,则完全非线性函数 f x= Tr ag x 的q ( ) k: , 原像分布 k, k, k,由下式确定 0 1 2 p - 1 l l l - 1 - 1 2 2 δ 当 2| l 时 ,0 ?b ?p - 1p p ?p ,i λ, b k= l - 1 b l - 1 当 2 |Π l 时 ,0 ?b ?p - 1 2 p ?p k′, b - λ λ 0 , 当 b ?b δ( ) k′= ,为二次特征 。 , 其中 ,=λb , b p λ1 , 当 b = 2 l p - 1 p - 1 p - 1 χ = 1 p , b l () αα α由式 4,= ,且= χ( )= ξ 证明可知 kb k, k= q = p ,再由式χχ χ bbp b l ???χ ?1 b = 0 b = 0 b = 0 p , () () χ 5和式 6可知 ,当 ?1 时 ,得λ lΠ2 ξλ ?p,0 ?? p - 1 ,2 |l p p - 1 α =l - 1χ x λ x 2( )ξξλ ?p , l 0 ?? p - 1 ,2 |Πp p ?p x = 1 p - 1 ^ b ξχ χ 由于 k总是正整数 ,且 = 0 ,因此 ,对任意?B ,?1 ,我们可以选取一个足够大的正整数 N ,使b p ?b = 0 得λ2 p - 1 lΠ2 ξ(ξξξ ) λ ?p+ N 1 + + + , 0 ?? p - 1 ,2 |l p p p p p - 1 α ()= 7 χl - 1 x λ x 2p - 1 2( )ξξ(ξ ξλ ξ) + N 1 + + + , |Π 1 ,2 ?p 0 ?? p -p p p p p l ?p x = 1 λ p - 1 lΠ2 () αξ ) χ ξα(ξ 现在来确定 N 的值 ,当 = 1 ,2 |l 时由式 7知 ,= ?p+ N 1 + + + ,又=1 p p p 1 l p - 1 p - 1 p - 1 2 λN ?p , i = b l l Π2 )ξ( ( ) k?1 bk,于是有 k = ,所以有 k== p - 1N + N ?p= p ,即b bpii ??? λN , i ?b = 0 b = 0 i = 0 l - 1 l l - 1- 1 = p,于是 2 p N = i p ,同样当 2 Π| l ,可知 N l λ 2 p - 1 lΠ2l - 1 - 12 ξ λ ) (ξξξ) ( 0 ?? p - 1 ,2 |?p+ p i p 1 + + + , l p p p p p - 1 α()8 =χ l - 1 x λ x l - 1 2 p - 1 2 ( ( )ξ)ξ(ξ ξξ ) λ ?p + p1 + + + ,0 ?? p - 1 , 2 |Πl p p p p p ?p x = 1 l l - 1 l l - 1 - 1 l - 1 2 2 2 δ(() ) 即当 2| l 时 ,有 k= p p ?p 0 ?b ?p - 1;当 2 Π| l 时 ,有 k= p ?p k′0 ?b ?p - 1,i λλ b , b b b - i ) ( 其中 , k′= ,定理得证 。i p 参 考 文 献 : () 1 Biham E , Shair A. Differential Cryptanalysis of DES2like CryptosystemsJ . J . Cryptology , 1991 , 4 1: 3 - 721 . Matsui M. Linear Cryptanalysis Method for DES Cipher C ΠΠAdvances in Cryptology2EUROCRYT’93 Proceedings , Berlin : Springer2verlag , 1994 : 2 386 - 397 . Carlet C , Ding C. Highly Nonlinear MappingsJ . Journal of Complexity , 2004 ,20 : 205 - 244 . 3 Carlet C , Ding C , Yuan J . Linear Codes form Perfect Nonlinear Mappings and Their Secret Sharing Schemes J . IEEE Trans. Inform. Theory , 4 () 2005 , 51 6: 2089 - 2102 . Li C , Li Q , Ling S. Properties and Applications of Preimage Distributions of Perfect Nonlinear Functions J . IEEE Trans on. Inform. Theory , 5 () 2009 , 55 1: 64 - 69 . 冯克勤. 代数数论M. 北京 :科学出版社 ,2000 . 6