|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
IV. Конструкция бент-функции
Итак, разберем преобразование Уолша-Адамара. Для начала определим экспоненту булевой функции 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. Для начала посчитаем экспоненту.
А теперь выполним преобразование Уолша-Адамара над полученным вектором.
Как видно, 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». С помощью этой перестановки меняем местами аргументы и записываем их в значения. То есть отображение Т получается следующим образом:
Пусть также случайным образом сгенерировались значения функции h в таком виде:
Далее действуем так, как сказано по условию теоремы. Возьмем, к примеру, аргумент функции 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 выглядит следующим образом:
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.
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.) |