What is cryptography? (15 min)

Субтитры далеко не идеальны, но в целом, о чем идет речь, понять можно.

Пока мы не начали рассматривать технические стороны, я хочу провести краткий

обзор криптографии как науки и рассказать о ее направлениях. Итак,

суть криптографии, конечно же, состоит в защите коммуникаций, что, по существу,

состоит из двух частей. Первая - это создание ключа шифрования и того

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

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

в одном из сообщений в конце этого протокола по договоренности передается общий ключ,

назовем его общим ключом К, и помимо этого, фактически

только Алиса будет знать, что она сказла Бобу, и только Боб знает, что он сказал Алисе.

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

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

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

Мы поговорим о схемах шифрования, позволяющих расшарить ключ таким способом,

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

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

Другими словами, эти схемы шифрования дают обоюдную конфиденциальность и

интеграцию. Но криптография - это гороздо-гораздо больше, чем эти две

вещи. И я хочу привести несколько примеров этого. Итак, в качестве примера я

хочу привести то, что называется цифровой подписью. Итак, цифровая подпись,

в своей основе, - это аналог росписи. Росписи,

которую вы ставите на документах, в основном, вы подписываете

документы одной и той же росписью. Вы так же ставите одну и ту же роспись

на всех документах, которые вы хотите подписать. В цифровом мире, это не возможно,

поскольку атакующий только что получивший один, подписанный мной документ, сможет

скопипастить мою роспись на другой документ и подстроить так,

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

и ту же цифровую подпись для всех документов, которые я подписываю. Мы поговорим о том,

как генерировать цифровые подписи во второй части курса. Это

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

я дам вам совет, способ работы цифровых подписей основан на ассоциации

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

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

потому что подпись одного документа не будет соответствовать значению функции

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

позднее мы рассмотрим полностью, как создавать цифровые подписи и тогда мы

докажем, что такие конструкции безопасны. Другое применение криптографии, о котором я

хочу упомянуть - это анонимные сообщения. Итак, представим пользователя

Алису, которая хочет обратиться к некому чат-серверу Бобу. И положим, что она хочет поговорить о

медицинских условиях и хочет сделать это анонимно, так что

чат-сервер не может узнать кто она. Прекрасно, существует стандартный метод

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 дать доказательство что любой злоумышленник, который может атаковать

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

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

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

Все в порядке. Однако эти три шага на самом деле очень важны. В случае подписей

мы определяем, что означает для подпись тягучесть, а после мы

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

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

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

тогда вы увидите, как это на самом деле происходит. Ладно, на этом у меня

все. В следующем сегменте мы поговорим немного об истории

криптографии.