Захист інформації

border="0" /> та повідомлення Захист інформації, яка відповідає певній частині криптограми, яку отримали при використанні того ж самого ключа (атака при частково відомому відкритому повідомлені).

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

Сучасні кріптосистеми важаються стійкими, якщо вони стійки до всіх трьох атак.

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

Дешифрування після передачі кріптограми по каналам зі спотвореннями не повинно збільшувати число помилок у порівнянні з тим числом помилок, які виникли у каналі зв’язку внаслідок спотворень, іншими словами не повинно відбуватися розмноження помилок.

Пояснемо суть поняття розмноження помилок. Нехай при передачі кріптограми Захист інформації по каналу зв’язку виникли помилки (див. мал.2.1).

Захист інформації Захист інформаціїЗахист інформації Захист інформації,t


Захист інформаціїЗахист інформації

Мал.2.1. Система шифрування-дешифрування.

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

Захист інформації (2.2)

Помилки не розмножуються при умові, що t’=t.

Якщо ключ шифрування дорівнює ключу дешифрування, тобто

Захист інформації=Захист інформації=Захист інформації, (2.3)

то система називається сіметричною (одноключовою). Тоді у пункти шифрування та дешифрування повинні бути доставлені однакові ключі. Якщо Захист інформації№Захист інформації, то система шифрування називається несіметричною (двоключовою). У цьому випадку ключ Захист інформації доставляється у пункт шифрування, а Захист інформації - у пункт дешифрування. Оба ключа повинні бути зв’язані функціональною залежністю Захист інформації=j(Захист інформації), але такою, щоб відомому ключу шифрування неможливо було б відтворити ключ дешифрування. Для несиметричних систем шифрування j() повинна бути складно розрахуємою функцією. У такій системі є можливість секретним чином розподіляти серед законних користувачів тільки їх ключі дешифрування, а ключі шифрування зробити відкритими та оприлюднити, наприклад у загальнодоступному довіднику. Розглядаєма система тому називається системою з відкритим (загальнодоступним) ключом Захист інформації. Кріптосистема з загальнодоступним ключом (Public key criptosystem) була вперше запропанована Діффі та Хелманом у 1978р.

У цій частині курсу будуть розглядатися тільки одноключові системи.


2.3 Особливі крітерії стійкості кріптосистем


Існують два основних класа стійкості кріптосистем:

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

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

Система є теоретично недешифруємою, якщо будь-яка криптограма Захист інформації, отримана у ній, при відсутності знання про ключ Захист інформації, не містить ніяких відомостей про повідомлення Захист інформації, зашифроване у цю кріптограму. У відповідності з терією інформації це має місце, коли (при відсутності відомостей про ключ) дорівнює нулю взаємна інформація між численністю повідомлень М та численністю кріптограм Е, тобто І(Е, М) =0, де І(Е, М) =Н(М) - Н(М/Е), Н(м) - ентропія джерела повідомлень, Н(М/Е) - умовна ентропія численності повідомлень М при заданій численності криптограм Е.

При ідеальному шифруванні фактично виникає "обрив канала" від легальних користувачів до опонентів.

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

Захист інформації (2.4)

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

Розглянемо приклад побудови теоретично недешифруємих систем (див. мал.2.2).

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

Захист інформації (2.5)

використовуючи побітне додавання Е з ключем Захист інформації, який також є двоїчною послідовністю довжини n.

Наприклад,

Захист інформації011001101111010001110

Е

Захист інформації010011110101100110101

___________________________

Захист інформації001010011010110111011

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

Захист інформації (2.6)

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

Елементи ключа вибирають незалежно, тому достатньо довести рівність Р(М|Е) =Р(М) для одного елемента. По формулі Бейеса

Захист інформації (2.7)

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

Звідси р(Е) =р(М=0) р(Е|М=0) +р(М=1) р(Е|М=1) =0.5(р(М=0) +р(М=1)) = 0.5 і отимаємо

Захист інформації (2.8)

Останнє рівняння і є умовою теоретичної недешифруємості.

Відзначимо, що дана система має суттєвий недолік, який полягає у тому, що потрібна довжина ключа N повинна дорівнювати довжині повідомлення, тому необхідна генерація, передача у секреті, зберігання великого числа біт ключа, що робить розглядаєму систему дорогою та непридатною для масового використання, доступною лише для привілейованих користувачів. Але поки на доведено, що умова n=N є необхідною для побудови ТНДШ.

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

Захист інформації
шифрування - на мал.2.5.


Мал.2.5. Граф шифрування одним ключом.
Мал.2.6. Граф шифрування в одну криптограму.

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

Захист інформації (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Ш, як показано на мал

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: