Что такое криптография?

Видеолекцию "Что такое криптография?" профессора Дэна Боне (Стэнфордский Университет) в рамках курса по криптографии можно найти здесь:
https://class.coursera.org/crypto/lecture/2

Ниже приведен перевод титров этой лекции. Тэгом [слайд] я обозначаю содержание слайдов (здесь могут быть вопросы, формулы, картинки, пояснения и т.п.), которые профессор приводит по ходу лекции для наглядности материала



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

[слайд]
Ядро криптографии:
1. Создание безопасных ключей:
Алиса (знает, что разговаривает с Бобом) <================ > Боб (знает, что разговаривает с Алисой)
У Алисы и у Боба есть общий ключ К
Атакующий пытается подслушать разговор Алисы и Боба, не зная общего ключа

2. Безопасная связь
Есть общий ключ, идет безопасная передача сообщений (соблюдается конфиденциальность и целостность)
[слайд]

В начале курса мы уже говорили, что является ядром криптографии, если хотите ее краеугольным камнем. Это две составляющие. Первое - создание безопасных ключей, когда наша Алиса пытается поговорить с сервером Боба, скажем, и в конце протокола согласования, по сути, имеем общий ключ, который создается между двумя сторонами. Кроме того, Алиса точно знает, что она общается с сервером (а не с кем-либо) и намерена продолжить разговор. И Боб точно знает, что он действительно разговаривает с клиентом, скажем, имя которого - Алиса. И злоумышленник, конечно, не знает ничего о секретном ключе. Второе - как мы уже говорили, когда обе стороны договорились об общем ключе, между ними начинает работать безопасная передача сообщений. Но оказывается, что криптография может делать еще многое, многое, многое, многое другое. Я дам вам очень краткий обзор того, что еще можно с помощью нее сделать.

[слайд]
Но криптография может делать еще многое, многое, многое, многое другое
1. Цифровая подпись
2. Анонимное общение
[слайд]

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

Другой раздел криптографии имеет дело с анонимным общением. Ну, например, здесь у нас есть пользователь Алиса. Она хочет поговорить с сервером Бобом, но Алиса не хочет, чтобы сервер Боб знал, что это она. Есть множество причин, почему вы хотите общаться с сервером конфиденциально и поэтому вопрос заключается в том, как это сделать. И оказывается, есть концепция, называемая смешанная сеть (mixed network), которая действительно разрешает правильно шифровать и маршрутизировать трафик через несколько прокси-серверов, тем самым позволяя общаться Алисе с сервером так, что этот бедный сервер не имеет понятия, кто на самом деле с ним говорит. Таким образом, анонимная коммуникация - еще одно хорошее применение криптографии.

[слайд]
Один из видов анонимной коммуникации - анонимные цифровые деньги.
Вопросы:
- Как анонимно расплатиться “цифровыми деньгами”?
- Как избежать двойных расходов?
[слайд]

Теперь, когда у вас есть возможность анонимно общаться, вы можете спросить: “а у меня может быть анонимная цифровая наличность (деньги)?” Итак, еще раз, в физическом мире, у нас есть деньги и их анонимность означает, что как только я взял долларовую купюру из банка, я могу пойти и потратить долларовую купюру у продавца и нет такого способа, чтобы кто-то мог сказать, что это именно я потратил этот доллар у продавца (бумажные деньги имеют уникальный номер, по которому их можно отследить, но нельзя отследить их владельца). По сути, когда я использую деньги, я делаю это анонимно. Вопрос в том, можем ли мы сделать то же самое в цифровом мире? И тут проблема оказывается гораздо, гораздо сложнее. И еще вопрос, если у меня есть цифровая монета, или у нас здесь, например, есть Алиса, у нее есть один доллар цифровых монет, вопрос в том, сможет ли она на самом деле пойти и потратить этот доллар? У продавца, например, да так, что продавец понятия не имеет, кто на самом деле потратил деньги.

Есть еще одна причина, вызывающая сложность - в цифровом мире очень легко для Алисы взять цифровую монету и скопировать ее в другую монету. Так что, теперь вдруг вместо одной монеты стало две, и кто скажет, что Алиса не может пойти и потратить эти монеты у других продавцов. Если она действовала анонимно, то нет возможности сказать, кто на самом деле совершил это мошенничество. Кто же на самом деле потратил монету дважды у двух разных продавцов? И вот, кажется, возникает напряженность между безопасностью и неприкосновенностью частной жизни, потому что нет никакого способа узнать, кто совершает такое мошенничество. И оказывается, что это полностью выполнимо. И мы будем говорить позже об анонимных цифровых деньгах. Просто, чтобы дать вам подсказку, я скажу, что каждый раз, когда я провожу монету, я полностью анонимный. Но если я трачу монеты более одного раза, то тут же внезапно, моя личность будет полностью раскрыта и у меня могут быть юридические проблемы из-за двойного расходования одной и той же монеты. Далее на курсе мы более подробно рассмотрим как работают с анонимными цифровыми деньгами.

[слайд]
Протоколы
1. Проблема выборов
на слайде изображены несколько человечков, над каждым стоит 1 или 0
2. Закрытые аукционы
[слайд]

Другое применение криптографии связано с более абстрактными протоколами, но прежде, чем я озвучу общий результат, я приведу вам два примера. Первый пример связан с избирательной системой. Так вот, проблема выборов. Предположим. У нас есть две партии. Партия нуля и партия единиц. И избиратели голосуют за эти партии. Например, этот избиратель голосует за партию нуля, а этот за партию единиц (на слайде, профессор над человечками рисует 0 и 1, всего человечков - 5). И так далее. Таким образом, на этих выборах, партия нуля получила три голоса, а партия единиц - два голоса. Победителем на выборах, конечно, является партия нуля. Но в целом, победителем на выборах является та сторона, которая получает большинство голосов. Теперь, в чем заключается проблема выборов (голосования). Избирателям хотелось бы как-то посчитать большинство голосов, но сделать это таким образом, чтобы не обнаружились их индивидуальные голоса. Окей? Вопрос, как это сделать? А для этого, мы собираемся добавить избирательный центр, который поможет нам подсчитать большинство голосов, но сохранит сами голоса в тайне (профессор рисует избирательный центр, куда стекаются голоса). И каждый избиратель будет отправлять фонемы шифрования своих голосов в избирательный центр. И в конце выборов, избирательный центр может посчитать, кто стал победителем. Однако, кроме победителя, ничего не будет известно об отдельных голосах. Либо в противном случае, отдельные голоса сохраняются в тайне. Конечно, избирательный центр также проверяет, что, например, избиратель имеет право голоса, и избиратель проголосовал только один раз. Но весь остальной мир не должен ничего знать, кроме результата выборов. В нашем случае протокол включает в себя шесть сторон: пять избирателей и один избирательный центр. Эти стороны считаем между собой. И в конце вычислений становится известен результат выборов, но ничего не известно об отдельных голосах.

Аналогичная проблема возникает в контексте закрытых аукционов. В закрытом аукционе каждый участник предлагает свою ставку для принятия участия в торгах. А теперь предположим такой аукционный механизм - победитель аукциона, это тот, кто больше предложит заплатить. Но сумма, которую заплатит победитель на самом деле является второй по величине ставкой. Таким образом, он платит вторую наибольшую цену (Аукцион второй цены — закрытый аукцион, при котором победителем является участник с самой высокой ценой, но уплатить он должен «вторую цену», то есть цену своего ближайшего конкурента) Итак, стандартный механизм аукциона мы обозначили как победитель аукциона. А теперь то, что мы хотели бы сделать - дать возможность участникам выяснить, кто больше заплатит, и сколько он должен заплатить, но все остальные сведения об отдельных предложениях должны оставаться в тайне. Так, например, фактическая сумма ставки победителя должна оставаться тайной. Единственное, что доступно общественности - вторая по величине ставка и личность победителя. Итак, еще раз, как сделать так, чтобы аукцион работал озвученным способом. По сути, участники будут отправлять свои зашифрованных заявки в центр аукциона. Сам центр будет вычислять личность победителя, а на самом деле он будет также вычислять вторую наибольшую цену, но кроме этих двух значений больше ничего не показывать, имеется ввиду отдельные предложения.

[слайд]
Протоколы
1. Проблема выборов
на слайде изображены несколько человечков, где уже каждый - это некая переменная х1, х2 …
2. Закрытые аукционы

Цель: вычислить f(x1, x2, x3, x4)
“Теорема”: все, что можно сделать при помощи доверенных центров, также можно сделать и без них
3. Протокол конфиденциального вычисления
[слайд]

На самом деле перечисленные примеры - это пример гораздо более общей проблемой называемой протоколом конфиденциального вычисления (многостороннего вычисления) - secure multi-party computation. Позвольте мне объяснить, что такое протокол конфиденциального вычисления. Так вот, участники имеют свои тайные входные данные. В случае выборов, входными данными были бы голоса. В случае проведения аукциона, входными данными были бы ставки. И тогда надо произвести вычисление зависящее от входных данных каждого участника, т.е. надо вычислить какую-то функцию на основании входных данных. В случае выборов, функцию большинства. В случае аукциона, функцию нахождения “второй наибольшей цены”, наибольшее число для Х1 до Х4. И вопрос, как можно посчитать функцию так, чтобы стало известно ее значение, но входящие данные (отдельные голоса) были бы не доступны? Итак, позвольте мне, показать вам тупой, небезопасный способ сделать это. Что мы делаем - добавляем доверенную сторону. И этот доверенный центр собирает отдельные входящие данные. И он по-своему обещает сохранить эти входящие данные в секрете, так, что только он будет знать, что они есть. Затем, он публикует для всего мира значение функции. Таким образом, идея состоит в том, что теперь значение функции стало общедоступным, но ничего не известно об отдельных входящих данных. И да, конечно, доверенный центр подразумевает, что вы должны ему верить, и если по какой-то причине он не заслуживает доверия, то у вас серьезные проблемы. Таким образом, существует довольно распространенная “теорема” в [неразборчиво], и на самом деле это довольно удивительный факт. Она гласит, что любые вычисления, которые вы хотели бы сделать, любая функция F, которую вы хотели бы посчитать, если их можно вычислить с доверенным лицом, то вы можете также посчитать и без доверенного лица. В принципе, что мы собираемся сделать - мы собираемся избавиться от центра авторизации. Таким образом, участники на самом деле не собираются отправлять свои входящие данные в центр авторизации. И, фактически, центр авторизации в системе больше не нужен. Вместо этого, стороны должны сделать так, чтобы возможно было бы общение друг с другом с помощью некоторых протоколов. Таких, где в конце протокола значение функции становится известно всем. Остальные данные, кроме как значение функции, не должны быть обнаружены. Другими словами, входящие данные участников держатся в тайне. Но опять же нет никакого центра авторизации, для участников есть только один способ - говорить друг с другом таким образом, чтобы появился конечный результат. И это весьма общий результат, удивительно то, что это вообще выполнимо. В конце класса, мы на самом деле узнаем, как все это работает.

[слайд]
“Магическая” криптография
* Аутсорсинг частных вычислений
* Нулевое знание
Алиса знает множители числа N = p*q, а Боб знает только число N и он хочет проверить: а точно ли Алиса знает множители. Алиса доказывает Бобу, что она знает P и Q, не разглашая их конкретное значение.
[слайд]

А сейчас я расскажу о некоторые приложениях криптографии, которые иначе, как просто волшебными, я не могу классифицировать. Позвольте мне привести вам два примера. Итак, первый - называется аутсорсинг частных вычислений (privately outsourcing computation). Я на примере поиска Google проиллюстрирую. Итак, представьте, у Алисы есть поисковый запрос, на который она желает получить результат. Оказывается, что существует очень специфические схемы шифрования, где Алиса посылает свой шифрованный запрос в Google. А затем, поскольку в Google используется своя схема шифрования, Google на самом деле вычисляет зашифрованные значения, ничего не зная про открытый текст. Таким образом, Google сможет запустить свой алгоритм поиска, получив зашифрованный запрос, и возвратив зашифрованные результаты. Окей. Google отправляет зашифрованные результаты обратно Алисе. Алиса расшифровывает, и получает результаты. Но магия здесь в том, что Google увидел только зашифрованный запрос и ни более. Получается, что Google в результате не знает, что искала Алиса, но тем не менее Алиса на самом деле знала, знала точно, что именно она искала. Хорошо, а что это за такие волшебные схемы шифрования. Их ввели сравнительно недавно, всего лишь новая разработка около двух-трех лет назад, позволяющая вычислять незашифрованные данные, даже если мы не знаем, что внутри шифрования. Но, прежде чем бежать и думать о реализации этого механизма, я должен предупредить вас, что на самом деле на данный момент это все теория, в том смысле, чтобы запустить поиск Google по шифрованным данным, вероятно, потребуется миллиард лет. Но тем не менее, сам факт, что это выполнимо, уже удивителен, и это уже очень полезно для относительно простых расчетов. Фактически, мы увидим некоторые приложения позже.

Второе волшебное приложение криптографии, которое я хочу вам показать, называется нулевое знание. И в частности, я расскажу вам о так называемом доказательстве с нулевым разглашением. Вот оно (профессор показывает его на слайде). Так вот, что происходит, есть определенное число N, которое Алиса знает. И знает, что число N - произведение двух больших простых чисел. Итак, представим, два простых числа P и Q. Причем длина каждого из них будем думать, состоит, например, из 1000 цифр. И вы, наверное, знаете, что после умножения длина произведения легко уместится в 2000 цифр. Но если я просто дам вам только произведение. На самом деле разложение на множители (простые числа) не тривиальная задача. И в самом деле, мы собираемся воспользоваться тем знанием, что факторинг является труднореализуемым. [неразборчиво] системы рассмотрим во второй половине курса. Хорошо, у Алисы есть число N, и она также знает, его множители. Она передает число N Бобу. Он на самом деле не может факторизовать число N. Теперь, магия в доказательстве с нулевым разглашением в том, что Алиса может доказать Бобу, что она знает множители N. Да, вы можете дать это доказательство Бобу, Боб сможет проверить и убедиться, что Алиса знает эти множители, однако Боб о конкретных их значениях не узнает ничего. Ничего не узнает о множителях P и Q, и это доказуемо. Это и есть самое главное. Такие доказательства касаются не только разложения на множители N. На самом деле, практически зная ответ на любую головоломку и вы хотите доказать, что вы знаете ответ, вы сможете доказать, что это ваши знания. Если у вас есть решенный кроссворд. Ну, может, кроссворды не самый лучший пример. Но если у вас есть, например, головоломка судоку, и вы хотите доказать, что вы ее решили, вы сможете доказать этот факт так, что Боб ничего не узнает о решении, и в то же время Боб будет убежден, что у вас действительно есть решение этой головоломки. Окей. Вот такое волшебство.

[слайд]
Точная наука.
Три шага в криптографии:
1. Определить модель угрозы
2. Предложить конструкцию
3. Доказать, что злоумышленник не может сломать конструкцию в соответствии с настоящей моделью угрозы
[слайд]

И последнее, что я хочу сказать, что современная криптография является очень точной наукой. И в самом деле, каждое понятие, которое мы собираемся рассматривать следует трем правилам. Очень строгие правила, окей, и мы будем сталкиваться с ними снова и снова, поэтому я хочу объяснить, что они собой представляют. Первое, что мы собираемся делать, когда мы вводим новый примитив, например, цифровую подпись, мы собираемся определить - модель угрозы. То есть, что может сделать злоумышленник при атаке на цифровую подпись и какова его цель при создании подписи? Итак, мы собираемся точно определить, что это означает для подписи, например, то, что она должна быть неподдельна. Неподдельна. В качестве примера мы рассматриваем цифровую подпись. Для каждого другого примитива мы собираемся точно определить, какие угрозы существуют.

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

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


Пока не указано иное, содержимое этой страницы распространяется по лицензии Creative Commons Attribution-ShareAlike 3.0 License