WEBVTT

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

00:08:23.441 --> 00:08:28.087
сервер би отклонио SSL и проследио писмо

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

00:15:37.487 --> 00:15:39.280
у неколико следећих одељака.