Оскільки передбачається, що система є ідеальною, то по визначенню для будь-якого повідомлення та кріптограми повинна виконуватися умова: , з якого, враховуючи, що

(2.9)

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

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

Нехай ключ представляє собою послідовність довжиною N із алфавіта К об'ємом . Тоді загальне число ключів буде дорівнювати . Порівнюючи це число ключів з числом повідомлень , де m - об'єм алфавіта джерела, n - довжина повідомлення, отримаємо, що необхідна умова ТНДШ приймає вигляд

, або (2.10)

У частному випадку, коли L=m, отримаємо, що N=n, що співпадає з достатньою умовою, яку отримали вище для прикладу двоїчного кодування по модулю два.

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

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

, або (2.11)

Оскільки для будь-яких джерел Н(М) <logm, то (7) дає меньш жорсткі умови, ніж (6). Чим більше надлишок джерела, тим менше його ентропія. Таким чином для забезпечення найбільш економного з точки зору ключа ідеального шифра, необхідно попередньо стиснути повідомлення, а потім провести додавання по модулю два з ключовою послідовністю.

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

Приклад: нехай задані такі параметри джерела повідомлень та ключа: L=2, m=32, ентропія джерела Н(М) =0.5 біта на букву. Тоді при шифруванні усіх послідовностей джерела довжина ключа повинна бути N=5n, тоді як після стиснення повідомлення такого джерела вони можуть бути зменшені вдвічи.

2.4. Поняття про відстань єдиності

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

Будемо вважати, що опоненту відома кріптограма Е та опис системи шифрування-дешифрування симетричної кріптосистеми, тобто функції f(M,K) та g(E,K), але невідомий ключ К. Використовуючи до прийнятої кріптограми Е усі можливі ключі К, можна спробувати відновити повідомлення, коли серед численності ключів тільки один є вірним, тоді як інші - помилкові. Відбраковку ключів можна виконувати, використовуючи крітерій, який полягає у отриманні осмисленного текста. Однак може статися, що одній кріптограмі будуть відповідати декілька осмисленних розшифровок. У цьому випадку навіть при необмеженій розрахунковій потужності опонента немає засобу, щоб знайти істиний ключ та відновити дійсно зашифроване повідомлення.

Мал.2.7. Розшифровка кріптограми тотальним перебором ключів.

Нехай одній кріптограмі відповідає S осмислених розшифровок (мал.2.7). З них очевидно будуть помилкові, та одна істинна. Передбачемо також, що алфавіти повідомлень та кріптограм, а також довжини послідовностей повідомлень та кріптограм співпадають.

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

(2.15)

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

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

(2.16)

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

Аналіз формули для відстані єдиності показує, що чим менш надлишковим є джерело, тобто чим більше Н(М) до logm, тим більше відстань єдиності. Використовуючи дану формулу неважко побачити, що для дійсних повідомлень з надлишковістю та при відносно невеликій довжині ключа відстань єдиності є прийнятною для аналізу з боку опонента.

Пример. Пусть алфавит сообщения содержит 32 буквы, а энтропия сообщения H(M) = 1,5 (что примерно соответствует энтропии русского языка). Тогда при двоичном ключе длиною N = 128 символов, расстояние единственности составляет 40 букв.

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

В заключение следует сделать общий вывод о том, что стойкие системы шифрования, криптоанализ которых не зависит от вычислительных или аппаратных возможностей оппонента, к сожалению не реализуемы на коротких ключах (N << n).

2.5. Вычислительно стойкие криптосистемы

Криптосистема называется вычислительно стойкой, если наилучший алгоритм дешифрования требует времени (или оборудования) больше, чем имеется в распоряжении оппонента.

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

Существенная сложность при разработке вычислительно стойких криптосистем возникает в связи с определением наилучшего алгоритма криптоанализа. В действительности эта задача не решена ни для одной мощной криптосистемы, т.е. для достаточно мощных шифров наилучшие такие алгоритмы просто не известны. Поэтому можно говорить лишь об известных в настоящее время наилучших методах криптоанализа, которые применимы к отдельным классам шифров или разработаны для конкретных шифров. (Обычно ограничиваются наилучшими известными в настоящее время алгоритмами криптоанализа и берут значительный запас на быстродействие и количество вычислительных средств) Поэтому теоретически всегда существует возможность, что будет найден некоторый новый метод криптоанализа, который позволит решить задачу "в реальном времени". Однако для современных шифров вероятность такого "прорыва" весьма мала, поскольку он требует решения весьма сложных, и обычно давно известных в математике задач. Это особенно верно для систем с открытым ключом, для которых задача криптоанализа может быть четко сформулирована как некоторая вполне конкретная математическая задача.

В современной математике существует область "Теория сложности алгоритмов", где различают "простые" и "сложные" задачи. Задачи полиномиальной сложности, для решения которых необходимое число элементарных операций является полиномиальной функцией от размерности задачи, относятся к простым. Время T(N) для их решения  N n, где N - размерность задачи. Наиболее сложные (трудные) задачи требуют для своего решения числа операций, которое экспоненциально зависит от размерности задачи, т.е. T(N)  abN, где aиb>0 некоторые постоянные, в силу чего весь класс таких задач называется EXPTIME.

Нужно избегать построения криптосистем с полиномиальным временем криптоанализа и стараться строить криптосистемы так, чтобы их вскрытие относилось к задачам второго класса сложности.

Помимо двух уже рассмотренных классов задач в теории сложности выделяют еще один важный класс задач, называемых недетерминистско - полиномиальными (NP задачами). NP - задачи - это задачи, для которых пока неизвестны алгоритмы решения с полиномиальной сложностью (это не означает, что они вообще не существуют). Однако, если решение такой задачи найдено, то проверка его правильности это задача полиномиальной сложности.

Рис.2.8. Граф для поиска Гамильтонова цикла

Имеется достаточно широкий класс известных NP-задач, имеющий многовековую историю попыток их полиномиального решения. Так, например, для заданного графа (см. рис 2.8) нужно найти путь (Гамильтонов путь) проходящий по всем вершинам графа только один раз. Не известен алгоритм нахождения Гамильтонова цикла полиномиальной сложности от числа вершин графа. Хотя, если такой цикл найден, то проверить правильность предлагаемого решения всегда можно с помощью алгоритма полиномиальной сложности.

Среди задач NP класса имеется подкласс (см. рис.2.9) наиболее сложных задач, которые называются NP - трудными. Это задачи, обладающие следующим свойством: если для какой - то из них найдется алгоритм решения с полиномиальной сложностью, то это будет означать, что существуют алгоритмы с полиномиальной сложностью для решения всех задач из NP класса.

Рис.2.9. Соотношение между задачами NP и NPC класса.

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

Отметим, однако, что имеется важное, существенное отличие в подходе к оценке сложности произвольных алгоритмов и сложности криптоанализа. В классической теории сложности оценка производится для самой трудной задачи, т.е. при наихудших входных данных, тогда как во втором - при всех входных данных, в том числе и при наилучших, т.е. при наиболее благоприятных для криптоанализа ключах.

Помимо рассмотренных ранее классов детерминированных алгоритмов, существует еще класс так называемых рандомизированных полиномиальных алгоритмов. К нему принадлежат такие алгоритмы, которые имеют полиномиальную сложность, но дают правильный ответ на поставленную задачу лишь с некоторой вероятностью. Очевидно, что если эта вероятность близка к единице, то с практической точки зрения, рандомизированные алгоритмы не хуже детерминированных.

Поэтому необходимо также исключить такие криптографические схемы, которые имеют рандомизированный алгоритм криптоанализа с полиномиальной сложностью.

Таким образом, основные очевидные требования к вычислительно стойким криптосистемам можно сформулировать в следующем виде:

Число ключей LN должно быть непереборно большим, например при L = 2 нужно иметь N = 64, N = 128 и т.п., поскольку в противном случае, приняв криптограмму длиною больше расстояния единственности (n > nре) можно правильно дешифровать переданное сообщение путем полного перебора ключей.

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

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

3. основнi види сучасних методiв шифрування i дешифрування

Класифікація.

Класифікація сучасних методів шифрування і дешифрування може відбуватися по різних ознаках. По стійкості вони діляться на:

1. Ідеальні (досконалі або безумовно стійкі, ТНДШ).

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

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

По засобах формування криптограми з повідомлення розрізняють:

Блокові шифри.

Потокові шифри.

4. Шифри з відкритим ключем.

5. Маскуватори аналогових повідомлень.

З погляду використання ключа виділяють:

1. Двоключеві системи (несиметричні), .

2. Одноключеві (симетричні), = .

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

Мал. 3.1. Блокове шифрування.

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

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

Мал. 3.2. Потокове шифрування.

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

,(3.1)

де - i-ий символ гами залежачий функціонально від ключа K Відновлення повідомлення відбувається по аналогічному прийомі:

(3.2)

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

Мал. 3.3. Потокове шифрування гамуванням.

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

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

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

Мал. 3.4. Перетворення спектра: а) інверсія б) перестановка смуг.

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

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

Для надійного шифрування мовного сигналу його потрібно перетворити в цифрову форму, потім використовувати стійкі шифри пристосовані для шифрування для дискретних повідомлень, наприклад потокові шифри. Проте при перетворенні розмови в цифрову форму за допомогою імпульсно-кодової модуляції або дельта-модуляції істотно розширюється необхідна смуга частот каналу зв'язку, що призводить до необхідності використовувати більш широкополосні канали. Для того щоб передати зашифрований сигнал у тієї ж смузі частот (0,3-3,4 kГц), що використовується звичайно для передачі вихідного мовного сигналу, застосовуються спеціальні мовоперетворюючі пристрої - вокодери. Ці пристрої вимагають невеликої швидкості передачі, порядку 1200-2400 біт/c, завдяки чому зашифрований сигнал також може бути переданий по каналі ТЧ.

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

Конкретні засоби побудови блокових і потокових шифрів розглянемо в наступних розділах.

Блокові симетричні шифри.

Основні принципи побудови блокових симетричних шифрів.

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

Переплутування (нелінійне перетворення підстановка) символів.

Перемішування (розосередження, перестановка) символів.

Ітерування (повторення пунктів 1 і 2 багаторазово).

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

Мал.3.5. Побудова блокових шифрів.

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

Найпростішим засобом завдання нелінійного перетворення є табличний засіб, коли двоїчний блок спочатку перетвориться в число, потім це число по таблиці перетвориться в інше і, нарешті, отримане число знову по таблиці перетвориться в двоїчний блок. Наприклад, шифруються блоки довжиною n = 3, яким зіставлені такі числа: 000 - 0, 001 - 1, 010 - 2,..., 111 - 7. Тоді таблиця підстановок може бути задана в такий спосіб:

{0, 1, 2, 3, 4, 5, 6, 7}{4, 2, 6, 7, 0, 5, 1, 3}.

Це означає, що, наприклад, вхідний блок 011 буде перетворений у вихідний блок 111. Складність такого перетворення залежить від довжини таблиці, що дорівнює 2n, де n - довжина блока.

Вигляд нелінійного перетворення звичайно залежить від певних біт розширеного ключа, що виробляється з вихідного ключа. Наприклад, нелінійне перетворення, що залежить від біт розширеного ключа = (K1,K2,K3), може мати вигляд

f(,) = f((K1,K2,K3), (M1,M2,M3)) = = (E1, E2, E3).

E1 = K1K2M1M2, E2 = K2K3M2M3,

E3 = (K1 K2) M1M3, = (E1, E2, E3). (3.3)

Якщо криптограма і повідомлення = (M1, M2, M3) відомі, то при виконанні криптоаналізу можна скласти рівняння щодо елементів розширеного ключа . Це буде система нелінійних рівнянь із невідомими K1, K2, K3, де дії виконуються по модулю два.

У процесі шифрування часто виконується декілька перетворень із двоїчними блоками, при чому, крім лінійної операції додавання по модулю два, використовуються, наприклад, операції додавання по модулю 2n, 2n+1 або множення по модулю 2n+1, де n - довжина блока і т.п. Тому криптоаналіз гарного блокового шифру не зводиться до відомих поліноміальних задач.

Більшість сучасних блокових шифрів реалізується на основі, так називаної, структури Файстеля. Для цього попередньо з вихідного ключа  = 0 за допомогою заданого детермінованого перетворення, що входить в опис алгоритму шифрування, формується послідовність розширених ключів i, i = 1,2,...,d, де d - число ітерацій.

Мал.3.6. Підготовка блоків для шифрування на основі структури Файстеля.

Далі структура Файстеля припускає такий засіб перетворення блоків. Спочатку послідовність двоїчних символів повідомлення розбивається на блоки довжиною n=2n0 (мал.3.6).

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

,

i=2,3,...,d, (3.4)

де 0 і  1 - підблоки першого блока вихідного повідомлення, f(,) - детермінована відкрита нелінійна функція, i-1 - елементи послідовності розширених ключів, сформовані детермінованим способом з основного секретного ключа даної криптосистеми. Криптограма, сформована на останній ітерації d, приймає вигляд

= ( d - 1, d). (3.5)

Наприклад, якщо дано = ( 0, 1), то обчислюємо

2 = 0 f(1, 1),

складаємо (1,2), знову обчисляємо

3 = 1 f( 2, 2),

складаємо (2,3) і т.д.,..., до отримання послідовностей d - 1 і d, із котрих і формується криптограма = (d - 1,d).

Перевага такої структури складається в тому, що по-перше, для неї виконується принцип перемішування між підблоками, по-друге, дуже просто реалізується алгоритм дешифрування при ключі, відомому законному користувачу. При цьому важливо те, що функція f(,) навіть не обов'язково повинна мати обернену! Дійсно, коректне дешифрування в даній структурі виконується по тому ж алгоритмі, що і шифрування: Нехай = ( 0, 1) = ( d - 1, d).

Тоді

,..., ,...,

1 = 3 f( 2, 2), 0 = 2 f( 1, 1),

= ( 0, 1), що, як очевидно і збігається з вихідним повідомленням.

Є багато різноманітних блокових шифрів, заснованих на структурі Файстеля, що відрізняються вибором функції f і засобом формування розширених ключів i i=1,2,…,d з основного ключа . Нехай на такий шифр відбувається напад із відомим повідомленням. Тоді, знаючи опис функції f і засіб побудови підключей по основному ключу, опонент може скласти систему нелінійних рівнянь і спробувати її вирішити щодо ключа як невідомого. Стійкість даного типу шифрів грунтується на складності рішення системи нелінійних рівнянь із діями по модулі два. Доведено, що в загальному випадку ця задача відноситься до класу NP - важких задач.

Багатократне шифрування блоків.

На перший погляд представляється очевидним, що можна значно підвищити стійкість шифру, якщо криптограму, отриману за допомогою ключа 1, зашифрувати ще раз за допомогою іншого ключа2, тобто реалізувати процедури шифрування-дешифрування в такий спосіб:

, . (3.6)

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

Метод, що у даному випадку використовується для дешифрування, називається "зустріччю в центрі". Нехай є криптограма , отримана шляхом повторного шифрування.

(3.7)

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

11 і 22. (3.8)

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8