 |
Методи рандомізації повідомлень
|
|
|
|
Огляд методик рандомізації повідомлень. Наступним удосконаленням, направленим на підвищення стійкості всієї системи в цілому є створення ключів сеансу. Ця операція необхідна в тих випадках, коли відбувається часте шифрування схожих блоків даних одним і тим же ключем. Наприклад, це має місце при передачі інформації або команд в автоматизованих системах управління, в банківських операціях і багатьох інших випадках передачі інформації, що має визначений заздалегідь відомий формат.
В цьому випадку необхідне введення якої-небудь випадкової величини в процес шифрування. Це можна зробити декількома способами:
1 записом в початок файлу даних псевдовипадкової послідовності байт заздалегідь обумовленої довжини з відкиданням її при дешифруванні – цей метод працюватиме лише при використанні алгоритмів створення ланцюжків з пам'яттю (CBC,CFB,OFB);
2 використанням модифікованих алгоритмів створення ланцюжків, які при шифруванні кожного блоку змішують з ним або:
а фіксовану випадкову величину, прикріплену на початок зашифрованого файлу, або
б значення, що обчислюються за допомогою того ж шифру і ключа від заздалегідь обумовленої величини;
3 створенням спеціально для кожного файлу абсолютно випадкового ключа, так званого ключа сеансу, яким і шифрується весь файл (сам же ключ сеансу шифрується первинним ключем, що називається в цьому випадку майстер-ключем, і поміщається на початку зашифрованого файлу).
Всі вказані схеми принципово не мають очевидних недоліків, але завдяки більшій опрацьованості останнього методу зазвичай застосовується саме він.
Генератори випадкових і псевдовипадкових послідовностей. Найбільша проблема всіх методів рандомізації повідомлень – це породження дійсно випадкової послідовності біт. Річ у тому, що генератори випадкових послідовностей, використовувані для загальних цілей, наприклад, в мовах програмування, є насправді псевдовипадковими генераторами. Оскільки, в принципі, існує кінцева, а не безкінечна множина станів ЕОМ, і, як би складно не формувалося в алгоритмі число, воно все одно має відносно небагато біт інформаційної насиченості.
|
|
|
Давайте розглянемо проблему створення випадкових і псевдовипадкових чисел детальніше. Найчастіше в прикладних завданнях результат формують з лічильника тіків – системного годинника. В цьому випадку дані про поточну годину несуть приблизно 16 біт інформації, значення лічильника тиків – ще 16 біт. Це дає нам 32 біта інформації – як ви пам'ятаєте, на сьогоднішній день межею стійкої криптографії є значення в 40 біт, при реальних довжинах ключів в 128 біт. Природно, що подібного методу вкрай недостатньо. Йдемо далі, до 32 біт можна додати ще 16 біт з надшвидкого таймера, що працює на частоті 1,2 Мгц в комп'ютерах архітектури IBM РС AT і цього ще недостатньо. Крім того, навіть якщо ми зможемо набрати довжину ключа в 128 біт (що дуже сумнівно), вона нестиме псевдовипадковий характер, оскільки заснована на стані тільки даної ЕОМ на момент початку шифрування. Джерелами по-справжньому випадкових величин можуть бути лише зовнішні об'єкти, наприклад, людина.
Два найчастіше використовуваних методи створення випадкових послідовностей за допомогою людини засновані на введенні з клавіатури. В обох випадках користувача просять, не замислюючись, понабирати на клавіатурі безглузді поєднання букв.
За першим методом над самими введеними значеннями виробляються дії, що підвищують випадковість вихідного потоку. Так, наприклад, обов'язково видаляються верхні 3 біта введеного символу ASCII, часто відкидається ще один верхній і ще один нижній біти. Потім, об'єм отриманої послідовності зменшується ще в три рази накладенням першого і другого біта на третій операцією XOR. Це, в принципі, генерує досить випадкову послідовність біт.
|
|
|
За другим методом на введені символи алгоритм не звертає жодної уваги, зате конспектує інтервали часу, через які сталися натиснення. Запис моментів здійснюється за відліками швидкого системного таймера (частота 1,2 Мгц) або внутрішньому лічильнику процесора. Оскільки старші й молодші біти мають певну кореляцію між символами (перші через фізичні характеристики людини, другі - через особливості операційної системи), то вони відкидаються (зазвичай 0-8 старших біта і 4-10 молодших).
Ще до таких методів, хоча вони рідко використовуються, можна віднести:
1 комбінацію обох клавіатурних методів;
2 метод, заснований на маніпуляторі "миша", - він виділяє випадкову інформацію із зсувів користувачем покажчика миші.
У потужних криптосистемах військового застосування використовуються дійсно випадкові генератори чисел, засновані на фізичних процесах. Вони є платами, або зовнішніми пристроями, що підключаються до ЕОМ через порт введення-виводу. Два основні джерела білого Гаусівського шуму:
1 високоточне вимірювання теплових флуктуацій;
2 запис радіоефіру на частоті, вільній від радіомовлення.
Архівація
Загальні принципи архівації. Класифікація методів. Наступною великою темою є архівація даних. Як Вам відомо, переважна більшість сучасних форматів запису даних містять їх у вигляді, зручному для швидкого маніпулювання, для зручного прочитання користувачами. При цьому дані займають об'єм більший, ніж це дійсно потрібно для їх зберігання. Алгоритми, які усувають надмірність запису даних, називаються алгоритмами стискування даних, або алгоритмами архівації. В даний час існує величезна кількість програм для стискування даних, заснованих на декількох основних способах.
Навіщо ж потрібна архівація в криптографії? Річ у тому, що в сучасному криптоаналізі, тобто науці про протистояння криптографії, з очевидністю доведено, що вірогідність злому криптосхеми за наявності кореляції між блоками вхідної інформації значно вище, ніж за відсутності такої. А алгоритми стискування даних за визначенням і мають своїм основним завданням усунення надмірності, тобто кореляцій між даними у вхідному тексті.
|
|
|
Всі алгоритми стискування даних якісно поділяються на:
1 алгоритми стискування без втрат, при використанні яких дані відновлюються без щонайменших змін;
2 алгоритми стискування з втратами, які видаляють з потоку даних інформацію, що трохи впливає на суть даних, або взагалі не сприймається людиною (такі алгоритми зараз розроблені лише для аудіо- та відео-зображень).
У криптосистемах, природно, використовується лише перша група алгоритмів.
Існує два основні методи архівації без втрат:
- алгоритм Хаффмана (англ. Huffman), орієнтований на стискування послідовностей байт, не зв'язаних між собою;
- алгоритм Лемпеля-Зіва (англ. Lempel, Ziv), орієнтований на стискування будь-яких видів текстів, тобто використання неодноразового повторення "слів" – послідовностей байт.
Практично всі популярні програми архівації без втрат (ARJ, RAR, ZIP) використовують об'єднання цих двох методів – алгоритм LZH.
Алгоритм Хаффмана. Алгоритм заснований на тому факті, що деякі символи із стандартного 256-символьного набору в довільному тексті можуть зустрічатися частіше за середній період повтору, а інші, відповідно, – рідше. Отже, якщо для запису поширених символів використовувати короткі послідовності біт, завдовжки менше 8, а для запису символів, що зустрічаються рідко – довгі, то сумарний об'єм файлу зменшиться.
Хаффман запропонував дуже простий алгоритм визначення того, який символ необхідно кодувати яким кодом для отримання файлу з довжиною, дуже близькою до його ентропії (тобто інформаційній насиченості). Нехай у нас є список всіх символів, що зустрічаються у вихідному тексті, причому відома кількість появ кожного символу в ньому. Випишемо їх вертикально в ряд у вигляді вічок майбутнього графа з правого краю аркуша (рис. 4.5а). Виберемо два символи з найменшою кількістю повторень в тексті (якщо три або більше число символів мають однакові значення, вибираємо будь-які два з них). Проведемо від них лінії вліво до нової вершини графа і запишемо в неї значення, рівне сумі частот повторення кожного з об'єднуваних символів (рис.4.5б). Далі не братимемо до уваги при пошуку найменших частот повторення два об'єднані вузли (для цього зітремо числа в цих двох вершинах), але розглядатимемо нову вершину як повноцінне вічко з частотою появи, рівній сумі частот появи двох вершин, що з'єдналися. Повторюватимемо операцію об'єднання вершин до тих пір, поки не прийдемо до однієї вершини з числом (рис.4.5в і 4.5г), для перевірки. вочевидь, що в ній буде записана довжина кодованого файлу. Тепер розставимо на двох ребрах графа, що виходять з кожної вершини, біти 0 і 1 довільно – наприклад, на кожному верхньому ребрі 0, а на кожному нижньому – 1. Тепер для визначення коду кожної конкретної букви необхідно просто пройти від вершини дерева до неї, виписуючи нулі і одиниці по маршруту слідування. Для рис. 4.5 символ "А" отримує код "100", символ "Б" – код "0", символ "К" – код "101", а символ "О" – код "11".
|
|
|
В теорії кодування інформації показується, що код Хаффмана є префіксним, тобто код жодного символу не є початком коду якого-небудь іншого символу. Перевірте це на нашому прикладі. А з цього виходить, що код Хаффмана однозначно відновлюваний одержувачем, навіть якщо не повідомляється довжини коду кожного переданого символу. Одержувачеві пересилають лише дерево Хаффмана в компактному вигляді, а потім вхідна послідовність кодів символів декодується ним самостійно без якої-небудь додаткової інформації.
Наприклад, при отриманні послідовності "01001101000" ним спочатку відділяється перший символ "Б": "0-1001101000", потім знову починаючи з вершини дерева – "А" "0-100-1101000", потім аналогічно декодується весь запис "0-100-11-0-100-0" "БАОБАБ".
Рисунок 4.5 - Алгоритм Хаффмана
4.4.3 Алгоритм Лемпеля-Зіва. Класичний алгоритм Лемпеля-Зіва – LZ77, названий так за роком своєї публікації, гранично простий. Він формулюється таким чином: "якщо у вихідному потоці, що пройшов раніше, вже зустрічалася подібна послідовність байт, причому запис про її довжину і зсув від поточної позиції коротше чим сама ця послідовність, то у вихідний файл записується посилання (зсув, довжина), а не сама послідовність". Так фраза "КОЛОКОЛ_ ОКОЛО_КОЛОКОЛЬНИ" закодується як "КОЛО(-4,3)_(-5,4)О_(-14,7) ЬНИ".
Поширений метод стискування RLE (англ. Run Length Encoding), який полягає в записі замість послідовності однакових символів одного символу і їх кількості, є підкласом даного алгоритму. Розглянемо, наприклад, послідовність "ААААААА". За допомогою алгоритму RLE вона буде закодована як "(А,7)", в той же час її можна досить добре стискувати і за допомогою алгоритму LZ77: "А(-1,6)". Дійсно, міра стискування саме такої послідовності ним гірше (приблизно на 30-40%), але сам по собі алгоритм LZ77 більш універсальний, і може набагато краще обробляти послідовності, які взагалі нестискуються методом RLE.
|
|
|
Хешування паролів
Від методів, що підвищують криптостійкість системи в цілому, перейдемо до блоку хешування паролів – методу, що дозволяє користувачам запам'ятовувати не 128 байт, тобто 256 шістнадцяткових цифр ключа, а деякий осмислений вираз, слово або послідовність символів, що називається паролем. Дійсно, при розробці будь-якого криптоалгоритму слід враховувати, що в половині випадків кінцевим користувачем системи є людина, а не автоматична система. Це ставить питання про те, чи зручно, і взагалі чи реально людині запам'ятати 128-бітовий ключ (32 шістнадцяткових цифри). Насправді межа запам’ятовуваності становить 8-12 подібних символів, а, отже, якщо ми заставлятимемо користувача оперувати саме ключем, тим самим ми практично змусимо його до запису ключа на якому-небудь листку паперу або електронному носієві, наприклад, в текстовому файлі. Це, природно, різко знижує захищеність системи.
Для вирішення цієї проблеми були розроблені методи, що перетворюють вимовний, осмислений рядок довільної довжини, – пароль, у вказаний ключ заздалегідь заданої довжини. У переважній більшості випадків для цієї операції використовуються так звані хеш-функції (від англ. hashing – дрібна нарізка і перемішування). Хеш-функцією називається таке математичне або алгоритмічне перетворення заданого блоку даних, яке володіє такими властивостями:
1 хеш-функція має нескінченну область визначення;
2 хеш-функція має кінцеву область значень
3 вона необоротна
4 зміна вхідного потоку інформації на один біт змінює близько половини всіх біт вихідного потоку, тобто результату хеш-функції.
Ці властивості дозволяють подавати на вхід хеш-функції паролі, тобто текстові рядки довільної довжини на будь-якій національній мові і, обмеживши область значень функції діапазоном 0..2N-1, де N – довжина ключа в бітах, отримувати на виході досить рівномірний розподілені блоки інформації – ключі.
Неважко відмітити, що вимоги 3 і 4 до хеш-функції, виконують блокові шифри. Це вказує на один з можливих шляхів реалізації стійких хеш-функцій – проведення блокових криптоперетворень над матеріалом рядка-пароля. Цей метод і використовується в різних варіаціях практично у всіх сучасних криптосистемах. Матеріал рядка-пароля багато разів послідовно використовується як ключ для шифрування деякого заздалегідь відомого блоку даних – на виході виходить зашифрований блок інформації, що однозначно залежний лише від пароля і при цьому має досить хороші статистичні характеристики. Такий блок або декілька таких блоків і використовуються як ключ для подальших криптоперетворень.
Характер використання блокового шифру для хешування визначається відношенням розміру блоку використовуваного криптоалгоритму і розрядності необхідного хеш-результату.
Якщо вказані вище величини збігаються, то використовується схема одноланцюгового блокового шифрування. Первинне значення хеш-результату H0 встановлюється рівним 0, весь рядок-пароль розбивається на блоки байт, рівні довжині ключа, що використовується для хешування блокового шифру, потім здійснюється перетворення за рекурентною формулою:
Hj=Hj-1 XOR EnCrypt(Hj-1,PSWj),
де EnCrypt(X,Key) – використовуваний блоковий шифр (рис.4.6).
Значення Hk використовується як шуканий результат.
У тому випадку, коли довжина ключа рівно в два рази перевершує довжину блоку, а подібна залежність досить часто зустрічається в блокових шифрах, використовується схема, що нагадує мережу Фейштеля. Характерним недоліком і приведеної вище формули, і хеш-функції, заснованої на мережі Фейштеля, є велика ресурсоємність відносно пароля. Для проведення лише одного перетворення, наприклад, блоковим шифром з ключем завдовжки 128 біт використовується 16 байт рядка-пароля, а сама довжина пароля рідко перевищує 32 символи. Отже, при обчисленні хеш-функції над паролем буде здійснено максимум 2 "повноцінних" криптоперення.
Вирішення цієї проблеми можна досягти двома шляхами:
1 заздалегідь "розмножити" рядок-пароль, наприклад, записавши його багато разів послідовно до досягнення довжини, скажімо, в 256 символів;
2 модифікувати схему використання криптоалгоритму так, щоб матеріал рядка-пароля "повільніше" витрачався при обчисленні ключа.
Іншим шляхом пішли дослідники Девіс і Маєр, що запропонували алгоритм також на основі блокового шифру, але який використовує матеріал рядка-пароля багато разів і невеликими порціями.
Рисунок 4.6 - блоковий шифр
Цей алгоритм має елементи обох приведених вище схем, але криптостійкість цього алгоритму підтверджена багаточисельними реалізаціями в різних криптосистемах. Алгоритм отримав назву "Tandem DM" (рис.4.7):
Рисунок 4.7 - Алгоритм "Tandem DM"
Квадратними дужками (X16=[A8,B8]) тут позначено просте об'єднання (склеювання) двох блоків інформації рівної величини в один – подвоєної розрядності. А як процедура EnCrypt(X,Key) знову може бути вибраний будь-який стійкий блоковий шифр. Як видно з формул, даний алгоритм орієнтований на те, що довжина ключа двократно перевищує розмір блоку криптоалгоритму. А характерною особливістю схеми є той факт, що рядок пароля прочитується блоками по половині довжини ключа, і кожен блок використовується в створенні хеш-результату двічі. Таким чином, при довжині пароля в 20 символів і необхідності створення 128 бітового ключа внутрішній цикл хеш-функції повториться 3 рази.
|
|
|
