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

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


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


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


- Мі
→ Сj
– ? ;


- Kij
→ Мі
→ Сj
– ?


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


Мі
→ Сj
; Kij
– ?


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


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






Мі →






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


Kij


→ Сj



(Мі
, Сj
) → Kij
– ?


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






Сj →






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


Kij


→ Мі

(Сj
, Мі
) → Kij


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


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


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


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


.


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




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


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



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


,


.


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


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



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



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


,


,


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


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


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


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


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


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


.


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 входить в показник:


.


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



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


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


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


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


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


1) афінні:


,


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


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


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


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


- гамування;


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


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


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


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


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



,


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


.


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


,


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


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


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


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


.


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


.


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











А В
ХА
ХВ

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



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


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


,


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


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


.


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


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


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


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


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



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


, де .


,


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


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


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


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


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


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


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


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




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


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


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


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


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




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



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

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



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


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


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


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


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


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


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


Мi , Kj ,






Рис 1

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



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


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

Приклад:



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


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


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


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


,


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


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


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


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


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


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


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


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


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


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


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


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


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


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


Афінний шифр


Твердження 1


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


,


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


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


,


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


,


де


,


.


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


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


Твердження 2


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


,


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


.


Твердження 3


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


,


.


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


.


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


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




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


.


Таким чином:


.


.


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


.


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

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

Название реферата: Криптосистеми

Слов:1550
Символов:14604
Размер:28.52 Кб.