АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

IV. Конструкция бент-функции

Читайте также:
  1. Архитектоника зданий и сооружений, выполненных в деревянных конструкциях. Арх.формы, выполненные в дереве.
  2. Деконструкция «цивилизации»
  3. Конструкция анализатора IROX
  4. Конструкция вирпула
  5. Конструкция гезаконов
  6. Конструкция и изготовление древних луков
  7. Конструкция и принцип действия БТИЗ
  8. Конструкция и принцип действия пакетосборщиков и пакеторазборщиков
  9. Конструкция и принцип действия подъемных механизмов
  10. Конструкция и размеры
  11. Конструкция и схема включения

 

Итак, разберем преобразование Уолша-Адамара. Для начала определим экспоненту булевой функции f:

exp(f) = (-1)f(x)

Очевидно, что при 0 экспонента принимает значение 1, а при 1 – значение (-1).

Определение.Преобразованием Уолша—Адамара булевой функции f от n переменных называется целочисленная функция Wf, заданная на множестве Zn2равенством

Wf(v) = S uÎZn2exp(<u,v>Åf(u))

В [5, глава 6, §6.5] и [6, глава 2, §2.3] описан алгоритм преобразования Уолша-Адамара 2-го рода:

1. Посчитать экспоненту булевой функции f.

2. Делим полученный вектор пополам.

3. Первую половину складываем со второй и записываем результат в первую половину нового столбца.

4. Из первой половины вычитаем вторую и записываем результат во вторую половину нового столбца.

5. Каждые половинки делим еще на две половины.

6. Повторяем шаги 3-5 до тех пор, пока каждый кусочек не будет состоять из одного элемента.

Таким образом, мы получили вектор после преобразования Уолша-Адамара 2-го рода. Теперь осталось только посчитать нелинейность.

Формула подсчета нелинейности имеет вид:

N(f) = 2n-1 – ½ * max( |Wf (v)| ) ,

где аÎVn , Wf (v) – значения элементов вектора, полученного после преобразования Уолша-Адамара 2-го рода. Она взята из [1, стр.10] и [2, глава 2, §2.2].

Докажем эту формулу. Вес Хэмминга функции f выглядит так:

wt(f)=S xÎZn2f(x)=S xÎZn2(1 - exp(f))/2

Очевидно, что S xÎZn2 exp(f)=Wf(q). Тогда получаем wt(f)=2n−1 − Wf(q)/2. Из этого следует:

wt(f(x)Å<a,x>)=2n−1 −Wf(x)Å<a,x>(q)/2=2n−1− Wf(a)/2.

Аффинная функция g может задаваться либо g(x)=<a,x>, либо g(x)=<a,x>Å1. Посчитаем расстояние между функциями f и g в обоих случаях. В первом случае:

dist(f,g)=wt(f(x)Å<a,x>)=2n−1− Wf(a)/2.

Во втором случае:

dist(f,g)= wt(f(x)Å<a,x>Å1)=2n - wt(f(x)Å<a,x>)=2n−1+ Wf(a)/2.

Таким образом, минимальное расстояние от f до множества аффинных функций равно 2n-1 – ½ * max( |Wf (v)| ). Формула доказана.

Разберем этот алгоритм на примере 1, у которого n=3. Для начала посчитаем экспоненту.



 

f(x) exp(f)
-1
-1
-1
-1

 

 

А теперь выполним преобразование Уолша-Адамара над полученным вектором.

 

      -1   -1     -1   -1         -2        
 
     
 
        -2      
 
     
  -4

 

Как видно, max( |Wf (a)| ) = 4. Значит, нелинейность N(f) равна 2.

Для криптографических целей булева функция должна быть максимально нелинейной. Иначе говоря, она должна как можно меньше быть похожей на аффинную функцию.

Определение. Бент-функциейназывается такая булева функция от n переменных (n четно), что модуль каждого коэффициента Уолша-Адамара этой функции равен 2n/2. Коэффициенты Уолша-Адамара – это значения вектора, полученного после преобразования Уолша-Адамара 2-го рода.

Теорема (Мэйоран—МакФарланд). Пусть T : Zn/22→ Zn/22— любое взаимно однозначное отображение, h ∈ Fn/2 — произвольная функция. Тогда функция f ∈ Fn такая, что f(u’,u’’) = <u’,T(u’’)> Å h(u’’) является бент-функцией. Здесь введены следующие обозначения: Zn/22 – множество из n/2 аргументов, принимающие значения 0 и 1, Fn – множество булевых функций, u’, u’’Î Zn/22 .

Эту теорему осуществляет программа meyoran-mcfarland. Опишем, как она действует. Теорема взята из [3, глава 1, §1.2].

Сначала генерируется случайная перестановка. Этот процесс основан на алгоритме Фишера-Йетса. Он выглядит следующим образом:

 

1. Число i идет по порядку от 1 до n, где n – число переменных (четное).

2. Генерируется случайное число в интервале [1 ; i] (назовем его k).

‡агрузка...

3. Меняем местами числа на местах i и k в массиве per, где per – это массив, перед выполнением цикла имеющий вид: <1, 2, 3, …, n>

4. Повторяем шаги 2,3 до тех пор, пока i не будет больше n.

 

Алгоритм описан в [4].

Случайная перестановка нам нужна для того, чтобы построить взаимно однозначное отображение Т. То есть благодаря перестановке можно поменять местами все аргументы отображения и записать их в значения.

Чтобы вывести все возможные аргументы функции f от n переменных, нужно перевести по порядку все числа от 0 до 2n-1 из десятичной системы счисления в двоичную. Этот процесс осуществляет процедура conversion.

А для создания значений функции h применяется обыкновенная генерация нулей и единиц, происходящая 2n/2 раз.

Далее действуем точно так же, как и сказано в условии теоремы. То есть сначала считаем скалярное произведение пары u’ и T(u’’), потом складываем полученное произведение и h(u’’) по модулю 2. Полученные значения являются значениями бент-функции f.

Разберем этот алгоритм на примере. Пусть n=4, тогда m=n/2=2. Допустим, что случайным образом сгенерировалась перестановка «2,4,3,1». С помощью этой перестановки меняем местами аргументы и записываем их в значения. То есть отображение Т получается следующим образом:

 

 

u’’ T(u’’)

 

Пусть также случайным образом сгенерировались значения функции h в таком виде:

 

 

u’’ h(u’’)

 

Далее действуем так, как сказано по условию теоремы. Возьмем, к примеру, аргумент функции f, равный 1011. Получается, что u’=10, u’’=11, T(u’’)=00, h(u’’)=0. Из этого следует, что

f(u’,u’’) = <u’,T(u’’)> Å h(u’’) = 1*0 Å 0*0 Å 0 = 0.

Таким образом, бент-функция f выглядит следующим образом:

 

u’,u’’ f(u’,u’’)

 

V. Заключение

 

Методов конструирования бент-функций огромное количество: теорема Диллона, теоремы Ротхауса и многие другие. В данной работе был разобран один из этих методов – это теорема Мэйорана-МакФарланда.

Также были написаны на языке Pascal и протестированы программы, реализующие алгоритмы построения полинома Жегалкина, преобразования Уолша-Адамара 2-го рода и построения бент-функции на основании теоремы Мэйорана-МакФарланда. На компьютере автора работы все программы работают без проблем до 9 переменных включительно. Так, к примеру, функция, имеющая значения AB16DA3B061877353AD14BFC97DFE6F2705E0173DD50AC7DE19990B44C973DBA, является бент-функцией. Полином Жегалкина этой функции имеет вид: 1+X8+X6X7X8+X5+X5X8+X5X7X8+X5X6X8+X5X6X7+X4X8+X4X7+X4X7X8+X4X6X8+X4X6X7+X4X5X8+X4X5X6+X4X5X6X8+X4X5X6X7+X3+X3X8+X3X6X8+X3X6X7+X3X6X7X8+X3X5+X3X5X8+X3X5X6+X3X5X6X8+X3X5X6X7+X2+X2X8+X2X7+X2X6+X2X6X8+X2X6X7+X2X6X7X8+X2X5X8+X2X5X6X7+X1+X1X7+X1X7X8+X1X6X8+X1X6X7X8. Степень этого полинома равна 4, а ее нелинейность равна 120.

 


1 | 2 |


Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)