Криптосистеми (47497)

Посмотреть архив целиком




















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



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


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


- Мі → Сj – ? ;

- Kij → Мі → Сj – ?


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


Мі → Сj; Kij – ?


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

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


Мі →


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




Kij


Сj


і , Сj) → Kij – ?


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


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

Сj →




Kij

Мі


j , Мі) → Kij


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

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

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

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


.


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



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

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



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


,

.


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

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




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



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


,

,


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

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

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

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

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

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


.


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А, YВ – відкриті ключі.

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


,


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

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


.


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

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

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

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

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



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


, де .

,


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

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

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


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


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

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

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

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



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

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

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

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

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



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



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

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


Случайные файлы

Файл
14130.rtf
20064-1.rtf
101216.rtf
сов.doc
148019.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.