Разбор лекций
.pdfДанный материалсодержит разборвсех лекций,кроме половинки последней (она приведена без разбора). При необходимости – печатать рекомендуется в режиме«2страницы на 1листе».
1. Введение
Перед тем,какначать,предлагаюдоговориться отом,чтопри чтении должны быть понятны все детали какого-либоопределения или доказательства. А проблемы обычновозникают, когда употребляются давнозабытые никому ненужные термины,окоторыхниктоне помнит.
А этовпервуюочередь такие страшные слова,как «группа»,«полугруппа»,«моноид»… Подождите,не разбегайтесь,сейчасстанет понятнее :) Обещаю,чтопосле прочтения раздела эти определения станут для вассамыми простыми.А уж если не станут,обещаю переместиться вместе сосвоими моноидами вКорзину и больше никогдане напоминать о себе.
Итак,начнемссамогоначала. Чтотакое бинарная операция?Читаемстрогое определение: бинарная операция – этооперация арности два. Первое,чтохочется сделать,увидев такое определение – закрыть справочникпокриптографии и больше не вспоминать онем.Нона самомделе,бинарная операция– этовсеголишь операция,принимающая на вход два аргументаи возвращающая единственный для этойпары результат. Два умножить на три равношесть – простой и всемпонятный пример(результат единственный,потому чтокроме шести эторавняться ничему не будетни сейчас,ни в обозримомбудущем).
Теперь разберемся,чтотакое внутренняя бинарнаяоперация некоторогомножества. А этовсе та же бинарная операция,носодниммаленькимусловием– ее аргументы и результат принадлежат одному и тому же множеству. Все тот же простой пример– два умножить натри равношесть,нотеперь уже намножестве натуральных чисел. Два– натуральное число,три – натуральное число,шесть – натуральное число,и этот результат единственный. Чтоеще нужно?Все сходится. А вот уже другой пример– один минуспять равноминусчетыре,все в томже множестве натуральных чисел. Один – натуральное число,пять – натуральное,а вот минусчетыре – уже нет!
Теперь разберемся стакими вещами,как ассоциативность и коммутативность. Этосовсем просто,только нужноиметь ввиду одну вещь:значком«*» отмечается не умножение,а любая операция,относительнокоторой ведется рассмотрение.
Ассоциативность |
x*(y*z) = (x*y)*z |
|
|
Коммутативность |
x*y = y*x |
|
|
Поздравляю,самое сложное уже позади. Теперь комбинируемполученнуюинформацию… и пошли определения. Для удобства они сведены вотвтакуютабличку
Каждое следующее определения включает в себя все предыдущие,плюсдополнительные условия,указанные вколонке «Расшифровка».
Название |
Расшифровка |
|
|
|
|
||
Группоид |
МножествоGсодной внутренней бинарной операцией |
||
|
|
|
|
Подгруппоид |
Замкнутость относительнооперации * (если х,у |
|
G’,тоx*y G’). |
|
|
||
|
Является подмножествомG’группоида (G;*) |
|
|
|
|
|
|
Полугруппа |
Ассоциативность x*(y*z)=(x*y)*z |
|
|
|
|
|
|
Моноид |
Единичный элемент (g*e=g) |
|
|
|
|
||
Группа |
Обратимость (для каждогоэлементаимеется обратный: |
||
|
g*g’=g’*g=e) |
|
|
|
|
|
|
Абелева группа |
Коммутативность (x*y = y*x) |
|
|
|
|
||
Кольцо |
МножествоR сдвумя внутренними операциями:«+» и «-», |
||
|
причем: |
|
|
|
1. R – абелева группа относительно«+» |
|
|
|
2. Операция умножения ассоциативна:x*(y*z)=(x*y)*z |
||
|
3. Для любых a,b,c R:a*(b+c)=a*b+a*c |
|
|
|
(b+c)*a=b*a+c*a |
|
|
Коммутативное кольцо |
Операция умножения – коммутативна:x*y = y*x |
|
|
|
|
||
Поле |
Этокоммутативное кольцо,ненулевые элементы которого |
||
|
образуют группу относительнооперации умножения |
||
|
|
|
|
Докольцавроде бы все понятно. Первое условие кольца тоже. А кчему тамнаписанопро коммутативность и ассоциативность умножения?Эторазве не всегда верно?А вот и нет. Делов том,что«х» и «у» -не обязательночисла! Этоможет быть все,чтоугодно.
Например,матрицы. А в такомслучаеx*y не равноy*x. Ну вот,опять кого-тозапутал. Тогда пример:
1 |
2 |
* |
5 |
6 |
= |
19 |
22 |
3 |
4 |
* |
7 |
8 |
= |
43 |
50 |
5 |
6 |
|
1 |
2 |
|
23 |
34 |
7 |
8 |
|
3 |
4 |
|
31 |
46 |
Тот самый случай,когда операция умножения – не коммутативна.
Вот,вроде бы,и все. С самымначаломразобрались.
Теперь перемещаемся нацелый семестрвперед иначинаемполноценный курс.
Классификация булевыхфункций.
Обозначим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) ( )
|
|
|
говорится,чторезультат булевой функции будет |
||
Такчтоже говорится в определении?(А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 инвертированийпеременных(группасдвигов).Состоит из преобразованийвида:
g= |
… |
|
,(a1…an) Vn. |
… |
Всеготакихпреобразований–2n («а»может принимать значение0или1,иихn штук)
3.ГруппаДжевонсаQn (группаоднотипностиилигеометрической эквивалентности).
Являетсяпроизведением группSn и∑n.Представляет собойпреобразованияв видеперестановкипеременныхиинвертированиинекоторыхизних.
g= |
… |
|
… |
где(j1…jn)–перестановкачисел (1…n)–дает размерность n! (a1…an) Vn –дает размерность 2n
Отсюда:|Qn|=n!* 2n
4.ГруппаGLn(2)–линейныхподстановок (полная линейнаягруппа). Представляет собойпреобразования:
g(x)=x*A,гдеА –двоичнаяматрицаразмераn xn (невырожденная)
g(x)=(x1…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:
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
f1 |
1 |
0 |
1 |
1 |
0 |
0 |
f2 |
1 |
2 |
1 |
1 |
1 |
0 |
f3 |
0 |
1 |
1 |
1 |
0 |
0 |
f4 |
0 |
0 |
1 |
1 |
1 |
1 |
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.