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

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

флаг cn
Jack

Если у нас есть пространство сообщений 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 включительно.

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

1250
1 + 0
Рейтинг:21
poncho avatar Crypto
флаг my
poncho

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

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

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

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

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

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

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

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