Реферат: Баричев С. Криптография без секретов
<span Times New Roman",«serif»; color:blue">От автора<span Times New Roman",«serif»">Эта книга — краткое введение в криптографию. С одной стороны, здесьизложен материал, который отвечает на многие вопросы, которые возникают у техкто делает на ниве этой науке первые шаг, с другой стороны здесь есть тот минимуминформации, который достаточен для того чтобы самостоятельно оценивать любыереальные криптосистемы или даже создавать свои собственные.
Язык книги делался по возможности доступным, но не освобождает Читателяот необходимости владения элементарными основами математики, в частностиалгебры и теории групп и полей.
Многие вопросы к сожалению остались за обложками этой книги. В частностипосле долгих сомнений Автор решил отказаться от рассмотрения DES, ввиду его крайней непрактичности инеуживчивости на российской почве<span Times New Roman",«serif»;mso-fareast-font-family:«Times New Roman»; mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">[1]
.Массу полезной информации можно найти на сервере<span Courier New";mso-bidi-font-family:«Times New Roman»">
<span Courier New";mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">ftp.rsa.com. В faq5.docВы если и не найдете ответ на любой вопрос по криптографии, то обнаружитебольшое количество ссылок на другие источники.Автор будет признателен за любые замечания и вопросы, которые прощевсего направить по адресу: bar@glasnet.ru
Баричев Сергей
<span Times New Roman",«serif»;mso-fareast-font-family:«Times New Roman»;mso-ansi-language: EN-US;mso-fareast-language:RU;mso-bidi-language:AR-SA"><span Times New Roman",«serif»; color:blue">Введение<span Times New Roman",«serif»">
Проблема защиты информации путем ее преобразования,исключающего ее прочтение посторонним лицом волновала человеческийум с давних времен. История криптографии — ровесница истории человеческогоязыка. Более того, первоначально письменность сама по себе былакриптографической системой, так как в древних обществах ею владели толькоизбранные. Священные книги Древнего Египта, Древней Индии тому примеры.
С широким распространением письменности криптография стала формироватьсякак самостоятельная наука. Первые криптосистемы встречаются уже в начале нашейэры. Так, Цезарь в своей переписке использовал уже более менее систематическийшифр, получивший его имя.
Бурное развитие криптографические системы получили в годыпервой и второй мировых войн. Начиная с послевоенного времени и по нынешнийдень появление вычислительных средств ускорило разработку исовершенствование криптографическихметодов.
Почему проблема использования криптографических методовв информационных системах (ИС) стала в настоящий момент особо актуальна?
С одной стороны, расширилось использование компьютерныхсетей, в частности глобальной сети Интернет, по которым передаются большиеобъемы информации государственного, военного, коммерческого ичастного характера, не допускающего возможность доступа к ней постороннихлиц.
С другой стороны, появление новых мощных компьютеров, технологий сетевых и нейронных вычисленийсделало возможным дискредитацию криптографических систем еще недавносчитавшихся практически нераскрываемыми.
Проблемой защиты информации путем ее преобразования занимаетсякриптология (kryptos — тайный, logos — наука).Криптология разделяется на два направления — криптографию и криптоанализ.Цели этих направлений прямо противоположны.
Криптография занимаетсяпоиском и исследованием математических методов преобразованияинформации.
Сфера интересов криптоанализа- исследование возможности расшифровыванияинформации без знания ключей.
В этой книге основное внимание будет уделено криптографическимметодам.
Современная криптография включает в себя четыре крупных раздела:
1.
2.
3.
4.
Основные направления использования криптографических методов — передача конфиденциальнойинформации по каналам связи (например, электронная почта), установлениеподлинности передаваемых сообщений, хранение информации (документов,баз данных) на носителях в зашифрованном виде.
ТерминологияИтак,криптография дает возможность преобразовать информацию таким образом, что еепрочтение (восстановление) возможно только при знании ключа.
В качествеинформации, подлежащей шифрованию и дешифрованию, будут рассматриваться тексты, построенные на некотором алфавите. Под этими терминами понимаетсяследующее.
Алфавит — конечное множествоиспользуемых для кодирования информации знаков.
Текст — упорядоченный набор из элементовалфавита.
В качествепримеров алфавитов, используемых в современных ИС можно привести следующие:
*<span Times New Roman"">
алфавит Z33 — 32 буквы русского алфавита и пробел;*<span Times New Roman"">
алфавит Z256 — символы, входящие в стандартные коды ASCII и КОИ-8;*<span Times New Roman"">
бинарный алфавит- Z2 = {0,1};*<span Times New Roman"">
восьмеричныйалфавит или шестнадцатеричный алфавит;Шифрование — преобразовательныйпроцесс: исходный текст, которыйносит также название открытого текста,заменяется шифрованным текстом.
исходный
текст
шифрованный
текст
Криптографическая система
КЛЮЧ
<img src="/cache/referats/16705/image001.gif" v:shapes="_x0000_s1026 _x0000_s1027 _x0000_s1028 _x0000_s1029 _x0000_s1030 _x0000_s1031 _x0000_s1036 _x0000_s1038 _x0000_s1044 _x0000_s1049 _x0000_s1050 _x0000_s1051">Дешифрование — обратный шифрованиюпроцесс. На основе ключа шифрованный текст преобразуется в исходный.
шифрованный
текст
исходный
текст
Криптографическая система
КЛЮЧ
<img src="/cache/referats/16705/image002.gif" v:shapes="_x0000_s1117 _x0000_s1118 _x0000_s1119 _x0000_s1120 _x0000_s1121 _x0000_s1122 _x0000_s1123 _x0000_s1124 _x0000_s1125 _x0000_s1126 _x0000_s1127 _x0000_s1128 _x0000_s1129">Ключ — информация, необходимаядля беспрепятственного шифрования и дешифрования текстов.
Криптографическая система представляетсобой семейство T преобразованийоткрытого текста. Члены этого семейства индексируются, или обозначаютсясимволом k; параметр k является ключом. Пространство ключей K — это набор возможных значений ключа. Обычно ключ представляетсобой последовательный ряд букв алфавита.
Криптосистемыразделяются на симметричные и с открытым ключом.
В симметричных криптосистемах и дляшифрования, и для дешифрования используется одини тот же ключ.
В системах с открытым ключом используютсядва ключа — открытый и закрытый, которые математически связаныдруг с другом. Информация шифруется с помощью открытого ключа, которыйдоступен всем желающим, арасшифровывается с помощью закрытого ключа, известного только получателю сообщения.
Термины распределение ключей и управление ключами относятся кпроцессам системы обработки информации, содержанием которых являетсясоставление и распределение ключей между пользователями.
Электронной (цифровой) подписьюназывается присоединяемое к тексту его криптографическое преобразование,которое позволяет при получении текста другим пользователем проверить авторствои подлинность сообщения.
Криптостойкостью называетсяхарактеристика шифра, определяющая его стойкость к дешифрованиюбез знания ключа (т.е. криптоанализу). Имеется несколько показателейкриптостойкости, среди которых:
·<span Times New Roman"">
·<span Times New Roman"">
ПреобразованиеTk определяется соответствующималгоритмом и значением параметра k.Эффективность шифрования с целью защиты информации зависит от сохранениятайны ключа и криптостойкости шифра.
Требования к криптосистемамПроцесс криптографического закрытия данных может осуществлятьсякак программно, так и аппаратно. Аппаратная реализация отличаетсясущественно большей стоимостью, однако ей присущи и преимущества:высокая производительность, простота, защищенность и т.д. Программнаяреализация более практична, допускает известную гибкость в использовании.
Для современных криптографических систем защиты информациисформулированы следующие общепринятые требования:
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
<span Times New Roman",«serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA"><span Times New Roman",«serif»; color:blue">Симметричные криптосистемы<span Times New Roman",«serif»">
Все многообразие существующих криптографических методовможно свести к следующим классам преобразований:
Симметричные
криптосистемы
<span Times New Roman",«serif»">Гаммирование
<span Times New Roman",«serif»">Подстановки
<span Times New Roman",«serif»">Блочные шифры
<span Times New Roman",«serif»">Перестановки
<img src="/cache/referats/16705/image003.gif" v:shapes="_x0000_s1061 _x0000_s1081 _x0000_s1082 _x0000_s1083 _x0000_s1084"><span Times New Roman",«serif»">Моно- и многоалфавитные подстановки.
Наиболее простой вид преобразований, заключающийся в заменесимволов исходного текста на другие (того же алфавита) по более или менеесложному правилу. Для обеспечения высокой криптостойкости требуетсяиспользование больших ключей.
<span Times New Roman",«serif»">Перестановки.
Также несложный метод криптографического преобразования.Используется как правило в сочетании с другими методами.
<span Times New Roman",«serif»">Гаммирование.
Этот метод заключается в наложении на исходный текст некоторойпсевдослучайной последовательности, генерируемой на основе ключа.
<span Times New Roman",«serif»">Блочные шифры.
Представляют собой последовательность (с возможным повторениеми чередованием) основных методов преобразования, применяемую кблоку (части) шифруемого текста. Блочные шифры на практике встречаютсячаще, чем “чистые” преобразования того или иного класса в силу их болеевысокой криптостойкости. Российский и американский стандарты шифрованияоснованы именно на этом классе шифров.
<span Times New Roman",«serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">Перестановки
Перестановкой <span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">s
набора целых чисел (0,1,...,N-1) называется его переупорядочение. Для тогочтобы показать, что целое i перемещеноиз позиции i в позицию <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">s(i), где 0 <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">£(i) < n, будем использовать запись<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">s
<span Times New Roman",«serif»;mso-ansi-language:EN-US">=<span Times New Roman",«serif»">(<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">s<span Times New Roman",«serif»">(0), <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">s<span Times New Roman",«serif»">(1),..., <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">s<span Times New Roman",«serif»">(N-1)).Число перестановок из (0,1,...,N-1) равно n!=1*2*...*(N-1)*N. Введем обозначение <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">s
для взаимно-однозначного отображения (гомоморфизма) набора S={s0,s1,...,sN-1}, состоящего из n элементов, на себя.<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">s
<span Times New Roman",«serif»">: S <span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">®<span Times New Roman",«serif»"> S<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">s
<span Times New Roman",«serif»">:si <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">®<span Times New Roman",«serif»"> s<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">s<span Times New Roman",«serif»">(i)<span Times New Roman",«serif»">, 0 <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">£<span Times New Roman",«serif»"> i < nБудем говорить, что вэтомсмысле <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">s
является перестановкой элементов S.И, наоборот, автоморфизм S соответствует перестановке целых чисел (0,1,2,.., n-1).Криптографическим преобразованиемT для алфавита Zmназывается последовательность автоморфизмов: T={T(n):1<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">£
n<<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">¥}<span Times New Roman",«serif»; mso-ansi-language:EN-US">T(n): Zm,n
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-ansi-language:EN-US;mso-char-type: symbol;mso-symbol-font-family:Symbol">®<span Times New Roman",«serif»;mso-ansi-language:EN-US">Zm,n,1<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-ansi-language:EN-US;mso-char-type: symbol;mso-symbol-font-family:Symbol">£<span Times New Roman",«serif»;mso-ansi-language:EN-US">n<<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-ansi-language:EN-US;mso-char-type: symbol;mso-symbol-font-family:Symbol">¥<span Times New Roman",«serif»">Каждое T(n)является, таким образом,перестановкой n-грамм из Zm,n.
Поскольку T(i)и T(j) могутбыть определены независимо при i<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">¹
j,число криптографических преобразований исходного текста размерности n равно (mn)!<span Times New Roman",«serif»;mso-fareast-font-family:«Times New Roman»; mso-ansi-language:EN-US;mso-fareast-language:RU;mso-bidi-language:AR-SA">[2].Оно возрастает непропорционально при увеличении m и n: так, при m=33и n=2 число различныхкриптографических преобразований равно 1089!.. Отсюда следует, что потенциальносуществует большое число отображений исходного текста в шифрованный.Практическая реализация криптографических систем требует, чтобы преобразования {Tk:k<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">Î
K} были определены алгоритмами,зависящими от относительно небольшого числа параметров (ключей). Системы подстановокОпределениеПодстановкой <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">p
на алфавите Zmназывается автоморфизм Zm, при котором буквы исходного текста tзамещены буквами шифрованного текста <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">p(t):<span Times New Roman",«serif»; mso-no-proof:yes">Zm
<span Times New Roman",«serif»"><span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Wingdings;mso-no-proof:yes">à<span Times New Roman",«serif»; mso-no-proof:yes"> Zm<span Times New Roman",«serif»">;<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol;mso-no-proof:yes">p<span Times New Roman",«serif»; mso-no-proof:yes">: <span Times New Roman",«serif»; mso-ansi-language:EN-US">t <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Wingdings;mso-no-proof:yes">à<span Times New Roman",«serif»;mso-ansi-language:EN-US"> <span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol; mso-no-proof:yes">p<span Times New Roman",«serif»; mso-no-proof:yes">(t)<span Times New Roman",«serif»">.Набор всех подстановокназывается симметрической группой Zmè будет вдальнейшем обозначаться какSYM(Zm).
УтверждениеSYM(Zm) c операцией произведения является группой, т.е.операцией, обладающей следующими свойствами:
<span Times New Roman"">
Замкнутость:произведение подстановок <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">p1<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">p2 является подстановкой:<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol;mso-no-proof:yes">p
: t<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol; mso-no-proof:yes">p1(<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol;mso-no-proof:yes">p2(t)).<span Times New Roman"">
Ассоциативность:результат произведения <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">p1<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">p2<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">p3 не зависит от порядка расстановки скобок:(<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol;mso-no-proof:yes">p
1<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol;mso-no-proof:yes">p2)<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol; mso-no-proof:yes">p3=<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol;mso-no-proof:yes">p1(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol; mso-no-proof:yes">p2<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol;mso-no-proof:yes">p3)<span Times New Roman"">
Существованиенейтрального элемента: постановка i, определяемая как i(t)=t, 0<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family: Symbol">£t<m, является нейтральнымэлементом SYM(Zm)по операции умножения: i<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">p=<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">pi для <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">"<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">p<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">ÎSYM(Zm).<span Times New Roman"">
Существованиеобратного: для любой подстановки <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">p существует единственная обратнаяподстановка <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">p-1,удовлетворяющая условию<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol; mso-no-proof:yes">pp
‑1=<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol; mso-no-proof:yes">p‑1<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol;mso-no-proof:yes">p=i.Число возможных подстановок в симметрической группе Zmназывается порядком SYM(Zm)и равно m! .
Определение.Ключом подстановки k для Zmназывается последовательность элементов симметрической группы Zm:
<span Times New Roman",«serif»;mso-no-proof:yes">k
<span Times New Roman",«serif»;mso-no-proof:yes">=(p0,p1,...,pn<span Times New Roman",«serif»">-1<span Times New Roman",«serif»;mso-no-proof:yes">,...), pn<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol; mso-no-proof:yes">Î<span Times New Roman",«serif»; mso-no-proof:yes">SYM(Zm), 0<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol;mso-no-proof:yes">£<span Times New Roman",«serif»;mso-no-proof:yes">n<<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol; mso-no-proof:yes">¥<span Times New Roman",«serif»; mso-no-proof:yes">Подстановка, определяемая ключом k, является криптографическим преобразованием Tk, при помощи которогоосуществляется преобразование n-граммыисходного текста (x0,x1 ,..,xn-1) в n-грамму шифрованного текста (y0,y1 ,...,yn-1):
<span Times New Roman",«serif»; mso-no-proof:yes">yi=p(xi),
<span Times New Roman",«serif»"> 0<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol; mso-no-proof:yes">£<span Times New Roman",«serif»; mso-no-proof:yes">i<nгде n – произвольное(n=1,2,..). Tk называетсямоноалфавитной подстановкой, если pнеизменно при любом i, i=0,1,..., в противном случае Tkназывается многоалфавитной подстановкой.
Примечание. К наиболеесущественным особенностям подстановки Tkотносятся следующие:
1. Исходный текст шифруетсяпосимвольно. Шифрования n-граммы(x0,x1 ,..,xn-1) и ее префикса (x0,x1 ,..,xs-1)связаны соотношениями
<span Times New Roman",«serif»">Tk(x0,x1,..,xn-1)=(y0,y1 ,...,yn-1)
<span Times New Roman",«serif»">Tk(x0,x1,..,xs-1)=(y0,y1 ,...,ys-1)
2. Буква шифрованного текстаyi является функцией только i-й компоненты ключа pi и i-й буквы исходного текста xi.
<span Times New Roman",«serif»">Подстановка ЦезаряПодстановка Цезаря является самым простым вариантом подстановки.Она относится к группе моноалфавитныхподстановок.
Определение.Подмножество Cm={Ck:0<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">£
k<m} симметрической группы SYM(Zm),содержащее m подстановок<span Times New Roman",«serif»; mso-no-proof:yes">Ck: j
<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol; mso-no-proof:yes">®<span Times New Roman",«serif»; mso-no-proof:yes">(j+k) (mod m), 0<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol;mso-no-proof:yes">£<span Times New Roman",«serif»; mso-no-proof:yes">k<span Times New Roman",«serif»; mso-no-proof:yes"> < m,называется подстановкой Цезаря.
Умножение коммутативно, CkCj=CjCk=Cj+k, C0– идентичнаяподстановка, а обратной к Cк является Ck-1=Cm-k, где 0<k<m. Семейство подстановок Цезаря названо по имени римскогоимператора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлятьпослания с использованием 50-буквенного алфавита и подстановки C3.
Подстановка определяется по таблице замещения, содержащей пары соответствующихбукв “исходный текст – шифрованный текст”. Для C3 подстановкиприведены в Табл. 1. Стрелка (<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings">à
) означает, что буква исходного текста (слева)шифруется при помощи C3 в букву шифрованного текста (справа).Определение. СистемойЦезаря называется моноалфавитная подстановка, преобразующая n-грамму исходного текста (x0, x1 ,..,xn-1) в n‑грамму шифрованного текста (y0,y1 ,...,yn-1) в соответствии с правилом
<span Times New Roman",«serif»; mso-no-proof:yes">y
<span Times New Roman",«serif»; mso-ansi-language:EN-US">i<span Times New Roman",«serif»; mso-no-proof:yes">=Ck(xi),0<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol;mso-no-proof:yes">£<span Times New Roman",«serif»; mso-no-proof:yes">i<n.Например, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посредством подстановки C3преобразуется в еюыолхиврсеюивцнгкгрлб.
Таблица 1.
А<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
гЙ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
мТ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
хЫ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
юБ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
дК<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
нУ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
цЬ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
яВ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
еЛ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
оФ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
чЭ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
_Г<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
жМ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
пХ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
шЮ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
аД<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
зН<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
рЦ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
щЯ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
бЕ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
иО<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
сЧ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
ъ_<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
вЖ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
йП<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
тШ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
ыЗ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
кР<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
уЩ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
ьИ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
лС<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
фЪ<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Wingdings;mso-no-proof:yes">à
эПри своей несложности система легко уязвима. Если злоумышленник имеет
1) шифрованный и соответствующий исходный текст или
2) шифрованный текст выбранного злоумышленником исходного текста,
то определение ключа и дешифрование исходного текста тривиальны.
<span Times New Roman",«serif»">Болееэффективны обобщения подстановки Цезаря — шифрХилла и шифр Плэйфера. Ониоснованы на подстановке не отдельных символов, а 2-грамм (шифр Плэйфера) или n-грамм<span Times New Roman",«serif»;mso-fareast-font-family:«Times New Roman»; mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">[3]
(шифр Хилла). При более высокой криптостойкости они значительно сложнее дляреализации и требуют достаточно большого количества ключевой информации.<span Times New Roman",«serif»">Многоалфавитныесистемы. Системы одноразового использования.<span Times New Roman",«serif»">Слабая криптостойкость моноалфавитных подстановок преодолевается сприменением подстановок многоалфавитных.
Многоалфавитная подстановкаопределяется ключом <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">p
=(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">p1,<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">p2,...), содержащим не менее двух различных подстановок. В начале рассмотрим многоалфавитныесистемы подстановок с нулевым начальным смещением.
Пусть {Ki: 0<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">£
i<n}- независимые случайные переменные с одинаковым распределением вероятностей,принимающие значения на множестве ZmPкл{(K0, K1,..., Kn-1)=(k0, k1, ..., kn-1)}=(1/m)n
Система одноразовогоиспользования преобразует исходный текст
<span Times New Roman",«serif»">X=(X0, x1, ..., xn-1)
в шифрованный текст
<span Times New Roman",«serif»">Y=(Y0, y1, ..., yn-1)
при помощи подстановки Цезаря
<span Times New Roman",«serif»">Yi=CKi(xi)=(Ki+Xi) (mod m) i=0...n-1 (1)
Для такой системы подстановки используют также термин “одноразоваялента” и “одноразовый блокнот”. Пространство ключей К системы одноразовойподстановки является вектором рангов (K0,K1, ..., Kn-1) и содержит mn точек.
Рассмотрим небольшой примершифрования с бесконечным ключом. В качестве ключа примем текст
<span Times New Roman",«serif»"> “БЕСКОНЕЧНЫЙ_КЛЮЧ....”.
Зашифруем с его помощью текст“ШИФР_НЕРАСКРЫВАЕМ”. Шифрование оформим в таблицу:
ШИФРУЕМЫЙ_ТЕКСТ
24
8
20
16
19
5
12
27
9
32
18
5
10
17
18
БЕСКОНЕЧНЫЙ_КЛЮЧ
1
5
17
10
14
13
5
23
13
27
9
32
10
11
30
ЩРДЪАТТССЦЪЫДФЬП
=SUM(ABOVE) 25
=SUM(ABOVE) 13
=SUM(ABOVE)-33 4
=SUM(ABOVE) 26
=SUM(ABOVE)-33 0
=SUM(ABOVE) 18
=SUM(ABOVE) 17
=SUM(ABOVE)-33 17
=SUM(ABOVE) 22
=SUM(ABOVE)-33 26
=SUM(ABOVE) 27
=SUM(ABOVE)-33 4
=SUM(ABOVE) 20
=SUM(ABOVE) 28
=SUM(ABOVE)-33 15
Исходный текст невозможно восстановить безключа.
Наложение белого шума в виде бесконечного ключа на исходный текстменяет статистические характеристики языка источника. Системы одноразовогоиспользования теоретически не расшифруемы<span Times New Roman",«serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">[4]
,так как не содержат достаточной информации для восстановления текста.Почему же э