Криптосистеми

Криптосистеми




1. ОБЧИСЛЮВАЛЬНО СТІЙКІ ТА ЙМОВІРНО СТІЙКІ КРИПТОСИСТЕМИ



Криптоаналітик знає криптиосистему, може мати апаратуру, може перехоплювати криптограми. При цьому, криптоаналітик може визначити:



- Мі → Сj – ? ;

- Kij → Мі → Сj – ?



Атака при відомих парах повідомлень та криптограм



Мі → Сj; Kij – ?



Атака з вибором повідомлення

Криптоаналітик знає Мі та алгоритм зашифровування



            

            Мі →





Алгоритм зашифровування





Kij



→ Сj



(Мі , Сj) → Kij – ?



Атака з вибором криптограм



            Сj →





Розшифровування



Kij

→ Мі



(Сj , Мі) → Kij



Адаптивна атака

Така атака, при якій може здійснюватись зашифровування та розшифровування

Визначення обчислювально стійкої криптосистеми та умови реалізації

Обчислювально стійка криптосистема визначається як така, у якої 



. 



Така система може будуватись як і безумовно стійка криптосистема. У обчислювально стійких криптосистемах замість ключової послідовності Кi використовують Гi.



	

	



Процес – процес гамаутворення (шифроутворення).

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







Ключ повинен породжуватись рівно ймовірно, випадково та незалежно. Як правило, більшість пристроїв працюють з бітами.



,

.

				

				Функція Ψ, для забезпечення необхідного рівня стійкості, повинна задовольняти ряду складних умов:

					Період повторення повинен бути не менше допустимої величини:

		

		


				

					Закон формування гами повинен забезпечувати „секретність” гами. Тобто, Гі повинна протистояти криптоаналітику 

		

		 

				

				В якості показника оцінки складності гами використовується структурна скритність:

				

		,  

				,

				

				де  – повний період;

				– кількість бітів, які криптоаналітик повинен одержати, щоб зробити обернення функції Ψ, тобто знайти ключ.

					Відновлюваність гами в просторі та часі.

					Відсутність колізії, тобто, співпадання відрізків гами.

Розглянута система відноситься до класу симетричних.

В якості оцінки стійкості використовується така множина параметрів



.



1. =128, 192, 256, 512



.

2. біт.


3. Безпечний час для атаки типу „груба сила”:



.



4. Відстань єдності шифру . Можна показати, що для обчислювально стійкої криптосистеми справедливо співвідношення:



,



де  – умовна апостеріорна ентропія криптоаналітика;

– ентропія джерела ключів;

l – довжина зашифрованого тексту або гами;

d – збитковість мови (під надмірністю d розуміється ступінь корельованості (залежності) символів у мові і не порівняно ймовірностні їхньої появи в повідомленні);

m – розмірність алфавіту.

Криптоаналіз вважається успішним, якщо =0.







Фізичний зміст l0 – мінімальна кількість гами шифрування, яку необхідно достовірно перехопити, щоби мати можливість розв’язати задачу визначення ключа, або обернення функції Ψ. Якщо n < l0 , то однозначно повідомлення. 

Імовірно стійка криптосистема відноситься до класу асиметричної:






При відомому одного з цих ключів складність повинна бути не нижче ніж субекспоненціальна



.



В залежності від виду двохключових перетворень криптоперетворення можна розділити на:

1) криптоперетворення в кільцях. Задача факторизації модуля на два простих числа:







2) криптоперетворення в полях Галуа GF(p). Задача розв’язання обернення функції:



,



де  – відкритий ключ;

 – первісний елемент;

– особистий ключ;

Р – просте число.

3) криптоперетворення в групах точок еліптичних кривих E(GF(q)). Задача розв’язання дискретного логарифму:



,



де d – особистий ключ;

Q – відкритий ключ;

G – базова точка;

q – поле.



2. МАТЕМАТИЧНІ МОДЕЛІ КРИПТОПЕРЕТВОРЕНЬ



Криптоперетворення розподіляються на:

- симетричні, якщо виконується умова:



,



або ключ обчислюється не нижче ніж з поліноміальною складністю;

-асиметричні, якщо виконується умова:



,



або ключ може бути обчислений при знанні іншого не нижче ніж з субекспоненційною складністю.

Поліноміальною складністю називається така складність, при якій n входить в основу:







Субекспоненційною складністю називається така складність, при якій n входить в показник:



.




Основною ознакою для таких криптоперетворень являється ключ (або ключі). Кожне криптоперетворення задається прямим і зворотнім перетворенням:







Основні асиметричні криптоперетворення по математичному базису:

перетворення в полях GF(p);

перетворення в кільцях NZ;

перетворення на еліптичних кривих EC.

Основні симетричні криптоперетворення по математичному базису:

1) афінні: 



,



де А – деяка матриця;

2) нелінійні: не можна представити у вигляді лінійної функції.

В залежності від виду симетричні криптоперетворення діляться на:

- підстановка;

- гамування;

- управляємий зсув бітів;

- перестановка і інші елементарні перетворення.

Сутність асиметричних криптоперетворень в кільці

Нехай Мі – блок інформації, який треба захистити. Представимо цей блок у вигляді числа lM. Використовується ключова пара (Ек, Dк), що породжується випадково.

Пряме перетворення:





,



де  - функція Ейлера.



.



Зворотне перетворення:



,



т.ч. перетворення зворотне і однозначне.

Стійкість проти атак в кільці визначається складністю факторизації числа N на прості числа P та Q.

Сутність асиметричних криптоперетворень в полі

Нехай є просте поле Галуа GF(p). Для кожного p існує множина первісних елементів:



.



Кожний первісний елемент породжує поле:



.



Криптоперетворення пов’язані з побудуванням пари ключів. Нехай є два користувачі А та В.






А

В

ХА

ХВ













де ХА, ХВ – випадкові ключі довжиною lk;

YА, YВ – відкриті ключі.

При побудуванні використовуються властивості поля.



,



де r – сеансовий ключ.

Користувач А передає користувачу В пару . Потім користувач В обчислює:



.



Таким чином, перетворення в полі є зворотнім та однозначним.

Модель криптоаналітика заключається в тому, що необхідно знайти ХВ. Реалізуючи рівняння відносно ХВ одержимо секретний ключ. Стійкість проти атак в полі визначається складністю розв’язання рівняння .

Сутність асиметричних криптоперетворень в групі точок еліптичних кривих

За 20 років розроблено нові математичні апарати, які дозволяють ефективно розв’язувати рівняння, що реалізовані в полях та кільцях. В 90-х роках було запропоновано використовувати криптоперетворення, що базуються на перетвореннях в групі точок еліптичних кривих над полями GF(p), GF(2m), GF(pm).

Для випадку простого поля:







елементом перетворення є точка на еліптичній кривій, тобто ,що обчислюється за модулем р. Формується ключова пара:



, де .

,



де G – базова точка на еліптичній кривій порядку

QA – відкритий ключ, точка на еліптичній кривій з координатами (ха, уа).

Задача криптоаналітика знайти таємний ключ dA. Складність розв’язку цього рівняння набагато вище, ніж в полі. В полі – субекспоненційна складність, а в групі точок еліптичних кривих – експоненційна складність.



3. СИМЕТРИЧНІ КРИПТОПЕРЕТВОРЕННЯ



				Застосовувані на практиці криптоперетворення розділяють на 2 класи по стійкості:

			обчислювально стійкі.

			ймовірно стійкі (доказово стійкі).

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

				

				

				

				
Nвар – кількість команд, операцій для рішення задачі криптоаналізу.

				 - продуктивність криптосистеми, вар/сек. 

				k – коефіцієнт кількості сек/рік  

				Рр – імовірність рішення задачі.

				ВР і ДС повинні задовольняти. До доказово стійких перетворень відносять перетворення з відкритими ключами, з відкритим поширенням ключів і т.д. У цих системах задача криптоаналізу полягає в рішенні якоїсь іншої математичної задачі. Обчислювально стійкі системи реалізуються за рахунок застосування симетричних криптоперетворень.

				

				

				

				

				У симетричних криптосистемах ключ зашифрування або збігається з ключем розшифрування, або обчислюється один з іншого з поліноміальною складністю.

				

				

				

Поліноміальна складність

				Нехай n – розмірність вхідних даних, що підлягають криптоперетворенню і нехай t(n) є складність перетворення цих даних у сек. тактах, командах. Складність називають поліноміальної, якщо вона представлена:

				

				 

				

				
 - набір констант.

				

				    - експонентна складність

				

				В даний час як функцію f реалізуючої криптоперетворення використовуються афінні шифри. 

				Афінне перетворення – перетворення, яке можна одержати комбінуючи рухи, дзеркальні відображення і гомотепію в напрямку координатних осей.

				Гомотепія – перетворення простору чи площини щодо точки по направляючим осях з коефіцієнтами. 

				До афінних шифрів відносяться шифри зрушення, лінійні афінні шифри. 

				У потокових криптоперетвореннях об'єктами взаємодії є символи повідомлення Мi і символи ключа j, причому з використанням символів ключа формується Гi.

				

				Мi , j ,  

				

				

				Рис 1

				

				Розшифрування: 

				






				При обчисленні необхідно строго синхронізувати по i, тобто: Гi при розшифруванні і зашифруванні та сама. 

М – ічне шифрування (по mod).

				Приклад: 

				

				

				

Двійкове гамування 



				

				

				Гi повинна породжуватися псевдовипадковим чи випадковим процесом. Реалізація процесу повинна залежати від вихідного ключа. 

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

Симетричні криптоперетворення, якщо або:



,



або можуть бути обчислені один при знанні іншого не нижче ніж з поліноміальною складністю.

Симетричні шифри діляться на блокові та потокові шифри.

Блокові симетричні шифри використовуються в чотирьох режимах роботи:

блокового шифрування;

потокового шифрування;

потокового шифрування зі зворотнім зв’язком по криптограмі;

вироблення імітоприкладки;

вироблення псевдопослідовностей (ключів).

Побудування таких шифрів здійснюється на використані декількох елементарних табличних або криптографічних перетворень. До них відносяться:

афінні перетворення;

перетворення типу підстановка (перестановка) символів;

гамування (складання з ключем);

аналітичної підстановки (заміни).

Основні криптоперетворення симетричного типу

Афінний шифр

Твердження 1

Нехай  є мова за алфавітом  і алфавіт мови співпадає з алфавітом криптограми. Кожному символу поставлене  число. Тоді існує афінний шифр з ключем , елементами якого є:



,



якщо найменший спільний дільник .

В афінному шифрі зашифровування здійснюється таким чином:



,



а розшифровування:



,


де 



,

.



Цей шифр є однозначно зворотнім.

Лінійний шифр

Твердження 2 

Якщо в афінному шифрі , то існує лінійний взаємозворотній шифр, у якому зашифровування здійснюється як:



,



а розшифровування:



.



Твердження 3

Якщо в афінному шифрі , то існує адитивний однозначно зворотній шифр правилом шифрування:



,

.



доведення здійснюється з урахуванням афінного шифру



.


У вказаних шифрах вимога не виконується. Симетрія шифру заключається в тому, що ключі поліноміально легко зв’язані і один може бути легко визначени при знанні іншого.

Шифр „Підстановка в полі”









Розв’язок можна звести до розв’язку діафантового рівняння:



.



Таким чином:



.

.



Нехай , таким чином поліном :



	.

	

Як правило, таке перетворення використовується як табличне. Воно здійснюється без ключа, ключем може бути тільки примітивний поліном.