What is cryptography? (15 min)

Перш ніж ми почнемо з технічним матеріалом, я хочу дати вам

короткий огляд того, що криптографія і про різних областях криптографії. Таким

чином, основою криптографії, звичайно, є безпека зв'язку, яка по суті

складається з двох частин. Перший ключ безпеки створенний і те, як

ми спілкуємося безпечно тільки у нас є ключ. Ми вже говорили, що ключ

безпеки створення по суті зводиться до Аліси і Боба відправки повідомлень один

з одним так, що в кінці цього протоколу, є ключ, що обидва

вони домовляться, загальний ключ К, а крім того, за рамки просто ключ , насправді

Аліса буде знати, що вона говорить Боб і Боб буде знати, що він розмовляє з

Еліс. Але бідний зловмисник, який слухає цю розмову не знає, що

ключ є. І ми побачимо, як це зробити пізніше в курсі. Тепер, як тільки вони

Тепер, як тільки у них є спільний ключ, вони хочуть безпечно обмінюватися повідомленнями за допомогою цього ключа, і

ми поговоримо про схеми шифрування, які дозволяють їм зробити це таким чином, що

зловмисник не може з'ясувати, які повідомлення були відправлені туди і назад. І

Крім того зловмисник не може навіть спотворювати цього руху без виявлення.

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

цілісність. Але криптографії робить багато, багато, набагато більше, ніж просто цих двох

речі. І я хочу дати вам декілька прикладів. Таким чином перший приклад я

щоб дати вам є те, що називається цифровим підписом. Так цифрового підпису

в основному, це аналогові підпис у фізичному світі. У фізичному

світ, пам'ятаєте, коли ви підписуєте документ, по суті, ви пишете ваш підпис на

документа а підпис є завжди те ж саме. Ви завжди писати те ж

підпис на всі документи, який потрібно підписати. У цифровому світі це не можу

Можливо, робота, тому що якщо зловмисник просто отримали один підписаного документа з мене, він

можна вирізати і вставити мій підпис до інших документів, які я не могла

хотіли підписування. І так, це просто не можливо в цифровий світ який мій

підпис є однаковими для всіх документів, які я хочу, щоб підписати. Так що ми будемо говорити

про те, як побудувати цифрових підписів у другій половині курсу. Він має

дійсно дуже цікавим примітивно і ми побачимо, як саме це зробити. Просто до

дати вам підказку, як цифрові підписи працюємо в основному за рахунок на

цифровий підпис за допомогою функції вмісту, який підписується. Так що зловмисник хто

намагається копіювати мій підпис з одного документа до іншого не буде досягти успіху

тому що підпис. На новий документ не буде належної функції на

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

Ми будемо бачити, як саме, щоб побудувати цифрові підписи пізніше, і тоді ми будемо

Доведіть, що ці конструкції безпечним.
Інший додаток криптографії що я

хотілося б відзначити, є анонімні зв'язку. Так, тут, уявіть собі користувача

Alice хоче поговорити з деякими чат-сервера, Боб. І, можливо, вона хоче, щоб говорити про

медичний стан, і тому вона хоче зробити це анонімно, так що чату

сервер насправді не знає, хто вона.
Ну, є стандартним методом, називається на

mixnet, що дозволяє спілкуватися за допомогою Інтернету з Бобом через Alice

послідовність проксі таку, яка в кінці зв'язку Боб поняття не має, хто він

просто говорив для. Чином, mixnets робота в основному як Alice відправляє її повідомлень

Щоб Боб через послідовність проксі, отримати зашифровані ці повідомлення та

дешифрувати відповідним чином, тому що Боб не знав, хто він розмовляв з і проксі

себе навіть не знаю, що Alice розмовляє з Боб, або, що фактично хто

більш загально говорити кому. Одна цікава річ про це анонімно

канал зв'язку, що є, це письма. Іншими словами, навіть

Хоча Боб не має уявлення хто він розмовляє, він все ще може реагувати на Alice і

Alice отримають ці повідомлення. Як тільки ми анонімні зв'язку, ми можемо побудувати

інші механізми конфіденційності. І я хочу, щоб дати вам один приклад, який називається Анонім

електронні гроші. Пам'ятайте, що у фізичному світі, якщо у мене є фізична

долар, я можу ходити в книжковий магазин і купити книгу і купець б не мають

ідея, хто я. Питання в тому, чи ми можемо зробити точно таку ж річ у цифрових

світ. У цифровому світі в основному, Alice може мати цифровий долар,

цифрові долар монета. І вона, можливо, захочете витратити цей цифровий долар на деяких онлайн

торговці, можливо деякі онлайновий книжковий магазин.
Тепер що ми хотіли б зробити це зробити так

що коли Alice витрачає її монета в книжковому магазині, книжковий магазин б не мають

ідея, хто Alice. Так що ми надаємо ж анонімності, що ми отримуємо від фізичного готівкою.

Тепер проблема полягає в тому, що у цифровому світі Alice можна вважати монети, що вона

було, це один долар монета, і перед тим, як вона провела її, вона може фактично зробити його копії.

А потім раптом замість просто один долар монета тепер все

раптом вона має три долар монети і вони все-таки звичайно, і

Ніщо не заважає їй беручи ці реплік монета долар і

проводив його в інші купців. І так питання, як робити ми надаємо Анонім

цифрова готівка? Але в той же час, також запобігти Alice подвійний витрати на

Долар монета в різних купців. У певному сенсі є парадокс тут де

анонімність є конфлікт з безпеки, тому що якщо ми маємо анонімні готівкою, що є

нічого, щоб запобігти Alice двічі витрачати монети і тому, що монети

анонімний ми не маємо змоги говорити, хто вчинив цей шахрайства. І тому питання

Це, як ми вирішимо цю напругу. І виявляється, це цілком здійснимо. І

Ми будемо говорити про анонімний цифрова готівка пізніше. Просто щоб дати вам підказку, я буду

сказати, що як ми робимо це, в основному переконавшись, що якщо Alice витрачає монети

один раз, то ніхто не знає хто вона є, але якщо вона витрачає монети більш ніж один раз, всі

є раптове, її особистість цілком піддається і потім вона може бути підлягають

різного роду юридичних проблем. І так, це як анонімний цифрова готівка б

працювати на високому рівні, і ми побачимо, як реалізувати це пізніше в курсі.

Інший додаток криптографії має справу з більш абстрактним протоколи, але

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

Перший приклад має відношення до виборчої системи. Так ось це проблема виборів.

Припустимо, що... ми дві партії, партії нуль і одна сторона. І виборці голосують за ці

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

партії, один. І так далі. Так у цих виборах, партія нуль отримав три голоси і два учасника

отримав два голоси. Так переможцем виборів, звичайно, є партія нуль. Але

більш загально, переможцем виборів є сторона, яка отримує більшість

голосів. Тепер голосування проблема полягає в наступному. Виборці якось хотів

обчислювати більшість голосів, але зробити це таким чином такі, що нічого іншого

відомо про своїх індивідуальних голосів.
Добре? Тому виникає питання: як це зробити?

І щоб зробити це, ми збираємося представити виборів центр, який допоможе нам

обчислимо, більшість, але зберегти голосів в іншому таємницю. І те, що сторони

буде робити це вони будуть кожен відправити смішні шифрування свої голоси вибори

Центр таким чином, що в кінці вибори, вибори центр, здатен

обчислення та виведення переможця виборів. Однак, крім переможець

виборів нічого відомо про окремих голосів. Окремі

голосів в іншому випадку залишатися повністю приватним.
Звичайно, вибори центр є також

буде переконатися, що цей виборців наприклад дозволено голосувати і виборець має

тільки один раз голосувала. Але, крім цієї інформації виборів центр і на

інший світ дізнався, нічого іншого, про що виборців голосування іншим, ніж у

результат виборів. Так, це приклад протоколу, який включає в себе шість

сторонами. У цьому випадку є п'ять виборців в одних виборів центр. Ці

сторони обчислювати між собою. І в кінці обчислення, результат

відомо, вибори, але нічого відомо про окремих входи. Зараз

Аналогічна проблема з'являється в контексті приватних аукціонів. Таким чином, у приватних

аукціон, кожен учасник має свою власну ставку, що він хоче взяти участь в торгах. І тепер припустимо, що

Аукціон механізм, що використовується є те, що називається аукціон Vickrey де на

визначення Vickrey аукціоні, що переможець торгах. Але в

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

Другий найвищі ставки. Добре, так що це Аукціон стандартний механізм називається на

Vickrey аукціон. І тепер те, що ми хотіли б зробити це в основному дозволити учасникам

обчислимо, щоб з'ясувати, який запропонував найвищу ціну і скільки він повинен

платити, але Крім цього, інформація про окремі ставки

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

слід зберігати в таємниці. Єдине, що має стати готелю є другим найвищий

Купівля та ідентичність торгах. Знову тепер як ми будемо робити

що є, ми будемо ввести центром аукціон і подібно всім, по суті,

буде відправити їх зашифровані ставки аукціон центру. Аукціон центр буде

обчислювати ідентичності переможця і насправді він буде обчислити другий

найвищі ставки, але ці два значення, ніж інші, нічого відомо про на

окремі ставки. Тепер це дійсно приклад набагато більш загальної проблеми

називається безпечне багатопартійної обчислень. Дозвольте мені пояснити, що безпечне multi-party

обчислення є про. Так от в основному abstractly, учасники мають таємницю

входи до себе. Так, у випадку з виборами, буде входи до

голосів. У разі аукціон входи б секретний ставки. А потім

те, що вони хотіли б зробити це обчислимо якусь функцію їх входів.

Знову ж таки у разі проведення виборів, функції у більшості. У випадку з

аукціон, функція трапляється бути другий найвищої, найбільший номер серед x один

Щоб x чотири. І питання є, як вони можуть це зробити, таке, що вартість на

Функція виявляється, але нічого відомо про окремих голосів? Так

Дозвольте мені показати вам роду німий, небезпечно спосіб зробити це. Що ми зробити, це ввести в

надійних партії. І потім, це надійні, авторитет в основному збирає окремі

входи. Та це цікаве обіцяє зберігати окремі входи таємницю, так що тільки його

буде знати, що вони є. І потім, він публікує значення функції, щоб

у світі. Так, ідея в тому, тепер, що значення функції став громадськості, але

нічого відомо про окремих входи. Але, звичайно, ви отримали

Це надійні органу, що ви отримали довіряти і якщо з якоїсь причини, не

надійним, то у вас є проблеми. І так, там дуже центральний теорема

криптографічного і це дійсно так дивно факт. Це говорить, що будь-яке

обчислення ви хотіли зробити, будь-яка функція f ви хотіли обчислимо, що ви можете

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

Дозвольте мені на високому рівні пояснити, що це означає. В основному, є те, що ми збираємося робити,

Ми збираємося позбутися від адміністрації. Так сторін насправді не збираються надіслати

їх входів адміністрацією. І справді, там більше не буде бути в

повноважень у системі. Замість цього, що сторони збираєтеся робити, є вони збираються

говорити один з одним за допомогою деяких протоколу.
Така, що наприкінці всі протокол

раптом стає відомо значення функції, всім. Та ще

нічого, крім значення функції розкривається. Іншими словами, на

окремими входами є все ще тримається в секреті.
Але знову ж таки, немає не повноважень, є

просто спосіб для них говорити один з одним, така, що розкривається кінцевого виводу. Так

Це досить загальний результат, це роду дивно те, що на всіх

здійснимо. І справді це і в кінці класу ми побачимо насправді як

зробити це сталося. Зараз є деякі додатки криптографії, що я не можу

класифікувати будь-які інші іншим чином, ніж говорити, що вони є чисто магічне. Дозвольте мені навести

Ви два приклади що. Таким по-перше, те, що називається приватною аутсорсинг

обчислення. Так що я дам вам приклад пошуку в Google, просто для ілюстрації на

точки. Так собі уявити Alice має пошукового запиту, що вона хоче, щоб видавати. Виявляється, що

є дуже спеціальні шифрування схем, така, що Alice можна надіслати шифрування з

її запиту до Google. А потім, через власності схема шифрування

Google насправді можна обчислювати зашифровані значення не знаючи, що в

Звичайний текстів є. Так що Google насправді можна запустити свій алгоритм масові пошуку на

зашифровані запиту та відновлення зашифрований результатів. Добре. Google надсилає на

зашифровані результати назад до Alice. Alice буде розшифровувати, і тоді вона буде отримати на

Результати. Магія тут, але всі Google побачив, був просто encryptions, її запитів

і більше нічого. І так, Google в результаті поняття не має що Alice просто

шукали і тим не менш Alice дійсно дізнався точно, що вона

хотіли дізнатися. Добре, так, ці магічні роду схем шифрування. Вони

порівняно недавно, це тільки новий розвиток від близько двох або трьох років

тому, що дозволяє нам для обчислення на зашифрованих даних, навіть якщо ми не знаємо

що таке всередині шифрування. Тепер перш ніж ви поспішайте і думати про впровадження

Це, я повинен попередити вас, що це дійсно на даний момент тільки теоретичні, в

тому сенсі, що працює в Google пошуку на шифрування даних, ймовірно, буде потрібно на

мільярдів років. Але тим не менше, просто тому, що це здійснимо вже дійсно

дивно і вже досить корисні для відносно прості міркування. Таким чином, у

факт, ми побачимо деякі додатки це пізніше. Магічні застосунку я

хочете, щоб показати, що ви є те, що називається нульовий знань. І, в зокрема, я вам скажу

Ви про те, що називається нульові знання доказ знань. Так ось...

що відбувається, існує певне число N, який знає Alice. І як

число n був побудований як продукт двох великих простих чисел. Так що, уявіть собі

Тут ми маємо два простих чисел, P і Q. Кожного, ви можете думати про нього, як як 1000 цифр.

І ви, напевно, знаєте, що множення двох 1000-значні номери є досить легко. Але якщо

Я просто дати вам свій продукт, з'ясувати їх факторизації в простих чисел

насправді досить складно. І, по суті, ми збираємося використовувати те, що факторингу

важко побудувати громадськості ключових криптосистемах у другій половині курсу.

Гаразд, так Alice сталося мати цього числа N, і вона також знає, що факторизації з

Н. Тепер Боб просто має номер н. Він насправді не знає, що факторизації.

Тепер магічне про нульові знання доказ знань, це факт

Alice можна довести до Боб, що вона знає, що факторизації н. Так, ви можете фактично

Дайте цьому доказ до Боб, що Боб можна перевірити і стати переконаний, що Alice

знає факторизації N, проте Боб дізнається, нічого не на всіх. Про фактори p

і q і це доказовою. Боб абсолютно дізнається, нічого взагалі про на

фактори p і Q. І оператор насправді є дуже, дуже загальні. Це

не тільки про довівши факторизації н. Справді, майже будь-який головоломка, що ви

хочете, щоб довести, що ви знаєте відповідь, ви можете довести це ваші знання. Так що якщо

у вас кросворд, яке ви вирішили. Ну, може бути кросворди не є на

Кращий приклад. Але якщо ви, як судоку головоломки, наприклад, що ви хочете

довести, що ви вже вирішена, ви можете довести це Боб таким чином, що Боб б дізнатися

нічого про рішення, і ще Боб б переконатися що ви дійсно зробити

є рішення цієї головоломки. Добре. Тому ті роду магічні додатків.

І так що останнє, що я хочу сказати, що сучасна криптографія на дуже

науковим. І справді, кожен концепції, що ми збираємося описати збирається

Виконайте три кроки дуже строгий, добре, і ми будемо бачити ці три кроки

знову і знову і знову, так, я хочу, щоб пояснити, що вони є. Тому перше, що

Ми збираємося робити, коли ми ввести нові примітивно, як цифровий підпис

Ми збираємося вказати, що загроза модель саме. Тобто, що можна на

Зловмисник чи напасти на цифровий підпис і що його мета в кування

підписи? Добре, так що ми будемо визначити саме те, що це означає для підпису

Наприклад, щоб бути unforgeable.
Unforgeable. Добре, і я даю Цифрова

підписи просто як приклад. Для кожного примітивно, ми описали ми збираємося

точно визначити, що є загроза моделі.
Тоді ми будемо пропонувати будівництво

і тоді ми збираємося дати доказ, будь-які зловмисник що це можливість напасти на

Будівництво під загрозу модель. Що зловмисник може також використовуватися для вирішення деяких

Основні важкою проблемою. І, як результат, якщо проблема дійсно важко, що

фактично доводить, що немає зловмисник може розірвати будівництво під загрозу моделі.

Добре. Але ці три кроки, дійсно дуже важливо. У випадку з

підписи, ми будемо визначити, що це означає для підпису, щоб бути, forgeable, то ми будемо

дати на будівництво, і потім, наприклад ми будемо говорити що кожен, хто може розірвати наших

Будівництво потім можуть бути використані сказати цілих фактор, який, як вважають

важкою проблемою. Добре, так що ми будемо дотримуватися ці три кроки по всій, і

Тоді ви побачите, як це фактично йде. Добре, так що це кінець на

сегмент. І тоді у Наступний сегмент ми поговоримо трохи про історію

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