[Script Info] Title: [Events] Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text Dialogue: 0,0:00:00.00,0:00:04.26,Default,,0000,0000,0000,,Сада када смо видели неколико примера историјских шифри, које су све са значајним Dialogue: 0,0:00:04.26,0:00:07.13,Default,,0000,0000,0000,,слабостима, прећи ћемо на другу тему и говорићемо о много боље осмишљеним Dialogue: 0,0:00:10.12,0:00:13.12,Default,,0000,0000,0000,,шифрама. Али пре тога, желим да \Nпрецизније одредим појам шифре. Dialogue: 0,0:00:13.12,0:00:17.43,Default,,0000,0000,0000,,Пре свега, шифра се у ствари\Nсастоји од два алгоритма. Dialogue: 0,0:00:17.43,0:00:21.69,Default,,0000,0000,0000,,Постоје алгоритам за шифровање \Nи за дешифровање. Међутим, Dialogue: 0,0:00:21.69,0:00:26.01,Default,,0000,0000,0000,,шифра се дефинише са три елемента. \NТу је скуп свих могућих кључева, Dialogue: 0,0:00:26.01,0:00:31.29,Default,,0000,0000,0000,,који ћу да означим словом К, и понекад\Nћу да га називам простором кључева - Dialogue: 0,0:00:31.29,0:00:35.97,Default,,0000,0000,0000,,скуп свих могућих кључева.\NЗатим ту је скуп свих могућих порука, Dialogue: 0,0:00:35.97,0:00:40.36,Default,,0000,0000,0000,,и скуп свих могућих шифрованих текстова.\NЗначи ова тројка на неки начин одређује Dialogue: 0,0:00:40.36,0:00:44.76,Default,,0000,0000,0000,,околину над којом се дефинише шифра.\NСама шифра је пар ефикасних Dialogue: 0,0:00:44.76,0:00:49.24,Default,,0000,0000,0000,,алгоритама Е и D. Е је алгоритам за шифровање;\ND је алгоритам за дешифровање. Dialogue: 0,0:00:49.24,0:00:57.76,Default,,0000,0000,0000,,Наравно, Е узима кључеве и поруке,\Nи враћа шифроване текстове - шифрате. Dialogue: 0,0:00:57.76,0:01:06.77,Default,,0000,0000,0000,,Алгоритам за дешифровање узима \Nкључеве и шифрате, а враћа поруке. Dialogue: 0,0:01:06.77,0:01:12.28,Default,,0000,0000,0000,,Једини захтев је да ови алгоритми буду доследни. Dialogue: 0,0:01:12.28,0:01:17.93,Default,,0000,0000,0000,,Ово својство се назива "исправност".\NЗначи за сваку поруку из простора порука, Dialogue: 0,0:01:17.93,0:01:23.59,Default,,0000,0000,0000,,и за сваки кључ у простору кључева, \Nмора да важи, да ако шифрујем Dialogue: 0,0:01:23.59,0:01:29.18,Default,,0000,0000,0000,,поруку кључем k и дешифрујем \Nкористећи овај исти кључ, Dialogue: 0,0:01:29.18,0:01:34.71,Default,,0000,0000,0000,,треба да добијем првобитну поруку.\NДакле ова једначина назива се Dialogue: 0,0:01:34.71,0:01:39.97,Default,,0000,0000,0000,,једначином доследности, и она мора \Nда важи за сваку шифру, Dialogue: 0,0:01:39.97,0:01:44.97,Default,,0000,0000,0000,,иначе не би било могуће дешифровање. Dialogue: 0,0:01:44.97,0:01:49.78,Default,,0000,0000,0000,,Желим да нагласим да је реч "ефикасан"\Nпод наводницима, зато што она Dialogue: 0,0:01:49.78,0:01:54.04,Default,,0000,0000,0000,,може да има различито значење.\NЗа оне више окренуте ка теорији, Dialogue: 0,0:01:54.04,0:01:58.81,Default,,0000,0000,0000,,"ефикасан" значи извршава се у полиномном времену, тј. алгоритми Е и D Dialogue: 0,0:01:58.81,0:02:02.84,Default,,0000,0000,0000,,извршиви су у полиномној временској \Nзависности од величине улаза. Dialogue: 0,0:02:02.84,0:02:07.04,Default,,0000,0000,0000,,За оне окренуте ка пракси, "ефикасан"\Nзначи извршив у оквиру задатог времена. Dialogue: 0,0:02:07.04,0:02:11.47,Default,,0000,0000,0000,,На пример, алгоритам Е треба да обради\Nгигабајт података за мање од једног минута. Dialogue: 0,0:02:11.47,0:02:16.07,Default,,0000,0000,0000,,У сваком случају, реч "ефикасан" \Nобухвата оба ова виђења, Dialogue: 0,0:02:16.07,0:02:20.16,Default,,0000,0000,0000,,и можете да је тумачите како вам више одговара.\NЈа ћу и у наставку да је користим Dialogue: 0,0:02:20.16,0:02:24.14,Default,,0000,0000,0000,,под наводницима; као што сам рекао,\Nако више нагињете ка теорији Dialogue: 0,0:02:24.19,0:02:27.96,Default,,0000,0000,0000,,сматрајте да се односи на полиномно време,\Nиначе, на задато временско ограничење. Dialogue: 0,0:02:27.96,0:02:32.10,Default,,0000,0000,0000,,Следеће што желим да напоменем,\Nтиче се алгоритма Е. Dialogue: 0,0:02:32.10,0:02:36.46,Default,,0000,0000,0000,,Најчешће је ово алгоритам насумичних вредности; то јест приликом шифровања Dialogue: 0,0:02:36.46,0:02:40.98,Default,,0000,0000,0000,,порука, алгоритам Е узима случајне битове, Dialogue: 0,0:02:40.98,0:02:45.68,Default,,0000,0000,0000,,и користи ове битове да шифрује \Nпоруке које му се прослеђују. Dialogue: 0,0:02:45.68,0:02:50.26,Default,,0000,0000,0000,,Са друге стране, алгоритам за дешифровање \Nувек је алгоритам са утврђеним излазима. Dialogue: 0,0:02:50.26,0:02:54.56,Default,,0000,0000,0000,,То значи да за исте вредности кључа и шифрата\Nувек даје исти излаз, независно Dialogue: 0,0:02:54.56,0:02:58.97,Default,,0000,0000,0000,,од било какве насумичности \Nкоја постоји у алгоритму. Dialogue: 0,0:02:58.97,0:03:03.55,Default,,0000,0000,0000,,Сада када мало боље схватамо појам шифре,\Nжелим да вам дам први пример безбедне шифре. Dialogue: 0,0:03:03.55,0:03:08.36,Default,,0000,0000,0000,,Зове се "једнократна бележница". Развио ју је Вернам почетком 20-тог века. Dialogue: 0,0:03:08.36,0:03:12.72,Default,,0000,0000,0000,,Пре него што објасним начин рада ове шифре, Dialogue: 0,0:03:12.72,0:03:17.38,Default,,0000,0000,0000,,хајде да користећи праву терминологију\Nкажемо шта овде видимо. Dialogue: 0,0:03:17.38,0:03:22.22,Default,,0000,0000,0000,,Простор порука за Вернамову шифру - једнократну бележницу - је исти као и простор шифрата, Dialogue: 0,0:03:22.22,0:03:27.65,Default,,0000,0000,0000,,а то је једноставно скуп свих низова бинарних бројева дужине n. То значи, Dialogue: 0,0:03:27.65,0:03:33.85,Default,,0000,0000,0000,,свих низова битова знакова 0 и 1.\NПростор кључева је исти као простор порука, Dialogue: 0,0:03:33.85,0:03:40.13,Default,,0000,0000,0000,,што је такође скуп свих n-битних бинарних низова. Дакле, кључ код једнократне бележнице Dialogue: 0,0:03:40.13,0:03:46.29,Default,,0000,0000,0000,,јесте насумично изабран низ битова, Dialogue: 0,0:03:46.29,0:03:51.51,Default,,0000,0000,0000,,дужине која је иста као дужина поруке\Nкоја треба да се шифрује. Dialogue: 0,0:03:51.51,0:03:56.73,Default,,0000,0000,0000,,Сада када смо видели чиме је дефинисана шифра, Dialogue: 0,0:03:56.73,0:04:02.01,Default,,0000,0000,0000,,можемо да видимо како ради, \Nшто је у ствари врло једноставно. Dialogue: 0,0:04:02.01,0:04:07.81,Default,,0000,0000,0000,,Шифрати, који су производ шифровања\Nпоруке одређеним кључем, Dialogue: 0,0:04:07.81,0:04:13.77,Default,,0000,0000,0000,,добијају се операцијом XOR над \Nовим двема вредностима: К XOR М. Dialogue: 0,0:04:13.77,0:04:20.03,Default,,0000,0000,0000,,Подсетимо се ознаке за операцију XOR.\NXOR значи збир по модулу 2. Dialogue: 0,0:04:20.03,0:04:26.82,Default,,0000,0000,0000,,Ако узмем рецимо поруку 0110111, Dialogue: 0,0:04:26.82,0:04:33.87,Default,,0000,0000,0000,,и неки кључ, нпр. 1011001,\Nкада шифрујем поруку на овај начин, Dialogue: 0,0:04:33.87,0:04:38.84,Default,,0000,0000,0000,,све што треба је да израчунам XOR\Nове две вредности. Dialogue: 0,0:04:38.84,0:04:43.94,Default,,0000,0000,0000,,Другим речима, одрадим збир по модулу 2,\Nбит по бит; и добијем: 1101110. Dialogue: 0,0:04:43.94,0:04:48.64,Default,,0000,0000,0000,,Ово је шифрат.\NКако ћу да дешифрујем? Dialogue: 0,0:04:48.64,0:04:52.89,Default,,0000,0000,0000,,У ствари, поновим исту операцију.\NШифрат се дешифрује овим истим кључем. Dialogue: 0,0:04:52.89,0:04:57.25,Default,,0000,0000,0000,,Извршим операцију XOR над кључем и шифратом. Dialogue: 0,0:04:57.25,0:05:01.82,Default,,0000,0000,0000,,Све што остаје је да потврдимо\Nда је задовољен захтев за доследношћу. Dialogue: 0,0:05:01.82,0:05:06.44,Default,,0000,0000,0000,,Сада ћу да урадим ово поступно, а у будуће \Nћу да претпоставим да вам је познато. Dialogue: 0,0:05:06.44,0:05:10.80,Default,,0000,0000,0000,,Дакле желимо да се уверимо\Nда дешифровањем шифрата, Dialogue: 0,0:05:10.80,0:05:14.89,Default,,0000,0000,0000,,шифрованог одређеним кључем,\Nобавезно добијам поруку m. Dialogue: 0,0:05:14.89,0:05:20.48,Default,,0000,0000,0000,,Да видимо...\NПосматрам шифрат над k и m. Dialogue: 0,0:05:20.48,0:05:25.100,Default,,0000,0000,0000,,По дефиницији ово је k XOR m.\NА шта представља дешифровање Dialogue: 0,0:05:25.100,0:05:31.63,Default,,0000,0000,0000,,вредности k XOR m? То је k XOR (k XOR m).\NА будући да је XOR збир по модулу 2, Dialogue: 0,0:05:31.63,0:05:36.95,Default,,0000,0000,0000,,сабирање је асоцијативно,\Nдакле ово је исто што и (k XOR k) XOR m, Dialogue: 0,0:05:36.95,0:05:43.01,Default,,0000,0000,0000,,а као што знате (k XOR k) је нула,\Nа нула XOR било која вредност Dialogue: 0,0:05:43.01,0:05:49.07,Default,,0000,0000,0000,,је само m. Овим смо показали да је\Nједнократна бележница шифра, Dialogue: 0,0:05:49.07,0:05:54.28,Default,,0000,0000,0000,,али ово нам ништа не говори о безбедности шифре. Dialogue: 0,0:05:54.28,0:05:58.32,Default,,0000,0000,0000,,Прећи ћемо на безбедност за који час,\Nали пре тога, само једно питање, Dialogue: 0,0:05:58.32,0:06:02.20,Default,,0000,0000,0000,,да будемо сигурни да се разумемо.\NРецимо да вам је дата Dialogue: 0,0:06:02.20,0:06:06.09,Default,,0000,0000,0000,,порука m, и шифрат те поруке,\Nкоришћењем једнократне бележнице. Dialogue: 0,0:06:06.09,0:06:10.52,Default,,0000,0000,0000,,Све што знате је порука и шифрат.\NМоје питање за вас је, Dialogue: 0,0:06:10.52,0:06:15.47,Default,,0000,0000,0000,,знајући пар m и с, да ли можете да\Nоткријете кључ који је коришћен Dialogue: 0,0:06:15.47,0:06:20.59,Default,,0000,0000,0000,,приликом добијања с на основу m? Dialogue: 0,0:06:20.59,0:06:23.03,Default,,0000,0000,0000,,Надам се да сви уочавате да је, у ствари,\Nзнајући поруку и шифрат, Dialogue: 0,0:06:23.03,0:06:25.47,Default,,0000,0000,0000,,врло лако добити вредност кључа.\NКонкретно, кључ је једноставно Dialogue: 0,0:06:25.47,0:06:30.24,Default,,0000,0000,0000,,m XOR с. Ако вам није очигледно, Dialogue: 0,0:06:30.24,0:06:35.24,Default,,0000,0000,0000,,видећемо зашто је то тако, мало касније. Dialogue: 0,0:06:35.24,0:06:40.20,Default,,0000,0000,0000,,Једнократна бележница је одлична\Nшто се тиче перформанси, Dialogue: 0,0:06:40.20,0:06:44.66,Default,,0000,0000,0000,,све што се извршава је XOR операција између кључа и поруке, дакле ово је врло, врло брза Dialogue: 0,0:06:44.66,0:06:48.46,Default,,0000,0000,0000,,шифра за рад са врло великим порукама. Dialogue: 0,0:06:48.46,0:06:52.77,Default,,0000,0000,0000,,Нажалост, у пракси је тешко примењива.\NРазлог за то је што су кључеви Dialogue: 0,0:06:52.77,0:06:56.91,Default,,0000,0000,0000,,исте дужине као и порука.\NЗначи ако Алиса и Боб желе Dialogue: 0,0:06:56.91,0:07:01.32,Default,,0000,0000,0000,,безбедну комуникацију, тј. Алиса жели\Nда пошаље поруку Бобу, пре него Dialogue: 0,0:07:01.32,0:07:06.01,Default,,0000,0000,0000,,што почне са слањем поруке,\Nона мора да пошаље Бобу кључ, Dialogue: 0,0:07:06.01,0:07:10.54,Default,,0000,0000,0000,,који је исте дужине као и порука.\NАли, ако постоји начин да пошаље Dialogue: 0,0:07:10.54,0:07:15.06,Default,,0000,0000,0000,,Бобу тајни кључ исте дужине као и порука,\Nможе лепо да тим начином пошаље Dialogue: 0,0:07:15.06,0:07:19.44,Default,,0000,0000,0000,,и саму поруку. Дакле чињеница да је кључ\Nисте дужине као и порука, Dialogue: 0,0:07:19.44,0:07:23.49,Default,,0000,0000,0000,,је прилично незгодна, и чини овај начин\Nшифрирања јако тешким за примену. Dialogue: 0,0:07:23.49,0:07:28.04,Default,,0000,0000,0000,,Мада ћемо да видимо да је замисао иза\Nједнократне бележнице врло корисна, Dialogue: 0,0:07:28.04,0:07:32.59,Default,,0000,0000,0000,,а ово ћемо да покажемо мало касније.\NА сада да се задржимо мало на безбедности. Dialogue: 0,0:07:32.59,0:07:36.92,Default,,0000,0000,0000,,Поставља се очигледно питање:\Nзашто је једнократна бележница безбедна? Dialogue: 0,0:07:36.92,0:07:41.20,Default,,0000,0000,0000,,Зашто је ово добра шифра?\NДа бисмо одговорили на ово питање, Dialogue: 0,0:07:41.20,0:07:45.19,Default,,0000,0000,0000,,најпре морамо да видимо шта је то уопште\Nбезбедна шифра, шта чини шифру Dialogue: 0,0:07:45.19,0:07:49.76,Default,,0000,0000,0000,,безбедном? Да бисмо се бавили безбедношћу шифара, морамо да се позабавимо најпре Dialogue: 0,0:07:49.76,0:07:54.96,Default,,0000,0000,0000,,теоријом информације. Заправо, прва особа\Nкоја се озбиљно бавила питањем Dialogue: 0,0:07:55.15,0:08:00.08,Default,,0000,0000,0000,,безбедности шифара, јесте чувени отац теорије информације, Клод Шенон, Dialogue: 0,0:08:00.08,0:08:05.04,Default,,0000,0000,0000,,који је још 1949. објавио познати рад,\Nу којем је проучавао Dialogue: 0,0:08:05.04,0:08:10.60,Default,,0000,0000,0000,,безбедност једнократне бележнице.\NЗамисао иза Шенонове дефиниције безбедности Dialogue: 0,0:08:10.60,0:08:15.18,Default,,0000,0000,0000,,је следећа: у основи, ако је све\Nшто стоји на располагању сам шифрат, Dialogue: 0,0:08:15.18,0:08:19.38,Default,,0000,0000,0000,,на основу њега не сме ништа да се сазна о отвореном тексту. Dialogue: 0,0:08:19.38,0:08:23.41,Default,,0000,0000,0000,,Другим речима, шифрат не сме да открива никакву информацију о отвореном тексту. Dialogue: 0,0:08:23.41,0:08:28.05,Default,,0000,0000,0000,,И видите сада зашто је неко ко је изумео теорију информације могао да дође до овог појма, Dialogue: 0,0:08:28.05,0:08:32.52,Default,,0000,0000,0000,,зато што је неопходно да се искаже, формално објасни, шта у ствари представља информација Dialogue: 0,0:08:32.52,0:08:37.65,Default,,0000,0000,0000,,о отвореном тексту. Сада ћу да вам покажем Шенонову дефиницију, Dialogue: 0,0:08:37.65,0:08:42.84,Default,,0000,0000,0000,,најпре ћу да је испишем полако. Dialogue: 0,0:08:42.84,0:08:48.03,Default,,0000,0000,0000,,Рецимо да имамо шифру (Е, D) одређену над тројком (K, M, C) као и раније. Dialogue: 0,0:08:48.03,0:08:53.41,Default,,0000,0000,0000,,K, M, и C одређују простор кључева, простор порука и простор шифрата. Dialogue: 0,0:08:53.41,0:08:58.40,Default,,0000,0000,0000,,Шифра има савршену тајност Dialogue: 0,0:08:58.40,0:09:03.59,Default,,0000,0000,0000,,ако важи следеће: за сваке две поруке m0 и m1, Dialogue: 0,0:09:03.59,0:09:08.68,Default,,0000,0000,0000,,у простору порука, при чему је једини захтев\Nза ове две поруке Dialogue: 0,0:09:08.68,0:09:13.83,Default,,0000,0000,0000,,да буду исте дужине (видећемо зашто Dialogue: 0,0:09:13.83,0:09:19.11,Default,,0000,0000,0000,,је потребан овај услов за који час)\Nи за сваки шифрат, Dialogue: 0,0:09:19.11,0:09:25.22,Default,,0000,0000,0000,,у простору шифрата, дакле за сваки пар порука\Nи за сваки шифрат, Dialogue: 0,0:09:25.22,0:09:31.12,Default,,0000,0000,0000,,мора да важи, да је вероватноћа да се Dialogue: 0,0:09:31.36,0:09:37.10,Default,,0000,0000,0000,,шифровањем m0 са k добија c, Dialogue: 0,0:09:37.10,0:09:43.55,Default,,0000,0000,0000,,иста као и вероватноћа да се Dialogue: 0,0:09:43.55,0:09:49.82,Default,,0000,0000,0000,,шифровањем m1 са k добија c. Dialogue: 0,0:09:49.82,0:09:54.92,Default,,0000,0000,0000,,Дакле вероватноћа да шифровањем m1 добијемо с\Nје потпуно иста као и вероватноћа Dialogue: 0,0:09:54.92,0:09:59.96,Default,,0000,0000,0000,,да шифровањем m0 добијемо с. Dialogue: 0,0:09:59.96,0:10:04.66,Default,,0000,0000,0000,,Дакле да ово важи за кључеве чија је расподела Dialogue: 0,0:10:04.66,0:10:10.16,Default,,0000,0000,0000,,равномерна у простору кључева.\NКористићу ознаку к са стрелицом Dialogue: 0,0:10:10.16,0:10:15.39,Default,,0000,0000,0000,,са малим r изнад да означим чињеницу\Nда је к променљива са насумичном вредношћу Dialogue: 0,0:10:15.39,0:10:20.49,Default,,0000,0000,0000,,која је равномерно узоркована у простору К.\NОво је главни садржај Dialogue: 0,0:10:20.49,0:10:25.89,Default,,0000,0000,0000,,Шенонове дефиниције. Хајде да размислимо мало\Nо томе шта се овом дефиницијом каже. Dialogue: 0,0:10:25.89,0:10:30.96,Default,,0000,0000,0000,,Дакле шта значи да су ове\Nдве вероватноће једнаке? Dialogue: 0,0:10:30.96,0:10:36.30,Default,,0000,0000,0000,,То значи да ако сам ја нападач\Nи пресретнем одређени шифрат с, Dialogue: 0,0:10:36.30,0:10:41.58,Default,,0000,0000,0000,,тада је у ствари, вероватноћа да је\Nовај шифрат шифра за m0, иста Dialogue: 0,0:10:41.58,0:10:46.80,Default,,0000,0000,0000,,као и вероватноћа да је он шифра за m1. Dialogue: 0,0:10:46.80,0:10:52.22,Default,,0000,0000,0000,,Зато што су ове две вероватноће једнаке.\NДакле ако је све што имам шифрат с, Dialogue: 0,0:10:52.22,0:10:57.64,Default,,0000,0000,0000,,тада ја никако не могу да знам да ли је\Nшифрат потекао од m0 или од m1, Dialogue: 0,0:10:57.64,0:11:03.20,Default,,0000,0000,0000,,јер је, понављам, вероватноћа да се добије с Dialogue: 0,0:11:03.20,0:11:08.65,Default,,0000,0000,0000,,иста за обе ове поруке. Dialogue: 0,0:11:08.65,0:11:13.29,Default,,0000,0000,0000,,Овде поново имамо дефиницију.\NИ сада само желим да ово поново Dialogue: 0,0:11:13.29,0:11:17.75,Default,,0000,0000,0000,,запишем мало прецизније. Dialogue: 0,0:11:17.75,0:11:22.33,Default,,0000,0000,0000,,Дакле ако имам на располагању неки шифрат, Dialogue: 0,0:11:22.33,0:11:27.12,Default,,0000,0000,0000,,не могу на основу тога да тврдим\Nод које поруке потиче m0 или m1. Dialogue: 0,0:11:27.12,0:11:32.09,Default,,0000,0000,0000,,Штавише, ово важи за све поруке, \Nза сваки пар порука. Dialogue: 0,0:11:32.09,0:11:37.12,Default,,0000,0000,0000,,И не само да не могу да разликујем да ли је шифрат добијен од m0 или m1, Dialogue: 0,0:11:37.12,0:11:42.14,Default,,0000,0000,0000,,не знам ни да ли потиче од m2, m3, m4, m5, Dialogue: 0,0:11:42.14,0:11:47.11,Default,,0000,0000,0000,,зато што све оне имају исту вероватноћу\Nда се од њих добије с. Dialogue: 0,0:11:47.11,0:11:52.07,Default,,0000,0000,0000,,То значи, да приликом шифровања порука једнократном бележницом, Dialogue: 0,0:11:52.07,0:11:56.73,Default,,0000,0000,0000,,чак и најмоћнији декриптор,\Nколико год паметан био, Dialogue: 0,0:11:56.73,0:12:02.53,Default,,0000,0000,0000,,не може да сазна ништа о отвореном тексту Dialogue: 0,0:12:02.53,0:12:09.62,Default,,0000,0000,0000,,на основу шифрата.\NДа кажемо ово на још један начин, Dialogue: 0,0:12:09.62,0:12:16.32,Default,,0000,0000,0000,,не постоји напад који је усмерен само на шифрат Dialogue: 0,0:12:16.32,0:12:23.26,Default,,0000,0000,0000,,на шифру са савршеном тајношћу.\NНапади који су усмерени само на шифрат Dialogue: 0,0:12:23.26,0:12:29.44,Default,,0000,0000,0000,,нису једини постојећи напади - постоје друге врсте напада, којима је подложна оваква шифра. Dialogue: 0,0:12:32.16,0:12:36.77,Default,,0000,0000,0000,,Сада када смо разумели појам савршене тајности, Dialogue: 0,0:12:36.77,0:12:41.33,Default,,0000,0000,0000,,поставља се питање, да ли је могуће направити шифру са овом особином? Dialogue: 0,0:12:41.33,0:12:45.52,Default,,0000,0000,0000,,Испоставља се да једнократна књижница\Nима савршену тајност. Dialogue: 0,0:12:45.52,0:12:50.72,Default,,0000,0000,0000,,Желим и да вам изведем доказ за ово,\Nто је уједно и Шенонов први резултат, Dialogue: 0,0:12:50.72,0:12:55.86,Default,,0000,0000,0000,,доказ је једноставан, тако да\Nхајде да га одмах изведемо. Dialogue: 0,0:12:55.86,0:13:01.06,Default,,0000,0000,0000,,Потребно је да протумачимо шта то значи,\Nта вероватноћа Pr (Е(k, m0) = с). Dialogue: 0,0:13:01.06,0:13:06.20,Default,,0000,0000,0000,,Није тешко да се види да за сваку поруку Dialogue: 0,0:13:06.20,0:13:11.02,Default,,0000,0000,0000,,и за сваки шифрат, вероватноћа да се шифровањем m кључем k Dialogue: 0,0:13:11.02,0:13:16.16,Default,,0000,0000,0000,,добија с, при чему се, по дефиницији,\Nкључ бира насумице, Dialogue: 0,0:13:16.16,0:13:23.72,Default,,0000,0000,0000,,представља количник броја кључева из скупа К, Dialogue: 0,0:13:24.76,0:13:31.53,Default,,0000,0000,0000,,таквих да ако шифрујем m са k добијам с, Dialogue: 0,0:13:31.53,0:13:37.21,Default,,0000,0000,0000,,подељених са укупним бројем могућих кључева. Dialogue: 0,0:13:37.21,0:13:42.83,Default,,0000,0000,0000,,То је вероватноћа да ако одаберем насумице неки кључ, он ће да преслика m у с. Dialogue: 0,0:13:42.83,0:13:47.71,Default,,0000,0000,0000,,To je практично број кључева који пресликавају m у с,\Nкроз укупни број кључева. Dialogue: 0,0:13:47.71,0:13:53.41,Default,,0000,0000,0000,,Претпоставимо сада да имамо шифру\Nтакву да за све поруке и све шифрате, Dialogue: 0,0:13:53.41,0:13:58.97,Default,,0000,0000,0000,,важи да ако погледам овај број, број k из скупа К, таквих да је Е(k, m) = с Dialogue: 0,0:13:58.97,0:14:04.39,Default,,0000,0000,0000,,другим речима, посматрам број кључева Dialogue: 0,0:14:04.39,0:14:09.26,Default,,0000,0000,0000,,који пресликавају m у с; претпоставимо да је\Nовај број нека константа. Dialogue: 0,0:14:09.26,0:14:14.08,Default,,0000,0000,0000,,Рецимо да је то 2, 3, 10 или 15. Dialogue: 0,0:14:14.08,0:14:19.33,Default,,0000,0000,0000,,Рецимо да је то константна вредност. У том случају, према дефиницији, за свако m0 и m1 Dialogue: 0,0:14:19.33,0:14:24.75,Default,,0000,0000,0000,,и за свако с, ова вероватноћа мора да буде иста,\Nзато што је именилац исти, Dialogue: 0,0:14:24.75,0:14:30.10,Default,,0000,0000,0000,,бројилац исти, нека константа,\Nи из тога следи да је и вероватноћа Dialogue: 0,0:14:30.10,0:14:35.64,Default,,0000,0000,0000,,увек иста за свако m и с. Дакле ако је ово тачно, шифра мора да има Dialogue: 0,0:14:35.64,0:14:43.62,Default,,0000,0000,0000,,савршену тајност. Да видимо сада\Nшта можемо да кажемо Dialogue: 0,0:14:43.62,0:14:48.80,Default,,0000,0000,0000,,о овој величини за једнократну бележницу.\NПитање за вас је, ако имате Dialogue: 0,0:14:48.80,0:14:54.77,Default,,0000,0000,0000,,на располагању шифрат и поруку,\Nколико једнократних кључева постоји, Dialogue: 0,0:14:54.77,0:15:00.38,Default,,0000,0000,0000,,који пресликавају поруку m у с?\NДругим речима, колико кључева Dialogue: 0,0:15:00.38,0:15:06.10,Default,,0000,0000,0000,,постоји, таквих да је m XOR k = c? Dialogue: 0,0:15:06.10,0:15:12.68,Default,,0000,0000,0000,,Надам се да сте одговорили да је један.\NДа видимо и зашто: Dialogue: 0,0:15:12.68,0:15:18.30,Default,,0000,0000,0000,,За једнократну бележницу, израз Е(k, m) = c, \Nпо дефиницији значи Dialogue: 0,0:15:18.30,0:15:24.88,Default,,0000,0000,0000,,да је k XOR m = c.\NАли то такође значи да мора да је Dialogue: 0,0:15:24.88,0:15:31.77,Default,,0000,0000,0000,,m XOR с = k. Ово смо добили тако што смо извршили XOR обе стране са m. Dialogue: 0,0:15:31.77,0:15:37.56,Default,,0000,0000,0000,,Из овога произилази,\Nда је за једнократну бележницу, Dialogue: 0,0:15:37.56,0:15:43.71,Default,,0000,0000,0000,,број кључева у К, таквих да је E(k, m) = c, једноставно 1, Dialogue: 0,0:15:43.71,0:15:49.85,Default,,0000,0000,0000,,и то важи за све поруке и шифрате. Тако да, на основу претходно реченог, Dialogue: 0,0:15:49.85,0:15:54.99,Default,,0000,0000,0000,,произилази да једнократна бележница има савршену тајност. Dialogue: 0,0:15:54.99,0:15:59.09,Default,,0000,0000,0000,,Овим је доказ завршен.\NОво је врло једноставна лема. Dialogue: 0,0:15:59.09,0:16:03.64,Default,,0000,0000,0000,,Међутим, иако је толико једноставно\Nда се она докаже, Dialogue: 0,0:16:03.64,0:16:08.19,Default,,0000,0000,0000,,из овог доказа произилази јако моћан закључак. Dialogue: 0,0:16:08.19,0:16:12.33,Default,,0000,0000,0000,,Ово у ствари значи да за једнократну бележницу не постоји напад који се ослања само на шифрат. Dialogue: 0,0:16:12.33,0:16:16.39,Default,,0000,0000,0000,,Дакле за разлику од шифре замене, или Вижнерове шифре, или шифарског диска, Dialogue: 0,0:16:16.39,0:16:20.78,Default,,0000,0000,0000,,које су све могле да буду разбијене нападом који се ослања само на шифрат, Dialogue: 0,0:16:20.78,0:16:25.11,Default,,0000,0000,0000,,код једнократне бележнице, како смо доказали, ово једноставно није могуће. Dialogue: 0,0:16:25.11,0:16:29.28,Default,,0000,0000,0000,,На основу шифрата, ништа се не сазнаје о отвореном тексту. Али, као што видимо, Dialogue: 0,0:16:29.28,0:16:33.13,Default,,0000,0000,0000,,ово није крај приче. То јест, јесмо ли завршили? Будући да смо открили начин Dialogue: 0,0:16:33.13,0:16:37.36,Default,,0000,0000,0000,,да шифрирамо тако да декриптор не може да открије ништа Dialogue: 0,0:16:37.36,0:16:41.21,Default,,0000,0000,0000,,о нашој поруци, можда смо дакле завршили са течајем? Али заправо, као што ћемо да видимо, Dialogue: 0,0:16:41.21,0:16:45.26,Default,,0000,0000,0000,,постоје и други напади. У ствари, једнократна бележница и није тако безбедна шифра. Dialogue: 0,0:16:45.26,0:16:49.32,Default,,0000,0000,0000,,Постоје други могући напади, Dialogue: 0,0:16:49.32,0:16:54.08,Default,,0000,0000,0000,,које ћемо ускоро да видимо. Наглашавам поново ову чињеницу, да и поред савршене тајности, Dialogue: 0,0:16:54.08,0:16:58.78,Default,,0000,0000,0000,,не произилази да је једнократна бележница безбедна шифра. Али, као што смо рекли, Dialogue: 0,0:16:58.78,0:17:03.73,Default,,0000,0000,0000,,код једнократне бележнице незгодно је то\Nшто је тајни кључ јако дугачак. Dialogue: 0,0:17:03.73,0:17:08.07,Default,,0000,0000,0000,,Ако постоји начин да се тајни кључ безбедно пренесе другој страни, онда може Dialogue: 0,0:17:08.07,0:17:12.25,Default,,0000,0000,0000,,тим истим начином да се саопшти\Nи сама порука другој страни, Dialogue: 0,0:17:12.25,0:17:16.65,Default,,0000,0000,0000,,а у том случају уопште нам и не треба шифра.\NДакле, још једном, проблем је то Dialogue: 0,0:17:16.65,0:17:21.10,Default,,0000,0000,0000,,што једнократна бележница има јако дуги кључ,\Nи намеће се питање да ли постоје Dialogue: 0,0:17:21.10,0:17:25.45,Default,,0000,0000,0000,,друге шифре које имају савршену тајност,\Nали много, много краће кључеве? Dialogue: 0,0:17:25.45,0:17:30.14,Default,,0000,0000,0000,,Лоша вест је то што је Шенон, након што је доказао да једнократна бележница има Dialogue: 0,0:17:30.14,0:17:34.94,Default,,0000,0000,0000,,савршену тајност, доказао и теорему\Nда свака шифра која има Dialogue: 0,0:17:34.94,0:17:39.88,Default,,0000,0000,0000,,савршену тајност, мора да има на располагању најмање исти број кључева Dialogue: 0,0:17:39.88,0:17:44.94,Default,,0000,0000,0000,,као и број порука које се обрађују шифром. То значи, да ако шифра има савршену тајност, Dialogue: 0,0:17:44.94,0:17:51.04,Default,,0000,0000,0000,,тада број кључева, то јест дужина кључа Dialogue: 0,0:17:51.04,0:17:56.31,Default,,0000,0000,0000,,мора да буде већа или једнака дужини поруке. Dialogue: 0,0:17:56.31,0:18:00.83,Default,,0000,0000,0000,,Заправо, пошто једнократна бележница задовољава овај услов код једнакости, Dialogue: 0,0:18:00.83,0:18:04.86,Default,,0000,0000,0000,,она је у ствари оптимална шифра која има савршену тајност. Dialogue: 0,0:18:04.86,0:18:09.06,Default,,0000,0000,0000,,Дакле једнократна бележница је занимљива шифра, Dialogue: 0,0:18:09.06,0:18:13.36,Default,,0000,0000,0000,,али јако тешка за примену, Dialogue: 0,0:18:13.36,0:18:17.79,Default,,0000,0000,0000,,због дугачних кључева. Сам појам савршене тајности, Dialogue: 0,0:18:17.79,0:18:21.84,Default,,0000,0000,0000,,иако врло занимљив, говори нам у суштини да шифре које су згодне за примену Dialogue: 0,0:18:21.84,0:18:26.28,Default,,0000,0000,0000,,не могу да буду безбедне. Али, као што смо напоменули, сама замисао која је Dialogue: 0,0:18:26.28,0:18:30.99,Default,,0000,0000,0000,,у основи једнократне бележнице је јако добра.\NА у следећој лекцији ћемо да видимо, Dialogue: 0,0:18:30.99,0:18:33.55,Default,,0000,0000,0000,,како да на основу ње направимо применљив систем.