Класифікація криптоалгоритмів
| {{{img}}} | ||
| Імя | Тарас | |
| Прізвище | Куриляк | |
| По-батькові | Тарасович | |
| Факультет | ФІС | |
| Група | СНсп-43 | |
| Залікова книжка | № ПК 08-108 | |
Криптографічний алгоритм, або шифр - це математична формула, що описує процеси шифрування і розшифрування. Щоб зашифрувати відкритий текст, криптоалгоритм працює в сполученні з ключем - словом, числом або фразою.
Криптографічних алгоритмів існує безліч. Їх призначення в загальних рисах зрозуміло: захист інформації. Захищати ж інформацію потрібно від різних загроз і різними способами. Щоб правильно задіяти криптоалгоритм (КА), тобто забезпечити надійний і адекватний захист, потрібно розуміти, які бувають КА і який тип алгоритму краще пристосований для вирішення конкретного завдання.
Зміст
Основна схема класифікації криптоалгоритмів
1. Тайнопис. Відправник і одержувач роблять над повідомленням перетворення, відомі лише їм двом. Стороннім особам невідомий сам алгоритм шифрування. Деякі фахівці вважають, що тайнопис не є криптографією взагалі.
2. Криптографія з ключем. Алгоритм впливу на передані дані відомий усім стороннім особам, але він залежить від деякого параметра - "ключа", яким володіють лише відправник і одержувач.
- Симетричні криптоалгоритми. Для зашифровки і розшифровки повідомлення використовується один і той же блок інформації (ключ).
- Асиметричні криптоалгоритми. Алгоритм такий, що для зашифровки повідомлення використовується один ( "відкритий") ключ, відомий усім бажаючим, а для розшифровки - інший ( "закритий"), який існує тільки в одержувача.
В залежності від кількості ключів, які застосовуються у конкретному алгоритмі:
- Безключові КА – не використовують в обчисленнях ніяких ключів;
- Одноключові КА – працюють з одним додатковим ключовим параметром (якимсь таємним ключем);
- Двухключові КА – на різних стадіях роботи в них застосовуються два ключових параметри: секретний та відкритий ключі.
В задежності від характеру впливів, що виробляються над даними, алгоритми підрозділяються на:
- Перестановочні - Блоки інформації (байти, біти, більші одиниці) не змінюються самі по собі, але змінюється їх порядок проходження, що робить інформацію недоступною сторонньому спостерігачеві.
- Підстановочні - Самі блоки інформації змінюються за законами криптоалгоритму. Переважна більшість сучасних алгоритмів належить цій групі.
Залежно від розміру блоку інформації криптоалгоритми поділяються на:
- Потокові шифри - Одиницею кодування є один біт. Результат кодування не залежить від минулого раніше вхідного потоку. Схема застосовується в системах передачі потоків інформації, тобто в тих випадках, коли передача інформації починається і закінчується в довільні моменти часу і може випадково перериватися. Найбільш поширеними представниками потокових шифрів являються скремблери.
- Блочні шифри - Одиницею кодування є блок з декількох байтів (в даний час 4-32). Результат кодування залежить від усіх вихідних байтів цього блоку. Схема застосовується при пакетній передачі інформації та кодування файлів.
Симетричні криптоалгоритми
Симетричні криптосистеми – спосіб шифрування, в якому для шифрування і дешифрування застосовується один і той же криптографічний ключ. До винаходу схеми асиметричного шифрування єдиним існуючим способом було симетричне шифрування. Ключ алгоритму повинен зберігатися в секреті обома сторонами.
Алгоритми шифрування і дешифрування даних широко застосовуються в комп'ютерній техніці в системах приховування конфіденційної і комерційної інформації від не коректного використання сторонніми особами. Головним принципом у них є умова, що особа яка приймає повідомлення, заздалегідь знає алгоритм шифрування, а також ключ до повідомлення, без якого інформація є всього лише набір символів, що не мають сенсу.
Симетричні криптоалгоритми виконують перетворення невеликого (1 біт або 32-128 біт) блоку даних в залежності від ключа таким чином, що прочитати оригінал повідомлення можна тільки знаючи цей секретний ключ
Потокові шифри
Головною відмінною рисою потокових шифрів є побітна обробка інформації. Як наслідок, шифрування і дешифрування в таких схемах може обриватися в довільний момент часу, як тільки з'ясовується, що потік що передається перервався, і також відновлюється при виявленні факту продовження передачі. Подібна обробка інформації може бути представлена у вигляді автомата, який на кожному своєму такті:
- генерує за будь-яким законом один біт шифрувальної послідовності;
- яким-небудь оборотним перетворенням накладає на один біт відкритого потоку даний шифрувальний біт, отримуючи зашифрований біт.
Всі сучасні потокові шифри діють за даною схемою. Біт шифрування, що виникає на кожному новому кроці автомата, як втім і цілий набір таких біт, прийнято позначати символом γ (гамма), а самі потокові шифри отримали через це друга назва - шифри гамування.
Шифри гамування набагато швидші за своїх найближчих конкурентів - блокових шифрів - у тому випадку, якщо потокове шифрування реалізується апаратно. Як ми побачимо, базові схеми шифрів гамування влаштовані просто i як би "самі просяться" в апаратну реалізацію - це й не дивно, якщо взяти до уваги історію та основну мету їх створення. У тих же випадках, коли з яких-небудь причин дані алгоритми реалізовані програмно, їх швидкість порівняна з блочними шифрами, а іноді і набагато нижче за них.
Трьома основними компонентами, над якими обчислюється функція, що породжує гаму, є:
- ключ;
- номер поточного кроку шифрування;
- прилеглі від поточної позиції біти вихідного і / або зашифрованого тексту.
Ключ є необхідною частиною гаммуючого шифру. Якщо ключ і схема породження гами не є секретним, то поточний шифр перетворюється на звичайний перетворювач-кодер - скремблер (від англ. Scramble - перемішувати, збивати).
Блочні шифри
На сьогоднішній день розроблено досить багато стійких блокових шифрів. Практично всі алгоритми використовують для перетворень певний набір бієктивних (оборотних) математичних перетворень.
Характерною особливістю блокових криптоалгоритмів є той факт, що в ході своєї роботи вони виробляють перетворення блоку вхідної інформації фіксованої довжини і отримують результуючий блок того ж обсягу, але недоступний для прочитання стороннім особам, що не володіють ключем.
Блочні шифри є основою, на якій реалізовані практично всі криптосистеми. Методика створення ланцюжків із зашифрованих блочними алгоритмами байт дозволяє шифрувати ними пакети інформації необмеженої довжини. Таку властивість блокових шифрів, як швидкість роботи, використовується асиметричними криптоалгоритмами, повільними за своєю природою. Відсутність статистичної кореляції між бітами вихідного потоку блочного шифру використовується для обчислення контрольних сум пакетів даних і в хешуванні паролів.
Криптоалгоритм іменується ідеально стійким, якщо прочитати зашифрований блок даних можна тільки перебравши всі можливі ключі, до тих пір, поки повідомлення не виявиться осмисленим. Так як по теорії ймовірності шуканий ключ буде знайдено з ймовірністю 1/2 після перебору половини всіх ключів, то на злом ідеально стійкого криптоалгоритму з ключем довжини N потрібно в середньому [math]2^{N-1}[/math] перевірок. Таким чином, у загальному випадку стійкість блочного шифру залежить тільки від довжини ключа і зростає експоненціально з її зростанням. Навіть припустивши, що перебір ключів проводиться на спеціально створеній багатопроцесорної системі, в якій завдяки діагональному паралелізму на перевірку 1 ключа йде тільки 1 такт, то на злом 128 бітного ключа сучасній техніці буде потрібно не менше [math]10^{21}[/math] років. Звичайно, все сказане стосується тільки ідеально стійких шифрів.
Архівація
Архівація (стиснення даних) - це процес подання інформації в іншому вигляді (перекодування) з потенційним зменшенням обсягу, необхідного для її зберігання. Існує безліч класів різних алгоритмів стиснення даних, кожен з яких орієнтований на свою область застосування.
Всі алгоритми стиснення даних якісно діляться на:
- алгоритми стиснення без втрат, при використанні яких дані на виході відновлюються без найменших змін.
- алгоритми стиснення з втратами, які видаляють з потоку даних інформацію, незначно впливає на суть даних, або взагалі не сприймається людиною (такі алгоритми зараз розроблені тільки для аудіо, відео та зображень). У криптосистемах, звичайно, використовується тільки перша група алгоритмів.
Існує два основні методи архівації без втрат:
- алгоритм Гоффмана (англ. Huffman), орієнтований на стиск послідовностей байт, не пов'язаних між собою,
- алгоритм Лемпеля-Зіва (англ. Lempel, Ziv), орієнтований на стиск будь-яких видів текстів, тобто використовує факт неодноразового повторення "слів" - послідовностей байт.
Практично всі популярні програми архівації без втрат (ARJ, RAR, ZIP тощо) використовують поєднання цих двох методів - алгоритм LZH.
Хешування паролів
Для того, щоб не змушувати людину запам'ятовувати ключ - довгу послідовність цифр, були розроблені методи перетворення рядка символів будь-якої довжини (так званого пароля) в блок байт заздалегідь заданого розміру (ключ). На алгоритми, що використовуються в цих методах, накладаються вимоги, які можна порівняти з вимогами самих криптоалгоритмів.
Від методів, що підвищують крипостійкість системи в цілому, перейдемо до блоку хешування паролів - методу, що дозволяє користувачам запам'ятовувати не 128 байт, тобто 256 шістнадцяткові цифр ключа, а деякий осмислений вираз, слово або послідовність символів, що називається паролем. Дійсно, при розробці будь-якого криптоалгоритму слід враховувати, що в половині випадків кінцевим користувачем системи є людина, а не автоматична система. Це ставить питання про те, чи зручно і взагалі чи реально людині запам'ятати 128-бітний ключ (32 шістнадцяткові цифри).
Насправді межа запам’ятовуваності лежить на межах 8-12 подібних символів, а, отже, якщо ми будемо примушувати користувача оперувати саме ключем, тим самим ми практично змусимо його до запису ключа на якому-небудь листку паперу або електронному носії, наприклад, у текстовому файлі. Це, звичайно, різко знижує захищеність системи.
Для вирішення цієї проблеми були розроблені методи, що перетворюють осмислений рядок довільної довжини - пароль, у вказаний ключ заздалегідь заданої довжини.
Цей метод і використовується в різних варіаціях практично у всіх сучасних криптосистемах. Матеріал рядка-пароля багаторазово послідовно використовується як ключ для шифрування деякого заздалегідь відомого блоку даних - на виході виходить зашифрований блок інформації, однозначно залежить тільки від пароля і при цьому має досить гарні статистичні характеристики. Такий блок або кілька таких блоків і використовуються як ключ для подальших криптоперетворень.
Транспортне кодування
У деяких системах передачі інформації потрібно, щоб потік містив лише певні символи ASCII кодів. Однак, вихідний потік криптоалгоритму має дуже високу рандомізацію і в ньому зустрічаються з однаковою ймовірністю всі 256 символів. Для подолання цієї проблеми використовується транспортне кодування.
Оскільки системи шифрування даних часто використовуються для кодування текстової інформації: листування, рахунків, платежів електронної комерції, і при цьому криптосистема повинна бути абсолютно прозорою для користувача, то над вихідним потоком криптосистеми часто проводиться транспортне кодування, то є додаткове кодування (не шифрування!) Інформації виключно для забезпечення сумісності з протоколами передачі даних.
Вся справа в тому, що на виході криптосистеми, байт може приймати всі 256 можливих значень, незалежно від того чи був вхідний потік текстовою інформацією чи ні. А при передачі поштових повідомлень багато систем орієнтовані на те, що допустимі значення байтів тексту лежать в більш вузькому діапазоні: всі цифри, знаки пунктуації, абетка латиниці плюс, можливо, національної мови. Перші 32 символи набору ASCII служать для спеціальних цілей. Для того, щоб вони і деякі інші службові символи ніколи не з'явилися у вихідному потоці використовується транспортне кодування.
Порівняння з асиметричними криптосистемами
В основному, симетричні алгоритми шифрування вимагають менше обчислень, ніж асиметричні. На практиці, це означає, що якісні асиметричні алгоритми в сотні або в тисячі разів повільніші за якісні симетричні алгоритми. Недоліком симетричних алгоритмів є необхідність мати секретний ключ з обох боків передачі інформації. Так як ключі є предметом можливого перехоплення, їх необхідно часто змінювати та передавати по безпечних каналах передачі інформації під час розповсюдження.
Переваги:
- Швидкість (за даними Applied Cryptography - на 3 порядки вище);
- Простота реалізації (за рахунок більш простих операцій);
- Менша необхідна довжина ключа для порівнянної стійкості;
- Вивченість (за рахунок більшого віку).
Недоліки:
- Складність управління ключами у великій мережі. Це означає квадратичне зростання числа пар ключів, які треба генерувати, передавати, зберігати і знищувати в мережі. Для мережі в 10 абонентів потрібно 45 ключів, для 100 вже 4950, для 1000 - 499500 і т. д.
- Складність обміну ключами. Для застосування необхідно вирішити проблему надійної передачі ключів кожному абоненту, тому що потрібен секретний канал для передачі кожного ключа обом сторонам.
Для компенсації недоліків симетричного шифрування в даний час широко застосовується комбінована (гібридна) криптографічний схема, де за допомогою асиметричного шифрування передається сеансовий ключ, що використовується сторонами для обміну даними за допомогою симетричного шифрування.
Важливою властивістю симетричних шифрів є неможливість їх використання для підтвердження авторства, так як ключ відомий кожній стороні.
Асиметричні алгоритми
Асиметричні алгоритми шифрування – алгоритми шифрування, які використовують різні ключі для шифрування та розшифрування даних.
Головне досягнення асиметричного шифрування в тому, що воно дозволяє людям, що не мають існуючої домовленості про безпеку, обмінюватися секретними повідомленнями. Необхідність відправникові й одержувачеві погоджувати таємний ключ по спеціальному захищеному каналі цілком відпала.
Алгоритм RSA
Алгоритми RSA є класикою асиметричної криптографії. У ньому в якості необоротного перетворення відправки використовується зведення цілих чисел у великі ступеня за модулем.
Алгоритм RSA стоїть біля витоків асиметричної криптографії. Він був запропонований трьома дослідниками –математиками: Рональдом Рівестом (R. Rivest), Аді Шамір (A. Shamir) та Леонардом Адльманом (L. Adleman) в 1977-78 роках.
Першим етапом будь-якого асиметричного алгоритму є створення пари ключів: відкритого та закритого, та поширення відкритого ключа "по всьому світу".
Насправді операції зведення в ступінь великих чисел досить трудомісткі для сучасних процесорів, навіть якщо вони проводяться за оптимізованими за часом алгоритмами. Тому зазвичай весь текст повідомлення кодується звичайним блоковим шифром (набагато більш швидким), але з використанням ключа сеансу, а от сам ключ сеансу шифрується якраз асиметричним алгоритмом за допомогою відкритого ключа одержувача і поміщається в початок файлу.
Електроний цифровий підпис
Як виявилося, теорія асиметричного шифрування дозволяє дуже красиво вирішувати ще одну проблему інформаційної безпеки - перевірку справжності автора повідомлення. Для вирішення цієї проблеми за допомогою симетричної криптографії була розроблена дуже трудомістка і складна схема. У той же час за допомогою, наприклад, того ж алгоритму RSA створити алгоритм перевірки дійсності автора та незмінності повідомлення надзвичайно просто.
Припустимо, що нам потрібно передати який-небудь текст, не обов'язково секретний, але важливо те, щоб у нього при передачі по незахищеному каналу не були внесені зміни. До таких текстів зазвичай відносяться різні розпорядження, довідки, і тому подібна документація, яка не представляє секрету. Обчислимо від нашого тексту будь-яку хеш-функцію - це буде число, яке більш-менш унікально характеризує даний текст.
У принципі, можна знайти інший текст, який дає те ж саме значення хеш-функції, але змінити в нашому тексті десять-двадцять байт так, щоб текст залишився повністю осмисленим, та ще й змінився в вигідну нам сторону (наприклад, зменшив суму до оплати в два рази) - надзвичайно складно. Саме для усунення цієї можливості хеш-функції створюють такими ж складними як і криптоалгоритми - якщо текст з таким же значенням хеш-функції можна буде підібрати тільки методом повного перебору, а безліч значень становитиме як і для блокових шифрів [math]2^{32}-2^{128}[/math] можливих варіантів, то для пошуку подібного тексту зловмисникові "потрібні" ті ж самі мільйони років.
Механізм розповсюдження відкритих ключів
Здавалося б, асиметричні криптосистеми позбавлені одного з найголовніших недоліків симетричних алгоритмів - необхідності попереднього обміну сторонами секретним ключем по захищеною схемою (наприклад, з рук в руки чи за допомогою повіреного кур'єра). Начебто достатньо "розтрубити" по всьому світу про свій відкритий ключ, і ось готова надійна лінія передачі повідомлень.
Але виявляється не все так просто: припустимо я Ваш потенційний співрозмовник. Для того, щоб відправити зашифроване повідомлення, я повинен дізнатися ваш відкритий ключ. Якщо Ви не приносили мені його особисто на дискеті, значить я його просто взяв з інформаційної мережі. А тепер головне питання: де доказ, що даний набір байт є саме Вашим відкритим ключем? Адже зловмисник може згенерувати довільну пару (закритий ключ, відкритий ключ), потім активно розповсюджувати або пасивно підміняти при запиті Ваш відкритий ключ створеним ним. У цьому випадку при відправленні повідомлення 1) я зашифрую його тим ключем, який думаю, що є Вашим, 2) зловмисник, перехопивши повідомлення дешифрує його парним закритим ключем, прочитає і більше того: 3) може переслати далі, зашифрувавши дійсно вже Вашим відкритим ключем .
Таким чином, якщо між відправником і одержувачем немає конфіденційної схеми передачі асиметричних ключів, то виникає серйозна небезпека появи зловмисника-посередника.
Але асиметрична криптографія знайшла витончений спосіб дуже значного зниження ризику подібної атаки. Якщо замислитися, то неправильно говорити, що між Вами і Вашим співрозмовником немає гарантованої лінії зв'язку. Наприклад, можна надіслати цей відкритий ключ, підписавши повідомлення своїм електронним підписом.
На сьогоднішній день не існує єдиної мережі розповсюдження відкритих ключів, і справа, як це часто буває, полягає у війні стандартів. Розвиваються кілька незалежних систем, але жодна з них не отримала значної переваги над іншими, який називається "світовим стандартом".
