PROFILPELAJAR.COM

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

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

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

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

Историја

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

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

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

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

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

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

Опис

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

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

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

ATTACKATDAWN

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

LEMONLEMONLE

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

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

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

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

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

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

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

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

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

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

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

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

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

Кључ: ABCDEF AB CDEFA BCD EFABCDEFABCD Отворено: CRYPTO IS SHORT FOR CRYPTOGRAPHY Шифрат: CSASXT IT UKSWT GQU GWYQVRKWAQJB

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

Кључ: ABCDAB CD ABCDA BCD ABCDABCDABCD Отворено: CRYPTO IS SHORT FOR CRYPTOGRAPHY Шифрат: CSASTP KV SIQUT GQU CSASTPIUAQJB

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

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

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

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

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

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

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

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

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

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

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

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

Варијанте

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

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

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

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

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

   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Z  Z Y X W V U T S R Q P O N M L K J I H G F E D C B A
Y  Y X W V U T S R Q P O N M L K J I H G F E D C B A Z

. . . . . . . . . . . . . . . . . . . . . . . . . . .

A  A Z Y X W V U T S R Q P O N M L K J I H G F E D C B

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

Види још

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

Референце

^ Smith, Laurence D. (1943). „Substitution Ciphers”. Cryptography the Science of Secret Writing: The Science of Secret Writing. Dover Publications. стр. 81. ISBN 978-0-486-20247-1.
^ ^а ^б David, Kahn (1999). „On the Origin of a Species”. The Codebreakers: The Story of Secret Writing. Simon & Schuster. ISBN 978-0-684-83130-5.
^ Knudsen, Lars R. (1998). „Block Ciphers— a survey”. Ур.: Bart Preneel and Vincent Rijmen. State of the Art in Applied Cryptography: Course on Computer Security and Industrial Cryptograph Leuven Belgium, June 1997 Revised Lectures. стр. 29. ISBN 978-3-540-65474-2.
^ Codes, Ciphers, & Codebreaking (The Rise Of Field Ciphers)
^ David, Kahn (1999). „Crises of the Union”. The Codebreakers: The Story of Secret Writing. Simon & Schuster. стр. 217—221. ISBN 978-0-684-83130-5.
^ Singh, Simon (1999). „Chapter 2: Le Chiffre Indéchiffrable”. The Code Book. Anchor Book, Random House. стр. 63—78. ISBN 978-0-385-49532-5.
^ Henk C.A. van Tilborg, ур. (2005). Encyclopedia of Cryptography and Security (First edition изд.). Springer. стр. 115. ISBN [[Посебно:BookSources/978-0-387-23473-1}-|978-0-387-23473-1}-]] Проверите вредност параметра |isbn=: invalid character (помоћ).
^ Mountjoy, Marjorie (1963). „The Bar Statistics”. NSA Technical Journal. VII (2,4). -{Published in two parts.
^ „Lab exercise: Vigenere, RSA, DES, and Authentication Protocols” (PDF). CS 415: Computer and Network Security. Архивирано из оригинала (PDF) 23. 7. 2011. г. Приступљено 10. 11. 2006.

Литература

Smith, Laurence D. (1943). „Substitution Ciphers”. Cryptography the Science of Secret Writing: The Science of Secret Writing. Dover Publications. стр. 81. ISBN 978-0-486-20247-1.
David, Kahn (1999). „On the Origin of a Species”. The Codebreakers: The Story of Secret Writing. Simon & Schuster. ISBN 978-0-684-83130-5.
Knudsen, Lars R. (1998). „Block Ciphers— a survey”. Ур.: Bart Preneel and Vincent Rijmen. State of the Art in Applied Cryptography: Course on Computer Security and Industrial Cryptograph Leuven Belgium, June 1997 Revised Lectures. стр. 29. ISBN 978-3-540-65474-2.
David, Kahn (1999). „Crises of the Union”. The Codebreakers: The Story of Secret Writing. Simon & Schuster. стр. 217—221. ISBN 978-0-684-83130-5.
Singh, Simon (1999). „Chapter 2: Le Chiffre Indéchiffrable”. The Code Book. Anchor Book, Random House. стр. 63—78. ISBN 978-0-385-49532-5.
Henk C.A. van Tilborg, ур. (2005). Encyclopedia of Cryptography and Security (1. изд.). Springer. стр. 115. ISBN 978-0-387-23473-1.

Спољашње везе

Чланци

Програмирање

Sharky's Online Vigenere Cipher – Encode and decode messages, using a known key, within a Web browser (JavaScript)
PyGenere: an online tool for automatically deciphering Vigenère-encoded texts (6 languages supported)
Tim's Vigenère Cracker^{[мртва веза]} Another tool for automatic decyphering using an entropy-based approach. English only.
Crypt::Vigenere – a CPAN module implementing the Vigenère cipher
Breaking the indecipherable cipher: Perl code to decipher Vigenère text, with the source in the shape of Babbage's head
Vigenère Cipher, an implementation - Sources in Java and C (GNU GPL)
Java Vigenere applet with source code (GNU GPL)

[1] Smith, Laurence D. (1943). „Substitution Ciphers”. Cryptography the Science of Secret Writing: The Science of Secret Writing. Dover Publications. стр. 81. ISBN 978-0-486-20247-1.

[KahnOrigin-2] а ^б David, Kahn (1999). „On the Origin of a Species”. The Codebreakers: The Story of Secret Writing. Simon & Schuster. ISBN 978-0-684-83130-5.

[3] Knudsen, Lars R. (1998). „Block Ciphers— a survey”. Ур.: Bart Preneel and Vincent Rijmen. State of the Art in Applied Cryptography: Course on Computer Security and Industrial Cryptograph Leuven Belgium, June 1997 Revised Lectures. стр. 29. ISBN 978-3-540-65474-2.

[4] Codes, Ciphers, & Codebreaking (The Rise Of Field Ciphers)

[5] David, Kahn (1999). „Crises of the Union”. The Codebreakers: The Story of Secret Writing. Simon & Schuster. стр. 217—221. ISBN 978-0-684-83130-5.

[6] Singh, Simon (1999). „Chapter 2: Le Chiffre Indéchiffrable”. The Code Book. Anchor Book, Random House. стр. 63—78. ISBN 978-0-385-49532-5.

[7] Henk C.A. van Tilborg, ур. (2005). Encyclopedia of Cryptography and Security (First edition изд.). Springer. стр. 115. ISBN [[Посебно:BookSources/978-0-387-23473-1}-|978-0-387-23473-1}-]] Проверите вредност параметра |isbn=: invalid character (помоћ).

[8] Mountjoy, Marjorie (1963). „The Bar Statistics”. NSA Technical Journal. VII (2,4). -{Published in two parts.

[9] „Lab exercise: Vigenere, RSA, DES, and Authentication Protocols” (PDF). CS 415: Computer and Network Security. Архивирано из оригинала (PDF) 23. 7. 2011. г. Приступљено 10. 11. 2006.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]