Криптографические методы защиты информации
Учебно-методическое пособие: Том 1
Покупка
Основная коллекция
Многотомное издание:
Том 1 (2021)
Издательство:
РИОР
Автор:
Бабаш Александр Владимирович
Год издания: 2021
Кол-во страниц: 413
Дополнительно
Вид издания:
Учебно-методическая литература
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-369-01267-3
ISBN-онлайн: 978-5-16-103992-2
Артикул: 447550.06.01
Доступ онлайн
В корзину
Пособие предназначено для студентов высших учебных заведений, обучающихся по специальности «Прикладная информатика (в экономике)». Оно также содержит методический материал для ряда инновационных курсов лекций по профилю «Информационная безопасность» и может быть использовано для блока дисциплин этого профиля. Ряд представленных результатов полезен специалистам и аспирантам, специализирующимся в указанной области.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 01.03.02: Прикладная математика и информатика
- 02.03.02: Фундаментальная информатика и информационные технологии
- 09.03.02: Информационные системы и технологии
- 09.03.03: Прикладная информатика
- 10.03.01: Информационная безопасность
- ВО - Магистратура
- 01.04.02: Прикладная математика и информатика
- 02.04.02: Фундаментальная информатика и информационные технологии
- 09.04.02: Информационные системы и технологии
- 09.04.03: Прикладная информатика
- 10.04.01: Информационная безопасность
- ВО - Специалитет
- 10.05.04: Информационно-аналитические системы безопасности
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
ВЫСШЕЕ ОБРАЗОВАНИЕ - БАКАЛАВРИАТ серия основана в 1 996 г. А.В. БАБАШ КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ Том 1 УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ Второе издание, переработанное и дополненное Рекомендовано Учебно-методическим объединением по образованию в области прикладной информатики в качестве учебно-методического пособия для студентов высших учебных заведений, обучающихся по специальности «Прикладная информатика» и другим междисциплинарным специальностям znanium.com Москва РИОР ИНФРА-М
УДК 004.056(075.8) ББК 32.973.202я73 Б12 ФЗ Издание не подлежит маркировке № 436-ФЗ в соответствии с п. 1 ч. 4 ст. 11 Автор: Бабаш А.В. —д-р физ.-мат. наук, профессор, Российский экономический университет им. Г.В. Плеханова Бабаш А.В. Б12 Криптографические методы защиты информации. Т. 1 : учеб.-метод. пособие / А.В. Бабаш. — 2-е изд., перераб. и доп. — М. : РИОР : ИНФРА-М, 2019. — 413 с. — (Высшее образование: Бакалавриат). — DOI: https://doi. org/10.12737/14413 ISBN 978-5-369-01267-3 (РИОР) ISBN 978-5-16-009048-1 (ИНФРА-М, print) ISBN 978-5-16-103992-2 (ИНФРА-М, online) Пособие предназначено для студентов высших учебных заведений, обучающихся по специальности «Прикладная информатика (в экономике)». Оно также содержит методический материал для ряда инновационных курсов лекций по профилю «Информационная безопасность» и может быть использовано для блока дисциплин этого профиля. Ряд представленных результатов полезен специалистам и аспирантам, специализирующимся в указанной области. УДК 004.056(075.8) ББК 32.973.202я73 ISBN 978-5-369-01267-3 (РИОР) ISBN 978-5-16-009048-1 (ИНФРА-М, print) ISBN 978-5-16-103992-2 (ИНФРА-М, online) © Бабаш А.В. Оригинал-макет подготовлен в Издательском Центре РИОР Подписано в печать 18.03.2019. Формат 60x90/8. Бумага офсетная. Гарнитура BookAntiqua. Печать офсетная. Усл. печ. л. 51,75. Уч.-изд. л. 53,87. Доп. тираж 20 экз. Заказ № Цена свободная. ТК 447550 - 1022055 - 180319 ООО «Издательский Центр РИОР» 127282, Москва, ул. Полярная, д. 31В. E-mail: info@riorp.ru https://riorpub.com ООО «Научно-издательский центр ИНФРА-М» 127282, Москва, ул. Полярная, д. 31В, стр. 1. Тел.: (495) 280-15-96. Факс: (495) 280-36-29. E-mail: books@infra-m.ru http://www.infra-m.ru Отпечатано в типографии ООО «Научно-издательский центр ИНФРА-М» 127282, Москва, ул. Полярная, д. 31В, стр. 1. Тел.: (495) 280-15-96, 280-33-86. Факс: (495) 280-36-29.
СОДЕРЖАНИЕ Введение....................................................................... 7 Часть 1. ОСНОВЫ КРИПТОГРАФИИ Глава 1. Модели шифров по К. Шеннону. Способы представления реализаций шифров.. 8 1.1. Алгебраическая модель шифра............................................ 8 1.2. Примеры моделей шифров................................................. 9 1.3. Свойства шифров....................................................... 12 1.4. Вероятностная модель шифра............................................ 14 1.5. Совершенные шифры..................................................... 14 1.6. Способы представления реализаций шифров............................... 15 1.7. Основные понятия теории автоматов................................... 16 Глава 2. Блочные шифры........................................................ 19 2.1. Блочный шифр DES...................................................... 21 2.2. Основные режимы работы алгоритма DES.................................. 28 2.3. Области применения алгоритма DES...................................... 31 2.4. Алгоритм шифрования данных IDEA....................................... 33 2.5. Отечественный стандарт шифрования данных.............................. 35 Глава 3. Поточные шифры....................................................... 46 3.1. Шифры гаммирования.................................................... 53 3.2. Поточный шифр гаммирования RC4........................................ 54 Глава 4. Идея открытого ключа — революция в криптографии...................... 55 4.1. Модель системы связи с открытым ключом................................ 58 4.2. Принципы построения криптосистем с открытым ключом.................... 61 4.3. Схема цифровой подписи с использованием однонаправленной функции...... 63 4.4. Открытое распределение ключей Диффи-Хеллмана.......................... 63 Глава 5. Недостатки модели шифра К. Шеннона. Обобщенная модель шифра........ 65 Глава 6. Дешифрование простейших шифров..................................... 68 6.1. Дешифрование шифра перестановки....................................... 69 6.2. Дешифрование шифра гаммирования при некачественной гамме.............. 73 6.3. О дешифровании фототелеграфных изображений............................ 76 6.4. Дешифрование шифра гаммирования при перекрытиях....................... 77 Глава 7. Дешифрование шифра Виженера.......................................... 80 7.1. Задача определения периода гаммы в шифре гаммирования по заданному шифртексту.................................................... 89 7.2. Возможности переноса изложенных результатов на шифры поточной замены (ПЗ) 97 Глава 8. Общее понятие информации. Способы представления информации, подлежащей шифрованию. Дискретизация непрерывных сигналов.................... 103 Глава 9. Открытые сообщения и их характеристики.............................. 108 9.1. Вероятностные источники сообщений................................... 110 9.2. О числе осмысленных текстов, получаемых в стационарном источнике независимых символов алфавита............................................ 111 9.3. Критерии на осмысленные сообщения.................................... 114 9.4. Частотные характеристики осмысленных сообщений....................... 118 Глава 10. Основные понятия и теоремы математической теории информации....... 120 Глава 11. Стационарные эргодические модели содержательных сообщений......... 128 3
Глава 12. Энтропии шифртекстов и ключей.......................................... 131 Глава 13. Расстояния единственности шифра........................................ 134 13.1. Расстояния единственности для открытого текста и ключа................. 134 13.2. Расстояние единственности шифра гаммирования с неравновероятной гаммой. 139 Глава 14. О вероятности определения ключа по шифртексту фиксированной длины в модели случайного шифра.................................................. 142 Глава 15. Теоретическая стойкость шифров......................................... 147 Часть 2. ПРАКТИЧЕСКАЯ СТОЙКОСТЬ ШИФРОВ Глава 16. Понятие практической стойкости шифров.................................. 148 16.1. Типовые задачи криптоанализа............................................ 148 16.2. Базовые подходы к оценке стойкости шифров............................... 149 Глава 17. Принципы построения методов определения ключей шифрсистем............. 153 Глава 18. Методы опробования..................................................... 157 18.1. Методы использования эквивалентных ключей............................... 161 18.2. Метод опробования с использованием памяти............................... 164 18.3. Модификация метода опробования с использованием памяти.................. 166 18.4. Метод расшифровки черного ящика......................................... 166 18.5. Метод упорядоченного опробования в задаче определения входного слова автомата....................................................... 168 18.6. Опробование в методе использования гомоморфизмов........................ 170 18.7. Опробование в методе согласования («встреча по середине»)............... 172 18.8. Опробование в методе согласования для определения начального состояния последовательного соединения автоматов.............................. 173 18.9. Опробование в алгоритме согласования для вычисления дискретного логарифма.... 178 Глава 19. Принципы построения статистических методов криптоанализа............... 181 19.1. Метод «разделяй и побеждай»............................................. 181 19.2. Задачи восстановления ключа шифрующего автомата A....................... 182 19.3. Корреляционные атаки на поточные шифры................................. 186 19.4. Метод статистических аналогов........................................... 190 19.5. Статистический метод определения пары: входного слова и начального состояния конечного автомата..................................... 191 19.6. Метод разностного анализа определения входного слова конечного автомата. 192 19.7. Метод линейного криптоанализа определения входного слова автомата....... 193 Глава 20. Аналитические методы криптоанализа..................................... 195 20.1. Решение систем линейных уравнений....................................... 195 20.2. Методы решения систем нелинейных уравнений.............................. 199 Глава 21. Типовые вероятностные подзадачи методов криптоанализа.................. 203 Часть 3. СИНТЕЗ СИММЕТРИЧНЫХ ШИФРОВ И ИХ КРИПТОСХЕМ Глава 22. Шифры, близкие к совершенным шифрам.................................... 207 Глава 23. Гомоморфизмы и конгруэнции шифров...................................... 212 Глава 24. Групповые шифры. Обратимые групповые шифры............................. 215 Глава 25. Инварианты шифров...................................................... 219 Глава 26. Введение в вопросы синтеза криптосхем.................................. 221 Глава 27. Статистическая структура двоичной функции.............................. 223 Глава 28. Регистры сдвига, одноканальные линии задержки......................... 228 4
Часть 4. ИМИТОСТОЙКОСТЬ ШИФРОВ, ПОМЕХОУСТОЙЧИВОСТЬ ШИФРОВ, СЕТИ ЗАСЕКРЕЧЕННОЙ СВЯЗИ Глава 29. Имитостойкость шифров в модели К. Шеннона.......................... 235 Глава 30. Примеры имитации и способы имитозащиты............................. 241 Глава 31. Помехоустойчивые шифры............................................. 244 31.1. Общие понятия и определения......................................... 244 31.2. Шифры, не размножающие искажений типа «замена»...................... 245 31.3. Шифры, не размножающие искажений типа «пропуск»..................... 247 Глава 32. Помехоустойчивые шифрующие автоматы................................ 255 Глава 33. Общие математические задачи, связанные с проблемой построения помехоустойчивых шифров..................................................... 258 33.1. Введение............................................................ 258 33.2. Основные понятия и обозначения...................................... 259 33.3. Описание полугруппы G (Q, р)........................................ 261 33.4. Описание группы ^(Ц s).............................................. 264 33.5. Описание полугруппы G (Q, р, s) .................................... 268 33.6. Описание полугруппы G ( Q , р ' ) .................................. 269 Глава 34. Основные понятия сетей засекреченной связи. Компрометация абонентов... 275 Глава 35. Перекрытия в сетях засекреченной связи............................. 280 Часть 5. ШИФРЫ С ОТКРЫТЫМ КЛЮЧОМ ШИФРОВАНИЯ Глава 36. Схемы шифрования RSA, Эль Гамаля, Полига-Хеллмана.................. 282 36.1. Основные понятия модулярной арифметики.............................. 282 36.2. Криптосистема шифрования данных RSA................................. 288 36.3. Схема шифрования Эль Гамаля......................................... 290 36.4. Схема шифрования Полига-Хеллмана.................................... 291 Глава 37. Идентификация пользователя......................................... 292 Глава 38. Процедуры аутентификации........................................... 293 38.1. Основные принципы построения протоколов идентификации и аутентификации.......................................................... 293 38.2. Аутентификация с использованием ассиметричной криптосистемы и кода аутентификации сообщения........................................... 295 38.3. Типовые схемы идентификации и аутентификации пользователя информационной системы.................................................... 296 38.4. Особенности применения пароля для аутентификации пользователя....... 298 38.5. Взаимная проверка подлинности пользователей........................ 299 38.6. Протоколы идентификации с нулевой передачей знаний.................. 302 38.7. Упрощенный вариант схемы идентификации с нулевой передачей знаний. Протокол Фиата-Шамира..................................................... 302 38.8. Параллельная схема идентификации с нулевой передачей знаний (с нулевым раскрытием).................................................... 303 38.9. Модифицированный протокол Фиата-Шамира.............................. 305 38.10. Схема идентификации Шнорра......................................... 306 38.11. Схема идентификации Гиллоу-Куискуотера............................. 307 38.12. Способ проверки подлинности, где не требуется предъявлять секретный пароль.... 307 38.13. Проверка подлинности с помощью систем шифрования с открытым ключом. 308 38.14. Биометрическая идентификация и аутентификация пользователя......... 308 5
Глава 39. Хэш-функции........................................................ 310 39.1. Основные понятия.................................................... 310 39.2. Хэш-функция Шаумома, ван Хейста, Пфицмана........................... 312 39.3. Хэш-функции и блочные шифры......................................... 312 39.4. Однонаправленные хэш-функции........................................ 313 39.5. Отечественный стандарт хэш-функции.................................. 316 Глава 40. Электронная цифровая подпись....................................... 317 40.1. Электронная цифровая подпись для аутентификации данных.............. 317 40.2. Алгоритмы электронной цифровой подписи.............................. 319 40.3. Алгоритм цифровой подписи RSA....................................... 320 40.4. Недостатки алгоритма цифровой подписи RSA........................... 321 40.5. Алгоритм цифровой подписи Эль-Гамаля................................ 322 40.6. Цифровая подпись Эль-Гамаля......................................... 323 40.7. Особенности протокола Эль-Гамаля.................................... 324 40.8. Алгоритм цифровой подписи DSA....................................... 326 40.9. Отечественный стандарт цифровой подписи............................. 329 40.10. Цифровые подписи с дополнительными функциональными свойствами...... 330 40.11. Алгоритм неоспоримой цифровой подписи Д. Чома...................... 332 40.12. Протокол подписи, позволяющий отправителю сообщения не предоставлять право получателю доказывать справедливость своей подписи. 333 Глава 41. Управление ключами................................................. 335 41.1. Генерация ключей.................................................... 335 41.2. Концепция иерархии ключей........................................... 337 41.3. Распределение ключей................................................ 339 41.4. Протокол аутентификации и распределения ключей для симметричных криптосистем............................................. 341 41.5. Протокол для асимметричных криптосистем с использованием сертификатов открытых ключей.............................................. 343 41.6. Использование криптосистемы с открытым ключом для шифрования и передачи секретного ключа симметричной криптосистемы.................... 344 41.7. Использование системы открытого распределения ключей Диффи-Хеллмана. 346 41.8. Протокол SKIP управления криптоключами.............................. 348 Глава 42. Криптографические протоколы на эллиптических кривых................ 350 42.1. Основные понятия конечных полей..................................... 350 42.2. Криптографические протоколы. Протокол Диффи-Хеллмана................ 354 42.3. Протокол электронной цифровой подписи............................... 355 Часть 6. КРИПТОАНАЛИЗ ШИФРОВ С ОТКРЫТЫМ КЛЮЧОМ Глава 43. Атаки на простейшие парольные системы.............................. 356 Глава 44. Атаки на систему RSA............................................... 358 Глава 45. Атаки на систему открытого шифрования Меркля-Хеллмана.............. 366 Глава 46. Атаки на систему открытого шифрования NTRU......................... 372 Глава 47. Методы вычисления коллизий для хэш-функций......................... 380 Глава 48. Атаки на криптографические протоколы. Компрометация криптопротоколов............................................... 386 Глава 49. Атаки на шифры, определенные эллиптическими кривыми................ 394 Глава 50. Методы вычисления дискретных логарифмов............................ 397 Глава 51. Методы факторизации................................................ 405 Основнаялитература........................................................... 412
ВВЕДЕНИЕ Пособия «История криптографии», «Криптография», написанные в соавторстве с Генрихом Петровичем Шанкиным, и предлагаемое пособие являются результатом многолетней работы по методическому обеспечению ряда фундаментальных дисциплин в области информационных технологий. На пособие «Криптография» изданное в 2002 году, а затем переизданное в 2007 году были получены положительные рецензии: института информационных наук и технологий безопасности Российского государственного гуманитарного университета (РГГУ); Московского института радиотехники электроники и автоматики (МИРЭА); центрального банка Российской Федерации (ЦБ РФ); заведующего кафедрой информационной безопасности Московского государственного института электроники и математики (МИЭМ) кандидата физико-математических наук, профессора Прокофьева И.В; члена-корреспондента Академии криптографии, доктора физико-математических наук, профессора, профессора Грушо А.А.; профессора кафедры «Криптология и дискретная математика» Московского инженерно-физического института (МИФИ), доктора технических наук, профессора Щербакова А.Ю.; члена-корреспондента Международной Академии Информатизации, кандидата технических наук Шурупова А.Н. В рецензиях было высказано пожелание о введении раздела, посвященного криптоанализу и синтезу шифров с открытым ключом, а также включения материалов, связанных с теоретико-автоматным подходом в криптографии. В данном трехтомном издании эти пожелания реализованы. Так, в первом томе освещаются проблемы симметричных и ассиметричных шифров. Во втором и третьем томе раскрыты некоторые направления теории автоматов и криптографии не достаточно полно изложенные в имеющихся современных учебных пособиях написанных на русском языке [например, 1-37]. К этим направлениям относятся части: неотличимость состояний и входных слов автоматов; свойства автоматов; периоды выходных последовательностей автомата; приближенные периоды выходных последовательностей автомата; эксперименты с автоматами; модели автоматов, построенные на хэмминговой мере близости их выходных последовательностей; модели автоматов, построенные на основе обобщения понятия гомоморфизма автоматов; помехоустойчивые шифрующие автоматы. Материалы пособия базируются на известных учебных пособиях, и материалах спецкурсов читаемых автором в течение нескольких лет на факультетах МГУ им. М.В. Ломоносова, ИКСИ Академии ФСБ, РГСУ, МИРЭА и МЭСИ, а также на отдельных публикациях в журналах «Дискретная математика», «Проблемы передачи информации», в сборнике «Труды по дискретной математике», в тезисах докладов на различных конференциях. В пособии учтены тенденции развития образования в части перехода обучения на бакавлавриат и магистратуру. Для облегчения целенаправленного выборочного изучения этих материалов работа написана в форме сборника отдельных разделов и подразделов. 7
Часть 1. ОСНОВЫ КРИПТОГРАФИИ Глава 1 Модели шифров по К. Шеннону. Способы представления реализаций шифров К. Шеннон в книге «Работы по теории информации и кибернетике», 1963 (раздел «Теория связи в секретных системах») одним из первых ввел и систематически исследовал простую и естественную математическую модель шифра. Он рассматривал так называемые «секретные системы», в которых смысл сообщения скрывается при помощи шифра или кода, но само шифрованное сообщение не скрывается, и предполагается, что противник обладает любым специальным оборудованием, необходимым для перехвата и записи передаваемых сигналов. Рассматривается только дискретная информация, то есть считается, что сообщение, которое должно быть зашифровано, состоит из последовательности дискретных символов, каждый из которых выбран из некоторого конечного множества. Эти символы могут быть буквами или словами некоторого языка, амплитудными уровнями квантованной речи или видеосигнала. Ядром секретной системы является собственно шифр. 1.1. Алгебраическая модель шифра Пусть X, К, У - некоторые конечные множества, которые названы, соответственно, множеством открытых текстов, множеством ключей и множеством шифрованных сообщений (криптограмм). На прямом произведении ХхК множеств X и К задана функция f: ХхК—У (1(х,у)=у, хеХ, уеК, уеУ). Функции f соответствует семейство отображений f%: Х—У, уеК, каждое отображение задано так: для хеХ Ух⁾=Ш Таким образом, fy - ограничение f на множестве Хх{у}. Здесь {у} - множество, состоящее из одного элемента. Заметим, что задание семейства отображений (fy)yₑK , fy: Х——У однозначно определяет отображение ЕХхК—У, £(х,у)=£у(х). Введенная четверка А=(Х,К,У,1) определяет трехосновную универсальную алгебру, сигнатура которой состоит из функциональной единственной операции f. ОПРЕДЕЛЕНИЕ. Введенная тройка множеств Х,К,У с функцией f: ХхК—У А=(Х,К,У,£) называется алгебраической моделью шифра, коротко - шифром, если выполнены два условия: 1) функция f - сюрьективна (осуществляет отображение «на» У); 2) для любого уеК функция fy инъективна (образы двух различных элементов различны). Из 2) вытекает, что | Х | < | У |. Запись £(х,у)=у называется уравнением шифрования. Имеется в виду, что открытое сообщение х зашифровывается шифром A на ключе у и получается шифрованный текст у. Уравнением расшифрования называют запись £у-1(у)=х (В1(у,у)=х), подразумевая, что шифрованный текст у=1(х,у) расшифровывается на ключе у и получается исходное открытое 8
сообщение х. Для краткости, в ряде случаев, используют и более простые обозначения уравнений шифрования и расшифрования, а именно, соответственно: ух=у и у⁻¹у=х. Требование инъективности отображений (fY)%ₑK в определении шифра равносильно требованию возможности однозначного расшифрования криптограммы (однозначного восстановления открытого текста по известным шифрованному тексту и ключу). Требование же сюрьективности отображения f не играет существенной роли, и оно обычно вводится для устранения некоторых технических, с точки зрения математики, дополнительных неудобств, то есть для упрощения изложения. Подчеркнем, что множество X названо множеством открытых текстов. Его можно понимать как множество текстов возможных для зашифрования на данном шифре. Введенная модель шифра отражает лишь функциональные свойства шифрования и расшифрования в классических с точки зрения истории криптографии системах шифрования (в системах с симметричным ключом). В этой модели открытый текст (или шифрованный текст) - это лишь элемент абстрактного множества X (или У), не учитывающий особенностей языка, его статистических свойств, вообще говоря, не являющийся текстом в его привычном понимании. При детализации модели шифра в ряде случаев указывают природу элементов множеств. 1.2. Примеры моделей шифров Обозначим через I некоторый алфавит, а через I* -множество всех слов в алфавите I, то есть множество конечных последовательностей (цд₂,...,ц), ijeI, je{i,...,L}, Le{i,2,....} Шифр простои замены. Пусть Х=М - некоторое подмножество из I*, а K - множество всех подстановок на I, т.е. K=S(I) - симметрическая группа подстановок на I. Для каждого geK определим fg , положив для (ц,12,...,1г) из М fg(ii,i2,...,iL)=g(ii),g(i2),...,g(iL). Положим дополнительно f(ii,i2,.,iL,g)=fg( ii,i2,.,iL) и y=f(M)={f(ii,i2,...,iL,g): geS(I), (ii,i2,...,iL)eM}. Таким образом, нами определен шифр А=(М, S(I), У, f) простой замены, более точно: алгебраическая модель шифра простой замены с множеством открытых текстов Х=М. Шифр перестановки. Положим X - множество открытых (содержательных) текстов в алфавите I длины кратной Т. K=St - симметрическая группа подстановок степени Т, для geST определим fg положив для (ii,i2,.. .,й) е X fg⁽ⁱi,ⁱ2,.,ⁱT⁾ = ⁽ⁱg(i),ⁱg(2),.,ⁱg(T)⁾; доопределим fg на остальных элементах из X по правилу: текст хеХ делится на отрезки длины Т и каждый отрезок длины Т шифруется на ключе g по указанному выше закону шифрования. Последовательность, составленная из букв образов зашифрованных слов, является шифрованным текстом, соответствующим открытому тексту х и ключу g. Таким образом, нами определена функция f:XxK^y и шифр перестановки (X,ST,y,f). Для шифрования текста длины не кратной Т его дополняют буквами до длины кратной Т. Шифр гаммирования. Пусть буквы алфавита I упорядочены в некотором естественном порядке. «Отождествим» номера этих букв с самими буквами. То есть формально положим I={i,2,...,n}, |I|=n. Положим X - некоторое подмножество множества IL, KcIL. Для ключа y=yi,y2,.,YL из K и открытого текста х= ii,i2,.,iL их X положим fY(ii,i2,.,iL)=yi,y2,.,yL, где yj=ij⁺Yj mod(n), je{i,...,L}. Иногда под шифром гаммирования понимают и следующие способы шифрования: yj=ij-Yj; yj=Yj - ijmod(n). 9
Шифр дискового шифратора. Пусть I={1,2,...,n}, открытый текст ь,!.',.. .д будет шифроваться с помощью последовательности подстановок Л1,..., Лу..., Я|. из симметрической группы подстановок степени n. Именно, fk(ii,i2,.,ib)= тсДц),..., Л)(1)),.,пь(1ъ). Выбор ключа k будет пояснен позднее. При такой его интерпретации сначала объясним правило зашифрования дискового шифратора с одним диском (рис. 1.2.1). Рис. 1.2.1. Дисковый шифратор Криптосхему этого шифра можно представить в виде рис. 1.2.2. Рис. 1.2.2. Дисковый шифратор. Средний диск реализует подстановку ( 0 ••• i ••• n -1 X = 1 < x0 • xi • xn-1 При повороте среднего диска на — получаем рис. 1.2.3. n Рис. 1.2.3. Дисковый шифратор. Средний диск повёрнут на и реализует n ту же подстановку относительно своих контактов 10
Если повернуть входной и выходной диски на - 2я n см. рис. 1.2.4. Рис. 1.2.4. Дисковый шифратор. Входной и выходной диски повёрнуты на - 2я , n средний диск реализует ту же подстановку относительно своих контактов. Это эквивалентно повороту среднего диска на 2я . n Сравнивая положения дискового шифратора на рис. 2.3, можно увидеть, что при повороте среднего диска на — дисковый шифратор реализует подстановку n 1 (i Y i -1 Y xi-i T⁻¹XT = I II ⁱ ¹ I i⁻ V< xi-i X xi-i +¹ i i. xi-1⁺¹J где (0 1 T = I 11 2 i i +1 n - 2 n -1 n 0 1 При повороте среднего диска на 2яш n , m е 1,n -1 дисковый шифратор реализует подстановку T ШХТШ. Если имеется N «средних» дисков, соединённых последовательно, реализующих „ _ „ VV v „ „ .......... „ ²%У1 ,• подстановки Xi, X2,..., Xn и повёрнутых относительно начального положения на--, 1 n е 1, N то конструкция в целом реализует правило зашифрования л,= T⁻Y¹X₁TY¹⁻Y²X₂TY²⁻Y³ ...XN₋₁TYN⁻¹⁻YNXNTYN . Положения дисков в каждом такте могут изменяться в соответствии с законом движения дисков. Ключ k определен коммутациями (постановками) дисков, их расположением (порядком) на оси и их начальными угловыми положениями. Б каждый такт работы дискового шифратора вырабатывается подстановка шифрования ^. Поточный шифр. Шифр поточной замены. Бведем сначала вспомогательный шифр (I,r,Y,f) для шифрования букв алфавита I. Для ключа Yi^T, и буквы (открытого текста) 1е I шифрованный текст имеет вид £у1(1)=у. Обозначим через К - множество ключей поточно 11
го шифра. Для натурального числа L введем отображение Ф: К^-Г¹, для фиксированного ключа /еК положим Ф(%)=у1,у2/^,уь. Поточный шифр (IL,K,F,Y') для вспомогательного шифра (X=I,K=r,Y,f) шифрует открытый текст i1,i2,.,iL на ключе /еК по правилу F%(ii,12,^,iL)= fY1(i1), fy^),., fyL(iL), где fy(i)=f(i,y). Поточным шифром замены мы называем поточный шифр, для которого опорный шифр имеет вид (X=I,K=r,Y=I,f), а (fy)yₑᵣ - семейство подстановок на I. Примерами поточных шифров служат шифры гаммирования, шифры простой замены. Поточный шифр с опорным шифром вида: I=K={1,2,...,n}, f(i, y)=i+y mod |I| так же называют шифром гаммирования. При этом условно различают программный шифр гаммирования, в случае | К |<|I|L, и случайный шифр гаммирования, в случае K=IL, Ф - тождественное отображение. Более общее понятие поточного шифра состоит в том, что в качестве множества открытых текстов рассматриваются все последовательности алфавита I длины не превосходящей некоторого L(0). Для шифрования текстов длины L используется гамма ФД/^У^/.-./Уь. Таким образом, используются L функций Фр je{1,...,L(0)}. 1.3. Свойства шифров Произведение шифров. Произведением шифров A1=(X1,K1,Y1,f1), A2=(X2,K2,Y2,f2), Y1CX2 называют шифр A=(X1,K1xK2,Y2,f), для которого f(x,(z1,X2))=f2(f1(x,X1),/2), (Х1,/2)еК1хК2. Транзитивность шифра. Шифр A=(X,K,Y,f) называют транзитивным, если при любых xeX и у<^ найдется /еК, при котором Дх,/)=у. Исходя из введенных определений, легко доказывается, что для транзитивного шифра |X|<|Y|<|K|. Основные параметры шифра. Ряд требований к шифрам формулируется с использованием понятий, точное определение которых будет дано позднее. Тем не менее, на качественном уровне понимания, эти параметры можно трактовать следующим образом. Стойкость шифра. Ряд шифров являются совершенными в том смысле, что положение противника, стремящегося к их дешифрованию, не облегчается в результате перехвата шифртекста, то есть наличие криптограммы не уменьшает неопределенности в возможном выборе открытого текста. Такие шифры относят к так называемому классу теоретически стойких шифров. Ряд шифров, а это многие практически используемые шифры, таковы, что эта неопределенность при перехваченной криптограмме полностью исчезает, то есть становится известным, что данная криптограмма может быть получена шифрованием только единственного открытого текста (неизвестно только какого). Yро-вень стойкости таких систем оценивается по затратам времени и сил, необходимых для получения этого единственного открытого текста. При больших затратах или малой вероятности успеха в дешифровании, говорят, что шифр практически стойкий. Объем ключа. Ключ шифрования (он же ключ расшифрования) должен быть неизвестен противнику, и находиться как в передающем пункте связи, так и в приемном пункте. Обычная практика использования ключа состоит в том, что он используется как одноразовый шприц - единожды, при шифровании лишь одного открытого текста. Для регулярной связи корреспондентов, следовательно, надо иметь в их пунктах связи достаточно большое количество ключей, то есть должна решаться задача секретной доставки ключей. Эта задача решается более просто, если объем каждого ключа сравнительно небольшой. 12
Сложность выполнения операций шифрования и расшифрования. Эти операции должны быть по способу выполнения по возможности простыми. Если они выполняются вручную, то их сложность приводит к большим затратам времени на их выполнение и появлению ошибок. При использовании шифровальной аппаратуры возникают вопросы о простоте технической реализации аппаратуры, ее стоимости и о достижении необходимой скорости выполнения операций, связанных с процессами шифрования и расшифрования. Разрастание числа ошибок. Б некоторых типах шифров ошибка в одной букве, допущенная при шифровании, приводит к большому числу ошибок в расшифрованном тексте. Такие ошибки разрастаются в результате операций расшифрования, вызывая значительную потерю информации, и часто требует повторного зашифрования текста и передачи новой криптограммы. Естественно, при выборе шифра для связи стараются минимизировать возрастание числа ошибок. Помехоустойчивость шифра. При действии помех в линиях связи происходит искажение текста криптограммы, что приводит при расшифровании к искажениям открытого текста, а зачастую и к нечитаемости текста. Свойство шифра противостоять разрастанию ошибок при расшифровании текстов называют помехоустойчивостью. Имитостойкость шифра. К активным действиям противника в канале связи относят его попытки навязать абоненту сети связи ложную информация. Это делается путем искажения шифрованного текста в канале связи, либо его замене на ранее переданный шифртекст. Бывают и другие действия противника, ведущие к принятию ложной информации. Шифры, обладающие свойством противостоять попыткам навязывания ложной информации называются имитостойкими. Увеличение объема сообщения. Для некоторых шифров объем сообщения увеличивается в результате операции шифрования. Этот нежелательный эффект проявляется, например, при попытке выровнять статистику сообщения путем добавления некоторых вспомогательных символов («пустышек»), или при рандомизации открытого сообщения, то есть, по сути, применения к нему некоторого пропорционального кода. Основные свойства модели шифра.Бажным классом шифров является введенные выше так называемые транзитивные шифры, то есть шифры, для которых уравнение £(х,/)=у разрешимо относительно ус К при любых парах (х,у)еХхУ и так называемые t-транзитивные шифры, шифры, для которых система уравнений ^х()),у)=у()), je{1,...,t} имеет решение относительно уеК для любых подмножеств {х(1),х(2),..., \(t)|cX мощности t и любых подмножеств {у (1),у(2),.,у (t)}cy мощности t. Эндоморфный шифр. Другой важный класс шифров представляют так называемые эндоморфные шифры (термин предложил К. Шеннон), то есть шифры (X,K,y,f), для которых множество открытых текстов X совпадает с множеством криптограмм у. Для таких шифров (X,K,y,f) каждое преобразование fy, уеК является биекцией X в X (подстановкой на X). Множество таких биекций обозначают через n(K,f)={fy: уеК}, а сам эндоморфный шифр - через A=(X,n(K,f)) и называют подстановочной моделью эндоморфного шифра. При этом под ключом этого шифра понимают биекцию леП(К^). Уравнение шифрования записывают в виде лх=у, уравнение расшифования записывают в виде л-¹у=х. Групповой шифр. Эндоморфный шифр, у которого множество подстановок n(K,f) является смежным классом по некоторой подгруппе из S(X) называют групповым шифром . Транзитивный шифр, для которого | X | = | К | называют минимальным шифром. 13
Для эндоморфных шифров Ai=(X/n(Ki/fi)) Az=(X,11(К Л ’)) используют понятие произведения шифров Ai-A2=(X, n(Ki/fi)-n(K2,f2)/ где n(Ki,fi)- ЩК^)^^: nien(Ki,fi)/ т.п 11(1<Лф. Очевидно, произведение эндоморфных шифров будет транзитивным шифром, если таковым является хотя бы один из них. Эквивалентные ключи шифра. ОПРЕДЕЛЕНИЕ. Ключи /, /' шифра (X,K,y,f) называются эквивалентными, если при любом хеХ f⁽x,X)= f⁽x,X'⁾. 1.4. Вероятностная модель шифра Одно из важнейших предположений К. Шеннона при исследовании секретных систем состояло в том, что каждому возможному передаваемому сообщению (открытому тексту) соответствует априорная вероятность, определяемая вероятностным процессом получения сообщения. Аналогично, имеется и априорные вероятности использования различных ключей шифра. Эти вероятностные распределения на множестве открытых текстов и множестве ключей характеризуют априорные знания криптоаналитика противника относительно используемого шифра. При этом К. Шеннон предполагал, что сам шифр известен противнику. ОПРЕДЕЛЕНИЕ. Вероятностной моделью шифра называется его алгебраическая модель с заданными дискретными, независимыми вероятностными распределениями Р(Х)=(р(х), хеХ), Р(К)=(р(/), /еК) на множествах X и К . Естественно, вероятностные распределения на X и К индуцируют вероятностное распределение Р(У)=(р(у),уеУ) на У, совместные распределения P(X, К), P(X,y), Р(У,К) и условные распределения P(X/ у)=(р(х/ у), xеX) и Р(К/ у)=(р(//у),/еК). Вероятностной модели шифра соответствует так называемая матрица (р(у/х)) размера | X | х | У | переходных вероятностей шифра, составленная из условных вероятностей р(у/х) - вероятности зашифрования открытого текста х в криптограмму у при случайном выборе ключа /еК в соответствии с Р(К). 1.5. Совершенные шифры При определении теоретической стойкости шифра используют вероятностную модель шифра и следующие рассуждения. Зная шифр и априорные вероятности открытых текстов и ключей, обладая перехватом шифртекста уеУ противник может вычислить условные вероятности р(х/у) при всех xеX. Если при этом окажется, что один из элементов х(0) их X имеет значительную вероятность р(х(0)/Y)=i-e, а все остальные элементы их X, вместе взятые, имеют вероятность ^ р(х / у) = е, то это означает, что с надежностью i-e найдено истинное открытое х ф х (0) сообщение. В этом смысле говорят, что дешифрование сводится к вычислению апостериорных вероятностей р(х/у) при всех xеX. Напротив, если окажется, что при любом xеX выполняется равенство р(х/у)=р(х), то перехваченная криптограмма у не несет никакой информации об открытом сообщении. Если это равенство выполняется дополнительно и при любом уеУ, то это свидетельствует о высокой способности шифра противостоять попыткам дешифрования, то есть о высокой криптостойкости шифра. Последние шифры К. Шеннон назвал «совершенными» шифрами. i4
Доступ онлайн
В корзину