Дипломная работа: Криптография
Определение. Системой Цезаря называется моноалфавитная подстановка, преобразующая n-грамму исходного текста (x0, x1 ,..,xn-1) в n‑грамму шифрованного текста (y0 ,y1 ,...,yn-1) в соответствии с правилом
yi=Ck(xi), 0£i<n.
Например, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посредством подстановки C3 преобразуется в еюыолхиврсеюивцнгкгрлб.
Таблица 1.
| Аàг | Йàм | Тàх | Ыàю |
| Бàд | Кàн | Уàц | Ьàя |
| Вàе | Лàо | Фàч | Эà_ |
| Гàж | Мàп | Хàш | Юàа |
| Дàз | Нàр | Цàщ | Яàб |
| Еàи | Оàс | Чàъ | _àв |
| Жàй | Пàт | Шàы | |
| Зàк | Рàу | Щàь | |
| Иàл | Сàф | Ъàэ |
При своей несложности система легко уязвима. Если злоумышленник имеет
1) шифрованный и соответствующий исходный текст или
2) шифрованный текст выбранного злоумышленником исходного текста,
то определение ключа и дешифрование исходного текста тривиальны.
Более эффективны обобщения подстановки Цезаря - шифр Хилла и шифр Плэйфера. Они основаны на подстановке не отдельных символов, а 2-грамм (шифр Плэйфера) или n-грамм[3] (шифр Хилла). При более высокой криптостойкости они значительно сложнее для реализации и требуют достаточно большого количества ключевой информации.
Многоалфавитные системы. Системы одноразового использования.
Слабая криптостойкость моноалфавитных подстановок преодолевается с применением подстановок многоалфавитных.
Многоалфавитная подстановка определяется ключом p=(p1,
p2, ...),
содержащим не менее двух различных подстановок. В начале рассмотрим многоалфавитные
системы подстановок с нулевым начальным смещением.
Пусть {Ki: 0£i<n} - независимые случайные переменные с одинаковым распределением вероятностей, принимающие значения на множестве Zm
Pкл{(K0, K1, ..., Kn-1)=(k0, k1, ..., kn-1)}=(1/m)n
Система одноразового использования преобразует исходный текст
X=(X0, x1, ..., xn-1)
в шифрованный текст
Y=(Y0, y1, ..., yn-1)
при помощи подстановки Цезаря
Yi=CKi(xi)=(Ki+Xi) (mod m) i=0...n-1 (1)
Для такой системы подстановки используют также термин “одноразовая лента” и “одноразовый блокнот”. Пространство ключей К системы одноразовой подстановки является вектором рангов (K0, K1, ..., Kn-1) и содержит mn точек.
Рассмотрим небольшой пример шифрования с бесконечным ключом. В качестве ключа примем текст
“БЕСКОНЕЧНЫЙ_КЛЮЧ....”.
Зашифруем с его помощью текст “ШИФР_НЕРАСКРЫВАЕМ”. Шифрование оформим в таблицу:
| ШИФРУЕМЫЙ_ТЕКСТ | 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 |
| ЩРДЪАТТССЦЪЫДФЬП | 25 | 13 | 4 | 26 | 0 | 18 | 17 | 17 | 22 | 26 | 27 | 4 | 20 | 28 | 15 |
Исходный текст невозможно восстановить без ключа.
Наложение белого шума в виде бесконечного ключа на исходный текст меняет статистические характеристики языка источника. Системы одноразового использования теоретически не расшифруемы[4], так как не содержат достаточной информации для восстановления текста.
Почему же эти системы неприменимы для обеспечения секретности при обработке информации? Ответ простой - они непрактичны, так как требуют независимого выбора значения ключа для каждой буквы исходного текста. Хотя такое требование может быть и не слишком трудным при передаче по прямому кабелю Москва - Нью-Йорк, но для информационных оно непосильно, поскольку там придется шифровать многие миллионы знаков.
Посмотрим, что получится, если ослабить требование шифровать каждую букву исходного текста отдельным значением ключа.
Системы шифрования Вижинера
Начнем с конечной последовательности ключа
k = (k0 ,k1 ,...,kn),
которая называется ключом пользователя, и продлим ее до бесконечной последовательности, повторяя цепочку. Таким образом, получим рабочий ключ
k = (k0 ,k1 ,...,kn), kj = k(j mod r, 0 £ j < ¥ .
Например, при r = ¥ и ключе пользователя 15 8 2 10 11 4 18 рабочий ключ будет периодической последовательностью:
15 8 2 10 11 4 18 15 8 2 10 11 4 18 15 8 2 10 11 4 18 ...
Определение. Подстановка Вижинера VIGk определяется как
VIGk : (x0, x1, ..., xn-1) ® (y0, y1, ..., yn-1) = (x0+k, x1+k,. .., xn-1+k).
Таким образом:
1) исходный текст x делится на r фрагментов
xi = (xi , xi+r , ..., xi+r(n-1)), 0 £ i < r;
2) i-й фрагмент исходного текста xi шифруется при помощи подстановки Цезаря Ck :
(xi , xi+r , ..., xi+r(n-1)) ® (yi , yi+r , ..., yi+r(n-1)),
Вариант системы подстановок Вижинера при m=2 называется системой Вернама (1917 г).
В то время ключ k=(k0 ,k1 ,...,kк-1) записывался на бумажной ленте. Каждая буква исходного текста в алфавите, расширенном некоторыми дополнительными знаками, сначала переводилась с использованием кода Бодо в пятибитовый символ. К исходному тексту Бодо добавлялся ключ (по модулю 2). Старинный телетайп фирмы AT&T со считывающим устройством Вернама и оборудованием для шифрования, использовался корпусом связи армии США.
Очень распространена плохая с точки зрения секретности практика использовать слово или фразу в качестве ключа для того, чтобы k=(k0 ,k1 ,...,kк-1) было легко запомнить. В ИС для обеспечения безопасности информации это недопустимо. Для получения ключей должны использоваться программные или аппаратные средства случайной генерации ключей.
Пример. Преобразование текста с помощью подстановки Вижинера (r=4)
Исходный текст (ИТ1):
НЕ_СЛЕДУЕТ_ВЫБИРАТЬ_НЕСЛУЧАЙНЫЙ_КЛЮЧ
Ключ: КЛЮЧ
Разобьем исходный текст на блоки по 4 символа:
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
