SIMON類非線性函數的線性性質研究

關 杰 盧健偉

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

1 引言

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

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

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

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

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

本文組織架構如下：第2節介紹SIMON類算法輪函數、不相交2次型以及線性相關優勢等基本概念，第3節給出SIMON類非線性函數的線性性質，第4節進行全文總結。

2 基本概念

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

3.1 F 譜值的取值范圍

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

定理4研究了最大非平凡相關優勢點的結構和計數，但是最小非平凡相關優勢點的結構和計數也是需要重點考慮的問題。下面給出特定條件下非平凡相關優勢取到最小值的充分必要條件。

結合定理5，給出非平凡相關優勢取到最小值1/2n/2時的一個充分條件。

表1 F abc(x)相關優勢計數表

4 結束語

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

5 附錄

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

續表2