Сучасна криптографія

Вступ

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

Священні книги Стародавнього Єгипту, Стародавньої Індії тому приклади.

З широким поширенням писемності криптографія стала формуватися як самостійна наука. Перші криптосистеми зустрічаються вже на початку нашої ери. Так, Цезар у своєму листуванні використовував вже більш менш систематичний шифр, отримав його ім'я.

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

Чому проблема використання криптографічних методів у інформаційних системах (ІС) стала в зараз особливо актуальна?

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

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

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

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

Третя глава даної роботи розповідає про хеш-функціях і (методи) алгоритмах їх побудови.

У четвертій чолі буде розказано про модернізацію електронного підпису Ель Гамаля і задачі дискретного логарифмування.

Глава 1. Основні поняття сучасної криптографії

Проблемою захисту інформації шляхом її перетворення займається кріптологія (kryptos - таємний, logos - наука). Криптология розділяється на два напрямки -- криптографію і криптоаналіз. Мета цих напрямків прямо протилежні.

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

Сфера інтересів криптоаналізу - дослідження можливості розшифровки інформації без знання ключів.

У цій роботі основну увагу буде приділено криптографічних методів.

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

Симетричні криптосистеми.

Криптосистеми з відкритим ключем.

Системи електронного підпису.

Управління ключами.

Основні напрями використання криптографічних методів - передача конфіденційної інформації по каналах зв'язку (наприклад, електронна пошта), встановлення автентичності переданих повідомлень, зберігання інформації (документів, баз даних) на носіях в зашифрованому вигляді.

Криптографія дає можливість перетворити інформацію таким чином, що її прочитання (відновлення) можливе тільки при знанні ключа.

Як інформації, що підлягає шифрування і дешифруванню, будуть розглядатися тексти, побудовані на деякому алфавіті. Під цими термінами розуміється наступне.

Алфавіт -- кінцеве безліч використовуваних для кодування інформації знаків.

Текст -- упорядкований набір з елементів алфавіту.

Як прикладів алфавітів, що використовуються в сучасних ІС можна навести наступні:

алфавіт Z33 - 32 літери російського алфавіту і пробіл;

алфавіт Z256 - символи, що входять до стандартні коди ASCII і КОИ-8;

бінарний абетка - Z2 = (0,1);

вісімковій алфавіт або шістнадцятковий алфавіт;

Шифрування -- перетворювальні процес: вихідний текст, який носить також назву відкритого тексту, замінюється шифрованих текстом.

Дешифрування -- зворотний процес шифрування. На основі ключа зашифровані текст перетвориться в вихідний.

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

Криптографічний система являє собою сімейство T перетворень відкритого тексту. Члени цього сімейства індексуються, або позначаються символом k; параметр k є ключем. Простір ключів K - це набір можливих значень ключа. Зазвичай ключ представляє собою послідовний ряд букв алфавіту.

Криптосистеми розділяються на симетричні і з відкритим ключем.

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

У системах з відкритим ключем використовуються два ключі - відкритий і закритий, які математично пов'язані один з одним. Інформація шифрується за допомогою відкритого ключа, що доступний усім бажаючим, а розшифровується за допомогою закритого ключа, відомого тільки одержувачу повідомлення. Терміни розподіл ключів і керування ключами відносяться до процесам системи обробки інформації, змістом яких є складання та розподіл ключів між користувачами.

Електронної (цифровий) підписом називається що приєднуються до тексту його криптографічне перетворення, яке дозволяє при отриманні тексту іншим користувачем перевірити авторство і достовірність повідомлення.

криптостійкості називається характеристика шифру, що визначає його стійкість до дешифруванню без знання ключа (тобто криптоаналіз). Є декілька показників криптостійкості, серед яких:

кількість всіх можливих ключів;

середній час, необхідне для криптоаналізу.

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

Вимоги до криптосистемами

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

Для сучасних криптографічних систем захисту інформації сформульовані наступні загальноприйняті вимоги:

зашифроване повідомлення повинно піддаватися читання тільки при наявності ключа;

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

число операцій, необхідних для розшифрування інформації шляхом перебору всіляких ключів повинно мати строгу нижню оцінку і виходити за межі можливостей сучасних комп'ютерів (з урахуванням можливості використання мережевих обчислень);

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

незначне зміна ключа повинно приводити до істотної зміни виду зашифрованого повідомлення навіть при використанні одного і того ж ключа;

структурні елементи алгоритму шифрування повинні бути незмінними;

додаткові біти, що вводяться в повідомлення в процесі шифрування, повинен бути повністю та надійно сховані в зашифрованому тексті;

довжина шифрованого тексту повинна бути рівною довжині вихідного тексту;

не повинно бути простих і легко встановлюваних залежністю між ключами, послідовно використовуваними в процесі шифрування;

будь-який ключ з безлічі можливих повинен забезпечувати надійний захист інформації;

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

Глава 2. Протоколи розподілу криптографічних ключів та протоколи електронної підпису.

Системи з відкритим ключем .

Як би не були складні і надійні криптографічні системи - їх слабке місць при практичній реалізації - проблема розподілу ключів. Для того, щоб був можливий обмін конфіденційною інформацією між двома суб'єктами ІС, ключ повинен бути згенерований одним з них, а потім якимось чином знову ж таки в конфіденційному порядку переданий іншому. Тобто в загальному випадку для передачі ключа знову ж таки потрібне використання якийсь криптосистеми.

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

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

Оригінальний текст шифрується відкритим ключем одержувача і передається йому. Зашифрований текст у принципі не може бути розшифровано тим же відкритим

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

Криптографічні системи з відкритим ключем використовують так звані незворотні або односторонні функції, які мають наступну властивість: при заданому значенні x відносно просто обчислити значення f (x), однак якщо y = f (x), то немає простого шляху для обчислення значення x.

Безліч класів необоротних функцій і породжує все розмаїття систем з відкритим ключем. Проте не кожна необоротна функція годиться для використання в реальних ІС.

У самому визначенні незворотності присутня невизначеність. Під необоротністю розуміється не теоретична незворотність, а практична неможливість обчислити протилежне значення використовуючи сучасні обчислювальні засоби за осяжний інтервал часу. Тому щоб гарантувати надійний захист інформації, до систем з відкритим ключем (СОК) пред'являються два важливих і очевидних вимоги:

1. Перетворення вихідного тексту повинно бути незворотним і виключати його відновлення на основі відкритого ключа.

2. Визначення закритого ключа на основі відкритого також повинно бути неможливим на сучасному технологічному рівні. При цьому бажана точна нижня оцінка складності (кількості операцій) розкриття шифру.

Алгоритми шифрування з відкритим ключем одержали широке поширення в сучасних інформаційних системах. Так, алгоритм RSA став світовим стандартом де-факто для відкритих систем і рекомендований МККТТ.

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

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

Обчислення логарифма в кінцевому полі.

Обчислення коренів алгебраїчних рівнянь.

Алгоритм Диффи-Хеллмана .

Діффі і Хелман запропонували для створення криптографічних систем з відкритим ключем функцію дискретного піднесення до ступінь.

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

Якщо y = ax,, 1

Зворотній завдання обчислення x з y буде досить складною. Якщо p вибрано досить правильно, то витяг логарифма потребують обчислень, пропорційних

L (p) = exp ((ln p ln ln p) 0.5)

Для обміну інформацією першого користувач вибирає випадкове число x1, рівноймовірно з цілих 1 ,..., p-1. Це число він тримає в секреті, а іншому користувачеві посилає число

y1 = ax1 mod p

Аналогічно надходить і друга користувач, генеруючи x2 і обчисливши y2, відправляючи його першому користувачу.

У результаті цього вони можуть обчислювати k12 = ax1x2 mod p.

Для того, щоб обчислити k12, перший користувач зводить y2 до степеня x1. Те ж робить і другу користувач. Таким чином, в обох користувачів виявляється загальний ключ k12, який можна використовувати для шифрування інформації звичайними алгоритмами. На відміну від алгоритму RSA, даний алгоритм не дозволяє шифрувати власне інформацію.

Не знаючи x1 та x2, зловмисник може спробувати вирахувати k12, знаючи тільки перехоплені y1 і y2. Еквівалентність цієї проблеми проблеми обчислення дискретного логарифма є головний і відкритий питання в системах з відкритим ключем. Простого рішення до цього часу не знайдено. Так, якщо для прямого перетворення 1000-бітових простих чисел потрібно 2000 операцій, то для зворотного перетворення (обчислення логарифма в поле Галуа) - потрібно близько 1030 операцій.

Як видно, при всій простоті алгоритму Діффі-Хелман, його недоліком є відсутність гарантованої нижній оцінки трудомісткості розкриття ключа.

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

Як узагальнення сказаного про розподіл ключів слід сказати наступне. Завдання управління ключами зводиться до пошуку такого протоколу розподілу ключів, який забезпечував б:

можливість відмови від центру розподілу ключів;

взаємне підтвердження автентичності учасників сеансу;

підтвердження вірогідності сеансу механізмом запиту-відповіді,

використання для цього програмних або апаратних засобів;

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

Ієрархічні схеми розподілу ключів.

Розглянемо наступну задачу.

Нехай абоненти мережі зв'язку не рівноправні між собою, а розділені на "класи безпеки "C1, C2, ..., Cn. На безлічі цих класів визначено деякий частковий порядок; якщо Cj