[Script Info] Title: [Events] Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text Dialogue: 0,0:00:00.00,0:00:03.91,Default,,0000,0000,0000,,Намера ми је да вам у следећих неколико одељака покажем да ако користимо безбедни PRG, Dialogue: 0,0:00:03.91,0:00:07.89,Default,,0000,0000,0000,,добијамо безбедну шифру тока. Пре свега морамо да дефинишемо Dialogue: 0,0:00:07.89,0:00:11.68,Default,,0000,0000,0000,,шта подразумевамо под безбедношћу шифре тока? Кад год дефинишемо безбедност, Dialogue: 0,0:00:11.68,0:00:15.17,Default,,0000,0000,0000,,увек је дефинишемо у смислу тога шта нападач може да уради, и шта Dialogue: 0,0:00:15.17,0:00:18.67,Default,,0000,0000,0000,,покушава да уради. У вези са шифрама тока, сетите се да се оне користе искључиво Dialogue: 0,0:00:18.67,0:00:22.74,Default,,0000,0000,0000,,са једнократним кључем, и услед тога највише што нападач икад може да види Dialogue: 0,0:00:22.74,0:00:26.75,Default,,0000,0000,0000,,јесте један шифрат шифрован коришћењем кључем који користимо. Дакле Dialogue: 0,0:00:26.75,0:00:30.77,Default,,0000,0000,0000,,ограничавамо нападачеву могућност на прибављање само једног шифрата. Dialogue: 0,0:00:30.77,0:00:34.64,Default,,0000,0000,0000,,У ствари, касније ћемо да дозволимо нападачу да уради много, много више, Dialogue: 0,0:00:34.64,0:00:38.46,Default,,0000,0000,0000,,али за сада ћемо да му дамо само један шифрат. И желимо да видимо Dialogue: 0,0:00:38.46,0:00:42.56,Default,,0000,0000,0000,,шта подразумевамо под безбедношћу шифре? Прва дефиниција Dialogue: 0,0:00:42.56,0:00:46.89,Default,,0000,0000,0000,,која нам пада на памет, јесте да можда желимо да захтевамо да нападач Dialogue: 0,0:00:46.89,0:00:50.72,Default,,0000,0000,0000,,не може да прибави тајни кључ. Дакле на основу шифрата Dialogue: 0,0:00:50.72,0:00:54.61,Default,,0000,0000,0000,,не треба да будете у стању да прибавите тајни кључ. Али то је лоша дефиниција Dialogue: 0,0:00:54.61,0:00:58.72,Default,,0000,0000,0000,,зато што, погледајте следећу сјајну шифру, где шифрујемо Dialogue: 0,0:00:58.72,0:01:02.86,Default,,0000,0000,0000,,поруку коришћењем кључа k тако што једноставно избацимо поруку. Dialogue: 0,0:01:02.86,0:01:07.43,Default,,0000,0000,0000,,Наравно ово је сјајна шифра, не ради ништа са поруком Dialogue: 0,0:01:07.43,0:01:12.00,Default,,0000,0000,0000,,осим што шифрат избаци као саму поруку. Ово није нарочито добро шифровање; Dialogue: 0,0:01:12.00,0:01:16.03,Default,,0000,0000,0000,,међутим, на основу шифрата, тј. поруке, сироти нападач Dialogue: 0,0:01:16.03,0:01:20.49,Default,,0000,0000,0000,,не може да прибави кључ, зато што му кључ није познат. Услед тога ова шифра, Dialogue: 0,0:01:20.49,0:01:24.63,Default,,0000,0000,0000,,која очигледно није безбедна, била би сматрана безбедном под овим Dialogue: 0,0:01:24.79,0:01:28.64,Default,,0000,0000,0000,,захтевима безбедности. Дакле оваква дефиниција не би ваљала. Dialogue: 0,0:01:28.64,0:01:32.32,Default,,0000,0000,0000,,Дакле прибављање тајног кључа је погрешан начин да се дефинише безбедност. Следеће што Dialogue: 0,0:01:32.32,0:01:35.100,Default,,0000,0000,0000,,можемо да покушамо је да кажемо да можда нападача није брига Dialogue: 0,0:01:35.100,0:01:39.68,Default,,0000,0000,0000,,за тајни кључ, већ га заправо занима отворени текст. Можда би требало Dialogue: 0,0:01:39.68,0:01:43.52,Default,,0000,0000,0000,,да нападачу буде тешко да дође до целокупног отвореног текста. Али чак и то Dialogue: 0,0:01:43.52,0:01:48.22,Default,,0000,0000,0000,,није довољно зато што, посматрајмо следећи начин шифровања. Рецимо Dialogue: 0,0:01:48.22,0:01:53.44,Default,,0000,0000,0000,,да код овог шифровања узимамо две поруке, ја ћу да користим Dialogue: 0,0:01:53.44,0:01:58.01,Default,,0000,0000,0000,,ове две линије да означим спајање двеју порука, m0 || m1 значи Dialogue: 0,0:01:58.01,0:02:03.10,Default,,0000,0000,0000,,спајање m0 и m1. Рецимо да ова шифра даје Dialogue: 0,0:02:03.10,0:02:08.06,Default,,0000,0000,0000,,m0 као отворену, и спаја то са шифром од m1. Можда чак и Dialogue: 0,0:02:08.06,0:02:13.34,Default,,0000,0000,0000,,коришћењем једнократне бележнице. Дакле овде се нападачу даје један Dialogue: 0,0:02:13.34,0:02:17.48,Default,,0000,0000,0000,,шифрат, а његов циљ је да дође до целокупног отвореног текста. Али Dialogue: 0,0:02:17.48,0:02:21.70,Default,,0000,0000,0000,,сироти нападач то не може да учини зато што, можда смо шифровали m1 коришћењем Dialogue: 0,0:02:21.70,0:02:25.87,Default,,0000,0000,0000,,једнократне бележнице, тако да нападач не може да дође до m1 зато што, знамо да је Dialogue: 0,0:02:25.87,0:02:30.04,Default,,0000,0000,0000,,једнократна бележница безбедна када се користи код само једног шифрата. Дакле ова конструкција Dialogue: 0,0:02:30.04,0:02:34.06,Default,,0000,0000,0000,,би задовољила дефиницију, али нажалост ово очигледно није безбедно Dialogue: 0,0:02:34.06,0:02:37.96,Default,,0000,0000,0000,,шифровање, зато што је процурило пола отвореног текста. Dialogue: 0,0:02:37.96,0:02:42.18,Default,,0000,0000,0000,,m0 је потпуно доступно нападачу, тако да, мада не може да дође до Dialogue: 0,0:02:42.18,0:02:46.46,Default,,0000,0000,0000,,целокупног отвореног текста, могао би да поврати већину отвореног текста, а то очигледно Dialogue: 0,0:02:46.46,0:02:50.66,Default,,0000,0000,0000,,није безбедно. Наравно већ знамо решење за ово, говорили смо Dialogue: 0,0:02:50.66,0:02:54.75,Default,,0000,0000,0000,,о Шеноновој дефиницији савршене безбедности, где је Шенонова идеја била Dialogue: 0,0:02:54.75,0:02:58.84,Default,,0000,0000,0000,,да када нападач пресретне шифрат, не треба да сазна никакву Dialogue: 0,0:02:58.84,0:03:02.82,Default,,0000,0000,0000,,информацију о отвореном тексту. Не треба чак ни да сазна ни један бит Dialogue: 0,0:03:02.82,0:03:07.22,Default,,0000,0000,0000,,отвореног текста, нити сме да му буде могуће да предвиди Dialogue: 0,0:03:07.22,0:03:11.20,Default,,0000,0000,0000,,мали део отвореног текста; никакву информацију о отвореном тексту. Dialogue: 0,0:03:11.20,0:03:14.93,Default,,0000,0000,0000,,Подсетимо се укратко Шеноновог појма савршене безбедности Dialogue: 0,0:03:14.93,0:03:19.44,Default,,0000,0000,0000,,рекли смо да шифра има савршену безбедност Dialogue: 0,0:03:19.44,0:03:25.07,Default,,0000,0000,0000,,ако, када имамо две поруке исте дужине, расподела Dialogue: 0,0:03:25.07,0:03:30.17,Default,,0000,0000,0000,,шифрата - ако одаберемо насумично кључ и посматрамо расподелу Dialogue: 0,0:03:30.17,0:03:34.84,Default,,0000,0000,0000,,шифрата, ако шифрујемо m0, добијамо потпуно исту расподелу као када Dialogue: 0,0:03:34.84,0:03:39.26,Default,,0000,0000,0000,,шифрујемо m1. Наслућујемо овде да ако нападач посматра шифрат, Dialogue: 0,0:03:39.26,0:03:43.84,Default,,0000,0000,0000,,не зна да ли је потекао из расподеле која је последица шифровања Dialogue: 0,0:03:43.84,0:03:48.20,Default,,0000,0000,0000,,са m0 или из расподеле која је последица шифровања са m1. Dialogue: 0,0:03:48.20,0:03:52.51,Default,,0000,0000,0000,,Услед тога, он не може да одреди да ли смо шифровали m0 или m1. И то важи за све Dialogue: 0,0:03:52.51,0:03:56.88,Default,,0000,0000,0000,,поруке истих дужина, и захваљујући томе сироти нападач не зна Dialogue: 0,0:03:56.88,0:04:01.21,Default,,0000,0000,0000,,која порука је била шифрована. Наравно већ смо рекли да је ова дефиниција Dialogue: 0,0:04:01.21,0:04:05.40,Default,,0000,0000,0000,,превише јака, у смислу да захтева врло дугачке кључеве, и ако шифра има кратке кључеве Dialogue: 0,0:04:05.40,0:04:09.54,Default,,0000,0000,0000,,никако не може да задовољи ову дефиницију. Конкретно, шифра тока Dialogue: 0,0:04:09.54,0:04:14.33,Default,,0000,0000,0000,,не може да задовољи ову дефиницију. Покушајмо да мало ослабимо ову дефиницију, Dialogue: 0,0:04:14.33,0:04:19.11,Default,,0000,0000,0000,,сетимо се претходног одељка. Можемо да кажемо да уместо да захтевамо Dialogue: 0,0:04:19.11,0:04:23.84,Default,,0000,0000,0000,,да две расподеле буду потпуно истоветне, ми захтевамо да Dialogue: 0,0:04:23.84,0:04:28.69,Default,,0000,0000,0000,,две расподеле буду рачунски нераспознатљиве. Другим речима, сироти, Dialogue: 0,0:04:28.86,0:04:33.35,Default,,0000,0000,0000,,ефикасни нападач не може да разликује две расподеле иако Dialogue: 0,0:04:33.35,0:04:37.82,Default,,0000,0000,0000,,расподеле могу да буду врло различите. На основу узорка Dialogue: 0,0:04:37.82,0:04:42.58,Default,,0000,0000,0000,,једне и друге расподеле, нападач не може да каже Dialogue: 0,0:04:42.58,0:04:47.12,Default,,0000,0000,0000,,из које расподеле је добио узорак. Испоставља се да је ова дефиниција Dialogue: 0,0:04:47.12,0:04:51.72,Default,,0000,0000,0000,,скоро одговарајућа, али је и даље мало прејака, и даље не може да се задовољи, Dialogue: 0,0:04:51.72,0:04:56.20,Default,,0000,0000,0000,,дакле морамо да додамо још једно ограничење, а то је да, уместо да кажемо да ова Dialogue: 0,0:04:56.20,0:05:00.80,Default,,0000,0000,0000,,дефиниција треба да важи за свако m0 и m1, она треба да важи само за парове m0, m1 Dialogue: 0,0:05:00.80,0:05:05.21,Default,,0000,0000,0000,,које нападач може да изложи. То нас у ствари Dialogue: 0,0:05:05.21,0:05:10.04,Default,,0000,0000,0000,,доводи до дефиниције семантичке безбедности. Још једном, ово је семантичка Dialogue: 0,0:05:10.04,0:05:15.05,Default,,0000,0000,0000,,безбедност за једнократне кључеве, другим речима, када нападач добија само један Dialogue: 0,0:05:15.05,0:05:19.82,Default,,0000,0000,0000,,шифрат. Дакле дефинишемо семантичку безбедност тако што дефинишемо два огледа, Dialogue: 0,0:05:19.82,0:05:24.56,Default,,0000,0000,0000,,оглед 0 и оглед 1. У општем случају, посматраћемо Dialogue: 0,0:05:24.56,0:05:29.23,Default,,0000,0000,0000,,их као оглед (b), где b може да буде 0 или 1. Dialogue: 0,0:05:29.23,0:05:32.89,Default,,0000,0000,0000,,Оглед се дефинише на следећи начин, имамо нападача који Dialogue: 0,0:05:32.89,0:05:37.16,Default,,0000,0000,0000,,покушава да разбије систем - нападач А, који је аналоган статистичким тестовима Dialogue: 0,0:05:37.16,0:05:41.28,Default,,0000,0000,0000,,у свету псеудослучајних генератора. Изазивач ради Dialogue: 0,0:05:41.28,0:05:45.09,Default,,0000,0000,0000,,следеће, постоје два изазивача, али они Dialogue: 0,0:05:45.09,0:05:49.41,Default,,0000,0000,0000,,су толико слични, да можемо да их опишемо као истог изазивача који у једном случају Dialogue: 0,0:05:49.41,0:05:53.63,Default,,0000,0000,0000,,узима на улазу битове постављене на 0, а у другом случају Dialogue: 0,0:05:53.63,0:05:57.19,Default,,0000,0000,0000,,постављене на 1. Да вам покажем шта изазивач ради. Најпре Dialogue: 0,0:05:57.19,0:06:01.35,Default,,0000,0000,0000,,он бира случајно кључ, а затим нападач Dialogue: 0,0:06:01.35,0:06:06.08,Default,,0000,0000,0000,,избацује две поруке, m0 и m1. Ово је јавни Dialogue: 0,0:06:06.08,0:06:11.04,Default,,0000,0000,0000,,пар порука, за које нападач жели да буде изазван, и као и обично, не Dialogue: 0,0:06:11.04,0:06:15.77,Default,,0000,0000,0000,,покушавамо да сакријемо дужину порука, захтевамо да буду једнаке дужине. Dialogue: 0,0:06:15.77,0:06:21.64,Default,,0000,0000,0000,,Тада изазивач избаци шифровану m0 Dialogue: 0,0:06:21.64,0:06:25.89,Default,,0000,0000,0000,,или шифровану m1, у огледу 0 изазивач избацује Dialogue: 0,0:06:25.89,0:06:30.30,Default,,0000,0000,0000,,шифровану m0, а у огледу 1 шифровану m1. Dialogue: 0,0:06:30.30,0:06:34.38,Default,,0000,0000,0000,,У томе је разлика између огледа. Dialogue: 0,0:06:34.38,0:06:38.80,Default,,0000,0000,0000,,Нападач покушава да погоди да ли је добио шифровану m0 Dialogue: 0,0:06:38.80,0:06:44.05,Default,,0000,0000,0000,,или шифровану m1. Ево мало ознака. Дефинишимо Dialogue: 0,0:06:44.05,0:06:50.26,Default,,0000,0000,0000,,догађај Wb као догађај када за оглед b нападач избацује 1. Dialogue: 0,0:06:50.26,0:06:55.08,Default,,0000,0000,0000,,Дакле то је такав догађај, да у огледу 0 W0 значи да Dialogue: 0,0:06:55.08,0:07:00.34,Default,,0000,0000,0000,,је нападач избацио 1, а у огледу 1 W1 значи да је нападач избацио 1. Dialogue: 0,0:07:00.34,0:07:05.29,Default,,0000,0000,0000,,Сада можемо да дефинишемо предност овог нападача, и кажемо да је Dialogue: 0,0:07:05.29,0:07:10.42,Default,,0000,0000,0000,,предност семантичке безбедности нападача А над шемом Е Dialogue: 0,0:07:10.42,0:07:15.50,Default,,0000,0000,0000,,разлика између вероватноћа ова два догађаја. Другим речима Dialogue: 0,0:07:15.50,0:07:20.14,Default,,0000,0000,0000,,посматрамо да ли се нападач понаша различито када добије Dialogue: 0,0:07:20.14,0:07:24.82,Default,,0000,0000,0000,,шифровану m0 у односу на то када добије шифровану m1. Желим да будем Dialogue: 0,0:07:24.82,0:07:29.20,Default,,0000,0000,0000,,сигуран да је ово јасно, па ћу да поновим. Дакле у огледу 0 добио Dialogue: 0,0:07:29.20,0:07:33.53,Default,,0000,0000,0000,,је шифровану m0, а у огледу 1 шифровану m1, Dialogue: 0,0:07:33.53,0:07:37.70,Default,,0000,0000,0000,,и сада нас занима да ли нападач избацује 1 или не, Dialogue: 0,0:07:37.70,0:07:42.36,Default,,0000,0000,0000,,у овим огледима. Ако у оба огледа нападач избацује 1 са Dialogue: 0,0:07:42.36,0:07:47.01,Default,,0000,0000,0000,,истом вероватноћом, то значи да нападач није могао да разликује Dialogue: 0,0:07:47.01,0:07:51.55,Default,,0000,0000,0000,,два огледа. Оглед 0 изгледа нападачу исто Dialogue: 0,0:07:51.55,0:07:56.21,Default,,0000,0000,0000,,као оглед 1, зато што у оба случаја враћа 1 са истом вероватноћом. Dialogue: 0,0:07:56.21,0:08:01.29,Default,,0000,0000,0000,,Међутим, ако нападач може да избаци 1 у једном огледу са значајно Dialogue: 0,0:08:01.29,0:08:05.76,Default,,0000,0000,0000,,различитом вероватноћом него у другом огледу, тада је нападач Dialogue: 0,0:08:05.76,0:08:10.27,Default,,0000,0000,0000,,могао да разликује ова два огледа. Да искажемо ово Dialogue: 0,0:08:10.27,0:08:14.46,Default,,0000,0000,0000,,формалније, предност, зато што је то разлика двеју Dialogue: 0,0:08:14.46,0:08:18.92,Default,,0000,0000,0000,,вероватноћа, предност је број између 0 и 1. Ако је предност Dialogue: 0,0:08:18.92,0:08:22.89,Default,,0000,0000,0000,,блиска нули, то значи да нападач није био у стању да разликује Dialogue: 0,0:08:22.89,0:08:27.13,Default,,0000,0000,0000,,оглед 0 од огледа 1. Међутим ако је предност блиска јединици, Dialogue: 0,0:08:27.13,0:08:31.54,Default,,0000,0000,0000,,то значи да је нападач био у стању да разликује оглед 0 од Dialogue: 0,0:08:31.54,0:08:36.11,Default,,0000,0000,0000,,огледа 1, што у ствари значи да је био у стању да разликује шифровање Dialogue: 0,0:08:36.11,0:08:40.30,Default,,0000,0000,0000,,m0 од шифровања m1. Дакле то је наша дефиниција, у ствари, Dialogue: 0,0:08:40.30,0:08:44.06,Default,,0000,0000,0000,,то је само дефиниција предности, а дефиниција је управо Dialogue: 0,0:08:44.06,0:08:47.71,Default,,0000,0000,0000,,оно што бисте и очекивали, кажемо да је шема симетричног шифровања Dialogue: 0,0:08:47.71,0:08:52.35,Default,,0000,0000,0000,,семантички безбедна, ако за све "ефикасне" нападаче, Dialogue: 0,0:08:52.35,0:08:56.93,Default,,0000,0000,0000,,ако је за све ефикасне нападаче предност занемарљива. Другим речима, Dialogue: 0,0:08:56.98,0:09:01.81,Default,,0000,0000,0000,,не постоји ефикасан нападач који може да разликује шифровање m0 од шифровања m1, Dialogue: 0,0:09:01.81,0:09:06.10,Default,,0000,0000,0000,,и, тиме се каже, понављам, да за ове две Dialogue: 0,0:09:06.10,0:09:10.76,Default,,0000,0000,0000,,поруке нападач је био у стању да прикаже да није био у стању да разликује Dialogue: 0,0:09:10.76,0:09:15.06,Default,,0000,0000,0000,,ове две расподеле. Желим да вам покажем, ово је заправо врло Dialogue: 0,0:09:15.06,0:09:19.60,Default,,0000,0000,0000,,елегантна дефиниција, не мора да тако изгледа одмах, али желим да вам покажем неке Dialogue: 0,0:09:19.60,0:09:24.41,Default,,0000,0000,0000,,последице ове дефиниције, а видећете зашто је ова дефиниција таква каква јесте. Dialogue: 0,0:09:24.41,0:09:28.60,Default,,0000,0000,0000,,Погледајмо неке примере. Први пример је - претпоставимо Dialogue: 0,0:09:28.60,0:09:33.19,Default,,0000,0000,0000,,да имамо разбијену шему шифровања, другим речима, претпоставимо да имамо нападача А Dialogue: 0,0:09:33.19,0:09:38.28,Default,,0000,0000,0000,,који некако, добивши шифрат, увек може да открије бит најмање Dialogue: 0,0:09:38.28,0:09:44.15,Default,,0000,0000,0000,,тежине из отвореног текста. Дакле добивши шифру од m0, овај нападач Dialogue: 0,0:09:44.15,0:09:48.80,Default,,0000,0000,0000,,може да добије бит најмање тежине у m0. Ово је јако лоша Dialogue: 0,0:09:48.80,0:09:52.91,Default,,0000,0000,0000,,шема шифровања, зато што одаје бит најмање тежине из Dialogue: 0,0:09:52.91,0:09:57.13,Default,,0000,0000,0000,,отвореног текста самим шифратом. Желим да вам покажем да ова шема није Dialogue: 0,0:09:57.13,0:10:01.61,Default,,0000,0000,0000,,семантички безбедна, чиме се показује да ако систем јесте семантички Dialogue: 0,0:10:01.61,0:10:05.93,Default,,0000,0000,0000,,безбедан, не постоји нападач ове врсте. Погледајмо зашто овај систем Dialogue: 0,0:10:05.93,0:10:10.25,Default,,0000,0000,0000,,није семантички безбедан. Ми ћемо да користимо Dialogue: 0,0:10:10.25,0:10:14.37,Default,,0000,0000,0000,,нашег нападача, који може да открије битове најмање тежине, ми ћемо да Dialogue: 0,0:10:14.37,0:10:18.37,Default,,0000,0000,0000,,га користимо да разбијемо семантичку безбедност, то јест да разликујемо Dialogue: 0,0:10:18.37,0:10:22.76,Default,,0000,0000,0000,,оглед 0 од огледа 1. Ево шта ћемо да урадимо. Dialogue: 0,0:10:22.76,0:10:26.99,Default,,0000,0000,0000,,Ми смо алгоритам В, а овај алгоритам В ће да користи Dialogue: 0,0:10:26.99,0:10:31.16,Default,,0000,0000,0000,,алгоритам А у свом телу. Дакле прво што ће да се деси је, Dialogue: 0,0:10:31.16,0:10:35.61,Default,,0000,0000,0000,,наравно изазивач ће да одабере насумични кључ, и прво што ће да се деси је Dialogue: 0,0:10:35.61,0:10:39.76,Default,,0000,0000,0000,,да ћемо да избацимо две поруке, Dialogue: 0,0:10:39.76,0:10:43.49,Default,,0000,0000,0000,,а које ће да имају различите битове најмање тежине. Dialogue: 0,0:10:43.49,0:10:47.73,Default,,0000,0000,0000,,Једна ће да се завршава са 0, а друга са 1. Dialogue: 0,0:10:47.73,0:10:51.20,Default,,0000,0000,0000,,И шта ће сада изазивач да уради? Он ће да нам да Dialogue: 0,0:10:51.20,0:10:55.24,Default,,0000,0000,0000,,шифровање било од m0 било од m1, у зависности од тога да ли смо у огледу 0 Dialogue: 0,0:10:55.24,0:10:59.12,Default,,0000,0000,0000,,или у огледу 1. А тада ћемо само да проследимо овај шифрат нападачу, Dialogue: 0,0:10:59.12,0:11:03.87,Default,,0000,0000,0000,,дакле нападачу А. А које је својство нападача А? Добивши шифрат, Dialogue: 0,0:11:03.87,0:11:08.50,Default,,0000,0000,0000,,нападач А може да нам каже који је бит најмање тежине отвореног текста. Dialogue: 0,0:11:08.50,0:11:13.37,Default,,0000,0000,0000,,Другим речима, нападач ће да избаци бит најмање тежине од m0 или m1, Dialogue: 0,0:11:13.37,0:11:17.89,Default,,0000,0000,0000,,а то је практично бит b. И затим ћемо само да Dialogue: 0,0:11:17.89,0:11:23.05,Default,,0000,0000,0000,,избацимо то као наш погодак, назовимо то b'. Дакле овим Dialogue: 0,0:11:23.05,0:11:28.38,Default,,0000,0000,0000,,се описује семантичка безбедност нападача. А ви ми кажите шта се предност Dialogue: 0,0:11:28.38,0:11:33.59,Default,,0000,0000,0000,,над семантичком безбедношћу код овог нападача? Па погледајмо: у огледу 0, која је Dialogue: 0,0:11:33.59,0:11:38.78,Default,,0000,0000,0000,,вероватноћа да нападач В избацује 1? Дакле у огледу 0 се увек Dialogue: 0,0:11:38.78,0:11:43.70,Default,,0000,0000,0000,,добија шифровање од m0, и зато нападач А увек избацује Dialogue: 0,0:11:43.70,0:11:48.63,Default,,0000,0000,0000,,бит најмање тежине од m0, а то је увек 0. У огледу Dialogue: 0,0:11:48.63,0:11:53.12,Default,,0000,0000,0000,,0, В увек избацује 0. Дакле вероватноћа да ће да избаци 1 је нула. Dialogue: 0,0:11:53.12,0:11:57.83,Default,,0000,0000,0000,,Међутим у огледу 1, добијамо шифровану m1. Дакле колико је вероватно да ће Dialogue: 0,0:11:57.83,0:12:02.78,Default,,0000,0000,0000,,нападач В да избаци 1 у огледу 1? Па, увек ће да избаци 1, Dialogue: 0,0:12:02.78,0:12:07.43,Default,,0000,0000,0000,,због својства алгоритма А. И услед тога, предност је практично 1. Dialogue: 0,0:12:07.43,0:12:12.38,Default,,0000,0000,0000,,Дакле то је велика предност, највећа што може да буде. Што значи да је овај Dialogue: 0,0:12:12.38,0:12:17.09,Default,,0000,0000,0000,,нападач потпуно разбио систем. Дакле под семантичком Dialogue: 0,0:12:17.09,0:12:22.30,Default,,0000,0000,0000,,безбедношћу, просто сазнавање бита најмање тежине је довољно да потпуно Dialogue: 0,0:12:22.30,0:12:27.19,Default,,0000,0000,0000,,разбије систем - под дефиницијом семантичке безбедности. Занимљива ствар Dialogue: 0,0:12:27.19,0:12:32.39,Default,,0000,0000,0000,,овде је наравно да се не ради само о биту најмање тежине, Dialogue: 0,0:12:32.39,0:12:37.12,Default,,0000,0000,0000,,у ствари, било који бит поруке, на пример, бит највеће тежине, Dialogue: 0,0:12:37.12,0:12:42.04,Default,,0000,0000,0000,,седми бит, можда XOR свих битова поруке, итд, Dialogue: 0,0:12:42.04,0:12:46.55,Default,,0000,0000,0000,,било каква информација, било који бит отвореног текста који може да Dialogue: 0,0:12:46.55,0:12:50.81,Default,,0000,0000,0000,,се сазна, значио би да систем није семантички безбедан. Dialogue: 0,0:12:50.81,0:12:55.53,Default,,0000,0000,0000,,Дакле све што нападач треба да уради јесте да се појави са две поруке, Dialogue: 0,0:12:55.53,0:13:00.25,Default,,0000,0000,0000,,m0 и m1, које су такве да је код једне од њих, то што сазнаје има вредност 0, Dialogue: 0,0:13:00.25,0:13:04.63,Default,,0000,0000,0000,,а код друге има вредност 1. На пример, А је сазнао XOR Dialogue: 0,0:13:04.63,0:13:08.78,Default,,0000,0000,0000,,битова поруке - тада m0 и m1 само треба да имају Dialogue: 0,0:13:08.78,0:13:13.26,Default,,0000,0000,0000,,различити XOR свих битова у поруци, и нападач А би могао Dialogue: 0,0:13:13.26,0:13:18.17,Default,,0000,0000,0000,,да разбије семантичку безбедност. Практично ако је шифра Dialogue: 0,0:13:18.17,0:13:23.20,Default,,0000,0000,0000,,семантички безбедна, никаква информација се не открива Dialogue: 0,0:13:23.20,0:13:27.39,Default,,0000,0000,0000,,ефикасном нападачу. То је управо и појам савршене тајности, али Dialogue: 0,0:13:27.39,0:13:31.32,Default,,0000,0000,0000,,примењен само на ефикасне нападаче уместо на све нападаче. Dialogue: 0,0:13:31.32,0:13:35.04,Default,,0000,0000,0000,,Следеће што желим да вам покажем је да је једнократна бележница Dialogue: 0,0:13:35.04,0:13:38.82,Default,,0000,0000,0000,,семантички безбедна, и боље би било да јесте, зато што је Dialogue: 0,0:13:38.82,0:13:42.77,Default,,0000,0000,0000,,и више од тога, она је савршено безбедна. Погледајмо зашто ово важи. Dialogue: 0,0:13:42.77,0:13:47.01,Default,,0000,0000,0000,,Још једном посматрамо овакве огледе, дакле претпоставимо да нападач претендује Dialogue: 0,0:13:47.01,0:13:51.45,Default,,0000,0000,0000,,да разбије семантичку безбедност једнократне бележнице. Он ће најпре Dialogue: 0,0:13:51.45,0:13:55.87,Default,,0000,0000,0000,,да избаци две поруке, m0 и m1, исте дужине. Dialogue: 0,0:13:55.87,0:13:59.67,Default,,0000,0000,0000,,Шта добија као изазов? Добија или шифровану Dialogue: 0,0:13:59.67,0:14:03.99,Default,,0000,0000,0000,,m0 или шифровану m1, под једнократном бележницом. Dialogue: 0,0:14:03.99,0:14:07.89,Default,,0000,0000,0000,,И покушава да разликује ове две могуће шифрате које добија. Dialogue: 0,0:14:07.89,0:14:12.26,Default,,0000,0000,0000,,У огледу 0, добија шифровану m0, а у огледу 1, добија Dialogue: 0,0:14:12.26,0:14:16.58,Default,,0000,0000,0000,,шифровану m1. Поставља се питање, која је предност нападача А Dialogue: 0,0:14:16.58,0:14:21.30,Default,,0000,0000,0000,,над једнократном бележницом? Подсећам вас да је својство једнократне бележнице Dialogue: 0,0:14:21.30,0:14:26.21,Default,,0000,0000,0000,,да је k XOR m0 са расподелом истоветном са k XOR m1. Dialogue: 0,0:14:26.21,0:14:31.19,Default,,0000,0000,0000,,Другим речима, ово су потпуно подударне расподеле. Dialogue: 0,0:14:31.19,0:14:36.03,Default,,0000,0000,0000,,То је својство XOR - ако XOR-ујемо случајни Dialogue: 0,0:14:36.03,0:14:40.67,Default,,0000,0000,0000,,кључ k са било чим, m0 или m1, добијамо униформну расподелу. Dialogue: 0,0:14:40.67,0:14:45.38,Default,,0000,0000,0000,,Дакле у оба случаја алгоритам А добија на улазу потпуно исту расподелу. Можда Dialogue: 0,0:14:45.38,0:14:50.21,Default,,0000,0000,0000,,униформну расподелу шифрата. И зато ће да се понаша на потпуно Dialogue: 0,0:14:50.21,0:14:55.04,Default,,0000,0000,0000,,исти начин у оба случаја, зато што добија потпуно исту расподелу на улазу. Dialogue: 0,0:14:55.04,0:14:59.70,Default,,0000,0000,0000,,Следи да је његова предност 0, што значи да једнократна бележница јесте семантички Dialogue: 0,0:14:59.72,0:15:04.15,Default,,0000,0000,0000,,безбедна. Занимљиво је то што, не само што је семантички безбедна, Dialogue: 0,0:15:04.15,0:15:08.24,Default,,0000,0000,0000,,већ је семантички безбедна за све нападаче. Не морамо чак да се ограничимо Dialogue: 0,0:15:08.24,0:15:12.45,Default,,0000,0000,0000,,на ефикасне нападаче. Нема нападача, колико год паметан био, који Dialogue: 0,0:15:12.45,0:15:16.88,Default,,0000,0000,0000,,би могао да разликује k XOR m0 од k XOR m1, зато што су ове две Dialogue: 0,0:15:16.88,0:15:21.30,Default,,0000,0000,0000,,расподеле истоветне. Добро, дакле једнократна бележница је семантички безбедна. Dialogue: 0,0:15:21.30,0:15:25.56,Default,,0000,0000,0000,,Тиме смо завршили са дефиницијом семантичке безбедности, и следеће што ћемо Dialogue: 0,0:15:25.56,0:15:30.09,Default,,0000,0000,0000,,да докажемо је да из безбедности PRG-а следи да је шифра тока Dialogue: 0,0:15:30.09,0:15:31.19,Default,,0000,0000,0000,,семантички безбедна.