WEBVTT 00:00:00.000 --> 00:00:03.911 Намера ми је да вам у следећих неколико одељака покажем да ако користимо безбедни PRG, 00:00:03.911 --> 00:00:07.892 добијамо безбедну шифру тока. Пре свега морамо да дефинишемо 00:00:07.892 --> 00:00:11.679 шта подразумевамо под безбедношћу шифре тока? Кад год дефинишемо безбедност, 00:00:11.679 --> 00:00:15.174 увек је дефинишемо у смислу тога шта нападач може да уради, и шта 00:00:15.174 --> 00:00:18.670 покушава да уради. У вези са шифрама тока, сетите се да се оне користе искључиво 00:00:18.670 --> 00:00:22.737 са једнократним кључем, и услед тога највише што нападач икад може да види 00:00:22.737 --> 00:00:26.754 јесте један шифрат шифрован коришћењем кључем који користимо. Дакле 00:00:26.754 --> 00:00:30.772 ограничавамо нападачеву могућност на прибављање само једног шифрата. 00:00:30.772 --> 00:00:34.641 У ствари, касније ћемо да дозволимо нападачу да уради много, много више, 00:00:34.641 --> 00:00:38.460 али за сада ћемо да му дамо само један шифрат. И желимо да видимо 00:00:38.460 --> 00:00:42.560 шта подразумевамо под безбедношћу шифре? Прва дефиниција 00:00:42.560 --> 00:00:46.892 која нам пада на памет, јесте да можда желимо да захтевамо да нападач 00:00:46.892 --> 00:00:50.718 не може да прибави тајни кључ. Дакле на основу шифрата 00:00:50.718 --> 00:00:54.609 не треба да будете у стању да прибавите тајни кључ. Али то је лоша дефиниција 00:00:54.609 --> 00:00:58.717 зато што, погледајте следећу сјајну шифру, где шифрујемо 00:00:58.717 --> 00:01:02.855 поруку коришћењем кључа k тако што једноставно избацимо поруку. 00:01:02.855 --> 00:01:07.427 Наравно ово је сјајна шифра, не ради ништа са поруком 00:01:07.427 --> 00:01:12.000 осим што шифрат избаци као саму поруку. Ово није нарочито добро шифровање; 00:01:12.000 --> 00:01:16.029 међутим, на основу шифрата, тј. поруке, сироти нападач 00:01:16.029 --> 00:01:20.493 не може да прибави кључ, зато што му кључ није познат. Услед тога ова шифра, 00:01:20.493 --> 00:01:24.630 која очигледно није безбедна, била би сматрана безбедном под овим 00:01:24.793 --> 00:01:28.636 захтевима безбедности. Дакле оваква дефиниција не би ваљала. 00:01:28.636 --> 00:01:32.317 Дакле прибављање тајног кључа је погрешан начин да се дефинише безбедност. Следеће што 00:01:32.317 --> 00:01:35.999 можемо да покушамо је да кажемо да можда нападача није брига 00:01:35.999 --> 00:01:39.680 за тајни кључ, већ га заправо занима отворени текст. Можда би требало 00:01:39.680 --> 00:01:43.518 да нападачу буде тешко да дође до целокупног отвореног текста. Али чак и то 00:01:43.518 --> 00:01:48.223 није довољно зато што, посматрајмо следећи начин шифровања. Рецимо 00:01:48.223 --> 00:01:53.436 да код овог шифровања узимамо две поруке, ја ћу да користим 00:01:53.436 --> 00:01:58.014 ове две линије да означим спајање двеју порука, m0 || m1 значи 00:01:58.014 --> 00:02:03.100 спајање m0 и m1. Рецимо да ова шифра даје 00:02:03.100 --> 00:02:08.060 m0 као отворену, и спаја то са шифром од m1. Можда чак и 00:02:08.060 --> 00:02:13.337 коришћењем једнократне бележнице. Дакле овде се нападачу даје један 00:02:13.337 --> 00:02:17.478 шифрат, а његов циљ је да дође до целокупног отвореног текста. Али 00:02:17.478 --> 00:02:21.702 сироти нападач то не може да учини зато што, можда смо шифровали m1 коришћењем 00:02:21.702 --> 00:02:25.872 једнократне бележнице, тако да нападач не може да дође до m1 зато што, знамо да је 00:02:25.872 --> 00:02:30.043 једнократна бележница безбедна када се користи код само једног шифрата. Дакле ова конструкција 00:02:30.043 --> 00:02:34.055 би задовољила дефиницију, али нажалост ово очигледно није безбедно 00:02:34.055 --> 00:02:37.962 шифровање, зато што је процурило пола отвореног текста. 00:02:37.962 --> 00:02:42.185 m0 је потпуно доступно нападачу, тако да, мада не може да дође до 00:02:42.185 --> 00:02:46.462 целокупног отвореног текста, могао би да поврати већину отвореног текста, а то очигледно 00:02:46.462 --> 00:02:50.658 није безбедно. Наравно већ знамо решење за ово, говорили смо 00:02:50.658 --> 00:02:54.747 о Шеноновој дефиницији савршене безбедности, где је Шенонова идеја била 00:02:54.747 --> 00:02:58.835 да када нападач пресретне шифрат, не треба да сазна никакву 00:02:58.835 --> 00:03:02.818 информацију о отвореном тексту. Не треба чак ни да сазна ни један бит 00:03:02.818 --> 00:03:07.221 отвореног текста, нити сме да му буде могуће да предвиди 00:03:07.221 --> 00:03:11.205 мали део отвореног текста; никакву информацију о отвореном тексту. 00:03:11.205 --> 00:03:14.926 Подсетимо се укратко Шеноновог појма савршене безбедности 00:03:14.926 --> 00:03:19.442 рекли смо да шифра има савршену безбедност 00:03:19.442 --> 00:03:25.069 ако, када имамо две поруке исте дужине, расподела 00:03:25.069 --> 00:03:30.167 шифрата - ако одаберемо насумично кључ и посматрамо расподелу 00:03:30.167 --> 00:03:34.838 шифрата, ако шифрујемо m0, добијамо потпуно исту расподелу као када 00:03:34.838 --> 00:03:39.257 шифрујемо m1. Наслућујемо овде да ако нападач посматра шифрат, 00:03:39.257 --> 00:03:43.839 не зна да ли је потекао из расподеле која је последица шифровања 00:03:43.839 --> 00:03:48.203 са m0 или из расподеле која је последица шифровања са m1. 00:03:48.203 --> 00:03:52.513 Услед тога, он не може да одреди да ли смо шифровали m0 или m1. И то важи за све 00:03:52.513 --> 00:03:56.877 поруке истих дужина, и захваљујући томе сироти нападач не зна 00:03:56.877 --> 00:04:01.212 која порука је била шифрована. Наравно већ смо рекли да је ова дефиниција 00:04:01.212 --> 00:04:05.400 превише јака, у смислу да захтева врло дугачке кључеве, и ако шифра има кратке кључеве 00:04:05.400 --> 00:04:09.535 никако не може да задовољи ову дефиницију. Конкретно, шифра тока 00:04:09.535 --> 00:04:14.328 не може да задовољи ову дефиницију. Покушајмо да мало ослабимо ову дефиницију, 00:04:14.328 --> 00:04:19.114 сетимо се претходног одељка. Можемо да кажемо да уместо да захтевамо 00:04:19.114 --> 00:04:23.841 да две расподеле буду потпуно истоветне, ми захтевамо да 00:04:23.841 --> 00:04:28.686 две расподеле буду рачунски нераспознатљиве. Другим речима, сироти, 00:04:28.863 --> 00:04:33.353 ефикасни нападач не може да разликује две расподеле иако 00:04:33.353 --> 00:04:37.815 расподеле могу да буду врло различите. На основу узорка 00:04:37.815 --> 00:04:42.580 једне и друге расподеле, нападач не може да каже 00:04:42.580 --> 00:04:47.120 из које расподеле је добио узорак. Испоставља се да је ова дефиниција 00:04:47.120 --> 00:04:51.716 скоро одговарајућа, али је и даље мало прејака, и даље не може да се задовољи, 00:04:51.716 --> 00:04:56.200 дакле морамо да додамо још једно ограничење, а то је да, уместо да кажемо да ова 00:04:56.200 --> 00:05:00.797 дефиниција треба да важи за свако m0 и m1, она треба да важи само за парове m0, m1 00:05:00.797 --> 00:05:05.208 које нападач може да изложи. То нас у ствари 00:05:05.208 --> 00:05:10.038 доводи до дефиниције семантичке безбедности. Још једном, ово је семантичка 00:05:10.038 --> 00:05:15.050 безбедност за једнократне кључеве, другим речима, када нападач добија само један 00:05:15.050 --> 00:05:19.819 шифрат. Дакле дефинишемо семантичку безбедност тако што дефинишемо два огледа, 00:05:19.819 --> 00:05:24.562 оглед 0 и оглед 1. У општем случају, посматраћемо 00:05:24.562 --> 00:05:29.230 их као оглед (b), где b може да буде 0 или 1. 00:05:29.230 --> 00:05:32.890 Оглед се дефинише на следећи начин, имамо нападача који 00:05:32.890 --> 00:05:37.161 покушава да разбије систем - нападач А, који је аналоган статистичким тестовима 00:05:37.161 --> 00:05:41.279 у свету псеудослучајних генератора. Изазивач ради 00:05:41.279 --> 00:05:45.093 следеће, постоје два изазивача, али они 00:05:45.093 --> 00:05:49.414 су толико слични, да можемо да их опишемо као истог изазивача који у једном случају 00:05:49.414 --> 00:05:53.634 узима на улазу битове постављене на 0, а у другом случају 00:05:53.634 --> 00:05:57.193 постављене на 1. Да вам покажем шта изазивач ради. Најпре 00:05:57.193 --> 00:06:01.349 он бира случајно кључ, а затим нападач 00:06:01.349 --> 00:06:06.076 избацује две поруке, m0 и m1. Ово је јавни 00:06:06.076 --> 00:06:11.039 пар порука, за које нападач жели да буде изазван, и као и обично, не 00:06:11.039 --> 00:06:15.766 покушавамо да сакријемо дужину порука, захтевамо да буду једнаке дужине. 00:06:15.766 --> 00:06:21.643 Тада изазивач избаци шифровану m0 00:06:21.643 --> 00:06:25.890 или шифровану m1, у огледу 0 изазивач избацује 00:06:25.890 --> 00:06:30.301 шифровану m0, а у огледу 1 шифровану m1. 00:06:30.301 --> 00:06:34.385 У томе је разлика између огледа. 00:06:34.385 --> 00:06:38.796 Нападач покушава да погоди да ли је добио шифровану m0 00:06:38.796 --> 00:06:44.051 или шифровану m1. Ево мало ознака. Дефинишимо 00:06:44.051 --> 00:06:50.260 догађај Wb као догађај када за оглед b нападач избацује 1. 00:06:50.260 --> 00:06:55.084 Дакле то је такав догађај, да у огледу 0 W0 значи да 00:06:55.084 --> 00:07:00.342 је нападач избацио 1, а у огледу 1 W1 значи да је нападач избацио 1. 00:07:00.342 --> 00:07:05.291 Сада можемо да дефинишемо предност овог нападача, и кажемо да је 00:07:05.291 --> 00:07:10.425 предност семантичке безбедности нападача А над шемом Е 00:07:10.425 --> 00:07:15.497 разлика између вероватноћа ова два догађаја. Другим речима 00:07:15.497 --> 00:07:20.136 посматрамо да ли се нападач понаша различито када добије 00:07:20.136 --> 00:07:24.818 шифровану m0 у односу на то када добије шифровану m1. Желим да будем 00:07:24.818 --> 00:07:29.201 сигуран да је ово јасно, па ћу да поновим. Дакле у огледу 0 добио 00:07:29.201 --> 00:07:33.530 је шифровану m0, а у огледу 1 шифровану m1, 00:07:33.530 --> 00:07:37.700 и сада нас занима да ли нападач избацује 1 или не, 00:07:37.700 --> 00:07:42.356 у овим огледима. Ако у оба огледа нападач избацује 1 са 00:07:42.356 --> 00:07:47.013 истом вероватноћом, то значи да нападач није могао да разликује 00:07:47.013 --> 00:07:51.549 два огледа. Оглед 0 изгледа нападачу исто 00:07:51.549 --> 00:07:56.206 као оглед 1, зато што у оба случаја враћа 1 са истом вероватноћом. 00:07:56.206 --> 00:08:01.286 Међутим, ако нападач може да избаци 1 у једном огледу са значајно 00:08:01.286 --> 00:08:05.761 различитом вероватноћом него у другом огледу, тада је нападач 00:08:05.761 --> 00:08:10.266 могао да разликује ова два огледа. Да искажемо ово 00:08:10.266 --> 00:08:14.455 формалније, предност, зато што је то разлика двеју 00:08:14.455 --> 00:08:18.918 вероватноћа, предност је број између 0 и 1. Ако је предност 00:08:18.918 --> 00:08:22.886 блиска нули, то значи да нападач није био у стању да разликује 00:08:22.886 --> 00:08:27.129 оглед 0 од огледа 1. Међутим ако је предност блиска јединици, 00:08:27.129 --> 00:08:31.538 то значи да је нападач био у стању да разликује оглед 0 од 00:08:31.538 --> 00:08:36.112 огледа 1, што у ствари значи да је био у стању да разликује шифровање 00:08:36.112 --> 00:08:40.299 m0 од шифровања m1. Дакле то је наша дефиниција, у ствари, 00:08:40.299 --> 00:08:44.055 то је само дефиниција предности, а дефиниција је управо 00:08:44.055 --> 00:08:47.714 оно што бисте и очекивали, кажемо да је шема симетричног шифровања 00:08:47.714 --> 00:08:52.346 семантички безбедна, ако за све "ефикасне" нападаче, 00:08:52.346 --> 00:08:56.932 ако је за све ефикасне нападаче предност занемарљива. Другим речима, 00:08:56.982 --> 00:09:01.808 не постоји ефикасан нападач који може да разликује шифровање m0 од шифровања m1, 00:09:01.808 --> 00:09:06.103 и, тиме се каже, понављам, да за ове две 00:09:06.103 --> 00:09:10.759 поруке нападач је био у стању да прикаже да није био у стању да разликује 00:09:10.759 --> 00:09:15.064 ове две расподеле. Желим да вам покажем, ово је заправо врло 00:09:15.064 --> 00:09:19.595 елегантна дефиниција, не мора да тако изгледа одмах, али желим да вам покажем неке 00:09:19.595 --> 00:09:24.410 последице ове дефиниције, а видећете зашто је ова дефиниција таква каква јесте. 00:09:24.410 --> 00:09:28.601 Погледајмо неке примере. Први пример је - претпоставимо 00:09:28.601 --> 00:09:33.190 да имамо разбијену шему шифровања, другим речима, претпоставимо да имамо нападача А 00:09:33.190 --> 00:09:38.285 који некако, добивши шифрат, увек може да открије бит најмање 00:09:38.285 --> 00:09:44.149 тежине из отвореног текста. Дакле добивши шифру од m0, овај нападач 00:09:44.149 --> 00:09:48.799 може да добије бит најмање тежине у m0. Ово је јако лоша 00:09:48.799 --> 00:09:52.911 шема шифровања, зато што одаје бит најмање тежине из 00:09:52.911 --> 00:09:57.128 отвореног текста самим шифратом. Желим да вам покажем да ова шема није 00:09:57.128 --> 00:10:01.609 семантички безбедна, чиме се показује да ако систем јесте семантички 00:10:01.609 --> 00:10:05.931 безбедан, не постоји нападач ове врсте. Погледајмо зашто овај систем 00:10:05.931 --> 00:10:10.254 није семантички безбедан. Ми ћемо да користимо 00:10:10.254 --> 00:10:14.366 нашег нападача, који може да открије битове најмање тежине, ми ћемо да 00:10:14.366 --> 00:10:18.372 га користимо да разбијемо семантичку безбедност, то јест да разликујемо 00:10:18.372 --> 00:10:22.755 оглед 0 од огледа 1. Ево шта ћемо да урадимо. 00:10:22.755 --> 00:10:26.987 Ми смо алгоритам В, а овај алгоритам В ће да користи 00:10:26.987 --> 00:10:31.165 алгоритам А у свом телу. Дакле прво што ће да се деси је, 00:10:31.165 --> 00:10:35.608 наравно изазивач ће да одабере насумични кључ, и прво што ће да се деси је 00:10:35.608 --> 00:10:39.762 да ћемо да избацимо две поруке, 00:10:39.762 --> 00:10:43.493 а које ће да имају различите битове најмање тежине. 00:10:43.493 --> 00:10:47.727 Једна ће да се завршава са 0, а друга са 1. 00:10:47.727 --> 00:10:51.205 И шта ће сада изазивач да уради? Он ће да нам да 00:10:51.205 --> 00:10:55.238 шифровање било од m0 било од m1, у зависности од тога да ли смо у огледу 0 00:10:55.238 --> 00:10:59.120 или у огледу 1. А тада ћемо само да проследимо овај шифрат нападачу, 00:10:59.120 --> 00:11:03.871 дакле нападачу А. А које је својство нападача А? Добивши шифрат, 00:11:03.871 --> 00:11:08.505 нападач А може да нам каже који је бит најмање тежине отвореног текста. 00:11:08.505 --> 00:11:13.374 Другим речима, нападач ће да избаци бит најмање тежине од m0 или m1, 00:11:13.374 --> 00:11:17.892 а то је практично бит b. И затим ћемо само да 00:11:17.892 --> 00:11:23.050 избацимо то као наш погодак, назовимо то b'. Дакле овим 00:11:23.050 --> 00:11:28.376 се описује семантичка безбедност нападача. А ви ми кажите шта се предност 00:11:28.376 --> 00:11:33.593 над семантичком безбедношћу код овог нападача? Па погледајмо: у огледу 0, која је 00:11:33.593 --> 00:11:38.775 вероватноћа да нападач В избацује 1? Дакле у огледу 0 се увек 00:11:38.775 --> 00:11:43.704 добија шифровање од m0, и зато нападач А увек избацује 00:11:43.704 --> 00:11:48.633 бит најмање тежине од m0, а то је увек 0. У огледу 00:11:48.633 --> 00:11:53.120 0, В увек избацује 0. Дакле вероватноћа да ће да избаци 1 је нула. 00:11:53.120 --> 00:11:57.827 Међутим у огледу 1, добијамо шифровану m1. Дакле колико је вероватно да ће 00:11:57.827 --> 00:12:02.783 нападач В да избаци 1 у огледу 1? Па, увек ће да избаци 1, 00:12:02.783 --> 00:12:07.428 због својства алгоритма А. И услед тога, предност је практично 1. 00:12:07.428 --> 00:12:12.384 Дакле то је велика предност, највећа што може да буде. Што значи да је овај 00:12:12.384 --> 00:12:17.091 нападач потпуно разбио систем. Дакле под семантичком 00:12:17.091 --> 00:12:22.295 безбедношћу, просто сазнавање бита најмање тежине је довољно да потпуно 00:12:22.295 --> 00:12:27.187 разбије систем - под дефиницијом семантичке безбедности. Занимљива ствар 00:12:27.187 --> 00:12:32.388 овде је наравно да се не ради само о биту најмање тежине, 00:12:32.388 --> 00:12:37.117 у ствари, било који бит поруке, на пример, бит највеће тежине, 00:12:37.117 --> 00:12:42.040 седми бит, можда XOR свих битова поруке, итд, 00:12:42.040 --> 00:12:46.552 било каква информација, било који бит отвореног текста који може да 00:12:46.552 --> 00:12:50.814 се сазна, значио би да систем није семантички безбедан. 00:12:50.814 --> 00:12:55.532 Дакле све што нападач треба да уради јесте да се појави са две поруке, 00:12:55.532 --> 00:13:00.249 m0 и m1, које су такве да је код једне од њих, то што сазнаје има вредност 0, 00:13:00.249 --> 00:13:04.626 а код друге има вредност 1. На пример, А је сазнао XOR 00:13:04.626 --> 00:13:08.775 битова поруке - тада m0 и m1 само треба да имају 00:13:08.775 --> 00:13:13.265 различити XOR свих битова у поруци, и нападач А би могао 00:13:13.265 --> 00:13:18.174 да разбије семантичку безбедност. Практично ако је шифра 00:13:18.174 --> 00:13:23.203 семантички безбедна, никаква информација се не открива 00:13:23.203 --> 00:13:27.392 ефикасном нападачу. То је управо и појам савршене тајности, али 00:13:27.392 --> 00:13:31.318 примењен само на ефикасне нападаче уместо на све нападаче. 00:13:31.318 --> 00:13:35.045 Следеће што желим да вам покажем је да је једнократна бележница 00:13:35.045 --> 00:13:38.821 семантички безбедна, и боље би било да јесте, зато што је 00:13:38.821 --> 00:13:42.773 и више од тога, она је савршено безбедна. Погледајмо зашто ово важи. 00:13:42.773 --> 00:13:47.010 Још једном посматрамо овакве огледе, дакле претпоставимо да нападач претендује 00:13:47.010 --> 00:13:51.449 да разбије семантичку безбедност једнократне бележнице. Он ће најпре 00:13:51.449 --> 00:13:55.874 да избаци две поруке, m0 и m1, исте дужине. 00:13:55.874 --> 00:13:59.667 Шта добија као изазов? Добија или шифровану 00:13:59.667 --> 00:14:03.988 m0 или шифровану m1, под једнократном бележницом. 00:14:03.988 --> 00:14:07.886 И покушава да разликује ове две могуће шифрате које добија. 00:14:07.886 --> 00:14:12.259 У огледу 0, добија шифровану m0, а у огледу 1, добија 00:14:12.259 --> 00:14:16.579 шифровану m1. Поставља се питање, која је предност нападача А 00:14:16.579 --> 00:14:21.297 над једнократном бележницом? Подсећам вас да је својство једнократне бележнице 00:14:21.297 --> 00:14:26.208 да је k XOR m0 са расподелом истоветном са k XOR m1. 00:14:26.208 --> 00:14:31.187 Другим речима, ово су потпуно подударне расподеле. 00:14:31.187 --> 00:14:36.026 То је својство XOR - ако XOR-ујемо случајни 00:14:36.026 --> 00:14:40.674 кључ k са било чим, m0 или m1, добијамо униформну расподелу. 00:14:40.674 --> 00:14:45.382 Дакле у оба случаја алгоритам А добија на улазу потпуно исту расподелу. Можда 00:14:45.382 --> 00:14:50.209 униформну расподелу шифрата. И зато ће да се понаша на потпуно 00:14:50.209 --> 00:14:55.036 исти начин у оба случаја, зато што добија потпуно исту расподелу на улазу. 00:14:55.036 --> 00:14:59.699 Следи да је његова предност 0, што значи да једнократна бележница јесте семантички 00:14:59.723 --> 00:15:04.148 безбедна. Занимљиво је то што, не само што је семантички безбедна, 00:15:04.148 --> 00:15:08.244 већ је семантички безбедна за све нападаче. Не морамо чак да се ограничимо 00:15:08.244 --> 00:15:12.450 на ефикасне нападаче. Нема нападача, колико год паметан био, који 00:15:12.450 --> 00:15:16.875 би могао да разликује k XOR m0 од k XOR m1, зато што су ове две 00:15:16.875 --> 00:15:21.299 расподеле истоветне. Добро, дакле једнократна бележница је семантички безбедна. 00:15:21.299 --> 00:15:25.559 Тиме смо завршили са дефиницијом семантичке безбедности, и следеће што ћемо 00:15:25.559 --> 00:15:30.093 да докажемо је да из безбедности PRG-а следи да је шифра тока 00:15:30.093 --> 00:15:31.186 семантички безбедна.