что такое программа для криптоанализа

Классический криптоанализ

На протяжении многих веков люди придумывали хитроумные способы сокрытия информации — шифры, в то время как другие люди придумывали еще более хитроумные способы вскрытия информации — методы взлома.

В этом топике я хочу кратко пройтись по наиболее известным классическим методам шифрования и описать технику взлома каждого из них.

Шифр Цезаря

Самый легкий и один из самых известных классических шифров — шифр Цезаря отлично подойдет на роль аперитива.
Шифр Цезаря относится к группе так называемых одноалфавитных шифров подстановки. При использовании шифров этой группы «каждый символ открытого текста заменяется на некоторый, фиксированный при данном ключе символ того же алфавита» wiki.

Способы выбора ключей могут быть различны. В шифре Цезаря ключом служит произвольное число k, выбранное в интервале от 1 до 25. Каждая буква открытого текста заменяется буквой, стоящей на k знаков дальше нее в алфавите. К примеру, пусть ключом будет число 3. Тогда буква A английского алфавита будет заменена буквой D, буква B — буквой E и так далее.

Для наглядности зашифруем слово HABRAHABR шифром Цезаря с ключом k=7. Построим таблицу подстановок:

И заменив каждую букву в тексте получим: C(‘HABRAHABR’, 7) = ‘OHIYHOHIY’.

При расшифровке каждая буква заменяется буквой, стоящей в алфавите на k знаков раньше: D(‘OHIYHOHIY’, 7) = ‘HABRAHABR’.

Криптоанализ шифра Цезаря

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

Аффиный шифр

Рассмотрим немного более интересный одноалфавитный шифр подстановки под названием аффиный шифр. Он тоже реализует простую подстановку, но обеспечивает немного большее пространство ключей по сравнению с шифром Цезаря. В аффинном шифре каждой букве алфавита размера m ставится в соответствие число из диапазона 0… m-1. Затем при помощи специальной формулы, вычисляется новое число, которое заменит старое в шифртексте.

Процесс шифрования можно описать следующей формулой:

,

где x — номер шифруемой буквы в алфавите; m — размер алфавита; a, b — ключ шифрования.

Для расшифровки вычисляется другая функция:

,

С учетом этого ограничения вычислим пространство ключей аффиного шифра на примере английского алфавита. Так как английский алфавит содержит 26 букв, то в качестве a может быть выбрано только взаимно простое с 26 число. Таких чисел всего двенадцать: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 и 25. Число b в свою очередь может принимать любое значение в интервале от 0 до 25, что в итоге дает нам 12*26 = 312 вариантов возможных ключей.

Криптоанализ аффиного шифра

Очевидно, что и в случае аффиного шифра простейшим способом взлома оказывается перебор всех возможных ключей. Но в результате перебора получится 312 различных текстов. Проанализировать такое количество сообщений можно и в ручную, но лучше автоматизировать этот процесс, используя такую характеристику как частота появления букв.

Давно известно, что буквы в естественных языках распределены не равномерно. К примеру, частоты появления букв английского языка в текстах имеют следующие значения:

Т.е. в английском тексте наиболее встречающимися буквами будут E, T, A. В то время как самыми редкими буквами являются J, Q, Z. Следовательно, посчитав частоту появления каждой буквы в тексте мы можем определить насколько частотная характеристика текста соответствует английскому языку.

Для этого необходимо вычислить значение:

,

где n_i — частота i-й буквы алфавита в естественном языке. И f_i — частота i-й буквы в шифртексте.

Чем больше значение χ, тем больше вероятность того, что текст написан на естественном языке.

Таким образом, для взлома аффиного шифра достаточно перебрать 312 возможных ключей и вычислить значение χ для полученного в результате расшифровки текста. Текст, для которого значение χ окажется максимальным, с большой долей вероятности и является зашифрованным сообщением.

Разумеется следует учитывать, что метод не всегда работает с короткими сообщениями, в которых частотные характеристики могут сильно отличатся от характеристик естественного языка.

Шифр простой замены

Очередной шифр, относящийся к группе одноалфавитных шифров подстановки. Ключом шифра служит перемешанный произвольным образом алфавит. Например, ключом может быть следующая последовательность букв: XFQABOLYWJGPMRVIHUSDZKNTEC.

При шифровании каждая буква в тексте заменяется по следующему правилу. Первая буква алфавита замещается первой буквой ключа, вторая буква алфавита — второй буквой ключа и так далее. В нашем примере буква A будет заменена на X, буква B на F.

При расшифровке буква сперва ищется в ключе и затем заменяется буквой стоящей в алфавите на той же позиции.

Криптоанализ шифра простой замены

Шифр Полибия

Еще один шифр подстановки. Ключом шифра является квадрат размером 5*5 (для английского языка), содержащий все буквы алфавита, кроме J.

При шифровании каждая буква исходного текста замещается парой символов, представляющих номер строки и номер столбца, в которых расположена замещаемая буква. Буква a будет замещена в шифртексте парой BB, буква b — парой EB и так далее. Так как ключ не содержит букву J, перед шифрованием в исходном тексте J следует заменить на I.

Например, зашифруем слово HABRAHABR. C(‘HABRAHABR’) = ‘AB BB EB DA BB AB BB EB DA’.

Криптоанализ шифра Полибия

Шифр имеет большое пространство ключей (25! = 2 83 для английского языка). Однако единственное отличие квадрата Полибия от предыдущего шифра заключается в том, что буква исходного текста замещается двумя символами.

Поэтому для атаки можно использовать методику, применяемую при взломе шифра простой замены — поиск восхождением к вершине.
В качестве основного ключа выбирается случайный квадрат размером 5*5. В ходе каждой итерации ключ подвергается незначительным изменениям и проверяется насколько распределение триграмм в тексте, полученном в результате расшифровки, соответствует распределению в естественном языке.

Перестановочный шифр

Помимо шифров подстановки, широкое распространение также получили перестановочные шифры. В качестве примера опишем Шифр вертикальной перестановки.

В процессе шифрования сообщение записывается в виде таблицы. Количество колонок таблицы определяется размером ключа. Например, зашифруем сообщение WE ARE DISCOVERED. FLEE AT ONCE с помощью ключа 632415.

Так как ключ содержит 6 цифр дополним сообщение до длины кратной 6 произвольно выбранными буквами QKJEU и запишем сообщение в таблицу, содержащую 6 колонок, слева направо:

Для получения шифртекста выпишем каждую колонку из таблицы в порядке, определяемом ключом: EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE.

При расшифровке текст записывается в таблицу по колонкам сверху вниз в порядке, определяемом ключом.

Криптоанализ перестановочного шифра

Лучшим способом атаки шифра вертикальной перестановки будет полный перебор всех возможных ключей малой длины (до 9 включительно — около 400 000 вариантов). В случае, если перебор не дал желаемых результатов, можно воспользоваться поиском восхождением к вершине.

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

Шифр Плейфера

Шифр Плейфера — подстановочный шифр, реализующий замену биграмм. Для шифрования необходим ключ, представляющий собой таблицу букв размером 5*5 (без буквы J).

Процесс шифрования сводится к поиску биграммы в таблице и замене ее на пару букв, образующих с исходной биграммой прямоугольник.
Рассмотрим, в качестве примера следующую таблицу, образующую ключ шифра Плейфера:

Зашифруем пару ‘WN’. Буква W расположена в первой строке и первой колонке. А буква N находится во второй строке и третьей колонке. Эти буквы образуют прямоугольник с углами W-E-S-N. Следовательно, при шифровании биграмма WN преобразовывается в биграмму ES.
В случае, если буквы расположены в одной строке или колонке, результатом шифрования является биграмма расположенная на одну позицию правее/ниже. Например, биграмма NG преобразовывается в биграмму GP.

Криптоанализ шифра Плейфера

Так как ключ шифра Плейфера представляет собой таблицу, содержащую 25 букв английского алфавита, можно ошибочно предположить, что метод поиска восхождением к вершине — лучший способ взлома данного шифра. К сожалению, этот метод не будет работать. Достигнув определенного уровня соответствия текста, алгоритм застрянет в точке локального максимума и не сможет продолжить поиск.
Чтобы успешно взломать шифр Плейфера лучше воспользоваться алгоритмом имитации отжига.

Отличие алгоритма имитации отжига от поиска восхождением к вершине заключается в том, что последний на пути к правильному решению никогда не принимает в качестве возможного решения более слабые варианты. В то время как алгоритм имитации отжига периодически откатывается назад к менее вероятным решениям, что увеличивает шансы на конечный успех.

Суть алгоритма сводится к следующим действиям:

Для расчета коэффициентов, определяющих принадлежность текста к естественному языку лучше всего использовать частоты появления триграмм.

Шифр Виженера

Шифр Виженера относится к группе полиалфавитных шифров подстановки. Это значит, что в зависимости от ключа одна и та же буква открытого текста может быть зашифрована в разные символы. Такая техника шифрования скрывает все частотные характеристики текста и затрудняет криптоанализ.

Шифр Виженера представляет собой последовательность нескольких шифров Цезаря с различными ключами.

Продемонстрируем, в качестве примера, шифрование слова HABRAHABR с помощью ключа 123. Запишем ключ под исходным текстом, повторив его требуемое количество раз:

Цифры ключа определяют на сколько позиций необходимо сдвинуть букву в алфавите для получения шифртекста. Букву H необходимо сместить на одну позицию — в результате получается буква I, букву A на 2 позиции — буква C, и так далее. Осуществив все подстановки, получим в результате шифртекст: ICESCKBDU.

Криптоанализ шифра Виженера

Первая задача, стоящая при криптоанализе шифра Виженера заключается в нахождении длины, использованного при шифровании, ключа.

Для этого можно воспользоваться индексом совпадений.

Индекс совпадений — число, характеризующее вероятность того, что две произвольно выбранные из текста буквы окажутся одинаковы.
Для любого текста индекс совпадений вычисляется по формуле:

,

где f_i — количество появлений i-й буквы алфавита в тексте, а n — количество букв в тексте.

Для английского языка индекс совпадений имеет значение 0.0667, в то время как для случайного набора букв этот показатель равен 0.038.
Более того, для текста зашифрованного с помощью одноалфавитной подстановки, индекс совпадений также равен 0.0667. Это объясняется тем, что количество различных букв в тексте остается неизменным.

Это свойство используется для нахождения длины ключа шифра Виженера. Из шифртекста по очереди выбираются каждая вторая буквы и для полученного текста считается индекс совпадений. Если результат примерно соответствует индексу совпадений естественного языка, значит длина ключа равна двум. В противном случае из шифртекста выбирается каждая третья буква и опять считается индекс совпадений. Процесс повторяется пока высокое значение индекса совпадений не укажет на длину ключа.

Успешность метода объясняется тем, что если длина ключа угадана верно, то выбранные буквы образуют шифртекст, зашифрованный простым шифром Цезаря. И индекс совпадений должен быть приблизительно соответствовать индексу совпадений естественного языка.
После того как длина ключа будет найдена взлом сводится к вскрытию нескольких шифров Цезаря. Для этого можно использовать способ, описанный в первом разделе данного топика.

Исходники всех вышеописанных шифров и атак на них можно посмотреть на GitHub.

Источник

Учебное пособие по криптографии: криптоанализ, RC4, CrypTool

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

В этой статье мы познакомим вас с миром криптологии и познакомим вас с тем, как защитить информацию от попадания в чужие руки.

Что такое криптография?

Криптография — это изучение и применение методов, которые скрывают реальный смысл информации, преобразовывая ее в форматы, нечитаемые человеком, и наоборот.

Проиллюстрируем это на примере. Предположим, вы хотите отправить сообщение «Я ЛЮБЛЮ ЯБЛОКИ», вы можете заменить каждую букву во фразе третьей последовательной буквой в алфавите. Зашифрованное сообщение будет иметь вид «K NQXG CRRNGV». Чтобы расшифровать наше сообщение, нам нужно будет вернуться на три буквы в алфавите, используя букву, которую мы хотим расшифровать. На изображении ниже показано, как выполняется преобразование.

Процесс преобразования информации в нечитаемую человеком форму называется шифрованием.

Процесс обратного шифрования называется расшифровкой.

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

Зашифрованная информация называется шифром.

Что такое криптоанализ?

Криптоанализ — это искусство попытки расшифровать зашифрованные сообщения без использования ключа, который использовался для шифрования сообщений. Криптоанализ использует математический анализ и алгоритмы для расшифровки шифров. Успех атак криптоанализа зависит от:

Ниже приведен список наиболее часто используемых атак криптоанализа:

Что такое криптология?

Криптология сочетает в себе методы криптографии и криптоанализа.

Алгоритмы шифрования

MD5 — это аббревиатура от Message-Digest 5. Используется для создания 128-битных хеш-значений. Теоретически хеши нельзя преобразовать в исходный простой текст. MD5 используется для шифрования паролей, а также для проверки целостности данных.

MD5 не устойчив к столкновениям. Устойчивость к коллизиям — это трудности нахождения двух значений, которые дают одинаковые хеш-значения.

Хакерская активность: используйте CrypTool

В этом практическом сценарии мы создадим простой шифр, используя алгоритм RC4. Затем мы попытаемся расшифровать его, используя атаку грубой силы. Для этого упражнения предположим, что мы знаем, что секретный ключ шифрования составляет 24 бита. Мы будем использовать эту информацию, чтобы взломать шифр.

Мы будем использовать CrypTool 1 в качестве нашего инструмента криптологии. CrypTool 1 — это образовательный инструмент с открытым исходным кодом для криптологических исследований. Вы можете скачать его с

Создание потокового шифра RC4

Зашифруем следующую фразу:

Никогда не недооценивайте решимость ребенка, у которого много времени и мало денег

Мы будем использовать 00 00 00 в качестве ключа шифрования.

Атака на потоковый шифр

Резюме

Криптография — это наука о шифровании и расшифровке сообщений.

Шифр — это сообщение, которое было преобразовано в формат, нечитаемый человеком.
Расшифровка превращает шифр в исходный текст.

Криптоанализ — это искусство расшифровки шифров без знания ключа, используемого для их шифрования.
Криптология сочетает в себе методы криптографии и криптоаналитика.

Источник

Что такое программа для криптоанализа

Применение частотного криптоанализа в написании программы дешифратора

Автор работы награжден дипломом победителя III степени

В настоящее время первостепенным фактором, влияющим на политическую и экономическую составляющие национальной безопасности, является степень защищенности информации и информационной среды. Вследствие чего большое значение приобретают вопросы обеспечения безопасности информационных и телекоммуникационных технологий и гарантированной защиты данных в компьютерных сетях экономически значимых структур. О необходимости надежной защиты свидетельствуют многочисленные компьютерные преступления, совершаемые как в кредитно-финансовой сфере, так и в государственных органах.
Защита информации в компьютерных системах обладает рядом специфических особенностей, связанных с тем, что информация не является жестко связанной с носителем, может легко и быстро копироваться и передаваться по каналам связи. Известно очень большое число угроз информации, которые могут быть реализованы как со стороны внешних нарушителей, так и со стороны внутренних нарушителей.
В данной работе рассматривается решение проблем защиты электронной информации на базе использования криптографических методов, которые позволяют решать важнейшие проблемы защищенной автоматизированной обработки и передачи данных

Цель работы: Изучить методы частотного криптоанализа для написания программы дешифратора.

Цель достигается посредством решения следующих задач:

ознакомиться с простейшими методами шифрования информации;

изучить метод частотного криптоанализа;

выбрать язык, текст на котором будет дешифроваться;

реализовать алгоритмы на алгоритмическом языке;

Простейшие методы шифрования информации

Шифр Цезаря, также известный как шифр сдвига, код Цезаря или сдвиг Цезаря — один из самых простых и наиболее широко известных методов шифрования.

Шифр Цезаря — это вид шифра подстановки, в котором каждый символ в открытом тексте заменяется символом, находящимся на некотором постоянном числе позиций левее или правее него в алфавите. Например, в шифре со сдвигом вправо на 3, А была бы заменена на Г, Б станет Д, и так далее.

Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки со своими генералами.

Шаг шифрования, выполняемый шифром Цезаря, часто включается как часть более сложных схем, таких как шифр Виженера, и все ещё имеет современное приложение в системе ROT13. Как и всемоноалфавитные шифры, шифр Цезаря легко взламывается и не имеет практически никакого применения на практике.

Криптоанализ (от др.-греч κρυπτός — скрытый и анализ) — наука о методах расшифровки зашифрованной информации без предназначенного для такой расшифровки ключа.

Термин был введён американским криптографом Уильямом Ф. Фридманом в 1920 году. Неформально криптоанализ называют также взломом шифра.

В большинстве случаев под криптоанализом понимается выяснение ключа; криптоанализ включает также методы выявления уязвимости криптографических алгоритмов или протоколов.

Первоначально методы криптоанализа основывались на лингвистических закономерностях естественного текста и реализовывались с использованием только карандаша и бумаги. Со временем в криптоанализе нарастает роль чисто математических методов, для реализации которых используются специализированные криптоаналитические компьютеры.

Попытку раскрытия конкретного шифра с применением методов криптоанализа называют криптографической атакой на этот шифр. Криптографическую атаку, в ходе которой раскрыть шифр удалось, называют взломом или вскрытием.

Частотный анализ, частотный криптоанализ — один из методов криптоанализа, основывающийся на предположении о существовании нетривиального статистического распределения отдельных символов и их последовательностей как в открытом тексте, так и в шифротексте, которое, с точностью до замены символов, будет сохраняться в процессе шифрования и дешифрования.

Упрощённо, частотный анализ предполагает, что частота появления заданной буквы алфавита в достаточно длинных текстах одна и та же для разных текстов одного языка. При этом в случае моноалфавитного шифрования если в шифротексте будет символ с аналогичной вероятностью появления, то можно предположить, что он и является указанной зашифрованной буквой. Аналогичные рассуждения применяются к биграммам (двубуквенным последовательностям), триграммам и т.д. в случае полиалфавитных шифров.

Метод частотного криптоанализа известен с IX-го века (работы Ал-Кинди), хотя наиболее известным случаем его применения в реальной жизни, возможно, является дешифровка египетских иероглифов Ж.-Ф. Шампольоном в 1822 году. В художественной литературе наиболее известными упоминаниями являются рассказы «Золотой жук» Эдгара По, «Пляшущие человечки» Конан Дойля, а также роман «Дети капитана Гранта» Жюль Верна.

Начиная с середины XX века большинство используемых алгоритмов шифрования разрабатываются устойчивыми к частотному криптоанализу, поэтому он применяется, в основном, для обучения.

Описание частотного криптоанализа

Утверждается, что вероятность появления отдельных букв, а также их порядок в словах и фразах естественного языка подчиняются статистическим закономерностям: например, пара стоящих рядом букв «ся» в русском языке более вероятна, чем «цы», а « оь » в русском языке не встречается вовсе (зато часто встречается, например, в чеченском ). Анализируя достаточно длинный текст, зашифрованный методом замены, можно по частотам появления символов произвести обратную замену и восстановить исходный текст.

Как упоминалось выше, важными характеристиками текста являются повторяемость букв (количество различных букв в каждом языке ограничено), пар букв, то есть m (m-грамм), сочетаемость букв друг с другом, чередование гласных и согласных и некоторые другие особенности. Примечательно, что эти характеристики являются достаточно устойчивыми.

Идея состоит в подсчете чисел вхождений каждой n m возможных m-грамм в достаточно длинных открытых текстах T=t₁t₂…t_l, составленных из букв алфавита ₁, a₂, …, a_n>. При этом просматриваются подряд идущие m-граммы текста:

В силу этого, относительную частоту считают приближением вероятности P (a_i1a_i2…a_im) появления данной m-граммы в случайно выбранном месте текста (такой подход принят при статистическом определении вероятности).

В общем смысле частоту букв в процентном выражении можно определить следующим образом: подсчитывается сколько раз она встречается в шифро-тексте, затем полученное число делится на общее число символов шифро-текста; для выражения в процентном выражении, еще умножается на 100.

Но существует некоторая разница значений частот, которая объясняется тем, что частоты существенно зависят не только от длины текста, но и от характера текста. Например, текст может быть технического содержания, где редкая буква Ф может стать довольно частой. Поэтому для надежного определения средней частоты букв желательно иметь набор различных текстов.

Практическая часть работы заключается в написании программы дешифратора и она состоит из 5 этапов:

выбор языка программирования, на котором будут реализовываться алгоритмы;

выбор языка, текст на котором будет шифроваться и дешифроваться;

реализация зашифровки текста алгоритмом шифра Цезаря на алгоритмическом языке PascalABC ;

подсчет частот появления каждой буквы в идеальном и зашифрованном текстах и реализация подсчета частот на алгоритмическом языке PascalABC ;

расшифровка закодированного текста на основе идеального путем использования частотного криптоанализа.

Следующим этапом практической части данной работы был выбор языка, тексты на котором будут шифроваться и дешифроваться. Выбирая между русским и английским языком, я решил выбрать русский для более наглядного представления зашифрованного текста. Также русский язык наиболее легок для понимания.

4 Этап. Следующий шаг моей практической работы заключался в подсчете частот появления букв в зашифрованном и исходном тексте. Именно с помощью частот появления букв мы сможем дешифровать текст. Частоту мы считаем следующим образом:

Считаем общее количество букв в тексте;

Считаем сколько раз каждая буква встречается в тексте;

Делим подсчитанное количество каждой буквы на общее количество букв в тексте и, таким образом, получаем частоту появления каждой буквы в тексте.

Программа была реализована и представлена в приложении Б и В.

5 Этап. Завершающим этапом моей работы было расшифровка текста частотным криптоанализом. Для этого была написана программа дешифратор. Для этого

Это и есть наши зашифрованные буквы. То есть в 1 столбце массива у нас остались коды букв из таблицы ASCII исходного текста, а в 3 столбце получились коды букв из таблицы ASCII зашифрованного текста. Коды 3 столбца соответствуют кодам букв с 1 столбца. То есть мы расшифровали закодированный текст. Далее мы расшифруем закодированный текст путем замены закодированных букв на соответствующие буквы из 1 столбца. И таким образом, путем применения классического частотного криптоанализа мы расшифровали наш текст.

В ходе проделанной работы были выполнены все поставленные задачи. А именно:

Был изучен алгоритм шифрования текста шифром Цезаря;

Был изучен криптографический метод шифрования информации. А именно частотный криптоанализ;

Был выбран язык программирования, на котором будет реализованы алгоритмы;

Также была реализована практическая часть данной работы. Были написаны алгоритмы программ, необходимых для программы дешифратора;

Была выполнена главная часть работы. Была написана программа дешифратор.

2) Савельев А. Я. «Основы информатики: Учебник для вузов». – М.: Оникс 2001.-370с

4) Ведеев Д. «Защита данных в компьютерных сетях. Открытые системы».- М.: Дрофа 1995, №3.-180с

Источник