Книга: Фомичев В. М. «Дискретная математика и криптология»

Книга написана ведущим специалистом в области криптологии, имеющим многолетний опыт преподавания в МИФИ.
Изложены базовые вопросы криптологии и необходимые для их изучения основы математического аппарата. С целью закрепления материала даны задачи и упражнения.
Рекомендуется для студентов, аспирантов, изучающих дисциплины по криптологии и компьютерной безопасности, преподавателей, а также практических работников, имеющих дело с криптографическими методами защиты информации.

Содержание:

ВСТУПИТЕЛЬНОЕ СЛОВО...... 3 ПРЕДИСЛОВИЕ...... 4 Часть I. ИЗБРАННЫЕ ГЛАВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ Глава 1. МНОЖЕСТВА И ОТОБРАЖЕНИЯ...... 8 1. 1. Понятие множества...... 8 1. 2. Подмножества и операции над множествами...... 9 1. 3. Системы подмножеств множества...... 10 1. 4. Частично упорядоченные множества...... 14 1. 5. Свойства некоторых решеток...... 17 1. 6. Графы...... 20 1. 7. Отображения множеств...... 25 1. 8. Задачи и упражнения...... 29 Глава 2. АЛГЕБРАИЧЕСКИЕ ОСНОВЫ...... 32 2. 1. Операции, полугруппы, группы...... 32 2. 2. Кольца и поля...... 37 2. 3. Некоторые свойства матриц...... 39 2. 4. Векторные пространства...... 41 2. 5. Конечные расширения полей...... 43 2. 6. Задачи и упражнения...... 46 Глава 3. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ...... 49 3. 1. Элементарные булевы функции...... 49 3. 2. Реализация функций формулами...... 51 3. 3. Разложение булевых функций по переменным...... 52 3. 4. Полнота и замкнутость системы функций...... 54 3. 5. Важнейшие замкнутые классы...... 56 3. 6. Критерий полноты системы булевых функций...... 61 3. 7. Основные способы задания булевых функций...... 65 3. 8. Связь различных представлений функций...... 72 3. 9. Понятие о классификации двоичных функций...... 77 3. 10. Задачи и упражнения...... 84 Глава 4. ФУНКЦИИ k-ЗНАЧНОЙ ЛОГИКИ...... 90 4. 1. Начальные понятия и элементарные функции...... 90 4. 2. Важные классы функций k-значной логики...... 93 4. 3. Примеры полных систем в Pk...... 95 4. 4. Распознавание полноты и критерии полноты в Pk...... 97 4. 5. Особенности k-значных логик...... 100 4. 6. Задачи и упражнения...... 102 Глава 5. СБАЛАНСИРОВАННОСТЬ ОТОБРАЖЕНИЙ...... 105 5. 1. О связи отображений с системами функций...... 105 5. 2. Критерии сбалансированности отображений...... 106 5. 3. Критерии биективности преобразований...... 109 5. 4. Некоторые классы отображений...... 110 5. 5. Задачи и упражнения...... 116 Глава 6. СТРУКТУРА И ПЕРИОДЫ ПРЕОБРАЗОВАНИЙ...... 120 6. 1. Периоды последовательностей...... 120 6. 2. Граф отображения...... 122 6. 3. Характеристики периодичности преобразования...... 124 6. 4. Полноцикловые преобразования...... 126 6. 5. Линейные регистры сдвига...... 131 6. 6. Аффинные преобразования максимального периода...... 133 6. 7. Задачи и упражнения...... 136 Глава 7. ПСЕВДОСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ...... 138 7. 1. Подходы к анализу последовательностей...... 138 7. 2. Линейные рекуррентные последовательности...... 139 7. 3. Линейная сложность последовательностей...... 140 7. 4. Статистические требования к последовательностям...... 145 7. 5. Статистическое тестирование последовательностей...... 148 7. 6. Задачи и упражнения...... 153 Глава 8. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА НЕЛИНЕЙНЫХ ОТОБРАЖЕНИЙ...... 155 8. 1. Перемешивающие свойства отображений...... 155 8. 2. Совершенность композиции преобразований...... 157 8. 3. Усиление свойства совершенности...... 160 8. 4. Алгебраические характеристики нелинейности...... 163 8. 5. Линейный синдром при итерациях...... 166 8. 6. Приближения нелинейных отображений...... 169 8. 7. Задачи и упражнения...... 172 Глава 9. КОНЕЧНЫЕ АВТОМАТЫ МИЛИ...... 176 9. 1. Функционирование автомата, виды автоматов...... 176 9. 2. Способы задания автоматов Мили...... 178 9. 3. Отношения и операции с автоматами...... 181 9. 4. Различимость состояний и входов...... 183 9. 5. Периодичность в конечных автоматах...... 187 9. 6. Задачи и упражнения...... 190 Часть II. ОСНОВЫ КРИПТОЛОГИИ Глава 10. ОСНОВНЫЕ ПОНЯТИЯ И ЗАДАЧИ КРИПТОЛОГИИ...... 194 10. 1. Задачи криптографии...... 194 10. 2. Основные понятия криптологии...... 195 10. 3. Симметричные и асимметричные шифрсистемы...... 197 10. 4. Понятие о криптографических протоколах...... 198 10. 5. Организация секретной связи, задачи криптоаналитика...... 199 10. 6. Обеспечение целостности сообщений...... 205 10. 7. Цифровая подпись...... 206 Глава 11. КЛЮЧЕВАЯ СИСТЕМА ШИФРА...... 211 11. 1. Строение и порядок ключевого множества...... 211 11. 2. Вероятностная модель ключевого множества...... 212 11. 3. Генерация ключей...... 213 11. 4. Обеспечение секретности ключей...... 214 11. 5. Протоколы обмена ключами...... 219 Глава 12. ИСТОЧНИКИ ОТКРЫТЫХ ТЕКСТОВ...... 229 12. 1. Характеристики открытых текстов...... 229 12. 2. Детерминированные модели...... 230 12. 3. Вероятностные модели...... 231 Глава 13. КРИПТОГРАФИЧЕСКАЯ СТОЙКОСТЬ ШИФРОВ...... 238 13. 1. Вероятностные модели шифра...... 238 13. 2. Совершенно стойкие шифры...... 239 13. 3. Системный подход к оценке практической стойкости шифров...... 242 13. 4. Другие подходы к оценке практической стойкости шифров...... 246 Глава 14. ШИФРЫ ПЕРЕСТАНОВКИ И ЗАМЕНЫ...... 249 14. 1. Шифры перестановки...... 249 14. 2. Шифры замены...... 252 Глава 15. ШИФРУЮЩИЕ АВТОМАТЫ...... 259 15. 1. Математические модели шифра...... 259 15. 2. Автоматная модель симметричного шифра...... 260 15. 3. Отношения и операции с шифрующими автоматами...... 263 15. 4. Моноключевые шифрующие автоматы...... 265 15. 5. Криптографические генераторы...... 266 15. 6. Эквивалентность ключей и шифрующих автоматов...... 268 15. 7. Различимость входов...... 272 15. 8. Задачи и упражнения...... 273 Глава 16. ПОТОЧНЫЕ ШИФРЫ...... 275 16. 1. Различия между поточными и блочными шифрами...... 275 16. 2. Синхронные поточные шифры...... 276 16. 3. Самосинхронизирующиеся поточные шифры...... 280 16. 4. Шифры гаммирования...... 282 16. 5. Криптографические свойства поточных шифров...... 282 16. 6. Задачи и упражнения...... 289 Глава 17. СИММЕТРИЧНЫЕ БЛОЧНЫЕ ШИФРЫ...... 291 17. 1. Сравнение характеристик асимметричных и симметричных блочных шифров...... 291 17. 2. Принципы построения блочных шифров...... 291 17. 3. Слабые ключи итеративного шифра...... 304 17. 4. Режимы шифрования...... 306 17. 5. Усложнение симметричных блочных шифров...... 314 17. 6. Задачи и упражнения...... 316 Глава 18. КРИПТОГРАФИЧЕСКИЕ ГЕНЕРАТОРЫ...... 318 18. 1. Элементная база криптосхем...... 318 18. 2. Фильтрующие генераторы...... 319 18. 3. Комбинирующие генераторы...... 321 18. 4. Корреляционные атаки...... 326 18. 5. Генераторы гаммы с неравномерным движением...... 327 18. 6. Генераторы с дополнительной памятью...... 335 18. 7. Задачи и упражнения...... 339 ПРИЛОЖЕНИЯ...... 341 1. Алгоритм шифрования DES...... 341 2. Алгоритм ГОСТ 28147–89...... 345 3. Блочный шифр IDEA...... 347 4. RIJNDAEL...... 350 5. Стандарт генерации ключей ANSI Х 9. 17...... 357 6. Алгоритм А 5/1...... 358 7. Американский стандарт хеш-функции (SHS)...... 359 8. Криптосистема RSA...... 361 9. Шифрсистема Эль Гамаля...... 363 10. Схема цифровой подписи Эль Гамаля...... 364 Ответы и решения...... 365 Словарь...... 372 Литература...... 386

Издательство: "Диалог-МИФИ" (2003)

ISBN: 5864041858