有限域2n上一類冪函數(shù)的差分譜及應(yīng)用

滿玉瑩，夏永波(中南民族大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院，武漢 430074)

眾所周知，密碼學(xué)因其廣泛的應(yīng)用而備受關(guān)注. 密碼函數(shù)是構(gòu)成分組密碼、序列密碼和Hash函數(shù)等對(duì)稱密碼算法的重要組件，其密碼學(xué)性質(zhì)的好壞對(duì)該密碼算法的安全性有著至關(guān)重要的影響，并且密碼函數(shù)在通信和編碼領(lǐng)域中也有著廣泛的應(yīng)用[1]. 近年來(lái)，如何設(shè)計(jì)S-盒來(lái)有效抵抗線性攻擊和差分攻擊是研究的熱點(diǎn). 差分一致性可以用來(lái)衡量密碼函數(shù)抵抗差分攻擊的能力，一個(gè)密碼函數(shù)的差分一致性越小，其抵抗差分攻擊的能力就越強(qiáng)[2-3]. 對(duì)于密碼函數(shù)差分性質(zhì)的研究，其中的一個(gè)課題就是計(jì)算密碼函數(shù)的差分譜，差分譜從取值頻次上對(duì)密碼函數(shù)的差分分布表進(jìn)行了刻畫，在差分分析中可為尋找差分攻擊路徑提供依據(jù). 由于具有較低差分一致性的冪函數(shù)在硬件實(shí)現(xiàn)方面更為便利，所以其通常被用于S-盒的設(shè)計(jì)中. 例如美國(guó)高級(jí)加密標(biāo)準(zhǔn)(AES)就是使用有限域28上差分一致性為4的Inverse函數(shù)x|→x-1來(lái)設(shè)計(jì)的[4]. 對(duì)于冪函數(shù)往往通過確定其差分譜來(lái)進(jìn)一步刻畫它的差分性質(zhì). 因此確定具有較低差分一致性冪函數(shù)的差分譜受到了國(guó)內(nèi)外密碼學(xué)者廣泛的關(guān)注.

設(shè)n=4k，對(duì)于有限域2n上的冪函數(shù)F(x)=x22k+2k+1(該函數(shù)被稱為Bracken-Leander冪函數(shù))，因?yàn)槠渚哂休^低的差分一致性和較高的非線性度，所以其受到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注. 2010年，BRACKEN和LEANDER首次在文獻(xiàn)[5]中研究了F(x)的Walsh譜和差分一致性，證明了無(wú)論k是奇數(shù)還是偶數(shù)，F(xiàn)(x)都是4差分置換，并且分別得到了k是奇數(shù)和偶數(shù)時(shí)F(x)的Walsh譜. 對(duì)于F(x)差分譜的計(jì)算，BLONDEAU等人在文獻(xiàn)[3]中利用平方和指標(biāo)函數(shù)得到了F(x)的差分譜，但是該方法只適用于k為奇數(shù)的情況. 隨后在2017年，XIONG、YAN在文獻(xiàn)[6]中通過研究差分方程(x+1)22k+2k+1+x22k+2k+1=b的解數(shù)直接確定了F(x)的差分譜，他們的方法同時(shí)適用于偶數(shù)k和奇數(shù)k.

本文將提供一種新的方法求解F(x)的差分譜：利用BRACKEN和LEANDER在文獻(xiàn)[5]中給出的該函數(shù)的Walsh譜，基于文獻(xiàn)[7]中提出的差分譜和Walsh變換之間的關(guān)系確定了F(x)的差分譜. 該方法相比于文獻(xiàn)[6]中所用方法更為簡(jiǎn)單. 利用F(x)的差分譜，確定F(x)的兩個(gè)密碼學(xué)指標(biāo)ambiguity和deficiency的取值. 此外對(duì)于Kassami冪函數(shù)也計(jì)算了它的ambiguity和deficiency.

1 基礎(chǔ)知識(shí)

設(shè)p為任意素?cái)?shù)，n為正整數(shù)，pn是含有pn個(gè)元素的有限域并且pn{0}· 下面給出本文所需的基本概念·

定義1[3]設(shè)F(x)是從pn到pn的一個(gè)函數(shù)，則F(x)在(a,b)∈pn×pn處的Walsh變換定義為：

F(x)的Walsh譜定義為多重集ΛF={WF(a,b):a,b∈pn,a≠0}·

定義2[8]設(shè)F(x)為有限域pn到自身的映射，對(duì)于任意pn，定義差分方程ΔaF(x)=F(x+a)-F(x),δF(a,b)為ΔaF(x)=b在pn上解的個(gè)數(shù)，即：

δF(a,b)=|{x∈pn|ΔaF(x)=b}|,

其中|S|表示集合S的基數(shù)· 稱矩陣(δF(a,b))a,b∈pn為F(x)的差分分布表· 令：

F(x)的差分一致性定義為δ(F)·

設(shè)F(x)為有限域pn到自身的映射，若δ(F)=k則稱F(x)為k-差分一致性函數(shù)· 特別地，若δ(F)=1，則稱函數(shù)為完全非線性函數(shù)(PN函數(shù))，若δ(F)=2，則稱函數(shù)為幾乎完全非線性函數(shù)(APN函數(shù))· 對(duì)于特征為2的有限域，函數(shù)的差分一致性最低只能達(dá)到2，這是因?yàn)槿魓0滿足方程F(x+a)-F(x)=b則有x0+a也一定滿足該方程·

下面沿用定義2中的記號(hào)給出密碼函數(shù)差分譜的定義，密碼函數(shù)的差分譜是對(duì)其差分性質(zhì)更精細(xì)的一種刻畫·

定義3[9]設(shè)F(x)為pn到自身的映射，若F(x)的差分均勻度為k，則為F(x)的差分譜，其中：

由此得δF(a,b)=δF(1,b/ad)· 也就是說(shuō)冪函數(shù)F(x)的差分譜完全由δF(1,b)的值確定出來(lái)，其中b遍歷pn· 令：

ωi=|{b∈pn|δF(1,b)=i}|,0≤i≤k,

為了描述F(x)的差分函數(shù)ΔaF(x)=F(x+a)-F(x)的單射性和滿射性，PANARIO等人在文獻(xiàn)[10]中提出了兩個(gè)新的密碼學(xué)指標(biāo)：ambiguity和deficiency. 利用定義3中密碼函數(shù)差分譜的定義，下面給出ambiguity和deficiency的定義·

定義4[10]設(shè)F(x)為pn到自身的映射，F(xiàn)(x)的ambiguity定義為的deficiency定義為

A(F)是衡量F(x)的差分函數(shù)ΔaF(x)的單射性，并且F(x)的ambiguity越低，F(xiàn)(x)的差分函數(shù)ΔaF(x)越接近單射·D(F)是衡量F(x)的差分函數(shù)ΔaF(x)的滿射性，并且F(x)的deficiency越低，F(xiàn)(x)的差分函數(shù)ΔaF(x)越接近滿射·

若F(x)=xd是有限域2n(n≥2)上的一個(gè)4差分一致性函數(shù)，則對(duì)于A(F)和D(f)的界有如下引理·

引理1[11]設(shè)F(x)=xd是有限域2n(n≥2)上的一個(gè)4差分一致性函數(shù)，則有：

(2n-1)(2n-1+4)≤A(F)≤3·2n-1(2n-1),

(2n-1)(2n-1+1)≤D(F)≤3·2n-2(2n-1)·

設(shè)F(x)是從pn到pn的一個(gè)k-差分一致性冪函數(shù)，{ω0,ω1,…，ωk}為其差分譜，則冪函數(shù)F(x)有如下性質(zhì)·

下面給出后續(xù)證明中用到的重要引理·

引理2[5]設(shè)函數(shù)F(x)=x22k+2k+1是定義在有限域2n上的一類冪函數(shù)，其中n=4k.則F(x)的Walsh譜由如表1和表2給出·

表1 當(dāng)k為偶數(shù)時(shí)F(x)的Walsh譜Tab.1 The Walsh spectrum of F(x) when k is even

表2 當(dāng)k為奇數(shù)時(shí)F(x)的Walsh譜Tab.2 The Walsh spectrum of F(x) when k is odd

(1)當(dāng)k為偶數(shù)時(shí)

(2)當(dāng)k為奇數(shù)時(shí)

對(duì)于冪函數(shù)F(x)=xd，文獻(xiàn)[7]中給出了F(x)的Walsh譜和定義2中δF(a,b)之間的關(guān)系，借助這一關(guān)系，可以建立Walsh譜和差分譜之間的如下關(guān)系·

引理3 設(shè)F(x)=xd是pn到pn的一個(gè)k-差分一致性冪函數(shù)，{ω0,ω1,…,ωk}為其差分譜，WF(a,b)為F(x)在(a,b)∈pn×pn處的Walsh變換，則有：

證明由

的解· 設(shè)u=-x1+x2=x3-x4則有x2=x1+u和x3=x4+u.因此有：

2 主要結(jié)果及證明

定理1 設(shè)F(x)=x22k+2k+1是有限域2n上的冪函數(shù)，其中n=4k，則F(x)為4差分一致性函數(shù)且差分譜為：

{ω0=5·24k-3-23k-3,ω1=0,ω2=24k-2+23k-2,ω3=0,ω4=24k-3-23k-3}·

證明對(duì)于有限域2n上的Bracken-Leander冪函數(shù)，BRACKEN和LEANDER在文獻(xiàn)[5]中證明了F(x)為4差分一致性函數(shù)，設(shè)該函數(shù)的差分譜為{ω0,ω1,ω2,ω3,ω4}· 因?yàn)镕(x)的差分方程(x+1)22k+2k+1+x22k+2k+1=b的解是成對(duì)出現(xiàn)的，所以有ω1=ω3=0，下面只需求得ω0,ω2,ω4的值·

由Walsh變換的定義知當(dāng)a=0時(shí)容易得出:

當(dāng)k為奇數(shù)時(shí)可得:

進(jìn)一步由引理3知:

24n+22n(2n-1)(4ω2+16ω4),

STEM教育與STEM職業(yè)的聯(lián)系 教育的目的是為社會(huì)建設(shè)培養(yǎng)專業(yè)人才，對(duì)接社會(huì)的現(xiàn)代化發(fā)展。STEM教育理工科屬性很強(qiáng)，從事社會(huì)建設(shè)的科技產(chǎn)業(yè)建設(shè)者需要具有此類的設(shè)計(jì)性思維，對(duì)于社會(huì)的科技產(chǎn)業(yè)具有很強(qiáng)的帶動(dòng)作用。

由此可得到F(x)的差分譜并且當(dāng)k為偶數(shù)和k為奇數(shù)時(shí)F(x)的差分譜相同·

下面給出利用Magma軟件計(jì)算實(shí)例所得到的結(jié)果·

例1 取k=2,n=8· 利用Magma軟件，得到F(x)=x21在28上的差分一致性為4且差分譜為：

{ω0=152,ω2=80,ω4=24}·

例2 取k=3,n=12· 利用Magma軟件，得到F(x)=x73在212上的差分一致性為4且差分譜為：

{ω0=2496,ω2=1152,ω4=448}·

以上求得的F(x)差分譜無(wú)論是數(shù)值結(jié)果還是理論結(jié)果都與文獻(xiàn)[8]中所得結(jié)果是一樣的·

3 兩類冪函數(shù)的ambiguity和deficiency

利用定理1中給出的Bracken-Leander冪函數(shù)的差分譜，可確定該函數(shù)的ambiguity和deficiency.

定理2 有限域2n上Bracken-Leander冪函數(shù)F(x)=x22k+2k+1，其中n=4k.F(x)的ambiguity為A(F)=(2n-23k-1)(2n-1)，F(xiàn)(x)的deficiency為D(F)=(2n-1)(5·2n-3-23k-3)·

證明由F(x)=x22k+2k+1的差分譜以及F(x)的ambiguity和deficiency的定義可得：

利用定理2中的結(jié)果，下面考慮F(x)=x22k+2k+1的A(F)和D(F)與引理1中上下界的接近程度·

設(shè)n,k為正整數(shù)，當(dāng)gcd(k,n)=s且n/s為奇數(shù)時(shí)，稱冪函數(shù)G(x)=x22k-2k+1為Kassami冪函數(shù)· 文獻(xiàn)[12]中證明了G(x)的差分一致性為2s· 隨后，BLONDEAU等人在文獻(xiàn)[3]中確定了其差分譜為：

{ω0=2n-2n-2,ωi=0(?i,2≤i<2s),ω2s=2n-2},

{ω0=2n-2n-2，ω2=0,ω4=2n-2},

定理3 有限域2n上Kassami冪函數(shù)H(x)=x22k-2k+1，其中n=2t，2t且gcd(k,n)=2.H(x)的ambiguity為A(H)=3·2n-1(2n-1)，H(x)的deficiency為D(H)=3·2n-2(2n-1)·

證明由H(x)的差分譜以及ambiguity和deficiency的定義可得：

3·2n-1(2n-1),

D(H)=(2n-1)ω0=3·2n-2(2n-1)·

易見冪函數(shù)H(x)=x22k-2k+1的A(H)和D(H)達(dá)到引理1中的上界·

4 結(jié)論

近年來(lái)關(guān)于有限域上低差分一致性密碼函數(shù)的研究已經(jīng)取得了很多重要的結(jié)果，已有大量?jī)绾瘮?shù)的差分一致性被確定出來(lái)，但仍有很多冪函數(shù)的差分譜尚未被確定. 本文基于Bracken-Leander冪函數(shù)Walsh譜的研究結(jié)果，利用差分譜和Walsh變換之間的關(guān)系，確定了Bracken-Leander冪函數(shù)的差分譜. 冪函數(shù)差分譜的研究，最終都會(huì)轉(zhuǎn)化為求解有限域上一些方程的根的個(gè)數(shù)及其分布，對(duì)于差分譜未知的低差分冪函數(shù)能否找到一些新的求解方程的技巧是確定其差分譜的關(guān)鍵. 目前國(guó)內(nèi)外學(xué)者對(duì)于有限域上密碼函數(shù)差分譜的研究主要集中在少數(shù)幾類冪函數(shù)以及次數(shù)不超過6的正規(guī)化置換多項(xiàng)式上，對(duì)于其他低差分一致性的密碼函數(shù)能否確定出其差分譜，將是后續(xù)研究的問題.