Видеолекцию "Теория информации и одноразовый блокнот" профессора Дэна Боне (Стэнфордский Университет) в рамках курса по криптографии можно найти здесь:
https://class.coursera.org/crypto/lecture/4
Ниже приведен перевод титров этой лекции. Тэгом [слайд] я обозначаю содержание слайдов (здесь могут быть вопросы, формулы, картинки, пояснения и т.п.), которые профессор приводит по ходу лекции для наглядности материала.
Шифротекст (ciphertext) в русскоязычной литературе чаще всего именуют словом «криптограмма» (я буду использовать именно его в тексте перевода).
Открытый текст (plaintext; выглядит очень похоже на термин plain text, используемый для обозначения текстовых данных) широко применяется в криптографии и означает любые незашифрованные данные, в том числе и нетекстовые.
На данный момент, после обзора нескольких исторических шифров (каждый из которых уже взломан), мы собираемся поговорить о шифрах, которые намного лучше спроектированы. Но прежде чем мы займемся ими, я хочу дать более точное определение - что такое шифр.
Шифр – это пара «эффективных» алгоритмов (E,D), где
E: K * M -> C
D: K * C -> M
Итак, вспоминайте, шифр на самом деле состоит из двух алгоритмов. Алгоритма шифрования и расшифрования. Но в действительности, шифр задан тремя сущностями. Это множество всех возможных ключей, которое я обозначаю через символ K, иногда я буду называть его пространством ключей (key space) - это множество всех возможных ключей. Далее множество всех возможных сообщений M, и множество всех возможных криптограмм C. Окей, эта тройка сущностей в некотором смысле выступает средой, в которой определен шифр. И тогда шифром является пара эффективных алгоритмов E и D, где E - алгоритм шифрования, а D - алгоритм расшифрования. Конечно, входными параметрами E являются ключи и сообщения, а на выходе - криптограммы. А алгоритм расшифрования D берет ключи и криптограммы и выводит сообщения. Единственное требование к шифру состоит в том, что эти алгоритмы являются последовательными (consistent). Они удовлетворяют, так называемому свойству корректности (correctness property) для каждого сообщения в пространстве сообщений и для каждого ключа в пространстве ключей.
Для каждого $m \in M$ и $k \in K$: $D(k, E(k,m)) = m$ [1]
Т.е. если я зашифрую сообщение с ключом k, а затем расшифрую его с помощью того же ключа k, то я должен получить исходное сообщение, с которого начал. Таким образом, равенство [1] называется уравнением последовательности (consistency equation) и каждый шифр должен удовлетворять ему, чтобы шифр работал, в противном случае мы не сможем расшифровать. Еще на что я хотел бы обратить ваше внимание - я выделяю слово эффективный в кавычках. И причина, почему я так делаю - потому, что эффективный означает разные вещи для разных людей.
Если вы по натуре теоретик, то эффективность для вас – выполнение алгоритма за полиномиальное время. Например, алгоритмы E и D должны выполняться за полиномиальное время с заданными входными параметрами. Если же вы практик, то эффективность для вас – выполнение алгоритма за конкретный промежуток времени. Например, требование к алгоритму E – шифрование одного гигабайта данных за одну минуту. В любом случае, слово эффективность охватывает оба понятия, и для себя вы можете интерпретировать ее так, как вы хотите. Вот поэтому я взял слово «эффективный» в кавычки.
Еще одно замечание, которое я хочу сделать, касается алгоритма E. Он в большинстве случаев - рандомизированный алгоритм. Это означает, что для шифрования алгоритм E создает случайные биты для своей работы (алгоритм E использует при шифровании ключ – это равновероятная случайная величина), и он использует эти случайные биты в процессе шифрования входящих сообщений. С другой стороны, алгоритм расшифровки D всегда детерминированный. Другими словами, ключ и шифротекст всегда одно и то же (ключ и криптограмма уже известны). Они не зависят от любой случайности, которая используется в алгоритме. Итак, теперь, когда мы понимаем, что такое шифр, я хочу вам показать в своем роде первый пример безопасного шифра.
Он называется одноразовым блокнотом (one time pad - OTP), разработанный Гилбертом Вернамом в начале ХХ века. Прежде, чем я объясню, как работает шифр, давайте определимся с терминологией, которую только что рассмотрели.
$M = C = \{0,1\}^n$ $K = \{0,1\}^n$
Итак, пространство сообщений для одноразового блокнота (шифра Вернама) такое же, как пространство криптограмм – конечное множество всех бинарных строк (т.е. строки состоят из последовательности бит, последовательности 0 и 1) – {0,1}n. Пространство ключей в основном такое же, как и пространство сообщений – и снова это множество всех бинарных строк. Ключ в одноразовом блокноте – это просто длинная случайная строка, случайная последовательность бит. Настолько длинная, как само сообщение для шифрования.
Окей, теперь, когда мы определились с терминами, мы можем указать, как работает шифр, и это на самом деле очень просто. По существу криптограмма – это результат шифрования сообщения с определенным ключом, обычный XOR ключа и сообщения.
$c = E(k, m) = k\;XOR\;m$
$D(k,c) = k\;XOR\;c$
И сейчас, не спеша, я собираюсь это требование проверить, и затем я буду считать, что вы поняли этот момент. Что мы собираемся сделать: нам придется убедиться, что если я расшифровываю зашифрованный текст, который был зашифрован с использованием определенного ключа, то я в лучшем случае должен получить исходное сообщение m. Ну, что ж, давайте посмотрим. Если я шифрую k и m, это просто k XOR m. А расшифровывая k XOR m с помощью k? Получим k XOR k XOR m. И так, как я сказал, что XOR – это сложение по модулю два, то k XOR k = 0. И тогда k XOR k XOR m, это просто 0 XOR m. И получим исходное сообщение m.
Итак, эта проверка показывает, что одноразовый блокнот является шифром, но она ничего не говорит о безопасности шифра. Но мы поговорим о безопасности шифра через минуту. А сейчас, позвольте мне задать вам вопрос, для того, чтобы убедиться, что мы с вами на одной волне. Предположим, вы получили сообщение m, и знаете его криптограмму, полученную с помощью одноразового блокнота. Т.е. у вас есть сообщение и зашифрованный текст. Вопрос: с учетом этой пары m и c можно выяснить, какой ключ использовался при создании c из m?.. Итак, я надеюсь, что вы все поняли, что, зная сообщение и его шифротекст, очень легко восстановить ключ. Ключ – это просто m XOR c. Если этот момент не совсем ясен для вас, чуть позже вы увидите, почему это так.
Окей. Одноразовый блокнот с точки зрения производительности очень круто. Потому что все, что вы делаете, вы только XORите ключ с сообщением. И шифр работает супер, супер быстро с очень длинными сообщениями. К сожалению, его очень сложно использовать на практике. По сути, причина этого кроется в ключе, длина которого сопоставима с длиной сообщения. Так что, если Алиса с Бобом захотят безопасно обменяться данными, то Алисе необходимо послать ключ (обратите внимание такой же длины, что и сообщение) Бобу, прежде чем она отправит, хоть один бит сообщения. А значит, если у нее есть способ передать такой длинный секретный ключ Бобу, то она может таким же способом передавать и само сообщение (и зачем тогда нужно шифрование, если есть такой способ). Поэтому тот факт, что ключ должен быть сопоставим с сообщением по длине, создает проблему и делает одноразовый блокнот трудно применимым на практике. Хотя позже мы увидим, что идея одноразового блокнота на самом деле очень полезна.
Но сейчас я хочу сосредоточиться немного на безопасности. Возникают простые вопросы: почему одноразовый блокнот безопасен, почему он является хорошим шифром? Прежде чем ответить на этот вопрос, сначала мы должны ответить на следующий: с чего начинается безопасный шифр, что делает шифр безопасным? За ответом мы обратимся к теории информации. И первым человеком, серьезно изучавшим безопасность шифров, был очень известный - да вы его знаете - отец теории информации Клод Шеннон, который опубликовал свою знаменитую статью еще в 1949 году, где он анализирует безопасность одноразового блокнота.
Итак, идея определения Шенноном безопасности заключается в следующем. По существу, если всё, что вы видите - это криптограмма, то по ней вы абсолютно ничего не сможете узнать об открытом тексте (plaintext). Иными словами, криптограмма не должна раскрывать ни капельки информации об открытом тексте. Вам станет понятно, почему он - тот, кто придумал теорию информации – так решил, когда мы сформулируем, что же на самом деле означает информация об открытом тексте. Вот, что сделал Шеннон - я покажу вам его определение. Шеннон сказал, и это вы уже знаете, что у нас есть шифр (E, D), заданный тремя множествами (К, М, C), где К, М и C определяют пространство ключей, пространство сообщений и пространство криптограмм. И когда мы говорим, что шифр имеет абсолютную секретность (perfect secrecy), значит, выполняется условие:
Пусть у нас есть два сообщения m0 и m1 , принадлежащих пространству сообщений.
$m_0, m_1 \in М$
На эти сообщения накладывается единственное требование - они имеют одинаковую длину. Уже скоро вы поймете, почему это требование необходимо.
len(m0) = len(m1)
И каждая криптограмма принадлежит пространству криптограмм.
$c \in C$
А теперь я спрашиваю, какова вероятность шифрования m0 ключом k (шифрование m0 ключом k дает с, окей? – E(k, m0) = c) или какова вероятность шифрования m1 ключом k? И какая будет вероятность, если мы выбираем случайный ключ k? Ответ такой: вероятность шифрования m1 , получая с, точно такая же, как вероятность шифрования m0 , получая с.
$Pr[\;E(k, m_0) = c\;] = Pr[\;E(k, m_1) = c\;]$
И как я уже сказал, ключ k является распределенным на пространстве ключей K. Т.е. k равновероятно распределен на K. Таким образом, ключ k выбирается равновероятно из множества всех возможных ключей K (я часто буду писать k и стрелку с маленьким r над ним, чтобы обозначить тот факт, что r является случайной величиной, которая равновероятно выбирает k из множества всех возможных ключей K). Итак, главная часть определения Шеннона выглядит так:
Определение Шеннона:
$Pr[\;E(k, m_0) = c\;] = Pr[\;E(k, m_1) = c\;]$
где k выбирается равновероятно из множества всех возможных ключей K
А сейчас давайте подумаем немного о том, о чем на самом деле говорит это определение. Оно означает, что эти две вероятности одни и те же? Так вот. Допустим, я злоумышленник, и я перехватил определенную криптограмму c, тогда в действительности вероятность того, что криптограмма является результатом шифрования m0 точно такая же, как вероятность того, что криптограмма – результат шифрования m1. А потому, что эти вероятности равны. Итак, если всё, что у меня есть – это перехваченная криптограмма c, то я понятия не имею, является ли криптограмма результатом шифрования m0 или m1 , потому что – я повторюсь - вероятность получения c одинакова как при шифровании m0 , так и при шифровании m1.
Вот здесь, вы видите то же самое определение (профессор показывает следующий слайд, на котором определение Шеннона написано уже не от руки; а пустое место под ним профессор заполнит свойствами этого определения). И ниже я просто напишу свойства этого определения более точнее. Давайте запишем еще раз.
- данная криптограмма не скажет нам – это результат шифрования m0 или m1 (для всех m0 ,m1)
Определение Шеннона означает, что если у меня есть конкретная криптограмма, то я не могу сказать, откуда она взялась. Я не могу сказать, какое сообщение было зашифровано m0 или m1. И на самом деле, это свойство верно для всех сообщений. Для всех m0 и m1. Так что, я не могу сказать, что криптограмма c - это результат шифрования m0 или m1 , и я не могу сказать, что эта же криптограмма – не результат шифрования m2 или m3 , или m4 , или m5 , потому что все эти сообщения в равной степени могут быть открытым текстом для криптограммы c.
- самый умный противник ничего не узнает об открытом тексте на основании криптограммы
Значит, если вы зашифровали сообщения с помощью одноразового блокнота, то даже самый умный и могущественный противник не сможет ничего узнать об открытом тексте на основании криптограммы, нисколечко.
- атака с использованием только шифрованного текста (ciphertext-only attack) не единственная!! (но и другие типы атак могут оказаться возможными)
Получается, что атака с использованием только шифрованного текста невозможна для шифра с абсолютной секретностью. Но такая атака на шифр, на самом деле, не является единственной возможной атакой. И действительно, другие атаки могут оказаться возможными.
Окей. Теперь, когда мы понимаем, что значит абсолютная секретность, ответим на вопрос о том, можем ли мы построить шифр с абсолютной секретностью? И получается, что за примером далеко ходить не надо, шифр одноразового блокнота имеет абсолютную секретность. Поэтому я хочу доказать вам этот факт. Давайте приступим. Итак, мы должны интерпретировать следующее (смотрим определение Шеннона), чему равна вероятность $Pr[\;E(k, m) = c\;]$? На самом деле, не так уж трудно заметить, что для каждого сообщения, и для каждой криптограммы вероятность того, что E(k,m)=c равна вероятности выбора нашего случайного ключа k (количество значений k, где k принадлежит K и выполняется условие E(k,m)=c) к общему числу ключей (|K|).
Для каждого m,c$Pr[\;E(k, m) = c\;] = \frac{количество\;значений\;k,\;где\;k \in K\;и\;E(k,m)=c}{|K|}$ [2]
Теперь. Если я шифрую сообщение ключом k, то я получаю с. Затем, я подсчитываю (буквально) количество таких ключей k, и делю на общее количество ключей. Правильно? Т.е. это означает, что, если я выберу случайный ключ k, то зашифровав им, сообщение m, получу с. Правильно. И вероятность будет равна числу таких ключей k, деленное на общее число ключей. А теперь предположим, что у нас есть шифр E(k,m) = c, используемый для всех сообщений и криптограмм, с выбранным ключом k, и я подсчитываю, сколько раз встречается k. Другими словами, я считаю количество ключей k, отображающих m в c. Пусть это количество будет постоянным значением (константой). Допустим – два, три, или десять, или пятнадцать - абсолютная константа. Если это так, то, по определению [2] для всех m0 и m1 и для всех с, эта вероятность должна быть одной и той же, потому что знаменатель один и тот же, числитель один и тот же, как константы, и поэтому вероятность всегда одинакова для всех m и с. Вывод, если это свойство истинно, то шифр должен иметь, шифр имеет абсолютную секретность.
Для каждого m,c: если (количество значений k, где k принадлежит K и выполняется условие E(k,m)=c) – константа, то шифр имеет абсолютную секретность.
Итак, давайте посмотрим, что вышесказанное означает для одноразового блокнота. Секунду, у меня вопрос, если у меня есть сообщение m и криптограмма c, то, сколько существует ключей в шифре Вернама, для отображения m в c? Т.е., другими словами, сколько существует таких ключей, что m XOR k = с? Надеюсь, вы все ответили – один ключ. А почему это так? В одноразовом блокноте шифрование с ключом k работает так: m XOR k = с. Отсюда можно просто найти k = m XOR c. Да, я просто XORю известное мне сообщение m и известную мне криптограмму c. Окей? И получается, что в одноразовом блокноте, на самом деле, количество ключей k – всего лишь один. И это справедливо для всех сообщений и криптограмм.
[слайд]
Лемма: Одноразовый блокнот обладает абсолютной секретностью
Доказательство:
Для каждого m,c: E(k,m)=c
1) k XOR m = c, k = m XOR c
2) (количество значений k, где k принадлежит K и выполняется условие E(k,m)=c) = 1 (ключ)
Значит, одноразовый блокнот обладает абсолютной секретностью
[/слайд]
И снова повторюсь, что одноразовый блокнот имеет абсолютную секретность. И доказательство этого очень и очень простое (см. слайд). Самое смешное здесь то, что, хотя эта лемма выглядит простой, следствием доказательства оказывается очень сильное утверждение: на шифр Вернама нельзя осуществить атаку с использованием только шифрованного текста (ciphertext-only attack). Таким образом, рассмотренные ранее: шифр замены, или шифр Виженера, или роторные машины - все их можно было взломать, используя атаку с использованием только шифрованного текста. А для одноразового блокнота – и мы это только что доказали – такой взлом просто невозможен. Имея на руках только криптограмму, вы просто ничего не узнаете об открытом тексте. Однако, это еще не конец истории. Я хочу сказать, что мы сделали? Я имею в виду то, что мы на данный момент закончили обучение, потому что получили такой способ шифрования, при котором злоумышленник не сможет восстановить что-нибудь из нашего сообщения. Но, на самом деле, как мы увидим позже, есть и другие атаки. И действительно, одноразовый блокнот не такой уж безопасный шифр. Да, существуют другие атаки, и мы увидим это в ближайшее время. Окей.
[слайд] Плохие новости…
Теорема: абсолютная секретность – это когда |K| >= |M|
Т.е. абсолютная секретность – это когда длина ключа >= длина сообщения
Но это условие трудно реализуемое на практике.
[/слайд]
Я еще раз подчеркну тот факт, что одноразовый блокнот обладает абсолютной секретностью, но не является безопасным шифром на практике. Окей. Но, как мы сказали ранее, проблема с одноразовым блокнотом в том, что секретный ключ очень длинный. Если у вас есть способ передать секретный ключ на другую сторону, то таким же способом можно передать и само сообщение на другую сторону, а в этом случае нам вообще не нужно применять шифрование. Понятно? А т.к. проблема для одноразового блокнота в длинных ключах, то возникает очевидный вопрос: существуют ли другие шифры, обладающие абсолютной секретностью и, при этом, имеющие короткие ключи? Так вот, плохая новость заключается в том, что Шеннон доказав теорему, что одноразовый блокнот имеет абсолютную секретность, доказал еще одну теорему, которая говорит, что если шифр имеет абсолютную секретность, количество ключей в шифре должно быть не менее числа сообщений, обрабатываемых шифром. Итак, это означает, что если у меня есть шифр, обладающий абсолютной секретностью, то должно выполняться обязательное требование - количество ключей, или, вернее, длина моего ключа должна быть больше, чем длина сообщения. Поскольку одноразовый блокнот удовлетворяет этому равенством, то одноразовый блокнот является оптимальным шифром, обладающий абсолютной секретностью, понятно? В общем, этот факт свидетельствует о том, что одноразовый блокнот - интересный шифр. Но на практике он трудно реализуемый. Опять же, из-за этих самых длинных ключей.
И хотя само понятие абсолютная секретность - довольно интересное, получается так, что мы не выяснили: что же делает реальные шифры безопасными. И в следующей лекции мы посмотрим как же этого добиться в реальной жизни. Хотя - повторюсь - идея одноразового блокнота весьма хорошая.
