一類新的代數(shù)免疫度最優(yōu)的奇變元旋轉(zhuǎn)對稱布爾函數(shù)的構(gòu)造*

王 勇， 鄭 東，2， 趙慶蘭， 李路陽， 師 宇

1. 西安郵電大學(xué) 無線網(wǎng)絡(luò)安全技術(shù)國家工程實(shí)驗(yàn)室， 西安 710121

2. 衛(wèi)士通摩石實(shí)驗(yàn)室， 北京 100070

1 引言

布爾函數(shù)[1]在對稱密碼系統(tǒng)中有著重要的應(yīng)用， 可以作為流密碼中的濾波函數(shù)和組合函數(shù)， 也可以作為分組密碼中的S 盒， 其密碼學(xué)性質(zhì)的優(yōu)劣在很大程度上影響著密碼系統(tǒng)的安全性. 若用于密碼系統(tǒng)的布爾函數(shù)的非線性度較低， 則流密碼系統(tǒng)容易受到快速相關(guān)攻擊[2]， 而分組密碼系統(tǒng)容易受到線性攻擊[3].為了抵抗Berlekamp-Massey 攻擊[4]和Ronjom-Helleseth 攻擊[5]， 布爾函數(shù)必須具備較高的代數(shù)次數(shù).因此， 用于密碼系統(tǒng)的布爾函數(shù)需要考慮的密碼學(xué)指標(biāo)包括: 非線性度、平衡性、代數(shù)次數(shù)等. Courtois和Meier[6]提出代數(shù)攻擊之后， 代數(shù)免疫度[7，8]成為衡量布爾函數(shù)抵抗代數(shù)攻擊能力的密碼學(xué)指標(biāo). 文獻(xiàn)[8] 指出n元旋轉(zhuǎn)對稱布爾函數(shù)的代數(shù)免疫度上界為「n/2若達(dá)到此邊界， 則表明該布爾函數(shù)具有最優(yōu)的抵抗代數(shù)攻擊的能力. 2003 年， 快速代數(shù)攻擊[9]被提出. 若存在代數(shù)次數(shù)較低的函數(shù)g/= 0， 使得f ·g的代數(shù)次數(shù)不是很高， 則認(rèn)為對f進(jìn)行快速代數(shù)攻擊是可行的. 快速代數(shù)免疫度FAI (fast algebraic immunity)[10]用于衡量一個布爾函數(shù)抵抗快速代數(shù)攻擊的能力.

沈黎鵬和陳克非在文獻(xiàn)[19] 給出一種新的方案， 其構(gòu)造函數(shù)的非線性度在變元個數(shù)n ≥25 時(shí)超過了以往同類的構(gòu)造， 但是在n ≤23 時(shí)作者沒有給出確定的非線性度， 且沒有考慮快速代數(shù)攻擊等相關(guān)問題.而在實(shí)際應(yīng)用中， 代數(shù)攻擊的出現(xiàn)要求流密碼設(shè)計(jì)中的布爾函數(shù)的輸入變元個數(shù)n至少為15[20，21]， 但是考慮到快速計(jì)算的需求， 特別是在輕量級密碼算法的設(shè)計(jì)中， 變元個數(shù)也不宜過大. 文獻(xiàn)[22] 指出變元個數(shù)n在18 左右即可以滿足密碼學(xué)性質(zhì)和計(jì)算效率的需要. 本文給出一種新的代數(shù)免疫度最優(yōu)的奇變元RSBFs 的方案， 在變元個數(shù)n ≤23 時(shí)非線性度是同類構(gòu)造中最高的. 此外， 新函數(shù)具有較高的代數(shù)次數(shù)，在n= 11，13，15 時(shí)， 還具有幾乎最優(yōu)的抵抗快速代數(shù)攻擊的能力， 為布爾函數(shù)的實(shí)際應(yīng)用提供了更多選擇.

本文其余章節(jié)安排如下: 第2 節(jié)給出了布爾函數(shù)相關(guān)基礎(chǔ)知識; 第3 節(jié)介紹了整數(shù)拆分理論， 并且給出了奇變元RSBFs 的具體構(gòu)造方案; 第4 節(jié)證明了本文構(gòu)造的函數(shù)是代數(shù)免疫度最優(yōu)的， 還給出了非線性度、代數(shù)次數(shù)、抵抗快速代數(shù)攻擊能力的分析求解過程; 第5 節(jié)是總結(jié)全文.

2 預(yù)備知識

若f是平衡的， 則有Wf(0n)=0 (這里0n代表長為n的全零向量).

對于f ∈Bn，f和仿射函數(shù)之間最小漢明距離表示其非線性度， 記為NL(f)， 即:

由文獻(xiàn)[8] 可知AI(f)≤「n/2若AI(f)=「n/2則f具有最優(yōu)的抵抗代數(shù)攻擊的能力.

定義2[10]對于f ∈Bn， 快速代數(shù)免疫度用FAI(f) 表示， 即:

其中1≤deg(g)＜AI(f). 若FAI(f) =n， 則稱f抵抗快速代數(shù)攻擊的能力是最優(yōu)的. 若FAI(f) =n-1， 則稱f抵抗快速代數(shù)攻擊的能力是幾乎最優(yōu)的.

文獻(xiàn)[9] 表明， 對于f ∈Bn， 假如存在代數(shù)次數(shù)較低的函數(shù)g以及適當(dāng)?shù)暮瘮?shù)h， 使得f ·g=h， 則說明f不具備良好的抵抗快速代數(shù)攻擊的能力.f的代數(shù)免疫度達(dá)到最優(yōu)， 但并不能說明其具有抵抗快速代數(shù)攻擊的能力.

定義3[23]如果F(x) 可表示為:

3 構(gòu)造奇變元旋轉(zhuǎn)對稱布爾函數(shù)

3.1 整數(shù)拆分

首先引入整數(shù)拆分[25]的有關(guān)理論. 對于一個正整數(shù)k和一個長度為m的整數(shù)序列， 若滿足k1+k2+···+km=k， 其中ki ＞0， 1≤i ≤m， 則稱此序列為k的一個m拆分. 該序列是考慮先后順序的， 也就是說僅僅是不同順序的序列也代表著k的不同形式的拆分. 例如整數(shù)4 的拆分組合為(4)， (3，1)，(2，2)， (2，1，1)， (1，3)， (1，2，1)， (1，1，2)， (1，1，1，1). 由文獻(xiàn)[25] 可知， 將一個正整數(shù)k拆分為長度為m的分

對于k的m拆分， 若下面(1) 和(2) 兩個條件成立， 記為pm(k)， 即:

(1)k1+k2+···+km=k;

(2)km ≥km-1≥···≥k1.

由文獻(xiàn)[25] 可知pm(k) 的計(jì)數(shù)可通過遞推公式得到， 即pm(k) =pm-1(k-1)+pm(k-m)， 且滿足p1(k)=pk(k)=1.

3.2 構(gòu)造集合T′h 和T′′h

3.3 構(gòu)造集合T 和U

3.4 構(gòu)造函數(shù)

其中F(x) 是擇多函數(shù). 不難看出， 式(8)中的f(x) 是一個n元旋轉(zhuǎn)對稱布爾函數(shù)， 且具有平衡性.

例1 當(dāng)k=5， 即n=11 時(shí)， 有:

根據(jù)U的構(gòu)造規(guī)則可知:

4 密碼學(xué)性質(zhì)分析

4.1 代數(shù)免疫度

這里先給出一些證明所需的引理. 引理1 給出了基于擇多函數(shù)構(gòu)造代數(shù)免疫度最優(yōu)的布爾函數(shù)的方法.

則有|～T|=|～U|=nLk.

定理1 式(8)中的f(x) 具有最優(yōu)的代數(shù)免疫度.

4.2 非線性度

在分析非線性度之前， 先給出一些必要的引理.

表1 將本文構(gòu)造的布爾函數(shù)f(x) 的非線性度相對于擇多函數(shù)的增加部分與同類研究成果進(jìn)行了對比， 當(dāng)變元個數(shù)小于25 時(shí)本文所構(gòu)造的函數(shù)的非線性度高于現(xiàn)有的所有同類構(gòu)造， 且增加幅度較為顯著，當(dāng)變元個數(shù)大于等于25 時(shí)f(x) 的非線性度也高于除文獻(xiàn)[19] 之外的同類構(gòu)造.

表1 非線性度超過擇多函數(shù)部分的比較Table 1 Comparison of part of nonlinearity exceeding majority function

4.3 代數(shù)次數(shù)

這里給出了本文構(gòu)造的f(x) 的代數(shù)次數(shù)的分析， 結(jié)果表明在某些情況下代數(shù)次數(shù)可以達(dá)到n-1.

定理3 式(8)中函數(shù)f(x) 的代數(shù)次數(shù)滿足:

證明: 式(8)中布爾函數(shù)f(x) 可表示為f(x)=F(x)+R(x)， 其中

由于wt(R) = 2|～T| 為偶數(shù)， 根據(jù)式(2)可知deg(R)≤n-1.R(x) 的代數(shù)正規(guī)型中n-1 次項(xiàng)x1x2···xn/xt(1≤t ≤n) 的系數(shù)等價(jià)于集合～T和～U中滿足xt分量為0 的向量個數(shù)N(mod 2). 根據(jù)向量x生成軌道的定義可知，x的每一個分量元素都會在位置t出現(xiàn)， 則

若N=1(mod 2)， 則有deg(R)=n-1; 若N=0(mod 2)， 有deg(R)＜n-1.

根據(jù)上述分析可知， 若滿足k= 2m(m ≥3)，N= 0(mod 2)， 或2m-1+1≤k ≤2m-1，N= 1(mod 2)， 則有deg(f) =n-1; 若滿足k= 2m(m ≥3)，N= 1(mod 2)， 或2m-1+1≤k ≤2m-1，N=0(mod 2)， 則有deg(f)≤n-2.

利用式(7)給出的|Th| 計(jì)數(shù)公式， 可計(jì)算出5≤k ≤25 范圍對應(yīng)的N的值， 再結(jié)合定理3 可得到式(8)中的f(x) 對應(yīng)的代數(shù)次數(shù)， 這里給出了5≤k ≤25 范圍內(nèi)式(8)中的f(x) 對應(yīng)的代數(shù)次數(shù):

4.4 抵抗快速代數(shù)攻擊的能力

布爾函數(shù)f(x) 的代數(shù)免疫度達(dá)到了最優(yōu)， 但并不能說明其具有抵抗快速代數(shù)攻擊的能力. 一個著名的程序是Simon Fischer 程序， 它可以評估一個函數(shù)抵抗快速代數(shù)攻擊的能力. 在運(yùn)行Simon Fischer 程序時(shí)， 需要函數(shù)的真值表和輸入n，e，d， 輸出將顯示滿足gf=h， deg(g)+deg(h)＜n的非零函數(shù)g和h的解的個數(shù)， 其中deg(g)=d， deg(h)=e. 受計(jì)算資源限制， 現(xiàn)有文獻(xiàn)對布爾函數(shù)抵抗快速代數(shù)攻擊能力的分析通常在小變元范圍內(nèi)進(jìn)行. 本文為了檢驗(yàn)當(dāng)n= 11，13，15 時(shí)式(8)中的f(x) 抵抗快速代數(shù)攻擊的能力， 對滿足d ≥「n/2+d ＜n的e和d的組合， 利用計(jì)算機(jī)執(zhí)行了Simon Fischer 程序， 實(shí)驗(yàn)結(jié)果表明， 當(dāng)n= 11，13，15 時(shí)， 不存在e+d ＜n-1 的(e，d) 組合， 僅存在e+d ≥n-1 的(e，d) 組合.因此， 對于n=11，13，15， 有FAI(f)=n-1. 即本文構(gòu)造的函數(shù)至少在n=11，13，15 時(shí)， 抵抗快速代數(shù)攻擊的能力達(dá)到了幾乎最優(yōu).

5 結(jié)論

自從2007 年以來， 如何構(gòu)造具有最優(yōu)代數(shù)免疫度的奇變元旋轉(zhuǎn)對稱布爾函數(shù)一直是很多學(xué)者所關(guān)注的問題， 而如何提高該類函數(shù)的非線性度是研究的難點(diǎn)之一. 文獻(xiàn)[19] 在變元個數(shù)大于23 時(shí)提升了現(xiàn)有同類構(gòu)造的非線性度， 本文在變元個數(shù)小于等于23 時(shí)提升了現(xiàn)有同類構(gòu)造的非線性度. 此外本文構(gòu)造的函數(shù)的代數(shù)次數(shù)在某些情況下能達(dá)到平衡函數(shù)的最高代數(shù)次數(shù)n-1， 并且經(jīng)實(shí)驗(yàn)驗(yàn)證構(gòu)造的函數(shù)在n=11，13，15 時(shí)， 還具備幾乎最優(yōu)的抵抗快速代數(shù)攻擊的能力. 本文的構(gòu)造可以推進(jìn)對安全性和計(jì)算效率要求較高的密碼算法中的布爾函數(shù)的理論研究， 并為密碼算法(特別是需要使用小變元布爾函數(shù)的輕量級密碼算法) 的設(shè)計(jì)提供了更多可供選擇的布爾函數(shù).