Шифр Вернама и гаммирование
Шифр Вернама и шифроблокноты
Шифр Вернама был предложен а 1917 г. телеграфистом Гильбертом Вернамом. Суть шифра Вернама том, что шифрованный тест есть объединение открытого текста и ключа с помощью исключающего ИЛИ (то есть EncryptedText = OpenText XOR Key). Ключ - случайная последовательность бит. Вернам построил телеграфный аппарат, который выполнял эту операцию после подачи ленты с ключом.
Вернам заметил, что для обеспечения стойкости шифра каждая лента должна быть одноразовой. Это непросто применить на практике, потому возможно закольцовывать несколько лент, причём их длины различны и являются взаимно простыми. Например,
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
Как видим, в зелёной и жёлтой лентах нет закономерностей в размещении бит, при этом длины 7 и 5 - взаимно простые. Когда эта единая большая лента заканчивается, вновь начинаем с левого бита зелёной ленты. При практическом применении шифра Вернама, разумеется, лучше больше лент и длины побольше.
Возможно также применение так называемой схемы шифроблокнотов. Стороны, которые обмениваются сообщениями, имеют в своём распоряжении по одинаковому блокноту. На каждой страничке шифроблокнота - по ключу. После посылки очередного сообщения обе стороны вырывают страничку из своего блокнота, на которой был записан текущий ключ. Для следующего сообщения будет использоваться ключ со следующей страницы, которая потом так же будет вырвана. В современных условиях в качестве шифроблокнотов могут быть файлы на носителях электронной информации - тогда каждый раз удаляется очередной использованный ключ: все ключи одноразовые.
Проблема в том, что шифроблокноты нужно как-то передать. Для этого нужна личная встреча или надёжный посредник. Чего нельзя точно - так это передавать шифроблокнот по тому же каналу, что будет использоваться для передачи сообщений. На крайняк следует использовать два канала - один для ключей, другой для сообщений. Тогда противнику придётся прослушивать два канала, чтобы раскрыть передаваемые сведения, что несколько усложняет его задачу.
Гаммирование
Пусть есть какой-то алфавит, его символы закодированы числами. Каждое число предстваляется в виде группы из m бит, а m выбирается так, чтобы можно было закодировать все символы алфавита. Допустим, в алфавите 8 символов. Если m = 2, можем закодировать только 4 из них, а вот m = 3 - пойдёт.
Есть открытый текст. Каждый символ имеет какой-то номер в алфавите, поэтому может быть закодирован теми самыми битами. Например, алфавит: {А = 00, Б = 01, В = 10, Г = 11}, m = 2. Тогда БАГ => 01 00 11. Эти группы бит соединяем в одну цепочку. То есть был БАГ, а стало 010011.
На всякий случай стоит пояснить, что такое псевдослучайные числа. Это числа, последовательность которых получена по некоторому алгоритму, причём так, что со стороны её трудно отличить от случайной. Некоторые алгориты получения псевдослучайных чисел можно узнать здесь.
Что дальше? Полученная ранее цепочка разбивается на блоки по q бит, пусть всего получилось N блоков. Пусть есть ещё группа G из p целых разных псевдослучайных чисел, не меньших 0 и не больших 2^q - 1 (^ - значок степени). Нумерация блоков и псевдослучайных чисел ведётся с нуля, i-ый блок складываем с q-битным представлением (i mod p)-го числа группы G, получаем какую-то группу бит B(i). Все полученные таким способом группы бит (то есть B(i), i = 0,1,...,N-1) объединяем и далее по полученному набору бит выписываем символы шифрованного текста.
Сложение бит делается так: если оба бита одинаковые, в итоге 0, иначе 1 (известно как операция XOR). Например, 101 + 110 = 011.
Важно, чтобы параметр q был довольно большим числом - это повышает стойкость к атакам.
Псевдослучайные числа получаются с помощью специальных генераторов псевдослучайных чисел (ГПСЧ). За счёт их применения псевдослучайную последовательность непосредственно хранить не нужно - вместо этого нужно хранить несколько параметров алгоритма генерации. Такие последовательности являются периодическими, и параметр p, указанный выше, как раз и есть период.
Теперь пример. Здесь просто покажем сложение блоков с псевдослучайной последовательностью, без пояснений по ГПСЧ. Возьмём русский алфавит без Ё, Тогда можно кодировать по 5 бит (A = 00000, Б = 00001, В = 00010...). Тогда БАГ = 000010000000011. Пусть q = 3, p = 2, G = десятичный вид:{4, 5} = двоичный вид: {100, 101} (для демонстрации пойдёт, хотя вообще это не особо случайный ряд, да и период маловат). БАГ = 000 010 000 000 011.
| Блок | "Налагаемые" биты |
Сложение |
| 000 | 100 | 100 |
| 010 | 101 | 111 |
| 000 | 100 | 100 |
| 000 | 101 | 101 |
| 011 | 100 | 111 |
Посмотрите внимательно на среднюю колонку - "налагаемые" битовые наборы циклически повторяются: их меньше, чем блоков.
Наборы из правой колонки объядиняем. Поскольку символы алфавита кодируются 5 битами, группируем по 5 бит: ШИФР(БАГ) = 100111100101111 = {19, 25, 15}, то есть нам нужно найти в алфавите символы номер 19, 25, 15 (нумерация ведётся с нуля).
| 0-9 | АБВГДЕЖЗИЙ |
| 10-19 | КЛМНОПРСТУ |
| 20-29 | ФХЦЧШЩЪЫЬЭ |
| 30-31 | ЮЯ |
Итог - пресловутое УЩП. То есть БАГ изменился до неузнаваемости.
Описанный метод шифрования называется гаммированием. Последовательность бит, которая "преобразует" открытый текст, называется гаммой или гамма-последовательностью.
Шифр Вернама и гаммирование: расшифрование
Поскольку x XOR x = 0, OpenText XOR Key XOR Key = OpenText. Это означает, что и для шифра Вернама, и для гаммирования алгоритм расшифрования тот же, что и алгоритм шифрования.
Отличия шифра Вернама и гаммирования
1. В гаммировании не используется никаких шифроблокнотов и прочей дряни, заставляющей полностью хранить ключ. Требуется только знание параметров ГПСЧ, на основе которых последовательность псевдослучайных чисел восстанавливается по мере необходимости - при шифровании и расшифровании.
2. Гаммирование является блочным шифром. Это было легко заметить на примере, где открытый текст делился на блоки бит (в табличке к нему один из столцов так и называется - "блок"). Шифр Вернама блочным не является, что легко понять по описанию. Он относится к так называемым поточным шифрам.
Коротко о получении случайных и псевдослучайных чисел
Как получить "рандомизированную" последовательность чисел?
1. Псевдослучайная генерация. Есть так называемые генераторы псевдослучайных чисел (ГПСЧ). Они создают закономерные ряды чисел, но закономерности плохо видны со стороны - тем, кто о них не знает. При этом числа обычно циклически повторяются. Допустим, ряд 5, 1, 4, 3, 7, 2, 6, 5, 1, 4... Тут 7 чисел, которые будут снова и снова повторяться. В таком случае период последовательности равен 7.
2. Неалгоритмический подход. Есть неалгоритмические пути получения случайных чисел. Для этого возможно использовать какие-либо случайные величины из внешнего мира - например, характеристики шумов, космического излучения и т.д. В конце концов, если просто зафиксировать текущий момент времени, то количество часов, минут, даже секунд неслучайно. А вот количество миллисекунд для нас непредсказуемо, то есть может считаться случайной величиной.
В реальных приложениях обычно используют ГПСЧ.