Сравнительный анализ устойчивости некоторых известных шифров

1. Введение.

2. Методы шифрования.

1. Подстановочные криптоалгоритмы.

1. Шифр Цезаря.

2. «Тарабарская грамота».

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

4. Шифры и арифметика остатков.

5. Частотный анализ.

2. Перестановочные криптоалгоритмы.

1. Перестановочная криптограмма при помощи «ключевого слова».

2. Шифр Тритемиуса.

2. Анализ устойчивости.

4. Заключение.

5. Библиографический список.

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

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

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

Этот период развития криптографии как искусства начался с незапамятных времён до начала XX века, когда появились первые шифровальные машины. Понимание математического характера решаемых задач пришло только в середине XX века - после работ выдающегося американского ученого Клода Шеннона.

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

При современном уровне развития науки и техники сделать абсолютно надежный отдельный (секретный) канал связи между удаленными абонентами для неоднократной передачи больших объемов информации практически нереально.

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

В данной статье использованы следующие понятия:

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

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

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

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

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

Открытый текст – сообщение, текст которого необходимо сделать непонятным для посторонних (зашифровать его).

Вскрытие (взламывание) шифра – процесс получения защищаемой информации (открытого текста) из шифрованного сообщения без знания точного шифра.

Атака на шифр – попытка вскрытия шифра.

Стойкость шифра – способность шифра противостоять всевозможным атакам на него.

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

Методы шифрования

Все криптоалгоритмы (алгоритмы шифрования) подразделяются на группы в зависимости от выбранного для классификации признака.

В работе представлена классификация критоалгоритмов по характеру воздействий, производимых над данными.

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

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

Шифр Цезаря

Один из самых первых методов шифрования носит имя римского Юлия Цезаря (1 век до н. э. ), который если и не сам изобрел его, то активно им пользовался. Этот шифр реализует следующее преобразование открытого текста: каждая буква открытого текста третьей после нее буквой в алфавите, который считается написанным по кругу, т. е. после буквы "я" следует буква "а". Цезарь заменял букву третьей после нее буквой, но можно заменять и какой-нибудь другой. Главное, чтобы тот, кому посылается шифрованное сообщение, знал эту величину сдвига.

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

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

"Тарабарская грамота"

"Тарабарская грамота" - тайнопись, применявшаяся русскими дипломатами XV-XVI веков. Ее еще называли "хитрая литорея", в которой все гласные буквы оставались неизменными, а согласные одна другой по следующей схеме: б в г д ж з к л м н щ ш ч ц х ф т с р п

(в первой строке согласные идут в обычном порядке, а во второй строке - в обратном).

Поскольку в каждом шифре применяют конечное число различных знаков, то их можно перенумеровать и в место самих знаков использовать их номера. Для русского языка можно обойтись 35 знаками: 31 буква (е и ё, ь и ъ не различаются), пробел, точка, запятая, тире.

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

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

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

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

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

Шифры и арифметика остатков

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

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

Каждая буква или знак записываются двузначным числом. Адресату для расшифровки надо разбить полученную последовательность цифр на двузначные числа, вычесть из каждого ключевое слово и заменить полученное число буквой алфавита или знаком препинания. Но если n больше чем 24, то сумма n+11 больше чем 35. Здесь надо вспомнить, что числа писали на кольце. И здесь нужно применить «арифметику остатков»

Частотный анализ

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

Наиболее частая буква русского языка - о. Ее относительная частота, равная 0,090, означает, что на 1000 букв русского языка приходится в среднем 90 букв о. В таблице не указан еще один "символ" - промежуток между словами (пробел). Его относительная частота наибольшая и равна 0,175.

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

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

Перестановочная криптограмма при помощи "ключевого слова"

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

Пусть описан следующий алгоритм шифрования: текст открытого сообщения записывается в 7 столбцов. Каждому из столбцов соответствует одна из букв слова "ЛУНАТИК", которое является ключом. Буквы в ключе пронумерованы в соответствии с их естественным номером в алфавите. Сначала выполняется перестановка столбцов, затем текст считывается по строкам.

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

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

Шифр Тритемиуса

Еще большие трудности для криптоанализа представляет шифр, связываемый с именем ученого аббата из Вюрцбурга Тритемиуса, которого к занятиям криптографией побуждало, быть может, не только монастырское уединение, но и потребность сохранять от огласки некоторые духовные тайны. Этот шифр является развитием шифра Цезаря и состоит в следующем. Буквы алфавита нумеруются по порядку числами 0,1,. ,30. При шифровании некоторое количество слов (или номера его букв) подписывается под сообщением с повторениями, как показано ниже: всвязиссоздавшимсяположениемотодвигаемсрокивозвращениядомойразаписьзаписьзаписьзаписьзаписьзаписьзаписьзаписьзаписьзаписьзмзайапис

Каждая буква сообщения "сдвигается" вдоль алфавита по следующему правилу: буква с номером m, под которой стоит буква с номером k, заменяется на букву с номером l=m+k (если m+k<31) или букву с номером l=m+k-31 (если m+k>31).

Например, первая буква b сдвигается на 7 букв и заменяется буквой i, следующая буква c остается без изменения и т. д. Таким образом, номер l кодирующей буквы вычисляется по формуле:

L = (m+k)mod 31, где mod - операция определения остатка.

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

После суммирования верхней и нижней строки по модулю 31 получаем последовательность чисел:

9. 17. 17. 7. 24. 4. 24. 17. 29. 15. 21. 27. 9. 24. 23. 20. 3. 26. 22. 14. 26. 22. 23. 1. 20. 8. 20. 20. 0. 14. 21. 4. 17. 16. 20. 27. 12. 12. 1. 24. 0. 6. 15. 2. 29. 15. 19. 12. 7. 25. 20. 21. 25. 26. 11. 14. 27. 22. 26. 12. 22. 8. 26.

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

Если ключевое слово известно, то дешифровка производится безо всякого труда на основе равенства

M = (l - k)mod 31

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

Анализ устойчивости

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

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

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

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

Были сформированы 4 группы учащихся 5 - 9 классов, которым предлагались задания по расшифровке сообщений.

При оценке устойчивости применялась временная шкала (в минутах):

25-сообщение не было расшифровано;

10-сообщение расшифровано, но на это затрачено 10 минут;

8-сообщение расшифровано с затратой времени от 6 до 8 минут;

5-сообщение расшифровано с затратой времени от 4 до 5 минут;

3-сообщение расшифровано с затратой времени до 3 минут.

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

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

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

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

Были получены следующие результаты: разгаданными оказались "Тарабарская грамота", шифр Цезаря, шифр двумя цифрами, не разгаданными остались перестановочная криптограмма и шифр Тритемиуса.

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

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

"Тарабарская грамота" - сообщение расшифровано с затратой времени до 3 минут.

Шифр Цезаря - сообщение расшифровано с затратой времени до 3 минут.

Перестановочная криптограмма-сообщение разгадано с затратой времени 8 минут.

Шифр двумя цифрами - сообщение разгадано с затратой времени 8 минут.

Шифр Тритемиуса - сообщение разгадано с затратой времени 10 минут.

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

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

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