Рейтинг:2

Будет ли OTP по-прежнему совершенно безопасным, если мы ограничим пространство для сообщений и ключей?

флаг cn

Если у нас есть пространство сообщений M {0,1,2,3,4,5,6}, а также пространство ключей K = {0,1,2,3,4,5,6} (генератор выбрал универсальные ключи k)

Мы определяем наше шифрование как XOR их побитового представления на K и M, используя 4 бита {0000, 0001, 0010, 0011, 0100, 0101, 0110}

Это одноразовый блокнот, верно? Потому что мы выполняем операцию XOR и используем ключ одинаковой длины.

Однако здесь сообщение и пространство ключей представлены с использованием 4 бит; он также ограничен значениями в диапазоне от 0000 до 0110 включительно.

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

Рейтинг:21
флаг my

Нарушает ли это каким-либо образом полную секретность?

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

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

В частности, если мы видим в зашифрованном тексте значение 0111, мы можем сделать вывод, что соответствующее значение открытого текста не 0000; в конце концов, для этого ключевое значение было бы 0111, и мы знаем, что это не так. Это значения, которые злоумышленник может вывести, не являются сообщением, и это является нарушением полной секретности.

Теперь, если у вас есть сообщение и ключ, состоящие из значений от 0 до 6, очевидно, что нужно изменить групповую операцию на «сложение по модулю 7»; то есть, чтобы зашифровать, вы добавляете сообщение к ключу, а затем, если это значение равно 7 или больше, вычитаете 7 - это дает вам зашифрованный текст. И, чтобы расшифровать, вы делаете «вычитание по модулю 7»; вы вычитаете ключ из зашифрованного текста и, если это значение отрицательное, добавляете 7. Это вполне допустимая групповая операция, и поскольку все значения ключа возможны (и предположительно равновероятны), она может удовлетворять требованиям совершенной секретности.

Jack avatar
флаг cn
Привет, почему если значение зашифрованного текста 0111 мы знаем, что открытый текст не будет 0000? Это потому, что ключ и сообщение не могут быть одним и тем же? Однако, если мы не ограничим пространство ключей тем же набором значений, что и пространство сообщений, как указано выше, будет ли это разрешено? Я сбит с толку.
Chris Peikert avatar
флаг in
Зашифрованный текст 0111 не может иметь лежащий в основе открытый текст 0000, потому что 0111 не является разрешенным ключом в системе, которую вы представили; открытый текст 0000 мог дать зашифрованный текст 0111 только в том случае, если ключ был 0111.
SAI Peregrinus avatar
флаг si
Я также хотел бы отметить, что наивная операция по модулю с использованием условного вычитания, как описано, может привести к утечке данных по побочному каналу. Математическая «совершенная секретность» не нарушается, но реальная секретность может быть нарушена!
poncho avatar
флаг my
@SAIPeregrinus: да; Я написал «очевидный» метод, потому что ожидал, что OP будет иметь относительно минимальный математический фон (и мои извинения, если я ошибаюсь) - реальная реализация хотела бы использовать лучшие (но более сложные для объяснения) методы.
Nobody avatar
флаг in
@SAIPeregrinus Какой сторонний канал? Мощность/время? Да, конечно, но это так далеко от вопроса, что я сначала был довольно сбит с толку вашим комментарием.
флаг jp
Итак, просто чтобы было ясно: то, что делает эту схему небезопасной, на самом деле *не* *уменьшение* в ключевом пространстве, как задано в вопросе, а *распределение* ключей. Правильный?
poncho avatar
флаг my
@ JörgWMittag: это правильно; изменение распределения таким образом, чтобы все возможные значения ключей, но некоторые из них имели разные вероятности, привело бы к утечке некоторой вероятностной информации об открытом тексте.
fgrieu avatar
флаг ng
Для полной секретности с этим сообщением и пространством ключей, что-то близкое к исходному OTP: $C\gets(K-M)\bmod7$ [C = (K+7-M)%7` в C] с расшифровкой $M\gets( K-C)\bmod7$ [M = (K+7-M)%7` в C]. Это имеет то преимущество, что шифрование и дешифрование такие же, как и в традиционном OTP.
Jack avatar
флаг cn
Я немного смущен тем, что означает равномерно случайное k, когда говорят, что k = {0000, 0001, 0010, 0011, 0100, 0101, 0110}, если оно равномерно случайно, разве это не должно быть нормально? @пончо
Jack avatar
флаг cn
@ChrisPeikert, но как злоумышленник узнает, что ключ не разрешен в указанном ключевом пространстве? я сбит с толку
Chris Peikert avatar
флаг in
@Jack Мы следуем принципу Керкхоффа и предполагаем, что противник знает все алгоритмы и распределения (ключа и сообщения), но не сам выбранный ключ. Это фактически отражено в формальном определении совершенной секретности.
Jack avatar
флаг cn
@ChrisPeikert Как пример с 0111 действителен? Когда мы говорим, что и k, и m равны {0000, 0001, 0010, 0011, 0100, 0101, 0110}. у вас никогда не может быть сообщения 0111
Chris Peikert avatar
флаг in
@Jack Настоящий ключ и сообщение могут быть 0110 и 0001 (соответственно), что делает зашифрованный текст 0111. Когда перехватчик видит этот зашифрованный текст, он может сделать вывод, что сообщение не было 0000. Однако до того, как зашифрованный текст был отправлен, 0000 был возможен сообщение. Вместе это является нарушением полной секретности.

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

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