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

Одноразовый блокнот, доказательство проблемы

флаг ms
IngIng

Мы знаем 2 открытых текста длины L и 2 зашифрованных текста длины L (мы не знаем, какой из них принадлежит какому), предполагая, что каждый заданный зашифрованный текст генерируется путем шифрования одного из заданных открытых текстов с помощью операции XOR (также известной как исключающее или) с одним и тем же ключ длины L (мы не знаем ключ). Вопрос заключается в том, чтобы доказать, что если ключ равномерно выбирается из пространства, определяемого длиной L, не существует программы, которая может выдать правильный ключ в качестве вывода с вероятностью более ½. Я только начал посещать занятия по криптографии, и у меня есть много вопросов, подобных этому. Я могу представить, почему вероятность равна ½, но не могу формально доказать это.

90
0 + 0
IngIng avatar
флаг ms
IngIng
Извините, я отредактировал вопрос. @kelalaka мы используем введение в современную криптографию Джонатана Каца и Иегуды Линделла, но это не вопрос из книги. Можете ли вы доказать это официально или можете дать мне какую-нибудь подсказку? Спасибо.
0
Ответить
Maarten Bodewes avatar
флаг in
Maarten Bodewes
@Maeher Хитрость в том, что вы узнаете только значения по отдельности, а не открытый текст / зашифрованный текст * пары *. Ингинг, так сколько возможных ключей? Перепишите $M_1\oplus C_2$!
0
Ответить
IngIng avatar
флаг ms
IngIng
@Maarten Bodewes, у нас есть 2 сообщения, которые зашифрованы одним и тем же ключом. $M1âC2 = M2âC1$, а также $M1âC1 = M2âC2$. У нас есть 2 равновозможных ключа. Я вижу, что вероятность равна $1/2$. Но как я могу официально написать это как ответ?
0
Ответить
Maarten Bodewes avatar
флаг in
Maarten Bodewes
НЕ уверен, я бы по крайней мере ввел $K'$ и указал, что вероятность того, что $P_1$ является открытым текстом $C_2$, точно такая же высокая, как и для $C_1$; из-за OTP нет информации, позволяющей различить их, так как $K$ является полностью случайным.
0
Ответить
Titanlord avatar
флаг tl
Titanlord
Знакомы ли вы с криптографическими экспериментами? Существует идеальный эксперимент по неразличимости, и для формального доказательства вы можете использовать его в качестве основы для вычисления вероятностей.
1
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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