1
00:00:00,000 --> 00:00:03,911
Намера ми је да вам у следећих неколико одељака покажем да ако користимо безбедни PRG,

2
00:00:03,911 --> 00:00:07,892
добијамо безбедну шифру тока. Пре свега морамо да дефинишемо

3
00:00:07,892 --> 00:00:11,679
шта подразумевамо под безбедношћу шифре тока? Кад год дефинишемо безбедност,

4
00:00:11,679 --> 00:00:15,174
увек је дефинишемо у смислу тога шта нападач може да уради, и шта

5
00:00:15,174 --> 00:00:18,670
покушава да уради. У вези са шифрама тока, сетите се да се оне користе искључиво

6
00:00:18,670 --> 00:00:22,737
са једнократним кључем, и услед тога највише што нападач икад може да види

7
00:00:22,737 --> 00:00:26,754
јесте један шифрат шифрован коришћењем кључем који користимо. Дакле

8
00:00:26,754 --> 00:00:30,772
ограничавамо нападачеву могућност на прибављање само једног шифрата.

9
00:00:30,772 --> 00:00:34,641
У ствари, касније ћемо да дозволимо нападачу да уради много, много више,

10
00:00:34,641 --> 00:00:38,460
али за сада ћемо да му дамо само један шифрат. И желимо да видимо

11
00:00:38,460 --> 00:00:42,560
шта подразумевамо под безбедношћу шифре? Прва дефиниција

12
00:00:42,560 --> 00:00:46,892
која нам пада на памет, јесте да можда желимо да захтевамо да нападач

13
00:00:46,892 --> 00:00:50,718
не може да прибави тајни кључ. Дакле на основу шифрата

14
00:00:50,718 --> 00:00:54,609
не треба да будете у стању да прибавите тајни кључ. Али то је лоша дефиниција

15
00:00:54,609 --> 00:00:58,717
зато што, погледајте следећу сјајну шифру, где шифрујемо

16
00:00:58,717 --> 00:01:02,855
поруку коришћењем кључа k тако што једноставно избацимо поруку.

17
00:01:02,855 --> 00:01:07,427
Наравно ово је сјајна шифра, не ради ништа са поруком

18
00:01:07,427 --> 00:01:12,000
осим што шифрат избаци као саму поруку. Ово није нарочито добро шифровање;

19
00:01:12,000 --> 00:01:16,029
међутим, на основу шифрата, тј. поруке, сироти нападач

20
00:01:16,029 --> 00:01:20,493
не може да прибави кључ, зато што му кључ није познат. Услед тога ова шифра,

21
00:01:20,493 --> 00:01:24,630
која очигледно није безбедна, била би сматрана безбедном под овим

22
00:01:24,793 --> 00:01:28,636
захтевима безбедности. Дакле оваква дефиниција не би ваљала.

23
00:01:28,636 --> 00:01:32,317
Дакле прибављање тајног кључа је погрешан начин да се дефинише безбедност. Следеће што

24
00:01:32,317 --> 00:01:35,999
можемо да покушамо је да кажемо да можда нападача није брига

25
00:01:35,999 --> 00:01:39,680
за тајни кључ, већ га заправо занима отворени текст. Можда би требало

26
00:01:39,680 --> 00:01:43,518
да нападачу буде тешко да дође до целокупног отвореног текста. Али чак и то

27
00:01:43,518 --> 00:01:48,223
није довољно зато што, посматрајмо следећи начин шифровања. Рецимо

28
00:01:48,223 --> 00:01:53,436
да код овог шифровања узимамо две поруке, ја ћу да користим

29
00:01:53,436 --> 00:01:58,014
ове две линије да означим спајање двеју порука, m0 || m1 значи

30
00:01:58,014 --> 00:02:03,100
спајање m0 и m1. Рецимо да ова шифра даје

31
00:02:03,100 --> 00:02:08,060
m0 као отворену, и спаја то са шифром од m1. Можда чак и

32
00:02:08,060 --> 00:02:13,337
коришћењем једнократне бележнице. Дакле овде се нападачу даје један

33
00:02:13,337 --> 00:02:17,478
шифрат, а његов циљ је да дође до целокупног отвореног текста. Али

34
00:02:17,478 --> 00:02:21,702
сироти нападач то не може да учини зато што, можда смо шифровали m1 коришћењем

35
00:02:21,702 --> 00:02:25,872
једнократне бележнице, тако да нападач не може да дође до m1 зато што, знамо да је

36
00:02:25,872 --> 00:02:30,043
једнократна бележница безбедна када се користи код само једног шифрата. Дакле ова конструкција

37
00:02:30,043 --> 00:02:34,055
би задовољила дефиницију, али нажалост ово очигледно није безбедно

38
00:02:34,055 --> 00:02:37,962
шифровање, зато што је процурило пола отвореног текста.

39
00:02:37,962 --> 00:02:42,185
m0 је потпуно доступно нападачу, тако да, мада не може да дође до

40
00:02:42,185 --> 00:02:46,462
целокупног отвореног текста, могао би да поврати већину отвореног текста, а то очигледно

41
00:02:46,462 --> 00:02:50,658
није безбедно. Наравно већ знамо решење за ово, говорили смо

42
00:02:50,658 --> 00:02:54,747
о Шеноновој дефиницији савршене безбедности, где је Шенонова идеја била

43
00:02:54,747 --> 00:02:58,835
да када нападач пресретне шифрат, не треба да сазна никакву

44
00:02:58,835 --> 00:03:02,818
информацију о отвореном тексту. Не треба чак ни да сазна ни један бит

45
00:03:02,818 --> 00:03:07,221
отвореног текста, нити сме да му буде могуће да предвиди

46
00:03:07,221 --> 00:03:11,205
мали део отвореног текста; никакву информацију о отвореном тексту.

47
00:03:11,205 --> 00:03:14,926
Подсетимо се укратко Шеноновог појма савршене безбедности

48
00:03:14,926 --> 00:03:19,442
рекли смо да шифра има савршену безбедност

49
00:03:19,442 --> 00:03:25,069
ако, када имамо две поруке исте дужине, расподела

50
00:03:25,069 --> 00:03:30,167
шифрата - ако одаберемо насумично кључ и посматрамо расподелу

51
00:03:30,167 --> 00:03:34,838
шифрата, ако шифрујемо m0, добијамо потпуно исту расподелу као када

52
00:03:34,838 --> 00:03:39,257
шифрујемо m1. Наслућујемо овде да ако нападач посматра шифрат,

53
00:03:39,257 --> 00:03:43,839
не зна да ли је потекао из расподеле која је последица шифровања

54
00:03:43,839 --> 00:03:48,203
са m0 или из расподеле која је последица шифровања са m1.

55
00:03:48,203 --> 00:03:52,513
Услед тога, он не може да одреди да ли смо шифровали m0 или m1. И то важи за све

56
00:03:52,513 --> 00:03:56,877
поруке истих дужина, и захваљујући томе сироти нападач не зна

57
00:03:56,877 --> 00:04:01,212
која порука је била шифрована. Наравно већ смо рекли да је ова дефиниција

58
00:04:01,212 --> 00:04:05,400
превише јака, у смислу да захтева врло дугачке кључеве, и ако шифра има кратке кључеве

59
00:04:05,400 --> 00:04:09,535
никако не може да задовољи ову дефиницију. Конкретно, шифра тока

60
00:04:09,535 --> 00:04:14,328
не може да задовољи ову дефиницију. Покушајмо да мало ослабимо ову дефиницију,

61
00:04:14,328 --> 00:04:19,114
сетимо се претходног одељка. Можемо да кажемо да уместо да захтевамо

62
00:04:19,114 --> 00:04:23,841
да две расподеле буду потпуно истоветне, ми захтевамо да

63
00:04:23,841 --> 00:04:28,686
две расподеле буду рачунски нераспознатљиве. Другим речима, сироти,

64
00:04:28,863 --> 00:04:33,353
ефикасни нападач не може да разликује две расподеле иако

65
00:04:33,353 --> 00:04:37,815
расподеле могу да буду врло различите. На основу узорка

66
00:04:37,815 --> 00:04:42,580
једне и друге расподеле, нападач не може да каже

67
00:04:42,580 --> 00:04:47,120
из које расподеле је добио узорак. Испоставља се да је ова дефиниција

68
00:04:47,120 --> 00:04:51,716
скоро одговарајућа, али је и даље мало прејака, и даље не може да се задовољи,

69
00:04:51,716 --> 00:04:56,200
дакле морамо да додамо још једно ограничење, а то је да, уместо да кажемо да ова

70
00:04:56,200 --> 00:05:00,797
дефиниција треба да важи за свако m0 и m1, она треба да важи само за парове m0, m1

71
00:05:00,797 --> 00:05:05,208
које нападач може да изложи. То нас у ствари

72
00:05:05,208 --> 00:05:10,038
доводи до дефиниције семантичке безбедности. Још једном, ово је семантичка

73
00:05:10,038 --> 00:05:15,050
безбедност за једнократне кључеве, другим речима, када нападач добија само један

74
00:05:15,050 --> 00:05:19,819
шифрат. Дакле дефинишемо семантичку безбедност тако што дефинишемо два огледа,

75
00:05:19,819 --> 00:05:24,562
оглед 0 и оглед 1. У општем случају, посматраћемо

76
00:05:24,562 --> 00:05:29,230
их као оглед (b), где b може да буде 0 или 1.

77
00:05:29,230 --> 00:05:32,890
Оглед се дефинише на следећи начин, имамо нападача који

78
00:05:32,890 --> 00:05:37,161
покушава да разбије систем - нападач А, који је аналоган статистичким тестовима

79
00:05:37,161 --> 00:05:41,279
у свету псеудослучајних генератора. Изазивач ради

80
00:05:41,279 --> 00:05:45,093
следеће, постоје два изазивача, али они

81
00:05:45,093 --> 00:05:49,414
су толико слични, да можемо да их опишемо као истог изазивача који у једном случају

82
00:05:49,414 --> 00:05:53,634
узима на улазу битове постављене на 0, а у другом случају

83
00:05:53,634 --> 00:05:57,193
постављене на 1. Да вам покажем шта изазивач ради. Најпре

84
00:05:57,193 --> 00:06:01,349
он бира случајно кључ, а затим нападач

85
00:06:01,349 --> 00:06:06,076
избацује две поруке, m0 и m1. Ово је јавни

86
00:06:06,076 --> 00:06:11,039
пар порука, за које нападач жели да буде изазван, и као и обично, не

87
00:06:11,039 --> 00:06:15,766
покушавамо да сакријемо дужину порука, захтевамо да буду једнаке дужине.

88
00:06:15,766 --> 00:06:21,643
Тада изазивач избаци шифровану m0

89
00:06:21,643 --> 00:06:25,890
или шифровану m1, у огледу 0 изазивач избацује

90
00:06:25,890 --> 00:06:30,301
шифровану m0, а у огледу 1 шифровану m1.

91
00:06:30,301 --> 00:06:34,385
У томе је разлика између огледа.

92
00:06:34,385 --> 00:06:38,796
Нападач покушава да погоди да ли је добио шифровану m0

93
00:06:38,796 --> 00:06:44,051
или шифровану m1. Ево мало ознака. Дефинишимо

94
00:06:44,051 --> 00:06:50,260
догађај Wb као догађај када за оглед b нападач избацује 1.

95
00:06:50,260 --> 00:06:55,084
Дакле то је такав догађај, да у огледу 0 W0 значи да

96
00:06:55,084 --> 00:07:00,342
је нападач избацио 1, а у огледу 1 W1 значи да је нападач избацио 1.

97
00:07:00,342 --> 00:07:05,291
Сада можемо да дефинишемо предност овог нападача, и кажемо да је

98
00:07:05,291 --> 00:07:10,425
предност семантичке безбедности нападача А над шемом Е

99
00:07:10,425 --> 00:07:15,497
разлика између вероватноћа ова два догађаја. Другим речима

100
00:07:15,497 --> 00:07:20,136
посматрамо да ли се нападач понаша различито када добије

101
00:07:20,136 --> 00:07:24,818
шифровану m0 у односу на то када добије шифровану m1. Желим да будем

102
00:07:24,818 --> 00:07:29,201
сигуран да је ово јасно, па ћу да поновим. Дакле у огледу 0 добио

103
00:07:29,201 --> 00:07:33,530
је шифровану m0, а у огледу 1 шифровану m1,

104
00:07:33,530 --> 00:07:37,700
и сада нас занима да ли нападач избацује 1 или не,

105
00:07:37,700 --> 00:07:42,356
у овим огледима. Ако у оба огледа нападач избацује 1 са

106
00:07:42,356 --> 00:07:47,013
истом вероватноћом, то значи да нападач није могао да разликује

107
00:07:47,013 --> 00:07:51,549
два огледа. Оглед 0 изгледа нападачу исто

108
00:07:51,549 --> 00:07:56,206
као оглед 1, зато што у оба случаја враћа 1 са истом вероватноћом.

109
00:07:56,206 --> 00:08:01,286
Међутим, ако нападач може да избаци 1 у једном огледу са значајно

110
00:08:01,286 --> 00:08:05,761
различитом вероватноћом него у другом огледу, тада је нападач

111
00:08:05,761 --> 00:08:10,266
могао да разликује ова два огледа. Да искажемо ово

112
00:08:10,266 --> 00:08:14,455
формалније, предност, зато што је то разлика двеју

113
00:08:14,455 --> 00:08:18,918
вероватноћа, предност је број између 0 и 1. Ако је предност

114
00:08:18,918 --> 00:08:22,886
блиска нули, то значи да нападач није био у стању да разликује

115
00:08:22,886 --> 00:08:27,129
оглед 0 од огледа 1. Међутим ако је предност блиска јединици,

116
00:08:27,129 --> 00:08:31,538
то значи да је нападач био у стању да разликује оглед 0 од

117
00:08:31,538 --> 00:08:36,112
огледа 1, што у ствари значи да је био у стању да разликује шифровање

118
00:08:36,112 --> 00:08:40,299
m0 од шифровања m1. Дакле то је наша дефиниција, у ствари,

119
00:08:40,299 --> 00:08:44,055
то је само дефиниција предности, а дефиниција је управо

120
00:08:44,055 --> 00:08:47,714
оно што бисте и очекивали, кажемо да је шема симетричног шифровања

121
00:08:47,714 --> 00:08:52,346
семантички безбедна, ако за све "ефикасне" нападаче,

122
00:08:52,346 --> 00:08:56,932
ако је за све ефикасне нападаче предност занемарљива. Другим речима,

123
00:08:56,982 --> 00:09:01,808
не постоји ефикасан нападач који може да разликује шифровање m0 од шифровања m1,

124
00:09:01,808 --> 00:09:06,103
и, тиме се каже, понављам, да за ове две

125
00:09:06,103 --> 00:09:10,759
поруке нападач је био у стању да прикаже да није био у стању да разликује

126
00:09:10,759 --> 00:09:15,064
ове две расподеле. Желим да вам покажем, ово је заправо врло

127
00:09:15,064 --> 00:09:19,595
елегантна дефиниција, не мора да тако изгледа одмах, али желим да вам покажем неке

128
00:09:19,595 --> 00:09:24,410
последице ове дефиниције, а видећете зашто је ова дефиниција таква каква јесте.

129
00:09:24,410 --> 00:09:28,601
Погледајмо неке примере. Први пример је - претпоставимо

130
00:09:28,601 --> 00:09:33,190
да имамо разбијену шему шифровања, другим речима, претпоставимо да имамо нападача А

131
00:09:33,190 --> 00:09:38,285
који некако, добивши шифрат, увек може да открије бит најмање

132
00:09:38,285 --> 00:09:44,149
тежине из отвореног текста. Дакле добивши шифру од m0, овај нападач

133
00:09:44,149 --> 00:09:48,799
може да добије бит најмање тежине у m0. Ово је јако лоша

134
00:09:48,799 --> 00:09:52,911
шема шифровања, зато што одаје бит најмање тежине из

135
00:09:52,911 --> 00:09:57,128
отвореног текста самим шифратом. Желим да вам покажем да ова шема није

136
00:09:57,128 --> 00:10:01,609
семантички безбедна, чиме се показује да ако систем јесте семантички

137
00:10:01,609 --> 00:10:05,931
безбедан, не постоји нападач ове врсте. Погледајмо зашто овај систем

138
00:10:05,931 --> 00:10:10,254
није семантички безбедан. Ми ћемо да користимо

139
00:10:10,254 --> 00:10:14,366
нашег нападача, који може да открије битове најмање тежине, ми ћемо да

140
00:10:14,366 --> 00:10:18,372
га користимо да разбијемо семантичку безбедност, то јест да разликујемо

141
00:10:18,372 --> 00:10:22,755
оглед 0 од огледа 1. Ево шта ћемо да урадимо.

142
00:10:22,755 --> 00:10:26,987
Ми смо алгоритам В, а овај алгоритам В ће да користи

143
00:10:26,987 --> 00:10:31,165
алгоритам А у свом телу. Дакле прво што ће да се деси је,

144
00:10:31,165 --> 00:10:35,608
наравно изазивач ће да одабере насумични кључ, и прво што ће да се деси је

145
00:10:35,608 --> 00:10:39,762
да ћемо да избацимо две поруке,

146
00:10:39,762 --> 00:10:43,493
а које ће да имају различите битове најмање тежине.

147
00:10:43,493 --> 00:10:47,727
Једна ће да се завршава са 0, а друга са 1.

148
00:10:47,727 --> 00:10:51,205
И шта ће сада изазивач да уради? Он ће да нам да

149
00:10:51,205 --> 00:10:55,238
шифровање било од m0 било од m1, у зависности од тога да ли смо у огледу 0

150
00:10:55,238 --> 00:10:59,120
или у огледу 1. А тада ћемо само да проследимо овај шифрат нападачу,

151
00:10:59,120 --> 00:11:03,871
дакле нападачу А. А које је својство нападача А? Добивши шифрат,

152
00:11:03,871 --> 00:11:08,505
нападач А може да нам каже који је бит најмање тежине отвореног текста.

153
00:11:08,505 --> 00:11:13,374
Другим речима, нападач ће да избаци бит најмање тежине од m0 или m1,

154
00:11:13,374 --> 00:11:17,892
а то је практично бит b. И затим ћемо само да

155
00:11:17,892 --> 00:11:23,050
избацимо то као наш погодак, назовимо то b'. Дакле овим

156
00:11:23,050 --> 00:11:28,376
се описује семантичка безбедност нападача. А ви ми кажите шта се предност

157
00:11:28,376 --> 00:11:33,593
над семантичком безбедношћу код овог нападача? Па погледајмо: у огледу 0, која је

158
00:11:33,593 --> 00:11:38,775
вероватноћа да нападач В избацује 1? Дакле у огледу 0 се увек

159
00:11:38,775 --> 00:11:43,704
добија шифровање од m0, и зато нападач А увек избацује

160
00:11:43,704 --> 00:11:48,633
бит најмање тежине од m0, а то је увек 0. У огледу

161
00:11:48,633 --> 00:11:53,120
0, В увек избацује 0. Дакле вероватноћа да ће да избаци 1 је нула.

162
00:11:53,120 --> 00:11:57,827
Међутим у огледу 1, добијамо шифровану m1. Дакле колико је вероватно да ће

163
00:11:57,827 --> 00:12:02,783
нападач В да избаци 1 у огледу 1? Па, увек ће да избаци 1,

164
00:12:02,783 --> 00:12:07,428
због својства алгоритма А. И услед тога, предност је практично 1.

165
00:12:07,428 --> 00:12:12,384
Дакле то је велика предност, највећа што може да буде. Што значи да је овај

166
00:12:12,384 --> 00:12:17,091
нападач потпуно разбио систем. Дакле под семантичком

167
00:12:17,091 --> 00:12:22,295
безбедношћу, просто сазнавање бита најмање тежине је довољно да потпуно

168
00:12:22,295 --> 00:12:27,187
разбије систем - под дефиницијом семантичке безбедности. Занимљива ствар

169
00:12:27,187 --> 00:12:32,388
овде је наравно да се не ради само о биту најмање тежине,

170
00:12:32,388 --> 00:12:37,117
у ствари, било који бит поруке, на пример, бит највеће тежине,

171
00:12:37,117 --> 00:12:42,040
седми бит, можда XOR свих битова поруке, итд,

172
00:12:42,040 --> 00:12:46,552
било каква информација, било који бит отвореног текста који може да

173
00:12:46,552 --> 00:12:50,814
се сазна, значио би да систем није семантички безбедан.

174
00:12:50,814 --> 00:12:55,532
Дакле све што нападач треба да уради јесте да се појави са две поруке,

175
00:12:55,532 --> 00:13:00,249
m0 и m1, које су такве да је код једне од њих, то што сазнаје има вредност 0,

176
00:13:00,249 --> 00:13:04,626
а код друге има вредност 1. На пример, А је сазнао XOR

177
00:13:04,626 --> 00:13:08,775
битова поруке - тада m0 и m1 само треба да имају

178
00:13:08,775 --> 00:13:13,265
различити XOR свих битова у поруци, и нападач А би могао

179
00:13:13,265 --> 00:13:18,174
да разбије семантичку безбедност. Практично ако је шифра

180
00:13:18,174 --> 00:13:23,203
семантички безбедна, никаква информација се не открива

181
00:13:23,203 --> 00:13:27,392
ефикасном нападачу. То је управо и појам савршене тајности, али

182
00:13:27,392 --> 00:13:31,318
примењен само на ефикасне нападаче уместо на све нападаче.

183
00:13:31,318 --> 00:13:35,045
Следеће што желим да вам покажем је да је једнократна бележница

184
00:13:35,045 --> 00:13:38,821
семантички безбедна, и боље би било да јесте, зато што је

185
00:13:38,821 --> 00:13:42,773
и више од тога, она је савршено безбедна. Погледајмо зашто ово важи.

186
00:13:42,773 --> 00:13:47,010
Још једном посматрамо овакве огледе, дакле претпоставимо да нападач претендује

187
00:13:47,010 --> 00:13:51,449
да разбије семантичку безбедност једнократне бележнице. Он ће најпре

188
00:13:51,449 --> 00:13:55,874
да избаци две поруке, m0 и m1, исте дужине.

189
00:13:55,874 --> 00:13:59,667
Шта добија као изазов? Добија или шифровану

190
00:13:59,667 --> 00:14:03,988
m0 или шифровану m1, под једнократном бележницом.

191
00:14:03,988 --> 00:14:07,886
И покушава да разликује ове две могуће шифрате које добија.

192
00:14:07,886 --> 00:14:12,259
У огледу 0, добија шифровану m0, а у огледу 1, добија

193
00:14:12,259 --> 00:14:16,579
шифровану m1. Поставља се питање, која је предност нападача А

194
00:14:16,579 --> 00:14:21,297
над једнократном бележницом? Подсећам вас да је својство једнократне бележнице

195
00:14:21,297 --> 00:14:26,208
да је k XOR m0 са расподелом истоветном са k XOR m1.

196
00:14:26,208 --> 00:14:31,187
Другим речима, ово су потпуно подударне расподеле.

197
00:14:31,187 --> 00:14:36,026
То је својство XOR - ако XOR-ујемо случајни

198
00:14:36,026 --> 00:14:40,674
кључ k са било чим, m0 или m1, добијамо униформну расподелу.

199
00:14:40,674 --> 00:14:45,382
Дакле у оба случаја алгоритам А добија на улазу потпуно исту расподелу. Можда

200
00:14:45,382 --> 00:14:50,209
униформну расподелу шифрата. И зато ће да се понаша на потпуно

201
00:14:50,209 --> 00:14:55,036
исти начин у оба случаја, зато што добија потпуно исту расподелу на улазу.

202
00:14:55,036 --> 00:14:59,699
Следи да је његова предност 0, што значи да једнократна бележница јесте семантички

203
00:14:59,723 --> 00:15:04,148
безбедна. Занимљиво је то што, не само што је семантички безбедна,

204
00:15:04,148 --> 00:15:08,244
већ је семантички безбедна за све нападаче. Не морамо чак да се ограничимо

205
00:15:08,244 --> 00:15:12,450
на ефикасне нападаче. Нема нападача, колико год паметан био, који

206
00:15:12,450 --> 00:15:16,875
би могао да разликује k XOR m0 од k XOR m1, зато што су ове две

207
00:15:16,875 --> 00:15:21,299
расподеле истоветне. Добро, дакле једнократна бележница је семантички безбедна.

208
00:15:21,299 --> 00:15:25,559
Тиме смо завршили са дефиницијом семантичке безбедности, и следеће што ћемо

209
00:15:25,559 --> 00:15:30,093
да докажемо је да из безбедности PRG-а следи да је шифра тока

210
00:15:30,093 --> 00:15:31,186
семантички безбедна.