Referat.me

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

Вид работы: реферат

Рубрика: Информатика и программирование

Размер файла: 75.95 Kb

Скачать файл: referat.me-139488.docx

Краткое описание работы: Визначення обчислювально стійкої криптосистеми, умови її реалізації, параметри оцінки стійкості. Імовірно стійка криптосистема. Математичні моделі асиметричних і симетричних криптоперетворень. Використання і побудування блокових і симетричних шифрів.

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

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


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А , 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

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

,

.

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

.


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

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

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

.

Таким чином:

.

.

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

.

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

Похожие работы

  • Системи автоматизованого проектування

    Організаційні основи розробки систем автоматизованого проектування на виробництві, їх впровадження і експлуатація. Загальні відомості про мікропроцесорні пристрої і системи. Основні поняття, визначення, постановка й розв’язок простих оптимізаційних задач.

  • Криптологія

    Створення математичної моделі інформаційної системи для надання користувачам інформації в використанні різних задач. Структурна схема захисту від зловмисних дій в системі. Класифікація криптоперетворень, умови реалізації безумовно стійких криптосистем.

  • Розробка автоматизованої інформаційної системи засобами табличного процесора EXCEL

    Визначення найкращої стратегії покупки при відомих і невідомих можливостях ринкової кон'юнктури. Макети таблиць "Анкета експертного опитування" та "Техніко-економічні показники проектів". Контрольні розрахунки кращого варіанта інвестиційного проекту.

  • Моделі та моделювання

    Модель – це прообраз, опис або зображення якогось об'єкту. Класифікація моделей за способом зображення. Математична модель. Інформаційна модель. Комп'ютерна модель. Етапи створення комп'ютерної моделі.

  • Криптографічні методи захисту інформації

    Основи безпеки даних в комп'ютерних системах. Розробка програми для забезпечення захисту інформації від несанкціонованого доступу: шифрування та дешифрування даних за допомогою криптографічних алгоритмів RSA та DES. Проблеми і перспективи криптографії.

  • Електронний цифровий підпис

    Вимоги до цифрового підпису. Використання хеш-функцій. Пристрої зберігання закритого ключа. Стандартні протоколи узгодження ключів. Підписування електронних документів різних форм: підпис в HTML-формі, записи в таблицях бази даних, файлів у форматі PDF.

  • Розробка імовірнісної моделі криптографічних протоколів

    Структура захищених систем і їх характеристики. Моделі елементів захищених систем. Оцінка стійкості криптографічних протоколів на основі імовірнісних моделей. Нормативно-правова база розробки, впровадження захищених систем.

  • Модель дослідження стійкості та якості перехідних процесів слідкувальної системи

    Задачі системного управління структурою і властивостями складних об'єктів. Аналіз вимог до точності та стійкості слідкувальної системи. Розробка алгоритмів визначення стійкості та якості перехідних процесів системи. Програмний комплекс системи.

  • Основи криптографії

    Криптографія як область знань щодо перетворення повідомлень у незрозумілу для сторонніх осіб форму, а також перевірки істинності цих повідомлень. Класифікація шифрів, принципи частотного криптоаналізу. Таблиця заміни при шифруванні, приклади шифрування.

  • Математичні функції в Excel. Запис макросів

    Основні математичні функції табличного процесора Excel, особливості та правила їх використання. Основи мови макросів, порядок їх запису та виконання. Поняття та характерні риси макрофункцій, їх призначення та правила використання в програмі Excel.