-
Перш ніж ми почнемо з технічним матеріалом, я хочу дати вам
-
короткий огляд того, що криптографія і про різних областях криптографії. Таким
-
чином, основою криптографії, звичайно, є безпека зв'язку, яка по суті
-
складається з двох частин. Перший ключ безпеки створенний і те, як
-
ми спілкуємося безпечно тільки у нас є ключ. Ми вже говорили, що ключ
-
безпеки створення по суті зводиться до Аліси і Боба відправки повідомлень один
-
з одним так, що в кінці цього протоколу, є ключ, що обидва
-
вони домовляться, загальний ключ К, а крім того, за рамки просто ключ , насправді
-
Аліса буде знати, що вона говорить Боб і Боб буде знати, що він розмовляє з
-
Еліс. Але бідний зловмисник, який слухає цю розмову не знає, що
-
ключ є. І ми побачимо, як це зробити пізніше в курсі. Тепер, як тільки вони
-
Тепер, як тільки у них є спільний ключ, вони хочуть безпечно обмінюватися повідомленнями за допомогою цього ключа, і
-
ми поговоримо про схеми шифрування, які дозволяють їм зробити це таким чином, що
-
зловмисник не може з'ясувати, які повідомлення були відправлені туди і назад. І
-
Крім того зловмисник не може навіть спотворювати цього руху без виявлення.
-
Іншими словами, ці схеми шифрування забезпечують обох конфіденційність і
-
цілісність. Але криптографії робить багато, багато, набагато більше, ніж просто цих двох
-
речі. І я хочу дати вам декілька прикладів. Таким чином перший приклад я
-
щоб дати вам є те, що називається цифровим підписом. Так цифрового підпису
-
в основному, це аналогові підпис у фізичному світі. У фізичному
-
світ, пам'ятаєте, коли ви підписуєте документ, по суті, ви пишете ваш підпис на
-
документа а підпис є завжди те ж саме. Ви завжди писати те ж
-
підпис на всі документи, який потрібно підписати. У цифровому світі це не можу
-
Можливо, робота, тому що якщо зловмисник просто отримали один підписаного документа з мене, він
-
можна вирізати і вставити мій підпис до інших документів, які я не могла
-
хотіли підписування. І так, це просто не можливо в цифровий світ який мій
-
підпис є однаковими для всіх документів, які я хочу, щоб підписати. Так що ми будемо говорити
-
про те, як побудувати цифрових підписів у другій половині курсу. Він має
-
дійсно дуже цікавим примітивно і ми побачимо, як саме це зробити. Просто до
-
дати вам підказку, як цифрові підписи працюємо в основному за рахунок на
-
цифровий підпис за допомогою функції вмісту, який підписується. Так що зловмисник хто
-
намагається копіювати мій підпис з одного документа до іншого не буде досягти успіху
-
тому що підпис. На новий документ не буде належної функції на
-
дані в новий документ і, як результат, не буде перевірити підпис. І як я вже сказав,
-
Ми будемо бачити, як саме, щоб побудувати цифрові підписи пізніше, і тоді ми будемо
-
Доведіть, що ці конструкції безпечним.
Інший додаток криптографії що я
-
хотілося б відзначити, є анонімні зв'язку. Так, тут, уявіть собі користувача
-
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, то ми будемо
-
дати на будівництво, і потім, наприклад ми будемо говорити що кожен, хто може розірвати наших
-
Будівництво потім можуть бути використані сказати цілих фактор, який, як вважають
-
важкою проблемою. Добре, так що ми будемо дотримуватися ці три кроки по всій, і
-
Тоді ви побачите, як це фактично йде. Добре, так що це кінець на
-
сегмент. І тоді у Наступний сегмент ми поговоримо трохи про історію
-
криптографії.