Вижнерова шифра

Вижнерова шифра је метод шифровања азбучног текста коришћењем серије Цезарових шифара, заснованих на словима кључа. Ово је прости облик шифре полиалфабетске замене.

Вижнерова шифра је добила име по Блезу де Вижнеру.

Вижнерова шифра је откривана више пута. Метод је први описао Ђован Батиста Белазо (итал. ); међутим, касније, у 19. веку је та шема погрешно приписана Блезу де Вижнеру (фр. ), тако да је сад позната као „Вижнерова шифра“.

Шифра је добро позната зато што, иако је лака за разумевање и примену, почетницима изгледа као непробојна; тако је и добила епитет фр. . Стога су многи покушавали да примене шеме шифровања, које су у основи Вижнерова шифра^[1].

Историја

Прва полиалфабетска шифра, коју је направио Леон Батиста Алберти (итал. ) око 1467, је користила металну шифарску плочу за замену шифарских алфабета. Албертијев систем је мењао алфабете после неколико речи, а замена је означавана словом одговарајућег алфабета у шифрату. Касније, Јохан Тритемијус ( ) у свом делу из 1508. је изумео квадратну таблицу (лат. ), кључну компоненту Вижнерове шифре. Међутим, он је дао само растући, крут и предвидљив систем замене шифарских алфабета.

Оно што је сада познато под именом Вижнерове шифре је првобитно описао Белазо 1553. у својој књизи итал. . Направио је према Тритемијусовој таблици, али је додао понављајући кључ за промену шифарског алфабета за свако слово.

Блез де Вижнер је 1586. објавио свој опис сличне, али јаче шифре са „аутокључем“ пред двором Анрија III (краљ Француске и Пољске). Касније, у 19. веку, проналазак Белазоове шифре је погрешно приписан Вижнеру. Дејвид Кан, у својој књизи енгл. , каже да је историја „игнорисала овај важан допринос и назвала регресивну и основну шифру по њему [Вижнеру], иако он ништа нема са тим“.^[2]

Репродукција шифарског диска Конфедерације. Познато је да постоји само пет оригинала.

Вижнерова шифра је стекла репутацију као изузетно јака. Познати писац и математичар Чарлс Латвиџ Доџсон (познатији као Луис Керол) је Вижнерову шифру назвао непробојном у свом делу из 1868. енгл. у дечјем часопису. Часопис енгл. је 1917. описао Вижнерову шифру као „немогућа за превод“.^[3] Ова репутација је незаслужена, јер је Казиски још у 19. веку потпуно разбио шифру, а познато је да су је неки криптоаналитичари повремено разбијали још у 16. веку.^[2]

Вижнерова шифра је довољно једноставна за пољску употребу ако се користи у спрези са шифарским дисковима.^[4] Конфедеративне Америчке Државе, на пример, су користиле бронзане шифарске дискове за примену Вижнерове шифре за време Америчког грађанског рата. Поруке Конфедерације су биле далеко од тајне и Унија је редовно разбијала њихове поруке. За време рата, вође Конфедерације су се првенствено ослањале на три кључа, енгл. (ова последња при крају рата).^[5]

Гилберт Вернем је покушао да поправи разбијену шифру (креирајући Вернем-Вижнерову шифру 1918), али и без обзира на то, шифра је за криптоаналитичаре и даље била рањива. Међутим, Вернамов рад је довео до "једнократне бележнице" (енгл. ), проверено непробојне шифре.

Опис

Вижнерова таблица, такође позната и као , може да се користи за шифровање и дешифровање.

Код Цезарове шифре, свако слово алфабета се помера за неки број места; на пример, са помаком 3, слово постаје , постаје итд. Вижнерова шифра се састоји од низа неколико Цезарових шифара са различитим помацима.

За шифровање може да се користи таблица алфабета, названа , Вижнерова таблица или Вижнеров квадрат. Састоји се од алфабета написаног 26 пута у новом реду, сваки ред ротиран улево у односу на претходни, одговарајући свим могућим комбинацијама (26) Цезарове шифре. У појединој тачки процеса шифровања, шифра користи други алфабет из једног од редова. Који ће се ред користити зависи од понављајућег кључа.

На пример, рецимо да је отворени текст који треба да се шифрује:

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

Прво слово отвореног текста се шифрује користећи алфабет из реда , које је прво слово кључа. То се ради тако што се тражи слово у реду и колони Вижнерове таблице, односно тражено слово је . За следеће слово отвореног текста се користи следеће слово кључа, слово у пресеку реда и колоне је тражено слово . По том систему се наставља до краја отвореног текста: Отворени текст: Кључ: Шифрат:

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

Вижнерова шифра може да се представи и алгебарски. Ако се словима абецеде до доделе вредности 0 до 25 и изврши сабирање по модулу 26, шифровање може да се напише као

${\displaystyle S_{i}\equiv O_{i}+K_{i}{\pmod {26}}}$

а дешифровање као

${\displaystyle O_{i}\equiv S_{i}-K_{i}{\pmod {26}}}$

( - отворени текст, - шифрат, - кључ)

Криптоанализа

Вижнерова шифра је ефикасна јер маскира карактерситичну фреквенцију слова отвореног текста, али одређени узорак ипак остаје.

Снага Вижнерове шифре, као и свих полиалфабетских шифара, је њена способност отежавања фреквентне анализе. Фреквентна анализа је вештина декриптовања поруке бројањем фреквенције слова шифрата и упоређивање са фреквенцијом слова нормалног текста. На пример, ако се слово јавља највећи број пута у шифрату чији је отворени текст на српском, може се претпоставити да одговара слову , јер је слово најчешће у српском језику. Коришћењем Вижнерове шифре, слово ће се замењивати различитим словима алфабета на различитим местима у поруци и тако онемогућити просту фреквентну анализу.

Основна слабост Вижнерове шифре је њен реклативно кратак и понављајући кључ. Ако криптоаналитичар открије дужину кључа, онда шифрат може да се посматра као серија Цезарових шифара, које се затим појединачно једноставно разбијају. Тестови Казиског и Фридмена помажу у одређивању дужине кључа.

Казискијев тест

Фридрих Казиски је 1863. први објавио успешан напад на Вижнерову шифру, али Чарлс Бебиџ је још 1854. развио исти тест. За разбијање Вижнерове шифре Бебиџ је био подстакнут кад је Џон Хол Брок Твејтс објавио „нову“ шифру у часопису : Кад је Бебиџ објавио да је то само још једна варијанта Вижнерове шифре, Твејтс се разљутио и изазвао Бебиџа да разбије шифру. Бебиџ је успео да декриптује узорак, за који се испоставило да је песма „Визија греха“ Алфреда Тенисона, а коришћен је кључ "", име Тенисонове жене.^[6].

Тест Казиског користи чињеницу да ће поједине честе речи вероватно бити шифроване истим словима кључа, па ће се у шифрату појавити поновљене групе слова. На пример, порука шифрована кључем неће шифровати исто сваки пут кад се појави у отвореном тексту:

Кључ: Отворено: Шифрат:

Шифрат у овом примеру нема поновљене низове слова који одговарају поновљеним низовима отвореног текста. Међутим, ако је дужина кључа различита, као у овом примеру:

Кључ: Отворено: Шифрат:

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

Шифрат: Растојање између поновљеног је 18. Стога, претпостављајући да поновљени сегменти представљају поновљене сегменте отвореног текста, наговештава да кључ има дужину од 18, 9, 6, 3 или 2 знака. Размак између је 20 знакова. То значи да би дужина кључа могла да буде 20, 10, 5, 4 или 2 знака (сви делиоци растојања су могуће дужине кључа - кључ дужине 1 је обична шифра померања, где је криптоанализа много једноставнија). Коришћењем пресека ова два скупа, може да се закључи да је дужина кључа (готово сигурно) 2. Наравно, у пракси се никад неће користити кључ дужине 1 или 2, овде је наведен само ради илустрације.

Фридменов тест

Овај тест (познат и као „Капа тест") је 1920. открио Виљем Фридмен. Фридмен је за разбијање шифре употребио "индекс подударности" (енгл. ), који мери неравномерност фреквенције слова шифре. Ако знамо вероватноћу ${\displaystyle \kappa _{p}}$ да у два насумично изабрана текста слова буду иста (за енглески око 0,067) и вероватноћу подударања насумичне селекције алфабета ${\displaystyle \kappa _{r}}$ (1/26 = 0.0385), дужина кључа може да се одреди као

${\displaystyle {\kappa _{p}-\kappa _{r}} \over {\kappa _{o}-\kappa _{r}}}$

из уочене мере подударности

${\displaystyle \kappa _{o}={\frac {\sum _{i=1}^{c}n_{i}(n_{i}-1)}{N(N-1)}}}$

где је ${\displaystyle c}$ величина алфабета (26), ${\displaystyle N}$ је дужина текста, а ${\displaystyle n_{1}}$ до ${\displaystyle n_{c}}$ су фреквенције слова шифрата.

Ово је само апроксимација чија тачност се повећава са дужином текста. У пракси ће се пробати различите дужине кључева блиских процењеној.^[7] Бољи приступ за шифре са поновљеним кључем је да се шифрат копира у табелу која има онолико колона колика је претпостављена дужина кључа, а затим да се за сваку колону посебно израчуна индекс подударности; кад се то уради за сваку могућу дужину кључа, највећи просечни ће одговарати вероватној дужини кључа.^[8] Такав тест се може допунити подацима из Казискијевог теста.

Фреквентна анализа

Кад се одреди дужина кључа, шифрат се дели у секције тако да свака секција одговара кључу за једно слово. Сваки део је еквивалентан шифрату једне Цезарове шифре. Помаци су одређени словима кључа. Даље се користи метод којим се разбија Цезарова шифра.

Варијанта Казискијевог теста је Керкхофсов метод, одређивање кључа дедукцијом на основу фреквенције речи у упоредним шифратима.^[9]

Варијанте

Варијанта Вижнерове шифре узастопни кључ (енгл. ) је такође некад сматрана као непробојна. Ова верзија као кључ користи блок текста дужине отвореног текста. Пошто је кључ дугачак као и порука, тестови Казиског и Фридмена више не вреде - кључ се не понавља. Фридмен је 1920. први открио слабост ове варијанте. Проблем код Вижнерове шифре са узастопним кључем је што криптоаналитичар има статистичке информације о кључу (под претпоставком да је блок текста из познатог језика) и та особина ће се одразити у шифрату.

Ако се користи кључ који је потпуно случајан, ако је дугачак као порука и користи се само једном, Вижнерова шифра је теоретски непробојна. У том случају кључ, а не шифра, обезбеђује криптографску отпорност, и ти системи се заједнички зову "једнократна бележница" (енгл. ), невезано за за то која шифра је примењена.

Вижнер је у ствари открио јачу шифру, шифру са аутокључем, иако је његово име везано за једноставнију полиалфабетску шифру. У ствари, те две шифре се често мешају, а обе су некад имале епитет фр. . Бебиџ је у ствари разбио јачу шифру са аутокључем, док се Казиском начелно даје заслуга за прво објављено решење полиалфабетске шифре са фиксним кључем.

Отворено: Кључ: Аутокључ: Шифрат:

Простија варијанта је да се шифровање изводи по методу декрипције Вижнерове шифре, а декриптовање коришћењем шифровања, метод који је познат као „Бофорова варијанта“ (Сер Франсис Бофорт, енгл. ): , а дешифровање као , уз коришћење тзв. Сестријеве (итал. ) таблице:

.

Упркос очигледној јачини, Вижнерова шифра у Европи није била у широкој употреби. Гронсфелдова шифра је варијанта која је идентична Вижнеровој шифри, осим што користи 10 шифарских алфабета (који одговарају цифрама 0 до 9). Шифра је појачана јер кључ није реч, али је ослабљена јер користи само 10 шифарских алфабета. Упркос тој слабости, Гронсфелдова шифра је била у широкој употреби у Немачкој и у Европи.

Види још

• Глосар криптологије