Регистрация Войти
Рейтинг:5
avatar Crypto

Совершенно секретный сменный одноразовый блокнот

флаг in
Lug322d

Рассмотрим переменный одноразовый блокнот, то есть $\mathcal{M}:=\{0,1\}^{\leq \ell}$ представляет собой набор простого текста. Теперь эта схема не является совершенно секретной, так как вы можете взять два простых текста разного размера, скажем $|м_1| = 1, |m_2| = 2$ и рассматривая зашифрованный текст $с$ длины 1 происходит следующее: $$Pr(E(k, m_1) = c) = \frac{1}{2},\ Pr(E(k, m_2) = c) = 0.$$

Таким образом, как я могу сделать конструкцию этого переменного одноразового блокнота такой, чтобы он был совершенно секретным? Это вообще возможно?

Я пробовал делать субодноразовые блокноты, т.е. $\ell$ одноразовые блокноты, но это не работает, когда у вас есть два сообщения одинаковой длины (такой же, как указано выше), поэтому моя другая идея заключалась в том, чтобы расширить все сообщения до длины $\ell$ добавлением нулей справа. Проблема, однако, в том, что если вы считаете $\элл = 4$, как расшифровать сообщения 1, 10, 100, 1000?

125
0 + 0
kodlu avatar
флаг sa
kodlu
ваши открытые тексты имеют одинаковый размер, не так ли?
0
Ответить
флаг in
Lug322d
@kodlu Нет, они не больше $\ell$.
0
Ответить
Paul Uszak avatar
флаг cn
Paul Uszak
Привет, Луг и добро пожаловать :-) Пожалуйста, просмотрите вопрос, так как он сбивает с толку. Что именно вы спрашиваете? Хотя мы здесь любим одноразовые блокноты...
0
Ответить
флаг in
Lug322d
Спасибо @PaulUszak! Проще говоря, я пытаюсь сформировать одноразовый блокнот переменной длины, что совершенно секретно.
0
Ответить
Paul Uszak avatar
флаг cn
Paul Uszak
Хорошо. Да, OTP является информационно безопасным. Но вы говорите формулами. Есть ли устройство для производства ключевого материала? И я не понимаю бит _"переменная"_.Вы имеете в виду, что |key| = |открытый текст|? А что такое $|m_1| = 1, |m_2| = 1$? Один бит?
0
Ответить
флаг in
Lug322d
Определение того, о чем я говорю, содержится в примере 2.2 этой книги: https://crypto.stanford.edu/~dabo/cryptobook/draft_0_3.pdf. И да, они однобитные, хотя $m_2$ должно быть двухбитным.
0
Ответить
Paul Uszak avatar
флаг cn
Paul Uszak
Извинения. Я не понял.
0
Ответить
флаг cn
Maeher
Уменьшите максимальную длину сообщения на единицу и используйте заполнение единицами и нулями. т.е. всегда добавляйте один бит 1 и заполняйте остальные битами 0. Чтобы распаковать, удалите все конечные нули и первую 1 с конца.
0
Ответить
флаг in
Lug322d
@Maeher Но тогда это уже не будет OTP. Злоумышленник может просто удалить и эти биты, и они получат OTP переменной длины.
0
Ответить
флаг jp
user253751
Вы предполагаете, что |E(K,m1)| = 1. Это обязательно?
0
Ответить
флаг cn
Maeher
@Lug322d нет, они не могут. Очевидно, вы дописываете *перед* шифрованием.
0
Ответить
Рейтинг:2
Marc Ilunga avatar Crypto
флаг tr
Marc Ilunga

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

Часто упускается из виду, что это определение безопасности не подходит для общих контекстов, где отправляются данные переменной длины. Например, приложение, в котором да и нет единственное отправленное сообщение было бы небезопасным при наивном применении одноразового блокнота.

Решение 1. Заполнение сообщения Самый простой способ — применить механизм сокрытия длины, схему заполнения, которая дополняет сообщения до одинаковой длины, а затем шифрует дополненное сообщение. А именно. для сообщений длиной $л$, сообщения могут быть дополнены до нужной длины $к = л + 2$ (долго тоже может работать). Заполнение $м$ является $pad(m) = m \|10^{k - |m| - 1}$. Это можно сделать, поскольку постановка задачи не ограничивает длину площадок.

Решение 2. Кодирование в группу. Поскольку есть $к = 2^l$ сообщений, другой идеей было бы кодировать (однозначно) сообщения в структуру, подобную группе, с той же кардинальностью; оттуда можно применить OTP к группе. Расшифровка требует расшифровки. Самый простой пример будет $(\mathbb{Z}/k\mathbb{Z}, +)$

0 + 0
флаг in
Lug322d
Итак, я снова прочитал это решение, и теперь у меня есть один вопрос для каждого решения. Что касается решения 1, как расшифровать сообщение, чтобы снова получить $m$? Получатель не может знать, какие биты ему нужно удалить, поскольку заполнение также было зашифровано. А для решения 2 я думаю, что количество возможных сообщений равно $\sum_{i=0}^\ell 2^i$, поскольку оно является переменной.
0
Ответить
Marc Ilunga avatar
флаг tr
Marc Ilunga
@Lug322d, относительно 1) Обычно предполагается, что законный приемник имеет доступ к пэдам. Таким образом, расшифровка работает, применяя заполнение и отменяя заполнение; очевидно, еще один скрытый момент заключается в том, что никто не модифицировал этот зашифрованный текст. Что касается 2) Это хороший момент, я думаю, это также зависит от того, что вы считаете сообщением. Вы считаете "01" и "001" разными сообщениями?
0
Ответить
флаг in
Lug322d
Я вижу, это имеет смысл. И да, 01 может отличаться от 001. Тем не менее, вы можете создать эту группу, но это не будет конечным полем, которое, если бы оно было, упростило бы многие вещи.
0
Ответить
Marc Ilunga avatar
флаг tr
Marc Ilunga
Второй метод по-прежнему будет работать, даже если вы различаете 01 и 001. Вы просто работаете в большей группе.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.