0:00:00.000,0:00:04.262
Сада када смо видели неколико примера историјских шифри, које су све са значајним

0:00:04.262,0:00:07.130
слабостима, прећи ћемо на другу тему и говорићемо о много боље осмишљеним

0:00:10.122,0:00:13.115
шифрама. Али пре тога, желим да [br]прецизније одредим појам шифре.

0:00:13.115,0:00:17.432
Пре свега, шифра се у ствари[br]састоји од два алгоритма.

0:00:17.432,0:00:21.694
Постоје алгоритам за шифровање [br]и за дешифровање. Међутим,

0:00:21.694,0:00:26.012
шифра се дефинише са три елемента. [br]Ту је скуп свих могућих кључева,

0:00:26.012,0:00:31.292
који ћу да означим словом К, и понекад[br]ћу да га називам простором кључева -

0:00:31.292,0:00:35.968
скуп свих могућих кључева.[br]Затим ту је скуп свих могућих порука,

0:00:35.968,0:00:40.365
и скуп свих могућих шифрованих текстова.[br]Значи ова тројка на неки начин одређује

0:00:40.365,0:00:44.756
околину над којом се дефинише шифра.[br]Сама шифра је пар ефикасних

0:00:44.756,0:00:49.236
алгоритама Е и D. Е је алгоритам за шифровање;[br]D је алгоритам за дешифровање.

0:00:49.236,0:00:57.762
Наравно, Е узима кључеве и поруке,[br]и враћа шифроване текстове - шифрате.

0:00:57.762,0:01:06.770
Алгоритам за дешифровање узима [br]кључеве и шифрате, а враћа поруке.

0:01:06.770,0:01:12.282
Једини захтев је да ови алгоритми буду доследни.

0:01:12.282,0:01:17.933
Ово својство се назива "исправност".[br]Значи за сваку поруку из простора порука,

0:01:17.933,0:01:23.593
и за сваки кључ у простору кључева, [br]мора да важи, да ако шифрујем

0:01:23.593,0:01:29.185
поруку кључем k и дешифрујем [br]користећи овај исти кључ,

0:01:29.185,0:01:34.711
треба да добијем првобитну поруку.[br]Дакле ова једначина назива се

0:01:34.711,0:01:39.974
једначином доследности, и она мора [br]да важи за сваку шифру,

0:01:39.974,0:01:44.970
иначе не би било могуће дешифровање.

0:01:44.970,0:01:49.782
Желим да нагласим да је реч "ефикасан"[br]под наводницима, зато што она

0:01:49.782,0:01:54.041
може да има различито значење.[br]За оне више окренуте ка теорији,

0:01:54.041,0:01:58.811
"ефикасан" значи извршава се у полиномном времену, тј. алгоритми Е и D

0:01:58.811,0:02:02.842
извршиви су у полиномној временској [br]зависности од величине улаза.

0:02:02.842,0:02:07.045
За оне окренуте ка пракси, "ефикасан"[br]значи извршив у оквиру задатог времена.

0:02:07.045,0:02:11.474
На пример, алгоритам Е треба да обради[br]гигабајт података за мање од једног минута.

0:02:11.474,0:02:16.073
У сваком случају, реч "ефикасан" [br]обухвата оба ова виђења,

0:02:16.073,0:02:20.158
и можете да је тумачите како вам више одговара.[br]Ја ћу и у наставку да је користим

0:02:20.158,0:02:24.139
под наводницима; као што сам рекао,[br]ако више нагињете ка теорији

0:02:24.189,0:02:27.964
сматрајте да се односи на полиномно време,[br]иначе, на задато временско ограничење.

0:02:27.964,0:02:32.100
Следеће што желим да напоменем,[br]тиче се алгоритма Е.

0:02:32.100,0:02:36.455
Најчешће је ово алгоритам насумичних вредности; то јест приликом шифровања

0:02:36.455,0:02:40.981
порука, алгоритам Е узима случајне битове,

0:02:40.981,0:02:45.676
и користи ове битове да шифрује [br]поруке које му се прослеђују.

0:02:45.676,0:02:50.258
Са друге стране, алгоритам за дешифровање [br]увек је алгоритам са утврђеним излазима.

0:02:50.258,0:02:54.558
То значи да за исте вредности кључа и шифрата[br]увек даје исти излаз, независно

0:02:54.558,0:02:58.970
од било какве насумичности [br]која постоји у алгоритму.

0:02:58.970,0:03:03.552
Сада када мало боље схватамо појам шифре,[br]желим да вам дам први пример безбедне шифре.

0:03:03.552,0:03:08.364
Зове се "једнократна бележница". Развио ју је Вернам почетком 20-тог века.

0:03:08.364,0:03:12.724
Пре него што објасним начин рада ове шифре,

0:03:12.724,0:03:17.383
хајде да користећи праву терминологију[br]кажемо шта овде видимо.

0:03:17.383,0:03:22.221
Простор порука за Вернамову шифру - једнократну бележницу - је исти као и простор шифрата,

0:03:22.221,0:03:27.653
а то је једноставно скуп свих низова бинарних бројева дужине n. То значи,

0:03:27.653,0:03:33.854
свих низова битова знакова 0 и 1.[br]Простор кључева је исти као простор порука,

0:03:33.854,0:03:40.134
што је такође скуп свих n-битних бинарних низова. Дакле, кључ код једнократне бележнице

0:03:40.134,0:03:46.290
јесте насумично изабран низ битова,

0:03:46.290,0:03:51.508
дужине која је иста као дужина поруке[br]која треба да се шифрује.

0:03:51.508,0:03:56.726
Сада када смо видели чиме је дефинисана шифра,

0:03:56.726,0:04:02.010
можемо да видимо како ради, [br]што је у ствари врло једноставно.

0:04:02.010,0:04:07.812
Шифрати, који су производ шифровања[br]поруке одређеним кључем,

0:04:07.812,0:04:13.766
добијају се операцијом XOR над [br]овим двема вредностима: К XOR М.

0:04:13.766,0:04:20.026
Подсетимо се ознаке за операцију XOR.[br]XOR значи збир по модулу 2.

0:04:20.026,0:04:26.825
Ако узмем рецимо поруку 0110111,

0:04:26.825,0:04:33.871
и неки кључ, нпр. 1011001,[br]када шифрујем поруку на овај начин,

0:04:33.871,0:04:38.838
све што треба је да израчунам XOR[br]ове две вредности.

0:04:38.838,0:04:43.942
Другим речима, одрадим збир по модулу 2,[br]бит по бит; и добијем: 1101110.

0:04:43.942,0:04:48.645
Ово је шифрат.[br]Како ћу да дешифрујем?

0:04:48.645,0:04:52.893
У ствари, поновим исту операцију.[br]Шифрат се дешифрује овим истим кључем.

0:04:52.893,0:04:57.248
Извршим операцију XOR над кључем и шифратом.

0:04:57.248,0:05:01.819
Све што остаје је да потврдимо[br]да је задовољен захтев за доследношћу.

0:05:01.819,0:05:06.443
Сада ћу да урадим ово поступно, а у будуће [br]ћу да претпоставим да вам је познато.

0:05:06.443,0:05:10.798
Дакле желимо да се уверимо[br]да дешифровањем шифрата,

0:05:10.798,0:05:14.893
шифрованог одређеним кључем,[br]обавезно добијам поруку m.

0:05:14.893,0:05:20.481
Да видимо...[br]Посматрам шифрат над k и m.

0:05:20.481,0:05:25.996
По дефиницији ово је k XOR m.[br]А шта представља дешифровање

0:05:25.996,0:05:31.628
вредности k XOR m? То је k XOR (k XOR m).[br]А будући да је XOR збир по модулу 2,

0:05:31.628,0:05:36.948
сабирање је асоцијативно,[br]дакле ово је исто што и (k XOR k) XOR m,

0:05:36.948,0:05:43.007
а као што знате (k XOR k) је нула,[br]а нула XOR било која вредност

0:05:43.007,0:05:49.066
је само m. Овим смо показали да је[br]једнократна бележница шифра,

0:05:49.066,0:05:54.277
али ово нам ништа не говори о безбедности шифре.

0:05:54.277,0:05:58.319
Прећи ћемо на безбедност за који час,[br]али пре тога, само једно питање,

0:05:58.319,0:06:02.205
да будемо сигурни да се разумемо.[br]Рецимо да вам је дата

0:06:02.205,0:06:06.092
порука m, и шифрат те поруке,[br]коришћењем једнократне бележнице.

0:06:06.092,0:06:10.522
Све што знате је порука и шифрат.[br]Моје питање за вас је,

0:06:10.522,0:06:15.467
знајући пар m и с, да ли можете да[br]откријете кључ који је коришћен

0:06:15.467,0:06:20.588
приликом добијања с на основу m?

0:06:20.588,0:06:23.030
Надам се да сви уочавате да је, у ствари,[br]знајући поруку и шифрат,

0:06:23.030,0:06:25.473
врло лако добити вредност кључа.[br]Конкретно, кључ је једноставно

0:06:25.473,0:06:30.241
m XOR с. Ако вам није очигледно,

0:06:30.241,0:06:35.238
видећемо зашто је то тако, мало касније.

0:06:35.238,0:06:40.198
Једнократна бележница је одлична[br]што се тиче перформанси,

0:06:40.198,0:06:44.656
све што се извршава је XOR операција између кључа и поруке, дакле ово је врло, врло брза

0:06:44.656,0:06:48.464
шифра за рад са врло великим порукама.

0:06:48.464,0:06:52.768
Нажалост, у пракси је тешко примењива.[br]Разлог за то је што су кључеви

0:06:52.768,0:06:56.907
исте дужине као и порука.[br]Значи ако Алиса и Боб желе

0:06:56.907,0:07:01.321
безбедну комуникацију, тј. Алиса жели[br]да пошаље поруку Бобу, пре него

0:07:01.321,0:07:06.011
што почне са слањем поруке,[br]она мора да пошаље Бобу кључ,

0:07:06.011,0:07:10.536
који је исте дужине као и порука.[br]Али, ако постоји начин да пошаље

0:07:10.536,0:07:15.061
Бобу тајни кључ исте дужине као и порука,[br]може лепо да тим начином пошаље

0:07:15.061,0:07:19.439
и саму поруку. Дакле чињеница да је кључ[br]исте дужине као и порука,

0:07:19.439,0:07:23.490
је прилично незгодна, и чини овај начин[br]шифрирања јако тешким за примену.

0:07:23.490,0:07:28.040
Мада ћемо да видимо да је замисао иза[br]једнократне бележнице врло корисна,

0:07:28.040,0:07:32.590
а ово ћемо да покажемо мало касније.[br]А сада да се задржимо мало на безбедности.

0:07:32.590,0:07:36.918
Поставља се очигледно питање:[br]зашто је једнократна бележница безбедна?

0:07:36.918,0:07:41.195
Зашто је ово добра шифра?[br]Да бисмо одговорили на ово питање,

0:07:41.195,0:07:45.191
најпре морамо да видимо шта је то уопште[br]безбедна шифра, шта чини шифру

0:07:45.191,0:07:49.759
безбедном? Да бисмо се бавили безбедношћу шифара, морамо да се позабавимо најпре

0:07:49.759,0:07:54.962
теоријом информације. Заправо, прва особа[br]која се озбиљно бавила питањем

0:07:55.150,0:08:00.076
безбедности шифара, јесте чувени отац теорије информације, Клод Шенон,

0:08:00.076,0:08:05.042
који је још 1949. објавио познати рад,[br]у којем је проучавао

0:08:05.042,0:08:10.603
безбедност једнократне бележнице.[br]Замисао иза Шенонове дефиниције безбедности

0:08:10.603,0:08:15.182
је следећа: у основи, ако је све[br]што стоји на располагању сам шифрат,

0:08:15.182,0:08:19.379
на основу њега не сме ништа да се сазна о отвореном тексту.

0:08:19.379,0:08:23.413
Другим речима, шифрат не сме да открива никакву информацију о отвореном тексту.

0:08:23.413,0:08:28.047
И видите сада зашто је неко ко је изумео теорију информације могао да дође до овог појма,

0:08:28.047,0:08:32.517
зато што је неопходно да се искаже, формално објасни, шта у ствари представља информација

0:08:32.517,0:08:37.653
о отвореном тексту. Сада ћу да вам покажем Шенонову дефиницију,

0:08:37.653,0:08:42.841
најпре ћу да је испишем полако.

0:08:42.841,0:08:48.029
Рецимо да имамо шифру (Е, D) одређену над тројком (K, M, C) као и раније.

0:08:48.029,0:08:53.411
K, M, и C одређују простор кључева, простор порука и простор шифрата.

0:08:53.411,0:08:58.404
Шифра има савршену тајност

0:08:58.404,0:09:03.592
ако важи следеће: за сваке две поруке m0 и m1,

0:09:03.592,0:09:08.684
у простору порука, при чему је једини захтев[br]за ове две поруке

0:09:08.684,0:09:13.831
да буду исте дужине (видећемо зашто

0:09:13.831,0:09:19.106
је потребан овај услов за који час)[br]и за сваки шифрат,

0:09:19.106,0:09:25.221
у простору шифрата, дакле за сваки пар порука[br]и за сваки шифрат,

0:09:25.221,0:09:31.118
мора да важи, да је вероватноћа да се

0:09:31.357,0:09:37.096
шифровањем m0 са k добија c,

0:09:37.096,0:09:43.551
иста као и вероватноћа да се

0:09:43.551,0:09:49.819
шифровањем m1 са k добија c.

0:09:49.819,0:09:54.920
Дакле вероватноћа да шифровањем m1 добијемо с[br]је потпуно иста као и вероватноћа

0:09:54.920,0:09:59.955
да шифровањем m0 добијемо с.

0:09:59.955,0:10:04.658
Дакле да ово важи за кључеве чија је расподела

0:10:04.658,0:10:10.157
равномерна у простору кључева.[br]Користићу ознаку к са стрелицом

0:10:10.157,0:10:15.390
са малим r изнад да означим чињеницу[br]да је к променљива са насумичном вредношћу

0:10:15.390,0:10:20.491
која је равномерно узоркована у простору К.[br]Ово је главни садржај

0:10:20.491,0:10:25.892
Шенонове дефиниције. Хајде да размислимо мало[br]о томе шта се овом дефиницијом каже.

0:10:25.892,0:10:30.965
Дакле шта значи да су ове[br]две вероватноће једнаке?

0:10:30.965,0:10:36.304
То значи да ако сам ја нападач[br]и пресретнем одређени шифрат с,

0:10:36.304,0:10:41.577
тада је у ствари, вероватноћа да је[br]овај шифрат шифра за m0, иста

0:10:41.577,0:10:46.798
као и вероватноћа да је он шифра за m1.

0:10:46.798,0:10:52.219
Зато што су ове две вероватноће једнаке.[br]Дакле ако је све што имам шифрат с,

0:10:52.219,0:10:57.639
тада ја никако не могу да знам да ли је[br]шифрат потекао од m0 или од m1,

0:10:57.639,0:11:03.196
јер је, понављам, вероватноћа да се добије с

0:11:03.196,0:11:08.651
иста за обе ове поруке.

0:11:08.651,0:11:13.286
Овде поново имамо дефиницију.[br]И сада само желим да ово поново

0:11:13.286,0:11:17.749
запишем мало прецизније.

0:11:17.749,0:11:22.326
Дакле ако имам на располагању неки шифрат,

0:11:22.326,0:11:27.125
не могу на основу тога да тврдим[br]од које поруке потиче m0 или m1.

0:11:27.125,0:11:32.090
Штавише, ово важи за све поруке, [br]за сваки пар порука.

0:11:32.090,0:11:37.117
И не само да не могу да разликујем да ли је шифрат добијен од m0 или m1,

0:11:37.117,0:11:42.144
не знам ни да ли потиче од m2, m3, m4, m5,

0:11:42.144,0:11:47.109
зато што све оне имају исту вероватноћу[br]да се од њих добије с.

0:11:47.109,0:11:52.074
То значи, да приликом шифровања порука једнократном бележницом,

0:11:52.074,0:11:56.729
чак и најмоћнији декриптор,[br]колико год паметан био,

0:11:56.729,0:12:02.530
не може да сазна ништа о отвореном тексту

0:12:02.530,0:12:09.624
на основу шифрата.[br]Да кажемо ово на још један начин,

0:12:09.624,0:12:16.315
не постоји напад који је усмерен само на шифрат

0:12:16.315,0:12:23.263
на шифру са савршеном тајношћу.[br]Напади који су усмерени само на шифрат

0:12:23.263,0:12:29.440
нису једини постојећи напади - постоје друге врсте напада, којима је подложна оваква шифра.

0:12:32.160,0:12:36.772
Сада када смо разумели појам савршене тајности,

0:12:36.772,0:12:41.327
поставља се питање, да ли је могуће направити шифру са овом особином?

0:12:41.327,0:12:45.517
Испоставља се да једнократна књижница[br]има савршену тајност.

0:12:45.517,0:12:50.719
Желим и да вам изведем доказ за ово,[br]то је уједно и Шенонов први резултат,

0:12:50.719,0:12:55.858
доказ је једноставан, тако да[br]хајде да га одмах изведемо.

0:12:55.858,0:13:01.061
Потребно је да протумачимо шта то значи,[br]та вероватноћа Pr (Е(k, m0) = с).

0:13:01.061,0:13:06.200
Није тешко да се види да за сваку поруку

0:13:06.200,0:13:11.022
и за сваки шифрат, вероватноћа да се шифровањем m кључем k

0:13:11.022,0:13:16.161
добија с, при чему се, по дефиницији,[br]кључ бира насумице,

0:13:16.161,0:13:23.720
представља количник броја кључева из скупа К,

0:13:24.758,0:13:31.533
таквих да ако шифрујем m са k добијам с,

0:13:31.533,0:13:37.207
подељених са укупним бројем могућих кључева.

0:13:37.207,0:13:42.833
То је вероватноћа да ако одаберем насумице неки кључ, он ће да преслика m у с.

0:13:42.833,0:13:47.707
To je практично број кључева који пресликавају m у с,[br]кроз укупни број кључева.

0:13:47.707,0:13:53.406
Претпоставимо сада да имамо шифру[br]такву да за све поруке и све шифрате,

0:13:53.406,0:13:58.967
важи да ако погледам овај број, број k из скупа К, таквих да је Е(k, m) = с

0:13:58.967,0:14:04.391
другим речима, посматрам број кључева

0:14:04.391,0:14:09.259
који пресликавају m у с; претпоставимо да је[br]овај број нека константа.

0:14:09.259,0:14:14.079
Рецимо да је то 2, 3, 10 или 15.

0:14:14.079,0:14:19.332
Рецимо да је то константна вредност. У том случају, према дефиницији, за свако m0 и m1

0:14:19.332,0:14:24.747
и за свако с, ова вероватноћа мора да буде иста,[br]зато што је именилац исти,

0:14:24.747,0:14:30.097
бројилац исти, нека константа,[br]и из тога следи да је и вероватноћа

0:14:30.097,0:14:35.644
увек иста за свако m и с. Дакле ако је ово тачно, шифра мора да има

0:14:35.644,0:14:43.616
савршену тајност. Да видимо сада[br]шта можемо да кажемо

0:14:43.616,0:14:48.804
о овој величини за једнократну бележницу.[br]Питање за вас је, ако имате

0:14:48.804,0:14:54.770
на располагању шифрат и поруку,[br]колико једнократних кључева постоји,

0:14:54.770,0:15:00.381
који пресликавају поруку m у с?[br]Другим речима, колико кључева

0:15:00.381,0:15:06.101
постоји, таквих да је m XOR k = c?

0:15:06.101,0:15:12.683
Надам се да сте одговорили да је један.[br]Да видимо и зашто:

0:15:12.683,0:15:18.303
За једнократну бележницу, израз Е(k, m) = c, [br]по дефиницији значи

0:15:18.303,0:15:24.885
да је k XOR m = c.[br]Али то такође значи да мора да је

0:15:24.885,0:15:31.766
m XOR с = k. Ово смо добили тако што смо извршили XOR обе стране са m.

0:15:31.766,0:15:37.561
Из овога произилази,[br]да је за једнократну бележницу,

0:15:37.561,0:15:43.707
број кључева у К, таквих да је E(k, m) = c, једноставно 1,

0:15:43.707,0:15:49.852
и то важи за све поруке и шифрате. Тако да, на основу претходно реченог,

0:15:49.852,0:15:54.987
произилази да једнократна бележница има савршену тајност.

0:15:54.987,0:15:59.093
Овим је доказ завршен.[br]Ово је врло једноставна лема.

0:15:59.093,0:16:03.644
Међутим, иако је толико једноставно[br]да се она докаже,

0:16:03.644,0:16:08.194
из овог доказа произилази јако моћан закључак.

0:16:08.194,0:16:12.328
Ово у ствари значи да за једнократну бележницу не постоји напад који се ослања само на шифрат.

0:16:12.328,0:16:16.393
Дакле за разлику од шифре замене, или Вижнерове шифре, или шифарског диска,

0:16:16.393,0:16:20.778
које су све могле да буду разбијене нападом који се ослања само на шифрат,

0:16:20.778,0:16:25.110
код једнократне бележнице, како смо доказали, ово једноставно није могуће.

0:16:25.110,0:16:29.281
На основу шифрата, ништа се не сазнаје о отвореном тексту. Али, као што видимо,

0:16:29.281,0:16:33.131
ово није крај приче. То јест, јесмо ли завршили? Будући да смо открили начин

0:16:33.131,0:16:37.359
да шифрирамо тако да декриптор не може да открије ништа

0:16:37.359,0:16:41.206
о нашој поруци, можда смо дакле завршили са течајем? Али заправо, као што ћемо да видимо,

0:16:41.206,0:16:45.261
постоје и други напади. У ствари, једнократна бележница и није тако безбедна шифра.

0:16:45.261,0:16:49.316
Постоје други могући напади,

0:16:49.316,0:16:54.075
које ћемо ускоро да видимо. Наглашавам поново ову чињеницу, да и поред савршене тајности,

0:16:54.075,0:16:58.785
не произилази да је једнократна бележница безбедна шифра. Али, као што смо рекли,

0:16:58.785,0:17:03.733
код једнократне бележнице незгодно је то[br]што је тајни кључ јако дугачак.

0:17:03.733,0:17:08.071
Ако постоји начин да се тајни кључ безбедно пренесе другој страни, онда може

0:17:08.071,0:17:12.253
тим истим начином да се саопшти[br]и сама порука другој страни,

0:17:12.253,0:17:16.652
а у том случају уопште нам и не треба шифра.[br]Дакле, још једном, проблем је то

0:17:16.652,0:17:21.105
што једнократна бележница има јако дуги кључ,[br]и намеће се питање да ли постоје

0:17:21.105,0:17:25.450
друге шифре које имају савршену тајност,[br]али много, много краће кључеве?

0:17:25.450,0:17:30.136
Лоша вест је то што је Шенон, након што је доказао да једнократна бележница има

0:17:30.136,0:17:34.945
савршену тајност, доказао и теорему[br]да свака шифра која има

0:17:34.945,0:17:39.878
савршену тајност, мора да има на располагању најмање исти број кључева

0:17:39.878,0:17:44.935
као и број порука које се обрађују шифром. То значи, да ако шифра има савршену тајност,

0:17:44.935,0:17:51.037
тада број кључева, то јест дужина кључа

0:17:51.037,0:17:56.309
мора да буде већа или једнака дужини поруке.

0:17:56.309,0:18:00.834
Заправо, пошто једнократна бележница задовољава овај услов код једнакости,

0:18:00.834,0:18:04.862
она је у ствари оптимална шифра која има савршену тајност.

0:18:04.862,0:18:09.056
Дакле једнократна бележница је занимљива шифра,

0:18:09.056,0:18:13.360
али јако тешка за примену,

0:18:13.360,0:18:17.790
због дугачних кључева. Сам појам савршене тајности,

0:18:17.790,0:18:21.840
иако врло занимљив, говори нам у суштини да шифре које су згодне за примену

0:18:21.840,0:18:26.279
не могу да буду безбедне. Али, као што смо напоменули, сама замисао која је

0:18:26.279,0:18:30.994
у основи једнократне бележнице је јако добра.[br]А у следећој лекцији ћемо да видимо,

0:18:30.994,0:18:33.547
како да на основу ње направимо применљив систем.