Главная Учебники - Разные Лекции (разные) - часть 33
Криптосистеми 1. ОБЧИСЛЮВАЛЬНО СТІЙКІ ТА ЙМОВІРНО СТІЙКІ КРИПТОСИСТЕМИ Криптоаналітик знає криптиосистему, може мати апаратуру, може перехоплювати криптограми. При цьому, криптоаналітик може визначити: - Мі
→ Сj
– ? ; - Kij
→ Мі
→ Сj
– ? Атака при відомих парах повідомлень та криптограм Мі
→ Сj
; Kij
– ? Атака з вибором повідомлення Криптоаналітик знає Мі
та алгоритм зашифровування Мі → Kij → Сj (Мі
, Сj
) → Kij
– ? Атака з вибором криптограм Сj → Kij (Сj
, Мі
) → Kij
Адаптивна атака Така атака, при якій може здійснюватись зашифровування та розшифровування Визначення обчислювально стійкої криптосистеми та умови реалізації Обчислювально стійка криптосистема визначається як така, у якої Така система може будуватись як і безумовно стійка криптосистема. У обчислювально стійких криптосистемах замість ключової послідовності Кi
використовують Гi
. Процес – процес гамаутворення (шифроутворення). Розшифровування здійснюється аналогічно з безумовно стійкою криптосистемою: Ключ повинен породжуватись рівно ймовірно, випадково та незалежно. Як правило, більшість пристроїв працюють з бітами. Функція Ψ, для забезпечення необхідного рівня стійкості, повинна задовольняти ряду складних умов: 1) Період повторення повинен бути не менше допустимої величини: 2)Закон формування гами повинен забезпечувати „секретність” гами. Тобто, Гі
повинна протистояти криптоаналітику В якості показника оцінки складності гами використовується структурна скритність: де 3)Відновлюваність гами в просторі та часі. 4) Відсутність колізії, тобто, співпадання відрізків гами. Розглянута система відноситься до класу симетричних. В якості оцінки стійкості використовується така множина параметрів 1. 2. 3. Безпечний час для атаки типу „груба сила”: 4. Відстань єдності шифру де l – довжина зашифрованого тексту або гами; d – збитковість мови (під надмірністю d розуміється ступінь корельованості (залежності) символів у мові і не порівняно ймовірностні їхньої появи в повідомленні); m – розмірність алфавіту. Криптоаналіз вважається успішним, якщо Фізичний зміст 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 , Розшифрування: При обчисленні необхідно строго синхронізувати по i, тобто: Гi при розшифруванні і зашифруванні та сама. Приклад: Гi повинна породжуватися псевдовипадковим чи випадковим процесом. Реалізація процесу повинна залежати від вихідного ключа. Правильне розшифрування виконується за умови, що відправник і одержувач використовують той самий ключ, вони можуть сформувати однакові гами. Необхідно забезпечити синхронізацію по i. Симетричні криптоперетворення, якщо або: або можуть бути обчислені один при знанні іншого не нижче ніж з поліноміальною складністю. Симетричні шифри діляться на блокові та потокові шифри. Блокові симетричні шифри використовуються в чотирьох режимах роботи: 1)блокового шифрування; 2)потокового шифрування; 3)потокового шифрування зі зворотнім зв’язком по криптограмі; 4)вироблення імітоприкладки; 5)вироблення псевдопослідовностей (ключів). Побудування таких шифрів здійснюється на використані декількох елементарних табличних або криптографічних перетворень. До них відносяться: - афінні перетворення; - перетворення типу підстановка (перестановка) символів; - гамування (складання з ключем); - аналітичної підстановки (заміни). Основні криптоперетворення симетричного типу Афінний шифр Твердження 1 Нехай якщо найменший спільний дільник В афінному шифрі зашифровування здійснюється таким чином: а розшифровування: де Цей шифр є однозначно зворотнім. Лінійний шифр Твердження 2 Якщо в афінному шифрі а розшифровування: Твердження 3 Якщо в афінному шифрі доведення здійснюється з урахуванням афінного шифру У вказаних шифрах вимога не виконується. Симетрія шифру заключається в тому, що ключі поліноміально легко зв’язані і один може бути легко визначени при знанні іншого. Шифр „Підстановка в полі” Розв’язок можна звести до розв’язку діафантового рівняння: Таким чином: Нехай Як правило, таке перетворення використовується як табличне. Воно здійснюється без ключа, ключем може бути тільки примітивний поліном.
|