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

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

1. Введение

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

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

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

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

 

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

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

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

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

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

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

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

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

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

Идея шифрования состоит в предотвращении просмотра истинного содержания сообщения(текста, файла и т.п.) теми , у кого нет средств его дешифрования. А прочесть файл сможет лишь тот, кто сможет его дешифровать.

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

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

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

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

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

Таблица 

(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 15 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

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

Часто   состоит из одного элемента. Например, в романе Ж. Верна ``Путешествие к центру Земли'' в руки профессора Лиденброка попадает пергамент с рукописью из знаков рунического письма. Каждое множество   состоит из одного элемента. Элемент каждого множества выбирается из набора символов вида 

(2)

 

В рассказе А. Конан Дойла ``Пляшущие человечки'' каждый символ изображает пляшущего человечка в самых различных позах 

(3)

 

На первый взгляд кажется, что чем хитрее символы, тем труднее вскрыть сообщение, не имея ключа. Это, конечно, не так. Если каждому символу однозначно сопоставить какую-либо букву или число, то легко перейти к зашифрованному сообщению из букв или чисел. В романе Ж. Верна ``Путешествие к центру Земли'' каждый рунический знак был заменен на соответствующую букву немецкого языка, что облегчило восстановление открытого сообщения. С точки зрения криптографов использование различных сложных символов не усложняет шифра. Однако, если зашифрованное сообщение состоит из букв или цифр, то вскрывать такое сообщение удобнее.

Рассмотрим некоторые примеры шифров замены. Пусть каждое множество   состоит из одной буквы. Например, 

(4)

 

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

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

Одним из первых шифров, известных из истории, был так называемый шифр Цезаря, для которого вторая строка в (4) является последовательностью, записанной в алфавитном порядке, но начинающейся не с буквы а: 

(5)

 

В одной из задач (задача 4.4) используется шифр Цезаря. Запомнить ключ в этом случае просто - надо знать первую букву второй строки (4) (последовательность букв в алфавите предполагается известной). Однако такой шифр обладает большим недостатком. Число различных ключей равно числу букв в алфавите. Перебрав эти варианты, можно однозначно восстановить открытое сообщение, так как приправильном выборе ключа получится ``осмысленный'' текст. В других случаях обычно получается ``нечитаемый'' текст. Задача 4.4 именно на это и рассчитана. Несмотря на то, что используется фраза на латинском языке, которого школьники не знают, многие участники олимпиады смогли указать открытое сообщение.