0:00:00.000,0:00:02.951 Пре него што пређемо на градиво техничке природе, желим да вам дам кратак 0:00:02.951,0:00:06.487 преглед о чему се заправо ради у криптографији и о њеним различитим областима. 0:00:06.487,0:00:10.487 Срж криптографије је наравно безбедна комуникација која се у суштини 0:00:10.487,0:00:14.539 састоји из два дела. Први део је успостављање тајног кључа 0:00:14.539,0:00:18.697 а други део безбедно комуницирање помоћу дељеног кључа. Већ смо рекли да се 0:00:18.697,0:00:22.854 успостављање тајног кључа своди на слање порука између Алисе и Боба 0:00:22.854,0:00:26.906 тако да на крају овог протокола постоји заједнички кључ о коме 0:00:26.906,0:00:30.906 су се обоје сложили, заједнички кључ k, и да, осим заједничког кључа, 0:00:30.906,0:00:35.274 Алиса зна да разговара са Бобом и Боб зна да разговара са Алисом. 0:00:35.274,0:00:39.964 Али сироти нападач који прислушкује овај разговор нема никакву представу о томе 0:00:39.964,0:00:44.011 шта је вредност заједничког кључа. Касније ћемо у течају да видимо како се ово постиже. 0:00:44.011,0:00:47.657 Једном када имају заједнички кључ, они желе да размењују поруке безбедно коришћењем кључа, 0:00:47.657,0:00:51.698 па ћемо да говоримо о начинима шифровања који им омогућавају да то чине 0:00:51.698,0:00:55.491 на такав начин да нападач не може да открије које поруке се размењују. 0:00:55.491,0:00:59.630 Осим тога, нападач не може да се меша у саобраћај а да не буде примећен. 0:00:59.630,0:01:03.227 Другим речима, ови начини шифровања омогућавају како тајност тако и 0:01:03.227,0:01:06.774 веродостојност. Али криптографија омогућава још много, много више него 0:01:06.774,0:01:10.519 ове две ствари. И желео бих да вам дам пар примера за ово. Први пример који 0:01:10.519,0:01:14.468 желим да вам дам је такозвани дигитални потпис. Дигитални потпис је 0:01:14.468,0:01:18.892 у суштини попут потписа у природном свету. Када у природном 0:01:18.892,0:01:23.372 свету потпишете документ, ставили сте свој потпис на њега, 0:01:23.372,0:01:27.740 и ваш потпис је увек исти. Увек стављате исти 0:01:27.740,0:01:32.164 потпис на све документе које желите да потпишете. У дигиталном свету, ово 0:01:32.164,0:01:36.812 није могуће, јер када би нападач прибавио макар само један документ који сам ја потписао, 0:01:36.812,0:01:41.180 он би могао да исече и залепи мој потпис на неки други документ који можда нисам 0:01:41.180,0:01:45.247 желео да потпишем. Тако да једноставно није могуће да у дигиталном свету 0:01:45.247,0:01:49.590 мој потпис буде исти за све документе које желим да потпишем. Тако да ћемо 0:01:49.590,0:01:53.830 у другом делу течаја да говоримо о томе како се праве дигитални потписи. 0:01:53.830,0:01:58.123 То је заиста занимљива примитива, и видећемо како се управо то ради. 0:01:58.123,0:02:02.098 Да вам наговестим, дигитални потписи се добијају 0:02:02.098,0:02:06.232 у функцији садржаја који се потписује. Тако да нападач који 0:02:06.232,0:02:10.313 покушава да копира мој потпис са једног документа на други не може да успе у томе, 0:02:10.313,0:02:14.541 зато што потпис на новом документу није одговарајућа функција 0:02:14.541,0:02:18.526 података у новом документу, и због тога потпис неће бити потврђен. Као што сам рекао, 0:02:18.526,0:02:22.608 касније ћемо да видимо како се управо добијају дигитални потписи, а затим ћемо 0:02:22.608,0:02:27.193 да докажемо да су такве конструкције безбедне. Још једна примена криптографије коју 0:02:27.193,0:02:31.096 сам желео да споменем, јесте анонимна комуникација. Замислите да корисник 0:02:31.096,0:02:35.828 Алиса жели да се обрати неком серверу за ћаскање, Бобу. И, можда жели да разговара о 0:02:35.828,0:02:40.382 неком медицинском стању, и жели да то учини анонимно, тако да сервер 0:02:40.382,0:02:45.113 не зна ко је она. Постоји стандардни поступак, који се назива 0:02:45.113,0:02:49.946 микснет, који омогућава Алиси да комуницира преко јавне интернет мреже са Бобом преко 0:02:49.946,0:02:54.856 низа посредника, тако да на крају комуникације Боб нема представу о томе са ким 0:02:54.856,0:02:59.537 је управо разговарао. Микснет ради тако што Алиса шаље своје поруке 0:02:59.537,0:03:03.818 Бобу преко низа посредника, ове поруке се шифрују 0:03:03.818,0:03:08.271 и дешифрују тако да Боб нема представу о томе са ким је разговарао, а сами посредници 0:03:08.271,0:03:12.724 не знају чак ни то да Алиса разговара са Бобом, или још уопштеније 0:03:12.724,0:03:16.750 ко разговара са ким. Занимљивост везана за овај анонимни 0:03:16.750,0:03:20.498 канал комуникације је што је ово обострано. Другим речима, 0:03:20.498,0:03:24.743 чак иако Боб нема представу са ким разговара, он може да одговори Алиси и 0:03:24.743,0:03:29.153 Алиса ће да добије те поруке. Када имамо анонимну комуникацију, можемо да надоградимо 0:03:29.153,0:03:33.784 друге механизме приватности. Желим да вам дам један пример који се зове анонимна 0:03:33.784,0:03:37.643 дигитална готовина. Приметите да када у природном свету имам долар, 0:03:37.643,0:03:42.108 могу да уђем у књижару и купим књигу, и трговац не би знао 0:03:42.108,0:03:46.876 ко сам ја. Питање је да ли можемо да имамо то исто у 0:03:46.876,0:03:50.963 дигиталном свету. Алиса у дигиталном свету може да има дигитални долар, 0:03:50.963,0:03:55.984 дигитални новчић од једног долара. И можда жели да потроши тај новац на неку куповину преко 0:03:55.984,0:04:00.760 мреже, рецимо у мрежној књижари. Желимо да постигнемо то да 0:04:00.760,0:04:05.539 када Алиса потроши свој новчић у књижари, књижара не може да зна 0:04:05.539,0:04:10.629 ко је Алиса. Тако да омогућавамо исту анонимност коју имамо приликом коришћења праве готовине. 0:04:10.629,0:04:15.470 Проблем је што у дигиталном свету, Алиса може да узме свој новчић 0:04:15.470,0:04:20.250 од једног долара, и пре него што га потроши, може да направи његове дупликате. 0:04:20.250,0:04:24.086 Тако да уместо да има само један новчић, 0:04:24.093,0:04:27.936 сада има три новчића, и они су сви истоветни наравно, 0:04:27.936,0:04:31.828 тако да је ништа не спречава да узме ове копије новчића 0:04:31.828,0:04:35.819 и потроши их код других трговаца. Тако да се поставља питање како се омогућава анонимна 0:04:35.819,0:04:39.849 дигитална готовина, а да се при томе спречи да Алиса више пута потроши 0:04:39.849,0:04:43.760 исти новчић код различитих трговаца. У извесном смислу овде постоји парадокс, зато што је 0:04:43.760,0:04:47.879 анонимност у противречности са безбедношћу - ако имамо анонимну готовину, ништа не може 0:04:47.879,0:04:51.999 да спречи Алису да не потроши исти новчић више пута, а зато што је новчић 0:04:51.999,0:04:56.244 анониман, немамо начин да утврдимо ко је починио превару. Тако да је питање 0:04:56.244,0:05:00.394 како да се разреши ова противречност. Испоставља се да је ово сасвим изводљиво. 0:05:00.394,0:05:04.757 Касније ћемо да говоримо и о анонимној дигиталној готовини. Само да вам наговестим, 0:05:04.757,0:05:09.173 све што треба да урадимо је да обезбедимо да ако Алиса потроши новчић 0:05:09.173,0:05:13.764 једном, нико не зна ко је она, али ако га потроши више него једном, 0:05:13.764,0:05:17.878 њен идентитет се разоткрива и она је подложна 0:05:17.878,0:05:22.096 законској одговорности. То је дакле начин на који се постиже анонимна дигитална готовина 0:05:22.096,0:05:26.158 и ми ћемо касније током течаја да видимо како се она спроводи. 0:05:26.158,0:05:30.219 Још једна примена криптографије везана је са још апстрактнијим протоколима, 0:05:30.219,0:05:34.333 али пре него што пређем на уопштене резулате, желим да вам дам два примера. 0:05:34.333,0:05:38.343 Први пример је везан за гласачке системе. Проблем гласања је следећи: 0:05:38.343,0:05:42.656 рецимо да постоје две странке, странка 0 и странка 1. Гласачи гласају за ове странке. 0:05:42.656,0:05:47.101 Тако на пример, овај гласач је могао да гласа за странку 0, овај за 0:05:47.101,0:05:52.313 странку 1, итд. Тако да је на овим изборима странка 0 добила 3 гласа а странка 1 0:05:52.313,0:05:56.590 је добила 2 гласа. Победник на изборима је наравно странка 0. 0:05:56.590,0:06:01.579 Али мало уопштеније, победник на изборима је странка која добије већину 0:06:01.579,0:06:06.453 гласова. Проблем гласања састоји се у следећем. Гласачи би желели да 0:06:06.453,0:06:11.720 се преброји већина гласова, али на такав начин да се ништа друго 0:06:11.720,0:06:16.797 не открива о њиховим појединачним гласовима. Поставља се питање како да се ово постигне? 0:06:16.797,0:06:21.493 Да бисмо ово постигли, увешћемо изборно седиште које ће да нам помогне у 0:06:21.493,0:06:26.633 пребројавању већинских гласова, али ће да сачува тајност гласача. Свака странка ће 0:06:26.633,0:06:32.027 да пошаље изборном седишту своје шифроване гласове 0:06:32.027,0:06:36.949 на такав начин да на крају избора, изборно седиште може да 0:06:36.949,0:06:41.615 преброји и да као излаз победника избора. Међутим, осим победника 0:06:41.615,0:06:46.580 избора, ништа се друго не открива о појединачним гласачима - појединачни гласови 0:06:46.580,0:06:51.366 у сваком погледу остају потпуно приватни. Наравно изборно седише такође треба да 0:06:51.366,0:06:56.331 потврди да на пример гласач има право гласа, и да је гласао 0:06:56.331,0:07:00.818 само једанпут. Али осим тог податка, изборно седиште и 0:07:00.818,0:07:05.484 остатак света нису сазнали ништа друго из гласова гласача осим 0:07:05.484,0:07:10.104 резултата избора. Ово је дакле пример протокола који обухвата 6 0:07:10.104,0:07:14.430 странака. У овом случају постоји 5 гласача у једном изборном седишту. 0:07:14.430,0:07:19.417 Ове странке броје гласове између себе. И на крају бројања, резултат 0:07:19.417,0:07:24.404 избора је познат, али ништа друго није откривено о појединачним улазима. 0:07:24.404,0:07:29.156 Слични проблем јавља се и код приватних аукција. 0:07:29.156,0:07:34.160 Тада сваки купац има сопствену понуду коју је спреман да плати. И претпоставимо 0:07:34.160,0:07:39.356 да је механизам аукције који се користи онај који називамо Викрејевом аукцијом, када 0:07:39.356,0:07:45.287 је победник онај купац који је понудио највише. 0:07:45.287,0:07:50.099 Али свота коју победник плаћа је заправо друга највећа понуда. Дакле он плаћа 0:07:50.099,0:07:54.850 другу највећу понуду. Ово је стандардни механизам аукције, познат као 0:07:54.850,0:08:00.028 Викрејева аукција. Оно што ми желимо да постигнемо јесте да омогућимо учесницима 0:08:00.028,0:08:04.779 да израчунају ко је понудио највише и колико треба да плати, 0:08:04.779,0:08:09.165 али да осим тога све остале информације о појединачним понудама 0:08:09.165,0:08:14.160 остану тајне. Тако да на пример, стварна количина новца коју је понудио купац са највећом 0:08:14.160,0:08:19.225 понудом, треба да остане тајна. Једина ствар која треба да је објави је друга највећа понуда 0:08:19.225,0:08:23.526 и идентитет купца са највећом понудом. Ово ћемо опет да постигнемо 0:08:23.526,0:08:28.172 тако што ћемо да уведемо седиште аукције, и, на сличан начин, свако 0:08:28.172,0:08:32.588 ће да пошаље своју шифровану понуду аукцијском седишту. Оно ће 0:08:32.588,0:08:37.119 да одреди идентитет победника и другу 0:08:37.119,0:08:41.822 највишу понуду, али осим ових двеју вредности, ништа друго се не открива о 0:08:41.822,0:08:46.126 појединачним понудама. Ово је у ствари пример много општијег проблема, 0:08:46.126,0:08:50.264 названог безбедни вишестраначки прорачун. Да вам објасним о чему се ради код 0:08:50.264,0:08:54.618 вишестраначког прорачуна. У општем случају, учесници имају тајни 0:08:54.618,0:08:58.649 улаз према себи. Тако да у случају избора, улази би били 0:08:58.649,0:09:02.787 гласови. У случају аукције, улази би били тајне понуде. А затим, 0:09:02.787,0:09:06.959 оно што желе да ураде јесте да прорачунају неку врсту функције својих улаза. 0:09:06.959,0:09:10.840 Још једном, у случају избора, функција јесте већина. У случају 0:09:10.840,0:09:15.088 аукције, функција је други највећи број између х1 0:09:15.088,0:09:19.179 до х4. И поставља се питање, како то могу да ураде, тако да вредност 0:09:19.179,0:09:23.375 функције буде откривена, али да се не открије ништа друго о појединачним гласовима. 0:09:23.375,0:09:27.675 Показаћу вам глупи, небезбедни начин да се ово уради. Увешћемо 0:09:27.675,0:09:31.774 странку од поверења. Овај поверљиви опуномоћеник сакупља појединачне 0:09:31.774,0:09:36.223 улазе, и обећава да ће појединачне улазе учинити тајним, тако да ће само он 0:09:36.223,0:09:40.510 да зна шта су они. И затим објављује вредност функције 0:09:40.510,0:09:44.742 свету. Замисао је да вредност функције постане јавна, 0:09:44.742,0:09:48.812 али да се ништа друго не открије о појединачним улазима. Али наравно, имате овог 0:09:48.812,0:09:52.990 поверљивог опуномоћеника, и ако он из неког разлога није 0:09:52.990,0:09:57.168 од поверења, имате проблем. Тако да постоји врло битна теорема у 0:09:57.168,0:10:01.001 криптографији, и стварно је изненађујућа, која гласи да који год 0:10:01.001,0:10:05.204 прорачун желели да извршите, коју год функцију F желели да прорачунате, ако можете 0:10:05.204,0:10:09.302 да је прорачунате са поверљивим опуномоћеником, можете и без њега. 0:10:09.302,0:10:13.559 Објаснићу вам шта ово значи, на високом нивоу. У суштини, сада ћемо 0:10:13.559,0:10:17.816 да се отарасимо опуномоћеника. Странке неће да шаљу 0:10:17.816,0:10:21.807 своје улазе опуномоћенику. У ствари, више неће да постоји 0:10:21.807,0:10:26.011 опуномоћеник у систему. Уместо тога, странке ће да 0:10:26.011,0:10:30.567 разговарају међусобно коришћењем неког протокола, таквог да на крају овог протокола 0:10:30.567,0:10:34.890 одједном вредност функције свима постаје позната, а да ипак 0:10:34.890,0:10:39.390 ништа друго осим вредности функције није откривено. Другим речима, 0:10:39.390,0:10:43.639 појединачни улази остају тајни, али нема опуномоћеника, постоји 0:10:43.639,0:10:47.867 само начин да се међусобно разговара тако да се открије коначни излаз. 0:10:47.867,0:10:51.846 Ово је врло општи резултат, и изненађујуће је да је ово уопште изводљиво. 0:10:51.846,0:10:56.024 А заправо јесте, и при крају часа ћемо заправо да видимо како да 0:10:56.024,0:11:00.577 ово постигнемо. Постоје неке примене криптографије 0:11:00.577,0:11:05.560 које не могу да разврстам другачије осим што ћу да кажем да су једноставно чаробне. 0:11:05.560,0:11:10.240 Даћу вам два таква примера. Први пример је такозвано приватно измештање прорачуна. 0:11:10.240,0:11:15.224 Даћу вам пример Гугл претраге само да вам представим у чему је ствар. 0:11:15.224,0:11:20.329 Замислите да Алиса има упит који жели да изда. Испоставља се да 0:11:20.329,0:11:25.434 постоје нарочите шеме шифровања такве да Алиса може да пошаље свој шифровани 0:11:25.434,0:11:30.368 упит Гуглу. А затим, због особина шеме за шифровање, 0:11:30.368,0:11:35.304 Гугл може да врши прорачун над шифрованим вредностима, а да при томе не зна 0:11:35.304,0:11:40.368 вредности отвореног текста. Дакле Гугл може да изврши свој гломазан алгоритам претраге 0:11:40.368,0:11:44.903 над шифрованим упитом и добије шифроване резултате. Гугл ће да пошаље 0:11:44.903,0:11:49.242 шифроване резултате натраг Алиси. Алиса ће да дешифрује и тада ће да добије 0:11:49.242,0:11:53.689 резултате. Чаролија у свему томе је да је Гугл видео само шифровани облик њених упита 0:11:53.689,0:11:57.493 и ништа више. И тако, Гугл у складу с тим нема представу о томе шта је у ствари Алиса 0:11:57.493,0:12:01.672 тражила, а ипак Алиса је сазнала баш оно што је 0:12:01.672,0:12:05.812 желела да сазна. Дакле, ово је врста чаробних шифрованих шема, оне су 0:12:05.812,0:12:09.985 јако скорашње, ово је нови изум од пре две или три године, 0:12:09.985,0:12:14.436 који ће да нам омогући да вршимо прорачуне над шифрованим подацима, иако заправо 0:12:14.436,0:12:18.667 не знамо шта је садржано под шифром. Пре него што пожурите да имплементирате ово, 0:12:18.667,0:12:22.470 требало би да вас упозорим да је ово у овој тачки развоја само теорија, 0:12:22.470,0:12:26.422 у том смислу што би за извршавање Гугл упита над шифрованим подацима било потребно 0:12:26.422,0:12:30.521 милијарду година. Упркос томе, сама чињеница да је ово изводљиво је врло 0:12:30.521,0:12:34.473 изненађујућа, и заиста врло корисна за релативно једноставне прорачуне. 0:12:34.473,0:12:38.671 Видећемо неке примене овог мало касније. Друга чаробна примена коју сам 0:12:38.671,0:12:42.474 желео да вам покажем је такозвано нула знање. Конкретно, говорићу ћу вам 0:12:42.474,0:12:46.080 о нечему што се зове доказ знања са нула знањем. 0:12:46.080,0:12:50.177 Ево о чему се ради: постоји неки број n, који је Алиси познат. 0:12:50.177,0:12:54.169 Овај број добијен је као производ два велика проста броја. Замислите да 0:12:54.169,0:12:58.835 имамо овде два проста броја, р и q. Можете да их оба схватите као 1000-цифрене бројеве. 0:12:58.835,0:13:03.892 И вероватно знате да је множење два 1000-цифрена броја прилично једноставно. 0:13:03.892,0:13:08.235 Али ако вам дам само њихов производ, његово разлагање на чиниоце је 0:13:08.235,0:13:12.427 у ствари прилично тешко. Искористићемо ту чињеницу да је разлагање на чиниоце 0:13:12.427,0:13:16.566 тешко да бисмо изградили криптосистеме са јавним кључем у другој половини течаја. 0:13:16.566,0:13:20.968 Алиса има овај број n, и такође зна чиниоце 0:13:20.968,0:13:24.898 од n. Боб има само број n, а не зна разлагање на чиниоце. 0:13:24.898,0:13:28.723 Чаробна ствар у вези са доказом знања са нула знањем је та, 0:13:28.723,0:13:33.144 што Алиса може да докаже Бобу да зна разлагање броја n на чиниоце, она заправо може да 0:13:33.144,0:13:37.457 понуди овај доказ Бобу, који он може да провери, и да буде уверен да Алиса зна 0:13:37.457,0:13:42.386 чиниоце броја n, а да Боб ништа не сазна о чиниоцима р 0:13:42.386,0:13:47.034 и q, и ово може да се докаже. Боб не сазнаје ништа 0:13:47.034,0:13:50.997 о чиниоцима р и q. Ово тврђење је заправо врло, врло општеважеће. 0:13:50.997,0:13:55.275 Овде се не ради само о томе да се докаже разлагање n на чиниоце. За скоро сваку слагалицу 0:13:55.275,0:13:59.606 за коју желите да докажете да имате њено решење, можете да то докажете при нула знању. 0:13:59.606,0:14:03.831 Значи ако имате укрштеницу коју сте решили - можда укрштеница и није најбољи пример - 0:14:03.831,0:14:07.845 али ако имате судоку слагалицу, на пример, за коју желите 0:14:07.845,0:14:12.282 да докажете да сте је решили, можете то да докажете Бобу на такав начин, да Боб не сазна 0:14:12.282,0:14:16.718 ништа о решењу, а да ипак буде уверен да заиста имате 0:14:16.718,0:14:20.930 решење ове слагалице. То су биле те чаробне примене. 0:14:20.930,0:14:25.000 Последња ствар коју сам желео да кажем је да је савремена криптографија јако 0:14:25.000,0:14:29.015 строга наука. Сваки појам који будемо описали, 0:14:29.015,0:14:33.129 следиће три јако строга корака, и ова три корака ћемо да видимо 0:14:33.129,0:14:37.338 поново и поново и поново, тако да желим да вам покажем шта су они. Прва ствар 0:14:37.338,0:14:41.493 коју ћемо да урадимо када представимо нову примитиву као што је дигитални потпис, 0:14:41.493,0:14:45.540 јесте да опишемо шта је тачно модел претње. То јест, шта нападач 0:14:45.540,0:14:49.534 може да уради да би напао дигитални потпис, и који је његов циљ приликом 0:14:49.534,0:14:53.851 фалсификовања. Дакле ми ћемо да одредимо шта то тачно значи да потпис 0:14:53.851,0:14:57.760 буде немогућ за фалсификовање. Дигитални потпис 0:14:57.760,0:15:01.998 наводим само као пример. За сваку примитиву коју ћемо да опишемо, ми ћемо 0:15:01.998,0:15:06.464 да тачно одредимо шта је модел претње. Затим ћемо да предложимо конструкцију 0:15:06.464,0:15:10.931 а затим и да докажемо да сваки нападач који успе да нападне 0:15:10.931,0:15:15.955 конструкцију под овим моделом претње, може да реши неки 0:15:15.955,0:15:20.150 тежак задатак који је у позадини. Сходно томе, ако је задатак јако тежак, тиме 0:15:20.150,0:15:24.350 доказујемо да ниједан нападач не може да пробије ову конструкцију под овим моделом претње. 0:15:24.350,0:15:27.843 Ова три корака су заправо врло важна. У случају 0:15:27.843,0:15:31.928 потписа, одредићемо шта то значи да потпис буде немогућ за фалсификовање, затим 0:15:31.928,0:15:35.914 ћемо да понудимо конструкцију, а затим ћемо да потврдимо да свако ко може да пробије нашу 0:15:35.914,0:15:39.801 конструкцију, може и да подели цели број на чиниоце, што се сматра 0:15:39.801,0:15:43.541 тешким задатком. Пратићемо ова три корака, 0:15:43.541,0:15:47.331 и онда ћете да видите како се ово добија. 0:15:47.331,0:15:51.218 Ово је крајовог одељка. У следећем одељку ћемо да разговарамо о историји 0:15:51.218,0:15:52.006 криптографије.