Класични криптографски системи доминирали су у далекој историји – данас су апсолутно несигурни и подложни криптоаналитичким нападима. Изучавамо их само због одређених идеја, односно, одређених основних принципа криптографије дефинисаних тим системима.
Шифре у класичној криптографији можемо поделити на следећи начин:
Шифре транспозиције
Шифре транспозиције заснивају се на принципу транспозиције (премештања) слова у отвореном тексту, популано названо скрембловање текста. Шифрат представља скрембловани текст, а кључ примењену транспозицију. Начин рада оваквог система одговара Шеноновом принципу дифузије, где се дифузија дефинише као ширење статистике отвореног текста и шифрата.
Транспозиција колона
Најједноставнији облик транспозиције колона већ сте обрадили на почетку прве лекције – Скитала представља једноставан систем транспозиције колона. Подсетимо се тог примера из прве лекције.
Пример 1. Отворени текст је: ШКОЛСКИЦЕНТАРНИКОЛАТЕСЛА. Отворени текст има 24 карактера које записујемо у одређени број редова дефинисаних кључем, на пример у четири реда:
Ш К О Л С К
И Ц Е Н Т А
Р Н И К О Л
А Т Е С Л А
Шифрат добијамо ишчитавањем колона добијене матрице: ШИРАКЦНТОЕИЕЛНКССТОЛКАЛА. За дешифровање шифрата неопходно је познавање кључа.
Унапређење овог система могуће је увођењем кључне речи која ће одредити редослед транспозиција по азбучном реду. Дужина кључне речи мора бити једнака или мања од броја колона, а ако је мања онда се понавља.
Пример 2. Отворени текст је: ШКОЛСКИЦЕНТАРНИКОЛАТЕСЛА. Кључ је број редова 4. Кључна реч је: УЧЕНИК. Азбука је азбука српског језика: А Б В Г Д Ђ Е Ж З И Ј К Л Љ М Н Њ О П Р С Т Ћ У Ф Х Ц Ч Џ Ш.
У Ч Е Н И К
- - - - - -
Ш К О Л С К
И Ц Е Н Т А
Р Н И К О Л
А Т Е С Л А
Прво слово из кључне речи које се појављује у азбуци је слово Е, што значи да прво ишчитавамо слова у трећој колони: ОЕИЕ. Друго слово из кључне речи које се појављује у азбуци је слово И, па стога ишчитавамо слова из пете колоне СТОЛ. Затим следи слово К и ишчитавање шесте колоне, па Н и ишчитавање четврте колоне, па У и ишчитавање прве колоне и на крају Ч и ишчитавање друге колоне. Сада шифрат изгледа овако: ОЕИЕСТОЛКАЛАЛНКСШИРАКЦНТ. За дефишфровање овог шифрата неопходно је познавање кључа, познавање кључне речи и познавање редоследа слова у азбуци.
Пример 3. Ставимо се сад у улогу криптоаналитичара, односно нападача Труди. Претпоставимо да Труди зна редослед слова у српској азбуци, да је пресрела шифрат из претходног примера ОЕИЕСТОЛКАЛАЛНКСШИРАКЦНТ којег је Алиса послала Бобу и да познаје шифарске системе са транспозицијом колона. Труди не зна кључ, нити зна да ли је Алиса користила и неку кључну реч како би “ојачала” шифрат. Шифрат од 24 слова Труди треба да упише у матрицу димензија [n,m], што могу бити матрице димензија [2,12], [3,8], [4,6], [6,4], [8,3], [12,2]. Након што је креирала шест матрица са уписаним словима шифрата, ишчитавањем колона Труди неће доћи до отвореног (смисленог) текста и закључиће да је Алиса користила и кључну реч. Због постојања кључне речи Труди мора да започне са заменом колона у свим матрицама све док не дође до смисленог текста, што је еквивалентно потпуној претрази простора кључева. Када дође до матрице димензија [6,4], у неком тренутку ће заменом колона доћи до смисленог текста.
Наравоученије из овог примера: за сигурност криптографског система неопходан је велики простор кључева, али то није довољан услов. Велики простор кључева може да успори нападача да заврши са нападом у прихватљивом временском року, али не може да га спречи да разбије систем.
Двострука транспозиција колона
Двострука транспозиција колона представља још веће унапређење транспозиција колона помоћу кључних речи. Имплементира се променом редоследа колона и редоследа редова у матрици димензија [n,m]. Кључ представља димензију матрице, односно број колона, а кључне речи редоследе пермутација по колонама и редовима. Шифрат добијамо ишчитавањем колона након транспозиција.
Пример 4. Отворени текст је: ШКОЛСКИЦЕНТАРНИКОЛАТЕСЛА. Кључ је број редова матрице 4, односно димензија матрице [6,4], а кључне речи 403152 и 2103.
0 1 2 3 4 5 4 0 3 1 5 2
+----------- +-----------
0|Ш К О Л С К 2|О Р К Н Л И
1|И Ц Е Н Т А ---> 1|Т И Н Ц А Е
2|Р Н И К О Л 0|С Ш Л К К О
3|А Т Е С Л А 3|Л А С Т А Е
Добијени шифрат је ОТСЛРИШАКНЛСНЦКТЛАКАИЕОЕ.
Пример 5. Ставимо се опет у улогу криптоаналитичара, односно нападача Труди. Претпоставимо да Труди пресрела шифрат из претходног примера ОТСЛРИШАКНЛСНЦКТЛАКАИЕОЕ којег је Алиса послала Бобу и да познаје шифарске системе са двоструком транспозицијом колона. Труди не зна кључ ни кључну реч. Како постоји шест могућих димензија матрице, а извршена је и транспозиција колона и транспозиција редова, потпуна претрага простора кључева ће јој одузети много времена. Можете ли да помогнете Труди? Постоји ли скраћени напад?
Труди може да започне са погађањем димензија матрице и пермутацијом колона. Са пермутацијом редова може да започне тек када види смислену реч или део речи у неком од редова. То значи да ће морати да изврши само делимичну претрагу простора кључева. Иако је на почетку лекције двострука транспозиција колона звучала као сјајна идеја, на крају опет можете закључити да и поред великог простора кључева и повећања комплексности алгоритма, нападач може да у одређеном временском периоду разбије систем.
Шифре супституције
Шифре субституције, односно шифре замене, заснивају се на замени (вредности) слова, а не на замени позиције слова као у претходном поглављу. То значи да се једно слово нпр. А пресликава у друго слово, нпр. Ф.
Ако посматрамо само мала слова алфабета енглеског језика којих има 26, простор кључева износи 26! што је једнако 403291461126605635584000000. Ако нам је потребна једна секунда да проверимо један кључ, значи да нам за потпуну претрагу простора кључева треба 6721524352110093926400000 минута, односно 112025405868501565440000 сати, односно 4667725244520898560000 дана, односно 12788288341153146740 година! Како су рачунари данас изузетно брзи, рецимо да можемо да проверимо милион кључева у секунди. То би значило да нам за потпуну претрагу кључева треба 12788288341153 година. Опет неприхватљив временски период. Милијарду кључева у секунди? 12788288341 година. И даље неприхватљиво. Да ли то значи да су шифарски системи са шифрама супституције безбедни. Наравно да не.
Моноалфабетске шифре
Моноалфабетске шифре користе фиксне замене током целе поруке и један тип моноалфабетских шифара сте већ обрадили на почетку прве лекције – Цезарова шифра. Подсетимо се тог примера из прве лекције.
Пример 6. Коришћена азбука су велика слова српског језика, отворени текст је НИКОЛАТЕСЛА, кључ и алгоритам за шифровање је померање азбуке три слова у десно:
А Б В Г Д Ђ Е Ж З И Ј К Л Љ М Н Њ О П Р С Т Ћ У Ф Х Ц Ч Џ Ш
Ч Џ Ш А Б В Г Д Ђ Е Ж З И Ј К Л Љ М Н Њ О П Р С Т Ћ У Ф Х Ц
што резултује шифратом ЛЕЗМИЧПГОИЧ. Поступак дешифровања је обрнут. Померену азбуку у десно враћамо три слова у лево:
Ч Џ Ш А Б В Г Д Ђ Е Ж З И Ј К Л Љ М Н Њ О П Р С Т Ћ У Ф Х Ц
А Б В Г Д Ђ Е Ж З И Ј К Л Љ М Н Њ О П Р С Т Ћ У Ф Х Ц Ч Џ Ш
што резултује отвореним текстом НИКОЛАТЕСЛА.
Ако сваком великом слову у српском језику доделимо број од 0 до 29, тако да је А=0, Б=1, В=2, …, Ш=29, онда можемо формализовати алгоритме шифровања и дешифровања на следећи начин:
Ci = Pi + K(mod 30)
Pi = Ci + (30 – K)(mod 30)
где је: Pi i-то слово отвореног текста, Ci i-то слово шифрата, K кључ односно померај.
Ако посматрамо енглески алфабет, онда ћемо словима додељивати вредности од 0 до 25, јер у енглеском алфабету постоји 26 слова. Такође ћемо приликом формализовања алгоритама користити операцију mod 26.
Ако радимо са ASCII карактерима, онда су словима већ додељене декадне вредности према ASCII табели у колони Dec:
Пример 7. Ставимо се опет у улогу криптоаналитичара, односно нападача Труди. Претпоставимо да је Труди пресрела шифрат из претходног примера ЛЕЗМИЧПГОИЧ и да зна алгоритме шифровања и дешифровања Цезаровом шифром, али да не зна кључ, односно померај. Пошто је у питању померај, а не фиксна замена по неком распореду, Труди ће из највише 29 покушаја доћи до кључа. Ако Труди познаје фреквенцију појаве слова у српском језику, до кључа ће вероватно доћи још брже.
Пример 7. Алиса и Боб, незадовољни Цезаровим кодом, креирали су свој шифарски систем са моноалфабетском шифром која изгледа овако:
А Б В Г Д Ђ Е Ж З И Ј К Л Љ М Н Њ О П Р С Т Ћ У Ф Х Ц Ч Џ Ш
Ј К М И О Т Н Њ П Р Ћ У Х Ц С Ф А Ш Ч Џ Е Ж Б В З Г Л Љ Д Ђ
Сада шифрат отвореног текста НИКОЛАТЕСЛА изгледа овако: ФРУШХЈЖНЕХЈ. а простор кључева се са 29 повећао на 30! (факторијел). Да ли је Труди побеђена? Наравно да није. Разбијање шифарских система са моноалфабетским шифрама помоћу фреквенцијске анализе појаве слова у неком језику је техника из IX века, до данас усавршена и потпуно функционална.
Унапређење оваквог начина моноалфабетског шифрирања представљају хомофоне шифре код којих шифрат може да садржи више знакова од укупног броја знакова у азбуци.
Пример 8. Алиса и Боб не одустају! Сада су сваком слову азбуке српског језика доделили по 3 карактера (нпр. броја) и њихов систем изгледа овако:
А Б В Г Д Ђ Е Ж З И Ј К Л Љ М Н Њ О П Р С Т Ћ У Ф Х Ц Ч Џ Ш
012 345 678 910 123 456 789 098 765 432 109 876 543 210 987 654 321 159 753 973 179 468 624 579 513 846 813 264 597 792
Сада шифрат отвореног текста НИКОЛАТЕСЛА изгледа овако: 654432876159543012468789179543012.
Решили су да ни то није довољно и да би било добро да словима која се често понављају доделе више вредности, па њихов систем изгледа овако:
А А Б В Г Д Ђ Е Е Ж З И Ј К Л Љ М Н Њ О О П Р С Т Ћ У У Ф Х Ц Ч Џ Ш
012 210 345 678 910 123 456 789 201 098 765 432 109 876 543 210 987 654 321 159 195 753 973 179 468 624 579 759 513 846 813 264 597 792
Шифрат генерисан на овај начин требао би да прикрије статистичке особине отвореног текста и да личи на случајан низ бројева. Међутим, Труди да зна да статистичком анализом може да разбије и овај систем јер је тешко постићи случајност (ентропију). Ентропија представља неодређеност шифрата, па ако шифрат има велику ентропију Труди ће имати много посла, и обрнуто. Данас се улажу велики напори како би се системи заштитили од напада заснованих на статистичким методама.
Полиграмске шифре
Полиграмске шифре представљају још једно унапређење шифарских система са шифрама субституције. Групе слова шифрују се заједно, а не као појединачна слова. На пример, НИК може да се шифрује са АБА, ОЛА може да се шифрује са ККА, итд. Два примера полиграмских шифара су плејфер (Playfeir) шифра и Хилова (Hill) шифра.
Плејфер шифра заснива се на замени блокова од два карактера (биграми). Овај поступак шифровања описао је Charles Wheatstone 1854. године, а користили га је војска Велике Британије у I светском рату. Кључ је била матрица димензија [5,5], са 25 слова, без слова Ј. Матрица се креирала на основу изабране кључне речи, а биграм P1P2 отвореног текста шифрује се у складу са следећим правилима:
- Ако су p1p2 у истом реду тада су c1c2 два слова десно од p1p2, где је прва колона суседна десна колона последњој колони.
- Ако су p1p2 у истој колони тада су c1c2 два слова испод p1p2, где је први ред суседни доњи последњем реду.
- Ако су p1p2 у различитим колонама и редовима тада су c1c2 остале две ивице темена правоугаоника који садржи ивице p1p2, где је c1 у истом реду као p1 док је c2 у истом реду као p2.
- Ако је p1=p2 тада се између њих врши уметање неутралног (NULL) карактера.
- Ако отворени текст има непаран број слова тада се на крај поруке додаје неутрални карактер.
Криптоанализа плејфер шифре зависи првенствено од величине отвореног текста који се шифрује. Ако је шифрат велик примењује се фреквенцијска анализа биграма. Ако је шифрат мали, фреквенцијска анализа није могућа па се погађају могуће речи, упоређују са структуром шифрата и поступно се реконструише матрица.
Хилова шифра креирана је године од стране Lester Hill-а и ради на основу линеарне алгебре. Она ради са групом од више од три слова отвореног текста. Величина блока отвореног текста одређује димензије матрице која се користи као кључ. Хил је увео и инвертовање и множење матрица у процесу скрембловања отвореног текста, и на крају и системе линеарних једначина. Да би доказао да његов систем није сувише компликован патентирао је и шифарску машину.
На овај начин Хил је заштитио шифарски систем од фреквенцијске анализе слова и биграма јер је прикрио структуру отвореног текста у потпуности. Међутим помоћу напада “познати отворени текст” и “изабрани отворени текст” систем се може разбити, па зато није никада доживео практичну примену.
Полиалфабетске шифре
Шифарски системи са полиалфабетским шифрама елиминишу пресликавања оригиналних фреквенција појављивања слова у отвореном тексту у њихове замене у шифрату коришћењем вишеструких замена.
Најпознатији пример полиалфабетских шифара представља Вижнерова шифра (Vigenere) из XIX века (заправо описана још у XVI веку од стране Ђована Батисте). Можемо је описати као мулти-Цезарову шифру, јер се свако слово отвореног текста пресликава у једно од могућих слова у зависности од позиције у тексту (полиалфабетска замена).
Овакав начин шифровања био је инспирација за развој много комплекснијих система за шифровање попут Енигме у II светском рату – Енигма у основи користи полиалфабетске шифре замене.
Перфектне шифре
Појам перфектне шифре дефинисао је Клод Шенон (кога смо раније помињали) 1949. године. Перфектна шифра представља криптографски механизам у којем шифрат не даје никакву информацију о отвореном тексту, нити даје информацију о кључу који је коришћен. Математички формулисано, ако се у простору отворених текстова P, отворени текст х појављује са вероватноћом p(x), онда постоји кључ који пресликава сваку поруку у сваки шифрат са једнаком вероватноћом. Просечна количина информација у порукама мери се ентропијом и зависи од вероватноће. Што је вероватноћа поруке већа, количина информација је мања и обрнуто. Функција која ово описује је бинарни логаритам, што значи да количина информација у поруци представља потребни број битова за опис поруке.
У класичној криптографији One-time pad (OTP) је једина доказана сигурна шифра. Дефинисали су је Гилберт Вернам и Џозеф Мауборн 1917 године. OTP ради над бинарним подацима. Шифрат се добија применом ексклузивне дисјункције (XOR, симбол ⊕, у програмском језику С оператор ^) над отвореним текстом и кључем, а отворени текст применом екскузивне дисјункције над шифратом и кључем. Сигурност се заснива на случајности кључа и на једнократној употреби кључа. ОТР је доказано безбедна када:
- Шифрат не даје никакву информацију о отвореном тексту
- Сваки отворени текст исте је дужине и исто је “вероватан”
- Кључ је случајан и коришћен само једном
- Кључ је познат само пошиљаоцу и примаоцу
- Кључ је исте дужине као и порука
- Механизам провере интегритета поруке не постоји
Пример 9. Алиса користи ASCII табелу (или програмски језик C) за претварање текстуалних у бинарне вредности. Написала је Бобу поруку ZDRAVO и шифровала је са кључем POBEDA користећи ексклузивну дисјункцију. Таблица истинитости ексклузивне дисјункције показује да на излазу добијамо 1 када су улази различити (10 и 01), односно добијамо 0 када су улази исти (00 и 11).
Z D R A V O
P 01011010 01000100 01010010 01000001 01010110 01001111
P O B E D A
K 01010000 01001111 01000010 01000101 01000100 01000001
C 00001010 00001011 00010000 00000100 00010010 00001110
Боб прима следећу поруку од Алисе: 000010100000101100010000000001000001001000001110 и дешифрује је, јер зна кључ.
C 00001010 00001011 00010000 00000100 00010010 00001110
P O B E D A
K 01010000 01001111 01000010 01000101 01000100 01000001
P 01011010 01000100 01010010 01000001 01010110 01001111
Z D R A V O
Алиса шаље наредну поруку Бобу користећи други кључ. Боб дешифрује и ту поруку јер зна кључ. Следи трећа порука и трећи кључ… Труди гледа дуге бинарне низове и збуњена је???
Ово је сценарио који се догодио у реалном животу у време другог светског рата и раних година хладног рата. Пројекат Венона спроводило је сигнално одељење (данас NSA) америчке контраобавештајне службе задужено за разбијање криптографских порука ради спречавања шпијунаже. Совјетска шпијунска мрежа на америчкој територији успела је да унесе кључеве у Америку, те је исте користила за шифровање порука ОТР шифрама. Поруке су биле у вези америчког нуклеарног програма.
Кодне књиге
Кодна књига (codebook) је књига која упарује речи (отворени текст) са кодовима (шифрат). Безбедност шифарских система са кодним књигама заснива се на физичкој безбедности самих кодних књига јер оне представљају кључ.
Данас се, у криптографији, појам кодна књига не односи само на физички одштампане књиге, него на било који документ, физички или електронски, који садржи табелу са упареним отвореним текстовима и шифратима. Највећи изазови у шифарским системима са кодним књигама односе се на безбедност дистрибуције и физичку безбедност кодних књига.