Шифрование и дешифрования информации методом замены
Введение
Сообщения, как бы сложны они не были, можно представить себе в виде последовательности знаков. Эти знаки берутся из заранее фиксированного набора, например, русского алфавита или палитры цветов (красный, желтый, зеленый). Разные знаки могут встречаться в сообщениях с разной частотой. Поэтому количество информации, передаваемой разными знаками может быть разным.
Рассмотрим подходы к дешифровке ряда простых шифров, что даст общую картину приемов, используемых в этой области. Существует пропасть между ручными и машинными способами шифровки. Ручные шифры весьма разнообразны и могут быть самыми неожиданными. Кроме того, закрываемые ими сообщения предельно кратки. По этой причине их вскрытие гораздо более эффективно выполняется людьми. Машинные шифры более стереотипны, вычислительно предельно сложны и предназначены для закрытия сообщений очень большой длины. Естественно, что вручную их расшифровать даже и не надо пытаться. Однако и здесь криптоаналитики играют главную роль, выступая в роли полководцев криптографической атаки, хотя само сражение ведут лишь технические и программные средства.
Всегда считаются известными тип шифра и язык сообщения. Их могут подсказать алфавит и статистические свойства шифровки. Однако обычно информация о языке и типе шифра становится известной из агентурных источников. Положение несколько напоминает взлом сейфа: если «медвежатник» и не знает заранее конструкции вскрываемого сейфа, что представляется маловероятным, то он быстро определит ее по внешнему виду, фирменному знаку. Поэтому неизвестным является только ключ, который предстоит вскрыть. Трудность заключается в том, что точно так же, как и не все болезни лечатся одним и тем же лекарством, а для каждой имеются свои специфические средства, так отдельные виды шифров вскрываются только своими приемами.
При традиционном криптоанализе систем шифрования возможность их раскрытия зависит, в значительной мере, от квалификации взломщика. Криптоаналитик должен хорошо владеть методами дискретной математики, теории чисел, теории сложности, абстрактной алгебры, статистики, алгоритмического анализа и прочих родственных криптографии математических дисциплин, а также иметь развитую интуицию, чтобы найти метод, ведущий к вскрытию шифра, предполагая, что он существует. Процесс криптоанализа всякий раз начинается с самого начала при подходе к новой системе и опыт, полученный при раскрытии одной системы шифрования, редко, когда может быть применен для раскрытия другой. Успех криптоанализа определяется алгоритмом шифрования - сложность вскрытия шифра зависит лишь от его конструкции. Это значит, что существует очень мало общих принципов криптоанализа, которые можно было бы практически использовать для раскрытия любых шифров и автоматический криптоанализ эффективен применительно к очень ограниченному классу алгоритмов.
Поэтому практически стойкость шифров к взлому принимается за меру криптографической стойкости их алгоритмов. Чем продолжительнее шифр не поддается раскрытию, тем больше причин считать его стойким. Однако стойкость шифра необязательно значит, что он является безопасным. Это означает лишь, что метод его взлома еще не найден любителями или не опубликован профессионалами. Как пример можно привести шифры, где кроме ключа шифрования имеется еще главный ключ, который называют ключом от черного входа. Такие шифры могут быть стойкими, но они не безопасны, так как обладатель главного ключа может читать любые шифровки. Следовательно, процесс криптоанализа может быть очень длительным по причине того, что криптоаналитику мало помогает успешное раскрытие других систем шифрования и ему неизвестна другая мера криптографической стойкости шифра, кроме продолжительности его сопротивления к взлому. Даже если взломщик не может прочесть сообщение, все равно нужно быть осторожным. В этом случае он может получить много информации, зная отправителя, получателя, время и длину сообщения.
Целью данной курсовой работы является написание компьютерной программы для шифрования и дешифрования информации методом замены.
Задачи:
– изучение проблем защиты информации при ее передаче;
– изучение метода замены для шифрования информации;
– создание формы для взаимодействия с пользователем программы;
– написание кода программы на языке программирования Delphi;
– тестирование программы, поиск недочетов и их устранение.
1 Шифрование
1.1 Общие сведения о шифровании
«Все, что необходимо для обеспечения безопасности – это качественное шифрование».
Это утверждение можно слышать повсеместно. Если информация защищена шифрованием, никто не в силах ее прочесть или изменить. Шифрование можно еще интерпретировать как аутентификацию.
Шифрование – важнейшее средство обеспечения безопасности. Механизмы шифрования помогают защитить конфиденциальность и целостность информации, идентифицировать источник информации. Тем не менее, само по себе шифрование не является решением всех проблем. Оно является только задерживающим действием. Известно, что любая система шифрования может быть взломана.
Шифрование представляет собой сокрытие информации от неавторизованных лиц с предоставлением в это же время авторизованным пользователям доступа к ней. Пользователи называются авторизованными, если у них есть соответствующий ключ для дешифрования информации.
Целью любой системы шифрования является максимальное усложнение получения доступа к информации неавторизованными лицами, даже если у них есть зашифрованный текст и известен алгоритм, использованный для шифрования. Пока неавторизованный пользователь не обладает ключом, секретность и целостность информации не нарушается.
С помощью шифрования обеспечиваются три состояния безопасности информации.
Конфиденциальность. Шифрование
используется для сокрытия
Целостность. Шифрование
используется для
Идентифицируемость. Шифрование
используется для
Термины, связанные с шифрованием:
– обычный текст – информация в исходном виде, также называемая открытым текстом.
– шифрованный текст – информация, подвергнутая действию алгоритма шифрования.
– алгоритм – метод, используемый для преобразования открытого текста в шифрованный текст.
– ключ – входные данные, посредством которых с помощью алгоритма происходит преобразование открытого текста в шифрованный или обратно.
– шифрование – процесс преобразования открытого текста в шифр.
– дешифрование – процесс преобразования шифра в открытый текст.
Существуют также четыре термина, которые необходимо знать:
– криптография – наука о сокрытии информации с помощью шифрования.
– криптограф – лицо, занимающееся криптографией.
– криптоанализ – искусство анализа криптографических алгоритмов на предмет наличия уязвимостей.
– криптоаналитик – лицо, использующее криптоанализ для определения и использования уязвимостей в криптографических алгоритмах.
Системы шифрования могут подвергнуться атакам тремя способами:
– через слабые места в алгоритме;
– посредством атаки «грубой силы» по отношению к ключу;
– через уязвимости в окружающей системе.
Проведение атаки на алгоритм показывает криптоаналитику уязвимости в методе преобразования открытого текста в шифр, чтобы раскрыть открытый текст без использования ключа.
Атаки «грубой силы» – попытками подбора любого возможного ключа для преобразования шифра в открытый текст. В данном случае, чем длиннее ключ, тем больше общее число ключей, и тем больше ключей должен перепробовать злоумышленник до того, как найдет корректный ключ. При наличии необходимого количества времени и ресурсов атаки заканчиваются успешно. Отсюда вывод, алгоритмы нужно оценивать по периоду времени, в течение которого информация остается защищенной при проведении данной атаки. Алгоритм расценивается как безопасный, если затраты на получение ключа с помощью атаки «грубой силы» превышают стоимость самой защищаемой информации.
Использованием уязвимостей в компьютерной системе, как правило, не обсуждается в контексте шифрования. Тем не менее, на практике проще атаковать саму компьютерную систему, чем алгоритм шифрования.
Вывод: система ничуть не меньше влияет на общую безопасность шифров, чем алгоритм шифрования и ключ.
1.2 Описание шифра простой замены
История криптографии насчитывает около 4 тысяч лет. В качестве основного критерия периодизации криптографии возможно использовать технологические характеристики используемых методов шифрования.
Имеются свидетельства, что криптография как техника защиты текста возникла вместе с письменностью, и способы тайного письма были известны уже древним цивилизациям Индии, Египта и Месопотамии. В древнеиндийских текстах среди 64-х искусств названы способы изменения текста, некоторые из них можно отнести к криптографическим. Автор таблички с рецептом для изготовления глазури для гончарных изделий из Месопотамии использовал редкие обозначения, пропускал буквы, а имена заменял на цифры, чтобы скрыть написанное. В дальнейшем встречаются различные упоминания об использовании криптографии, большая часть относится к использованию в военном деле.
Первый период (приблизительно с 3-го тысячелетия до н. э.) характеризуется господством моноалфавитных шифров (основной принцип — замена алфавита исходного текста другим алфавитом через замену букв другими буквами или символами). Второй период (хронологические рамки — с IX века на Ближнем Востоке (Ал-Кинди) и с XV века в Европе (Леон Баттиста Альберти) — до начала XX века) ознаменовался введением в обиход полиалфавитных шифров. Третий период (с начала и до середины XX века) характеризуется внедрением электромеханических устройств в работу шифровальщиков. При этом продолжалось использование полиалфавитных шифров. Четвёртый период — с середины до 70-х годов XX века — период перехода к математической криптографии. В работе Шеннона появляются строгие математические определения количества информации, передачи данных, энтропии, функций шифрования. Обязательным этапом создания шифра считается изучение его уязвимости к различным известным атакам — линейному и дифференциальному криптоанализу. Однако до 1975 года криптография оставалась «классической» или же, более корректно, криптографией с секретным ключом.
Современный период развития криптографии (с конца 1970-х годов по настоящее время) отличается зарождением и развитием нового направления — криптография с открытым ключом. Её появление знаменуется не только новыми техническими возможностями, но и сравнительно широким распространением криптографии для использования частными лицами. Правовое регулирование использования криптографии частными лицами в разных странах сильно различается — от разрешения до полного запрета.
Современная криптография образует отдельное научное направление на стыке математики и информатики — работы в этой области публикуются в научных журналах, организуются регулярные конференции. Практическое применение криптографии стало неотъемлемой частью жизни современного общества — её используют в таких отраслях, как электронная коммерция, электронный документооборот (включая цифровые подписи), телекоммуникации и других.
Наиболее известными и часто используемыми шифрами являются шифры замены. Они характеризуются тем, что отдельные части сообщения (буквы, слова...) заменяются на какие-либо другие буквы, числа, символы и т.д. При этом замена осуществляется так, чтобы потом, по шифрованному сообщению, можно было однозначно восстановить передаваемое сообщение.
Шифрами замены называются такие шифры, преобразования из которых приводят к замене каждого символа открытого сообщения на другие символы - шифробозначения, причем порядок следования шифробозначений совпадает с порядком следования соответствующих им символов открытого сообщения.
Пусть, например, зашифровывается сообщение на русском языке и при этом замене подлежит каждая буква сообщения. Формально в этом случае шифр замены можно описать следующим образом. Для каждой буквы б исходного алфавита строится некоторое множество символов Мб так, что множества Мб и Мв попарно не пересекаются при б ≠ в, то есть любые два различные множества не содержат одинаковых элементов (таблица 1). Множество Мб называется множеством шифробозначений для буквы б.
а |
б |
в |
… |
я |
Ма |
Мб |
Мв |
… |
Мя |
Таблица 1 – таблица соответствия
Таблица 1 является ключом шифра замены. Зная ее, можно осуществить как зашифрование, так и расшифрование.
Шифр простой замены, простой подстановочный шифр, моноалфавитный шифр — класс методов шифрования, которые сводятся к созданию по определённому алгоритму таблицы шифрования, в которой для каждой буквы открытого текста существует единственная сопоставленная ей буква шифр-текста. Само шифрование заключается в замене букв согласно таблице. Для расшифровки достаточно иметь ту же таблицу, либо знать алгоритм, по которой она генерируется.
При зашифровании каждая буква, а открытого сообщения, начиная с первой, заменяется любым символом из множества Ма. Если в сообщении содержится несколько букв а, то каждая из них заменяется на любой символ из Ма. За счет этого с помощью одного ключа (1) можно получить различные варианты зашифрованного сообщения для одного и того же открытого сообщения.
Например, если ключом является:
а б в г д е ж з и к л м н о п р
21 37 14 22 01 24 62 73 46 23 12 08 27 53 35 04
40 26 63 47 31 83 88 30 02 91 72 32 77 68 60 44
10 03 71 82 5 70 11 55 90 69 38 61 54 09 84 45
с т у ф х ц ч ш щ ъ ы ь э ю я
20 13 59 25 75 43 19 29 06 65 74 48 36 28 16
52 39 07 49 33 85 58 80 50 34 17 56 78 64 41
89 67 93 76 18 51 87 66 81 92 42 79 86 05 57
то сообщение «я знаком с шифрами замены» может быть зашифровано, например, любым из следующих трех способов:
16 55 54 10 69 09 61 89 29 90 49 44 10 08 02 73 21 32 83 54 74
41 55 77 10 23 68 08 20 66 90 76 44 21 61 90 55 21 61 83 54 42
57 30 27 10 91 68 32 20 80 02 49 45 40 32 46 55 40 08 83 27 42
Так как множества М0, М6, Мд, ..., Мя попарно не пересекаются, то по каждому символу шифрованного сообщения можно однозначно определить, какому множеству он принадлежит, и, следовательно, какую букву открытого сообщения он заменяет. Поэтому расшифрование возможно и открытое сообщение определяется единственным образом. В рассказе А. Конан Доила «Пляшущие человечки» каждый символ изображает пляшущего человечка в самых различных позах.
На первый взгляд кажется, что чем хитрее символы, тем труднее вскрыть сообщение, не имея ключа. Это, конечно, не так. Если каждому символу однозначно сопоставить какую-либо букву или число, то легко перейти к зашифрованному сообщению из букв или чисел. С точки зрения криптографов использование различных сложных символов не усложняет шифра. Однако, если зашифрованное сообщение состоит из букв или цифр, то вскрывать такое сообщение удобнее.
Рассмотрим некоторые примеры шифров замены. Пусть каждое множество Ма состоит из одной буквы. Например,
а б в г д е ж з и к л м н о п р с т у ф х ц ч ш щ ъ ы ь э ю я
г л ь п д р а м ц в э ъ х о б н с ж я и ю к щ ф е у ы ч ш т а
Такой шифр называется шифром простой однобуквенной замены. По этому ключу удобно проводить зашифрование и расшифрование: при зашифровании каждая буква открытого текста заменяется на соответствующую букву из второй строки (а на г и т. д.) При расшифровании, наоборот, г заменяется на а и т. д. При шифровании и расшифровании надо помнить вторую строчку, то есть ключ. Запомнить произвольный порядок букв алфавита достаточно сложно. Поэтому всегда пытались придумать какое-либо правило, по которому можно просто восстановить вторую строчку. Другим примером шифра замены может служить лозунговый шифр. Здесь запоминание ключевой последовательности основано на лозунге — легко запоминаемом слове. Например, выберем слово-лозунг «учебник» и заполним вторую строку таблицы по следующему правилу: сначала выписываем слово-лозунг, а затем выписываем в алфавитном порядке буквы алфавита, не вошедшие в слово- лозунг. Вторая строка примет вид: у ч е б н и к а в
у ч е б н и к а в г д ж з л м о
п р с т ф х ц ш щ ъ ы ь э ю я
В данном случае число вариантов ключа существенно больше букв алфавита. Рассмотренные шифры имеют одну слабость. Если в открытом сообщении часто встречается какая-либо буква, то в шифрованном сообщении часто будет встречаться соответствующий ей символ или буква. Поэтому при вскрытии шифра замены обычно стараются наиболее часто встречающимся символам шифрованного сообщения поставить в соответствие буквы открытого сообщения с наибольшей предполагаемой частотой появления. Если шифрованное сообщение достаточно большое, то этот путь приводит к успеху, даже если вы не знаете ключа. При анализе шифрованного сообщения следует исходить из того, что число различных вариантов для части определяемого ключа не такое уж большое, если вы находитесь на правильном пути. В противном случае либо вы получите противоречие, либо число вариантов ключа будет сильно возрастать. Обычно, начиная с некоторого момента определение открытого сообщения, становится делом техники. Вообще-то можно сказать, что вскрытие шифров замены является искусством и достаточно трудно формализовать этот процесс. Популярные у школьников криптограммы по сути дела являются шифром замены с ключом
0 1 2 3 4 5 6 7 8 9
ш и ф р з а м е н ы
в котором каждой цифре ставится в соответствие буква. При этом должны соблюдаться правила арифметики. Эти правила значительно облегчают определение открытого текста. Если шифрованное сообщение написано без пробелов между символами, то появляется дополнительная трудность при разбиении шифрованного Другое направление создания шифров замены состоит в том, чтобы множества шифробозначений Ма содержали более одного элемента. Такие шифры получили название шифров многозначной замены. Они позволяют скрыть истинную частоту букв открытого сообщения, что существенно затрудняет вскрытие этих шифров. Главная трудность, которая возникает при использовании таких шифров, заключается в запоминании ключа. Надо запомнить не одну строчку, а для каждой буквы алфавита а — множество ее шифробозначений Ма. Как правило, элементами множеств Ма являются числа. Из художественной литературы и кинофильмов про разведчиков известно, что во время второй мировой войны часто использовались так называемые книжные шифры. Множество шифробозначений для каждой буквы определяется всеми пятизначными наборами цифр, в каждом из которых первые две цифры указывают номер страницы, третья цифра — номер строки, четвертая и пятая цифры — номер места данной буквы в указанной строке. Поэтому при поимке разведчика всегда пытались найти книгу, которая могла быть использована им в качестве ключа.
1.3 Шифр Атбаш
К шифрам простой замены относятся многие способы шифрования, возникшие в древности или средневековье, как, например, Атбаш (также читается как этбаш) или Шифр Цезаря. Для вскрытия подобных шифров используется частотный криптоанализ.
Отметим, что шифр простой замены не всегда подразумевает замену буквы на какую-то другую букву. Допускается использовать замену буквы на цифру. К примеру, представим некий шифр-алфавит: А - 33; Б - 17; В - 8; Г - 16; Д - 2; Е - 15; Ё - 14; Ж - 13; З - 12; И - 98; Й - 10; К - 97; Л - 96; М - 24; Н - 0; О - 11; П - 5; Р - 25; С - 7; Т - 3; У - 64; Ф - 26; Х - 66; Ц - 69; Ч - 4; Ш - 6; Щ - 36; Ь - 21; Ъ - 22; Ы - 23; Э - 37; Ю - 39; Я - 18.
В данном шифре применяются цифры, заменяющие буквы. Никакой логики в этих цифрах нет. Такой простой шифр можно расшифровать, только имея таблицу шифров.
В шифрах простой замены замена производится только над одним-единственным символом. Для наглядной демонстрации шифра простой замены достаточно выписать под заданным алфавитом тот же алфавит, но в другом порядке или, например, со смещением. Записанный таким образом алфавит называют алфавитом замены.
Шифр Атбаш – шифр простой замены, использованный для еврейского алфавита и получивший оттуда свое название. Шифрование происходит заменой первой буквы алфавита на последнюю, второй на предпоследнюю (алеф (первая буква) заменяется на тав (последнюю), бет (вторая) заменяется на шин (предпоследняя); из этих сочетаний шифр и получил свое название). Шифр Атбаш для английского алфавита:
Исходный алфавит: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z;
Алфавит замены: Z Y X W V U T S R Q P O N M L K J I H G F E D C B A.
Шифр Атбаш был, скорее всего, изобретен Ессеями, иудейской сектой повстанцев. Они разработали множество различных кодов и шифров, которые использовались для сокрытия важных имен и названий, чтобы потом избежать преследования. Знания этих кодов и шифров были потом переданы Гностикам, которые, в свою очередь, передали их Катарам. Позже Орден Тамплиеров завербовал Катарских дворян и перенял знания шифров. Таким образом, шифр был использован на протяжении многих лет, от около 500 до н. э. до 1300 г. н. э. — момента, когда Орден Тамплиеров был распущен.
Позже Шонфилд стал интересоваться обвинениями в ереси, выдвинутыми против тамплиеров и, частично этимологией Бафомет. Шонфилд решил, что он применит к Бафомету шифр Atbash, которым, как он был убежден, владели тамплиеры.
Хотя и написано на иврите, это звучит как греческое слово Sophia, что означает «Мудрость» на английском языке. Тем не менее, есть ещё один оттенок этого термина, говорящий, что София была богиней, невестой Бога.
Многие придерживались мнения, что тамплиеры были последователями богини или, как минимум, придерживались факта женской божественности, которая была отвергаема в церкви. Следует помнить, что их покровитель, святой Бернард из Клерво был одержим Марией и настоял на признании её как царицы Небес и как Матери Божией. Были ли тамплиеры поклонниками богини или просто были мудры по отношению к женщинам, но без сомнения, теория Шонфилда о шифре Atbash является одной из наиболее правдоподобных объяснений этимологии Бафомета.
1.4 Шифр Цезаря
Шифр Цезаря — один из древнейших шифров. При шифровании каждая буква заменяется другой, отстоящей от ней в алфавите на фиксированное число позиций. Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки. Естественным развитием шифра Цезаря стал шифр Виженера. Пример щифрования с использованием ключа k = 4:
Исходный алфавит: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z;
Алфавит замены: E F G H I J K L M N O P Q R S T U V W X Y Z A B C D.
Современным примером шифра Цезаря является ROT13. Он сдвигает каждый символ английского алфавита на 13 позиций. Используется в интернет-форумах, как средство для сокрытия спойлеров, основных мыслей, решений загадок и оскорбительных материалов от случайного взгляда.
Шифр с использованием кодового слова является одним из самых простых как в реализации, так и в расшифровывании. Идея заключается в том, что выбирается кодовое слово, которое пишется впереди, затем выписываются остальные буквы алфавита в своем порядке. Шифр с использованием кодового слова WORD.
Исходный алфавит: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z;
Алфавит замены: W O R D A B C E F G H I J K L M N P Q S T U V X Y Z.
Как мы видим, при использовании короткого кодового слова мы получаем очень и очень простую замену. Также мы не можем использовать в качестве кодового слова слова с повторяющимися буквами, так как это приведёт к неоднозначности расшифровки, то есть двум различным буквам исходного алфавита будет соответствовать одна и та же буква шифрованного текста.
По традиции, зашифрованный текст пишут блоками (другое название «группы») по 5 символов, не учитывая пунктуацию и пробелы. Это помогает избежать ошибок при передаче шифрованного сообщения и позволяет скрыть границы слов в исходном тексте. Блок содержит 5 символов, так как раньше их было удобно передавать по телеграфу.
Главный недостаток этого метода шифрования — это то, что последние буквы алфавита (которые имеют низкие коэффициенты при частотном анализе) имеют тенденцию оставаться в конце. Более защищённый способ построить алфавит замены состоит в том, чтобы выполнить колоночное перемещение (перемещение столбцов) в алфавите, используя ключевое слово, но это нечасто делается. Несмотря на то, что число возможных ключей является очень большим (26! = 288.4), этот вид шифра может быть легко взломанным. При условии, что сообщение имеет достаточную длину, криптоаналитик может предположить значения некоторых самых распространённых букв исходя из анализа частотного распределения символов в зашифрованном тексте. Это позволяет формировать отдельные слова, которые могут быть предварительно использованы, для последующего получения более полного решения (частотный анализ). Согласно расстоянию уникальности английского языка 27.6 букв от зашифрованного текста должно быть достаточно, чтобы взломать шифр простой замены. На практике обычно достаточно около 50 символов для взлома, хотя некоторые шифротексты могут быть взломаны и с меньшим количеством символов, если найдены какие-либо нестандартные структуры. Но при равномерном распределении символов в тексте могут потребоваться куда более длинные шифротексты для взлома.