foundations_chap_2 (Лекции по информационной безопасности), страница 3

PDF-файл foundations_chap_2 (Лекции по информационной безопасности), страница 3 Информационное обеспечение разработок (13027): Лекции - 11 семестр (3 семестр магистратуры)foundations_chap_2 (Лекции по информационной безопасности) - PDF, страница 3 (13027) - СтудИзба2017-12-21СтудИзба

Описание файла

Файл "foundations_chap_2" внутри архива находится в папке "Лекции по информационной безопасности". PDF-файл из архива "Лекции по информационной безопасности", который расположен в категории "". Всё это находится в предмете "информационное обеспечение разработок" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "информационное обеспечение разработок и исследований" в общих файлах.

Просмотр PDF-файла онлайн

Текст 3 страницы из PDF

Для того, чтобы упростить дальнейшее изложение, перейдем к алфавиту из 32 символов,отбросив пробел из нашего исходного алфавита M. Вместо пробела всообщениях будем использовать одну из редко встречающихся букв,например, «Ф».Будем предполагать, что ключ K = (Y1 , Y2 , Y3 ) состоит их трехчисел, выбранных случайно равновероятно и независимо из множества {0, . . . , 31}. С помощью рекуррентного соотношения Yt = (Yt−1 +Yt−3 ) mod 32 порождаются элементы последовательности Y1 , .

. . , Yn+1для t > 3. Затем по формулеZt = (Yt + Yt+1 ) mod 32,t = 1, . . . , n,(2.2)вычисляется псевдослучайная последовательность Z1 , . . . , Zn , используемая вместо случайной гаммы. Как и в предыдущем примере, шифрование заключается в сложении по модулю 32 элементов гаммы спорядковыми номерами символов шифруемого текста, полученнымииз таблицы 2.4.Зашифруем на ключе K = (04, 31, 15) сообщение«ПРИКАЗЫВАЮФНАСТУПАТЬ».Рекуррентная последовательность Y1 , . . . , Yn+1 в данном случаебудет иметь вид: «04 31 15 19 18 01 20 06 07 27 01 08 03 04 12 15 19 3114 01 00».Сложим по модулю 32 порядковые номера символов нашего сообщения с элементами псевдослучайной последовательности (гаммы),полученной по формуле (2.2):15 16 08 10 00 07 27 02 00 30 20 13 00 17 18 19 15 00 18 28 — сообщение;03 04 02 05 19 21 26 13 02 28 09 11 07 16 27 02 18 13 15 01 — гамма;18 30 10 15 19 28 21 15 02 26 29 24 07 01 13 21 01 13 01 29 — зашифрованноесообщение.20Общее число возможных текстов из 20 символов составляет 32 ,3а количество различных ключей в данном случае 32 = 32768.

Следо-§ 2.1.ВВЕДЕНИЕ В ПРОБЛЕМЫ КЛАССИЧЕСКОЙ КРИПТОГРАФИИ145вательно, количество возможных вариантов расшифрования при неизвестном ключе не превосходит 32768 и, имея перехваченную криптограмму, а также зная алгоритм шифрования, криптоаналитик можетотбросить бо́льшую часть текстов как недопустимые (в частности,будет отброшено сообщение «ПРИКАЗЫВАЮ ОТСТУПАТЬ»).Таким образом, криптоаналитик имеет 32768 вариантов сообщения, из которых он должен выбрать единственный правильный.

Возникает вопрос — можно ли вообще отличить настоящее сообщениеот ошибочных вариантов? Если сообщение представляет собой осмысленный текст на русском языке, то его наверняка удастся отличить20от ложных, так как из 32 слов из рассматриваемого алфавита осмысленными текстами является только малая часть. Согласно исследованиям, проведенным еще К.

Шенноном [13], осмысленных текстов из620 букв на английском языке порядка 10 . Приблизительно такая жеоценка справедлива и для русского языка.Оценим вероятность появления среди всех вариантов расшифрования второго осмысленного текста, сделав разумное допущение о том,что тексты длины 20, являющиеся ложными вариантами расшифрования нашей криптограммы, выбираются из совокупности всех последовательностей, состоящих из 20 символов, совершенно случайно,независимо от того, имеют они смысл или нет. Вероятность того,что выбранный случайным образом текст не окажется осмысленным,20620равна приблизительно (32 − 10 )/32 .

Следовательно, вероятностьпоявления среди 32767 случайных текстов осмысленного текста оценивается следующим образом:6 3220 − 106 3276732767 × 10−20< 2.6 × 10 .<1−20203232Для сравнения, вероятность угадать 6 чисел, выбранных случайно из−1036, больше, чем 10 .Таким образом, мы показали, что в нашем случае криптоаналитик, прочитав варианты расшифрования криптограммы для всех возможных ключей, с вероятностью, близкой к единице, правильно определит переданное сообщение. Если он будет отбрасывать по одномуложному сообщению в секунду, то ему понадобится на просмотр всехвариантов около 9 часов.

Гораздо больше времени (546 часов при скорости один вариант в минуту) необходимо для получения вручнуюсамих вариантов расшифровки. Таким образом, трудоемкость ручного дешифрования рассматриваемой криптограммы методом переборавсех возможных ключей составляет 555 часов.Время дешифрования можно значительно сократить, если использовать ЭВМ для генерации вариантов сообщения. В этом случае все146КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫварианты будут получены практически мгновенно и, следовательно,трудоемкость дешифрования составит 9 часов, которые необходимыдля прочтения этих вариантов.

При этом, правда, нужно еще учестьвремя, необходимое для программирования ЭВМ. Очевидно, однако,что это время играет менее значительную роль, чем собственно времяперебора (если только речь не идет о дешифровании одной единственной криптограммы).В современных алгоритмах шифрования используются гораздо более длинные ключи, чем в нашем примере. В частности, широко используемый алгоритм шифрования DES имеет ключ объемом 56 бит.Если мы захотим просмотреть все варианты дешифрования сообщения, зашифрованного с помощью алгоритма DES (количество ключей5616в этом случае 2 ≈ 7.2 × 10 ), то для этого понадобится более 2 миллиардов лет при скорости один вариант в секунду.

Метод дешифрования перебором ключей становится действительно опасным, если имеется алгоритм, позволяющий автоматизировать отбраковку ошибочных вариантов с помощью ЭВМ. Для этого может использоваться несколько способов.Во-первых, если для проверки правильности сообщения используется контрольная сумма, то она же может послужить и для отбраковкиопробуемых вариантов.Во-вторых, если мы заранее знаем фрагмент дешифруемого сообщения (или значения некоторых служебных полей дешифруемых данных), то для отбраковки ложных сообщений достаточно произвестисравнение известного фрагмента со значением соответствующей части расшифрованных на опробуемом ключе сообщений.Может, однако, оказаться, что проверку указанных типов пройдетбольшое количество сообщений.

Например, если контрольная суммасодержит 32 бита, а ключ — 56 бит, то мы получим приблизительно242 = 16777216 сообщений, имеющих правильную контрольную сумму, среди которых нужно найти единственное подлинное. В такихслучаях, а также, если контрольная сумма отсутствует и неизвестна даже часть зашифрованного текста, при отбраковке ложных сообщений не обойтись без так называемых «критериев на открытыйтекст». Такие критерии предназначены для выявления тех последовательностей символов заданного алфавита, которые допустимы вкачестве открытых сообщений.Построим критерий на открытый текст для отбраковки ложныхвариантов в рассматриваемом нами примере.Проанализировав частоты встречаемости различных пар соседних букв в текстах русского языка (см.

таблицу 2.3), можно сделатьвывод, что вероятность появления 317 из них практически равна ну-§ 2.1.ВВЕДЕНИЕ В ПРОБЛЕМЫ КЛАССИЧЕСКОЙ КРИПТОГРАФИИ147лю. Для нашего случая, когда вместо пробела используется буква«Ф», столбец, соответствующий букве «Ф», объединяется со столбцом, соответствующим пробелу, и аналогичная операция проводитсясо строками. Поэтому в рассматриваемом алфавите из 32 букв число невозможных сочетаний соседних символов составляет 287. Данная особенность позволяет сформулировать критерий на открытыйтекст: если в тексте имеется хотя бы одна запретная биграмма, т. е.невозможное сочетание двух соседних символов, то он не является открытым сообщением.Очевидно, что с помощью такого критерия мы не сможем отбраковать все ложные варианты расшифрования, так как не любая последовательность символов без запретных биграмм является осмысленнымсообщением. Вероятность появления любой фиксированной пары символов в конкретном месте случайно равновероятно выбранного текста2(из множества текстов заданной длины) равна 1/32 для алфавита из32 символов.

Если пренебречь зависимостью соседних биграмм, тонесложно подсчитать вероятность того, что из девятнадцати пар соседних символов ни одна не окажется запретной:287 19≈ 0.002.1− 232Следовательно, среди 32768 вариантов сообщения лишь около 65 несодержат ни одного невозможного сочетания соседних букв. Воспользовавшись ЭВМ, можно практически мгновенно отбросить тексты снедопустимыми сочетаниями соседних букв. Затем несложно и вручную выбрать из оставшихся нескольких десятков вариантов правильный вариант.Читатель, знакомый с основами математической статистики, может попробовать построить и рассчитать другие, более совершенныекритерии на открытый текст, с помощью которых в данном примереи без участия человека можно определить единственный правильныйвариант дешифрования.Рассмотренный метод дешифрования, заключающийся в переборе всех возможных ключей, называют методом тотального опробования.

Очевидно, что время, необходимое для дешифрования такимметодом, будет зависеть от мощности используемой ЭВМ. Поэтому вслучае полной автоматизации перебора трудоемкость алгоритма удобнее всего измерять числом элементарных операций, производимых привыполнении этого алгоритма. Оценим трудоемкость дешифрованиярассматриваемого шифра методом тотального опробования.Для генерации одного символа опробуемого сообщения необходимо две операции сложения по модулю и несколько обращений к памяти. Проверка того, является ли сгенерированное сообщение текстом на148КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫрусском языке, реализуется с помощью n обращений к памяти и сравнений, где n — длина текста (на самом деле несколько меньше, так какесли в тексте уже найдена запретная биграмма, то проверять оставшиеся биграммы нет смысла).

Таким образом, трудоемкость метода тотального опробования ключей можно выразить формулой T = Cn |K|,где C — некоторая константа, не зависящая от размерности задачи. Внашем случае T = C × 20 × 32768 = C × 655360, то есть трудоемкостьопробования всех ключей нашего алгоритма шифрования составляетнесколько миллионов операций (современная персональная ЭВМ проделает эти вычисления практически мгновенно).При построении критерия на отбраковку ложных вариантов расшифрования вовсе не обязательно использовать все знаки сообщения.Скорее всего, достаточно будет небольшого отрезка из несколькихдесятков знаков. Соответственно, нет и необходимости расшифровывать сразу весь текст.

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5117
Авторов
на СтудИзбе
446
Средний доход
с одного платного файла
Обучение Подробнее