SIMON類非線性函數(shù)的線性性質(zhì)研究

關(guān) 杰 盧健偉

(戰(zhàn)略支援部隊信息工程大學 鄭州 450001)

1 引言

隨著技術(shù)的快速發(fā)展，信息處理功能已經(jīng)可以在越來越小的嵌入式設備中實現(xiàn)。這類微型嵌入式設備的計算與存儲能力十分有限，因此稱為資源受限設備。傳統(tǒng)密碼在設計上主要考慮提高算法的安全性，沒有考慮將算法應用于受限設備的情況。輕量級密碼(LightWeight Cryptography, LWC)的誕生給這類設備所處理的信息提供了相應的保護，成為密碼學研究的熱點之一。

SIMON算法[1]是美國國家安全局(the National Security Agency, NSA)在2013年設計的一類基于Feistel結(jié)構(gòu)的輕量級分組密碼算法，該算法的輪函數(shù)為F182(x)=(x<<<1)&(x<<<8)⊕(x<<<2)，只包含循環(huán)移位、按位與和異或這3類基本運算，因此軟件與硬件的實現(xiàn)效果較好。自從SIMON算法提出以來，密碼學者對其進行了大量分析。目前針對該算法的安全性分析主要包括差分分析[2-4]、線性分析[5-9]、不可能差分分析[10-12]、零相關(guān)分析[13-15]和積分分析[16,17]等。

SIMECK算法[18]是于2015年設計的一類輕量級分組密碼算法，其結(jié)合了SIMON算法和 SPECK算法的優(yōu)點，具有高效且低成本硬件實現(xiàn)的特點。該算 法 的 輪 函 數(shù) 為F051(x)=x&(x<<<5)⊕(x<<<1)，同樣沿用了SIMON算法輪函數(shù)的結(jié)構(gòu)，將循環(huán)移位參數(shù)由(1,8,2)修改為(0,5,1)。

這些算法的輪函數(shù)均采用了如下形式的非線性函數(shù)Fabc(x)=(x<<

本文主要研究了移位參數(shù)一般化的SIMON類算法輪函數(shù)Fabc(x)的線性性質(zhì)，給出了相關(guān)優(yōu)勢的取值范圍，并且證明了對于該范圍內(nèi)的每一個相關(guān)優(yōu)勢，都可以找到對應的掩碼對，解決了這類輪函數(shù)的Walsh譜分布規(guī)律問題，同時給出了非平凡相關(guān)優(yōu)勢取到 2?1與最小值的充分必要條件與計數(shù)情況，為SIMON系列算法與SIMECK算法等的線性安全性分析提供了理論基礎(chǔ)。

本文組織架構(gòu)如下：第2節(jié)介紹SIMON類算法輪函數(shù)、不相交2次型以及線性相關(guān)優(yōu)勢等基本概念，第3節(jié)給出SIMON類非線性函數(shù)的線性性質(zhì)，第4節(jié)進行全文總結(jié)。

2 基本概念

錄)，可以有效地將任意給定的2次布爾函數(shù)轉(zhuǎn)換為不相交2次型。

3.1 F 譜值的取值范圍

下面考慮掩碼對計數(shù)問題，由上述證明過程可知，一個輸出掩碼μ對應4個輸入掩碼η，故當w(μ)=1 時掩碼對數(shù)為4n，當w(μ)=2時，取遍i0后，μi0=μi0+t=1與μi0=μi0+n?t=1包 含 的μ的集合相同，故此時掩碼對數(shù)為4n，總計8n。證畢

定理4研究了最大非平凡相關(guān)優(yōu)勢點的結(jié)構(gòu)和計數(shù)，但是最小非平凡相關(guān)優(yōu)勢點的結(jié)構(gòu)和計數(shù)也是需要重點考慮的問題。下面給出特定條件下非平凡相關(guān)優(yōu)勢取到最小值的充分必要條件。

結(jié)合定理5，給出非平凡相關(guān)優(yōu)勢取到最小值1/2n/2時的一個充分條件。

表1 F abc(x)相關(guān)優(yōu)勢計數(shù)表

4 結(jié)束語

文獻[5]僅給出了SIMON類輪函數(shù)的線性逼近式的2次項相互獨立時的線性性質(zhì)，然而2次項相關(guān)時的線性性質(zhì)還未徹底解決。本文進一步研究了移位參數(shù)一般化下SIMON類算法輪函數(shù)的線性性質(zhì)，利用算法1將相關(guān)優(yōu)勢取值問題轉(zhuǎn)化為不相交2次型中2次項的個數(shù)問題，界定了相關(guān)優(yōu)勢的取值范圍，證明了在特定條件下對于該范圍內(nèi)的每一個相關(guān)優(yōu)勢點均可找到對應的掩碼對，證明了此類函數(shù)是多輸出部分bent函數(shù)，給出了非平凡相關(guān)優(yōu)勢取到最大值1/2時掩碼對的充要條件及計數(shù)，給出了特定條件下非平凡相關(guān)優(yōu)勢取到最小值的充分條件與掩碼對的計數(shù)。研究表明，當n為 偶數(shù)且t為奇數(shù)時，可以取到最小非平凡相關(guān)優(yōu)勢點。該研究成果為SIMON與SIMECK等算法的線性分析提供了理論基礎(chǔ)。接下來需要做的工作是給出此類函數(shù)移位參數(shù)抵抗各類密碼分析方法的選取準則，并應用于SIMON與SIMECK等算法的線性安全性分析。

5 附錄

表2 轉(zhuǎn)變成不相交2次型算法(算法1)

續(xù)表2