1.3. Характеристика криптографічної системи Хілла.

Алгебричний метод, який узагальнює афінну систему підставляння Цезаря, формалізований опис якого має такий вигляд:

,

був сформульований Лестером С. Хіллом¹ [7] для визначення n-грам.

Множина цілих чисел , для якої визначені операції додавання, віднімання та множення за модулем m, є прикладом кільця R, тобто алгебричною системою пар елементів. Ця алгебрична система володіє такими властивостями:

• пари елементів кільця R утворюють комутативну групу щодо операції додавання; для неї існують одиничний і зворотний елементи;

• операції множення та додавання задовольняють асоціативному і дистрибутивному законам.

Мультиплікативне зворотне ^-1 елемента  кільця R не завжди може існувати. Наприклад, якщо модуль m = 26, то значення (2^-1)mod 26 і (13^-l)mod 26 не можуть існувати.

Якщо модуль m є простим числом p, то існує зворотна величина будь-якого ненульового елемента t з (при m = p), оскільки значення (1·t)mod m, (2·t)mod m, (3·t)mod m, ..., ((p–1)·t)mod m відрізняються, якщо 1 t  p–1.

Множина , де p – просте число, є прикладом алгебричної системи, яку називають кінцевим полем. Ненульові елементи утворюють мультиплікативну групу.

Множина всіх n-грам з компонентами з кільця утворює векторний простір над кільцем . Кожна n-грама називається вектором. У векторному просторі для векторів визначено операції додавання та віднімання за модулем n, а також скалярне множення вектора на елемент t кільця . Додавання та скалярне множення є операціями, що задовольняють комутативному, асоціативному і дистрибутивному законам. Вектор є лінійною комбінацією векторів , якщо

. (1.5)

Лінійне перетворення є відображенням:

, (1.6)

яке задовольняє умові лінійності

для всіх s, t в і у . Лінійне перетворення може бути представлено матрицею розміром nn такого вигляду

, (1.7)

причому

Базисом для векторного простору є набір векторів з , які лінійно незалежні і породжують . Кожен базис для містить n лінійно незалежних векторів. Будь-який набір з n векторів, які лінійно незалежні над називаються базисом.

Нехай є лінійним перетворенням, що описується матрицею (7), причому . Якщо вектори лінійно незалежні над , тоді їх образи лінійно незалежні над тільки в тому випадку, якщо визначник матриці , що позначається як , не ділиться на будь-яке просте p, яке ділить m. Перетворення називається зворотним (або не виродженим) лінійним перетворенням, що має зворотне перетворення :

, (1.8)

де – одинична матриця. Окрім цього, є також лінійним перетворенням. На­приклад, коли m = 26 і матриця перетворення

,

то визначник цієї матриці

,

.

Тому існує зворотне перетворення . Неважко переконатися, що задовольняє такому співвідношенню

Нехай є лінійним перетворенням на з матрицею . Використовуємо це перетворення для визначення 3-грами підставляння в українському алфавіті за такою таблицею кодів:

0	1	2	3	4	5		0	1	2	3	4	5
а	б	в	г	д	е	0	0	1	2	3	4	5
є	ж	з	и	і	ї	1	6	7	8	9	10	11
й	к	л	м	н	о	2	12	13	14	15	16	17
п	р	с	т	у	ф	3	18	19	20	21	22	23
х	ц	ч	ш	щ	ю	4	24	25	26	27	28	29
я	ь	_	.	,	'	5	30	31	32	33	34	35

1.4. Обґрун­ту­вання ак­ту­аль­ності те­матики ро­бо­ти, ог­ляд су­час­них роз­ро­бок за те­мою.

Висновки до розділу, мета і завдання дослідження.