Перш ніж ми почнемо знайомиться з технічним матеріалом, я хочу зробити невеликий короткий огляд криптографії та різних її частин, і поговорити про те, що являє собою криптографія насправді.
[Слайд]
Ядро криптографії:
1. Створення безпечних ключів:
Аліса (знає, що розмовляє з Бобом) <================> Боб (знає, що розмовляє з Алісою)
У Аліси і у Боба є загальний ключ До
Атакуючий намагається підслухати розмову Аліси і Боба, не знаючи загального ключа
2. Безпечна зв'язок
Є загальний ключ, йде безпечна передача повідомлень (дотримується конфіденційність і цілісність)
[Слайд]
На початку курсу ми вже говорили, що є ядром криптографії, якщо хочете її наріжним каменем. Це дві складові. Перше - створення безпечних ключів, коли наша Аліса намагається поговорити з сервером Боба, скажімо, і в кінці протоколу узгодження, по суті, маємо спільний ключ, який створюється між двома сторонами. Крім того, Аліса точно знає, що вона спілкується з сервером (а не з ким-небудь) і має намір продовжити розмову. І Боб точно знає, що він дійсно розмовляє з клієнтом, скажімо, ім'я якого - Аліса. І зловмисник, звичайно, не знає нічого про секретному ключі. Друге - як ми вже говорили, коли обидві сторони домовилися про спільне ключі, між ними починає працювати безпечна передача повідомлень. Але виявляється, що криптографія може робити ще багато чого, багато чого, багато чого, багато чого іншого. Я дам вам дуже короткий огляд того, що ще можна за допомогою неї зробити.
[Слайд]
Але криптографія може робити ще багато чого, багато чого, багато чого, багато чого іншого
1. Використання цифрового підпису може
2. Анонімне спілкування
[Слайд]
Отже, перше, що можна зробити, наприклад, те, що називається цифровим підписом. У реальному світі, ми знаємо, що якщо ми хочемо підписати контракт, то, чим я займаюся, по суті, - просто беру і підписую своїм ім'ям контракт. У цифровому світі це вже небезпечно, тому що насправді, якщо я підпишу своїм ім'ям цифрової контракт, то дуже легко для тих, хто отримує мій цифровий контракт - просто вирізати і вставити мій підпис на зовсім інший контракт, який я, можливо, не хотів би підписувати. І тут питання, як ми скопіюємо поняття цифрового підпису з фізичного світу в світ цифрових технологій? І ми будемо говорити про це досить багато. Це цілком цікавий механізм, і ми побачимо, як насправді ми можемо підписувати документи, такі, що підпис не можна буде скопіювати на інший документ.
Інший розділ криптографії має справу з анонімним спілкуванням. Ну, наприклад, тут у нас є користувач Аліса. Вона хоче поговорити з сервером Бобом, але Аліса не хоче, щоб сервер Боб знав, що це вона. Є безліч причин, чому ви хочете спілкуватися з сервером конфіденційно і тому питання полягає в тому, як це зробити. І виявляється, є концепція, звана змішана мережа (mixed network), яка дійсно дозволяє правильно шифрувати і маршрутизировать трафік через кілька проксі-серверів, тим самим дозволяючи спілкуватися Алісі з сервером так, що цей бідний сервер не має поняття, хто насправді з ним говорить. Таким чином, анонімна комунікація - ще одне хороше застосування криптографії.
[Слайд]
Один з видів анонімної комунікації - анонімні цифрові гроші.
питання:
- Як анонімно розплатитися "цифровими грошима"?
- Як уникнути подвійних витрат?
[Слайд]
Тепер, коли у вас є можливість анонімно спілкуватися, ви можете запитати: "а у мене може бути анонімна цифрова готівку (гроші)?" Отже, ще раз, у фізичному світі, у нас є гроші і їх анонімність означає, що як тільки я взяв доларову купюру з банку, я можу піти і витратити доларову купюру у продавця і немає такого способу, щоб хтось міг сказати, що це саме я витратив цей долар у продавця (паперові гроші мають унікальний номер, за яким їх можна відстежити, але не можна відстежити їх власника). По суті, коли я використовую гроші, я роблю це анонімно. Питання в тому, чи можемо ми зробити те ж саме в цифровому світі? І тут проблема виявляється набагато, набагато складніше. І ще питання, якщо у мене є цифрова монета, або у нас тут, наприклад, є Аліса, у неї є один долар цифрових монет, питання в тому, чи зможе вона насправді піти і витратити цей долар? У продавця, наприклад, та так, що продавець гадки не має, хто насправді витратив гроші.
Є ще одна причина, що викликає складність - в цифровому світі дуже легко для Аліси взяти цифрову монету і скопіювати її в іншу монету. Так що, тепер раптом замість однієї монети стало дві, і хто скаже, що Аліса не може піти і витратити ці монети у інших продавців. Якщо вона діяла анонімно, то немає можливості сказати, хто насправді вчинив це шахрайство. Хто ж насправді витратив монету двічі у двох різних продавців? І ось, здається, виникає напруженість між безпекою та недоторканністю приватного життя, тому що немає ніякого способу дізнатися, хто робить таке шахрайство. І виявляється, що це повністю здійснимо. І ми будемо говорити пізніше про анонімні цифрових грошах. Просто, щоб дати вам підказку, я скажу, що кожен раз, коли я проводжу монету, я повністю анонімний. Але якщо я витрачаю монети більш ніж один раз, то тут же раптово, моя особистість буде повністю розкрита і у мене можуть бути юридичні проблеми через подвійне витрачання однієї і тієї ж монети. Далі на курсі ми більш детально розглянемо як працюють з анонімними цифровими грошима.
[Слайд]
протоколи
1. Проблема виборів
на слайді зображені кілька чоловічків, над кожним коштує 1 або 0
2. Закриті аукціони
[Слайд]
Інше застосування криптографії пов'язано з більш абстрактними протоколами, але перш, ніж я озвучу загальний результат, я приведу вам два приклади. Перший приклад пов'язаний з виборчою системою. Так ось, проблема виборів. Припустимо. У нас є дві партії. Партія нуля і партія одиниць. І виборці голосують за ці партії. Наприклад, цей виборець голосує за партію нуля, а цей за партію одиниць (на слайді, професор над чоловічками малює 0 і 1, всього чоловічків - 5). І так далі. Таким чином, на цих виборах, партія нуля отримала три голоси, а партія одиниць - два голоси. Переможцем на виборах, звичайно, є партія нуля. Але в цілому, переможцем на виборах є та сторона, яка отримує більшість голосів. Тепер, в чому полягає проблема виборів (голосування). Виборцям хотілося б якось порахувати більшість голосів, але зробити це таким чином, щоб не виявилися їхні індивідуальні голоси. Окей? Питання, як це зробити? А для цього, ми збираємося додати виборчий центр. який допоможе нам підрахувати більшість голосів, але збереже самі голоси в таємниці (професор малює виборчий центр, куди стікаються голосу). І кожен виборець буде відправляти фонеми шифрування своїх голосів у виборчий центр. І в кінці виборів, виборчий центр може порахувати, хто став переможцем. Однак, крім переможця, нічого не буде відомо про окремі голосах. Або в іншому випадку, окремі голоси зберігаються в таємниці. Звичайно, виборчий центр також перевіряє, що, наприклад, виборець має право голосу, і виборець проголосував тільки один раз. Але весь інший світ не повинен нічого знати, крім результату виборів. У нашому випадку протокол включає в себе шість сторін: п'ять виборців і один виборчий центр. Ці сторони вважаємо між собою. І в кінці обчислень стає відомий результат виборів, але нічого не відомо про окремі голосах.
Аналогічна проблема виникає в контексті закритих аукціонів. У закритому аукціоні кожен учасник пропонує свою ставку для прийняття участі в торгах. А тепер припустимо такий аукціонний механізм - переможець аукціону, це той, хто більше запропонує заплатити. Але сума, яку заплатить переможець насправді є другою за величиною ставкою. Таким чином, він платить другу найбільшу ціну (Аукціон другий ціни - закритий аукціон, при якому переможцем є учасник з найвищою ціною, але сплатити він повинен «другу ціну», тобто ціну свого найближчого конкурента) Отже, стандартний механізм аукціону ми позначили як переможець аукціону. А тепер те, що ми хотіли б зробити - дати можливість учасникам з'ясувати, хто більше заплатить, і скільки він повинен заплатити, але всі інші відомості про окремих пропозиціях повинні залишатися в таємниці. Так, наприклад, фактична сума ставки переможця повинна залишатися таємницею. Єдине, що доступно громадськості - друга за величиною ставка і особистість переможця. Отже, ще раз, як зробити так, щоб аукціон працював озвученим способом. По суті, учасники будуть відправляти свої зашифрованих заявки в центр аукціону. Сам центр буде обчислювати особистість переможця, а насправді він буде також обчислювати другу найбільшу ціну, але крім цих двох значень більше нічого не показувати, мається на увазі окремі пропозиції.
[Слайд]
протоколи
1. Проблема виборів
на слайді зображені кілька чоловічків, де вже кожен - це якась змінна х1, х2 ...
2. Закриті аукціони
Мета: обчислити f (x1, x2, x3, x4)
"Теорема": все, що можна зробити за допомогою довірених центрів, також можна зробити і без них
3. Протокол конфіденційного обчислення
[Слайд]
[Слайд]
"Магічна" криптографія
* Аутсорсинг приватних обчислень
* Нульове знання
Аліса знає множники числа N = p * q, а Боб знає тільки число N і він хоче перевірити: а чи точно Аліса знає множники. Аліса доводить Бобу, що вона знає P і Q, не розголошуючи їх конкретне значення.
[Слайд]
А зараз я розповім про деякі додатках криптографії, які інакше, як просто чарівними, я не можу класифікувати. Дозвольте мені навести вам два приклади. Отже, перший - називається аутсорсинг приватних обчислень (privately outsourcing computation). Я на прикладі пошуку Google проілюструю. Отже, уявіть, у Аліси є пошуковий запит, на який вона бажає отримати результат. Виявляється, що існує дуже специфічні схеми шифрування, де Аліса посилає свій шифрований запит в Google. А потім, оскільки в Google використовується своя схема шифрування, Google насправді обчислює зашифровані значення, нічого не знаючи про відкритий текст. Таким чином, Google зможе запустити свій алгоритм пошуку, отримавши зашифрований запит, і повернувши зашифровані результати. Окей. Google відправляє зашифровані результати назад Алісі. Аліса розшифровує, і отримує результати. Але магія тут в тому, що Google побачив тільки зашифрований запит і ні більше. Виходить, що Google в результаті не знає, що шукала Аліса, але тим не менше Аліса насправді знала, знала точно, що саме вона шукала. Добре, а що це за такі чарівні схеми шифрування. Їх ввели порівняно недавно, всього лише нова розробка близько двох-трьох років тому, дозволяє обчислювати незашифровані дані, навіть якщо ми не знаємо, що всередині шифрування. Але, перш ніж бігти і думати про реалізацію цього механізму, я повинен попередити вас, що насправді на даний момент це все теорія, в тому сенсі, щоб запустити пошук Google по шифрованих даними, ймовірно, буде потрібно мільярд років. Але тим не менше, сам факт, що це реально, вже дивний, і це вже дуже корисно для відносно простих розрахунків. Фактично, ми побачимо деякі додатки пізніше.
[Слайд]
Точна наука.
Три кроки в криптографії:
1. Визначити модель загрози
2. Запропонувати конструкцію
3. Довести, що зловмисник не може зламати конструкцію відповідно до цієї моделлю загрози
[Слайд]
І останнє, що я хочу сказати, що сучасна криптографія є дуже точною наукою. І справді, кожне поняття, яке ми збираємося розглядати слід трьом правилам. Дуже суворі правила, окей, і ми будемо стикатися з ними знову і знову, тому я хочу пояснити, що вони собою представляють. Перше, що ми збираємося робити, коли ми вводимо новий примітив, наприклад, цифровий підпис, ми збираємося визначити - модель загрози. Тобто, що може зробити зловмисник при атаці на цифровий підпис і яка його мета при створенні підпису? Отже, ми збираємося точно визначити, що це означає для підпису, наприклад, те, що вона повинна бути щира. Непідробна. Як приклад ми розглядаємо цифровий підпис. Для кожного іншого примітиву ми збираємося точно визначити, які загрози існують.
Далі ми збираємося запропонувати якусь конструкцію, а потім надати доказ того, що будь-який зловмисник здатний напасти на запропоновану конструкцію відповідно до цієї моделлю загрози. Атакуючий може також використовувати для вирішення деякі особливості проблеми. І в результаті, якщо проблема дійсно важка, тобто доводить, що зловмисник не може зламати конструкцію відповідно до цієї моделлю загрози. Окей.
Але ці три кроки, насправді дуже важливі. У випадку з підписом, ми визначимо загрозу - підробка підпису - далі, запропонуємо конструкцію, а потім, наприклад, ми говоримо, що будь-який, хто може порушити нашу конструкцію зіткнеться з проблемою факторизації цілих чисел, яка, як вважається, важко реалізована задача. Отже, ми збираємося застосувати описані три правила (загроза, конструкція, доказ) до всього, і тоді ви побачите, як насправді все виходить. Отже, це кінець сегмента. У наступному сегменті ми поговоримо трохи про історію криптографії.