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

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

1. ОБЧИСЛЮВАЛЬНО СТІЙКІ ТА ЙМОВІРНО СТІЙКІ КРИПТОСИСТЕМИ Криптоаналітик знає криптиосистему, може мати апаратуру, може перехоплювати криптограми. При цьому, криптоаналітик може визначити:

— М_і > С_j —? ;

— K_ij > М_і > С_j — ?

Атака при відомих парах повідомлень та криптограм М_і > С_j; K_ij — ?

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

(М_і, С_j) > K_ij — ?

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

(С_j, М_і) > K_ij

Адаптивна атака Така атака, при якій може здійснюватись зашифровування та розшифровування Визначення обчислювально стійкої криптосистеми та умови реалізації

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

.

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

.

1. =128, 192, 256, 512

.

2. біт.

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

.

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

q — поле.

2. МАТЕМАТИЧНІ МОДЕЛІ КРИПТОПЕРЕТВОРЕНЬ Криптоперетворення розподіляються на:

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

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

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

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

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

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

.

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

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

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

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

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

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

1) афінні:

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

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

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

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

— гамування;

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

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

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

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

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

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

.

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

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

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

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

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

.

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

.

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

де Х_А, Х_В — випадкові ключі довжиною l_k;

Y_А, Y_В — відкриті ключі.

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

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

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

.

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

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

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

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

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

де .

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

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

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

3. СИМЕТРИЧНІ КРИПТОПЕРЕТВОРЕННЯ Застосовувані на практиці криптоперетворення розділяють на 2 класи по стійкості:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мi, j ,

Рис 1

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

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

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

Приклад:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основні криптоперетворення симетричного типу Афінний шифр Твердження 1

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

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

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

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

де

.

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

Лінійний шифр Твердження 2

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

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

.

Твердження 3

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

.

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

.

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

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

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

.

Таким чином:

.

.

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

.

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