ДонНТУ   Портал магістрів

Реферат за темою випускної роботи

Зміст

Введення

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

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

Механізм хешування відомий вже достатню кількість часу, проте сам термін хешування з'явився в друкованих виданнях не так давно, в 1967 р. [1]. За словами Дональда Кнута [2], вперше ідея і принципи хешування були озвучені Г.П. Ланом в 1953 р. на внутрішньому меморандумі IBM. Для вирішення колізій хеш-адрес він запропонував використовувати метод ланцюжків. Жіні Амдал — інший співробітник IBM — запропонувала використовувати відкриту лінійну адресацію. Арнольд Думі в 1956 р. вперше описав хешування у відкритій пресі. Він запропонував використовувати як хеш-адреси залишок від ділення на просте число. Набагато більш ґрунтовне дослідження хеш-функцій було опубліковано в 1963 р. Вернером Букхольцом [3].

1. Актуальність теми

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

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

2. Мета і завдання дослідження

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

Основні завдання дослідження:

  1. Аналіз існуючих криптографічних алгоритмів.
  2. Вивчення методів SAT Solvers.
  3. Розробка алгоритму криптоаналізу.

Об'єктом дослідження є алгоритми шифрування даних.

Предметом дослідження є способи оптимізації алгоритмів шифрування даних.

3. Передбачувана наукова новизна

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

4. Огляд існуючих криптографічних алгоритмів

За класифікацією, наданою С. Панасенко [4], криптографічні алгоритми поділяються на безключеві, одноключеві і двохключові.

Безключові — не використовують будь-яких ключів в процесі криптографічних перетворень.

Одноключові — використовують у своїх обчисленнях якийсь секретний ключ.

Двохключові — на різних етапах обчислень застосовуються два види ключів: секретні та відкриті.

Більш детальна класифікація показана на малюнку 1.

Класифікація криптографічних алгоритмів

Рисунок 1 — Класифікація криптографічних алгоритмів

Деякі з алгоритмів розглянуті нижче.

4.1 Генератори випадкових чисел

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

В ідеалі випадкові числа повинні ґрунтуватися на справжньому фізичному джерелі випадкової інформації, яку неможливо передбачити. Приклади таких джерел включають шумливі напівпровідникові прилади, молодші біти оцифрованого звуку, інтервали між перериваннями пристроїв або натисканнями клавіш. Отриманий від фізичного джерела шум потім „дистилюється“ криптографічного хеш-функцією так, щоб кожен біт залежав від кожного біта. Досить часто для зберігання випадкової інформації використовується досить великий пул (кілька тисяч біт) і кожен біт пулу робиться залежним від кожного біта шумової інформації і кожного іншого біта пулу криптографически надійним (strong) способом.

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

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

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

4.2 Алгоритми симетричного шифрування

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

В даний час є цілий ряд алгоритмів симетричного шифрування. Серед них відзначимо DES (Data Encryption Standard — стандарт шифрування даних), IDEA (International Data Encryption Algorithm — міжнародний алгоритм шифрування даних) — патентований алгоритм, вживаний в PGP, і Blowfish — непатентований алгоритм, вживаний в SSH.

З алгоритмами симетричного шифрування пов'язане поняття стійкості шифру. Стійкість — це міра опору криптоаналітичнимї атакам. Стійкість алгоритму визначається розміром використовуваного ключа. В IDEA застосовуються 128-разрядні ключі. В алгоритмі Blowfish розмір ключа конфігурується від 32 до 448 біт. Чим довше ключ, тим більш стійкий шифр. У DES використовуються 56-разрядні ключі, тому даний алгоритм вважається відносно слабким.

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

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

4.3 Алгоритми асиметричного шифрування

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

Алгоритми асиметричного шифрування виникли у зв'язку з необхідністю передавати секретні ключі по незахищених каналах. Першу систему такого роду розробив Ральф Меркле (Ralph Merkle) в 1974 році. Першим алгоритмом, який завоював широку популярність, був алгоритм Діффі-Хеллмана, створений Уітфілдом Діффі (Whitfield Diffie) і Мартіном Хеллманом (Martin Hellman) в 1976 році. У 1977 році Рон Рівест (Ron Rivest), Аді Шамір (Adi Shamir) і Лен Ейдельман (Len Adleman) розробили схожий алгоритм RSA.

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

4.3.1 Шифрування з закритим ключем

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

Найбільш широко використовуваним алгоритмом з закритим ключем є стандарт Data Encryption Standard (DES). Цей алгоритм, розроблений компанією IBM в сімдесятих роках минулого століття, прийнятий в якості американського стандарту для комерційних і несекретних урядових комунікацій. Сучасні швидкості обчислень на порядок перевищують швидкості обчислень в сімдесятих роках, тому алгоритм DES вважається застарілим як мінімум з 1998 року.

Інші відомі системи шифрування із закритим ключем — це RC2, RC4, RC5, потрійний DES (triple DES) і IDEA. Потрійний DES-алгоритм забезпечує достатню ступінь захисту. Цей алгоритм використовує той же метод шифрування, що і DES, але застосовує його тричі, використовуючи при цьому до трьох різних ключів. Відкритий текст шифрується з використанням першого ключа, дешифрується за допомогою другого ключа, а потім шифрується із застосуванням третього ключа.

Схема алгоритму шифрування з закритим ключем

Рисунок 2 — Схема алгоритму шифрування з закритим ключем (анімація, 16 кадрів, 5 повторень, 54,1 КБ)

Умовні позначення:
     М — повідомлення;
     Н (М) — хешування повідомлення;
     Е — електронний цифровий підпис;
     К — секретний ключ;
     МЕ — не зашифроване повідомлення з ЕЦП;
     МЕК — зашифроване повідомлення з ЕЦП;

Явний недолік алгоритмів з закритим ключем полягає в тому, що для відправки комусь захищеного повідомлення необхідно володіти безпечним способом передачі цій особі закритого ключа [7].

4.3.2 Шифрування з відкритим ключем

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

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

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

Алгоритми шифрування з відкритим ключем використовують так звані необоротні чи односторонні функції. Ці функції мають наступну властивість: при заданому значенні аргументу х відносно просто обчислити значення функції (X), однак, якщо відомо значення функції y = f (x), то немає простого шляху для обчислення значення аргументу x. Наприклад, функція SIN. Знаючи x, легко знайти значення SIN (x) (Наприклад, x = π, тоді SIN (π) = 0). Однак, якщо SIN (x) = 0, однозначно визначити х можна, тому в цьому випадку х може бути будь-яким числом, що визначається за формулою i * π, де i — ціле число [8].

Висновки

Хешування, виникнення якого припало на середину ХХ століття, активно використовується і розвивається донині. Велике безліч розроблених алгоритмів обумовлено широким спектром їх застосування та необхідністю захисту величезної кількості різноманітних даних. За деяким думками, відкриття лінійного хешування Вітольдом Литвином [9] є найбільш важливим відкриттям з 1970х років. Лінійне хешування не має нічого спільного з класичною технологією лінійної адресації, що дозволяє багатьом хеш-адресам рости і виступати в полі елементів, що вставляються і видаляються. Лінійне хешування може також використовуватися для величезних баз даних, розподілених між різними вузлами в мережі.

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

Важливе зауваження

При написанні даного реферату магістерська робота ще не завершена. Остаточне завершення: грудень 2013 року. Повний текст роботи та матеріали по темі можуть бути отримані у автора або його керівника після вказаної дати.

Перелік джерел

  1. Hellerman H., Digital Computer System Principles. McGraw-Hill, 1967.
  2. Кнут Д., Искусство программирования, т.3. М.: Вильямс, 2000.
  3. Buchholz W., IBM Systems J., 2 (1963), 86–111
  4. Панасенко С.П., Алгоритмы шифрования. Специальный справочник. – СПб.: БХВ-Петербург, 2009, - 576 с.: ил.
  5. Введение в криптографию [Электронный ресурс]. – Режим доступа: http://algolist.manual.ru/defence/...
  6. Симметричное шифрование [Электронный ресурс]. – Режим доступа: http://www.open-security.org/linux/...
  7. Шифрование с закрытым ключом [Электронный ресурс]. – Режим доступа: http://sevidi.ru/phpstroy/...
  8. Шифрование с открытым ключом [Электронный ресурс]. – Режим доступа: https://sites.google.com/site/...
  9. Litwin W., Proc. 6th International Conf. on Very Large Databases (1980), 212-223