Сбалансированность бф

Во избежание прямых статистических атак на примитивы криптоалгоритма необходимым условием являются:

• сбалансированность компонентных БФ, реализующих преобразование;

• регулярность преобразования в целом.

БФ f(X), XGF(2)ⁿ называется сбалансированной, если количество единиц в ее таблице истинности равно количеству нулей, т.е. #{X  f(X)=0} = #{X  f(X)=1}=2^n-1.

Отображение Y=(X) : GF(2)ⁿGF(2)^m при n  m называется регулярным, если Y ровно 2^n-m раза принимает все 2^m различных значений из GF(2)^m, в то время как X проходит 2ⁿ значений из GF(2)ⁿ. Очевидно, что каждое регулярное отображение Y=(X) : GF(2)ⁿGF(2)^m при m=n является биективным отображением.

Необходимым условием регулярности отображения Y=(X) : GF(2)ⁿGF(2)^m при nm является сбалансированность любых линейных комбинаций компонентных БФ, реализующих векторную БФ (X) = {f₁(X), f₂(X), … , f_m(X)}.

Сбалансированность БФ в терминах ПУА эквивалентна условию , , где =(0, …, 0), т.е. значение ПУА в точке “0” определяет степень отклонения БФ f(X) от сбалансированности.

Показатель сбалансированности БФ является самым простым и, как правило, рассматривается в сочетании с другими показателями.

Корреляционные свойства БФ

Существенным усилением свойства сбалансированности БФ f(X) является требование сбалансированности всех частных функций, полученных из исходной функции фиксированием любых ее k или менее переменных. Указанное требование позволяет обеспечить стойкость криптографических преобразований к статистическим атакам при фиксированных значениях битов на входе преобразования. Данное свойство связано с показателем корреляционной иммунности (КИ). При этом БФ f(X), XGF(2)ⁿ называется корреляционно-иммунной порядка k (CI(k)), 1 k <n, если значение компонентов спектра УА для всех GF(2)ⁿ, вес Хэмминга которых 1  wt()  k..

Максимальный порядок КИ БФ Y=f(X), XGF(2)ⁿ не превышает значения n-1. Единственными функциями, достигающими максимального порядка k=n-1 являются аффинные БФ: f(x₁, x₂, …, x_n)=x₁x₂…x_n и f(x₁, x₂, …, x_n)=x₁x₂…x_n1. Достижение максимума показателя КИ БФ является достаточно сильным требованием, поэтому введем альтернативное понятие – корреляционно-эффективных БФ, для которых не менее чем на половине векторов значения компонентов спектра УА равны 0.

Корреляционно-иммунная степени k БФ f(X) называется совершенной корреляционно-иммунной степени k или резилентной функцией, если она является сбалансированной функцией.

При синтезе БФ, обеспечивающих высокую стойкость к разностному, линейному и корреляционному криптоанализу большое значение имеет автокорреляционная функция (АКФ) БФ. Под автокорреляцией БФ f(X) относительно вектора GF(2)ⁿ понимается функция вида:

(8)

Существует взаимосвязь между энергетическим спектром БФ и АКФ:

, GF(2)ⁿ , (9)

, GF(2)ⁿ, (10)

Данная взаимосвязь позволяет записывать основные показатели качества БФ в терминах АКФ.

Критерии распространения изменений для БФ

Важными характеристиками качества криптографических преобразований являются понятия критерия строгого лавинного эффекта – КСЛЭ (SAC – strict avalanche criterion) и критерия распространения – КР (PC – propagation criterion). Их основная сущность заключается в оценивание вероятности изменения значения БФ в зависимости от изменения части бит аргументов этих функций.

Пусть разность f(X, ) = f(X)f(X), где X, GF(2)ⁿ; f(X)GF(2), тогда БФ f(X) удовлетворяет:

• КСЛЭ, если разность f(X, ) является сбалансированной функцией для любых , вес которых wt() =1;

• КСЛЭ порядка k (SAC(k)), если любая функция, полученная из f(X) путем подстановки констант на места произвольных ее k переменных, удовлетворяет КСЛЭ.

Переходя к спектральным свойствам БФ f(X) удовлетворяет КСЛЭ, если АКФ r_(f )=0 для любых векторов GF(2)ⁿ, вес которых wt()=1.

Булева функция f(X), XGF(2)ⁿ удовлетворяет:

• КР степени ln (PC(l)), если при замене 1  i  l произвольных входных битов на свои дополнения функция f(X) изменяется с вероятностью Pr{f(X)  f(X)} = 0.5, что эквивалентно сбалансированности разности f(X, ) для любых , вес которых 1  wt()  l;

• КР степени l  n и порядка k  n-1 (PC(l)/k ), если любая функция, полученная из БФ f(X) фиксацией любых ее k переменных, удовлетворяет PC(l).

В терминах спектральных свойств БФ удовлетворяет КР степени l (PC(l)), если ее АКФ r_(f ) = 0 на всех векторах GF(2)ⁿ, вес Хэмминга которых лежит пределах 1  wt()  l. Очевидно, что КР является обобщением КСЛЭ, точнее КСЛЭ эквивалентен КР PC(1).

Исследование нелинейности БФ

При анализе эффективности криптографических преобразований, в частности в отношении линейного криптоанализа, одной из основных характеристик является нелинейность БФ, реализующих данное преобразование, которая показывает степень удаленности БФ от множества аффинных или линейных БФ. Нелинейность БФ является важным показателем, поскольку линейные функции легко вскрываются криптоаналистическими методами.

Под аффинными функциями f_афф(X), где  = {f_афф(X)}, XGF(2)ⁿ понимаются БФ следующего вида

f_афф(X) =  , (11)

где , cGF(2). При c=0 аффинные функции образуют подмножество линейных функций ={f_лин(X)}, каждая из которых является скалярным произведением вида f_лин(X) =  .

Удаленность БФ от множества аффинных  или линейных  БФ оценивается через расстояние Хемминга d(f, g) между двумя БФ f(X) и g(X), которое определяет количество отличающихся значений функций:

d(f, g) = #{f(X)g(X) : XGF(2)ⁿ} = wt(S(f )S(g)). (12)

Данное расстояние можно определить через сопряженные функции

d(f, g) =   =  . (13)

Коэффициент взаимной корреляции и расстояние Хемминга связаны между собой следующим соотношением:

r(f, g) =  . (14)

Суммарная корреляция не зависит от вида функции f(X), и для любой БФ f(X) всегда существует корреляция с какой-либо линейной функцией, т. е. существует такая f_лин, что .

На основании вышеизложенного, дадим определение нелинейности БФ f(X) : GF(2)ⁿGF(2), под которой понимается значение минимального расстояния Хэмминга между функцией f(X) и функциями f_афф(X):

. (15)

Аналогично нелинейность NL(f ) можно выразить через расстояние до линейных функций в терминах ПУА:

, (16)

т.е. для определения нелинейности БФ следует определить максимальное значение компоненты спектра УА. Используя данное соотношение, можно достаточно просто определять нелинейность БФ при малых значениях n.

На основании теоремы Парсеваля верхняя граница значения нелинейности NL(f) для любых БФ f(X), X  GF(2)ⁿ, определяется неравенством

NL(f )   (17)

где означает максимальное четное целое, меньшее либо равное значению аргумента.

Достичь наилучших показателей нелинейности для векторной БФ сложно, поэтому на практике используется понятие средней нелинейности векторной БФ (X), которые определяются из выражений:

. (18)

Пределы нелинейности для векторных БФ (X) совпадают с пределами для компонентных БФ.

Таким образом, обобщая изложенные результаты, сформулируем необходимые требования ко всему подстановочному преобразованию и к формирующим его компонентным БФ:

1. Регулярность отображения Y=(X) : GF(2)ⁿGF(2)^m при nm, т.е. сбалансированность всех компонентных БФ и их любых линейных комбинаций.

2. Высокая алгебраическая степень нелинейности deg(f ) компонентных БФ.

3. Соответствие БФ показателям корреляционной иммунности.

4. Соответствие БФ КСЛЭ и КР из множества SAC(k), PC(k)/l, т.е. низкие автокорреляционные показатели.

5. Высокая нелинейность NL(f ) компонентных БФ.

6. Высокая нелинейность NL((X)) или средняя нелинейность векторного преобразования.