Information theoretic security and the one time pad (19 min)

C определить пространство ключей, сообщение пространства и пространства текста шифруют. И когда мы говорим

Cypher тексты, бывает так, что если я смотрю на этот номер, число k, k и k,

D алгоритм дешифрации. E принимает на вход сообщения. И на выходе дает шифрованный

M XOR C. хорошо? Так что, говорит, что, за один раз коврик, на самом деле,

XOR m, которая является просто как вы знаете k XOR k нулевой и нулевой XOR ничего

XOR операция над сообщением и ключом. Просто K XOR M. Посмотрим на легкий пример.

Z соотвествует C. Так что это на самом деле не так сложно увидеть, что для каждого сообщения и

cyphertext пространство. Ладно? Таким образом, для каждой пары метод сообщений и для каждого шифра

k и m это просто k XOR m по определению. Что такое расшифровки k XOR

m использование k? Это просто k исключающего или (XOR m k). И так я сказал что XOR

Абсолютная Констанция. Если это так, то по определению, для всех n0 и n1 и

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

Вы получаете это сообщение и зашифрованный текст. Мой вопрос к вам это, учитывая

Вы, он очень простое доказательство, так что давайте идти вперед и смотреть на него и просто сделать это. Поэтому мы

Давайте посмотрим, почему это так. Для один время площадку, если у нас что, шифрования

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

Другими словами, я делаю сумму по модулю 2 бит за битом.

Единственным требованием является что бы эти алгоритмы были совместимыми. Они удовлетворяют,

Если выбрать случайный ключ, ключ карты m c. право. Поэтому это в основном число

Запомните что XOR, это "плюс в кружочке". XOR означает сумма

Зачастую это алгоритм с случайной величиной. Это означает что во время процесса шифрования

Здесь у нас есть определение, заявил снова.
И я просто хочу написать эти свойства

И в самом деле, другие нападения, возможно, другие нападения, может быть возможным.

И каждого ключа в пространстве ключей, я ожидаю, что если я шифрую

Идеальный тайны, количество ключей в шифр должен быть по крайней мере количество

Идеальный тайны, оказались еще теорема, которая говорит, что на самом деле если имеет шифр

Идея за один раз что pad является довольно хорошо.
И мы будем видеть в следующей лекции,

Используйте точный же метод также общаться сообщение на другой стороне,

Итого я получаю один, один, ноль, один, один, один, ноль. Это зашифрованный текст. Как я его расшифрую?

Каждый cyphertext вероятность того что шифрование n под ключ k

Ладно. Теперь, когда мы понимаем, что идеальный тайны, средства, вопрос, мы можем

Лемма. Теперь самое смешное, что, хотя эта Лемма настолько прост в

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

Но перед тем как мы сделаем это, Я хотел бы сначала дать более формальное определение

Ну, так что плохая новость заключается в Шеннон, после доказать, что имеет одноразовый Блокнот

Он назывется one time pad и был спроектирован Вернамом в начале

От. Я не могу сказать, если это, если сообщение зашифровано. N или n ноль

Почему это хороший шифруют? Затем чтобы ответить на этот вопрос, первое, что мы должны

Поэтому я надеюсь, что все вы понимаете, что на самом деле, учитывая сообщение

Создание c от м?

Так что означает, что эти два вероятности одинаковы? Хорошо что он

Таким образом 1-время pad является действительно здорово с точки зрения производительности все, что вы делаете

Таким образом, что e, k, m равен c. Другими словами я глядя на количество ключей

Таким образом, что, как хорошо. Если я зашифровать. И с k я получаю c. Так что я буквально подсчитать число

Теперь, когда мы увидели несколько примеров плохих шифров из истории,

Узнайте, абсолютно ничего не обычного текста. Иными словами текст cypher

Униформа в ключевых пространстве. Это единый в k k. И я часто буду писать k стрелка

Хотя мы увидим, что идея одноразовый блокнот на самом деле очень полезно

Числитель-это то же самое, это просто как постоянным, и поэтому вероятность

Шеннон и он опубликовал известный документ обратно в 1949 году, где он анализирует

Шифр подстановки, или vigenere шифр или роликовых машин, всех тех, кто

Эти сообщения является, что они имеют одинаковую длину. Да так, что мы только, мы увидим, почему

Это довольно интересно, в основном говорит, что он не сказать нам

Это карта m c., предположим, что это число случается быть константой. Так сказать

Это количество за один раз площадку. Так sec-, таким образом, вопрос к вам, если я

Это один раз, колодки были очень длинные ключи и так очевидный вопрос там

Это просто м. хорошо, так это фактически показывает, что одноразовый pad является на самом деле шифруют,

Это требование является необходимым в минуту. И для каждого cyphertext в

Я буду, я буду писать его медленно первой. Так что Шеннон сказал вы знаете, предположим, что мы

Я не могу сказать, если он пришел из n два или n три или N 4 или N 5 потому что все

алгоритм E может выполнить работу по шифрованию одного гигабайта данных за одну минуту.

алгоритм дешифрации всегда терминальный. Другими словами

атаковать только один раз [неразборчиво] не шифруют текст. Так, в отличие от

безопасности. Таким образом очевидные вопросы, вы знаете, почему одноразовый Блокнот безопасной?

безопасность одноразовый Блокнот. Это идея Шэннона определение безопасности

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

безопасный? Ладно так что исследования, безопасность шифров, мы должны говорить немного

бит, состоящих из нулей и единиц. Пространство ключей равно пространству сообщений

в one time pad шифре это просто случайная, большая строка, случайная последовательность бит.

в действительности является вероятность того, что текст шифруют шифрования n ноль

в самом деле Докажите, что это доказывает довольно мощное заявление снова. Это в основном говорит, для

в этом случае вам не нужно шифруют начать с. Ладно? Так что проблема снова

вам вопрос, просто чтобы убедиться, что мы все в синхронизации. Предположим, вы получаете

вероятность того, что, что равно C, вероятность того что наш случайный выбор ключа

вероятность шифрования n 1 и c-это точно так же, как

вероятность шифрования n ноль и получать c. И так же, как я сказал, где

вероятность. Так что теперь предположим, что у нас шифруют такие что для всех сообщений и все

вообще то, шифр определяется тройкой. Итак, набор всех возможных ключей

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

все N 0 и n из них. Так что не только я не могу сказать if'c' пришли из n ноль или один, N

все были перехвачены, я не знаю ли текст шифруют пришли от нуля m

всегда то же самое для всех n и c. И если это свойство имеет значение true, то cypher

всех конечных бинарных строк. Это означает все последовательности

гифр, я хочу показать первый пример безопасного шифра

говорит, что в один раз колодки, совершенный секретности. Идеальный тайны и что

говорит, что если я злоумышленник и я перехват конкретного шифруют текст c, затем

даже отправив первый бит сообщения, она должна передать ключ Бобу, как

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

для formulize, официально Объясните, что делает информацию о обычный текст на самом деле

для всех c эта вероятность должен быть же потому что знаменатель является то же самое,

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

до тех пор, как сообщение, она также может использовать этот же механизм также передать

доказывает, что есть нет, это не шифруют текста только нападение на шифр,

другие cyphers, которые имеет идеальный тайны и, возможно, намного короче ключи?

думайте о нем как о полиномиальном времени, иначе думайте о нем как

есть сообщение в зашифрованный текст, сколько ключей колодки один раз там [неразборчиво]

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

за полиномиальное время от размера сообщения на входе. Если вам больше нравится практика

завершает доказательство этой [неразборчиво] очень, очень простой. Очень, очень простой

зашифрованный текст это очень легко восстановить то, что это ключ. В частности, ключ

и мы будем видеть, что чуть-чуть позже. Но сейчас я хочу сосредоточиться немного на

из двух алгоритмов. Это алгоритм шифрования и алгоритм дешифрации. Но

из-за эти длинные ключи. И поэтому это понятие идеальной тайны, даже хотя

или текст шифруют пришли из m один, потому что снова вероятность получения c

имеет идеальный тайны, ладно? Поэтому в основном, это показывает, что это

имеет идеальный тайны. Теперь шифруют нападения на самом деле не только возможных атак.

иметь идеальный тайны. Затем обязательно количество ключей, или скорее длина моего

имея ключ и шифрованный текст мы всегда получим одинаковые сообщения на выходе. Он не зависит от

иначе его невозможно будет расшифровать. Одна вещь которую я должен упомянуть это то что Я

интересное понятие. Один раз, когда pad является интересным шифра. Но, на самом деле, в

интерпретировать его в вашей голове так как вам нравится. Я просто буду продолжать использовать

использовать их для шифрования исходного сообщения. С другой стороны

используя , все что я делаю это вычисляю XOR этих двух строк

используя конкретный ключ. То есть все что я делаю это XOR операцию ключа и шифрованного текста. Все что нам осталось

их равной вероятностью производить шифр text'c'. Так что это действительно значит

как вероятно это, если мы выбираем случайный ключ?
Как вероятно это, когда мы зашифровать n

как сделать это в практической системы.

как шифр работает и на практике это очень просто. И так, шифрованный текст,

карта, это сообщение заканчивается, так что [неразборчиво] C? Итак другими словами, сколько ключей

ключ 1011001. Когда мы вычислим шифрованное сообщение

ключ распределения, находится над распределением на ключ. Таким образом ключевым является

ключ, должен быть больше, чем длина сообщения. Так в самом деле, с одной

ключа, карта n c, деленное на общее количество ключей. Это ее

ключей и я разделить общее количество ключей. Право? Вот что значит, что

коврик для шифрования этого сообщения, используя один раз и сообщение m. Таким образом, все

количество ключей, в K, показывает расширенного управления Ключами, равен C. Это просто и это

колодки, что это просто невозможно. Учитывая cyphertext, вы просто узнать ничего не

которое в свою очередь просто все возможные бинарные строки. То есть ключ

которые я обозначу буквой K, и иногда буду называть пространством ключей,

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

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

кто изобрел теория информации прийти с этого понятия, потому что у вас есть

любых случайных величин использованных алгоритмом E. И так, тепер когда мы лучше понимаем что такое

медленно после чего буду предполагать что все это для вас просто

метод. Поэтому, возможно, мы сделали с курсом. Но на самом деле, как мы увидим, там

множество возможных шифров. Так вот эта тройка в каком то смысле определяет

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

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

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

надежно так что вы знаете, Элис хочет отправить сообщение конец Боб, прежде чем она начинает

настолько exo кольцо ключ в сообщении это супер, супер быстро. Шифр для

не означает, что один раз, когда pad является безопасной шифруют для использования. Ладно. Но как мы уже сказали

но он ничего не говорит о безопасности Сайпер. И мы будем говорить

ноль, мы получаем C. Что вероятность должно быть таким же, как когда мы шифрования N1. Ладно, так что

нужно своего рода интерпретировать что это значит, что такое эта вероятность что E K M

о безопасности шифра в минуту. Во-первых позвольте мне быстро задать

о конкретных временных ограничениях. Другой коментарий который я хочу сделать касается алгоритма E.

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

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

обычный текст. Однако как мы можем видеть, это просто не конец истории. Я

один и в самом деле, это свойство имеет значение true для всех сообщений. Для всех этих n равно нулю для

означает разные вещи для разных людей. Если вы более склонны к

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

означает, что мы сделали? Я имею в виду, в основном, мы сделали с курс сейчас, потому что мы

определение. И давайте думать немного о то, что это определение фактически говорит.

определили пространство на котором определен шифр мы можем определить

от K M под k равно C. Но в основном Ну, по определению, что

ответ, является то, что безопасный шифр начать с? Что такое, что делает шифра

пара m и c, вы можете на самом деле выяснить, одноразовый путь ключ, который был использован в

пара эввективных алгоритмов E и D. E алгоритм шифрации;

по модулю 2. Пусть есть сообщение 0110111 и есть

по определению. Все это, в основном количество ключей. Кей, поручить Кей.

по существу, пока сообщение. Так что если Алиса и Боб хотят общаться

подразумевает, что K XOR M равен C. Но это также просто говорит что k равным

пока это сообщение. Ну, если она имеет способ передать безопасный ключ Бобу это

понять, почему что в дело, а чуть позже в разговор, в лекции. Хорошо хорошо

построить шифров, которые на самом деле есть идеальный тайны? И получается, что мы не

практические cyphers будет безопасным.
И мы будем видеть, но, как мы уже говорили,

предполагаю, что можно сделать то же самое. То есть мы дешифруем шифрованный текст

придется искать очень далеко, один раз шаблон факт имеет идеальный тайны. Так что я

проблема с один раз pad является то, что секретный ключ очень долго. Если у вас

проблематичным и делает одноразовый блокнот очень трудно использовать на практике.

проводит для всех сообщений в зашифрованный текст. И так, опять же, то, что мы говорили раньше, он просто

проводит следующие состояния. Это так происходит для каждые два сообщения m нуль и M1 в

просто М с XOR. Тогда мы увидим, если не сразу очевидно, для вас мы будем

пространства в сообщение. За каждые два сообщения единственное требование я собираюсь поставить на

пространство в котором определен шифр. Итого шифр это

противника. Можно узнать ничего о обычный текст, узнает ничего о равнина

равно пространству шифрованных текстов, которое состоит из

равномерно пробы в пространство ключей k. хорошо, это основная часть Шеннона

реальность, это на самом деле довольно трудно использовать.
Это трудно использовать на практике, опять же,

с XOR. M Да, я просто x по обе стороны от m и я получить, что должно быть равно k

с немного r выше для обозначения тот факт, что k — это случайная величина что

само сообщение. Поэтому тот факт, что ключ, пока сообщение довольно

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

следующее. В принципе если все, что вы можете видеть это шифруют текст, то вы должны

слово эффективный и ставить на него кавычки. Как я сказал, если вы теоретик

сложения по модулю двух, Добавление ассоциативной, так что это так же, как (k XOR k)

случается, два, три, или десять или пятнадцать. Он просто ЛПГ, случается,

снова более точно. Так что давайте писать это снова. Так что [неразборчиво] определение

сообщение М. Так что же здесь происходит? Ну, давайте посмотрим. Так что, если я смотрю на шифрования

сообщение с ключом K и потом дешифрую его используя тот же ключ K,

сообщения, алгоритм E будет генерировать случайные биты для себя, и будет

сообщения, которые может обработать шифр. Ладно, так в частности, это означает, если я

способ. Общение секретный ключ через другой стороны. Вы можете также

среднее. Ладно, так что это то, что сделал Шеннон и поэтому lemme показать вам определение Шэннона,

ставлю слово эффективный в кавычки. Причиной тому является то, что эффективность

столь же вероятно шифруется ли m ноль или один m шифруется. Так

строго. Это очень известный, вы знаете, отец теории информации, Клод

там такие, которые M XOR K равен C?
Поэтому я надеюсь, что вы ответили все на один. И

текст, он лучше быть так, что, если я спросить, какова вероятность того, что,

текст. Алгоритм дешифрации берет ключи и шифрованный текст. На выходе дает сообщение.

текст. Из текста шифруют. Так сказать это еще один способ, в основном то, что это

теории, эффективность означает исполнение за поиномиальное время. То есть алгоритмы E и D должны выполняться

точно так же, как вероятность того, что incryption n 1. Потому что

трудно использовать на практике. Причина, по которой трудно использовать это ключи

у шифруют E D, которая определяется через тройной K M и c как и раньше. Так км и

увидите, что вскоре. Ладно? Я вновь подчеркиваю тот факт, что он имеет идеальный тайны делает

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

хотите доказать вам это Китая в первые результаты, и я хочу доказать этот факт

что извините текста шифруют мы сказать, что шифр совершенный тайны если

что называется, свойство корректности. Итак, для каждого сообщения в пространстве сообщений.

что такое шифр. Запомните, шифр состоит

что, если шифрования сообщений с один раз колодки тогда в действительности наиболее

шифрование и расшифровка очень длинные сообщения. К сожалению, это очень

шифрования n ноль с K, woops.
N ноль шифрования с k дает C, ладно? Так

эти вероятности равны. Так что если у меня есть, все у меня есть шифруют текст c это

это множество всех возможных ключей. Так же есть множество всех возможных сообщений и

это проверить что он удовлетворяет свойству консистентности. И я сделаю это

эффективный означает выполняется за определенный временной промежуток. Например

я получу на выходе сообщение с которого я начал. Это уравнение называется

являются другие нападения. И в самом деле, один раз pad является на самом деле не такой