Выбрать книгу по жанру
Фантастика и фэнтези
- Боевая фантастика
- Героическая фантастика
- Городское фэнтези
- Готический роман
- Детективная фантастика
- Ироническая фантастика
- Ироническое фэнтези
- Историческое фэнтези
- Киберпанк
- Космическая фантастика
- Космоопера
- ЛитРПГ
- Мистика
- Научная фантастика
- Ненаучная фантастика
- Попаданцы
- Постапокалипсис
- Сказочная фантастика
- Социально-философская фантастика
- Стимпанк
- Технофэнтези
- Ужасы и мистика
- Фантастика: прочее
- Фэнтези
- Эпическая фантастика
- Юмористическая фантастика
- Юмористическое фэнтези
- Альтернативная история
Детективы и триллеры
- Боевики
- Дамский детективный роман
- Иронические детективы
- Исторические детективы
- Классические детективы
- Криминальные детективы
- Крутой детектив
- Маньяки
- Медицинский триллер
- Политические детективы
- Полицейские детективы
- Прочие Детективы
- Триллеры
- Шпионские детективы
Проза
- Афоризмы
- Военная проза
- Историческая проза
- Классическая проза
- Контркультура
- Магический реализм
- Новелла
- Повесть
- Проза прочее
- Рассказ
- Роман
- Русская классическая проза
- Семейный роман/Семейная сага
- Сентиментальная проза
- Советская классическая проза
- Современная проза
- Эпистолярная проза
- Эссе, очерк, этюд, набросок
- Феерия
Любовные романы
- Исторические любовные романы
- Короткие любовные романы
- Любовно-фантастические романы
- Остросюжетные любовные романы
- Порно
- Прочие любовные романы
- Слеш
- Современные любовные романы
- Эротика
- Фемслеш
Приключения
- Вестерны
- Исторические приключения
- Морские приключения
- Приключения про индейцев
- Природа и животные
- Прочие приключения
- Путешествия и география
Детские
- Детская образовательная литература
- Детская проза
- Детская фантастика
- Детские остросюжетные
- Детские приключения
- Детские стихи
- Детский фольклор
- Книга-игра
- Прочая детская литература
- Сказки
Поэзия и драматургия
- Басни
- Верлибры
- Визуальная поэзия
- В стихах
- Драматургия
- Лирика
- Палиндромы
- Песенная поэзия
- Поэзия
- Экспериментальная поэзия
- Эпическая поэзия
Старинная литература
- Античная литература
- Древневосточная литература
- Древнерусская литература
- Европейская старинная литература
- Мифы. Легенды. Эпос
- Прочая старинная литература
Научно-образовательная
- Альтернативная медицина
- Астрономия и космос
- Биология
- Биофизика
- Биохимия
- Ботаника
- Ветеринария
- Военная история
- Геология и география
- Государство и право
- Детская психология
- Зоология
- Иностранные языки
- История
- Культурология
- Литературоведение
- Математика
- Медицина
- Обществознание
- Органическая химия
- Педагогика
- Политика
- Прочая научная литература
- Психология
- Психотерапия и консультирование
- Религиоведение
- Рефераты
- Секс и семейная психология
- Технические науки
- Учебники
- Физика
- Физическая химия
- Философия
- Химия
- Шпаргалки
- Экология
- Юриспруденция
- Языкознание
- Аналитическая химия
Компьютеры и интернет
- Базы данных
- Интернет
- Компьютерное «железо»
- ОС и сети
- Программирование
- Программное обеспечение
- Прочая компьютерная литература
Справочная литература
Документальная литература
- Биографии и мемуары
- Военная документалистика
- Искусство и Дизайн
- Критика
- Научпоп
- Прочая документальная литература
- Публицистика
Религия и духовность
- Астрология
- Индуизм
- Православие
- Протестантизм
- Прочая религиозная литература
- Религия
- Самосовершенствование
- Христианство
- Эзотерика
- Язычество
- Хиромантия
Юмор
Дом и семья
- Домашние животные
- Здоровье и красота
- Кулинария
- Прочее домоводство
- Развлечения
- Сад и огород
- Сделай сам
- Спорт
- Хобби и ремесла
- Эротика и секс
Деловая литература
- Банковское дело
- Внешнеэкономическая деятельность
- Деловая литература
- Делопроизводство
- Корпоративная культура
- Личные финансы
- Малый бизнес
- Маркетинг, PR, реклама
- О бизнесе популярно
- Поиск работы, карьера
- Торговля
- Управление, подбор персонала
- Ценные бумаги, инвестиции
- Экономика
Жанр не определен
Техника
Прочее
Драматургия
Фольклор
Военное дело
Криптография и свобода - Масленников Михаил - Страница 38
Здесь и всюду далее нам будут встречаться два разных типа арифметических операций сложения и вычитания: в кольце Z/N и в поле GF(N+1). Операции в кольце Z/N будем обозначать обычными символами “+” и “-“, а операции в поле GF(N+1) – o и ㊀ соответственно.
Теорема 1.
Пусть П – логарифмическая подстановка, х1х2, х1,х2 ЄZ/N, i – произвольный ненулевой элемент кольца Z/N.
Тогда если ни одна из точек х1+i,x1,х2+i,x2 не является выколотой, то П(х1+i)- П(x1) П(х2+i)- П(x2).
Доказательство.
Предположим, что П(х1+i)- П(x1)= П(х2+i)- П(x2), тогда ФП(х1+i)- П(x1)=ФП(х2+i)- П(x2).
Поскольку все точки не являются выколотыми, то отсюда вытекает, что (Фх1+i+roр)(Фх2+roр)=(Фх2+i+roр)(Фх1+roр).
Раскрывая скобки и сокращая одинаковые члены в левой и правой частях равенства, получаем
р (Фx1+i+roФx2+r)= р(Фx2+i+roФx1+r)
Поскольку р – ненулевой элемент, то отсюда вытекает, что
Фx1+r(Фi㊀ 1)= Фx2+r(Фi㊀ 1)
Поскольку i – произвольный ненулевой элемент Z/N, а Ф – примитивный элемент GF(N+1), то Фi1, откуда вытекает, что х1=х2.■
Теорема 2. Пусть П – логарифмическая подстановка.
Тогда для любого ненулевого значения iЄZ/N\{0} из условия, что ни одна из точек x, x+i не является выколотой вытекает, что П(х+i)- П(x) i.
Доказательство.
Пусть П(х+i)- П(x) = i. Тогда ФП(х+i)- П(x)= Фi, откуда Фx+r+ioр=Фi(Фx+roр), следовательно, р=рФi. Отсюда следует, что i=0. ■
Раскинулось поле широко! Операции возведения в степень и логарифмирования в конечном поле позволили ловко избавиться от неопределенности в разности значений подстановки и легко, просто элементарно решить задачу построения матрицы P(П) с минимальным числом нулей. Заметим, что если в определении логарифмических подстановок отказаться от условия, что р – произвольный ненулевой элемент поля GF(N+1), то при р=0 мы получаем обычные линейные подстановки, у которых число нулей в P(П) максимально!
Осталось совсем чуть-чуть: разобраться с выколотой точкой.
Для произвольного ненулевого фиксированного iЄZ/N рассмотрим отображение множества Z/N в Z/N вида:
Mi(х) = П(х+i)- П(х),
где П – логарифмическая подстановка. Тогда, в силу теоремы 1, количество различных значений в множестве {Mi(х), xЄZ/N\{x,x-i}}равно мощности этого множества, т.е.N-2, причем, в силу теоремы 2, это множество в точности совпадает с {Z/N\{i}}. В частности, при любом iN/2 существует такое значение х, xЄZ/N\{x,x-i}, что Mi(х)=N/2.
Теорема 3. Пусть П – логарифмическая подстановка.
Тогда если при некотором iN/2 в i-ой строке матрицы P(П) справедливо piN/2>1, то эта строка не содержит нулевых элементов.
Доказательство.
В силу теоремы 2 достаточно доказать, что pii0. Условие piN/2>1означает, что либо Mi(х)=N/2, либо Mi(х-i)=N/2. Зафиксируем то, которое равно N/2, а другое оставшееся значение обозначим через M. Суммируя, как и ранее мы уже делали в этой книге, значения Mi(х) по всем xЄZ/N, получаем:
N/2(N-1) – i + M + N/2 = 0.
Отсюда вытекает, что M=i, следовательно, pii0. ■
По коням! Пора заняться средней строчкой.
Начнем с самого любимого элемента – pN/2,N/2. Ранее мы уже отмечали, что этот элемент должен быть всегда четным (рассуждения для случая N=2n легко обобщаются для произвольного четного N). Следовательно, в логарифмической подстановке возможны только два значения pN/2,N/2: 0 или 2. Допустим, что pN/2,N/2=2. В силу теоремы 2 эти значения может давать только выколотая точка x0 и x+N/2, т.е.
П(х+N/2)- П(х)= П(х+N/2+N/2)- П(х+N/2)= П(х)- П(х+N/2)=N/2.
Отсюда вытекает, что 2П(х+N/2)=2П(х).
Рассмотрим два случая.
1. р=1, следовательно, П(х)=0. Тогда П(х+N/2)=N/2. Имеем:
ФП(х0+N/2)= ФN/2 Фx0+N/2+roр=ФN/2 ФN/2(1㊀ Фx0+r)= р ФN/2(1oр)= р 2ФN/2 = 1.
Возводя обе части последнего равенства в квадрат и учитывая, что ФN=1, получаем такое равенство возможно только в тривиальном поле из 3 элементов.
2. р1, следовательно, П(х) =N/2, П(х+N/2)=0, откуда
ФП(х0+N/2)= 1 Фx0+N/2+roр=1 р(1㊀ ФN/2)= 1 ФN/2= 1㊀ р-1.
Возводя это равенство в квадрат, получаем значение р:
р=2-1
С учетом условия П(х) =N/2 получаем: logФ2-1 = N/2, откуда 2-1 =ФN/22-2 =1. Такое также возможно только в тривиальном поле из 3 элементов.
Следовательно, во всех реальных практически значимых случаях pN/2,N/2=0. Тогда найдется по крайней мере одна строка i, в которой pN/2,i2, и по теореме 3 в ней не будет нулей. Общее число нулей в такой матрице, с учетом уже упоминавшейся ее симметричности, будет равно N-3. Это минимально возможное количество нулей и оно оказалось достижимым!
Заметим, что подстановка, обратная к логарифмической, также будет логарифмической. Действительно, если П(х) = logФ(Фx+roр), то ФП (х)= Фx+roр, откуда
х= logФ(ФП (х)-roр1), где р1 = (㊀ р)Ф-r. Следовательно, П-1П(х) = logФ(ФП (х)-roр1). При этом ФП (х)-roр1=(Фx+roр)Ф-roр1=Фx 0. Для случая х=х справедливо: П(х)= logФр, при этом Фx0=(㊀ р)Ф-r, откуда х = П-1П(х) = logФ((㊀ р)Ф-r) = logФр1
Осталось построить в явном виде логарифмическую подстановку. Заметим, что условие N+1 – простое число выполняется для практически очень важного случая N=256, следовательно, логарифмические подстановки заведомо существуют при N=256. Условию N+1 – простое число удовлетворяет также N=16 и именно для этого значения мы сейчас и построим логарифмические подстановки, предоставляя заинтересованному читателю возможность построить логарифмические подстановки при N=256 самостоятельно.
В качестве примитивного элемента поля GF(17) выберем Ф=3, а также положим р=1, r=0. Составим таблицу степеней значения Ф:
Используя эту таблицу, построим логарифмическую подстановку П
и ее матрицу Р(П)
Это подстановка с минимально возможным числом нулей в матрице Р(П).
Это был, пожалуй, мой самый красивый математический результат. Но, к большому сожалению, логарифмические подстановки так и не нашли достойного применения в криптографии. Почему? Да очень просто – их мало. Помните фразу про долговременные ключи-подстановки в дисковых шифраторах: «Их не опробуют. Их покупают.» Если в схемы типа «Ангстрем-3» мы будем ставить только логарифмические подстановки, то опробование всевозможных вариантов подобных подстановок сведется к опробованию всего лишь трех элементов: Ф – примитивного элемента в поле Галуа GF(257), р – произвольного ненулевого элемента поля GF(257) и r – произвольного элемента из Z/256. Это – копейки, совершенно ничтожная, по криптографическим меркам, величина. Если же выбирать подстановку случайно и равновероятно из всей симметрической группы S256, то общее число опробуемых вариантов будет совершенно астрономической величиной 256!, намного превосходящей психологически недосягаемую в криптографии величину 10100.
- Предыдущая
- 38/77
- Следующая