關(guān) 杰 盧健偉

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

1 引言

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

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

SIMECK算法[18]是于2015年設(shè)計(jì)的一類輕量級分組密碼算法，其結(jié)合了SIMON算法和 SPECK算法的優(yōu)點(diǎn)，具有高效且低成本硬件實(shí)現(xiàn)的特點(diǎ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)的每一個(gè)相關(guān)優(yōu)勢，都可以找到對應(yīng)的掩碼對，解決了這類輪函數(shù)的Walsh譜分布規(guī)律問題，同時(shí)給出了非平凡相關(guān)優(yōu)勢取到 2?1與最小值的充分必要條件與計(jì)數(shù)情況，為SIMON系列算法與SIMECK算法等的線性安全性分析提供了理論基礎(chǔ)。

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

2 基本概念

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

3.1 F 譜值的取值范圍

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

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

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

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

4 結(jié)束語

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

5 附錄

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

續(xù)表2