Криптографія 2
Криптогра́фія (від грецького kryptós — прихований і gráphein — писати) — наука про математичні методи забезпечення конфіденційності (неможливості прочитання інформації стороннім) і автентичності (цілісності і справжності авторства) інформації. Розвинулась з практичної потреби передавати важливі відомості найнадійнішим чином. Для математичного аналізу криптографія використовує інструментарій абстрактної алгебри.
Для сучасної криптографії характерне використання відкритих алгоритмів шифрування, що припускають використання обчислювальних засобів. Відомо більше десятка перевірених алгоритмів шифрування, які, при використанні ключа достатньої довжини і коректної реалізації алгоритму, роблять шифрований текст недоступним для криптоаналізу. Широко використовуються такі алгоритми шифрування як Twofish, IDEA, RC4 та ін.
Історія криптографії налічує близько 4 тисяч років. Як основний критерій періодизації криптографії можна взяти технологічні характеристики використовуваних методів шифрування. До нашого часу криптографія займалася виключно забезпеченням конфіденційності повідомлень (тобто шифруванням) — перетворенням повідомлень із зрозумілої форми в незрозумілу і зворотне відновлення на стороні одержувача, роблячи його неможливим для прочитання для того, хто перехопив або підслухав без секретного знання (а саме ключа, необхідного для дешифровки повідомлення). В останні десятиліття сфера застосування криптографії розширилася і включає не лише таємну передачу повідомлень, але і методи перевірки цілісності повідомлень, ідентифікування відправника/одержувача (аутентифікація), цифрові підписи, інтерактивні підтвердження, та технології безпечного спілкування тощо.
Найдавніші часи - Стародавній Рим
Найперші форми тайнопису вимагали не більше ніж аналог олівця та паперу, оскільки в ті часи більшість людей не могли читати. Поширення писемності, або писемності серед ворогів, викликало потребу саме в криптографії. Основними типами класичних шифрів є перестановочні шифри, які змінюють порядок літер в повідомленні, та підстановочні шифри, які систематично замінюють літери або групи літер іншими літерами або групами літер. Прості варіанти обох типів пропонували слабкий захист від досвідчених супротивників. Одним із ранніх підстановочних шифрів був шифр Цезаря, в якому кожна літера в повідомленні замінювалась літерою через декілька позицій із абетки. Цей шифр отримав ім'я Юлія Цезаря, який його використовував, зі зсувом в 3 позиції, для спілкування з генералами під час військових кампаній, подібно до коду EXCESS-3 в булевій алгебрі. Шляхом застосування шифрування намагаються зберегти зміст спілкування в таємниці, подібно до шпигунів, військових лідерів, та дипломатів. Зберіглися також відомості про деякі з ранніх єврейських шифрів. Застосування криптографії радиться в Камасутрі як спосіб спілкування закоханих без ризику незручного викриття. Стеганографія (тобто, приховування факту наявності повідомлення взагалі) також була розроблена в давні часи. Зокрема, Геродот приховав повідомлення — татуювання на поголеній голові раба — під новим волоссям. До сучасних прикладів стеганографії належать невидимі чорнила, мікрокрапки, цифрові водяні знаки, що застосовуються для приховування інформації.
Арабський період
Шифротексти, отримані від класичних шифрів (та деяких сучасних), завжди видають деяку статистичну інформацію про текст повідомлення, що може бути використано для зламу. Після відкриття частотного аналізу (можливо, арабським вченим аль-Кінді) в 9-тому столітті, майже всі такі шифри стали більш-менш легко зламними досвідченим фахівцем. Класичні шифри зберігли популярність, в основному, у вигляді головоломок.
Відродження
Майже всі шифри залишались беззахисними перед криптоаналізом з використанням частотного аналізу до винаходу поліалфавітного шифру, швидше за все, Леоном-Баттіста Альберті приблизно в 1467 році (хоча, існують свідчення того, що знання про такі шифри існували серед арабських вчених). Винахід Альберті полягав в тому, щоб використовувати різні шифри (наприклад, алфавіти підстановки) для різних частин повідомлення. Йому також належить винахід того, що може вважатись першим шифрувальним приладом: колесо, що частково реалізовувало його винахід.
Новий час
В поліалфавітному шифрі Віженера (англ. Vigenère cipher), алгоритм шифрування використовує ключове слово, яке керує підстановкою літер в залежності від того, яка літера ключового слова використовується. В середині 1800-тих, Чарльз Беббідж показав, що поліалфавітні шифри цього типу залишились частово беззахисними перед частотним аналізом.
19 століття
Хоча частотний аналіз є потужною та загальною технікою, шифрування, на практиці, часто було ефективним; багато із криптоаналітиків не знали цю техніку. Дешифрування повідомлень без частотного аналізу практично означало необхідність знання використаного шифру, спонукаючи, таким чином, до шпигунства, підкупу, крадіжок, зрад, тощо для отримання алгоритму. Згодом, в 19-тому столітті, було визнано, що збереження алгоритму шифрування в таємниці не забезпечує захист від зламу; насправді, було встановлено, що будь-яка адекватна криптографічна схема залишається у безпеці, навіть за умови доступу сторонніх. Збереження в таємниці ключа має бути достатньою умовою захисту інформації нормальним шифром. Цей фундаментальний принцип було вперше проголошено в 1883 Огюстом Керкгофсом, і загальновідомий як принцип Керкгоффза; різкіший варіант озвучив Клод Шеннон як максиму Шеннона — ворог знає систему. Було створено різні механічні прилади та інструменти для допомоги в шифруванні. Одним з найперших є скітала в стародавній Греції, палиця, що, як вважається, використовувалась Спартанцями в якості перестановочного шифру. В середньовіччя, було винайдено інші засоби, такі як дірочний шифр, що також використовувася для часткової стеганографії. Разом із винаходом поліалфавітних шифрів, було розроблено досконаліші засоби, такі як власний винахід Альберті шифрувальний диск, табула ректа Йогана Тритеміуса, та мультициліндр Томаса Джефферсона (повторно винайдений Базерієсом приблизно в 1900 році).
Початок 20-го століття
Декілька механічних шифрувально/дешифрувальних приладів було створено на початку 20-го століття і багато запатентовано, серед них роторні машини — найвідомішою серед них є Енігма, автомат, що використовувася Німеччиною з кінця 20-тих і до кінця Другої світової війни. Шифри, реалізовані прикладами покращених варіантів цих схем призвели до істотного підвищення криптоаналітичної складності після Другої світової війни...
Початок комп'ютерної ери
Поява цифрових комп'ютерів та електроніки після Другої світової війни зробило можливим появу складніших шифрів. Більше того, комп'ютери дозволяли шифрувати будь-які дані, які можна представити в комп'ютері у двійковому виді, на відміну від класичних шифрів, які розроблялись для шифрування письмових текстів. Це зробило непридатними для застосування лінгвістичні підходи в криптоаналізі. Багато комп'ютерних шифрів можна характеризувати за їхньою роботою з послідовностями бінарних бітів (інколи в блоках або групах), на відміну від класичних та механічних схем, які, зазвичай, працюють безпосередньо з літерами. Однак, комп'ютери також знайшли застосування у криптоаналізі, що, в певній мірі, компенсувало підвищення складності шифрів. Тим не менше, гарні сучасні шифри залшались попереду криптоаналізу; як правило, використання якісних шифрів дуже ефективне (тобто, швидке і вимагає небагато ресурсів), в той час як злам цих шифрів потребує набагато більших зусиль ніж раніше, що робить криптоаналіз настільки неефективним та непрактичним, що злам стає практично неможливим.
Асиметричні системи
Широкі академічні дослідження криптографії з'явились порівняно нещодавно — починаючи з середини 1970-тих, разом із появою відкритої специфікації стандарту DES (Data Encryption Standard) Національного Бюро Стандартів США, публікацій Діффі-Хелмана та оприлюдненням алгоритму RSA. Відтоді, криптографія перетворилась на загальнопоширений інструмент для передачі даних, в комп'ютерних мережах, та захисті інформації взагалі. Сучасний рівень безпеки багатьох криптографічних методів базується на складності деяких обчислювальних проблем, таких як розклад цілих чисел, або проблеми з дискретними логарифмами. В багатьох випадках, існують докази безпечності криптографічних методів лише за умови неможливості ефективного розв'язання певної обчислювальної проблеми. За одним суттєвим винятком — схема одноразових блокнотів. Разом із пам'яттю про історію криптографії, розробники криптографічних алгоритмів та систем також мають брати до уваги майбутній поступ технологій в своїх розробках. Наприклад, постійне підвищення обчислювальної потужності комп'ютерів розширило поле для атак грубої сили. Тому, відповідно і оновлюються стандарти в сенсі вибору довжини ключа. Можливі наслідки розвитку квантових комп'ютерів вже враховуються деякими розробниками криптографічних систем; анонсована поява малих реалізацій цих комп'ютерів робить важливою попередню підготовку. Взагалі кажучи, до початку 20-го століття, криптографія, в основному, була пов'язанна з лінгвістичними схемами. Після того, як основний акцент було зміщено, зараз криптографія інтенсивно використовує математичний апарат, включно з теорією інформації, теорією обчислювальної складності, статистики, комбінаторики, абстрактної алгебри та теорії чисел. Криптографія є також відгалуженням інженерії, але не звичним, оскільки вона має справу з активним, розумним та винахідливим супротивником; більшість інших видів інженерних наук мають справу з нейтральними силами природи. Існують дослідження з приводу взаємозв'язків між криптографічними проблемами та квантовою фізикою.
Захист даних з допомогою шифрування – одне з можливих рішень проблеми їхньої безпеки. Зашифровані дані стають доступними тільки для того, хто знає, як їх розшифрувати, і тому викрадення зашифрованих даних є абсолютно безглуздим для несанкціонованих користувачів. Коди і шифри використовувались задовго до появи ЕОМ. З теоретичного погляду не існує чіткої різниці між кодами і шифрами. Однак у сучасній практиці відмінність між ними, як правило, є достатньо чіткою. Коди оперують лінгвістичними елементами, поділяючи текст, що шифрується, на такі смислові елементи, як слова і склади. У шифрі завжди розрізняють два елементи: алгоритм і ключ.
Алгоритм дозволяє використати порівняно короткий ключ для шифрування наскільки завгодно великого тексту. Для захисту даних в ІС в основному використовуються шифри, тому далі мова піде саме про них. У цій главі будуть наведені основні корисні для практики концепції криптографічного захисту інформації, а також обговорені переваги і недоліки найбільш поширених засобів захисту.
Визначимо низку термінів, що використовуються у криптографії.
Гамування – процес накладення за певним законом гами шифру на відкриті дані. Під гамою шифру розуміється псевдовипадкова двійкова послідовність, що виробляється за заданим алгоритмом, для зашифровування відкритих даних і розшифрування зашифрованих даних.
Зашифровуванням даних називається процес перетворення відкритих даних на зашифровані з допомогою шифру, а розшифруванням даних – процес перетворення закритих даних на відкриті з допомогою шифру.
Шифруванням називається процес зашифровування або розшифрування даних.
Дешифруванням будемо називати процес перетворення закритих даних на відкриті при невідомому ключі і, можливо, невідомому алгоритмі.
Імітозахист – захист від нав'язування неправдивих даних. Для забезпечення імітозахисту до зашифрованих даних додається імітовставка, що являє собою послідовність даних фіксованої довжини, отриману за певним правилом з відкритих даних і ключа.
Ключ – конкретний таємний стан деяких параметрів алгоритму криптографічного перетворення даних, що забезпечує вибір одного варіанту із сукупності всіляких для даного алгоритму.
Криптографічний захист – це захист даних з допомогою криптографічного перетворення, під яким розуміється перетворення даних шифруванням і (або) виробленням імітовставки.
Синхропосилка – вхідні відкриті параметри алгоритму криптографічного перетворення.
Рівняння зашифровування – співвідношення, що описує процес утворення зашифрованих даних з відкритих даних у результаті перетворень, заданих алгоритмом криптографічного перетворення.
Під шифром розуміється сукупність зворотних перетворень безлічі відкритих даних на безліч зашифрованих даних, заданих алгоритмом криптографічного перетворення.
Криптостійкістю називається характеристика шифру, визначальна його стійкість до дешифрування. Звичайно ця характеристика визначається періодом часу, необхідним для дешифрування.
Одним з найбільш розповсюджених криптографічних стандартів на шифрування даних, що застосовуються в США, є DES (Data Encryption Standard). Первісно засіб, що лежить в основі даного стандарту, був розроблений фірмою IBM для своїх цілей. Він був перевірений Агенцією Національної Безпеки США, що не виявило в ньому статистичних або математичних вад. Це означало, що дешифрування даних, захищених з допомогою DES, не могло бути виконане статистичними (наприклад, з допомогою частотного словника) або математичними ("прокручуванням" в зворотному напрямку) засобами.
Після цього засіб фірми IBM був прийнятий як федеральний стандарт. Стандарт DES використовується федеральними департаментами і агенціями для захисту всіх достатньо важливих даних у комп'ютерах (виключаючи деякі дані, засоби захисту яких визначаються спеціальними актами). Його застосовують багато недержавних інститутів, у тому числі більшість банків і служб оберту грошей. Обумовлений у стандарті алгоритм криптографічного захисту даних опублікований для того, щоб більшість користувачів могли використати перевірений і апробований алгоритм з гарною криптостійкістю. Помітимо, що, з одного боку, публікація алгоритму небажана, оскільки може призвести до спроб дешифрування закритої інформації. Але, з іншого боку, це не настільки істотно (якщо стандарт сильний) у порівнянні зі слабкими засобами захисту даних, що використовуються державними інститутами. Інакше кажучи, втрати від публікації алгоритму криптографічного захисту набагато менші, ніж втрати від застосування засобів захисту з низькою криптостійкістю. Зрозуміло, стандартний алгоритм шифрування даних має володіти такими характеристиками, щоб його опублікування не відбилося на криптостійкості.
Засіб шифрування з використанням датчика ПВЧ найбільш часто використовується у програмній реалізації системи криптографічного захисту даних. Це пояснюється тим, що з одного боку, він достатньо простий для програмування, а з іншого боку, дозволяє створювати алгоритми з дуже високою криптостійкістю. Крім того, ефективність даного засобу шифрування є достатньо високою. Системи, основані на засобі шифрування з використанням датчика ПВЧ, дозволяють зашифрувати в секунду від декількох десятків до сотень кілобайт даних (тут і надалі всі характеристики наведені для персональних комп'ютерів).
Однак простота засобу може зіграти злий жарт з розробником власного алгоритму шифрування даних. Як вже було показане вище (проблема відомого тексту) шифр, який має дуже грізний вигляд, може бути чутливим до простих впливів. Тому кожний новий алгоритм шифрування даних перед його застосуванням має підлягати всебічному математичному, статистичному і криптографічному аналізам. Тільки після усунення всіх слабких сторін алгоритму він може використовуватися для шифрування даних. У противному випадку результати можуть бути катастрофічними.
Основною перевагою засобу DES є те, що він є стандартним. Як стверджує Національне Бюро Стандартів США, алгоритм має наступні властивості:
– високий рівень захисту даних проти дешифрування і можливої модифікації даних;
– простота і розуміння;
– високий ступінь складності, що робить його розкриття дорожче одержуваного при цьому прибутку;
– засіб захисту грунтується на ключі і не залежить ні від якої "таємності" алгоритму;
– економічний у реалізації та ефективний у швидкодії.
Важливою характеристикою цього алгоритму є його гнучкість при реалізації і використанні в різноманітних додатках обробки даних. Кожний блок даних шифрується незалежно від інших, що дозволяє розшифрувати окремий блок у зашифрованому повідомленні та структурі даних. Тому можна здійснювати незалежну передачу блоків даних і довільний доступ до зашифрованих даних. Ні тимчасова, ні позиційна синхронізація для операцій шифрування не потрібні.
Алгоритм виробляє зашифровані дані, в яких кожний біт є функцією від усіх бітів відкритих даних і всіх бітів ключа. Відмінність лише в одному біті даних дасть у результаті рівні ймовірності зміни для кожного біта зашифрованих даних.
Звичайно, ці властивості DES вигідно відрізняють його від засобу шифрування з використанням датчика ПВЧ, оскільки більшість алгоритмів шифрування, побудованих на основі датчиків ПВЧ, не характеризуються всіма перевагами DES. Однак і DES має низку недоліків.
Найістотнішим недоліком DES фахівці визнають розмір ключа, що вважається занадто малим. Стандарт у нинішньому вигляді не є неуразливим, хоча і є дуже тяжким для розкриття (досі не були зареєстровані випадки дешифрування інформації, зашифрованою з використанням засобу DES). Для дешифрування інформації засобом підбору ключів достатньо виконати 2^56 операцій розшифрування (тобто всього близько 7*10^16 операцій). Хоча в наш час немає апаратури, що могла б виконати в період часу, що оглядається, подібні обчислення, ніхто не гарантує, що вона не з'явиться в майбутньому. Деякі фахівці пропонують модифікацію для усунення цього недоліку: вхідний текст Р зашифровується спочатку за ключем К1, після цього за ключем К2 і, нарешті, за ключем К3. В результаті час, що вимагається для дешифрування, зростає до 2^168 операцій (приблизно, до 10^34 операцій).
Ще один недолік засобу DES полягає в тому, що окремі блоки, що містять однакові дані (наприклад, пропуски), матимуть однаковий вигляд у зашифрованому тексті, що з погляду криптоаналізу є невірним.
Засіб DES може бути реалізований і програмно. Залежно від швидкодії та типу процесора персонального комп'ютера програмна система, що шифрує дані з використанням засобу DES, може обробляти від декількох кілобайт до десятків кілобайт даних у секунду. У той же час необхідно відзначити, що базовий алгоритм все ж розрахований на реалізацію в електронних приладах спеціального призначення.
Алгоритм криптографічного перетворення, що був союзним стандартом і визначається ДГСТ 28147-89, вільний від недоліків стандарту DES і в той же час володіє всіма його перевагами. Крім того, у стандарт вже закладений засіб, з допомогою якого можна зафіксувати невиявлену випадкову або навмисну модифікацію зашифрованої інформації.
Однак у алгоритму є дуже істотний недолік, який полягає в тому, що його програмна реалізація дуже складна і практично позбавлена всякого сенсу із-за вкрай низької швидкодії. За оцінками авторів, за одну секунду на персональному комп'ютері можуть бути оброблені всього лише декілька десятків (максимально сотень) байт даних, а подібна продуктивність навряд чи задовольнить кого-небудь з користувачів. Хоча зараз вже розроблені апаратні засоби, що реалізують даний алгоритм криптографічного перетворення даних, які демонструють прийнятну продуктивність (біля 70 Кб/с для IBM ПC AT з тактовою частотою 12 Мгц), все ж складається враження, що розробники алгоритму цілком не піклувались про ефективність його програмної реалізації та про вартість шифрування даних.
Тепер зупинимося на засобі RSA. Він є дуже перспективним, оскільки для зашифровування інформації не вимагається передачі ключа іншим користувачам. Це вигідно відрізняє його від всіх описаних вище засобів криптографічного захисту даних. Але в наш час до цього засобу відносяться з підозрою, оскільки в ході подальшого розвитку може бути знайдений ефективний алгоритм визначення дільників цілих чисел, в результаті чого засіб шифрування стане абсолютно незахищеним. Крім того, не має чіткого доказу, що не існує іншого засобу визначення таємного ключа за відомим, окрім як визначення дільників цілих чисел.
Урешті-решт, засіб RSA має лише переваги. До числа цих переваг слід віднести дуже високу криптостійкість, досить просту програмну і апаратну реалізації. Щоправда, слід помітити, що використання цього засобу для криптографічного захисту даних нерозривно пов'язане з дуже високим рівнем розвитку техніки.
Цікаві книги:
http://progbook.net/seti/kriptograf/2672-cryptographic_boolean_functions_and_applications.html
http://progbook.net/seti/kriptograf/1568-teoreticheskaya_kriptografiya.html
http://progbook.net/seti/kriptograf/1554-elementy_kriptografii_osnovy_teorii_zashity_inform.html
http://progbook.net/seti/kriptograf/1502-kriptografiya_ot_papirusa_do_komp_yutera.html
http://progbook.net/seti/kriptograf/1498-elementarnoe_vvedenie_v_ellipticheskuyu_kriptograf.html
http://progbook.net/seti/kriptograf/1509-vzlomshiki_kodov.html
