Information theoretic security and the one time pad (19 min)

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

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

шифрама. Али пре тога, желим да
прецизније одредим појам шифре.

Пре свега, шифра се у ствари
састоји од два алгоритма.

Постоје алгоритам за шифровање
и за дешифровање. Међутим,

шифра се дефинише са три елемента.
Ту је скуп свих могућих кључева,

који ћу да означим словом К, и понекад
ћу да га називам простором кључева -

скуп свих могућих кључева.
Затим ту је скуп свих могућих порука,

и скуп свих могућих шифрованих текстова.
Значи ова тројка на неки начин одређује

околину над којом се дефинише шифра.
Сама шифра је пар ефикасних

алгоритама Е и D. Е је алгоритам за шифровање;
D је алгоритам за дешифровање.

Наравно, Е узима кључеве и поруке,
и враћа шифроване текстове - шифрате.

Алгоритам за дешифровање узима
кључеве и шифрате, а враћа поруке.

Једини захтев је да ови алгоритми буду доследни.

Ово својство се назива "исправност".
Значи за сваку поруку из простора порука,

и за сваки кључ у простору кључева,
мора да важи, да ако шифрујем

поруку кључем k и дешифрујем
користећи овај исти кључ,

треба да добијем првобитну поруку.
Дакле ова једначина назива се

једначином доследности, и она мора
да важи за сваку шифру,

иначе не би било могуће дешифровање.

Желим да нагласим да је реч "ефикасан"
под наводницима, зато што она

може да има различито значење.
За оне више окренуте ка теорији,

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

извршиви су у полиномној временској
зависности од величине улаза.

За оне окренуте ка пракси, "ефикасан"
значи извршив у оквиру задатог времена.

На пример, алгоритам Е треба да обради
гигабајт података за мање од једног минута.

У сваком случају, реч "ефикасан"
обухвата оба ова виђења,

и можете да је тумачите како вам више одговара.
Ја ћу и у наставку да је користим

под наводницима; као што сам рекао,
ако више нагињете ка теорији

сматрајте да се односи на полиномно време,
иначе, на задато временско ограничење.

Следеће што желим да напоменем,
тиче се алгоритма Е.

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

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

и користи ове битове да шифрује
поруке које му се прослеђују.

Са друге стране, алгоритам за дешифровање
увек је алгоритам са утврђеним излазима.

То значи да за исте вредности кључа и шифрата
увек даје исти излаз, независно

од било какве насумичности
која постоји у алгоритму.

Сада када мало боље схватамо појам шифре,
желим да вам дам први пример безбедне шифре.

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

Пре него што објасним начин рада ове шифре,

хајде да користећи праву терминологију
кажемо шта овде видимо.

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

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

свих низова битова знакова 0 и 1.
Простор кључева је исти као простор порука,

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

јесте насумично изабран низ битова,

дужине која је иста као дужина поруке
која треба да се шифрује.

Сада када смо видели чиме је дефинисана шифра,

можемо да видимо како ради,
што је у ствари врло једноставно.

Шифрати, који су производ шифровања
поруке одређеним кључем,

добијају се операцијом XOR над
овим двема вредностима: К XOR М.

Подсетимо се ознаке за операцију XOR.
XOR значи збир по модулу 2.

Ако узмем рецимо поруку 0110111,

и неки кључ, нпр. 1011001,
када шифрујем поруку на овај начин,

све што треба је да израчунам XOR
ове две вредности.

Другим речима, одрадим збир по модулу 2,
бит по бит; и добијем: 1101110.

Ово је шифрат.
Како ћу да дешифрујем?

У ствари, поновим исту операцију.
Шифрат се дешифрује овим истим кључем.

Извршим операцију XOR над кључем и шифратом.

Све што остаје је да потврдимо
да је задовољен захтев за доследношћу.

Сада ћу да урадим ово поступно, а у будуће
ћу да претпоставим да вам је познато.

Дакле желимо да се уверимо
да дешифровањем шифрата,

шифрованог одређеним кључем,
обавезно добијам поруку m.

Да видимо...
Посматрам шифрат над k и m.

По дефиницији ово је k XOR m.
А шта представља дешифровање

вредности k XOR m? То је k XOR (k XOR m).
А будући да је XOR збир по модулу 2,

сабирање је асоцијативно,
дакле ово је исто што и (k XOR k) XOR m,

а као што знате (k XOR k) је нула,
а нула XOR било која вредност

је само m. Овим смо показали да је
једнократна бележница шифра,

али ово нам ништа не говори о безбедности шифре.

Прећи ћемо на безбедност за који час,
али пре тога, само једно питање,

да будемо сигурни да се разумемо.
Рецимо да вам је дата

порука m, и шифрат те поруке,
коришћењем једнократне бележнице.

Све што знате је порука и шифрат.
Моје питање за вас је,

знајући пар m и с, да ли можете да
откријете кључ који је коришћен

приликом добијања с на основу m?

Надам се да сви уочавате да је, у ствари,
знајући поруку и шифрат,

врло лако добити вредност кључа.
Конкретно, кључ је једноставно

m XOR с. Ако вам није очигледно,

видећемо зашто је то тако, мало касније.

Једнократна бележница је одлична
што се тиче перформанси,

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

шифра за рад са врло великим порукама.

Нажалост, у пракси је тешко примењива.
Разлог за то је што су кључеви

исте дужине као и порука.
Значи ако Алиса и Боб желе

безбедну комуникацију, тј. Алиса жели
да пошаље поруку Бобу, пре него

што почне са слањем поруке,
она мора да пошаље Бобу кључ,

који је исте дужине као и порука.
Али, ако постоји начин да пошаље

Бобу тајни кључ исте дужине као и порука,
може лепо да тим начином пошаље

и саму поруку. Дакле чињеница да је кључ
исте дужине као и порука,

је прилично незгодна, и чини овај начин
шифрирања јако тешким за примену.

Мада ћемо да видимо да је замисао иза
једнократне бележнице врло корисна,

а ово ћемо да покажемо мало касније.
А сада да се задржимо мало на безбедности.

Поставља се очигледно питање:
зашто је једнократна бележница безбедна?

Зашто је ово добра шифра?
Да бисмо одговорили на ово питање,

најпре морамо да видимо шта је то уопште
безбедна шифра, шта чини шифру

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

теоријом информације. Заправо, прва особа
која се озбиљно бавила питањем

безбедности шифара, јесте чувени отац теорије информације, Клод Шенон,

који је још 1949. објавио познати рад,
у којем је проучавао

безбедност једнократне бележнице.
Замисао иза Шенонове дефиниције безбедности

је следећа: у основи, ако је све
што стоји на располагању сам шифрат,

на основу њега не сме ништа да се сазна о отвореном тексту.

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

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

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

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

најпре ћу да је испишем полако.

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

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

Шифра има савршену тајност

ако важи следеће: за сваке две поруке m0 и m1,

у простору порука, при чему је једини захтев
за ове две поруке

да буду исте дужине (видећемо зашто

је потребан овај услов за који час)
и за сваки шифрат,

у простору шифрата, дакле за сваки пар порука
и за сваки шифрат,

мора да важи, да је вероватноћа да се

шифровањем m0 са k добија c,

иста као и вероватноћа да се

шифровањем m1 са k добија c.

Дакле вероватноћа да шифровањем m1 добијемо с
је потпуно иста као и вероватноћа

да шифровањем m0 добијемо с.

Дакле да ово важи за кључеве чија је расподела

равномерна у простору кључева.
Користићу ознаку к са стрелицом

са малим r изнад да означим чињеницу
да је к променљива са насумичном вредношћу

која је равномерно узоркована у простору К.
Ово је главни садржај

Шенонове дефиниције. Хајде да размислимо мало
о томе шта се овом дефиницијом каже.

Дакле шта значи да су ове
две вероватноће једнаке?

То значи да ако сам ја нападач
и пресретнем одређени шифрат с,

тада је у ствари, вероватноћа да је
овај шифрат шифра за m0, иста

као и вероватноћа да је он шифра за m1.

Зато што су ове две вероватноће једнаке.
Дакле ако је све што имам шифрат с,

тада ја никако не могу да знам да ли је
шифрат потекао од m0 или од m1,

јер је, понављам, вероватноћа да се добије с

иста за обе ове поруке.

Овде поново имамо дефиницију.
И сада само желим да ово поново

запишем мало прецизније.

Дакле ако имам на располагању неки шифрат,

не могу на основу тога да тврдим
од које поруке потиче m0 или m1.

Штавише, ово важи за све поруке,
за сваки пар порука.

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

не знам ни да ли потиче од m2, m3, m4, m5,

зато што све оне имају исту вероватноћу
да се од њих добије с.

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

чак и најмоћнији декриптор,
колико год паметан био,

не може да сазна ништа о отвореном тексту

на основу шифрата.
Да кажемо ово на још један начин,

не постоји напад који је усмерен само на шифрат

на шифру са савршеном тајношћу.
Напади који су усмерени само на шифрат

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

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

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

Испоставља се да једнократна књижница
има савршену тајност.

Желим и да вам изведем доказ за ово,
то је уједно и Шенонов први резултат,

доказ је једноставан, тако да
хајде да га одмах изведемо.

Потребно је да протумачимо шта то значи,
та вероватноћа Pr (Е(k, m0) = с).

Није тешко да се види да за сваку поруку

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

добија с, при чему се, по дефиницији,
кључ бира насумице,

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

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

подељених са укупним бројем могућих кључева.

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

To je практично број кључева који пресликавају m у с,
кроз укупни број кључева.

Претпоставимо сада да имамо шифру
такву да за све поруке и све шифрате,

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

другим речима, посматрам број кључева

који пресликавају m у с; претпоставимо да је
овај број нека константа.

Рецимо да је то 2, 3, 10 или 15.

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

и за свако с, ова вероватноћа мора да буде иста,
зато што је именилац исти,

бројилац исти, нека константа,
и из тога следи да је и вероватноћа

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

савршену тајност. Да видимо сада
шта можемо да кажемо

о овој величини за једнократну бележницу.
Питање за вас је, ако имате

на располагању шифрат и поруку,
колико једнократних кључева постоји,

који пресликавају поруку m у с?
Другим речима, колико кључева

постоји, таквих да је m XOR k = c?

Надам се да сте одговорили да је један.
Да видимо и зашто:

За једнократну бележницу, израз Е(k, m) = c,
по дефиницији значи

да је k XOR m = c.
Али то такође значи да мора да је

m XOR с = k. Ово смо добили тако што смо извршили XOR обе стране са m.

Из овога произилази,
да је за једнократну бележницу,

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

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

произилази да једнократна бележница има савршену тајност.

Овим је доказ завршен.
Ово је врло једноставна лема.

Међутим, иако је толико једноставно
да се она докаже,

из овог доказа произилази јако моћан закључак.

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

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

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

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

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

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

да шифрирамо тако да декриптор не може да открије ништа

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

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

Постоје други могући напади,

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

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

код једнократне бележнице незгодно је то
што је тајни кључ јако дугачак.

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

тим истим начином да се саопшти
и сама порука другој страни,

а у том случају уопште нам и не треба шифра.
Дакле, још једном, проблем је то

што једнократна бележница има јако дуги кључ,
и намеће се питање да ли постоје

друге шифре које имају савршену тајност,
али много, много краће кључеве?

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

савршену тајност, доказао и теорему
да свака шифра која има

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

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

тада број кључева, то јест дужина кључа

мора да буде већа или једнака дужини поруке.

Заправо, пошто једнократна бележница задовољава овај услов код једнакости,

она је у ствари оптимална шифра која има савршену тајност.

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

али јако тешка за примену,

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

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

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

у основи једнократне бележнице је јако добра.
А у следећој лекцији ћемо да видимо,

како да на основу ње направимо применљив систем.