Как сделать криптоанализ
Добавил пользователь Алексей Ф. Обновлено: 04.10.2024
Криптография бывает двух типов: криптография, которая помешает читать ваши файлы вашей младшей сестре, и криптография, которая помешает читать ваши файлы людям из правительства.
Брюс Шнайер
Прикладная криптография
Шифр простой замены, простой подстановочный шифр, моноалфавитный шифр — класс методов шифрования, которые сводятся к созданию по определённому алгоритму таблицы шифрования, в которой для каждой буквы открытого текста существует единственная сопоставленная ей буква шифр-текста. Само шифрование заключается в замене букв согласно таблице. Для расшифровки достаточно иметь ту же таблицу, либо знать алгоритм, по которой она генерируется.
К шифрам простой замены относятся многие способы шифрования, возникшие в древности или средневековье, как, например, Атбаш (также читается как этбаш) или Шифр Цезаря. Для вскрытия подобных шифров используется частотный криптоанализ.
Для вскрытия шифра простой замены используется такой метод криптоанализа как Частотный анализ.
Частотный анализ — основывается на предположении о существовании нетривиального статистического распределения отдельных символов и их последовательностей как в открытом тексте, так и в шифротексте, которое, с точностью до замены символов, будет сохраняться в процессе шифрования и дешифрования.
Практика: Задание 1
Возьмём задание категории Crypto из репозитория "xairy/mipt-ctf"
Перейдя по ссылке мы получим текст. Текст не маленький 153тысячи символов.
Но нам это на руку, чем больше текст, тем с большей вероятностью мы будем угадывать символы.
Метод 1: CrypTool
Загружаем текст в CrypTool 1.4
Analysis -> Symmetric Encryption (classic) -> Ciphertext-Only -> Substitution Дальше программа сама сделает за нас все(Проведет анализ и выдаст исходный текст)
Остается указать автора как флаг
Метод 2: SubstitutionCipherDecryption
Автором данной статьи на просторах интернета была найдена интересная и удобная(на взгляд автора) программа SubstitutionCipherDecryption.exe
- В правой части мы можем видеть таблицу сравнения частотного анализа текстов на английком языке в общем и конкретно нашего текста(не забываем, что тексты разного характера имеют разные показатели честотной характеристики. Так например в научной статье или художественном произведении шанс встретить одну и ту же букву может отличаться на несколько процентов, что очень много). Так же мы можем анализировать Двойные сочетания символов, тройные и сочетания из 4 символов.
- При нажатии "AutoAssign" программа автоматически подставит ОЧЕВИДНЫЕ совпадения. Остальное легче сделать руками. Мы легко можем догадаться, что, допустим, THE - самое частое слово из 3 букв. Т.е. выбрав статистику слов из 3 букв мы сразу увидим очевидную замену
Метод 3 (От Создателя таска):
После добавления текста он подвергается анализу и выдает схожий с предыдущей программой результат
В современном мире остро стоит вопрос о конфиденциальности данных при обмене ими и их хранении, которая достигает за счет все возможных способов шифрования. Однако при появление новых алгоритмов шифрования начинают проводиться работы по изучению способов нарушить конфиденциальность данных, то есть ищут атаки на них.
В наше время широко распространены блочные алгоритмы шифрования, такие как AES, “Кузнечик” и др. Одним из потенциально эффективных способов проведения атак на них является линейный криптоанализ. Основную концепцию данного метода изложил Мицуру Мацуи (Mitsuru Matsui) в работе “Linear Cryptoanalysis Method for DES Cipher” [1] в 90х годах. Суть данного метода будет изложена в разделе 2 данной статьи.
В качестве примера эффективного использования данного метода представлен линейный криптоанализ блочного алгоритма шифрования NUSH [2], краткая справка по которому будет приведена ниже.
Основы линейного криптоанализа
Как было написано выше суть линейного криптоанализа изложена в “Linear Cryptoanalysis Method for DES Cipher”. При использование линейного криптоанализа предполагается, что известна структура шифра и что криптоаналитик обладает достаточной статистической выборкой “шифротекст-открытый ключ”, полученной на одном ключе.
После выполнения перечисленных выше требований структуру алгоритма заменяют простой линейной функцией. Как правило анализ линейных функций куда проще, чем нелинейных функций самого шифра, что может свести задачу анализа шифра к анализу его линейной модификации. Далее из полученной системы функций криптоаналитик угадывает биты ключа с определенной вероятностью.
Пусть скалярное произведение двоичных векторов по модулю 2. И пусть открытый текст, шифротекст и ключ соответственно.
Определение 1
Линейным приближением шифра называется соотношение L:
которое выполняется с вероятностью Величина преобладанием линейного соотношения, а векторы - называются масками.
Из определения несложно видеть, что для увеличения вероятности отгадывания ключа требуется увеличивать преобладание.
По мимо этого для приведенного ниже примера нам потребуется знание леммы Мацуи.
Лемма Мацуи (Pilling-up лемма, лемма “О набегании знаков”)
Пусть где - независимые случайные величины, принимающие значения из . Пусть
где . Тогдаслучайная величина принимает значение 0 с вероятностью , где
Следствие 1: если , где то итоговое преобладание равно нулю.
Доказательство можно найти по ссылке.
В 2000 году был объявлен европейский исследовательский проект для определения безопасных шифровальных алгоритмов NESSIE одним из участников, которого выступал блочный алгоритм симметричного шифрования, разработанный Анатолием Лебедевым и Алексеем Волчковым для российской компании LAN Crypto – NUSH. Алгоритм имеет несколько вариантов, отличающихся количеством раундов и длиной ключа (64, 128, 192 и 256 битов).
Его отличительной особенностью от других участников являлось отсутствие S- и P-блоков, а само шифрование проводилось только с использованием арифметических операций (XOR, AND и т.д.). В результате чего процесс шифрования ожидаемо проходит быстро. Это легко показать, если вспомнить, что сложность битовых операций , где k – битовая длина модуля.
Шифрование
Последняя итерация отличается от основных только отсутствием перестановки после вычисления выражений в правых частях равенств:
Выход: зашифрованный блок
Расшифрование
На первом итерации происходит
После чего происходит итерация
Линейный криптоанализ NUSH
Из алгоритма шифрования, приведенного выше, следует, что с вероятностью 1 выполняется
Тогда обозначим через булевую функцию. Легко можно убедиться, что сложение по модулю два не изменяется соотношение вероятностей для или . Таким образом мы имеем линейную апроксимацию с или для :
Используя (1) и (2) получаем линейную апроксимацию раундовой функции с вероятностью
Теперь получим связь между внутренними значениями открытого текста, шифротекста и ключа.
Рассмотрим связь между и между открытым текстом и ключом. Из алгоритма шифрования получаем, что , зависит от , , и . Здесь
означает последние 5 бит . Следовательно зависит от , , , , и . И эту зависимость можно выразить через функцию
Можно получить связь для и для открытого текста с ключом. Действую аналогичным образом получим, что зависит только от , , , , и .И эту зависимость можно выразить через функцию :
Можно получить связь для и для открытого текста с ключом. Действую аналогичным образом получим, что зависит только от , , , , , , и . И эту зависимость можно выразить через функцию :
Теперь определим связь между и для открытого текста с ключом. Из алгоритма расшифрования известно, что
Следовательно зависит только от. А они в свою очередь выражаются через и через . Прослеживая и дальше связь между промежуточными значениями получим, что зависят от и от .
Резюмируя последние пару абзацев получим, что зависит от , , , , , , , , , , , , . И эту зависимость можно выразить через функцию :
А зависимость для можно записать через :
Теперь перейдем непосредственно к линейному криптоанализу. Принимая во внимание (3) заметим, что 29-раундовая линейная апроксимация
содержит вероятность согласно лемме Мацуи. Эта линейная апроксимация может быть записана через введенные ранее функции
Из расписания ключей NUSH известно, что (11) содержит -бит ключа. Восстановим их по алгоритму, приведенному ниже.
Шаг 1. Для каждого кандидата в ключи через обозначим кол-во открытых текстов, удовлетворяющих (11).
Шаг 2. Если максимальное значение из всех , тогда сохранить .
Шаг 3. Остальные биты ключа ключа восстанавливаются, используя урезанную линейную апроксимацию раундов или методом исключения.
Вывод
В статье представлена основная концепция линейного криптоанализа и рассмотрен пример его применения в анализе алгоритма шифрования NUSH.
Литература
1. Mitsuru Matsui, Linear cryptoanalysis method for DES cipher, Advances in Cryptogy-Eurocrypt’93, Berlin: Springer-Verlag, 1993, 386-397.
2. Wu Wenling & Feng Dengguo, Linear cryptoanalysis of NUSH block cipher, Science in China (Seria F), February 2002, Vol. 45, № 1.
3. M. Heys, A Tutorial on Linear and Differential Cryptoanalysis, Cryptologia, June 2001, Vol. 26 №3.
Атака обычно характеризуется в соответствии с необходимыми данными:
Резюме
Семейства криптоаналитических атак
Существует несколько семейств криптоаналитических атак, наиболее известными из которых являются частотный анализ , дифференциальный криптоанализ и линейный криптоанализ .
Частотный анализ
Индекс совпадения
Вероятная словесная атака
Атака по словарю
Атака по словарю состоит из проверки всех слов в списке как ключевого слова . Это часто сочетается с атакой грубой силы .
Атака грубой силой
Атака грубой силой включает в себя тестирование всех возможных решений паролей или ключей . Это единственный способ восстановить ключ в самых современных и пока еще нетронутых алгоритмах, таких как AES . Он мало используется для паролей с очень большим количеством символов, потому что время, необходимое для расшифровки, становится слишком большим.
Атака парадокса дней рождения
Современный криптоанализ
С 1970-х годов появились современные блочные шифры, такие как DES . Он был тщательно изучен и подвергся атакам, что вызвало серьезные атаки в криптовалютном мире. Представленные ниже методы не являются общими, и для атаки на данный тип шифрования необходимы модификации.
Часто мы рассматриваем не полную версию алгоритма шифрования, а вариант с меньшим количеством оборотов (в случае схем типа Фейстеля или хеш-функций). Этот предварительный анализ, если он позволяет обнаружить уязвимости, предполагает атаку на весь алгоритм.
Линейный криптоанализ
Линейный криптоанализ, разработанный Мицуру Мацуи , заключается в линейной аппроксимации внутренней структуры метода шифрования. Он восходит к 1993 году и оказался наиболее эффективной атакой против DES . Новые алгоритмы невосприимчивы к этой атаке.
Дифференциальный криптоанализ
Дифференциальный криптоанализ - это статистический анализ изменений в структуре метода шифрования в результате небольшого изменения записей. При очень большом количестве помех возможно извлечение ключа. Эта атака датируется 1990 годом (представлена на конференции Crypto 90 ). Это связано с Эли Бихамом и Ади Шамиром . Однако теперь известно, что разработчики DES знали о варианте этой атаки, называемой T-атакой . Современные алгоритмы ( AES , IDEA и т. Д.) Предназначены для защиты от атак этого типа. Также возможны дифференциальные атаки на хэш-функции с модификациями проведения атаки. Одна такая атака была проведена против MD5 .
Дифференциально-линейный криптоанализ
Криптоанализ χ²
Криптоанализ χ² , концепция, разработанная Сержем Воденэ , позволяет получать результаты, аналогичные линейным или дифференциальным атакам. Соответствующий статистический анализ позволяет преодолеть недостатки последнего, избегая необходимости знать точную операцию шифрования.
Квадратичный криптоанализ
Квадратичный криптоанализ - недавнее изобретение Николя Куртуа и Йозефа Пепшика . Эта атака (называемая атакой XSL ) нацелена, в частности, на AES и другие шифры на основе Rijndael . Атака XSL является предметом многочисленных споров относительно ее истинной эффективности из-за ее эвристической природы. Он заключается в решении системы очень больших уравнений.
Криптоанализ по модулю
Предложенный Брюсом Шнайером , Дэвидом Вагнером и Джоном Келси в 1999 году, этот метод состоит в использовании рабочих различий (в соответствии с конгруэнтностью переменных) алгоритмов, использующих бинарные вращения.
Атаки по вспомогательному каналу
Атаки по побочным каналам являются частью большого семейства криптоаналитических методов, которые используют неожиданные свойства криптографического алгоритма во время его программной или аппаратной реализации. Действительно, теоретическая безопасность не обязательно гарантирует безопасность при использовании на практике. Атаки касаются разных параметров: времени, шума, энергопотребления и т. Д.
Компромисс времени / памяти
Эта концепция была введена Мартином Хеллманом в 1980 году. В 1993 году она была усовершенствована Филиппом Окслином с концепцией радужной таблицы . Эта система позволяла, среди прочего, атаковать пароли сеансов в Windows , когда они хранятся в формате LanManager , что до сих пор чаще всего имеет место. Это компромисс между атакой методом перебора и использованием словарей. Исчерпывающий поиск действительно требует очень много времени, а словарь всех возможных паролей потребует много места. Благодаря алгоритмическим процессам этому методу удается найти золотую середину между этими двумя принципами, создав таблицы управляемого размера.
Атаки на методы работы
Потоковые шифры (например, RC4 ) также используют вектор инициализации по тем же причинам. Подобная атака была недавно проведена в связи с шифрованием документов пакета Microsoft Office , использующего RC4. Вектор инициализации всегда один и тот же для данного документа. Таким образом, можно получить большой объем информации, сравнивая шифрование документа с шифрованием того же слегка измененного документа.
Атака встречей в середине
Чтобы улучшить его, добавьте проверяемые ссылки [ как это сделать? ] или шаблон > для отрывков, требующих источника.
Двойное шифрование с использованием одного и того же алгоритма, но с использованием двух разных ключей не эквивалентно шифрованию с ключом, который вдвое длиннее (в случае DES мы не переходим от 2 56 до 2112 операций для взлома шифрования) из-за атаки, называемой путем встречи в середине типа компрометации памяти и времени .
Атака теоретически работает следующим образом. В случае двойного шифрования предполагается, что известны открытый текст M и зашифрованный текст C , причем C получается двумя приложениями одного и того же шифрования с двумя априори разными ключами . Речь идет об определении пары ключей, которая позволяет перейти от M к C путем двойного шифрования. Операцию можно повторить с другими парами открытого текста и зашифрованного текста, если осталась не только одна пара возможных ключей. Пары ключей-кандидатов - это те, которые позволяют получить один и тот же блок с помощью единственного шифрования M, с одной стороны, с помощью единственного дешифрования C, с другой стороны: это встреча в середине.
Таким образом, атака допускает компромисс между памятью и временем. Для каждого возможного ключа, она требует хранения блока , полученного путем выполнения одной операции шифрования на M . Затем для всех возможных ключей и для каждого блока, полученного путем применения одной операции дешифрования к C , необходимо найти идентичный блок среди блоков, сохраненных на предыдущем шаге.
Пара из двух ключей, которые позволили получить этот промежуточный блок (один за счет шифрования M, другой за счет дешифрования C ), тогда является кандидатом на роль ключа двойного шифрования.
В случае DES и для 64-битного блока данных первый шаг требует 2 56 операций шифрования (и 2 блока памяти 56 по 64 разряда), а второй 2 56 операций (плюс в каждом случае поиск блока).
Сложность атаки в середине встречи на двойной шифр была увеличена только в 2 раза (без учета последнего шага сравнения) по сравнению с атакой с исчерпывающим поиском на одиночный шифр, в то время как атака грубой силы делает ее квадратной. Однако для этого требуется значительно увеличенное пространство памяти, но возможны некоторые корректировки (это так называемые менее радикальные компромиссы времени и памяти), если запрошенное пространство памяти слишком велико.
Атака также работает для объединения двух разных шифров, и ее можно практиковать симметрично.
В случае DES мы получаем теоретическую атаку порядка 257 операций шифрования, тогда как без модификации для этого потребовалось бы пространство памяти 256 × 64 бита. Именно из-за этой атаки двойной DES не используется, но также и безопасность 3DES с 3 отдельными ключами (168 бит) в 112 битах считается очень надежной , поскольку для расшифровки требуется порядка 2112 операций. его шифрование.
Атаки на асимметричные системы
Поиск ключа к шифрованию, обеспечиваемому асимметричной криптографией, требует других подходов. В случае RSA именно сложность факторизации обеспечивает надежность шифрования. Для Эль-Гамаля используется проблема дискретного логарифмирования . Однако в зависимости от того, как мы используем эти алгоритмы, могут появиться некоторые недостатки. RSA уязвим, если используются экспоненты с низкой величиной (атаки Дона Копперсмита и Винера). В особых условиях может быть атаковано избыточное шифрование с помощью RSA. Стандарт PKCS обеспечивает более надежное использование RSA, даже если ранние проекты стандарта были подвержены атакам со стороны вспомогательных каналов (Bleichenbacher).
Квантовый криптоанализ
В квантовых компьютерах , которые все еще находятся в научных исследованиях и разработках, могут быть использованы в криптоанализе.
В алгоритм Шора могут быть использованы для решения задач факторизации и дискретного логарифмирования в полиномиальное время , преодолев ряд открытого ключа криптосистемы , такие как RSA и ElGamal . В 2016 году NIST запустил проект стандартизации для поиска систем асимметричного шифрования, которые могли бы противостоять злоумышленнику с помощью квантового компьютера.
Точно так же алгоритм поиска Гровера будет квадратично ускорять атаки на симметричные системы шифрования, основанные на проблеме поиска в неупорядоченной базе (см. Поиск ключа грубой силой ). Однако такой атаке можно легко противостоять, удвоив длину ключа.
Прочие проанализированные свойства
Определенные свойства, наблюдаемые в алгоритмах шифрования, не обязательно приводят к атакам, но позволяют обнаруживать слабые места в конструкции, проблемы, которые могут скрывать другие, более важные.
Слабые ключи
Статистическая погрешность
Мы можем исследовать, вызывает ли структура шифрования статистические ошибки. В общем, предполагается, что алгоритм шифрования дает результат, близкий к генератору равномерно распределенных случайных чисел , чтобы давать как можно меньше информации и максимизировать энтропию . Если наблюдается смещение (например, 1 бит больше, чем 0 бит), то для разработки атаки иногда можно использовать дополнительный анализ. Среди прочего можно указать на атаки на RC6, чьи перестановки заметно отклоняются от характеристик, обычно наблюдаемых в генераторах псевдослучайных чисел .
Применение частотного криптоанализа в написании программы дешифратора
Автор работы награжден дипломом победителя III степени
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
В настоящее время первостепенным фактором, влияющим на политическую и экономическую составляющие национальной безопасности, является степень защищенности информации и информационной среды. Вследствие чего большое значение приобретают вопросы обеспечения безопасности информационных и телекоммуникационных технологий и гарантированной защиты данных в компьютерных сетях экономически значимых структур. О необходимости надежной защиты свидетельствуют многочисленные компьютерные преступления, совершаемые как в кредитно-финансовой сфере, так и в государственных органах.
Защита информации в компьютерных системах обладает рядом специфических особенностей, связанных с тем, что информация не является жестко связанной с носителем, может легко и быстро копироваться и передаваться по каналам связи. Известно очень большое число угроз информации, которые могут быть реализованы как со стороны внешних нарушителей, так и со стороны внутренних нарушителей.
В данной работе рассматривается решение проблем защиты электронной информации на базе использования криптографических методов, которые позволяют решать важнейшие проблемы защищенной автоматизированной обработки и передачи данных
Цель работы: Изучить методы частотного криптоанализа для написания программы дешифратора.
Цель достигается посредством решения следующих задач:
ознакомиться с простейшими методами шифрования информации;
изучить метод частотного криптоанализа;
выбрать язык, текст на котором будет дешифроваться;
реализовать алгоритмы на алгоритмическом языке;
Простейшие методы шифрования информации
Шифр Цезаря, также известный как шифр сдвига, код Цезаря или сдвиг Цезаря — один из самых простых и наиболее широко известных методов шифрования.
Шифр Цезаря — это вид шифра подстановки, в котором каждый символ в открытом тексте заменяется символом, находящимся на некотором постоянном числе позиций левее или правее него в алфавите. Например, в шифре со сдвигом вправо на 3, А была бы заменена на Г, Б станет Д, и так далее.
Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки со своими генералами.
Шаг шифрования, выполняемый шифром Цезаря, часто включается как часть более сложных схем, таких как шифр Виженера, и все ещё имеет современное приложение в системе ROT13. Как и всемоноалфавитные шифры, шифр Цезаря легко взламывается и не имеет практически никакого применения на практике.
Криптоанализ (от др.-греч κρυπτός — скрытый и анализ) — наука о методах расшифровки зашифрованной информации без предназначенного для такой расшифровки ключа.
Термин был введён американским криптографом Уильямом Ф. Фридманом в 1920 году. Неформально криптоанализ называют также взломом шифра.
В большинстве случаев под криптоанализом понимается выяснение ключа; криптоанализ включает также методы выявления уязвимости криптографических алгоритмов или протоколов.
Первоначально методы криптоанализа основывались на лингвистических закономерностях естественного текста и реализовывались с использованием только карандаша и бумаги. Со временем в криптоанализе нарастает роль чисто математических методов, для реализации которых используются специализированные криптоаналитические компьютеры.
Попытку раскрытия конкретного шифра с применением методов криптоанализа называют криптографической атакой на этот шифр. Криптографическую атаку, в ходе которой раскрыть шифр удалось, называют взломом или вскрытием.
Криптоанализ эволюционировал вместе с развитием криптографии: новые , более совершенные шифрыприходили на смену уже взломанным системам кодирования только для того , чтобы криптоаналитикиизобрели более изощренные методы взлома систем шифрования . Понятия криптографии и криптоанализанеразрывно связаны друг с другом: для того , чтобы создать устойчивую ко взлому систему , необходимоучесть все возможные способы атак на неё.
Частотный анализ, частотный криптоанализ — один из методов криптоанализа, основывающийся на предположении о существовании нетривиального статистического распределения отдельных символов и их последовательностей как в открытом тексте, так и в шифротексте, которое, с точностью до замены символов, будет сохраняться в процессе шифрования и дешифрования.
Упрощённо, частотный анализ предполагает, что частота появления заданной буквы алфавита в достаточно длинных текстах одна и та же для разных текстов одного языка. При этом в случае моноалфавитного шифрования если в шифротексте будет символ с аналогичной вероятностью появления, то можно предположить, что он и является указанной зашифрованной буквой. Аналогичные рассуждения применяются к биграммам (двубуквенным последовательностям), триграммам и т.д. в случае полиалфавитных шифров.
Начиная с середины XX века большинство используемых алгоритмов шифрования разрабатываются устойчивыми к частотному криптоанализу, поэтому он применяется, в основном, для обучения.
Описание частотного криптоанализа
Как упоминалось выше, важными характеристиками текста являются повторяемость букв (количество различных букв в каждом языке ограничено), пар букв, то есть m (m-грамм), сочетаемость букв друг с другом, чередование гласных и согласных и некоторые другие особенности. Примечательно, что эти характеристики являются достаточно устойчивыми.
Идея состоит в подсчете чисел вхождений каждой n m возможных m-грамм в достаточно длинных открытых текстах T=t1t2…tl, составленных из букв алфавита 1, a2, …, an>. При этом просматриваются подряд идущие m-граммы текста:
t 1 t 2 …t m , t 2 t 3 … t m+1 , …, t i-m+1 t l-m+2 …t l .
Если L (ai1ai2 … aim) — число появлений m-граммы ai1ai2…aim в тексте T, а L — общее число подсчитанных m-грамм, то при достаточно больших L частотыL (ai1ai2 … aim)/ L, для данной m-граммы мало отличаются друг от друга.
В силу этого, относительную частоту считают приближением вероятности P (ai1ai2…aim) появления данной m-граммы в случайно выбранном месте текста (такой подход принят при статистическом определении вероятности).
В общем смысле частоту букв в процентном выражении можно определить следующим образом: подсчитывается сколько раз она встречается в шифро-тексте, затем полученное число делится на общее число символов шифро-текста; для выражения в процентном выражении, еще умножается на 100.
Но существует некоторая разница значений частот, которая объясняется тем, что частоты существенно зависят не только от длины текста, но и от характера текста. Например, текст может быть технического содержания, где редкая буква Ф может стать довольно частой. Поэтому для надежного определения средней частоты букв желательно иметь набор различных текстов.
Практическая часть работы заключается в написании программы дешифратора и она состоит из 5 этапов:
выбор языка программирования, на котором будут реализовываться алгоритмы;
выбор языка, текст на котором будет шифроваться и дешифроваться;
реализация зашифровки текста алгоритмом шифра Цезаря на алгоритмическом языке PascalABC ;
подсчет частот появления каждой буквы в идеальном и зашифрованном текстах и реализация подсчета частот на алгоритмическом языке PascalABC ;
расшифровка закодированного текста на основе идеального путем использования частотного криптоанализа.
Следующим этапом практической части данной работы был выбор языка, тексты на котором будут шифроваться и дешифроваться. Выбирая между русским и английским языком, я решил выбрать русский для более наглядного представления зашифрованного текста. Также русский язык наиболее легок для понимания.
Следующим этапом моей практической части заключался в реализации алгоритма шифра Цезаря на алгоритмическом языке PascalABC . Как уже известно, шифр Цезаря – это алгоритм шифра замены, который сдвигает каждую букву исходного текста на определенное количество букв вперед. Этим числом K было выбрано число 5. Кодирование текста идет по таблице ASCII . Но так как наш зашифрованный и исходный текст только на русском языке, нам нужно было избавиться от всех остальных знаков и английских букв в таблице ASCII и оставить только русские буквы и пробел. Программа была реализована на алгоритмическом языке PascalABC . Исходный код программы представлен в приложении А.
4 Этап. Следующий шаг моей практической работы заключался в подсчете частот появления букв в зашифрованном и исходном тексте. Именно с помощью частот появления букв мы сможем дешифровать текст. Частоту мы считаем следующим образом:
Считаем общее количество букв в тексте;
Считаем сколько раз каждая буква встречается в тексте;
Делим подсчитанное количество каждой буквы на общее количество букв в тексте и, таким образом, получаем частоту появления каждой буквы в тексте.
Программа была реализована и представлена в приложении Б и В.
5 Этап. Завершающим этапом моей работы было расшифровка текста частотным криптоанализом. Для этого была написана программа дешифратор. Для этого
был создан двумерный массив, состоящий из 4 столбцов. В первый столбец были записаны коды русских букв из таблицы ASCII , во второй столбец записаны частоты появления букв исходного текста в соответствии с их кодами из первого столбца. В третий столбец были записаны коды букв из таблицы ASCII зашифрованного текста, а в 4 столбец были записаны частоты появления букв в соответствии с 3 столбцом. Далее, мы сортируем частоты исходного текста и зашифрованного по убыванию, ставим коды букв в соответствии с частотами. И получим, что у нас в каждой строке массива получились одинаковые частоты, но разные коды букв из таблицы ASCII .
Это и есть наши зашифрованные буквы. То есть в 1 столбце массива у нас остались коды букв из таблицы ASCII исходного текста, а в 3 столбце получились коды букв из таблицы ASCII зашифрованного текста. Коды 3 столбца соответствуют кодам букв с 1 столбца. То есть мы расшифровали закодированный текст. Далее мы расшифруем закодированный текст путем замены закодированных букв на соответствующие буквы из 1 столбца. И таким образом, путем применения классического частотного криптоанализа мы расшифровали наш текст.
В ходе проделанной работы были выполнены все поставленные задачи. А именно:
Был изучен алгоритм шифрования текста шифром Цезаря;
Был изучен криптографический метод шифрования информации. А именно частотный криптоанализ;
Был выбран язык программирования, на котором будет реализованы алгоритмы;
Также была реализована практическая часть данной работы. Были написаны алгоритмы программ, необходимых для программы дешифратора;
Была выполнена главная часть работы. Была написана программа дешифратор.
Читайте также: