Эта книга – «Аноним. Поточные шифры: Результаты зарубежной открытой криптологии» – появилась на свет в те годы, когда автора kiwi byrd не существовало даже в проекте. Соответственно, вся жизнь данного произведения в интернете проходит абсолютно самостоятельно.
Тем не менее, обстоятельства рождения книги таковы, что нет абсолютно никаких причин, которые могли бы помешать выложить её здесь. Для свободного доступа всем, кого подобные темы интересуют.
Общее представление о том, каким образом сформирована эта книга, дает предваряющий работу эпиграф из текстов античного автора Диогена Лаэртского:
Некоторые говорят, что Пифагор не оставил ни одного сочинения, но они ошибаются. Гераклит-физик едва ли не кричит: «Пифагор, Мнесархов сын, занимался собиранием сведений больше всех людей на свете и, понадергав себе эти сочинения, выдал за свою собственную мудрость многознайство и мошенничество»…
Скачать книгу «Поточные шифры» можно тут: PDF, 4 Мб
Более развернутое представление о содержании работы вполне дает
ОГЛАВЛЕНИЕ
Глава 0. Введение
0.1 Базовая терминология и общие положения … 1
0.2 Концепция Рюппеля о четырех подходах к конструированию поточных
шифров … 4
0.3 Классификация поточных шифров … 6
0.3.1 Синхронные поточные шифры и псевдослучайные генераторы … 7
0.3.2 Самосинхронизирующиеся поточные шифры и скрэмблеры … 8
Глава 1. Подход теории информации
1.1 Эпохи в криптологии … 10
1.2 Шенноновская модель криптоанализа … 11
1.3 Локальная рандомизация … 13
1.4 Практическая стойкость … 14
Глава 2. Строительные блоки для создания криптосхем
2.1 Конгруэнтные генераторы … 16
2.1.1 Генераторы псевдослучайных чисел … 16
2.1.2 Комбинирование ЛКГ и программная реализация … 18
2.2 Криптоанализ конгруэнтных генераторов … 20
2.2.1 Вскрытие конгруэнтных генераторов (неусеченных) … 21
2.2.2 Усеченные линейные конгруэнтные генераторы с известными
параметрами … 22
2.2.3 Усеченные линейные конгруэнтные генераторы с неизвестными
параметрами … 24
2.3 Регистры сдвига … 24
2.3.1 Алгебраические свойства регистров сдвига с линейной обратной связью … 25
2.3.2 РСЛОС максимального периода и примитивные многочлены … 27
2.3.3 Регистры Фибоначчи и Галуа, и их программная реализация … 29
2.4 Некоторые итоги … 33
Глава 3. Статистические свойства и меры сложности последовательностей
3.0 Подходы к анализу … 35
3.1 Статистические свойства последовательностей … 36
3.1.1 Постулаты Голомба … 36
3.1.2 Статистические тесты … 37
3.1.2.1 Теоретический фундамент … 37
3.1.2.2 Частотный тест … 38
3.1.2.3 Последовательный тест … 38
3.1.2.4 Тест серий … 39
3.1.2.5 Автокорреляционный тест … 39
3.1.2.6 Универсальный тест … 39
3.1.2.7 Тест повторений … 41
3.1.2.8 Сравнение тестов l-грамм … 42
3.1.2.9 Комбинирование тестов … 42
3.1.3 Отсечение слабых последовательностей … 43
3.2 Линейная сложность последовательностей и преобразования … 43
3.2.1 Концепция линейной сложности … 43
3.2.2 Алгоритм линейного синтеза Берлекампа-Мэсси … 44
3.2.3 Естественная интерпретация алгоритма Берлекампа-Мэсси … 47
3.2.4 Другие методы анализа линейной сложности … 50
3.2.5 Преобразования … 51
3.2.5.1 Дискретное преобразование Фурье и линейная сложность … 51
3.2.5.2 Преобразование Уолша и булевы функции … 53
3.2.5.3 Преобразование алгебраической нормальной формы … 54
3.2.6 Профиль линейной сложности … 56
3.3 Периодические последовательности … 57
3.3.1 Прагматические соображения … 57
3.3.2 Теоретический анализ периодических последовательностей … 58
3.4 Суммы и произведения периодических последовательностей … 59
3.4.1 Суммы периодических последовательностей … 59
3.4.2 Произведения периодических последовательностей … 60
3.4.3 Общая нижняя граница для линейной сложности произведения … 61
3.5 Другие меры сложности … 64
3.5.1 Общие результаты … 64
3.5.2 Квадратичный размах… 65
3.5.3 Деревья суффиксов … 66
3.6 Вместо резюме: две стороны теоретико-системного подхода … 68
Глава 4. Базовые схемы и их криптоанализ
4.0 Функции от периодических последовательностей … 69
4.1 Фильтрующий генератор … 70
4.1.1 Линейная сложность фильтр-генератора … 70
4.1.2 Алгоритм для оценки линейного размаха нелинейно фильтруемых последовательностей … 72
4.2 Комбинирующий генератор … 77
4.3 Корреляционные методы вскрытия комбинирующих генераторов … 80
4.3.0 Общий обзор … 80
4.3.1 Базовая корреляционная атака Зигенталера … 84
4.3.2 Быстрая корреляционная атака Майера и Штаффельбаха.. 86
4.3.3 Метод Пенцхорна для нахождения низковесовых полиномов
проверки четности … 89
4.3.4 Метод итерационного вероятностного декодирования
Михалевича-Голича … 94
4.3.5 Метод Маккея: алгоритм минимизации свободной энергии … 97
4.3.6 Сравнение алгоритмов и проблема сходимости … 102
4.4 Вскрытие фильтр-генераторов… 104
4.4.0 Основные результаты.. 104
4.4.1 Метод Зигенталера: криптоаналитическое представление
фильтр-генератора… 105
4.4.2 Модель Андерсона: на пути к «оптимальной корреляционной атаке» … 107
4.4.3 Математическая модель атаки Андерсона … 110
4.4.4 Инверсионная атака Голича … 111
4.4.5 Множества положительных разностей и корреляционный иммунитет … 114
4.4.6 Критерии обеспечения стойкости нелинейных фильтр-генераторов … 117
Глава 5. Криптографические функции. Критерии нелинейности и методы конструирования
5.0 Общий обзор … 119
5.1 Корреляционный иммунитет порядка k.. 122
5.1.1 Базовые понятия и результаты для узлов без памяти … 122
5.1.2 Конструирование корреляционно-иммунных функций … 124
5.1.3 Корреляционный иммунитет и автомат с памятью … 126
5.2 Классификация Майера-Штаффельбаха для критериев нелинейности … 129
5.2.1 Расстояние до линейных функций … 130
5.2.2 Функции с линейной структурой … 131
5.2.3 Совершенные нелинейные функции … 131
5.3 Бент-функции … 132
5.3.1 Конструкция Маиораны-Макфарленда и бент-отображения Нюберг … 133
5.3.2 Конструкции Карле … 134
5.3.3 Общая конструкция Доббертина … 137
5.4 Критерий распространения и эластичные функции … 141
5.4.1 Строгий лавинный критерий и критерий распространения … 141
5.4.2 Конструирование булевых функций, удовлетворяющих критериям
сбалансированности, нелинейности и распространения … 142
5.4.2.1 Базовые понятия и аппарат адамаровых матриц.. 142
5.4.2.2 Конкатенация и расщепление последовательностей.. 145
5.4.2.3 Модификация и перемножение последовательностей.. 147
5.4.2.4 Высоко нелинейные сбалансированные функции, удовлетворяющие
критерию распространения большой степени… 149
5.4.3 Эластичные функции … 150
5.4.3.1 Свойства эластичных функций … 150
5.4.3.2 Конструирование новых эластичных функций из уже известных … 151
5.4.3.3 Преобразование линейных эластичных функций в нелинейные … 152
5.5 Рекомендации конструкторам криптосхем … 153
Глава 6. Схемы с неравномерным движением регистров и без памяти
6.0 Неравномерное движение как способ достижения нелинейности … 154
6.1 Общий обзор конструкций с неравномерным движением регистров … 155
6.1.1 Схемы с управляющим регистром, их период и линейная сложность … 155
6.1.1.1 Базовая схема, генераторы «стоп-вперед» и «один-два шага» … 155
6.1.1.2 Период и линейная сложность … 156
6.1.1.3 Генератор с перемежающимся шагом … 158
6.1.1.4 Каскадный генератор … 159
6.1.1.5 Сжимающий генератор … 160
6.1.2 Схемы с самоуправлением … 161
6.1.2.1 Генератор [d,k]-самоусечения … 161
6.1.2.2 Самосжимающий генератор … 162
6.2 Каскадные генераторы … 163
6.2.1 Криптографические свойства «шагk,m»-каскадов … 164
6.2.2 Криптоанализ каскадов … 166
6.2.3 Систематическая атака Меникоччи … 169
6.3 Сжимающий и самосжимающий генераторы … 173
6.3.1 Сжимающий генератор … 173
6.3.1.1 Конструкция, период, линейная сложность и статистические свойства … 173
6.3.1.2 Приложение преобразования Фурье и -смещенных распределений
в анализе регистров с переменными точками съема и СГ … 175
6.3.1.3 Криптоаналитические подходы к вскрытию схемы … 178
6.3.1.4 Аспекты аппаратной и программной реализации … 179
6.3.2 Сжимающий Фибоначчи-генератор (Fish) и его вскрытие … 180
6.3.2.1 Обобщенный сжимающий генератор и алгоритм Fish … 180
6.3.2.2 Вскрытие криптосхемы Fish … 181
6.3.3 Самосжимающий генератор … 184
6.3.3.1 Сжатие и самосжатие … 185
6.3.3.2 Период и линейная сложность, примеры и экспериментальные результаты … 185
6.3.3.3 Криптоанализ … 187
6.4 Вскрытие схем с неравномерным движением … 190
6.4.1 Краткий обзор основных результатов … 190
6.4.2 Восстановление начального заполнения регистра
на основе новой меры расстояния между последовательностями … 192
6.4.3 Атака встраиванием и вероятностная корреляционная атака … 196
6.4.4 Восстановление полинома обратной связи и
быстрая корреляционная атака … 200
Глава 7. Схемы с памятью
7.1 Общий обзор … 208
7.1.1 Схемы с равномерным движением и памятью … 208
7.1.2 Схемы на регистрах сдвига с операцией переноса … 209
7.1.3 Схемы с неравномерным движением и памятью … 212
7.2Корреляционные свойства комбинирующих узлов с 1 битом памяти … 213
7.2.1 Базовая схема сумматора … 213
7.2.2 Обобщенный комбинирующий узел с 1 битом памяти … 214
7.2.3 Корреляция, обусловленная известным выходом … 216
7.2.4 Криптоанализ сумматора с двумя входами … 217
7.3 Комбинирующий узел с произвольным числом бит памяти … 219
7.3.1 Обобщенный двоичный комбинирующий узел с памятью
и корреляционные свойства векторных булевых функций … 219
7.3.2 Корреляционные свойства комбинирующих узлов с памятью … 222
7.3.3 Метод аппроксимации линейной последовательной схемой … 224
7.3.4 Корреляционная атака … 227
7.4 Регистры сдвига с переносом и 2-адический анализ … 228
7.4.1 Обзор 2-адических чисел … 229
7.4.2 Регистры сдвига с памятью, их реализация, требования к памяти … 230
7.4.3 Анализ РСОСП … 232
7.4.4 2-адический размах и сложность … 235
7.4.5 Алгоритм рациональной аппроксимации … 237
7.4.6 2-адический криптоанализ сумматора … 239
7.4.7 Длинные последовательности и их статистические свойства … 240
7.4.8 РСОСП максимального периода и криптосхемы на их основе … 241
Глава 8. Конкретные схемы криптогенераторов и самосинхронизирующиеся шифры
8.1 Обзор ранних схем … 245
8.1.1 Генератор Геффе … 245
8.1.2 Генератор Плесса … 246
8.1.3 Генератор-мультиплексор Дженнингса … 247
8.1.4 Пороговый генератор … 248
8.1.5 Генератор скалярного перемножения … 249
8.1.6 Генератор Вольфрама … 250
8.1.7 Генератор «1/p» … 251
8.1.8 Генератор суммирования … 253
8.1.9 Ранцевый генератор … 254
8.1.10 Аддитивный генератор … 255
8.1.11 Генератор Гиффорда … 256
8.2 Алгоритм А5 … 257
8.2.1 Описание криптосхемы … … 257
8.2.2 Криптоанализ шифра … 259
8.3 Алгоритм RC4 … 260
8.3.1 Описание криптосхемы … 260
8.3.2 Криптоанализ … 262
8.4 Алгоритм SEAL … 263
8.4.1 Семейство псевдослучайных функций … 263
8.4.2 Особенности SEAL.. 264
8.4.3 Описание алгоритма … 265
8.4.4 Стойкость SEAL.. 268
8.5 Обзор криптосхем 1990-х годов … 268
8.5.1 Фильтр-генератор на основе алгоритма сжатия данных Зива-Лемпела … 268
8.5.2 Модифицированный линейный конгруэнтный генератор (Чамберса) … 271
8.5.3 Каскад с неравномерным движением (Чамберса) … 273
8.5.4 Алгоритм WAKE… 275
8.5.5 Алгоритм PIKE.. 276
8.5.6 Алгоритм GOAL.. 277
8.5.7 Алгоритм ORYX… 278
8.5.8 Генератор ISAAC.. 280
8.5.9 Chameleon — новое приложение криптографии … 283
8.6 Самосинхронизирующиеся шифры … 284
8.6.1 Концептуальная схема … 285
8.6.2 Рекурсивная архитектура Маурера … 286
8.6.3 Схема Дэмена на регистре сдвига с условным дополнением … 287
Глава 9. Новые методы криптоанализа
9.1 Метод «встреча посередине» … 290
9.2 Криптографические слабости ресинхронизаций … 291
9.2.1 Типы ресинхронизаций и их интерпретация … 292
9.2.2 Общая атака нелинейно фильтруемых систем … 294
9.2.3 Атака мультиплексор-генератора … 296
9.3 Дифференциальный криптоанализ … 297
9.3.1 Аддитивный естественный поточный шифр … 297
9.3.2 Дифференциальная атака … 298
9.3.3 Теоретический базис атаки … 299
9.4 Линейный криптоанализ … 300
9.4.1 Линейные модели поточных шифров … 300
9.4.2 Линейный анализ генераторов на основе регистров сдвига … 302
9.5 Методы дискретной оптимизации: симулятор отжига и генетический алгоритм 9.5.1 Симулятор отжига и алгоритм Метрополиса … 302
9.5.2 Корреляционная атака, модифицированная симулятором отжига … 305
9.5.3 Генетические алгоритмы … 306
9.6 Оптимизация тотального перебора ключей … 307
9.7 О существовании стойких регистров сдвига … 310
9.7.1 Концептуальная модель … 310
9.7.2 Определения … 311
9.7.3 Существование стойких РСОС … 313
9.7.4 Атаки линейного синтеза … 315
Глава 10. Альтернативные конструкции
10.0 Взгляды на теорию стойкости … 317
10.1 Подход с позиций теории сложности … 319
10.1.1 Базовые идеи и концепции … 320
10.1.2 Генераторы … 322
10.1.2.1 Псевдослучайный генератор Шамира … 322
10.1.2.2 Генератор Блюма-Микали … 324
10.1.2.3 Генераторы RSA.. 326
10.1.2.4Генератор квадратичных вычетов … 327
10.2 Рандомизированные шифры … 329
10.2.1 Шифр Диффи … 330
10.2.2 Шифр «Рип ван Винкль» … 330
10.2.3 Шифр Маурера … 332
10.3 Хаотические шифры … 333
10.4 Система гаммирования POTP… 334
Глава последняя. Заключение
I. Современная ситуация в открытой криптографии … 337
II. Критерии для сравнения алгоритмов … 338
III. Программные и аппаратные шифры … 338
IV. Развитие теории … 339
V. Жизнь в реальном мире … 339
Библиография..341
Англо-русский предметный указатель …369
Русско-английский предметный указатель …378
#
Всем, кто сумел дочитать Оглавление до конца, но не уловил смысл фразы в названии публикации, можно напомнить один старый советский анекдот из эпохи застоя:
Два алкаша обсуждают, что купить их третьему другу в подарок:
– А давай подарим ему книгу!
– Нее, книга у него уже есть…
The END
kiwi arXiv 