0:00:00.000,0:00:03.583
Прошле недеље, проучили смо теорију бројева која нам је потребна за шифровање јавним кључем.

0:00:03.583,0:00:07.166
Ове недеље ћемо да применимо ово знање, и да саградимо

0:00:07.166,0:00:10.889
неколико безбедних шема за шифровање јавним кључем. Али најпре ћемо да дефинишемо шта је

0:00:10.889,0:00:14.565
шифровање јавним кључем, и шта значи да ово шифровање буде безбедно.

0:00:14.565,0:00:18.241
Да вас подсетим да у шеми са шифровањем јавним кључем,

0:00:18.241,0:00:21.778
постоји алгоритам шифровања који је обично означен са Е, и постоји алгоритам дешифровања

0:00:21.778,0:00:25.361
који означавамо са D. Међутим, овде алгоритам шифровања узима

0:00:25.361,0:00:29.477
јавни кључ, али алгоритам дешифровања узима тајни кључ. Овај пар се зове пар кључева.

0:00:29.477,0:00:34.356
Јавни кључ се користи за шифровање, а тајни за

0:00:34.356,0:00:39.002
дешифровање порука. У овом случају порука m је шифрована

0:00:39.002,0:00:43.880
јавним кључем, а излаз је шифрат с. И слично томе,

0:00:43.880,0:00:48.643
шифрат се потхрањује алгоритму дешифровања, и, користећи тајни кључ,

0:00:48.643,0:00:53.577
излаз из алгоритма дешифровања је изворна порука m. Шифровање јавним кључем

0:00:53.577,0:00:57.989
има пуно примена. Прошле недеље смо видели класичну примену

0:00:57.989,0:01:02.455
а то је успостављане сесије, наиме, размена кључева, и за сада посматрамо размену кључева

0:01:02.455,0:01:06.867
која је безбедна само од прислушкивања. Ако се сећате како овај протокол ради,

0:01:06.867,0:01:11.227
Алиса би произвела пар јавни кључ - тајни кључ,

0:01:11.227,0:01:15.546
послала би јавни кључ Бобу, Боб би произвео случајно х,

0:01:15.546,0:01:20.136
које ће да служи као њихова заједничка тајна, а затим би послао шифровано х Алиси,

0:01:20.136,0:01:24.904
шифровано њеним јавним кључем. Алиса може да дешифрује, поврати х, и сада обоје

0:01:24.904,0:01:29.554
имају заједнички кључ х који могу да користе да безбедно комуницирају међусобно.

0:01:29.554,0:01:34.143
Нападач може да види само јавни кључ,

0:01:34.143,0:01:38.972
х шифровано под јавним кључем, на основу којег не би требало да може да дође до

0:01:38.972,0:01:43.800
било каквих података о х. Дефинисаћемо тачније шта то значи

0:01:43.800,0:01:48.507
не бити у стању да сазнате било шта о х. Шифровање јавним кључем има

0:01:48.507,0:01:52.522
у ствари много других примена. На пример, јако је корисно код

0:01:52.522,0:01:57.235
неинтерактивних апликација. Рецимо сетите се система е-поште.

0:01:57.235,0:02:01.716
Овде Боб жели да пошаље писмо Алиси, и када га пошаље, писмо прелази од

0:02:01.716,0:02:06.603
једног предајника писама до другог, све док коначно не стигне до Алисе, када га она

0:02:06.603,0:02:10.502
дешифрује. Систем е-поште је развијен за неку врсту

0:02:10.502,0:02:15.045
немеђудејствујућих окружења, где Боб шаље писмо, и Алиса треба да прими то писмо,

0:02:15.045,0:02:19.195
а да при томе не треба да комуницира са Бобом да би га дешифровала.

0:02:19.195,0:02:23.502
Дакле у овом случају, због одсуства међудејства, не постоји прилика

0:02:23.502,0:02:27.705
да се успостави заједнички тајни кључ између Алисе и Боба. У овом случају,

0:02:27.705,0:02:32.169
Боб би послао писмо шифровано коришћењем Алисиног јавног кључа.

0:02:32.169,0:02:36.571
Дакле он шаље писмо; било ко на свету може да пошаље шифровано писмо Алиси,

0:02:36.571,0:02:41.103
коришћењем њеног јавног кључа. Када Алиса прими ово писмо, користи

0:02:41.103,0:02:45.748
свој тајни кључ да дешифрује шифрат и поврати отворени текст поруке.

0:02:45.748,0:02:50.507
Наравно мана оваквог система је што Боб треба да некако

0:02:50.507,0:02:54.804
прибави Алисин јавни кључ. За сада претпостављамо да Боб већ има

0:02:54.804,0:02:58.297
Алисин јавни кључ, а касније, заправо када будемо говорили

0:02:58.297,0:03:02.457
о дигиталним потписима, видећемо да ово може да се обави врло делотворно

0:03:02.457,0:03:06.823
коришћењем управљања јавним кључем, дакле, кажем, на ово ћемо да се вратимо нешто касније.

0:03:06.823,0:03:10.931
Основна ствар коју овде треба да запамтите је да се шифровање јавним кључем

0:03:10.931,0:03:14.578
користи за успостављање сесија. Ово је врло често у вебу, када се шифровање јавним кључем

0:03:14.578,0:03:18.840
користи за успостављање безбедног кључа између веб прегледача и веб сервера.

0:03:18.840,0:03:22.898
Шифровање јавним кључем је такође јако корисно код неинтерактивних апликација,

0:03:22.898,0:03:26.390
када било ко на свету, неинтерактивно, треба да пошаље поруку Алиси,

0:03:26.390,0:03:30.653
може да шифрује поруку користећи Алисин јавни кључ, а Алиса може да је дешифрује

0:03:30.653,0:03:36.105
и поврати отворени текст. Да вас подсетим мало детаљније

0:03:36.105,0:03:40.347
шта је систем за шифровање јавним кључем. Састоји се из три алгоритма, G, E и D.

0:03:40.347,0:03:44.431
G је алгоритам за стварање кључа, који у основи

0:03:44.431,0:03:48.672
ствара пар кључева, јавни и тајни. Као што је овде записано, G нема

0:03:48.672,0:03:53.018
улазне вредности, мада у стварности G заправо има једну улазну величину, такозвани

0:03:53.018,0:03:57.260
безбедоносни параметар, којим се одређује дужина кључева који се стварају

0:03:57.260,0:04:01.731
алгоритмом. Затим постоје алгоритам шифровања, као и обично, он узима

0:04:01.731,0:04:06.051
јавни кључ и поруку и производи шифрат, и алгоритам дешифровања,

0:04:06.051,0:04:10.530
који узима одговарајући тајни кључ и шифрат и производи одговарајућу поруку.

0:04:10.530,0:04:14.955
Као и обично, због усаглашености, кажемо да ако шифрујемо поруку под

0:04:14.955,0:04:19.380
датим јавним кључем, и затим је дешифрујемо одговарајућим тајним кључем, треба да

0:04:19.380,0:04:23.852
добијемо изворну поруку. А сада, шта значи за шифовање јавним кључем да буде безбедно?

0:04:23.852,0:04:27.913
Почећу од дефинисања безбедности од прислушкивања.

0:04:27.913,0:04:32.002
А затим ћемо да дефинишемо безбедност од активних напада.

0:04:32.002,0:04:36.237
Безбедност од прислушкивања дефинишемо јако слично као у симетричном случају,

0:04:36.237,0:04:40.626
који смо видели прошле недеље, зато ћу ово да пређем јако брзо.

0:04:40.626,0:04:44.808
Нападачка игра се дефинише на следећи начин. Дефинисали смо ова два огледа,

0:04:44.808,0:04:49.249
оглед нула и један. У оба огледа, изазивач

0:04:49.249,0:04:52.965
ствара пар од јавног и тајног кључа. Он ће да преда јавни кључ

0:04:52.965,0:04:57.342
нападачу. Нападач ће да избаци две поруке, m0 и m1,

0:04:57.342,0:05:01.663
исте дужине, и да добије натраг било шифровану m0 или

0:05:01.663,0:05:06.039
шифовану m1. У огледу 0 он добија шифровану m0, а у огледу 1,

0:05:06.039,0:05:10.748
шифровану m1. А затим нападач треба да каже

0:05:10.748,0:05:15.240
коју је добио - да ли је добио шифровану m0 или m1?

0:05:15.240,0:05:19.676
Дакле то је игра, нападач добија само један шифрат. То се поклапа

0:05:19.676,0:05:24.226
са нападом прислушкивања, када је нападач једноставно прислушкивао тај шифрат с.

0:05:24.226,0:05:28.719
А његов циљ је да каже да ли је шифрат с шифровање од m0 или од m1.

0:05:28.719,0:05:34.221
Није дозвољено никакво петљање у сам шифрат с за сада. Као и обично, кажемо да је

0:05:34.221,0:05:38.206
шема за шифровање јавним кључем семантички безбедна, ако нападач не може

0:05:38.206,0:05:42.085
да разликује оглед 0 од огледа 1. Другим речима, не може да каже

0:05:42.085,0:05:47.757
да ли је добио шифровање од m0 или од m1. Пре него што пређемо

0:05:47.757,0:05:52.311
на активне нападе, желим да напоменем у каквом су односу дефиниција коју смо

0:05:52.311,0:05:56.105
управо видели, и дефиниција безбедности од прислушкивања за симетричне шифре.

0:05:56.105,0:06:00.438
Ако се сећате, када смо говорили о безбедности од прислушкивања за симетричне шифре,

0:06:00.438,0:06:04.771
разликовали смо случај када је кључ коришћен једном, и случај када је

0:06:04.771,0:06:08.998
коришћен више пута. У ствари, видели смо да постоји јасна

0:06:08.998,0:06:13.357
разлика. На пример, једнократна бележница је безбедна ако се кључ користи само једном

0:06:13.357,0:06:17.382
за шифровање једне поруке, али није безбедна ако се кључ користи за шифровање

0:06:17.382,0:06:21.358
више порука. Имали смо две различите дефиниције, ако се сећате, имали смо дефиницију

0:06:21.358,0:06:25.383
за једнократну безбедност, и посебну дефиницију, која је

0:06:25.383,0:06:29.700
строжа, када је кључ коришћен више пута. Дефиниција коју сам вам показао на претходном

0:06:29.700,0:06:34.043
слајду је јако слична дефиницији једнократне безбедности

0:06:34.043,0:06:38.499
симетричних шифара. Заправо се испоставља да, код шифровања јавним кључем,

0:06:38.499,0:06:43.124
ако је систем безбедан под једнократним кључем, он је безбедан и под вишекратним кључем.

0:06:43.124,0:06:47.929
Другим речима, не морамо да изричито дамо нападачу могућност да

0:06:47.929,0:06:53.171
захтева шифровање порука по избору, зато што би он могао да створи

0:06:53.171,0:06:57.870
та шифровања и сам. Он располаже јавним кључем, и сходно томе може да самостално

0:06:57.870,0:07:04.672
шифрује коју год поруку жели. Из тога произилази да се сваки пар јавног и тајног кључа

0:07:04.672,0:07:09.289
у извесном смислу користи за шифровање више порука, зато што је нападач

0:07:09.289,0:07:13.905
могао да шифрује много, много порука по свом избору

0:07:13.905,0:07:18.891
коришћењем датог јавног кључа који смо му дали у првом кораку. Последица тога је

0:07:18.891,0:07:23.692
да је дефиниција једнократне безбедности довољна да подразумева вишекратну безбедност,

0:07:23.692,0:07:28.801
због чега овај појам називамо нераспознавањем под нападом са произвољним

0:07:28.801,0:07:34.012
отвореним текстом. Ово је само мања напомена којом објашњавамо зашто нам у поставци за јавно

0:07:34.012,0:07:37.770
шифровање не треба сложенија дефиниција да обухватимо

0:07:37.770,0:07:42.515
безбедност од прислушкивања. Сада када смо разумели ову безбедност,

0:07:42.515,0:07:47.343
погледајмо моћније противнике који могу да почине активне нападе.

0:07:47.343,0:07:51.585
Конкретно, погледајмо пример е-поште. Овде имамо нашег пријатеља Боба

0:07:51.585,0:07:56.228
који жели да пошаље писмо својој пријатељици Каролини. Каролина има

0:07:56.228,0:08:00.699
налог на Г-мејлу. Ово ради тако што се писмо шаље

0:08:00.699,0:08:05.514
Г-мејл серверу, шифровано. Г-мејл сервер дешифрује писмо, погледа ко је прималац,

0:08:05.514,0:08:09.297
и затим, ако је прималац Каролина,

0:08:09.297,0:08:13.653
прослеђује писмо Каролини. Ако је прималац нападач,

0:08:13.653,0:08:18.573
прослеђује писмо нападачу. Ово личи на прави начин рада Г-мејла,

0:08:18.573,0:08:23.441
зато што би пошиљалац послао писмо шифровано путем SSL-a Г-мејл серверу,

0:08:23.441,0:08:28.087
сервер би отклонио SSL и проследио писмо

0:08:28.087,0:08:33.081
одговарајућем примаоцу. Претпоставимо сада да Боб шифрује писмо коришћењем система

0:08:33.081,0:08:37.764
који омогућава нападачу да мења шифрат непримећен.

0:08:37.764,0:08:42.387
На пример, замислимо да је писмо шифровано коришћењем бројача, или нечим сличним.

0:08:42.387,0:08:47.070
Тада када нападач пресретне писмо, он може да промени примаоца,

0:08:47.070,0:08:50.732
тако да је прималац сада нападач@gmail.com, а знамо да је код

0:08:50.732,0:08:55.415
бројача ово врло лако да се уради. Нападач зна да је

0:08:55.415,0:09:00.278
писмо упућено Каролини, занима га само тело писма.

0:09:00.278,0:09:04.226
Лако може да промени примаоца писма на нападач@gmail.com, и сада када сервер

0:09:04.226,0:09:08.129
прими писмо, он га дешифрује, види да је прималац наводно нападач,

0:09:08.129,0:09:12.033
и прослеђује писмо нападачу. И сада нападач може

0:09:12.033,0:09:16.022
да прочита тело писма које је било упућено Каролини.

0:09:16.022,0:09:21.198
Ово је класичан пример активног напада, и приметићете да је нападач овде могао

0:09:21.198,0:09:26.174
да дешифрује сваки шифрат где је прималац "за: нападач".

0:09:26.174,0:09:31.548
Дакле сваки шифрат где отворени текст почиње речима "за: нападач".

0:09:31.548,0:09:36.657
Дакле циљ нам је да развијемо системе са јавним кључем који су безбедни, чак и ако нападач може

0:09:36.657,0:09:42.999
да мења шифрат и дешифрује извесне шифрате. Још једном желим да нагласим

0:09:42.999,0:09:47.612
да је овде циљ нападача да добије тело поруке.

0:09:47.612,0:09:52.055
Нападач већ зна да је писмо намењено Каролини. Све што је морао да уради је

0:09:52.055,0:09:56.863
да промени примаоца. Овај напад мењањем шифрата подстиче

0:09:56.863,0:10:01.620
дефинисање безбедности под произвољним шифратом. Ово је у ствари стандард за појам

0:10:01.620,0:10:07.462
безбедности код шифровања јавним кључем. Да вам објасним како се овде врши напад.

0:10:07.462,0:10:11.899
Као што сам рекао, циљ нам је да направимо системе који су безбедни под овим врло затвореним

0:10:11.899,0:10:15.756
појмом шифровања. Дакле имамо шему шифровања (G, E, D). Рецимо

0:10:15.756,0:10:20.140
да је дефинисана над простором порука и шифрата (М, С), и као и обично

0:10:20.140,0:10:24.313
дефинисаћемо два огледа, оглед 0 и 1.

0:10:24.313,0:10:28.222
Дакле b нам говори да ли изазивач имплементира оглед 0 или 1.

0:10:28.222,0:10:32.659
Изазивач почиње тако што ствара јавни кључ и тајни кључ, а затим даје

0:10:32.659,0:10:37.254
јавни кључ нападачу. Сада нападач може да каже: "Ево ти гомила

0:10:37.254,0:10:41.611
шифрата, молим да ми их дешифрујеш." Дакле овде нападач подноси

0:10:41.611,0:10:46.452
шифрат с1, и добија дешифровање шифрата с1, наиме m1.

0:10:46.452,0:10:51.414
Може да ово уради опет и опет, дакле подноси шифрат с2, и добија дешифровање

0:10:51.414,0:10:56.195
а то је m2, шифрат с3, и добија дешифровање m3, и тако даље.

0:10:56.195,0:11:00.188
Коначно нападач каже: "Завршили смо са фазом упита", и сада

0:11:00.188,0:11:04.485
подноси две поруке подједнаке дужине, m0 и m1 као и обично,

0:11:04.485,0:11:08.820
и прима као одговор шифрат с, који је шифровано

0:11:08.820,0:11:13.052
m0 или m1, у зависности од тога да ли смо у огледу 0 или 1.

0:11:13.052,0:11:17.003
Сада нападач може да настави да издаје упите у виду

0:11:17.003,0:11:21.063
шифрата. Дакле може да настави да издаје захтеве за дешифровањем. Дакле он поднесе

0:11:21.063,0:11:25.447
шифрат, и добије дешифровање шифрата, али наравно

0:11:25.447,0:11:29.994
мора да постоји ограничење. Када би нападач могао да поднесе произвољни шифрат,

0:11:29.994,0:11:34.270
наравно да би могао да добије изазов. Само би требало да поднесе

0:11:34.270,0:11:38.506
шифрат с из изазова као упит који треба да се дешифрује. И биће му речено

0:11:38.506,0:11:42.665
да ли је у фази изазова добио шифроване m0 или m1.

0:11:42.665,0:11:46.825
Зато овде стављамо ограничење, које каже да нападач може да поднесе било који

0:11:46.825,0:11:51.031
шифрат осим шифрата изазова. Дакле нападач

0:11:51.031,0:11:55.034
може да затражи дешифровање било којег шифрата по свом избору

0:11:55.034,0:11:59.297
осим шифрата изазова. Али и поред тога што су му дата сва ова дешифровања, и даље

0:11:59.297,0:12:03.196
не би требало да може да каже да ли му је враћена шифрована m0

0:12:03.196,0:12:09.212
или m1. Примећујете да је ово јако затворена дефиниција, која

0:12:09.212,0:12:14.113
даје нападачу већу моћ од оне коју смо видели на претходном слајду. Претходно је

0:12:14.113,0:12:18.710
нападач могао само да дешифрује поруке у којима је отворени текст почињао речима

0:12:18.710,0:12:23.611
"за: нападач". Овде, кажемо да нападач може да дешифрује произвољни шифрат,

0:12:23.611,0:12:29.717
докле год је он различит од шифрата изазова, с. А његов циљ

0:12:29.717,0:12:34.094
је да каже да ли је шифрат изазова шифровање од m0

0:12:34.094,0:12:37.918
или од m1. Као и обично, ако то не може, другим речима,

0:12:37.918,0:12:42.351
ако је његово понашање у огледу 0 исто као и понашање у огледу 1,

0:12:42.351,0:12:46.839
дакле ако није успео да разликује шифровање од m0 од шифровања од m1,

0:12:46.839,0:12:51.219
иако је имао сву ову моћ, тада кажемо да је систем безбедан

0:12:51.219,0:12:55.877
под произвољним шифратима - ССА безбедан. Понекад постоји акроним

0:12:55.877,0:13:00.596
за ову нераспознатљивост под нападом произвољним шифратима, али ја ћу да

0:13:00.596,0:13:05.745
кажем само ССА безбедан. Погледајмо сада како ово обухвата пример са е-поштом који смо видели

0:13:05.745,0:13:10.587
раније. Дакле претпоставимо да је систем шифровања који се користи такав, да имајући

0:13:10.587,0:13:15.429
само шифру поруке, нападач може да промени примаоца

0:13:15.429,0:13:20.129
од Алисе на, рецимо, Чарлија. Ево како тада добијамо ССА игру.

0:13:20.129,0:13:25.033
У првом кораку, нападач наравно добија јавни кључ. А тада нападач

0:13:25.033,0:13:29.578
издаје две поруке исте дужине, наиме у првој поруци,

0:13:29.578,0:13:33.943
тело је 0, а у другој 1. Али обе поруке су

0:13:33.943,0:13:39.890
намењене Алиси. Као одговор, он добија шифрат изазова, с.

0:13:39.890,0:13:45.130
Дакле сада имамо наш шифрат изазова с. Сада нападач

0:13:45.130,0:13:49.961
користи своју способност да промени примаоца.

0:13:49.961,0:13:55.269
Он ће да пошаље шифрат с', где је с' шифрована

0:13:55.269,0:14:01.760
порука Чарлију, чије је тело управо тело изазова, b. Дакле ако се сећате, b

0:14:01.760,0:14:07.822
је или 0 или 1. Пошто је отворени текст различит, знамо да

0:14:07.822,0:14:12.486
и шифрат мора да буде различит. Дакле с' мора да буде различито

0:14:12.486,0:14:17.206
од шифрата изазова, с. Дакле с' мора да буде различито од с.

0:14:17.206,0:14:21.758
Сходно томе, изазивач мора да дешифрује, у складу да дефиницијом ССА игре.

0:14:21.758,0:14:26.141
Изазивач мора да дешифрује било који шифрат који није једнак шифрату

0:14:26.141,0:14:30.648
изазова. Дакле изазивач дешифрује, и даје нападачу m'.

0:14:30.648,0:14:35.256
Дакле дао је нападачу b, и сада нападач може да избаци вредност за b

0:14:35.256,0:14:40.293
и да добије игру, са предношћу 1. Дакле предност код овакве шеме је 1.

0:14:40.293,0:14:45.143
Дакле једноставно зато што је нападач могао да промени у шифрату изазова

0:14:45.146,0:14:49.999
примаоца поруке, то му омогућава да победи у ССА игри са

0:14:49.999,0:14:55.003
предношћу 1. Дакле као што сам рекао, безбедност под произвољним шифратом је управо

0:14:55.003,0:14:59.327
исправни појам безбедности за системе шифровања јавним кључем.

0:14:59.327,0:15:03.651
Ово је јако занимљив појам - иако нападач има могућност

0:15:03.651,0:15:07.839
да дешифрује све што пожели, осим шифрата изазова, он и даље не може

0:15:07.839,0:15:12.028
да открије који је шифрат изазова. Дакле циљ до краја ове целине

0:15:12.028,0:15:16.275
и заправо и следеће јесте да изградимо ССА безбедне системе.

0:15:16.275,0:15:20.093
Изузетно је што је ово могуће, и показаћу вам

0:15:20.093,0:15:24.310
како се то ради. У ствари ССА системи које ћемо да изградимо

0:15:24.310,0:15:28.579
су управо они који се користе у стварности. Сваки пут када је неки систем покушао да примени

0:15:28.737,0:15:33.007
неки механизам шифровања јавним кључем који није био ССА безбедан, неко би пронашао

0:15:33.007,0:15:37.487
напад и успевао да га разбије. Видећемо неке примере ових напада

0:15:37.487,0:15:39.280
у неколико следећих одељака.