Как устроен традиционный одноразовый блокнот
В данном разделе будут собираться примеры использования одноразового блокнота, рассчитанного для ручного шифрования.
Определение, основные требования и свойства
Одноразовым блокнотом называют криптосистему, при создании которой соблюдены следующие требования:
- Используется истинно случайный секретный симметричный ключ, известный в простейшем случае двум сторонам.
- Ключ равен длине сообщения.
- Ключ используется в качестве гаммы поточного шифрования, для чего объединяется с открытым текстом при помощи легкообратимой функции. Для расшифрования другая сторона использует этот же ключ для проведения над шифртекстом обратного преобразования, приводящего к получению открытого текста (расшифровке).
- Ключ используется только один раз, после чего должен быть по возможности уничтожен или по крайней мере должны быть предприняты меры, предотвращающие его повторное использование.
Пояснение к п.1:
Ключ должен быть получен из физически непредсказуемого случайного процесса, например из генератора случайных чисел. Поскольку не существует датчиков, способных на практике собрать идеально случайные числа, то собранные данные обычно подвергают предварительной обработке, т.н. экстракции или дистилляции случайности. При этом из большего количества сырых данных получают меньшее количество экстрагированных случайных чисел при помощи специальной функции экстракции, в ряде случаев в качестве которой может выступать и криптографический хэш. Использованные числа будут иметь равномерное и плоское распределение, а сам одноразовый блокнот будет абсолютно информационно-теоретически стойким (невзламываемым). Однако следует помнить, что одноразовый блокнот без дополнительных средств аутентификации и проверки целостности сообщений нестоек к подмене текста противником, даже если он не знает ключа. В некоторых операционных системах компьютеров встроены генераторы псевдослучайных чисел, пригодные для применения в стойкой криптографии, но не подходящие для использования в одноразовом блокноте: они разворачивают малое число входных случайных данных в большое и используют потенциально недостаточно надёжные источники случайности (энтропии). Т.о., хотя одноразовый блокнот м.б. использован для ручного шифрования, для подготовки ключевого материала чаще всего используются компьютеры или специализированная электронная техника.
Пояснение к п.2:
Для обмена множеством сообщений стороны заранее заготавливают совместный массив из большого числа случайных данных.
Пояснение к п.3:
Для двоичных данных используется функция XOR, которая является самообратимой. Для десятичной системы счисления удобнее использовать сложение по модулю 10 для шифрования и вычитание по модулю 10 для расшифрования. Поскольку большинство систем генерации случайных чисел расчитаны на генерацию двоичных данных, то можно выбирать данные от генераторов случайных чисел побайтово по модулю 10, отбрасывая байты, большие по величине чем 249.
Пояснение к п.4:
При повторном использовании одного и того же фрагмента гаммы (ключа одноразового блокнота) его стойкость теряется. При уничтожении ранее использованных ключей противник теряет возможность прочесть ранее переданные тексты, если они также были уничтожены (не сохранилось исходных открытых текстов): свойство наперёд заданной секретности (Perfect Forward Secrecy).
Операция гаммирования в двоичной и десятичной системе
Операция XOR — это сложение по модулю два. Если начинать отсчёт с нуля, то модули для обычных чисел будут выглядеть так:
Число | 0 | 1 | 2 | 3 | 4 | 5 |
Модуль | 0 | 1 | 0 | 1 | 0 | 1 |
Т.о. XOR битов определяет их чётность, результат этой операции можно записать как:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0
Как несложно заметить, эта операция самообратима, коммутативна и ассоциативна: если P ⊕ K = C, то K ⊕ C = K ⊕ (P ⊕ K) = K ⊕ P ⊕ K = P
При работе с одноразовыми блокнотами в ручном режиме удобнее использовать сложение по модулю 10, что можно записать в виде таблицы (т.н. циркулянт):
+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 |
2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 |
3 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 |
4 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 |
5 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 |
6 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 |
7 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
8 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
9 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Обратная операция вычитания по модулю выглядит как (строка минус столбец):
- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0 | 0 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
1 | 1 | 0 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 |
2 | 2 | 1 | 0 | 9 | 8 | 7 | 6 | 5 | 4 | 3 |
3 | 3 | 2 | 1 | 0 | 9 | 8 | 7 | 6 | 5 | 4 |
4 | 4 | 3 | 2 | 1 | 0 | 9 | 8 | 7 | 6 | 5 |
5 | 5 | 4 | 3 | 2 | 1 | 0 | 9 | 8 | 7 | 6 |
6 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 9 | 8 | 7 |
7 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 9 | 8 |
8 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 9 |
9 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
Пример гаммирования в десятичной системе:
открытый текст | 25665 | 04501 | 78922 | 25554 | 25335 |
ключ | 85948 | 22026 | 98654 | 25651 | 75871 |
шифртекст | 00503 | 26527 | 66576 | 40105 | 90106 |
При обратной операции из шифртекста путём вычитании ключа по модулю десять получается открытый текст:
шифртекст | 00503 | 26527 | 66576 | 40105 | 90106 |
ключ | 85948 | 22026 | 98654 | 25651 | 75871 |
открытый текст | 25665 | 04501 | 78922 | 25554 | 25335 |
Методы защиты от подмены сообщений
Если противнику известен текст сообщения, но неизвестен ключ, то он может его легко подменить. Поэтому шифрование без аутентификации и проверки целостности не используется в криптографических протоколах. Например, в простейшем случае сообщение «встречаемся сегодня» может быть подменено противником на «встречаемся завтра.». Также могут быть подменены и какие-то фрагменты сообщений, если противник догадывается только о содержимом этих фрагментов (например сумме сделки).
Абсолютно стойкий одноразовый блокнот может быть дополнен абсолютно стойкими кодами аутентификации сообщений. Однако, проверка таких кодов требует использования компьютеров. Даже вычислительно стойкие коды проверки на хэш-функциях не могут быть вычислены вручную. Кроме того, такие коды требуют дополнительных полей для записи. Наконец, если сообщение проходит по каналам связи с помехами, то единичные случайные ошибки могут быть восстановлены по смыслу текста, но не позволят сойтись кодам проверки.
Для ручных одноразовых блокнотов используется слабая проверка целостности. В начале или в конце открытого текста ставится стандартный заголовок, шифруемый в виде пятизначной группы. Затем шифртекст разбивается на две половины в случайном месте по пятизначным группам, обе половины меняются местами и объединяются заново. Получатель может заранее расшифровать известный ему заголовок и найти в тексте эту пятизначную группу, чтобы начать расшировку непосредственно начиная с неё. Таким образом, даже если противник будет знать содержимое открытого текста, он не сможет быть точно уверенным как расположен открытый текст и не сможет сделать безошибочную подмену, в то время как расшифровывающая сторона поймёт это после расшифровки текста по заголовкам.
Другой метод слабой аутентификации — использование индивидуальных кодовых таблиц для каждого получателя.
Эффективное представление буквенного алфавита в десятичном коде
Перед шифрованием буквенный алфавит естественного языка удобнее закодировать в десятичный вид.
В русском алфавите — 35 букв, в латинском, необходимом для английского языка — 26. Конечно, каждую букву можно обозначить двумя десятичными цифрами, но это неэкономно и неудобно для приведения в пятизначные группы цифр, с которыми принято работать. Существуют по крайней мере два метода компактного представления: один рассчитан на максимальную компактность, второй — на удобство работы с пятизначными группами.
Первый способ
Подробнее он описан здесь и здесь.
Выбирается слово или фраза, длиной 7-8 символов, в которых есть самые распространённые в языке буквы: "AT-ONE-SIR", "ESTONIA- – -" (английский), "DEIN- -STAR", "DES- -TIRAN" (немецкий), "SENORITA- -", "ENDIOSAR- -" (испанский), "RADIO-NET-" (голландский), "ZA- – -OWIES" (польский). Для русского языка известно применение урезанного слова: СНЕГОПА- – -.
Слово вписывается в таблицу, заполняя первую строку, оставляя пробелы вместо чёрточек. Оставшиеся цифры, напротив которых нет символов в первой строке, заполняются оставшимися символами алфавита:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
A | T | O | N | E | S | I | R | |||
2 | B | C | D | F | G | H | J | K | L | M |
6 | P | Q | U | V | W | X | Y | Z | . | fig |
Буквы из первой строки кодируются одной цифрой, но при этом не используется 2 и 6. Наличие 2 и 6 означает двузначный код, соответствие которому ищется во второй и третьей строке. Последний символ "fig" переключает открытый текст в режим передачи цифр.
Русский вариант:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
С | Н | Е | Г | О | П | А | ||||
7 | Б | Ж | . | К | № | Р | Ф | Ч | Ы | Ю |
8 | В | З | , | Л | Н/Ц | Т | Х | Ш | Ь | Я |
9 | Д | И | П/Л | М | Н/Т | У | Ц | Щ | Э | ПВТ |
Таблица кодирования работает по аналогичному принципу, только с использованием трёх односимвольных строк и некоторых служебных аббревиатур.
Второй способ
Второй способ рассчитан на использование алфавита из сорока символов (не считая дополнительных возможностей, даваемых переключателями) и дополнительно цифр. При этом каждые три символа кодируются в пятизначную группу. Этот способ больше подходит, когда необходимо передавать текст с большими алфавитами, например содержащий компьютерные символы.
A/А | B/Б | C/В | D/Г | E/Д | F/Е | G/Ж | H/З |
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 |
0(00) | 0(01) | 0(10) | 0(11) | 1(00) | 1(01) | 1(10) | 1(11) |
---|---|---|---|---|---|---|---|
I/И | J/Й | K/К | L/Л | M/М | N/Н | O/О | P/П |
08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 |
2(00) | 2(01) | 2(10) | 2(11) | 3(00) | 3(01) | 3(10) | 3(11) |
Q/Р | R/С | S/Т | T/У | U/Ф | V/Х | W/Ц | X/Ч |
16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 |
4(00) | 4(01) | 4(10) | 4(11) | 5(00) | 5(01) | 5(10) | 5(11) |
Y/Ш | Z/Щ | @/Ъ | #/Ы | $/Ь | %/Э | (/Ю | )/Я |
24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 |
6(00) | 6(01) | 6(10) | 6(11) | 7(00) | 7(01) | 7(10) | 7(11) |
. | , | ! | ? | backspace | space | select0 | select1 |
32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 |
8(00) | 8(01) | 8(10) | 8(11) | 9(00) | 9(01) | 9(10) | 9(11) |
Рассмотрим пример кодирования:
ПУН | КТ_ | СТА | НЦИ | Я16 |
(15,65)(19,69)3(0,1) | (10,60)(18,58)9(0,1) | (17,67)(18,68)0(0,0) | (13,63)(22,72)2(0,0) | (31,81)(41,41)(6,6) |
15693 | 10589 | 17180 | 13222 | 31416 |
Первые две буквы могут быть закодированы двумя цифрами из первой или второй строки. Третья буква кодируется одной цифрой, но в скобках к ней прилагается набор двух битов, которые определяют какую из строк надо выбирать для предыдущих двух букв. Раскодирование происходит в обратном порядке: первые две пары цифр однозначно указывают на нужный символ, при этом с них считываются биты, которые указывают как нужно раскодировать пятую одиночную цифру.
Для передачи цифр достаточно использовать первые пары цифр в диапазоне (40 — 49) для кодирования (0 — 9) соответственно, а пятую цифру в пятизначной группе оставлять как есть. Если пятая цифра не нужна, то она ставится в ноль, а после неё в следующей пятизначной группе кодируется знак "backspace". Переключатель "select1" переключает в альтернативную раскладку или в расширенный режим использования запасных цифр (90 — 99), переключатель "select0" возвращает в положение по умолчанию.