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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

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

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вар – кількість команд, операцій для рішення задачі криптоаналізу.

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

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

,

.

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

.

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

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

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

.

Таким чином:

.

.

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

.

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

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Реферат
59.7кб. | скачати


Схожі роботи:
Криптографія та криптосистеми
Сучасні симетричні і асиметричні криптосистеми
© Усі права захищені
написати до нас
Рейтинг@Mail.ru