Цезарова шифра

Из Википедије, слободне енциклопедије
Код Цезарове шифре свако слово се мења одговарајућим словом из азбуке, помереним за одређени број места. У овом примеру је помак 3, тако да слово B постаје E у шифрованом тексту.

У криптографији, Цезарова шифра је један од најпростијих и најраспрострањенијих начина шифровања. То је тип шифре замењивања у коме се свако слово отвореног текста мења одговарајућим словом азбуке, помереним за одређени број места. На пример, са помаком 3, А се замењује словом Г, Б са Д итд. Овај метод је добио име по Јулију Цезару, који га је користио за размену порука са својим генералима.

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

Пример[уреди]

(Користи се конвенција да је отворен текст представљена малим словима, а шифрат великим словима.)

Претварање може да се представи поравнавањем две азбуке једне испод друге; азбука за шифровање је обична азбука ротирана лево или десно за одређени број места. На пример, овде је Цезарова шифра која користи леву ротацију од три места (параметар помак, у овом примеру 3, се користи као кључ):

Отворено:  абвгдђежзијклљмнњопрстћуфхцчџш
Шифра:     ГДЂЕЖЗИЈКЛЉМНЊОПРСТЋУФХЦЧЏШАБВ

За шифровање поруке једноставно се записује слово из линије „Шифра“ које се налази испод одговарајућег слова у линији „Отворено“. За дешифровање поступак је обрнут.

Отворено: Оџачар Филип шаље осмехе туђој жени, а његова кућа без деце.[1]
Шифрат:   ЏБГАГЋ ЧЛНЛТ ВГЊИ СУОИЏИ ФЦЗСЉ ЈИПЛ  Г РИЕСЂГ МЦХГ ДИК ЖИШИ

Математичко представљање[уреди]

Шифровање се такође може представити коришћењем модуларне аритметике тако што се прво слова претворе у бројеве, по шеми А=0, Б=1, ..., Ш=29. Шифровање слова x са помаком n може математички да се опише као

E_n(x) = (x + n) \mod {30}.

Сличне се изводи и дешифровање

D_n(x) = (x - n) \mod {30}.

Према наведеном, резултат је у опсегу 0..29. Ако резултат x+n или x-n није у опсегу од 0 до 29, треба додати или одузети 30.

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

Историја и употреба[уреди]

Цезарова шифра је добила име по Јулију Цезару, који је користио алфабет са левим помаком од три места.

Цезарова шифра је добила име по Јулију Цезару, који је, према наводима у тексту Светонија, такву шифру са помаком од три места користио као заштиту порука од војне важности:

Ако је имао да каже нешто поверљиво, он је то писао шифровано тако што је мењао редослед слова у алфабету и на тај начин постигао да се ниједна реч није могла препознати. Ако би неко то желео да дешифрује и добије значење тога, морао би да замени четврто слово алфабета, дакле D са A и тако даље за остала. — Светоније, Живот Јулија Цезара 56 [1].

Цезарова шифра је прва забележена употреба ове шеме, али је познато да су друге шифре замене коришћене раније. Његов рођак Август је такође користио шифровање, али са десним помаком од један и није вршио ротирање на почетак алфабета:

Увек кад је писао шифровано, писао је B уместо A, C уместо B и остала слова по истом принципу, користећи AA уместо X. — Suetonius, Живот Августа 88.

Постоји доказ да је Цезар користио и компликованије шифре и један аутор, Аул Гелије, указује на (сада изгубљену) расправу о његовим шифрама:

Има чак и једна прилично оштроумно написана расправа граматичара Проба о тајном значењу слова у састављању Цезарових порука.

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

Цезарова шифра са помаком један се налази на полеђини Мезузе.[2]

У 19. веку, лични огласи у новинама су коришћени за размену шифрованих порука коришћењем простих шема шифровања. Дејвид Кан (1967) у Тајмсу описује случајеве тајне комуникације љубавника шифроване Цезаровом шифром. Чак и касније, 1915, коришћена је Цезарова шифра: Руска војска је користила као замену за много компликованије шифре које су се код њихових трупа показале као сувише тешке за савладавање; Немачки и Аустријски криптоаналитичари нису имали муке да декриптују њихове поруке.

Данас се Цезарова шифра може наћи у дечјим играма. Цезаров помак од 13 се такође користи у ROT13 алгоритму, прост метод да се неки текст учини непрепознатљивим који се користи на неким Интернет форумима (да се сакрије спојлер), али не као метод шифровања.

Вижнерова шифра користи Цезарову шифру са различитим помаком на свакој позицији у тексту; вредност помака се дефинише коришћењем поновљеног кључа. Ако се користи случајно изабран кључ који се не понавља и који има дужину поруке, то је онда „шифровање једнократним кључем“ (енг. one-time pad - OTP) - шифра која је непробојна ако корисник сачува тајност кључа. Кључеви који су краћи од поруке представљају циклични узорак који се може открити статистички напредном верзијом фреквентне анализе.

Априла 2006. мафијашки бос Бернардо Провенцано је ухваћен на Сицилији делимично захваљујући криптоанализи његових порука писаних у варијанти Цезарове шифре. Провенцанова шифра је користила бројеве, тако да је "A" писано као "4", "B" као "5" итд.[3]

Разбијање шифре[уреди]

Помак Могући отворени текст
0 Е Њ Д З Љ П Љ У
1 Ђ Н Г Ж Л О Л Ћ
2 Д М В Е К Њ К Т
3 Г Љ Б Ђ Ј Н Ј С
4 В Л А Д И М И Р
5 Б К Ш Г З Љ З П
6 А Ј Џ В Ж Л Ж О
...
27 И Р Ж К Њ Т Њ Ц
28 З П Е Ј Н С Н Х
29 Ж О Ђ И М Р М Ф

За разбијање Цезарове шифре је довољан само шифрат. Могу да се размотре две ситуације: 1) нападач зна (или сумња) да се ради о шифри замењивања, али не и да је коришћена Цезарова шема; и 2) нападач зна да је коришћена Цезарова шифра, али не зна вредност помака.

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

У другом случају, разбијање шеме је још једноставније. Пошто је ограничен број могућих помака (за српски 30), сваки од њих редом може да се испита у „нападу грубом силом“. Један од начина да се то уради је да се напише одсечак шифрата у табелу свих могућих помака. Наведени пример је за шифрат "ЕЊДЗЉПЉУ"; отворени текст се одмах препознаје у реду са помаком 4. Други начин решавања овог метода је да се испод сваког слова шифрата испише цела азбука уназад, почев од тог слова. Овај напад се може убрзати коришћењем припремљених трака са словима. Траке се затим поравнају да се шифрат појави у једном реду, а отворени текст ће се појавити у неком од осталих редова.

Дистрибуција слова неког језика има карактеристичан и предвидљив облик. Цезарова шифра „ротира“ ову дистрибуцију и могуће је одредити помак испитујући резултујући график фреквенције слова.

Још један приступ грубом силом је да се упореди дистрибуција фреквенције слова. Представљањем фреквенције слова у графичком облику и знајући очекивану дистрибуцију слова у оригиналном језику отвореног текста, може се лако уочити вредност помака гледајући на посебне карактеристике графикона. Ово је познато као фреквентна анализа. На пример, у српскохрватском језику слова А, И, О и Е (као најзаступљенији) и Џ, Ф и Ђ (као најмање заступљена) су посебно карактеристична. Ово може радити и рачунар коришћењем статистичких метода.

За отворени текст у природном језику, по свему судећи би се добила једна веродостојна декрипција, али за изузетно кратке текстове могуће је појављивање више могућности због једнаког растојања слова (примери на енглеском: шифрат MPQY се може дешифровати као aden или know, исто тако ALIIP као dolls или wheel).

Вишеструка шифровања не омогућавају додатну сигурност. То је зато што ће два шифровања са рецимо помаком A и помаком B бити еквивалентна једном шифровању са помаком A + B.

Види још[уреди]

Референце[уреди]

  1. ^ "Оџачар Филип шаље осмехе туђој жени, а његова кућа без деце“ је панграм.
  2. ^ Alexander Poltorak The Mysterious Name
  3. ^ "Mafia boss undone by clumsy crypto" The Register

Литература[уреди]

  • David Kahn, The Codebreakers — The Story of Secret Writing, 1967. ISBN 0-684-83130-9.
  • F.L. Bauer, Decrypted Secrets, 2nd edition, 2000, Springer. ISBN 3-540-66871-3.
  • Chris Savarese and Brian Hart, The Caesar Cipher, 1999 link

Спољашње везе[уреди]