Афинна криптосистема

Лаборатория №1

Основи на криптирането на данни

Цел на работата:изучаване на основните принципи на криптиране на информация, запознаване с добре познати алгоритми за криптиране, придобиване на умения за тяхната софтуерна реализация.

Проблемът със скриването на информация е бил актуален за човечеството в древни времена, писмени доказателства за използването на най-простите методи за криптиране се намират сред древните гърци през 5-6 век. пр.н.е. Развитието на цивилизацията, появата на нови средства за комуникация (първо писмени, а след това електронни) наложиха все по-строги изисквания към методите за криптиране, което доведе до появата на отделна наука, която се занимава със защитата на информацията чрез нейното трансформиране -криптологията. Тази наука има две направления: криптография и криптоанализ.

Криптографиятае наука за методите и средствата за преобразуване на информация във форма, която прави трудни или невъзможни неоторизирани операции с нея (четене и/или модификация).

Основната концепция на криптографията е шифър [1].Шифърът е набор от инжективни (обратими) трансформации на набор от елементи на обикновен текст в набор от елементи на шифрован текст, индексирани от елементи от набор от ключове:

къдетоXX–кодирано съобщение от набор от обикновени текстове;

SS–шифрован текст от набора от възможни кодирани текстове;

k– ключ за криптиране;

F– преобразуване, извършено от шифъра.

Свойството инжективност на шифъра означава, че има преобразуванеF-1 такова, че

Процесът на преобразуване на обикновен текст (предаденото съобщение) в шифрован текст се наричашифроване.Обратното преобразуване на шифрован текст в обикновен текст се наричадекриптиране. Класификацията на шифрите по различни критерии може да се намери в [2].

Криптоанализъте наука (и практика на нейното приложение) за методите и средствата за разбиване на шифри. Отварянето се разбира като задача за получаване на съответния открит текст и/или ключ за криптиране от известен шифрован текст.

Към днешна дата са изобретени голям брой различни шифри. Някои от тях в момента се използват за практически цели за защита на данни в различни информационни системи, а някои са само от исторически интерес, тъй като трансформациите, използвани в тях, не осигуряват адекватна устойчивост срещу отваряне за текущото ниво на компютърна изчислителна мощ. Познаването на такива остарели криптоалгоритми обаче е от несъмнена полза, тъй като ви позволява да проследите еволюцията на криптоалгоритмите, кристализацията на съвременните принципи на криптиране в тях и да оцените силните и слабите страни на определени криптографски трансформации.

Един от първите документирани шифри ешифърът на Цезар, използван от известен генерал в собствената му кореспонденция. В шифъра всяка буква се заменя с буквата, разположенаkсимвола вдясно в азбуката по модул, равен на броя на буквите в азбуката:

Ck(j)=(j+k)(modn) e).

По този начин ключът за криптиране тук е числото k, което определя размера на отместването.

Очевидно обратното заместване е

Ако е необходимо, азбуката може да бъде разширена с препинателни знаци, главни букви, цифри, така че шифърът да може да се справи с всичкосимволи на изходния текст.

Общият брой на валидните ключове е n, като един от ключовете преобразува текста в себе си. Такъв малък брой ключове направи възможно извършването на прост криптоанализ на шифрования текст още по времето на Цезарпо метода на лентите, когато няколко ленти с написаната върху тях азбука бяха поставени една до друга, така че фрагмент от шифрования текст се получи хоризонтално. След това лентите се изместваха синхронно нагоре или надолу, докато някаква четима фраза се появи хоризонтално на мястото на шифрования текст. Стойността на изместване на лентата определя еднозначно ключаk.

Цезар шифър с ключова дума.

В тази версия на шифъра на Цезар ключът е даден от числотоk(0-1a,b(j)=(j-b+n)*a-1 (modn)

Търсенето на мултипликативното обратно (означено катоa-1 ) се извършва съгласно Евклидовия алгоритъм. Очевидно, когатоa=1, афинната криптосистема се изражда в шифър на Цезар. Взаимната простота наaиnе необходима, за да бъде преобразуването биективно; в противен случай са възможни преобразувания на различни знаци в един и неяснота при декодиране. Броят на ключовете в една афинна криптосистема зависи от кардиналността на използваната азбука. За азбуката на българския език коефициентътbможе да приема 33 стойности, коефициентътaможе да приема само стойности, взаимнопрости с числото 33: 1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32. Общо 20 стойности. Всички възможни комбинации от валидниbиaдават ключово пространство от 33*20=660-1=659 ключа (1 ключ се изважда, защото комбинацията отa=1 иb=33 трансформира азбуката в себе си).

Шифърът на Цезар и афинната криптосистема принадлежат към класа на моноазбучните криптосистеми, т.е.ключ, някои букви от оригиналния открит текст винаги ще бъдат заменени със същата буква в шифрования текст. Следователно тези шифри могат да бъдат разбити чрезметода на честотния криптоанализ.Честотният анализ използва свойството на шифрования текст, че честотата на появяване на символите в него съвпада с честотата на появяване на съответните знаци в открития текст. Ако обаче вземем предвид, че честотите на срещане на различните знаци в текстовете на съответния език са неравномерно разпределени (например относителната честота на срещане на буквата „А“ в текстовете на български език е 0,069, а на буквите „Ф“ 0,003), то чрез изчисляване на относителната честота на срещане на буквите в шифрования текст можем да приемем, че знакът, който най-често се среща в ciphertext съответства на знака, който най-често се среща в текстове на съответния език, и по този начин намерете ключаkза шифър на Цезар. За да разбиете параметритеaиbна афинна криптосистема, трябва да намерите съвпадение между две букви - най-често срещаната в шифрования текст и втората по честота. Ефективността на честотния анализ на шифър на Цезар с ключова дума до голяма степен зависи от дължината на използваната ключова фраза, докато общият брой разрешени азбучни отражения е, както вече беше споменато,n!.

Площад на Полибий

Друга модификация на едноазбучната замяна е квадратът на Полибий, при който азбучен знак се заменя с двойка числа или символи според определено правило. Помислете за правоъгълник, често наричан дъската на Полибий.