ГОСУДАРСТВЕННОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«БЕЛОРУССКО-РОССИЙСКИЙ УНИВЕРСИТЕТ»
Кафедра «Автоматизированные системы управления»
Реферат на тему:
”Изучение криптографических методов подстановки (замены)”
по дисциплине
“КРИПТОГРАФИЯ И ОХРАНА КОММЕРЧЕСКОЙ ИНФОРМАЦИИ”
Выполнил:
Студент гр. АСОИР-081
Чупилин А.М.
Проверил:
Доцент, кандидат техн. наук
Евсеенко И.А.
Могилев, 2010
Изучение криптографических методов подстановки (замены)
Определение. Подстановкой p на алфавите Zm называется автоморфизм Zm, при котором буквы исходного текста t замещены буквами шифрованного текста
p(t): Zm-Zm; p: t-p(t).
Набор всех подстановок SYM(Zm) называется симметрической группой Zm.
SYM(Zm) обладает следующими свойствами:
Замкнутость: произведение подстановок p1p2 является подстановкой:
p: t-p1(p2(t)).
Ассоциативность: результат произведения p1p2p3 не зависит от порядка расстановки скобок: (p1p2)p3=p1(p2p3)
Существование нейтрального элемента: подстановка i, определяемая как i(t)=t, 0£t<m, является нейтральным элементом SYM(Zm) по операции умножения: ip=pi для "pÎSYM(Zm).
Существование обратного: для любой подстановки p существует единственная обратная подстановка p-1, удовлетворяющая условию pp-1=p-1p=i.
Простая замена.
В наиболее простом методе подстановки (замены) символы шифруемого текста заменяются другими символами, взятыми из одного- (одно- или моноалфавитная подстановка) или нескольких (много- или полиалфавитная подстановка) алфавитов.
Самой простой разновидностью является прямая (простая) замена, когда буквы шифруемого сообщения заменяются другими буквами того же самого или некоторого другого алфавита. Таблица замены может иметь следующий вид (таблица 3):
Таблица 3 - Таблица простой замены
| Исходные символы шифруемого текста | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | р | q | r | s | t | u | v | w | x | y | z |
| Заменяющие символы | s | р | x | l | r | z | i | m | a | y | e | d | w | t | b | g | v | n | j | o | c | f | h | q | u | k |
Используя эту таблицу, зашифруем текст: «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 – количество символов алфавита.
В соответствии с этой системой буква xÎZm открытого текста преобразуется в букву yÎZm шифртекста согласно следующему правилу:
Е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
Алфавит подстановки B0B1B2B3B0B1B2B3B0B1
Эффект использования многоалфавитной подстановки заключается в том, что обеспечивается маскировка естественной статистики исходного языка, так как конкретный символ из исходного алфавита Х может быть преобразован в несколько различных символов шифровальных алфавитов В.
Степень обеспечиваемой защиты теоретически пропорциональна длине периода r в последовательности используемых алфавитов В.
В случае блочного шифра эта подстановка шифрует n-грамму (блок) открытого текста (х0, х1, х2, … , хn-1) в n-грамму (y0, y1, y2, … , yn-1) шифртекста в соответствии с формулой:
yi = πi (хi), 0 < i < n, n = 1, 2, 3, ... .
При n®∞ мы приближаемся к теоретически стойкой одноразовой системе шифрования.
Данный шифр может быть использован и для потокового шифрования, где открытый текст шифруется побуквенно (буква за буквой).
При этом i-ая буква шифртекста является функцией только i-ой компоненты πi ключа К и i-ой буквы хi; открытого текста.
Схема шифрования Вижинера
Схема шифрования Вижинера впервые была опубликована в 1586 г. и является одной из старейших и наиболее известных многоалфавитных систем. Свое название она получила по имени французского дипломата XVI века Блеза Вижинера. Этот шифр многоалфавитной замены можно описать таблицей шифрования, называемой таблицей (квадратом) Вижинера. Размер таблицы Вижинера равен длине алфавита. Таблица Вижинера представляет собой квадратную матрицу с n2 элементами, где n - число символов используемого алфавита. В таблице 4 показана верхняя часть таблицы Вижинера для кириллицы.
Таблица 4 - Таблица Вижинера