-
Пока мы не начали рассматривать технические стороны, я хочу провести краткий
-
обзор криптографии как науки и рассказать о ее направлениях. Итак,
-
суть криптографии, конечно же, состоит в защите коммуникаций, что, по существу,
-
состоит из двух частей. Первая - это создание ключа шифрования и того
-
как передать этот ключ в процессе общения. Мы уже говорили, что
-
созданный ключей шифрования передается в ходе общения между Алисой и Бобом
-
в одном из сообщений в конце этого протокола по договоренности передается общий ключ,
-
назовем его общим ключом К, и помимо этого, фактически
-
только Алиса будет знать, что она сказла Бобу, и только Боб знает, что он сказал Алисе.
-
Но бедный злоумышленник, прослушивающий их сообщения, не будет знать
-
что является общим ключом. И чуть позже мы узнаем, как это сделать. Итак, теперь у них есть
-
общий ключ, и они будут использовать его для безопасного обмена сообщениями.
-
Мы поговорим о схемах шифрования, позволяющих расшарить ключ таким способом,
-
чтобы атакующий не смог понять, что за сообщения отправляются. И,
-
кроме того, атакующий не смог даже вмешаться в обмен сообщениями, чтобы ни быть обнаруженным.
-
Другими словами, эти схемы шифрования дают обоюдную конфиденциальность и
-
интеграцию. Но криптография - это гороздо-гораздо больше, чем эти две
-
вещи. И я хочу привести несколько примеров этого. Итак, в качестве примера я
-
хочу привести то, что называется цифровой подписью. Итак, цифровая подпись,
-
в своей основе, - это аналог росписи. Росписи,
-
которую вы ставите на документах, в основном, вы подписываете
-
документы одной и той же росписью. Вы так же ставите одну и ту же роспись
-
на всех документах, которые вы хотите подписать. В цифровом мире, это не возможно,
-
поскольку атакующий только что получивший один, подписанный мной документ, сможет
-
скопипастить мою роспись на другой документ и подстроить так,
-
будто я сам его подписал. Итак, просто невозможно использовать одну
-
и ту же цифровую подпись для всех документов, которые я подписываю. Мы поговорим о том,
-
как генерировать цифровые подписи во второй части курса. Это
-
вполне интересные примитивы и мы уже знаем, как они работают. Так что
-
я дам вам совет, способ работы цифровых подписей основан на ассоциации
-
цифровой подписи с функцией, которая делает подписываемый контент верифицированным. Так что у атакующего
-
пытающегося скопировать вашу подпись с одного документа на другой, ничего не получится
-
потому что подпись одного документа не будет соответствовать значению функции
-
от данных в другом документе, и в результате подпись не будет подтверждена. И как я сказал
-
позднее мы рассмотрим полностью, как создавать цифровые подписи и тогда мы
-
докажем, что такие конструкции безопасны. Другое применение криптографии, о котором я
-
хочу упомянуть - это анонимные сообщения. Итак, представим пользователя
-
Алису, которая хочет обратиться к некому чат-серверу Бобу. И положим, что она хочет поговорить о
-
медицинских условиях и хочет сделать это анонимно, так что
-
чат-сервер не может узнать кто она. Прекрасно, существует стандартный метод
-
mixnet, который позволяет Алисе общаться в публичном интернет с бобом посредством
-
последовательности прокси, так что в конце общения Боб не имеет представления, с кем он
-
только что разговаривал. Способ Микснетов основан на том, что Алиса шлёт свои сообщения
-
Бобу через последовательность прокси-серверов. Эти сообщения шифруются
-
и дешифруются соответственно так, что Боб не знает, с кем он разговаривал и прокси-сервера
-
сами не знают, что Алиса разговаривает с Бобом, или фактически, кто
-
с кем разговаривает вообще. Один интересный момент об этом анонимном
-
канале общения состоит в том, что он двунаправленный. Иными словами, хотя
-
Боб не знает, скем он разговаривает, он тем не менее может отвечать Алисе и
-
Алиса будет получать эти сообщения. Имея анонимные сообщения, мы можем построить
-
другие механизмы защиты. И я хочу дать вам пример, который называется анонимные
-
электронные платежи. Помним, что в физическом мире, если у меня есть физический
-
доллар, я могу пойти в книжный магазин и купить книгу и торговец не будет знать
-
кто я. Вопрос в том, можем ли мы сделать то же самое в цифровом
-
мире. В цифровом мире, в частност, Алиса может иметь электронный доллар,
-
элетронную долларовую монету. И она может хотеть заплатить элетронный доллар неким онлайн-
-
торговцам, допустим в некий онлайновый книжный магазин. Теперь мы бы хотели сделать это так,
-
чтобы когда Алиса тратит свою монету в магазине, магазин не знал бы
-
кем является Алиса. Т.е. мы обеспечиваем такую же анонимность, когда получаем платёж наличными.
-
Теперь пролема в том, что в электронном мире Алиса может взять монету, которая у неё
-
есть, эту долларовую монету, и перед тем, как потратить её, она может её копировать.
-
И затем, вдруг, вместо наличия просто долларовой монеты, теперь,
-
вдруг, у неё есть три долларовых монеты и они все, разумеется, одинаковые, и
-
ничто ей не мешает взять эти копии и
-
потратить их у других торговцев. И вопрос в том, как мы обеспечиваем анонимность
-
электронных денег? Но в то же время, препятствуя Алисе дважды потратить
-
долларовую монету у разных продавцов. В некотором смысле возникает противоречие между
-
анонимностью и безопасностью, потому что если есть анонимные деньги
-
ничто не помешает Алисе потратить дважды монету и так как монета
-
анонимная, мы не имеем возможности сказать, кто совершил это мошенничество. И вопрос в том
-
как нам решить это противоречие. И оказывается, это вполне выполнимо. И мы поговорим об
-
анонимных электронных деньгах позже. В качестве намёка, скажу что,
-
то как мы это обычно делаем, убедившись, что если Алиса тратит монету
-
только раз, никто не знает кто она, но если она потратит еще раз,
-
внезапно, её личность становится полностью известной и её могут постигнуть
-
все виды юридических проблем. Таким образом анонимная цифровая наличность будет работать
-
на высоком уровне, и вдальнейшем в ходе занятий мы увидим, как реализовать это.
-
Еще одно применение криптографии связано с более абстрактными протоколами, но
-
прежде чем подвести общий итог, я хочу привести вам два примера. Итак:
-
первый пример связан с избирательными системами. Так вот - избирательная проблема.
-
Предположим... у нас есть две партии: "партия-0" и "партия-1". И избиратели голосуют за них.
-
Например, этот избиратель проголосовал за "партию-0", а этот - за "паритю-1"...
-
И так далее. В этих выборах "партия-0" набрала три голоса, а "партия-1" - два голоса.
-
Таким образом победитель выборов конечно же "партия-0".
-
Но в общем случае, победителем выборов является партия, набравшая большинство голосов.
-
Итак, избирательная проблема в следующем. Избиратели хотели бы как-то посчитать
-
большинство голосов, но сделать это так, чтобы ничего
-
не было известно о каждом отдельном голосе. Хорошо? Итак вопрос: как это сделать?
-
И чтобы сделать это, мы представим "избирательный центр", который поможет нам
-
вычислить большинство, сохранив тайну голосования. И единственное что каждая из партий
-
должна сделать, это отправить забавные шифры своих голосов "за" в избирательный
-
центр, таким образом в конце выборов, "избирательный центр" сможет
-
посчитать и определить победителя выборов, при этом
-
больше ничего не будет известо о каждом отдельном голосе. информация об индивидуальных
-
голосах остаётся полностью закрытой. Естественно, "избирательный центр" также
-
должен проверить что, например, данный избиратель имеет право голосовать и что избиратьель
-
проголосовал только раз. Но кроме этой информации "избирательный центр"
-
и весь остальной мир ничего не будут знать о голосе избирателя -
-
только результат выборов. Вот это пример протокола, который включает в себя шесть сторон.
-
В данном случае, есть пять избирателей в одном "избирательном центре". Эти стороны
-
вычисляются между собой. В конце выислений результат выборов известен,
-
но ничего кроме этого не известно об индивидуальных голосах.
-
Подобная проблема поднимается в контексте частных аукционов. Так в частном
-
аукционе у каждого участника есть своя ставка, означающая, что он хочет участвовать в торгах. А теперь предположим, что
-
используемый механизм аукциона, называемый аукционом Викри, где
-
по определению аукциона Викри, победителем является предложивший наивысшую цену.
-
Но сумма, которую платит победитель является на самом деле второй по величине ставкой. Таким образом, он платит
-
вторую по величине ставку. Итак, это стандартный механизм аукциона называется
-
аукционом Викри. И теперь чтобы мы хотели бы сделать - это просто позволить участникам
-
посчитать, чтобы чтобы выяснить, кто предложит самую высокую цену , и сколько он должен заплатить,
-
но кроме этого, чтобы все другие сведения об отдельных ставках
-
остались в тайне. Так, например, фактическая сумма ставки, которая предложит самую высокую цену
-
должна оставаться тайной. Единственное, что должно стать известным является вторая по величине ставка
-
и личность предложившего самую высокую цену. Итак, еще раз, то что мы сделаем -
-
это введем "аукционый центр", и таким же образом , по сути, каждый
-
будет отправлять свои зашифрованные ставки в "аукционный центр", который
-
выислит личность победителя и по сути также вычислит вторую по величине ставку,
-
но кроме этих двух величин ничего не будет известно
-
об отдельно взятых ставках. Это на самом деле пример гораздо более общей проблемы
-
называемой безопасными многосторонними вычислениями. Позвольте пояснить, что же такое безопасные многосторонние вычисления
-
Итак, здесь, по сути абстрактно, у участников есть сами по себе секретные входные данные.
-
В случае с выборами - это голоса "за".
-
В случае с аукционом секретными входными данными являются тайные ставки.
-
И всё что нужно сделать - это вычислить нектороую зависимость (функцию) от входных данных.
-
В случае с выборами - искомой функцией является "большинство", в случае с аукционом -
-
функцией является второе по величине число среди чисел от x1 до x4.
-
И вопрос в том, как добиться того, чтобы значение функции
-
стало известно, но ничего кроме этого не было известно об отдельно взятом голосе.
-
Позвольте, я покажу вариант неправильной небезопасной реальзации этого. Вначале представим доверенную сторону.
-
И потом, это доверенный оргн просто собирает отдельные входные данные.
-
И он, своего рода, "обещает" держать отдельные входные данные в тайне , так что только он будет знать их.
-
И в итоге он выдаёт значение функции миру.
-
Таким образом, идея такова, что значение функции стали достоянием общественности и
-
ничего не стало известным об отдельных голосах. Но и конечно есть
-
доверенный орган которому вы доверяете, но если по каким-то причинам он окажется не заслуживающим доверия, тогда у вас проблема.
-
Это является центральной теоремой в криптографии и
-
на самом деле это довольно удивительный факт. В ней говорится, что любое вычисление
-
которое вы хотели бы сделать, любая функция F, которую вы хотите вычислить, и которую можете вычислить
-
с доверенным органом - вы можете также сделать без него.
-
Позвольте мне на высоком уровне объяснить, что это значит. В принципе, то, что мы собираемся сделать, это
-
мы собираемся избавиться от органа. Таким образом, стороны фактически не будут отправлять
-
их входные данные в орган и фактически больше не будет органа в системе.
-
Вместо этого что будут делать стороны - это
-
общаться друг с другом используя некий протокол. Таким образом, что в конце протокола
-
вдруг значение функции становится известно всем. И больше
-
ничего кроме значения функции не становится известным. Другими словами,
-
индивидуальные входные данные остаются в тайне. Но в при этом нет органа,
-
а только способ передачи от одного к другому таким образом чтобы стал известен итоговый результат - выходные данные.
-
Этот достаточно общий результат - это своего рода удивительный факт, что это вообще выполнимо.
-
Это на самом деле так и ближе к концу занятий мы увидим как это сделать.
-
Eсть некоторые приложения криптографии, которые я не могу
-
классифицировать любым другим способом , кроме как сказать, что они являются чисто магическое. Позвольте мне дать вам
-
два примера этого. Итак:
первый - это то, что называется Частными облачными вычислениями.
-
Поэтому я дам вам пример поиска Google просто чтобы проиллюстрировать.
-
Итак, представьте, у Алисы есть поисковый запрос который она хочет выполнить. Оказывается что
-
есть особенные схемы шифрования, такие что Алиса может отправить свой
-
зашифрованый запрос в Google. И после этого, в зависимости от схемы шифрования
-
Googe может выполнить вычисления на зашифрованных значениях не зная, что в тексте.
-
Google vj;tn запустить собственные алгоритмы массового поиска на зашифрованом запросе
-
и получить зашифрованные результаты. Хорошо. Google вернёт
-
зашифрованные результаты Алисе. Алиса расшифрует их и получит результат.
-
но магия тут в том. что всё что увидел Google это просто шифрованый запро и ничего больше.
-
И так, в итоге Google не знает что Алиса искала,
-
тем не менее, Алиса узнала точно, что она хотела узнать.
-
Хорошо. Это магическое свойство схем шифрования.
-
Но если честно, только новые разработки, двух - трех-летней
-
давности позволяют вычислять шифрованные данные даже в тех случаях когда мы точно не знаем
-
что внутри шифровки. Теперь, прежде чем бежать и думать о применении этого,
-
Ддлжен вас предупредить, что это в настоящий момент только теория, в том смысле
-
что запуск Google-поиск с шифрованными даннми, вероятно, займет миллиард лет.
-
Но тем не менее сам факт того, что это выполнимо уже довольно
-
удивительно, и уже весьма полезно для относительно простых вычислений.
-
Несомненно, мы увидим нексколько таких приложений позже. Еще одно волшебное приложение
-
которое я хотел бы продемонстрировать это так называемое "нулевое знание". И в частности, я расскажу
-
вам о том, что называется "доказательство с нулевым разглашением". Итак, вот...
-
...что происходит, если есть определенное число N, которое знает, Алиса.
-
И способ как число N было построено - как произведение двух больших простых чисел. Итак, представьте
-
Здесь мы имеем два простых чисел, P и Q. Каждый, что вы можете думать его как 1000 цифр.
-
И вы , наверное, знаете , что умножение двух 1000- значных числа это довольно легко. Но если...
-
я просто дам вам их произведение, выяснить их разложение на простые числа
-
на самом деле довольно сложно. И в самом деле , мы собираемся воспользоваться тем, что розложение на простые числа сложнО
-
для построения криптосистем с открытым ключом во второй половине курса.
-
Итак, Алиса, случается, есть это число N, и она также знает, факторизация
-
N. Теперь Боб просто имеет номер N. Он не знает на самом деле факторизации.
-
Магические факт о нулевой знаний доказательство знаний, сейчас, что
-
Алиса может оказаться Боб, что она знает факторизации N. Да, вы можете фактически
-
Дайте этому доказательство Боб, что Боб можно проверить и стать убежден в том, что Алиса
-
знает факторизации N, однако Боб узнает ничего на всех. О факторах, P
-
и Q и это доказуемо. Боб абсолютно узнает ничего вообще про
-
факторы, P и Q. И заявление на самом деле это очень, очень общие. Это
-
не только о доказав факторизации N. В самом деле почти любой головоломки, что вы
-
хотите доказать, что вы знаете ответ, вы можете доказать, что это ваши знания. Так что если
-
у вас есть кроссворд, что вы решили. Ну, может быть это не кроссворды
-
Лучший пример. Но если у вас есть как головоломки Судоку, например, что вы хотите
-
чтобы доказать, что вы решили, вы можете доказать это Боб таким образом, что бы узнать, Боб
-
ничего вообще о решении, и пока Боб будет убежден что вы действительно
-
есть решение этой головоломки. Все в порядке. Так что те являются своего рода магический приложениями.
-
И поэтому Последнее, что я хочу сказать, что Современная криптография является очень
-
строгие науки. И в самом деле, каждый концепция, мы 're gonna описать является собираешься
-
Выполните три очень строгий, ладно, и мы 're gonna видеть эти три шага
-
снова и снова и снова так я хочу объяснить, какие они есть. Так первая вещь
-
Мы ты собираешься делать, когда мы представляем нового примитива, как цифровая подпись
-
Мы 're gonna указать точно модель угрозы. То есть, что может
-
Злоумышленник ду атаковать цифровой подписи и какова его цель в ковка
-
подписи? ОК, поэтому мы будем точно определять, что это означает для подписи
-
например, что она неподдельна.
Неподдельна. Ладно, я даю цифровую
-
подпись в качестве примера. Для каждый примитив, мы описываем, мы будем
-
точно определите, какова модель угрозы.
Затем мы 're gonna предлагать строительство
-
и затем мы 're gonna дать доказательство что любой злоумышленник, который может атаковать
-
строительство в рамках этой модели угрозы. Что злоумышленник может также использоваться для решения некоторых
-
базовым сложная проблема. И, как следствие, если проблема действительно трудно, что
-
на самом деле доказывает, что не злоумышленник может нарушить строительства при модели угрозы.
-
Все в порядке. Однако эти три шага на самом деле очень важны. В случае подписей
-
мы определяем, что означает для подпись тягучесть, а после мы
-
даем некую конструкцию, и затем, к примеру, мы говорим, что любой, кто может сломать нашу
-
конструкцию, которую может затем применить для, скажем, ряда факторов, которые могут оказаться
-
сложной проблемой. Итак, мы будем следовать следующим трем действиям во всем, и
-
тогда вы увидите, как это на самом деле происходит. Ладно, на этом у меня
-
все. В следующем сегменте мы поговорим немного об истории
-
криптографии.