0:00:00.000,0:00:03.911
Намера ми је да вам у следећих неколико одељака покажем да ако користимо безбедни PRG,

0:00:03.911,0:00:07.892
добијамо безбедну шифру тока. Пре свега морамо да дефинишемо

0:00:07.892,0:00:11.679
шта подразумевамо под безбедношћу шифре тока? Кад год дефинишемо безбедност,

0:00:11.679,0:00:15.174
увек је дефинишемо у смислу тога шта нападач може да уради, и шта

0:00:15.174,0:00:18.670
покушава да уради. У вези са шифрама тока, сетите се да се оне користе искључиво

0:00:18.670,0:00:22.737
са једнократним кључем, и услед тога највише што нападач икад може да види

0:00:22.737,0:00:26.754
јесте један шифрат шифрован коришћењем кључем који користимо. Дакле

0:00:26.754,0:00:30.772
ограничавамо нападачеву могућност на прибављање само једног шифрата.

0:00:30.772,0:00:34.641
У ствари, касније ћемо да дозволимо нападачу да уради много, много више,

0:00:34.641,0:00:38.460
али за сада ћемо да му дамо само један шифрат. И желимо да видимо

0:00:38.460,0:00:42.560
шта подразумевамо под безбедношћу шифре? Прва дефиниција

0:00:42.560,0:00:46.892
која нам пада на памет, јесте да можда желимо да захтевамо да нападач

0:00:46.892,0:00:50.718
не може да прибави тајни кључ. Дакле на основу шифрата

0:00:50.718,0:00:54.609
не треба да будете у стању да прибавите тајни кључ. Али то је лоша дефиниција

0:00:54.609,0:00:58.717
зато што, погледајте следећу сјајну шифру, где шифрујемо

0:00:58.717,0:01:02.855
поруку коришћењем кључа k тако што једноставно избацимо поруку.

0:01:02.855,0:01:07.427
Наравно ово је сјајна шифра, не ради ништа са поруком

0:01:07.427,0:01:12.000
осим што шифрат избаци као саму поруку. Ово није нарочито добро шифровање;

0:01:12.000,0:01:16.029
међутим, на основу шифрата, тј. поруке, сироти нападач

0:01:16.029,0:01:20.493
не може да прибави кључ, зато што му кључ није познат. Услед тога ова шифра,

0:01:20.493,0:01:24.630
која очигледно није безбедна, била би сматрана безбедном под овим

0:01:24.793,0:01:28.636
захтевима безбедности. Дакле оваква дефиниција не би ваљала.

0:01:28.636,0:01:32.317
Дакле прибављање тајног кључа је погрешан начин да се дефинише безбедност. Следеће што

0:01:32.317,0:01:35.999
можемо да покушамо је да кажемо да можда нападача није брига

0:01:35.999,0:01:39.680
за тајни кључ, већ га заправо занима отворени текст. Можда би требало

0:01:39.680,0:01:43.518
да нападачу буде тешко да дође до целокупног отвореног текста. Али чак и то

0:01:43.518,0:01:48.223
није довољно зато што, посматрајмо следећи начин шифровања. Рецимо

0:01:48.223,0:01:53.436
да код овог шифровања узимамо две поруке, ја ћу да користим

0:01:53.436,0:01:58.014
ове две линије да означим спајање двеју порука, m0 || m1 значи

0:01:58.014,0:02:03.100
спајање m0 и m1. Рецимо да ова шифра даје

0:02:03.100,0:02:08.060
m0 као отворену, и спаја то са шифром од m1. Можда чак и

0:02:08.060,0:02:13.337
коришћењем једнократне бележнице. Дакле овде се нападачу даје један

0:02:13.337,0:02:17.478
шифрат, а његов циљ је да дође до целокупног отвореног текста. Али

0:02:17.478,0:02:21.702
сироти нападач то не може да учини зато што, можда смо шифровали m1 коришћењем

0:02:21.702,0:02:25.872
једнократне бележнице, тако да нападач не може да дође до m1 зато што, знамо да је

0:02:25.872,0:02:30.043
једнократна бележница безбедна када се користи код само једног шифрата. Дакле ова конструкција

0:02:30.043,0:02:34.055
би задовољила дефиницију, али нажалост ово очигледно није безбедно

0:02:34.055,0:02:37.962
шифровање, зато што је процурило пола отвореног текста.

0:02:37.962,0:02:42.185
m0 је потпуно доступно нападачу, тако да, мада не може да дође до

0:02:42.185,0:02:46.462
целокупног отвореног текста, могао би да поврати већину отвореног текста, а то очигледно

0:02:46.462,0:02:50.658
није безбедно. Наравно већ знамо решење за ово, говорили смо

0:02:50.658,0:02:54.747
о Шеноновој дефиницији савршене безбедности, где је Шенонова идеја била

0:02:54.747,0:02:58.835
да када нападач пресретне шифрат, не треба да сазна никакву

0:02:58.835,0:03:02.818
информацију о отвореном тексту. Не треба чак ни да сазна ни један бит

0:03:02.818,0:03:07.221
отвореног текста, нити сме да му буде могуће да предвиди

0:03:07.221,0:03:11.205
мали део отвореног текста; никакву информацију о отвореном тексту.

0:03:11.205,0:03:14.926
Подсетимо се укратко Шеноновог појма савршене безбедности

0:03:14.926,0:03:19.442
рекли смо да шифра има савршену безбедност

0:03:19.442,0:03:25.069
ако, када имамо две поруке исте дужине, расподела

0:03:25.069,0:03:30.167
шифрата - ако одаберемо насумично кључ и посматрамо расподелу

0:03:30.167,0:03:34.838
шифрата, ако шифрујемо m0, добијамо потпуно исту расподелу као када

0:03:34.838,0:03:39.257
шифрујемо m1. Наслућујемо овде да ако нападач посматра шифрат,

0:03:39.257,0:03:43.839
не зна да ли је потекао из расподеле која је последица шифровања

0:03:43.839,0:03:48.203
са m0 или из расподеле која је последица шифровања са m1.

0:03:48.203,0:03:52.513
Услед тога, он не може да одреди да ли смо шифровали m0 или m1. И то важи за све

0:03:52.513,0:03:56.877
поруке истих дужина, и захваљујући томе сироти нападач не зна

0:03:56.877,0:04:01.212
која порука је била шифрована. Наравно већ смо рекли да је ова дефиниција

0:04:01.212,0:04:05.400
превише јака, у смислу да захтева врло дугачке кључеве, и ако шифра има кратке кључеве

0:04:05.400,0:04:09.535
никако не може да задовољи ову дефиницију. Конкретно, шифра тока

0:04:09.535,0:04:14.328
не може да задовољи ову дефиницију. Покушајмо да мало ослабимо ову дефиницију,

0:04:14.328,0:04:19.114
сетимо се претходног одељка. Можемо да кажемо да уместо да захтевамо

0:04:19.114,0:04:23.841
да две расподеле буду потпуно истоветне, ми захтевамо да

0:04:23.841,0:04:28.686
две расподеле буду рачунски нераспознатљиве. Другим речима, сироти,

0:04:28.863,0:04:33.353
ефикасни нападач не може да разликује две расподеле иако

0:04:33.353,0:04:37.815
расподеле могу да буду врло различите. На основу узорка

0:04:37.815,0:04:42.580
једне и друге расподеле, нападач не може да каже

0:04:42.580,0:04:47.120
из које расподеле је добио узорак. Испоставља се да је ова дефиниција

0:04:47.120,0:04:51.716
скоро одговарајућа, али је и даље мало прејака, и даље не може да се задовољи,

0:04:51.716,0:04:56.200
дакле морамо да додамо још једно ограничење, а то је да, уместо да кажемо да ова

0:04:56.200,0:05:00.797
дефиниција треба да важи за свако m0 и m1, она треба да важи само за парове m0, m1

0:05:00.797,0:05:05.208
које нападач може да изложи. То нас у ствари

0:05:05.208,0:05:10.038
доводи до дефиниције семантичке безбедности. Још једном, ово је семантичка

0:05:10.038,0:05:15.050
безбедност за једнократне кључеве, другим речима, када нападач добија само један

0:05:15.050,0:05:19.819
шифрат. Дакле дефинишемо семантичку безбедност тако што дефинишемо два огледа,

0:05:19.819,0:05:24.562
оглед 0 и оглед 1. У општем случају, посматраћемо

0:05:24.562,0:05:29.230
их као оглед (b), где b може да буде 0 или 1.

0:05:29.230,0:05:32.890
Оглед се дефинише на следећи начин, имамо нападача који

0:05:32.890,0:05:37.161
покушава да разбије систем - нападач А, који је аналоган статистичким тестовима

0:05:37.161,0:05:41.279
у свету псеудослучајних генератора. Изазивач ради

0:05:41.279,0:05:45.093
следеће, постоје два изазивача, али они

0:05:45.093,0:05:49.414
су толико слични, да можемо да их опишемо као истог изазивача који у једном случају

0:05:49.414,0:05:53.634
узима на улазу битове постављене на 0, а у другом случају

0:05:53.634,0:05:57.193
постављене на 1. Да вам покажем шта изазивач ради. Најпре

0:05:57.193,0:06:01.349
он бира случајно кључ, а затим нападач

0:06:01.349,0:06:06.076
избацује две поруке, m0 и m1. Ово је јавни

0:06:06.076,0:06:11.039
пар порука, за које нападач жели да буде изазван, и као и обично, не

0:06:11.039,0:06:15.766
покушавамо да сакријемо дужину порука, захтевамо да буду једнаке дужине.

0:06:15.766,0:06:21.643
Тада изазивач избаци шифровану m0

0:06:21.643,0:06:25.890
или шифровану m1, у огледу 0 изазивач избацује

0:06:25.890,0:06:30.301
шифровану m0, а у огледу 1 шифровану m1.

0:06:30.301,0:06:34.385
У томе је разлика између огледа.

0:06:34.385,0:06:38.796
Нападач покушава да погоди да ли је добио шифровану m0

0:06:38.796,0:06:44.051
или шифровану m1. Ево мало ознака. Дефинишимо

0:06:44.051,0:06:50.260
догађај Wb као догађај када за оглед b нападач избацује 1.

0:06:50.260,0:06:55.084
Дакле то је такав догађај, да у огледу 0 W0 значи да

0:06:55.084,0:07:00.342
је нападач избацио 1, а у огледу 1 W1 значи да је нападач избацио 1.

0:07:00.342,0:07:05.291
Сада можемо да дефинишемо предност овог нападача, и кажемо да је

0:07:05.291,0:07:10.425
предност семантичке безбедности нападача А над шемом Е

0:07:10.425,0:07:15.497
разлика између вероватноћа ова два догађаја. Другим речима

0:07:15.497,0:07:20.136
посматрамо да ли се нападач понаша различито када добије

0:07:20.136,0:07:24.818
шифровану m0 у односу на то када добије шифровану m1. Желим да будем

0:07:24.818,0:07:29.201
сигуран да је ово јасно, па ћу да поновим. Дакле у огледу 0 добио

0:07:29.201,0:07:33.530
је шифровану m0, а у огледу 1 шифровану m1,

0:07:33.530,0:07:37.700
и сада нас занима да ли нападач избацује 1 или не,

0:07:37.700,0:07:42.356
у овим огледима. Ако у оба огледа нападач избацује 1 са

0:07:42.356,0:07:47.013
истом вероватноћом, то значи да нападач није могао да разликује

0:07:47.013,0:07:51.549
два огледа. Оглед 0 изгледа нападачу исто

0:07:51.549,0:07:56.206
као оглед 1, зато што у оба случаја враћа 1 са истом вероватноћом.

0:07:56.206,0:08:01.286
Међутим, ако нападач може да избаци 1 у једном огледу са значајно

0:08:01.286,0:08:05.761
различитом вероватноћом него у другом огледу, тада је нападач

0:08:05.761,0:08:10.266
могао да разликује ова два огледа. Да искажемо ово

0:08:10.266,0:08:14.455
формалније, предност, зато што је то разлика двеју

0:08:14.455,0:08:18.918
вероватноћа, предност је број између 0 и 1. Ако је предност

0:08:18.918,0:08:22.886
блиска нули, то значи да нападач није био у стању да разликује

0:08:22.886,0:08:27.129
оглед 0 од огледа 1. Међутим ако је предност блиска јединици,

0:08:27.129,0:08:31.538
то значи да је нападач био у стању да разликује оглед 0 од

0:08:31.538,0:08:36.112
огледа 1, што у ствари значи да је био у стању да разликује шифровање

0:08:36.112,0:08:40.299
m0 од шифровања m1. Дакле то је наша дефиниција, у ствари,

0:08:40.299,0:08:44.055
то је само дефиниција предности, а дефиниција је управо

0:08:44.055,0:08:47.714
оно што бисте и очекивали, кажемо да је шема симетричног шифровања

0:08:47.714,0:08:52.346
семантички безбедна, ако за све "ефикасне" нападаче,

0:08:52.346,0:08:56.932
ако је за све ефикасне нападаче предност занемарљива. Другим речима,

0:08:56.982,0:09:01.808
не постоји ефикасан нападач који може да разликује шифровање m0 од шифровања m1,

0:09:01.808,0:09:06.103
и, тиме се каже, понављам, да за ове две

0:09:06.103,0:09:10.759
поруке нападач је био у стању да прикаже да није био у стању да разликује

0:09:10.759,0:09:15.064
ове две расподеле. Желим да вам покажем, ово је заправо врло

0:09:15.064,0:09:19.595
елегантна дефиниција, не мора да тако изгледа одмах, али желим да вам покажем неке

0:09:19.595,0:09:24.410
последице ове дефиниције, а видећете зашто је ова дефиниција таква каква јесте.

0:09:24.410,0:09:28.601
Погледајмо неке примере. Први пример је - претпоставимо

0:09:28.601,0:09:33.190
да имамо разбијену шему шифровања, другим речима, претпоставимо да имамо нападача А

0:09:33.190,0:09:38.285
који некако, добивши шифрат, увек може да открије бит најмање

0:09:38.285,0:09:44.149
тежине из отвореног текста. Дакле добивши шифру од m0, овај нападач

0:09:44.149,0:09:48.799
може да добије бит најмање тежине у m0. Ово је јако лоша

0:09:48.799,0:09:52.911
шема шифровања, зато што одаје бит најмање тежине из

0:09:52.911,0:09:57.128
отвореног текста самим шифратом. Желим да вам покажем да ова шема није

0:09:57.128,0:10:01.609
семантички безбедна, чиме се показује да ако систем јесте семантички

0:10:01.609,0:10:05.931
безбедан, не постоји нападач ове врсте. Погледајмо зашто овај систем

0:10:05.931,0:10:10.254
није семантички безбедан. Ми ћемо да користимо

0:10:10.254,0:10:14.366
нашег нападача, који може да открије битове најмање тежине, ми ћемо да

0:10:14.366,0:10:18.372
га користимо да разбијемо семантичку безбедност, то јест да разликујемо

0:10:18.372,0:10:22.755
оглед 0 од огледа 1. Ево шта ћемо да урадимо.

0:10:22.755,0:10:26.987
Ми смо алгоритам В, а овај алгоритам В ће да користи

0:10:26.987,0:10:31.165
алгоритам А у свом телу. Дакле прво што ће да се деси је,

0:10:31.165,0:10:35.608
наравно изазивач ће да одабере насумични кључ, и прво што ће да се деси је

0:10:35.608,0:10:39.762
да ћемо да избацимо две поруке,

0:10:39.762,0:10:43.493
а које ће да имају различите битове најмање тежине.

0:10:43.493,0:10:47.727
Једна ће да се завршава са 0, а друга са 1.

0:10:47.727,0:10:51.205
И шта ће сада изазивач да уради? Он ће да нам да

0:10:51.205,0:10:55.238
шифровање било од m0 било од m1, у зависности од тога да ли смо у огледу 0

0:10:55.238,0:10:59.120
или у огледу 1. А тада ћемо само да проследимо овај шифрат нападачу,

0:10:59.120,0:11:03.871
дакле нападачу А. А које је својство нападача А? Добивши шифрат,

0:11:03.871,0:11:08.505
нападач А може да нам каже који је бит најмање тежине отвореног текста.

0:11:08.505,0:11:13.374
Другим речима, нападач ће да избаци бит најмање тежине од m0 или m1,

0:11:13.374,0:11:17.892
а то је практично бит b. И затим ћемо само да

0:11:17.892,0:11:23.050
избацимо то као наш погодак, назовимо то b'. Дакле овим

0:11:23.050,0:11:28.376
се описује семантичка безбедност нападача. А ви ми кажите шта се предност

0:11:28.376,0:11:33.593
над семантичком безбедношћу код овог нападача? Па погледајмо: у огледу 0, која је

0:11:33.593,0:11:38.775
вероватноћа да нападач В избацује 1? Дакле у огледу 0 се увек

0:11:38.775,0:11:43.704
добија шифровање од m0, и зато нападач А увек избацује

0:11:43.704,0:11:48.633
бит најмање тежине од m0, а то је увек 0. У огледу

0:11:48.633,0:11:53.120
0, В увек избацује 0. Дакле вероватноћа да ће да избаци 1 је нула.

0:11:53.120,0:11:57.827
Међутим у огледу 1, добијамо шифровану m1. Дакле колико је вероватно да ће

0:11:57.827,0:12:02.783
нападач В да избаци 1 у огледу 1? Па, увек ће да избаци 1,

0:12:02.783,0:12:07.428
због својства алгоритма А. И услед тога, предност је практично 1.

0:12:07.428,0:12:12.384
Дакле то је велика предност, највећа што може да буде. Што значи да је овај

0:12:12.384,0:12:17.091
нападач потпуно разбио систем. Дакле под семантичком

0:12:17.091,0:12:22.295
безбедношћу, просто сазнавање бита најмање тежине је довољно да потпуно

0:12:22.295,0:12:27.187
разбије систем - под дефиницијом семантичке безбедности. Занимљива ствар

0:12:27.187,0:12:32.388
овде је наравно да се не ради само о биту најмање тежине,

0:12:32.388,0:12:37.117
у ствари, било који бит поруке, на пример, бит највеће тежине,

0:12:37.117,0:12:42.040
седми бит, можда XOR свих битова поруке, итд,

0:12:42.040,0:12:46.552
било каква информација, било који бит отвореног текста који може да

0:12:46.552,0:12:50.814
се сазна, значио би да систем није семантички безбедан.

0:12:50.814,0:12:55.532
Дакле све што нападач треба да уради јесте да се појави са две поруке,

0:12:55.532,0:13:00.249
m0 и m1, које су такве да је код једне од њих, то што сазнаје има вредност 0,

0:13:00.249,0:13:04.626
а код друге има вредност 1. На пример, А је сазнао XOR

0:13:04.626,0:13:08.775
битова поруке - тада m0 и m1 само треба да имају

0:13:08.775,0:13:13.265
различити XOR свих битова у поруци, и нападач А би могао

0:13:13.265,0:13:18.174
да разбије семантичку безбедност. Практично ако је шифра

0:13:18.174,0:13:23.203
семантички безбедна, никаква информација се не открива

0:13:23.203,0:13:27.392
ефикасном нападачу. То је управо и појам савршене тајности, али

0:13:27.392,0:13:31.318
примењен само на ефикасне нападаче уместо на све нападаче.

0:13:31.318,0:13:35.045
Следеће што желим да вам покажем је да је једнократна бележница

0:13:35.045,0:13:38.821
семантички безбедна, и боље би било да јесте, зато што је

0:13:38.821,0:13:42.773
и више од тога, она је савршено безбедна. Погледајмо зашто ово важи.

0:13:42.773,0:13:47.010
Још једном посматрамо овакве огледе, дакле претпоставимо да нападач претендује

0:13:47.010,0:13:51.449
да разбије семантичку безбедност једнократне бележнице. Он ће најпре

0:13:51.449,0:13:55.874
да избаци две поруке, m0 и m1, исте дужине.

0:13:55.874,0:13:59.667
Шта добија као изазов? Добија или шифровану

0:13:59.667,0:14:03.988
m0 или шифровану m1, под једнократном бележницом.

0:14:03.988,0:14:07.886
И покушава да разликује ове две могуће шифрате које добија.

0:14:07.886,0:14:12.259
У огледу 0, добија шифровану m0, а у огледу 1, добија

0:14:12.259,0:14:16.579
шифровану m1. Поставља се питање, која је предност нападача А

0:14:16.579,0:14:21.297
над једнократном бележницом? Подсећам вас да је својство једнократне бележнице

0:14:21.297,0:14:26.208
да је k XOR m0 са расподелом истоветном са k XOR m1.

0:14:26.208,0:14:31.187
Другим речима, ово су потпуно подударне расподеле.

0:14:31.187,0:14:36.026
То је својство XOR - ако XOR-ујемо случајни

0:14:36.026,0:14:40.674
кључ k са било чим, m0 или m1, добијамо униформну расподелу.

0:14:40.674,0:14:45.382
Дакле у оба случаја алгоритам А добија на улазу потпуно исту расподелу. Можда

0:14:45.382,0:14:50.209
униформну расподелу шифрата. И зато ће да се понаша на потпуно

0:14:50.209,0:14:55.036
исти начин у оба случаја, зато што добија потпуно исту расподелу на улазу.

0:14:55.036,0:14:59.699
Следи да је његова предност 0, што значи да једнократна бележница јесте семантички

0:14:59.723,0:15:04.148
безбедна. Занимљиво је то што, не само што је семантички безбедна,

0:15:04.148,0:15:08.244
већ је семантички безбедна за све нападаче. Не морамо чак да се ограничимо

0:15:08.244,0:15:12.450
на ефикасне нападаче. Нема нападача, колико год паметан био, који

0:15:12.450,0:15:16.875
би могао да разликује k XOR m0 од k XOR m1, зато што су ове две

0:15:16.875,0:15:21.299
расподеле истоветне. Добро, дакле једнократна бележница је семантички безбедна.

0:15:21.299,0:15:25.559
Тиме смо завршили са дефиницијом семантичке безбедности, и следеће што ћемо

0:15:25.559,0:15:30.093
да докажемо је да из безбедности PRG-а следи да је шифра тока

0:15:30.093,0:15:31.186
семантички безбедна.