Шта је криптографија? (15 min)

Пре него што пређемо на градиво техничке природе, желим да вам дам кратак

преглед о чему се заправо ради у криптографији и о њеним различитим областима.

Срж криптографије је наравно безбедна комуникација која се у суштини

састоји из два дела. Први део је успостављање тајног кључа

а други део безбедно комуницирање помоћу дељеног кључа. Већ смо рекли да се

успостављање тајног кључа своди на слање порука између Алисе и Боба

тако да на крају овог протокола постоји заједнички кључ о коме

су се обоје сложили, заједнички кључ k, и да, осим заједничког кључа,

Алиса зна да разговара са Бобом и Боб зна да разговара са Алисом.

Али сироти нападач који прислушкује овај разговор нема никакву представу о томе

шта је вредност заједничког кључа. Касније ћемо у течају да видимо како се ово постиже.

Једном када имају заједнички кључ, они желе да размењују поруке безбедно коришћењем кључа,

па ћемо да говоримо о начинима шифровања који им омогућавају да то чине

на такав начин да нападач не може да открије које поруке се размењују.

Осим тога, нападач не може да се меша у саобраћај а да не буде примећен.

Другим речима, ови начини шифровања омогућавају како тајност тако и

веродостојност. Али криптографија омогућава још много, много више него

ове две ствари. И желео бих да вам дам пар примера за ово. Први пример који

желим да вам дам је такозвани дигитални потпис. Дигитални потпис је

у суштини попут потписа у природном свету. Када у природном

свету потпишете документ, ставили сте свој потпис на њега,

и ваш потпис је увек исти. Увек стављате исти

потпис на све документе које желите да потпишете. У дигиталном свету, ово

није могуће, јер када би нападач прибавио макар само један документ који сам ја потписао,

он би могао да исече и залепи мој потпис на неки други документ који можда нисам

желео да потпишем. Тако да једноставно није могуће да у дигиталном свету

мој потпис буде исти за све документе које желим да потпишем. Тако да ћемо

у другом делу течаја да говоримо о томе како се праве дигитални потписи.

То је заиста занимљива примитива, и видећемо како се управо то ради.

Да вам наговестим, дигитални потписи се добијају

у функцији садржаја који се потписује. Тако да нападач који

покушава да копира мој потпис са једног документа на други не може да успе у томе,

зато што потпис на новом документу није одговарајућа функција

података у новом документу, и због тога потпис неће бити потврђен. Као што сам рекао,

касније ћемо да видимо како се управо добијају дигитални потписи, а затим ћемо

да докажемо да су такве конструкције безбедне. Још једна примена криптографије коју

сам желео да споменем, јесте анонимна комуникација. Замислите да корисник

Алиса жели да се обрати неком серверу за ћаскање, Бобу. И, можда жели да разговара о

неком медицинском стању, и жели да то учини анонимно, тако да сервер

не зна ко је она. Постоји стандардни поступак, који се назива

микснет, који омогућава Алиси да комуницира преко јавне интернет мреже са Бобом преко

низа посредника, тако да на крају комуникације Боб нема представу о томе са ким

је управо разговарао. Микснет ради тако што Алиса шаље своје поруке

Бобу преко низа посредника, ове поруке се шифрују

и дешифрују тако да Боб нема представу о томе са ким је разговарао, а сами посредници

не знају чак ни то да Алиса разговара са Бобом, или још уопштеније

ко разговара са ким. Занимљивост везана за овај анонимни

канал комуникације је што је ово обострано. Другим речима,

чак иако Боб нема представу са ким разговара, он може да одговори Алиси и

Алиса ће да добије те поруке. Када имамо анонимну комуникацију, можемо да надоградимо

друге механизме приватности. Желим да вам дам један пример који се зове анонимна

дигитална готовина. Приметите да када у природном свету имам долар,

могу да уђем у књижару и купим књигу, и трговац не би знао

ко сам ја. Питање је да ли можемо да имамо то исто у

дигиталном свету. Алиса у дигиталном свету може да има дигитални долар,

дигитални новчић од једног долара. И можда жели да потроши тај новац на неку куповину преко

мреже, рецимо у мрежној књижари. Желимо да постигнемо то да

када Алиса потроши свој новчић у књижари, књижара не може да зна

ко је Алиса. Тако да омогућавамо исту анонимност коју имамо приликом коришћења праве готовине.

Проблем је што у дигиталном свету, Алиса може да узме свој новчић

од једног долара, и пре него што га потроши, може да направи његове дупликате.

Тако да уместо да има само један новчић,

сада има три новчића, и они су сви истоветни наравно,

тако да је ништа не спречава да узме ове копије новчића

и потроши их код других трговаца. Тако да се поставља питање како се омогућава анонимна

дигитална готовина, а да се при томе спречи да Алиса више пута потроши

исти новчић код различитих трговаца. У извесном смислу овде постоји парадокс, зато што је

анонимност у противречности са безбедношћу - ако имамо анонимну готовину, ништа не може

да спречи Алису да не потроши исти новчић више пута, а зато што је новчић

анониман, немамо начин да утврдимо ко је починио превару. Тако да је питање

како да се разреши ова противречност. Испоставља се да је ово сасвим изводљиво.

Касније ћемо да говоримо и о анонимној дигиталној готовини. Само да вам наговестим,

све што треба да урадимо је да обезбедимо да ако Алиса потроши новчић

једном, нико не зна ко је она, али ако га потроши више него једном,

њен идентитет се разоткрива и она је подложна

законској одговорности. То је дакле начин на који се постиже анонимна дигитална готовина

и ми ћемо касније током течаја да видимо како се она спроводи.

Још једна примена криптографије везана је са још апстрактнијим протоколима,

али пре него што пређем на уопштене резулате, желим да вам дам два примера.

Први пример је везан за гласачке системе. Проблем гласања је следећи:

рецимо да постоје две странке, странка 0 и странка 1. Гласачи гласају за ове странке.

Тако на пример, овај гласач је могао да гласа за странку 0, овај за

странку 1, итд. Тако да је на овим изборима странка 0 добила 3 гласа а странка 1

је добила 2 гласа. Победник на изборима је наравно странка 0.

Али мало уопштеније, победник на изборима је странка која добије већину

гласова. Проблем гласања састоји се у следећем. Гласачи би желели да

се преброји већина гласова, али на такав начин да се ништа друго

не открива о њиховим појединачним гласовима. Поставља се питање како да се ово постигне?

Да бисмо ово постигли, увешћемо изборно седиште које ће да нам помогне у

пребројавању већинских гласова, али ће да сачува тајност гласача. Свака странка ће

да пошаље изборном седишту своје шифроване гласове

на такав начин да на крају избора, изборно седиште може да

преброји и да као излаз победника избора. Међутим, осим победника

избора, ништа се друго не открива о појединачним гласачима - појединачни гласови

у сваком погледу остају потпуно приватни. Наравно изборно седише такође треба да

потврди да на пример гласач има право гласа, и да је гласао

само једанпут. Али осим тог податка, изборно седиште и

остатак света нису сазнали ништа друго из гласова гласача осим

резултата избора. Ово је дакле пример протокола који обухвата 6

странака. У овом случају постоји 5 гласача у једном изборном седишту.

Ове странке броје гласове између себе. И на крају бројања, резултат

избора је познат, али ништа друго није откривено о појединачним улазима.

Слични проблем јавља се и код приватних аукција.

Тада сваки купац има сопствену понуду коју је спреман да плати. И претпоставимо

да је механизам аукције који се користи онај који називамо Викрејевом аукцијом, када

је победник онај купац који је понудио највише.

Али свота коју победник плаћа је заправо друга највећа понуда. Дакле он плаћа

другу највећу понуду. Ово је стандардни механизам аукције, познат као

Викрејева аукција. Оно што ми желимо да постигнемо јесте да омогућимо учесницима

да израчунају ко је понудио највише и колико треба да плати,

али да осим тога све остале информације о појединачним понудама

остану тајне. Тако да на пример, стварна количина новца коју је понудио купац са највећом

понудом, треба да остане тајна. Једина ствар која треба да је објави је друга највећа понуда

и идентитет купца са највећом понудом. Ово ћемо опет да постигнемо

тако што ћемо да уведемо седиште аукције, и, на сличан начин, свако

ће да пошаље своју шифровану понуду аукцијском седишту. Оно ће

да одреди идентитет победника и другу

највишу понуду, али осим ових двеју вредности, ништа друго се не открива о

појединачним понудама. Ово је у ствари пример много општијег проблема,

названог безбедни вишестраначки прорачун. Да вам објасним о чему се ради код

вишестраначког прорачуна. У општем случају, учесници имају тајни

улаз према себи. Тако да у случају избора, улази би били

гласови. У случају аукције, улази би били тајне понуде. А затим,

оно што желе да ураде јесте да прорачунају неку врсту функције својих улаза.

Још једном, у случају избора, функција јесте већина. У случају

аукције, функција је други највећи број између х1

до х4. И поставља се питање, како то могу да ураде, тако да вредност

функције буде откривена, али да се не открије ништа друго о појединачним гласовима.

Показаћу вам глупи, небезбедни начин да се ово уради. Увешћемо

странку од поверења. Овај поверљиви опуномоћеник сакупља појединачне

улазе, и обећава да ће појединачне улазе учинити тајним, тако да ће само он

да зна шта су они. И затим објављује вредност функције

свету. Замисао је да вредност функције постане јавна,

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

поверљивог опуномоћеника, и ако он из неког разлога није

од поверења, имате проблем. Тако да постоји врло битна теорема у

криптографији, и стварно је изненађујућа, која гласи да који год

прорачун желели да извршите, коју год функцију F желели да прорачунате, ако можете

да је прорачунате са поверљивим опуномоћеником, можете и без њега.

Објаснићу вам шта ово значи, на високом нивоу. У суштини, сада ћемо

да се отарасимо опуномоћеника. Странке неће да шаљу

своје улазе опуномоћенику. У ствари, више неће да постоји

опуномоћеник у систему. Уместо тога, странке ће да

разговарају међусобно коришћењем неког протокола, таквог да на крају овог протокола

одједном вредност функције свима постаје позната, а да ипак

ништа друго осим вредности функције није откривено. Другим речима,

појединачни улази остају тајни, али нема опуномоћеника, постоји

само начин да се међусобно разговара тако да се открије коначни излаз.

Ово је врло општи резултат, и изненађујуће је да је ово уопште изводљиво.

А заправо јесте, и при крају часа ћемо заправо да видимо како да

ово постигнемо. Постоје неке примене криптографије

које не могу да разврстам другачије осим што ћу да кажем да су једноставно чаробне.

Даћу вам два таква примера. Први пример је такозвано приватно измештање прорачуна.

Даћу вам пример Гугл претраге само да вам представим у чему је ствар.

Замислите да Алиса има упит који жели да изда. Испоставља се да

постоје нарочите шеме шифровања такве да Алиса може да пошаље свој шифровани

упит Гуглу. А затим, због особина шеме за шифровање,

Гугл може да врши прорачун над шифрованим вредностима, а да при томе не зна

вредности отвореног текста. Дакле Гугл може да изврши свој гломазан алгоритам претраге

над шифрованим упитом и добије шифроване резултате. Гугл ће да пошаље

шифроване резултате натраг Алиси. Алиса ће да дешифрује и тада ће да добије

резултате. Чаролија у свему томе је да је Гугл видео само шифровани облик њених упита

и ништа више. И тако, Гугл у складу с тим нема представу о томе шта је у ствари Алиса

тражила, а ипак Алиса је сазнала баш оно што је

желела да сазна. Дакле, ово је врста чаробних шифрованих шема, оне су

јако скорашње, ово је нови изум од пре две или три године,

који ће да нам омогући да вршимо прорачуне над шифрованим подацима, иако заправо

не знамо шта је садржано под шифром. Пре него што пожурите да имплементирате ово,

требало би да вас упозорим да је ово у овој тачки развоја само теорија,

у том смислу што би за извршавање Гугл упита над шифрованим подацима било потребно

милијарду година. Упркос томе, сама чињеница да је ово изводљиво је врло

изненађујућа, и заиста врло корисна за релативно једноставне прорачуне.

Видећемо неке примене овог мало касније. Друга чаробна примена коју сам

желео да вам покажем је такозвано нула знање. Конкретно, говорићу ћу вам

о нечему што се зове доказ знања са нула знањем.

Ево о чему се ради: постоји неки број n, који је Алиси познат.

Овај број добијен је као производ два велика проста броја. Замислите да

имамо овде два проста броја, р и q. Можете да их оба схватите као 1000-цифрене бројеве.

И вероватно знате да је множење два 1000-цифрена броја прилично једноставно.

Али ако вам дам само њихов производ, његово разлагање на чиниоце је

у ствари прилично тешко. Искористићемо ту чињеницу да је разлагање на чиниоце

тешко да бисмо изградили криптосистеме са јавним кључем у другој половини течаја.

Алиса има овај број n, и такође зна чиниоце

од n. Боб има само број n, а не зна разлагање на чиниоце.

Чаробна ствар у вези са доказом знања са нула знањем је та,

што Алиса може да докаже Бобу да зна разлагање броја n на чиниоце, она заправо може да

понуди овај доказ Бобу, који он може да провери, и да буде уверен да Алиса зна

чиниоце броја n, а да Боб ништа не сазна о чиниоцима р

и q, и ово може да се докаже. Боб не сазнаје ништа

о чиниоцима р и q. Ово тврђење је заправо врло, врло општеважеће.

Овде се не ради само о томе да се докаже разлагање n на чиниоце. За скоро сваку слагалицу

за коју желите да докажете да имате њено решење, можете да то докажете при нула знању.

Значи ако имате укрштеницу коју сте решили - можда укрштеница и није најбољи пример -

али ако имате судоку слагалицу, на пример, за коју желите

да докажете да сте је решили, можете то да докажете Бобу на такав начин, да Боб не сазна

ништа о решењу, а да ипак буде уверен да заиста имате

решење ове слагалице. То су биле те чаробне примене.

Последња ствар коју сам желео да кажем је да је савремена криптографија јако

строга наука. Сваки појам који будемо описали,

следиће три јако строга корака, и ова три корака ћемо да видимо

поново и поново и поново, тако да желим да вам покажем шта су они. Прва ствар

коју ћемо да урадимо када представимо нову примитиву као што је дигитални потпис,

јесте да опишемо шта је тачно модел претње. То јест, шта нападач

може да уради да би напао дигитални потпис, и који је његов циљ приликом

фалсификовања. Дакле ми ћемо да одредимо шта то тачно значи да потпис

буде немогућ за фалсификовање. Дигитални потпис

наводим само као пример. За сваку примитиву коју ћемо да опишемо, ми ћемо

да тачно одредимо шта је модел претње. Затим ћемо да предложимо конструкцију

а затим и да докажемо да сваки нападач који успе да нападне

конструкцију под овим моделом претње, може да реши неки

тежак задатак који је у позадини. Сходно томе, ако је задатак јако тежак, тиме

доказујемо да ниједан нападач не може да пробије ову конструкцију под овим моделом претње.

Ова три корака су заправо врло важна. У случају

потписа, одредићемо шта то значи да потпис буде немогућ за фалсификовање, затим

ћемо да понудимо конструкцију, а затим ћемо да потврдимо да свако ко може да пробије нашу

конструкцију, може и да подели цели број на чиниоце, што се сматра

тешким задатком. Пратићемо ова три корака,

и онда ћете да видите како се ово добија.

Ово је крајовог одељка. У следећем одељку ћемо да разговарамо о историји

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