id: Гость   вход   регистрация
текущее время 07:09 25/04/2024
Владелец: unknown (создано 01/12/2013 18:44), редакция от 23/02/2014 13:30 (автор: unknown) Печать
Категории: криптография, симметричное шифрование, протоколы, сайт проекта, руководства, статьи, разное
https://www.pgpru.com/Библиотека/Руководства/СамоделкиИПодручныеСредства/КакУстроенТрадиционныйОдноразовыйБлокнот
создать
просмотр
редакции
ссылки

Как устроен традиционный одноразовый блокнот


В данном разделе будут собираться примеры использования одноразового блокнота, рассчитанного для ручного шифрования.


Оглавление документа:

Определение, основные требования и свойства


Одноразовым блокнотом называют криптосистему, при создании которой соблюдены следующие требования:


  1. Используется истинно случайный секретный симметричный ключ, известный в простейшем случае двум сторонам.
  2. Ключ равен длине сообщения.
  3. Ключ используется в качестве гаммы поточного шифрования, для чего объединяется с открытым текстом при помощи легкообратимой функции. Для расшифрования другая сторона использует этот же ключ для проведения над шифртекстом обратного преобразования, приводящего к получению открытого текста (расшифровке).
  4. Ключ используется только один раз, после чего должен быть по возможности уничтожен или по крайней мере должны быть предприняты меры, предотвращающие его повторное использование.


Пояснение к п.1:
Ключ должен быть получен из физически непредсказуемого случайного процесса, например из генератора случайных чисел. Поскольку не существует датчиков, способных на практике собрать идеально случайные числа, то собранные данные обычно подвергают предварительной обработке, т.н. экстракции или дистилляции случайности. При этом из большего количества сырых данных получают меньшее количество экстрагированных случайных чисел при помощи специальной функции экстракции, в ряде случаев в качестве которой может выступать и криптографический хэш. Использованные числа будут иметь равномерное и плоское распределение, а сам одноразовый блокнот будет абсолютно информационно-теоретически стойким (невзламываемым). Однако следует помнить, что одноразовый блокнот без дополнительных средств аутентификации и проверки целостности сообщений нестоек к подмене текста противником, даже если он не знает ключа. В некоторых операционных системах компьютеров встроены генераторы псевдослучайных чисел, пригодные для применения в стойкой криптографии, но не подходящие для использования в одноразовом блокноте: они разворачивают малое число входных случайных данных в большое и используют потенциально недостаточно надёжные источники случайности (энтропии). Т.о., хотя одноразовый блокнот м.б. использован для ручного шифрования, для подготовки ключевого материала чаще всего используются компьютеры или специализированная электронная техника.


Пояснение к п.2:
Для обмена множеством сообщений стороны заранее заготавливают совместный массив из большого числа случайных данных.


Пояснение к п.3:
Для двоичных данных используется функция XOR, которая является самообратимой. Для десятичной системы счисления удобнее использовать сложение по модулю 10 для шифрования и вычитание по модулю 10 для расшифрования. Поскольку большинство систем генерации случайных чисел расчитаны на генерацию двоичных данных, то можно выбирать данные от генераторов случайных чисел побайтово по модулю 10, отбрасывая байты, большие по величине чем 249.


Пояснение к п.4:
При повторном использовании одного и того же фрагмента гаммы (ключа одноразового блокнота) его стойкость теряется. При уничтожении ранее использованных ключей противник теряет возможность прочесть ранее переданные тексты, если они также были уничтожены (не сохранилось исходных открытых текстов): свойство наперёд заданной секретности (Perfect Forward Secrecy).

Операция гаммирования в двоичной и десятичной системе


Операция XOR — это сложение по модулю два. Если начинать отсчёт с нуля, то модули для обычных чисел будут выглядеть так:


Число012345
Модуль010101

Т.о. XOR битов определяет их чётность, результат этой операции можно записать как:


0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0


Как несложно заметить, эта операция самообратима, коммутативна и ассоциативна: если PK = C, то KC = K ⊕ (PK) = KPK = P


При работе с одноразовыми блокнотами в ручном режиме удобнее использовать сложение по модулю 10, что можно записать в виде таблицы (т.н. циркулянт):


+0123456789
00123456789
11234567890
22345678901
33456789012
44567890123
55678901234
66789012345
77890123456
88901234567
99012345678

Обратная операция вычитания по модулю выглядит как (строка минус столбец):


-0123456789
00987654321
11098765432
22109876543
33210987654
44321098765
55432109876
66543210987
77654321098
88765432109
99876543210

Пример гаммирования в десятичной системе:


открытый текст2566504501789222555425335
ключ8594822026986542565175871
шифртекст0050326527665764010590106

При обратной операции из шифртекста путём вычитании ключа по модулю десять получается открытый текст:


шифртекст0050326527665764010590106
ключ8594822026986542565175871
открытый текст2566504501789222555425335

Методы защиты от подмены сообщений


Если противнику известен текст сообщения, но неизвестен ключ, то он может его легко подменить. Поэтому шифрование без аутентификации и проверки целостности не используется в криптографических протоколах. Например, в простейшем случае сообщение «встречаемся сегодня» может быть подменено противником на «встречаемся завтра.». Также могут быть подменены и какие-то фрагменты сообщений, если противник догадывается только о содержимом этих фрагментов (например сумме сделки).


Абсолютно стойкий одноразовый блокнот может быть дополнен абсолютно стойкими кодами аутентификации сообщений. Однако, проверка таких кодов требует использования компьютеров. Даже вычислительно стойкие коды проверки на хэш-функциях не могут быть вычислены вручную. Кроме того, такие коды требуют дополнительных полей для записи. Наконец, если сообщение проходит по каналам связи с помехами, то единичные случайные ошибки могут быть восстановлены по смыслу текста, но не позволят сойтись кодам проверки.


Для ручных одноразовых блокнотов используется слабая проверка целостности. В начале или в конце открытого текста ставится стандартный заголовок, шифруемый в виде пятизначной группы. Затем шифртекст разбивается на две половины в случайном месте по пятизначным группам, обе половины меняются местами и объединяются заново. Получатель может заранее расшифровать известный ему заголовок и найти в тексте эту пятизначную группу, чтобы начать расшировку непосредственно начиная с неё. Таким образом, даже если противник будет знать содержимое открытого текста, он не сможет быть точно уверенным как расположен открытый текст и не сможет сделать безошибочную подмену, в то время как расшифровывающая сторона поймёт это после расшифровки текста по заголовкам.


Другой метод слабой аутентификации — использование индивидуальных кодовых таблиц для каждого получателя.

Эффективное представление буквенного алфавита в десятичном коде


Перед шифрованием буквенный алфавит естественного языка удобнее закодировать в десятичный вид.


В русском алфавите — 35 букв, в латинском, необходимом для английского языка — 26. Конечно, каждую букву можно обозначить двумя десятичными цифрами, но это неэкономно и неудобно для приведения в пятизначные группы цифр, с которыми принято работать. Существуют по крайней мере два метода компактного представления: один рассчитан на максимальную компактность, второй — на удобство работы с пятизначными группами.

Первый способ


Подробнее он описан здесь и здесь.


Выбирается слово или фраза, длиной 7-8 символов, в которых есть самые распространённые в языке буквы: "AT-ONE-SIR", "ESTONIA- – -" (английский), "DEIN- -STAR", "DES- -TIRAN" (немецкий), "SENORITA- -", "ENDIOSAR- -" (испанский), "RADIO-NET-" (голландский), "ZA- – -OWIES" (польский). Для русского языка известно применение урезанного слова: СНЕГОПА- – -.


Слово вписывается в таблицу, заполняя первую строку, оставляя пробелы вместо чёрточек. Оставшиеся цифры, напротив которых нет символов в первой строке, заполняются оставшимися символами алфавита:

0123456789
AT ONE SIR
2BCDFGHJKLM
6PQUVWXYZ.fig

Буквы из первой строки кодируются одной цифрой, но при этом не используется 2 и 6. Наличие 2 и 6 означает двузначный код, соответствие которому ищется во второй и третьей строке. Последний символ "fig" переключает открытый текст в режим передачи цифр.


Русский вариант:

0123456789
СНЕГОПА
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 spaceselect0select1
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)
1569310589171801322231416

Первые две буквы могут быть закодированы двумя цифрами из первой или второй строки. Третья буква кодируется одной цифрой, но в скобках к ней прилагается набор двух битов, которые определяют какую из строк надо выбирать для предыдущих двух букв. Раскодирование происходит в обратном порядке: первые две пары цифр однозначно указывают на нужный символ, при этом с них считываются биты, которые указывают как нужно раскодировать пятую одиночную цифру.


Для передачи цифр достаточно использовать первые пары цифр в диапазоне (40 — 49) для кодирования (0 — 9) соответственно, а пятую цифру в пятизначной группе оставлять как есть. Если пятая цифра не нужна, то она ставится в ноль, а после неё в следующей пятизначной группе кодируется знак "backspace". Переключатель "select1" переключает в альтернативную раскладку или в расширенный режим использования запасных цифр (90 — 99), переключатель "select0" возвращает в положение по умолчанию.


 
На страницу: 1, 2 След.
Комментарии [скрыть комментарии/форму]
— Гость (23/02/2014 08:50)   <#>

Это не нарушит равномерность (случайность) распределения?


Может, всё-таки расшифровать?


55 дважды используется — это нормально? Метод долго курил, но в итоге вроде понял, спасибо. Код извращённый, но, тем не менее, instantaneous (в смысле C&T), да?

The following code is uniquely decodable but is not instantaneous because you do not know when one symbol is over without looking further



В ру-вики какая-то херня полная написана:

Код, состоящий из слов 0, 10, 11 и 100, префиксным не является, и то же сообщение можно трактовать несколькими способами.

Если промежутков или других знаков препинания между кодовыми комбинациями нет, то для однозначного декодирования комбинации 111011101 ни одна из кодовых комбинаций не может быть представлена перечисленными вариантами (префиксами).

Вообще-то префиксность (судя по англовики, это синоним instantaneous) не запрещает коду быть однозначно декодируемым.
— unknown (23/02/2014 13:45, исправлен 23/02/2014 19:25)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Это как раз сделано для того, чтобы оно не нарушалось. Каждый байт — это в десятичном виде число в интервале {0…255}. Лень составлять оформленную таблицу, поэтому вот фрагмент в виде трёхзначных десятичных чисел:



Если байт в десятичном виде < 249, то по модулю 10 — это последняя цифра этого числа. Распределение нормальное и равномерное.


Если выпадает байт, больший 249, то получается хвост в распределении, который надо отбросить вместе с этим байтом и сгенерить байт заново:



Спасибо за внимательность, опечатки исправлены.



В каждой группе из пяти цифр — три знака. Первые два становятся однозначно декодируемыми после получения пятой цифры. Пятая цифра даёт однозначное раскодирование после получения предыдущих четырёх в группе. Вот и думайте, куда его отнести. Это если считать ещё только стандартный режим, а есть же переключатели, например для передачи цифр.

— Гость (24/02/2014 06:04)   <#>
Ввиду того, что

Если пятая цифра не нужна, то она ставится в ноль, а после неё в следующей пятизначной группе кодируется знак "backspace".

код не является instantaneous. Т.е. вы не можете понять, ноль там или не ноль, до тех пор, пока не раскодируете следующую букву. Если цифры не используются, то, по-видимому, будет instantaneous даже с переключателями (переключатель влияет на раскодируемость вправо, а не влево, что нужно для потери свойства instantaneous).

P.S. Мне когда-то примеры кодов, которые не-instantaneous, казались ивзвращёнными и мало где используемыми, но, наверно, я просто пока мало знаю.
— unknown (24/02/2014 10:40)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Если цифры не используются, то, по-видимому, будет instantaneous даже с переключателями (переключатель влияет на раскодируемость вправо, а не влево, что нужно для потери свойства instantaneous).

За счёт того, что разделителем является условный пробел между каждыми пятицифровыми группами, то, получается — да.

Мне когда-то примеры кодов, которые не-instantaneous, казались ивзвращёнными и мало где используемыми, но, наверно, я просто пока мало знаю.

Есть не только коды, но ещё и алгоритмы шифрования (вычислительные, а не OTP), которые приспособлены для оптимальной работы с недвоичными данными — там тоже полно схожих извратов.
— Гость (24/02/2014 12:12)   <#>
Вообще, все эти определения (instantaneous или нет) субъективы в том смысле, что зависят от того, как вы определяете алфавит. Обычно рассматривается канал реального времени между Алисой и Бобом, по которому по одному передаются символы алфавита, из которых затем, в свою очередь, составляются (кодовые) слова, а слова потом сопоставляются тем данным, которые они кодировали. Но в OTP на бумаге вся шифровка передаётся сразу, поэтому такая мысленная картинка не отражает реальность. Можно кодовыми словами кодировать не одиночные цифры, а сразу готовые числа (это вопрос интерпретации одной и той же схемы кодирования), тогда получится, что свойство «не-instantaneous» снимается.


Разделитель непринципиален. Как раз сравнение по признаку instantaneous (дословный перевод — «мгновенный код» — неплохо отражает мысль) позволяет сравнить два типа кодов без разделителя. Когда код мгновенный, вы его раскодируете «мгновенно» несмотря на то, что разделителей нет, т.к. кодовые слова «не перекрываются». Когда код немгновенный, вы в ряде случаев вынуждены посмотреть, что будет идти дальше, прежде чем однозначно раскодировать уже полученное.


DH на openPGP-группах? ☺
— Гость (24/02/2014 12:15)   <#>

Криптостойкость через пропускную способность


По теме OTP когда-то возникла более фундаментальная мысль (не знаю, насколько она популярна у криптографов), применимая как к классическому OTP, так и квантовому: идеальное шифрование (безусловная IT-безопасность) то и только то, при котором канал между шифрователем и расшифровывателем имеет нулевую пропускную способность.

Классический OTP


Канальная интерпретация классического OTP такова: Алиса имеет последовательность битов своих данных, которые она посылает в зашумлённый канал. Канал (и физически и как математическое отображение) действует следующим образом: к каждому биту Алисы прибавляется или 0 или 1 случайным образом (двоичная арифметика). Понятно, что Боб, получив такие данные, не сможет ничего узнать о том, что посылала Алиса.

Вообразим, что между Алисой и Бобом есть реально имеено такой канал, но Алиса с Бобом сотрудничают, Алиса хочет передать ему информацию. Может ли она это сделать? В общем случае, шум в канале — не проблема. Для борьбы с шумом Алиса может выбирать кодовые слова, адаптированные к шуму, таким образом, что Боб их сможет различать с высокой вероятностью. Теорема Шеннона говорит, что для канала с пропускной способностью C существует такая схема кодирования информации, что в среднем, на бесконечном числе пересылок информации, за один посыл будет передаваться C бит информации с ошибкой, стремящейся к нулю.* Теорема Шеннона — «классическая» теорема существования: она утверждает, что код существует, но не даёт никаких намёков на способ его нахождения. Как найти такой код — отдельная большая проблема, которую изучает теория кодирования (многие проблемы там открыты до сих пор).

Кроме того, в обычной теории информации (неквантовой) выполняется принцип strong converse. Он утверждает, что при превышении пропускной способности канала вероятность раскодировать без ошибки кодовые слова правильным образом будет стремиться к нулю (в среднем, на бесконечном числе посылок через канал) независимо от выбора кодовых слов. Грубо говоря, вполне может так быть, что Боб в какой-то раз получит ровно то, что посылала Алиса или угадает, как исправить ошибки, но в среднем он будет от неё получать бессмысленный рандом, из которого нельзя будет извлечь ничего надёжным образом. Т.е. пропускная способность канала в классической теории информации (ТИ) — резкая граница на скорость передачи данных.

В классическом OTP, с учётом того, что strong converse выполняется, а C=0, получаем как бы доказательство идеальности шифрования одноразового блокнота. Это правильная интерпретация? ☺

Квантовый OTP


Интересно, что в квантовом OTP всё веселей. Дело в том, что в квантовой теории информации (КТИ), в общем случае, strong converse не выполняется, а есть только weak converse. Т.е. из теоремы Холево, являющейся аналогом теоремы Шеннона, weak следует, а strong нет. Конкретные каналы, для которых strong действительно невыполняется, тоже известны. Weak converse, по определению, говорит о том, что если вы превысили пропускную способность, то вероятность ошибки при раскодировании (в среднем) будет, как минимум, выше нуля, но необязательно единичной. Вроде как при росте скорости передачи данных ошибка будет как-то плавно увеличиваться от нуля (при равенстве пропускной способности) до единицы. Т.е. в КТИ, в отличие от классической ТИ, классическая пропускная способность уже не резкая граница на скорость передачи данных.

Вроде бы не так давно Винтер ввёл даже ещё более забавную штуку — pretty strong converse** — это разновидность weak converse, при котором вероятность ошибки при превышении пропускной способности становится скачком не меньше некоторого числа p, такого что 0<p<1, после чего она растёт с ростом скорости передачи данных.

Для конкретного канала, реализующего квантовый OTP через случайно выбираемые повороты с помощью матриц Паули, вроде бы strong converse всё же выполнен, но если аппелировать к озвученной здесь трактовке «идеальности шифрования», на это надо указывать явно (и даже доказывать, если ещё кем-то не доказано), т.к. в общем случае strong converse'а нет.

Общий случай


Ну, и, естественно, когда шифрование неидеальное, с точки зрения ТИ это, видимо, означает, что C>0, т.е. у «канала утечек» ненулевая пропускная способность. Чисто гипотетически можно себе вообразить, что пропускную способность для реального шифрования с помощью блочных шифров можно найти, но на практике это утопия. ☺ Однако, не факт, что вообще имеет смысл это делать, т.к. квантификация через пропускную способность может не отражать нестойкость шифра. К примеру, если вы оцениваете стойкость ГСЧ, мера утечки через пропускную способность точно не является адекватной. В частности, если ГСЧ смещён, взаимная информация между Алисой и Бобом всегда нулевая, поэтому нулевая и пропускная способность. Однако, информация о смещении ГСЧ (а это тип неидеальности ГСЧ) позволяет предсказать его выхлоп быстрее, чем полностью рандомно сгенерированной строки, поэтому «понижение безопасности» есть. Как я понимаю, Massey guessing entropy даёт правильную оценку этого понижения.


*Шум подразумевает, что какие-то искажения в канале более вероятны, какие-то менее вероятны, но можно написать код, учитывающий эти вероятности так, что вероятность что-то не раскодировать будет стремиться к нулю.
**См. fileслайды с пленарного доклада, стр. 55, 101, 118 и 119.
— unknown (24/02/2014 12:43)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

В смысле? Нет, это для симметрики, которую по условиям можно шифровать только блочными шифрами. Вот нужен, к примеру, блок размером не 2128, а 1050. И область определения входа-выхода такая же: десятичная степень, а не двоичная.

Об остальном, совсем неклассическом OTP, надо думать.
— Гость (24/02/2014 14:49)   <#>

Классический OTP тоже так можно рассматривать, трактовка приведена, но у меня нет ни малейшей гарантии, что так трактовать OTP правильно.


На тропической алгебре уже было, на вложенных алгебраических структурах тоже, а на openPGP-группах ещё нет. Можете считать {у,неу}дачной шуткой.


Понятно.


Где такое может понадобиться, кроме как в ручном шифровании и во всяких троичных компьютерах?
— unknown (24/02/2014 15:38, исправлен 24/02/2014 15:47)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Где такое может понадобиться, кроме как в ручном шифровании и во всяких троичных компьютерах

коды запуска ядерных ракет
Когда что-то ручное сочетается с неручным в специфических протоколах. Например, надо зашифровать поле с пин-кодом кредиток или номеров бюллетеней в базе данных без рэндомизации, аутентификации и увеличения размера шифртекста. Или что-то криптостойко перетасовать по ключу, как колоду карт, не сохраняя в памяти весь массив перетасовок, а имея произвольный доступ. Когда надо получить перестановку всех входов на выходы, зависящую от ключа, как в обычном блочном шифре, но для какого-то фиксированного числа входов. Это может даже не от степени зависеть, может быть вообще некруглое ни в какой обычной системе счисления число. И его надо сделать размером блока.

— Гость (09/01/2015 17:48)   <#>
Ключ равен длине сообщения.
Точно равен или может быть больше?

И теория, конечно, хорошо, а где софт под это?
А то весь сайт забит только решениями "открытый-закрытый ключ".
— ressa (09/01/2015 18:50)   профиль/связь   <#>
комментариев: 1079   документов: 58   редакций: 59
Зачем тебе софт под шифроблокнот? Для обмена сообщениями по сети – есть куча других решений. Почта – GnuPG, xmpp – OTR. Даже этого с головой достаточно.
— Гость (09/01/2015 19:59)   <#>
Дело не в самом шифроблокноте, конечно, а в том что симметричный шифр в отличие решений на открытом ключе (включая PGP/GNUPG и т.д. и т.п.) практически невзламываемый (если я ничего не путаю).
— Следящий (09/01/2015 20:35)   профиль/связь   <#>
комментариев: 97   документов: 1   редакций: 3
Не то чтобы симметричный вообще, а именно шифрблокнот в частности, и не "практически не взламываемый", а теоретически невзламываемый, а это даже круче :)
— Гость (09/01/2015 21:31)   <#>

Перл закручен покруче, чем афоризмы Кличко :))
Можете изложить свою мыслъ доступнее? Ии это шутка была?
— Следящий (09/01/2015 22:09, исправлен 09/01/2015 22:09)   профиль/связь   <#>
комментариев: 97   документов: 1   редакций: 3

Как это Вы так лихо кусок фразы выкинули и гогочете над собой (ибо это уже вообще по смыслу не то, что я написал) :)

На страницу: 1, 2 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3