Математичні основи криптографії

Великий вплив на розвиток криптографії зробили роботи американського математика Клода Шеннона, що з'явилися в середині XX століття. У цих роботах були закладені основи теорії інформації, а також був розроблений математичний апарат для досліджень в багатьох галузях науки, пов'язаних з інформацією. Більш того, прийнято вважати, що теорія інформації як наука народилася в 1948 році після публікації роботи К. Шенона "Математична теорія зв’язку").

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

Шифр заміни є простим, найбільш популярним шифром. Типовими прикладами є шифр Цезаря. Як видно з назви, шифр заміни здійснює перетворення заміни букв або інших "частин" відкритого тексту на аналогічні "частини" шифрованого тексту. Легко дати математичний опис шифру заміни. Нехай і - два алфавіти (відкритого і шифрованого текстів відповідно), що складаються з однакової кількості символів. Нехай також - взаємо-однозначне відображення в . Тоді шифр заміни діє так: відкритий текст перетвориться в шифрований текст .

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

Найважливішим для розвитку криптографії був результат Шенона про існування і єдиність абсолютно стійкого шифру. Єдиним таким шифром є яка-небудь форма так званої стрічки однократного використання, в якій відкритий текст "об’єднується" з повністю випадковим ключем такої ж довжини.

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

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

Тут - відкритий текст, - ключ, - шифрований текст.

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

1) повна випадковість (рівноймовірність) ключа (це, зокрема, означає, що ключ не можна виробляти за допомогою якого-небудь детермінованого пристрою);

2) рівність довжини ключа і довжини відкритого тексту;

3) однократність використання ключа.

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

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

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

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

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

Тому у користувача залишається єдиний шлях - отримання практичних оцінок стійкості, і складається з таких етапів:

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

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

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

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

Дата добавления: 2014-01-07