Разбор лекций

Данный материалсодержит разборвсех лекций,кроме половинки последней (она приведена без разбора). При необходимости – печатать рекомендуется в режиме«2страницы на 1листе».

1. Введение

Перед тем,какначать,предлагаюдоговориться отом,чтопри чтении должны быть понятны все детали какого-либоопределения или доказательства. А проблемы обычновозникают, когда употребляются давнозабытые никому ненужные термины,окоторыхниктоне помнит.

А этовпервуюочередь такие страшные слова,как «группа»,«полугруппа»,«моноид»… Подождите,не разбегайтесь,сейчасстанет понятнее :) Обещаю,чтопосле прочтения раздела эти определения станут для вассамыми простыми.А уж если не станут,обещаю переместиться вместе сосвоими моноидами вКорзину и больше никогдане напоминать о себе.

Итак,начнемссамогоначала. Чтотакое бинарная операция?Читаемстрогое определение: бинарная операция – этооперация арности два. Первое,чтохочется сделать,увидев такое определение – закрыть справочникпокриптографии и больше не вспоминать онем.Нона самомделе,бинарная операция– этовсеголишь операция,принимающая на вход два аргументаи возвращающая единственный для этойпары результат. Два умножить на три равношесть – простой и всемпонятный пример(результат единственный,потому чтокроме шести эторавняться ничему не будетни сейчас,ни в обозримомбудущем).

Теперь разберемся,чтотакое внутренняя бинарнаяоперация некоторогомножества. А этовсе та же бинарная операция,носодниммаленькимусловием– ее аргументы и результат принадлежат одному и тому же множеству. Все тот же простой пример– два умножить натри равношесть,нотеперь уже намножестве натуральных чисел. Два– натуральное число,три – натуральное число,шесть – натуральное число,и этот результат единственный. Чтоеще нужно?Все сходится. А вот уже другой пример– один минуспять равноминусчетыре,все в томже множестве натуральных чисел. Один – натуральное число,пять – натуральное,а вот минусчетыре – уже нет!

Теперь разберемся стакими вещами,как ассоциативность и коммутативность. Этосовсем просто,только нужноиметь ввиду одну вещь:значком«*» отмечается не умножение,а любая операция,относительнокоторой ведется рассмотрение.

Поздравляю,самое сложное уже позади. Теперь комбинируемполученнуюинформацию… и пошли определения. Для удобства они сведены вотвтакуютабличку

Каждое следующее определения включает в себя все предыдущие,плюсдополнительные условия,указанные вколонке «Расшифровка».

Докольцавроде бы все понятно. Первое условие кольца тоже. А кчему тамнаписанопро коммутативность и ассоциативность умножения?Эторазве не всегда верно?А вот и нет. Делов том,что«х» и «у» -не обязательночисла! Этоможет быть все,чтоугодно.

Например,матрицы. А в такомслучаеx*y не равноy*x. Ну вот,опять кого-тозапутал. Тогда пример:

Тот самый случай,когда операция умножения – не коммутативна.

Вот,вроде бы,и все. С самымначаломразобрались.

Теперь перемещаемся нацелый семестрвперед иначинаемполноценный курс.

Классификация булевыхфункций.

ОбозначимVn – множествоn-мерных двоичных векторов. Этовектора,координаты которых - нули и единички,адлина такоговектора– n.

Пусть G– некоторая группа преобразований множестваVn. Чтоэтотакое?Набор всевозможных преобразований исходных координат векторов:

(11) ( )

(11) ( )

Сколькоих может быть?Какминимумэтотождественное преобразование,когда каждый элемент переходит самв себя,а вмаксимальномслучае– все координаты как-то меняются местами,а ихnштук. Поэтому порядокгруппы Gбудет находиться в пределах: 1≤|G|≤(2n)!

Чтопроизошло,откуда (2n)! ?Давайте разбираться. Всегоимеетсяnэлементов. Каждый из них может принимать 2значения – всего2n значений. И эти значения могутбыть расставлены случайнымспособом. Отсюдафакториал.

Переходимкболее сложнымвещам. Булевы функции f(x1…xn) и Ψ(x1…xn) называют эквивалентными относительно группы G, если в G найдется такая подстановка g, при которой Ψ(х)=f(g(x)). Обозначается f ≡Ψ (первая линия сверху – волнистая!) Что же здесь на самом деле написано? Для этого вспомним, что такое булева функция. Это такая функция, которая для набора аргументов x1 … xn дает какой-то результат (тоже набор)

А чтотакое подстановка?Этокакое-топреобразование координат векторов:

(11) ( )

одинаковый в случаях:

1.Когданавход функции Ψ подали х

2.Когда на вход некоторой подстановки g подали х, и результат этой подстановки подали в функцию f.

Теперь выясним,является ли отношениеΨ(х)=f(g(x)) отношением эквивалентности на

P2(n)? Для этого оно должно быть рефлексивным, симметричным и транзитивным. Стоп… встретили 3 непонятных слова.

Чтобы их понять, придется ввести символ бинарного отношения. Обычно он обозначается R, но мы его для простоты обозначим знаком вопроса. Под ним могут скрываться знаки больше/меньше/равно и прочие неожиданности.

Так вот, рефлексивность требует выполнения условия: x?x is True. Простейший пример – вместо «?» подставляем равно.

Наше отношение рефлексивно, т.к. f(x)=f(e(x)). Да, все оказалось еще проще.

Симметричность требует выполнения незатейливого условия: x?y => y?x.

В нашем случае если f≡ Ψ, то Ψ≡f

Убедиться в этом несложно, достаточно заменить x на g-1(x):

Ψ(g-1(x))=f(g(g-1(x)); Ψ(g-1(x)) = f(x).

Условия транзитивности тоже не отличаются сложностью: a?b & b?c => a?c

В нашем случае: если f≡ Ψ & Ψ≡z, то f≡z

Действительно, первое условие дает: Ψ(x) = f(g(x)). Из второго условия z(x) = Ψ(h(x)). Но если Ψ(h(x)) = z(x), то, с учетом Ψ(x) = f(g(x)), получаем f(g(h(x)))=z(x).

Откуда это взялось? От Ψ можно перейти к f, применив функцию g к ее аргументу:

Ψ(h(x))= f(g(h(x)))

В свою очередь, Ψ(h(x)) = z(x) из условия 2.

Таким образом, рефлексивность, симметричность и транзитивность выполнены, а, значит, отношение f≡ Ψ является отношением эквивалентности.

Дальше узнаем, что, таким образом, множество P2(n) разбивается на классы эквивалентности относительно отношения f≡ Ψ. Загадочное определение. Что оно значит? А значит только то, что множество всех булевых функций разбивается на некоторые классы. И все функции из одного класса являются G-эквивалентными, а вот из разных – уже нет. Напомним, функции f и Ψ называются G-эквивалентными, если представимы в виде: Ψ(х)=f(g(x))

Итак, мы выяснили, что множество всех булевых функций P2(n) разбивается на классы эквивалентности. Теперь обозначим класс эквивалентности, содержащий функцию f, через [f]G. Другими словами: выбранная на P2(n) функция в любом случае окажется в каком-то классе эквивалентности. И этот класс мы обозначили как [f]G. Еще раз другими словами… точнее, рисунком:

Заметим, что 1 ≤ |[f]G| ≤ |G|.

Ну действительно, этот класс может состоять из единственной функции f. Отсюда получаем 1 ≤ |[f]G|. А откуда взялась вторая часть неравенства? И что это за группа G? Чтобы понять этот момент, нужно вспомнить всего 3 вещи. Вспоминаем: G – это некоторая группа преобразований множества Vn. Ее элементами являются подстановки g1, g2 и т.д. Теперь вспомним, что такое G-эквивалентные функции. Это функции, представимые в виде: Ψ(х)=f(g(x)). Наконец, вспомним, что такое [f]G. Это класс эквивалентности, то есть класс, содержащий все G-эквивалентные функции. Теперь комбинируем эти 3 вещи. Чтобы представить функцию Ψ через f, нам нужно некоторое значение g Ψ(х)=f(g(x)). А чтобы представить через нее другую функцию Ψ2? У нас же целый класс таких функций, которые можно получить из f! Для этого потребуется уже другое значение g: Ψ2(х)=f(g2(x)). Чтобы представить все возможные Ψ через функцию f класса [f]G, могут потребоваться все подстановки из G, а их количество равно |G|. А может потребоваться и меньше

– зависит от конкретного примера. Отсюда второе неравенство: |[f]G| ≤ |G|. Теперь должно быть понятно.

А если понятно, то идем дальше. Дальше нам предлагают узнать, что если |[f]G|=1, то f неизменна при всех преобразованиях g G.Втаком случаеговорят, чтофункция fинвариантна относительногруппы Gили G-инвариантна. Этоозначает,чтоf(x)=f(g(x)) для любых g G.Вот прочитал этоидолгонемог понять,апочемутак?Понять самые простыевещичастосложнеевсего. Вот почему 2*2=4?Предлагаюпринять этокак аксиомуипродолжить.Доказательстваэтогоянигдененашел.Итак,запоминаем:

если |[f]G|=1, то f неизменна при всех преобразованиях g G:f(x)=f(g(x)). Такая функция fназывается G-инвариантной.

Это хорошо, когда |[f]G|=1. А если ее размер – нечто большее, чем 1? Для определения степени инвариантности f относительно G используется понятие группы инерции. Группа инерции функции f в G – это множество преобразований из группы G, не изменяющих функцию f. Обозначается JG(f). Понятно, что для каждой функции f группа инерции своя.

JG(f) = {g G/f(g(x))=f(x)}.

Множество JG(f) является подгруппой группы G, причем 1≤|JG(f)|≤|G|. Действительно, таких подстановок g, что выполняется f(g(x))=f(x),может быть не большевсехперестановок группыG.

А теперь определение.Здесь нет ничегонового, простоонотак называется:если |JG(f)|=1,тофункцияf имеет тривиальнуюгруппуинерциивгруппеG.

Рассмотримтеперь теорему освязи весов:|[f]G|, |G|,|JG(f)|.

Теорема.

Для любой функции f P2 справедливо:

|[f]G| =||( |)|

Доказательство

Пусть g – произвольное преобразование изG. Определим,сколько преобразованийg’изG дают ту же функцию,чтои преобразование g. Тоесть выполнится равенство:f(g(x)) = f(g’(x)).

Сделаемзамену:y=g(x). Тогдаx=g-1(y). Сначалакажется непонятным,ноэто– чистая математика. Аналогичный пример:y=sin(x),тогдаx=sin-1(y) = arcsin(y).

f(g(x)) = f(g’(x)) y = g(x)

x = g^(−1)(y)

Подставляя (2) и (3) в (1) получаем:f(y)=f(g’*g-1(y)).Эторавенствовыполняется тогдаи толькотогда,когдаg’’=g’*g-1 JG(f).Откудаэто?Вспомним,чтоJG(f)–этомножество функций,неизменяющихфункциюf:f(g(x))=f(x).Внашем случаероль g играет g’*g-1,

для удобства обозначенный какg’’.

Теперь возьмемуравнение g’’=g’*g-1 и выразимизнегоg’:

g’=g’’*g

Чтотакое g?Вспомнимпервуюстрочку доказательства:«Пусть g – произвольное преобразование изG». Тоесть этонекоторое фиксированное преобразование

Чтотакое g’’?А этои не важно! Важното,чтомы получили ранее:g’’ JG(f).

Приходим к выводу:количествовсех подстановок изG,дающихтужефункцию,что иg,равномощностигруппыинерции|JG(f)|,иэтонезависит от выбораg.

Вучебникеимоихлекцияхнаписано,чтопосле этогоусловиетеоремыстановится очевидным.Увы,мнеонотак ине сталоочевидно,поэтомубольшеничегосказать о

теоременемогу.Хотя остаетсявсего одинкакой-тошаг.Наверное,слишком очевидный,потомучтояегонигдененашел.

Переходим от словк делутеорем к новым определениям.Заявлено, что,незная классификациюбулевыхфункций,нам никогданеудастсястать хорошими криптоаналитиками.И еслинасобеседованиепридут 2человека:знающий классификациюбулевыхфункцийивзломавшийAES,возьмут первого.Поэтому предлагаюнезамедлительноознакомитьсясэтимиклассами.Тем более, чтоихвсего

5.

1.ГруппаSn перестановокпеременных. Чтоможносказать новогооперестановках? Ихитак всезнают.Этотаблицазаменвот такоговида:

…

( )… ( )

Всеготакихпреобразований -n!(количествоперестановок изn штук).

Примечание.Функцияf(x)называетсясимметрической, еслиона инвариантна относительногруппыSn.Напомним,функцияназываетсяинвариантной относительногруппы,еслионанеизменна привсехпреобразованияхизэтой группы.Тоесть,внашем случае,JSn(f)=Sn

Вродебы,всехорошои понятно… Нонезабывайте,этокриптография.И ей занимаютсяжесткиекриптоаналитики.Поэтомупример будет максимально простойипонятный.«Симметрическойб.ф.является,например,суммавсех конъюнкцийрангаkот n переменных, 0≤k≤n». Вот ивсе:)P.S.Советуюсчитать эторекламнойпаузойисразупереходить к пункту2.

2.Группа∑n инвертированийпеременных(группасдвигов).Состоит из преобразованийвида:

Всеготакихпреобразований–2n («а»может принимать значение0или1,иихn штук)

3.ГруппаДжевонсаQn (группаоднотипностиилигеометрической эквивалентности).

Являетсяпроизведением группSn и∑n.Представляет собойпреобразованияв видеперестановкипеременныхиинвертированиинекоторыхизних.

где(j1…jn)–перестановкачисел (1…n)–дает размерность n! (a1…an) Vn –дает размерность 2n

Отсюда:|Qn|=n!* 2n

4.ГруппаGLn(2)–линейныхподстановок (полная линейнаягруппа). Представляет собойпреобразования:

g(x)=x*A,гдеА –двоичнаяматрицаразмераn xn (невырожденная)

Размерность группы | GLn(2)| определяется количеством невырожденных матриц,

ионоравно(2n-1)*(2n-2)*(2n-4)… =П(2n-2i) от i=0доn-1

Чтотакоеневырожденнаяматрица?Этоматрица,определитель которойотличен от нуля.

Почемутак –незнаю,этоужевопрослинейной алгебры.ВИнтернетенашел вот такойужас:

первый множитель - это количество вариантов первой строки матрицы (годятся все ненулевые), второй множитель - это количество вариантов второй строки (годятся все не

лежащие в лин. простанстве натянутом на первую строку), третий множитель - это количество вариантов третьей строки

ит.д.

5.ГруппаAGLn(2)аффинныхподстановок (полнаяаффиннаягруппа),является произведением группGLn и∑n.Состоит изпреобразованийвида:

g(x)=xA B

где:А –обратимаяматрицаразмераn xn над полем издвухэлементов

B=(b1…bn) Vn –вектор

Прощеговоря,А –этоматрицакак вп.4, аВ–простодвоичныйвектор длиныn. Размер матрицыА изп.4мызнаем:П(2n-2i)от i=0доn-1

Размер двоичноговекторадлиныn тоже:n!

Получили:| AGLn(2)| =n!* П(2n-2i)от i=0доn-1

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

Давайтерассмотрим ещеодноутверждениеиперейдем к самомуинтересному–к практике.

Утверждение. Пустьf≡ Ψ. Тогда: 1. ||f|| = ||Ψ||

2. Если G – подгруппа группы AGLn(2), то deg(f)=deg(Ψ)

3. Если G {Sn,∑n,Qn},тофункцииf иΨ имеют одинаковое число существенных переменных.

Доказательство

1.Первоесвойствоследует изнеизменностивеса функцииf(g(x))прилюбой подстановкеg

2.Прилюбойаффиннойподстановкеg измножестваVn степень нелинейности функцииf(g(x))невозрастает,поэтому: deg(f(x))≥def(f(g(x))≥deg(f(g-1(g(x)))=deg(f(x))

Степень нелинейности булевой функции deg(f) — число переменных в самом длинном слагаемом её полинома Жегалкина.

Аффинная (линейная) булева функция — булева функция, полином Жегалкина которой не имеет нелинейных членов, то есть членов, представляющих собой конъюнкцию нескольких переменных.

3.Любаяподстановкаg изGпреобразует парусоседнихвекторовмножестваVn в парутакжесоседнихвекторов.

соседние векторы - отличаются по весу (числу единичных компонент) ровно на единицу

Существеннаяпеременная–этокогда: f(…0…)≠f(…1…)

Итак,наэтом теорияразделазавершается.Переходим к практике. Пример.

Определить |JSn(f)| длябулевойфункцииf=(x1…x6).

1.Представим многочленЖегалкинаэтойбулевойфункцииввидесуммы однородныхмногочленов.Прощеговоря,перепишемфункциюввиде: f(x1…x6)=1 (x1 x3 x4) (x1*x2 x2x3 x4x5) x2x3x4 x3x4x5x6

2.Обозначим: f1=x1 x3 x4

f2=x1*x2 x2x3 x4x5 f3=x2x3x4

f4=x3x4x5x6

3.СоставимматрицуM(f)встречаемостипеременныхx1…x6 воднородных многочленахf1…f4:

4. ВсякаяперестановкаизгруппыJS(f)неизменяет матрицуM(f),тоесть

можнопереставлять толькоодинаковыестолбцы. Внашемслучае этотолькостолбцыx3иx4.

Нонеторопитесь записать ответ!Прирешениизадачитакимспособом нужновсегдапроверить,неизменитсялифункция,еслипоменятьx3и x4местами.Внашем случаефункцияизменится! Поэтомутакая перестановканеподходит,иJсостоит изединственнойперестановки– тождественной,котораяесть всегда.

Получаем ответ:|JS(f)|=1

Раздел 2.Частичноупорядоченныемножества

Незнаю,хорошоэтоилиплохо,новэтом разделепочтисовсемненадодумать.Не потребуетсяиразбирать что-тосложное,потомучтораздел состоит изопределенийчуть более,чем полностью. Темне менее,стоит сделать пометки,чтокакоеопределениезначит

–этонавернякапотребуетсявбудущем.

Начнем.

Множествовсех подмножеств множества Хназывается булеаноммножестваХ и обозначается 2Х.

Ну здесь все просто– множествоХ состоит изподмножеств Х1,Х2и т.д. И если взять все эти подмножества,тополучимбулеан множестваХ.

Утверждение:если Х есть n-множество,то|2X|=2n.

Чтоздесь сказано?Чтоесли в некотороммножествеnэлементов,томощность булеана этого множества равна2n. Почему?Давайте разберемся. Изчегосостоит множествоХ?Изнабора элементов:Х={х1..хn}. А чтотогда такое подмножествомножестваХ?Этокусочекот множестваХ, поэтому туда входят некоторые элементы x1…xn. А теперь поступимтак,какделают настоящие криптоаналитики. Зашифруемсамымстойкимкриптоалгоритмом. Рассмотримоднокакое-то подмножество. Вспомним,чтовнеговходят некоторые элементы исходногомножества Х. Тоесть каждый элемент изХ может входить или не входить в этоподмножество. ТолькоДА или НЕТ– никаких компромиссов криптоаналитики не терпят.Поэтому поставимвсоответствие каждому элементу x1…xn некоторое значение а,которое равноединице,если данный элемент входит в рассматриваемое подмножество,и 0,если не входит. Получили,чтонабору элементовx1..xn соответствует наборa1..an,где ai = 1,если xi входит врассматриваемое подмножество,и равно0в противномслучае. А чтотакоеa1…an?Этодвоичныйвектордлины n!Ничегонового,просто определение! Векторсостоит изn элементов,каждый изкоторых равен 0или 1.

Теперь вспомним,ачтомы хотели?Хотели доказать,что|2X|=2n, где 2Х – множествовсех подмножествмножестваХ. В прошломабзаце мы осознали,чтоколичестворазличных подмножествмножестваХ– этоколичестводвоичных векторов длины n(т.к. каждому подмножеству соответствует двоичный вектордлины n). А скольковсеговозможнодвоичных векторовдлины n?Ответ – 2n (элемент может принимать 1из2значений,и их количество– n).

Определение. МножестваX1…Xm называются попарноневложимыми,если Хi\Xj ≠ .

Для начала вспомним:А\В обозначает множествоэлементов,принадлежащихА и не принадлежащих В. Понятно,чтоесли одномножествополностьювходит вовторое,тоА\В=0.