Шифра транспозиције
Шифра транспозиције или шифра померања је метод шифровања у крптографији којим се елементи отвореног текста (који су обично карактери или групе карактера) оставе непромењени али се промени њихов међусобни положај тако да шифрат представља пермутацију отвореног текста, чиме се редослед јединица мења (отворени текст се прераспоређује). Математички бијективна функција се користи на позицијама карактера за шифровање, а инверзна функција за дешифровање.
Следи неколико имплементација.
Шифра шина-ограда уреди
Шифра шина-ограда је шифра транспозиције која је добила своје име на основу начина кодирања.У овој шифри, отворени текст је написан према доле на узастопним "шинама" неке имагинарне ограде, а затим се креће горе када дођемо до дна. Порука се потом чита у редовима. На пример, користећи три "шине" и поруку “ОТКРИВЕНИ СМО. ПОБЕГНИТЕ ОДМАХ” се шифровано пише:
- О...И...И...П...Г...Е...А.
- .Т.Р.В.Н.С.О.О.Е.Н.Т.О.М.Х
- ..К...Е...М...Б...И...Д...
Чита се:
- ОИИПГ ЕАТРВ НСООЕ НТОМХ КЕМБИД
(Шифра је сломљена на пет блокова да би се избегле грешке. Ово је уобичајена техника која се користи да би шифра била читљивија. Размак у шифри се не односи на размак у отвореном тексту и тако да нема никакву информацију о отвореном тексту.)
Шифру шине-ограде су користили древни Грци у скитали, механички систем за транспозицију шифре. Систем се састојао од цилиндра и траке која је обмотана око цилиндра. Порука која је кодирана је намотана на траку. Писма оригиналне поруке се промене када се трака одмота. Међутим, поруку је лако дешифровати када се трака стргне са цилиндра истог пречника као и кодирани цилиндар [1]
Шифра руте уреди
У шифри руте, отворени текст је писан у облику мреже датих димензија, затим се очитава у обрасцу датом у кључу. На пример, користећи отворени текст : “ОТКРИВЕНИ СМО.ПОБЕГНИТЕ”.
- О Р Е С П Е И
- Т И Н М О Г Т
- К В И О Б Н Е
Кључ се може одредити "спирално ка унутра,у смеру казаљке на сату, почевши од горњег десног угла". То би дало шифру:
- ИТЕН БОИВ КТОР ЕСПЕ ГОМНИ
Ове шифре имају много више кључева од шифре шина-ограда. У ствари, за поруке разумне дужине, број могућих кључева је превелики да се преброји чак и на модерним машинама. Међутим, нису сви кључеви једнако добри. Лоше одабране руте ће оставити много делова отвореног текста или ће текст једноставно обрнути, и то ће дати криптоаналитичару траг ка рути.
Варијација на шифре рута је “Унија шифри рута”, коришћена од стране “снаге Уније” током Америчког грађанског рата. Ово је личило на обичане шифре рута, али замењене су целе речи уместо појединачних слова. Јер би то оставило неке веома осетљиве речи изложене, те речи се прво сакрију кодом (криптографским). Службеник за шифре може такође додати null речи, које се често бирају да би шифрат постао духовит.
Транспозиција колона уреди
У транспозицији колона, порука је исписана у редовима фиксне дужине, а затим се прочита поново колону по колону, а колоне су изабране у неком пермутованом редоследу. Кључна реч обично дефинише ширину редова и пермутацију по колонама. На пример, реч КЕНГУР је дужине 6 (тако да су редови дужине 6), а пермутација је дефинисана азбучним редоследом слова кључне речи. У овом случају, редослед би био "3 2 4 1 6 5".
У правилној транспозицији колона, било који резервни простори су null; у неправилним транспозицијама колона, простори се остављају празни. На крају, порука се чита по колонама, у редоследу који је одређен кључном речју. На пример, претпоставимо да користимо кључну реч КЕНГУР и поруку ОТКРИВЕНИ СМО. ПОБЕГНИТЕ ОДМАХ. У редовној транспозицији колона, пишемо на следећи начин:
- 3 2 4 1 6 5
- О Т К Р И В
- Е Н И С М О
- П О Б Е Г Н
- И Т Е О Д М
- А Х Џ З Љ П
Последња 4 слова су управо null(ЏЗЉП). Шифрат се потом чита као:
- РСЕО3 ТНОТХ ОЕПИА КИБЕЏ ВОМНЖ ИМГДЉ.
У неправилном случају, колоне нису завршене са null:
- 3 2 4 1 6 5
- О Т К Р И В
- Е Н И С М О
- П О Б Е Г Н
- И Т Е О Д М
- А Х
Шифрат је:
- РСЕОТ НОТХО ЕПИАК ИБЕВО НМИМГД
Да се дешифрује, прималац мора да ради по дужинама колона тако што дужину поруке дели дужином кључне речи. Тада може поново да напише поруку по колонама, а затим прерасподели колоне тако што ће поново формирати кључну реч.
У случају да је порука блокирана у сегменте чија је дужина кључне речи велика на сваком сегменту се примењује иста пермутација (додељена од стране кључа). Ово је еквивалентно транспозицији колона где је читање по редовима уместо по колонама.
Транспозиција колона се користи за озбиљније сврхе, као саставни део сложенијих шифара још од 1950-их година.
Двострука транспозиција уреди
Транспозиције са једном колоном могу бити нападнуте погађањем могуће дужине колоне, исписивањем порука у своје колоне (али у погрешном редоследу, како кључ још увек није познат), а затим тражењем могућих анаграмa. С обзиром да је јача, двострука транспозиција често је коришћена. Ово је једноставно транспозиција колона примењена двапут. Исти кључ може бити коришћен за обе транспозиције, или два различита.
Као пример можемо узети резултат неправилне транспозиције колона у претходном делу, и извршити другу енкрипцију са различитомм кључном речју, ЛУСТЕР, производи пермутацију "2 6 4 5 1 3".
- 2 6 4 5 1 3
- Р С Е О Т Н
- О Т Х О Е П
- И А К И Б Е
- В О Н М И М
- Г Д
Као и раније, ово се чита по колонама да би се добио шифрат.
- ТЕБИР ОИВГН ПЕМЕЏ КНООИ МСТАОД
Ако је више порука, потпуно исте дужине, шифровано користећи исте кључеве, од њих могу истовремено да се направе анаграми. Ово може довести како до разбијања поруке,тако и до разбијања кључева (тако да свака друга порука послата са тим кључевима може бити прочитана).
Током Првог светског рата, Немачка војска је користила шифру двоструке транспозиције колона, ретко мењајући кључеве. Систем је регуларно решен од стране Француза, званог Убхи, који је могао да пронађе кључеве једном када је прекинут број порука исте дужине, што је обично трајало неколико дана. Међутим, успех Француза је постао широко познат, након објављивања у Матину, и Немци су променили систем 18. новембра 1914. године. [2] Током Другог светског рата, двоструку транспозицију шифре користиле су Холандске групе отпора, француски Маки и британска Управа за специјалне операције, која је била задужена за управљање подземним активностима у Европи. [3]Такође је коришћена од стране агената америчке Канцеларије за стратешке услуге и у хитним случајевима као шифра за немачку војску и морнарицу. [4]
Све до проналаска ВИК шифра, двострука транспозиција је генерално сматрана за најкомпликованију шифру тако да је агент могао поуздано да ради при тешким условима на терену.
Мизковски транспозиција уреди
Једна од варијанти облика транспозиције колона, коју је предложио Емил Виктор Теодор Мизковски 1902. године, захтева кључну реч са поновљеним словима. У уобичајеној пракси, каснија појављивања слова кључне речи се третирају као да су наредна слова по азбучном реду, на пример, кључна реч ЛИСИЦА даје нумерички кључни низ " 4 2 5 3 6 1 ". У транспозицији Мизковски, слова која се понављају у кључној речи су нумерисана исто, ЛИСИЦА, даје кључни низ " 3 2 4 2 5 1".
- 3 2 4 2 5 1
- О Т К Р И В
- Е Н И С М О
- П О Б Е Г Н
- И Т Е О Д М
- А Х
Отворен текст у колонома са јединственим бројевима се преписује одозго наниже, а у колонама где се бројеви понављају слева надесно:
- ВОНМТ РНЦОЕ ТОХОЕ ПИАКИ БЕИМГД
Прекинута транспозиција уреди
У прекинутој транспозицији, одређене позиције у мрежи су блокиране, и не попуњавају се приликом уноса текста. Ово прекида редовне моделе и чини криптоаналитичарев посао још тежим.
Решетке уреди
Транспозиција замене која користи решетке или физичке маске са исечцима. Ово може да произведе веома неправилну транспозицију у периоду одређеном величином решетке, али захтева да дописници чувају тајну о физичком кључу. Решетке су први пут предложене 1550. године, и биле су коришћене у војне сврхе првих неколико месеци Првог светског рата.
Транспозиција и криптоанализа уреди
С обзиром да транспозиција не утиче на учесталост појединачних симбола, једноставна транспозиција лако може бити детектована криптоанализом, одређивањем степена учесталости. Уколико у шифрованом тексту постоји фреквентна дистрибуција која је слична отвореном тексу, вероватно се ради о транспозицији. Ово може бити решено анаграмирањем - премештање делова шифрата, затим потрагом за деловима који личе на анаграме Српских речи, и на крају решавање анаграма.
Једном када су анаграми пронађени, они ће нам открити информације о шаблонима транспозиције, и они стога могу бити даље истражени.
Код једноставнијих транспозиција такође може да постоји проблем због чињенице да ће кључ који је веома близу правога кључа открити дугачке секвенце легитимног текста које ће бити праћене уметнутим бесмисленим текстом. Сходно томе, такве шифре могу бити рањиве на оптималне алгоритме тражења као што је генетски алгоритам.[5]
Детаљан опис криптоанализе немачког транспозиционог шифарника може се наћи у седмом поглављу Херберт Јардлијеве књиге "Амерички црни кабинет".
Комбинације уреди
Транспозиција се често комбинује са другим техникама као што су евалуационе методе.
На пример, једноставним комбиновањем субституционог шифровања са транспозицијом колона, избегавамо слабости обе методе. Заменом високофреквентних симбола у шифрованом тексту са великом количином слова отвореног текста, не откривамо делове текста услед транспозиције. Анаграмирање транспозиција неће бити од користи због субституције. Техника комбиновања је посебно моћна када се употреби у комбинацији са фракционисањем. Мане су то што су овакве шифре знатно теже и подложније грешкама од једноставних шифри.
Фракционисање уреди
Транспозиција је посебно ефектна када се примени у комбинацији са фракционисањем - која је прелиминарна фаза која дели сваки симбол оотвореног текста на неколико шифрованих симбола. На пример, алфабет отвореног текста може бити исписан у облику координатне мреже, и затим свако слово у поруци може бити замењено са његовим координатама. Друга метода фракционисања је једноставно превођење поруке у Морзеову абуку, са укљученим симболима за размаке као и за тачке и зарезе.
Када се оваква фракционисана порука транспозиционира, компоненте појединих слова постају широко раздвојене у поруци, на тај начин постижући Клод Елвуд Шенунову дифузију. Примери шифара који комбинују фракционисање и транспозицију укључују: бифидска шифра, трифидска шифра, АДФГВX шифра и ВИК шифра.
Још један начин био би да се свако слово замени са својом бинарном репрезентацијом, ово се транспозиционира, и онда се нови бинарни низ претвори у одговарајуће АСКИ карактере.
Понављање процеса транспозиције на бинарном низу више пута пре него што га променимо у АСКИ карактере би вероватно учинило овај код тежим за декодирање. Велики број модерних блок шифара користи комплексније форме транспозиције које су базиране на овој простој идеји.
Референце уреди
- ^ Smith, Laurence Dwight (1955) [1943], Cryptography / The Science of Secret Writing, New York: Dover, стр. 16,92—93
- ^ Kahn 1996, стр. 301-304
- ^ Kahn. стр. 535 and 539.
- ^ Kahn 1996, стр. 539
- ^ Matthews, Robert A. J. (1993). „The Use of Genetic Algorithms in Cryptanalysis”. Cryptologia. 17 (2): 187—201. doi:10.1080/0161-119391867863.
Литература уреди
- Kahn, David (1996). The Codebreakers: The Story of Secret Writing. Scribner.
- Yardley, Herbert (1931). The American Black Chamber. Bobbs-Merrill.