Изучение криптографических методов подстановки (замены)

ГОСУДАРСТВЕННОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«БЕЛОРУССКО-РОССИЙСКИЙ УНИВЕРСИТЕТ»

Кафедра «Автоматизированные системы управления»

Реферат на тему:

”Изучение криптографических методов подстановки (замены)”

по дисциплине

“КРИПТОГРАФИЯ И ОХРАНА КОММЕРЧЕСКОЙ ИНФОРМАЦИИ”

Выполнил:

Студент гр. АСОИР-081

Чупилин А.М.

Проверил:

Доцент, кандидат техн. наук

Евсеенко И.А.

Могилев, 2010

Изучение криптографических методов подстановки (замены)

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

(t): Zm Zm; : t (t).

Набор всех подстановок SYM(Zm) называется симметрической группой Zm.

SYM(Zm) обладает следующими свойствами:

Замкнутость: произведение подстановок 12 является подстановкой:

: t1(2(t)).

Ассоциативность: результат произведения 123 не зависит от порядка расстановки скобок: (12)3=1(23)

Существование нейтрального элемента: подстановка i, определяемая как i(t)=t, 0t<m, является нейтральным элементом SYM(Zm) по операции умножения: i=i для SYM(Zm).

Существование обратного: для любой подстановки существует единственная обратная подстановка -1, удовлетворяющая условию -1=-1=i.

Простая замена.

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

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

Таблица 3 - Таблица простой замены

Используя эту таблицу, зашифруем текст: «So ist das Leben. Eilen tut nicht gut. Das Leben ist schoen. Sie ist zu kurz wie Augenblick». Получим следующее зашифрованное сообщение: «Jb ajo lsj Drprt. Radrt oco taxmo ico. Lsj Drprt ajo jxmbrt. Jar ajo kc ecnk har Scirtpdaxe». Однако такой шифр имеет низкую стойкость, так как зашифрованный текст имеет те же статистические характеристики, что и исходный. Дальнейшая расшифровка не составляет труда. Если бы объем зашифрованного текста был намного больше, чем в рассмотренном примере, то частоты появления букв в зашифрованном тексте были бы еще ближе к частотам появления букв в английском или немецком алфавите и расшифровка была бы еще проще. Поэтому простую замену используют редко и лишь в тех случаях, когда шифруемый текст короток.

Шифр Цезаря

Является частным случаем шифра простой замены (одноалфавитной подстановки). При шифровании исходного текста каждая буква заменялась на другую букву того же алфавита путем смещения по алфавиту от исходной буквы на К букв. При достижении конца алфавита выполнялся циклический переход к его началу. Цезарь использовал шифр замены при смещении К = 3. Например, послание Цезаря VENI VIDI VICI (в переводе на русский означает "Пришел, Увидел, Победил"), направленное его другу Аминтию после победы над понтийским царем Фарнаком, сыном Митридата, выглядело бы в зашифрованном виде так:

YHQL YLGL YLFL

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

Рассматривая алфавит криптосистемы как множество целых чисел Zm, мы можем записать функцию шифрования Еk для k=3 в шифре Цезаря как

Еk : x> (x + 3) mod m, x Zm,

где x - числовой код буквы открытого текста;

x+3 - числовой код соответствующей буквы шифртекста;

m - количество символов в алфавите.

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

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

Шифр Цезаря с ключевым словом

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

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

Пример. Правило подстановки для k =3 и ключа «информация»:

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

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

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

Шифр Цезаря многоалфавитный.

В отличие от простого шифра Цезаря, многоалфавитный образуется множеством одноалфавитных подстановок, определяемых функциями шифрования Еk для различных значений ключа k, причем 0<k<m, где m - количество символов алфавита.

В соответствии с этой системой буква xZm открытого текста преобразуется в букву yZm шифртекста согласно следующему правилу:

Еk : y = (x + k) mod m,

где x - числовой код буквы открытого текста; y -числовой код соответствующей буквы шифртекста.

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

Шифры сложной замены

Шифры сложной замены называют многоалфавитными. Многоалфавитная подстановка последовательно и циклически меняет используемые алфавиты. При r-алфавитной подстановке символ х0 исходного сообщения заменяется символом из алфавита В0, символ х1 символом из алфавита B1, и так далее, символ хr-1 заменяется символом из алфавита Br-1, символ хr заменяется символом снова из алфавита В0, и т.д.

Общая схема многоалфавитной подстановки (r=4):

Входной символ х0 х1 х2 х3 х4 х5 х6 х7 х8 х9

Страницы: 1, 2, 3, 4, 5