Основы шифрования информации

Размещено на http://www.allbest.ru/

1. Понятие шифрования

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

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

Сфера интересов криптоанализа - исследование возможности расшифровывания информации без знания ключей.

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

Современная криптография включает в себя четыре основных направления:

1. Симметричные криптосистемы.

2. Криптосистемы с открытым ключом.

3. Системы электронной подписи.

4. Управление ключами.

Криптография дает возможность преобразовать информацию таким образом, что ее прочтение (восстановление) возможно только при знании ключа.

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

Алфавит - конечное множество используемых для кодирования информации знаков.

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

В качестве примеров алфавитов, используемых в современных информационных системах (ИС) можно привести следующие:

* алфавит Z₃₃ - 32 буквы русского алфавита и пробел;

* алфавит Z₄₄ - 43 буквы русского алфавита, знаки препинания и пробела;

* алфавит Z₂₅₆ - символы, входящие в стандартные коды ASCII и КОИ-8;

* бинарный алфавит - Z₂ = {0,1};

* восьмеричный алфавит - Z₈ = {0,1,2,3,4,5,6,7};

* шестнадцатеричный алфавит - Z₁₆ = {0,1,2,3,4,5,6,7,8,9,10,11, 12,13,14, 15};

и т.д.и т.п.

Шифрование - преобразовательный процесс: исходный текст, который носит также название открытого текста, заменяется шифрованным текстом (называемый также криптограммой) (рис.1).

Рис.1. Процесс шифрования данных

Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный (рис.2).

Рис.2. Процесс дешифрования данных

Ключ - информация, необходимая для шифрования и дешифрования текстов.

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

Пространство ключей K - это набор возможных значений ключа.

Обычно ключ представляет собой последовательный ряд букв алфавита.

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

Имеется несколько показателей криптостойкости, среди которых:

* количество всех возможных ключей;

* среднее время, необходимое для криптоанализа.

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

Существуют несколько способов, в соответствии с которыми могут классифицироваться криптографические системы.

Например, существует такая классификация:

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

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

- криптосистемы с секретным ключом;

- криптосистемы с открытым ключом.

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

2. ИЗ ИСТОРИИ КРИПТОГРАФИИ

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

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

Были и другие способы защиты информации, разработанные в античные времена. Напрмер, древнегреческий полководец Эней Тактика в IV веке до н.э. предложил устройство, названное впоследствии "диском Энея". Принцип его таков. На диске диаметром 10-15 см и толщиной 1-2 см высверливались отверстия по числу букв алфавита. В центре диска помещалась "катушка" с намотанной на ней ниткой достаточной длины.

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

Сам термин “шифр” арабского происхождения. В начале XV в. арабы опубликовали энциклопедию “Шауба Аль-Аща”, в которой есть специальный раздел о шифрах. В этой энциклопедии указан способ раскрытия шифра простой замены. Он основан на различной частоте повторяемости букв в тексте. В этом разделе есть перечень букв в порядке их повторяемости на основе изучения текста Корана. Заметим, что в русском тексте чаще всего встречается буква “О”, затем буква “Е” и на третьем месте стоят буквы “И” и “А”. Более точно: на 1000 букв русского текста в среднем приходится 90 букв “О”, 72 буквы “Е” или “Ё”, 60 букв “И” и “А” и т.д.

В Древней Греции идея Энея была использована при создании и других оригинальных шифров замены. Например, в одном из вариантов вместо диска использовалась линейка с числом отверстий, равных количеству букв алфавита. Каждое отверстие обозначалось своей буквой; буквы по отверстиям располагались в произвольном порядке. К линейке была прикреплена катушка с намотанной на нее ниткой. Рядом с катушкой имелась прорезь. При шифровании нить протягивалась через прорезь, а затем через отверстие, соответствующее первой букве шифруемого текста, при этом на нити завязывался узелок в месте прохождения ее через отверстие; затем нить возвращалась в прорезь и аналогично зашифровывалась вторая буква текста и т.д. После окончания шифрования нить извлекалась и передавалась получателю сообщения. Тот, имея идентичную линейку, протягивал нить через прорезь до отверстий, определяемых узлами, и восстанавливал исходный текст по буквам u1086 отверстий. Это устройство получило название "линейка Энея". Шифр, реализуемый линейкой Энея, является одним из примеров шифра замены: буквы заменяются на расстояния между узелками с учетом прохождения через прорезь. Ключом шифра являлся порядок расположения букв по отверстиям в линейке. Противник, завладевший нитью (даже имея линейку, но без нанесенных на ней букв), не сможет прочитать сообщение.

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

В Древней Греции (II в. до н. э.) был также известен шифр, называемый квадрат Полибия. Это устройство представляло собой квадрат 5 х 5, столбцы и строки которого нумеровали цифрами от 1 до 5. В каждую клетку этого квадрата записывалась одна буква. (В греческом варианте одна клетка оставалась пустой, в латинском - в одну клетку помещали две буквы i и j.) В результате каждой букве отвечала пара чисел и шифрованное сообщение превращалось в последовательность пар чисел.

Пример 1. 13 34 22 24 44 34 15 42 22 34 43 45 32

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

("Cogito, ergo sum" - лат, "Я мыслю, следовательно существую"). ?

Интересно отметить, что в несколько измененном виде шифр Полибия дошел до наших дней и получил своеобразное название "тюремный шифр". Для его использования нужно только знать естественный порядок расположения букв алфавита (как в указанном выше примере для английского языка). Стороны квадрата обозначаются не буквами (ABCDE), а числами (12345). Число 3, например, передается путем тройного стука. При передаче буквы сначала "отстукивается число, соответствующее строке, в которой находится буква, а затем номер соответствующего столбца. Например, буква "F" передается двойным стуком (вторая строка) и затем одинарным (первый столбец).

С применением этого шифра связаны некоторые исторические казусы. Так, декабристы, посаженные в тюрьму после неудавшегося восстания, не смогли установить связь с находившимся в "одиночке" князем Одоевским. Оказалось, что этот князь (хорошо образованный по тем временам) не помнил естественный порядок расположения букв в русском и французском алфавитах (другими языками он не владел). Декабристы для русского алфавита использовали прямоугольник размера 5x6 (5 строк и 6 столбцов) и редуцированный до 30 букв алфавит.

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

В 1 в. н.э. Ю. Цезарь во время войны с галлами, переписываясь со своими друзьями в Риме, заменял в сообщении первую букву латинского алфавита (А) на четвертую (D), вторую (В) - на пятую (Е), наконец, последнюю - на третью:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

? 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

? D 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

Пример 2. Донесение Ю. Цезаря Сенату об одержанной им победе над Понтийским царем выглядело так:

YHQL YLGL YLFL("Veni, vidi, vici" - лат. "Пришел, увидел, победил")?

Император Август (1 в. н. э.) в своей переписке заменял первую букву на вторую, вторую - на третью и т. д. Последнюю - на первую:

? 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

? 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 A

Пример 3. Любимое изречение императора Августа выглядело так:

GFTUJOB MFOUF ("Festina lente" - лат. "Торопись медленно") .?

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

В известных рассказах “Пляшущие человечки” Конан Дойля и “Золотой жук” Эдгара По используемые шифры относятся к указанному классу шифров. В другом классе шифров - перестановка - буквы сообщения каким-нибудь способом переставляются между собой. К этому классу принадлежит шифр скитала.

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

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

3. МАРШРУТНАЯ ТРАНСПОЗИЦИЯ

К классу перестановка относится шифр маршрутная транспозиция и его вариант постолбцовая транспозиция. В каждом из них в данный прямоугольник [nЎїm] сообщение вписывается заранее обусловленным способом, а столбцы нумеруются или обычным порядком следования, или в порядке следования букв ключа - буквенного ключевого слова.

Пример 4. Зашифруем фразу “Дела давно минувших дней, преданья старины глубокой”, используя для этого два прямоугольника 6Ўї8. В первом прямоугольнике столбцы нумеруются в обычном порядке следования - слева направо, а во втором - в порядке следования букв слова “Пушкин”. Используя расположение букв этого ключа в алфавите, получим набор чисел :

[4 5 6 2 1 3]:

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

1) двундтго енвеаалй лошйнруа амипьибб дихрянов андесыкг;

2) дихрянов амипьибб андесыкг двундтго енвеаалй лошйнруа. ?

4. ТАБЛИЦА ВИЖЕНЕРА

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

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

Пример 5. Таблица 1, составлена из 31 буквы русского алфавита (без букв Ё и Ъ).

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

м а т е м а т и к а м а т е м а т и к а м а т е м а

к р и п т о г р а ф и я с е р ь е з н а я н а у к а

ц р ь ф я о х ш к ф ф я д к э ь ч п ч а л н т ш ц а

К сообщению можно применять несколько систем шифрования.

5. МОДИФИЦИРОВАННЫЙ ШИФР ЦЕЗАРЯ

Аббат Тритемеус - автор первой печатной книги о тайнописи (1518г.) - предложил несколько шифров и среди них шифр, который можно считать усовершенствованием шифра Цезаря. Этот шифр устроен так. Все буквы алфавита нумеруются по порядку (от 1 до 31 в русском варианте). Затем выбирают какое-нибудь слово, называемое "ключом", и подписывают под сообщением с повторением.

Чтобы получить шифрованный текст, складывают номер очередной буквы с номером соответствующей буквы ключа. Если полученная сумма больше 31, то из нее вычитают 31. В результате получают последовательность чисел от 1 до 31. Вновь заменяя числа этой последовательности соответствующими буквами, получают шифрованный текст. Разбиваем этот текст на группы одной длины, получают шифрованное сообщение.

Пример 6. Выбираем ключевое слово "Пособие". Составляем сообщение "сессия начинается в конце семестра"

Чтобы получить шифрованный текст, складывают номер очередной буквы с номером соответствующей буквы ключа. Если полученная сумма больше 33, то из нее вычитают 33. В результате получают последовательность чисел от 1 до 33. Вновь заменяя числа этой последовательности соответствующими буквами, получают шифрованный текст. Разбивал этот текст на группы одной длины (например, по 5), получают шифрованное сообщение.

Если под ключом шифра понимать однобуквенное слово “В” (в русском варианте), то мы получим шифр Цезаря

Пример 7. Для сообщения из примера 6, получим:

ф и ф ф л в р г ь л р г и х ф в в н т р щ и ф и п и ф х у г ?

защита информация шифрование криптография

6. ОДНОРАЗОВЫЙ БЛОКНОТ

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

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

Занумеровав все символы расширенного алфавита Z₄₄ числами от 0 до 43, можно рассматривать любой передаваемый текст, как последовательность {a_n} чисел множества А={0,1,2,…,43}. Имея случайную последовательность {c_n} из чисел множества А той же длины что и передаваемый текст (ключ), складываем по модулю 44 число a_n передаваемого текста с соответствующим числом c_n ключа a_n+c_nЎХb_n(mod 44), 0ЎВ b_n ЎВ 43 получим последовательность {b_n} знаков шифрованного текста.

Чтобы получить передаваемый текст, можно воспользоваться тем же ключом:

a_nЎХb_n-c_n(mod 44), 0ЎВ a_n ЎВ 43.

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

6. СИММЕТРИЧЕСКИЕ КРИПТОСИСТЕМЫ

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

Обмен информацией осуществляется в 3 этапа:

1. отправитель передает получателю ключ (в случае сети с несколькими абонентами у каждой пары абонентов должен быть свой ключ, отличный от ключей других пар);

2. отправитель, используя ключ, зашифровывает сообщение, которое пересылается получателю;

3. получатель получает сообщение и расшифровывает его.

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

Криптографические алгоритмы обычно строятся с использованием простых и быстро выполняемых операторов нескольких типов. Множество обратимых операторов, преобразующих текст длиной n бит в текст длиной n бит, являются элементами группы обратимых операторов по умножению (например, подстановок n-разрядных слов). Пусть f, g, h -- обратимые операторы, то есть существуют f-1, g-1 и h-1. Поэтому hgf - последовательное выполнение операторов fgh - тоже обратимый оператор (операторы выполняются справа налево) с обратным оператором к этому произведению, h-1g-1 f-1. Поэтому дешифратор выполняет те же операции, что и шифратор, но в обратном порядке, и каждый оператор расшифрования является обратным к соответствующему оператору шифрования. Некоторые операторы являются взаимно обратными, то есть выполнение подряд два раза некоторой операции над текстом дает исходный текст.

7. Моно- и многоалфавитные подстановки

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

Определение. Подстановкой на алфавите Z_n называется отображение, при котором буквы исходного текста t замещены буквами шифрованного текста (t):

Z_n Z_n; : tt(t).

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

Определение. Подмножество C_n={C_k: 0ЎВk<n}, содержащее n подстановок C_k: jЎж(j+k) (mod n), 0ЎВk < n, называется подстановкой Цезаря.

Два целых числа n и n' называются сравнимыми по модулю m, если при делении на m они дают одинаковые остатки. Пишут nЎХn'(m) или nЎХn'(mod m), а число m называют модулем сравнения.

Таким образом, получается разбиение Z на классы чисел, сравнимых между собой по mod m и называемых классами вычетов по mod m.

Каждый класс вычетов имеет вид: {r}m=r+mZ={r+mk | kZ},

Семейство подстановок Цезаря названо по имени римского императора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлять послания с использованием 50-буквенного алфавита и подстановки C₃.

Подстановка определяется по таблице замещения, содержащей пары соответствующих букв “исходный текст - шифрованный текст”.

Для C₃ подстановки приведены в Табл. 2. Т.к 1=4 (mod 3), 2=5 (mod 3) …Стрелка () означает, что буква исходного текста (слева) шифруется при помощи C₃ в букву шифрованного текста (справа).

Определение. Системой Цезаря называется моноалфавитная подстановка, преобразующая исходный текст (x₀,x₁,..,x_n-1) в шифрованный текст (y₀,y₁,...,y_n-1) в соответствии с правилом: y_i=C_k(x_i), 0ЎВi<n.

Пример 59. Сообщение ИЗУЧАЙТЕ_КРИПТОГРАФИЮ посредством подстановки C₃ преобразуется в лкцъгмхивнултсжугчла. ?

При своей несложности система легко уязвима. Если злоумышленник имеет:

1) шифрованный и соответствующий исходный текст или

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

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

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

Пусть {K_i: 0ЎВi<n} - независимые случайные переменные с одинаковым распределением вероятностей, принимающие значения на множестве Z_m:

P{(K₀, K₁, ..., K_n-1)=(k₀, k₁, ..., k_n-1)}=(1/m)ⁿ

Система одноразового использования преобразует исходный текст: X=(x₀, x₁, ..., x_n-1) в шифрованный текст: Y=(y₀, y₁, ..., y_n-1)

при помощи подстановки Цезаря: y_i=C_Ki(x_i)=(K_i+x_i) (mod m) i=0,1,…n-1.

Для такой системы подстановки используют также термин “одноразовая лента” и “одноразовый блокнот”. Пространство ключей К системы одноразовой подстановки является вектором ранга (K₀, K₁,...,K_n-1) и содержит mn точек.

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

8. Системы шифрования Вижинера

Ослабим требование шифровать каждую букву исходного текста отдельным значением ключа. Начнем с конечной последовательности ключа: k = (k₀,k₁,...,k_n), которая называется ключом пользователя, и продлим ее до бесконечной последовательности, повторяя цепочку. Таким образом, получим рабочий ключ k = (k₀,k₁,...,k_n), k_j = k(j mod r, 0 ЎВ j < ЎД . Например, при r = ЎД и ключе пользователя 17 23 11 56 43 97 25 рабочий ключ будет периодической последовательностью:

17 23 11 56 43 97 25 17 23 11 56 43 97 25 17 23 11 56 43 97 25...

Определение. Подстановка Вижинера VIGk определяется так:

VIGk: (x₀,x₁, ..., x_n-1) Ўж (y₀, y₁, ..., y_n-1) = (x₀+k, x₁+k,. .., x_n-1+k).

Пример 61. Преобразование текста с помощью подстановки Вижинера при r=5.

Исходный текст - РАБОТАЙТЕ АККУРАТНО

Ключ: ПЕСНЯ

Разобьем исходный текст на блоки по 5 символов: РАБОТ АЙТЕ АККУР АТНО

и наложим на них ключ (используя таблицу Вижинера):

Р+П=Я, А+Е=Е и т.д. Получаем зашифрованный текст: ЯЕТЫР ППВТЮ ППЫ_О ПЧЮЫЯ ?

Можно выдвинуть и обобщенную систему Вижинера. Ее можно сформулировать не только при помощи подстановки Цезаря.

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

9. Перестановки

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

Введем обозначение Ґт для взаимно-однозначного отображения набора S={s₀,s₁, ...,s_n-1}, состоящего из n элементов, на себя, т.е. Ґт: S Ўж S,

Ґт:s_i Ўж s_Ґт(i), 0 ЎВ i < n. Будем говорить, что в этом смысле Ґт является перестановкой элементов S. И, наоборот, автоморфизм S соответствует перестановке целых чисел (0,1,2,.., n-1).

Криптографическим преобразованием T для алфавита Zm называется последовательность автоморфизмов: T={T(n):1ЎВn<ЎД} T(n): ZmЎжZm, 1ЎВn<ЎД. Каждое T(n) является, таким образом, перестановкой n-грамм из Zm. Поскольку T(i) и T(j) могут быть определены независимо при iЎБj, число криптографических преобразований исходного текста размерности n равно (mn)!2. Оно возрастает непропорционально при увеличении m и n: так, при m=33 и n=2 число различных криптографических преобразований равно 1089!. Отсюда следует, что потенциально существует большое число отображений исходного текста в шифрованный. Практическая реализация криптографических систем требует, чтобы преобразования {Tk: kK}, где K - множество ключей, были определены алгоритмами, зависящими от относительно небольшого числа параметров (ключей).

Размещено на Allbest.ru