Лекція 1 Основні поняття безпеки інформаційних систем

Розглядаються основні визначення що входять у поняття безпеки інформаційних систем (ІС). Дається класифікація видів загроз безпеці ІС і видів політики безпеки ІС.

1.1Основні поняття інформаційної безпеки комп'ютерних систем

1.1.1Поняття безпеки інформаційної системи

Безпека інформаційної системи - комбінація безпеки системи і циркулюючої в ній інформації.

Під безпекою ІС розуміють її захищеність від випадкового або навмисного втручання

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

Природа дій на ІС може бути найрізноманітнішою. Це і стихійні лиха (землетрус, ураган, пожежа), і вихід з ладу складових елементів ІС, і помилки персоналу, і спроба проникнення зловмисника.

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

1.1.2Поняття доступу до інформації

Поняття безпеки інформації має значення тільки у разі наявності санкціонованого або несанкціонованого доступу до неї з боку компонентів системи (суб'єктів і об'єктів).

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

Розрізняють санкціонований і несанкціонований доступ до інформації. Санкціонований доступ до інформації - це доступ до інформації, що не порушує

встановлені правила розмежування доступу. Правила розмежування доступу необхідні для регламентації права доступу суб'єктів доступу до об'єктів доступу.

Суб'єкт - це активний компонент системи, який може стати причиною потоку інформації від об'єкту до суб'єкта або зміни стану системи.

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

Несанкціонований доступ до інформації характеризуйся порушенням встановлених правил розмежування доступу.

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

1.1.3Конфіденційність, цілісність і доступність в системі

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

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

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

Цілісність компоненту або ресурсу системи - це властивість компоненту або ресурсу бути незмінними в семантичному значенні при функціонуванні системи в умовах випадкових або навмисних спотворень або руйнуючих дій.

Доступність компоненту або ресурсу системи - це властивість компоненту або ресурсу бути доступним для авторизованих законних суб'єктів системи.

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

Уразливість ІС - це деяка невдала властивість системи, яка робить можливим виникнення і реалізацію загрози.

Атака на комп'ютерну систему - це дія, що робиться зловмисником, яке полягає в пошуку і використовуванні тієї або іншої уразливості системи. Таким чином, атака - це реалізація загрози безпеки.

Протидія загрозам безпеки є метою захисту систем обробки інформації.

Безпечна або захищена система - це система із засобами захисту, які успішно і ефективно протистоять загрозам безпеки.

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

Політика безпеки - це сукупність норм, правил і практичних рекомендацій, що регламентують роботу засобів захисту ІС від заданої безлічі загроз безпеки.

1.1.4Класифікація інформації по рівню конфіденційності

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

Пропонується наступна схема класифікації інформації на 4 класи по рівню її конфіденційності.

	Клас	Тип інформації	Опис	Приклади
	0	відкрита	загальнодоступна	інформаційні брошури, відомості, що
		інформація	інформація	публікуються у ЗМІ
			інформація, неприступна у	фінансові звіти і тестова інформація
				за давно минулі періоди, звіти про
		внутрішня	відкритому вигляді, але не
	1			звичні засідання і зустрічі,
		інформація	несуча ніякої небезпеки при
				внутрішній телефонний довідник
			її розкритті
				фірми
				реальні фінансові дані, плани,
		конфіденційна	розкриття інформації веде	проекти, повний набір відомостей
	2			про клієнтів, інформація про колишні
		інформація	до значних втрат на ринку
				і поточні проекти з порушеннями
				етичних норм етичних норм
		секретна	розкриття інформації
	3		призведе до фінансової	(залежить від ситуації)
		інформація
			загибелі компанії

1.2Основні загрози безпеці інформаційних систем

1.2.1Види загроз по меті дії

По меті дії розрізняють три основні типи загроз безпеки ІС:

•загрози порушення конфіденційності інформації;

•загрози порушення цілісності інформації;

•загрози порушення працездатності системи (відмови в обслуговуванні).

Загрози порушення конфіденційності направлені на розголошування

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

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

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

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

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

1.2.2Види загроз по рівню зловмисності

Небезпечні дії на ІС можна підрозділити на випадкові і навмисні.

1.2.2.1Небезпечні випадкові дії

Аналіз досвіду проектування, виготовлення і експлуатації ІС показує, що інформація піддається різним випадковим діям на всіх етапах циклу життя і функціонування ІС.

Причинами випадкових дій при експлуатації ІС можуть бути:

•аварійні ситуації через стихійні біди і відключення електроживлення;

•відмови і збої апаратури;

•помилки в програмному забезпеченні:

•помилки в роботі обслуговуючого персоналу і користувачів;

•перешкоди в лініях зв'язку через дії зовнішнього середовища.

1.2.2.2Небезпечні навмисні дії

1.2.3Групи об'єктів дії

Безпека ІС - безпека її окремих компонент (груп об'єктів дії): апаратні засоби, програмне забезпечення, данні/інформація, персонал.

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

Компоненти ІС можна розбити на наступні групи:

•апаратні засоби - ЕОМ і їх складові частини (процесори, монітори, термінали, периферійні пристрої - дисководи, принтери, контролери, кабелі, лінії зв'язку);

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

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

•персонал - обслуговуючий персонал і користувачі.

1.2.4Шляхи реалізації загроз безпеки інформаційних систем

Проекція трьох видів загроз по меті дії на чотири групи об'єктів дії створює дванадцять загальних шляхів реалізації загроз безпеки ІС.

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

Об'єкти дії	Порушення	Порушення	Порушення
	конфіденційності	цілісності	працездатності
		інформації
Апаратні засоби	підключення;	підключення:	зміна режимів;
	використовування	використовування	висновок з ладу;
	ресурсів; розкрадання	ресурсів;	руйнування
	носіїв	модифікація, зміна
		режимів
Програмне	копіювання;	упровадження	спотворення:
забезпечення	розкрадання:	"троянського коня",	видалення; підміна
	перехоплення	"вірусів", "черв'яків"
Дані	копіювання;	спотворення;	спотворення;
	розкрадання:	модифікація	видалення: підміна
	перехоплення
Персонал	Розголошування;	"Маскарад";	"Маскарад";
	передача відомостей	вербування; підкуп	вербування; підкуп
	про захист; халатність	персоналу	персоналу

Лекція 2 Політика безпеки інформаційних систем

2.1Фрагментарний і комплексний підходи в забезпеченні безпеки

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

Існують два підходи до проблеми забезпечення безпеки ІС:

•"фрагментарний"

•комплексний.

2.1.1Фрагментарний підхід в забезпеченні безпеки

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

Превагою такого підходу є висока вибірковість до конкретної загрози.

Істотним недоліком даного підходу є відсутність єдиного захищеного середовища обробки інформації. Фрагментарні заходи захисту інформації забезпечують захист конкретних об'єктів ІС тільки від конкретної загрози. Навіть невелика видозміна загрози веде до втрати ефективності захисту.

2.1.2Комплексний підхід в забезпеченні безпеки

Комплексний підхід орієнтований на створення захищеного середовища обробки інформації в ІС, об'єднуючої в єдиний комплекс різнорідні заходи протидії загрозам.

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

До недоліків цього підходу відносяться:

•обмеження на свободу дій користувачів ІС;

•велика чутливість до помилок установки і настройки засобів захисту;

•складність управління.

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

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

2.2Політика безпеки інформаційних систем

2.2.1Поняття політики безпеки

Комплексний підхід до проблеми забезпечення безпеки заснований на розробленій для конкретної ІС політиці безпеки.

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

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

Політика безпеки визначається способом управління доступом, що визначає порядок доступу до об'єктів системи.

2.2.2Виборча політика безпеки

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

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

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

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

2.2.3Повноважна політика безпеки

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

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

•всі суб'єкти і об'єкти системи однозначно ідентифіковані:

•кожному об'єкту системи привласнена мітка конфіденційності інформації, яка визначає цінність інформації, що міститься в ньому;

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

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

Основним призначенням повноважної політики безпеки є:

•регулювання доступу суб'єктів системи до об'єктів з різними рівнями конфіденційності

•запобігання просочування інформації з верхніх рівнів посадової ієрархії на

нижні

•блокування можливих проникнень з нижніх рівнів на верхні.

2.2.4Розробка політики безпеки

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

2.2.4.1Напрями розробки політики безпеки

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

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

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

Основні напрями розробки політики безпеки :

•визначення які дані і наскільки серйозно необхідно захищати;

•визначення хто і який збиток може нанести фірмі в інформаційному аспекті;

•обчислення ризиків і визначення схеми зменшення їх до припустимої величини.

2.2.4.2Оцінка поточної ситуації

Існують дві системи оцінки поточної ситуації в області інформаційної безпеки на підприємстві.

Вони одержали образні назви "дослідження від низу до верху" і "дослідження зверху вниз".

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

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

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

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

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

2.2.4.3Визначення джерел загроз і розмірів збитку

Далі слідує з'ясування наскільки серйозний збиток може принести фірмі розкриття або інша атака на кожний конкретний інформаційний об'єкт. Цей етап носить назву "Обчислення ризиків". В першому наближенні ризиком називається віднощення

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

Збиток від атаки може бути представлений ненегативним числом в приблизній відповідності з наступною таблицею :

	Величина	Опис
	збитку

0 Розкриття інформації принесе нікчемний моральний і фінансовий збиток фірмі

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

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

3 Значні втрати на ринку і в прибутку. Від фірми йде відчутна частина клієнтів

4Втрати дуже значні, фірма на період до року втрачає положення на ринку. Для відновлення положення потрібні крупні фінансові позики.

5 Фірма припиняє існування

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

Вірогідність	Середня частота появи
0	Даний вид атаки відсутній
1	рідше, ніж раз на рік
2	близько 1 разу на рік
3	близько 1 разу на місяць
4	близько 1 разу на тиждень
5	практично щоденно

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

2.2.4.4Аналіз ризиків

Наступним етапом складається таблиця ризиків підприємства. Вона має наступний вигляд:

	Опис атаки	Збиток	Вірогідність	Ризик (=Збиток* Вірогідність)
	Спам (переповнювання поштового	1	4	4
	ящика)
	Копіювання жорсткого диска	3	1	3
	з центрального офіса
	...	...	...	2
			Разом :	9

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

ризику цього значення. Якщо таке перевищення має місце, значить, даний рядок – це одна

зпершочергових цілей розробки політики безпеки. Потім проводиться порівняння подвоєного значення (в нашому випадку 7*2=14) з інтегральним ризиком ("Разом"). Якщо інтегральний ризик перевищує допустиме значення, значить, в системі набирається множина дрібних похибок в системі безпеки, які в сумі не дадуть підприємству ефективно працювати. В цьому випадку з рядків вибираються ті, які дає найзначніший внесок в значення інтегрального ризику і проводиться спроба їх зменшити або усунути повністю.

2.3Система захисту інформаційних систем

2.3.1Процес побудови системи захисту

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

Процес побудови системи захисту включає наступні етапи:

•аналіз можливих загроз ІС;

•планування системи захисту;

•реалізація системи захисту;

•супровід системи захисту.

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

На етапі планування формується система захисту як єдина сукупність заходів протидії загрозам різної природи. Результатом етапу планування є розгорнений план захисту ІС, що містить:

•перелік компонентів ІС і можливих дій, які захищаються;

•мета захисту інформації в ІС;

•правила обробки інформації в ІС, що забезпечують її захист від різних дій;

•опис планованої системи захисту інформації.

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

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

2.3.2 Заходи забезпечення безпеки комп'ютерних систем

2.3.2.1 Адміністративні заходи захисту

На етапі планування формується система захисту як єдина сукупність заходів протидії загрозам різної природи.

За способами здійснення всі заходи забезпечення безпеки комп'ютерних систем підрозділяють на:

•морально-етичні;

•правові (законодавчі);

•адміністративні;

•фізичні;

•апаратно-програмні.

Перераховані заходи безпеки ІС можна розглядати як послідовність бар'єрів або рубежів захисту інформації. Для того, щоб дістатися до інформації, що захищається, потрібно послідовно подолати декілька рубежів захисту. Розглянемо їх докладніше.

2.3.2.1Морально-етичні заходи захисту

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

іоформленими в якесь зведення правил або розпоряджень. Наприклад, "Кодекс професійної поведінки членів Асоціації користувачів ЕОМ США" розглядає як неетичні дії, які умисне або ненавмисно:

•порушують нормальну роботу комп'ютерних систем;

•викликають невиправдані витрати ресурсів (машинного часу, пам'яті, каналів зв'язку

іт.п.);

•порушують цілісність інформації (яка зберігається або обробляється);

•порушують інтереси інших законних користувачів і т.п.

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

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

Прикладом угоди для доступу до комп'ютерів може служити документ такого роду

для факультету інформатики університету Мельбурну. Дивися також http://www.admin.com.

Я, що підписався нижче, теперішнім часом оголошую, що дотримуватимуся приведених нижче правил:

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

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

•Я не здійснюватиму доступ або спробу доступу ні до одного комп'ютера, реєстраційного запису, мережі або файлу без відповідного і явного дозволу. Такий доступ

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

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

•Я не використовуватиму університетські ресурси для отримання, розробки, запуску

ірозповсюдження неліцензійного програмного забезпечення.

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

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

•Я розумію, що дії, які суперечать викладеним вище принципам, спричиняють за собою жорсткі стягнення, включаючи відмову у вивченні теми або предмету, тимчасову заборону або позбавлення доступу до університетських обчислювальних засобів, тимчасове або повне виключення з університету, штраф та/або інші дії, передбачені Crimes Computer Act (цей закон діє в Австралії, але аналогічні закони є в багатьох інших країнах) 1988 року.

2.3.2.2 Правові засоби захисту

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

2.3.2.4 Адміністративні заходи захисту

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

Адміністративні заходи захисту відносяться до заходів організаційного характеру. Вони регламентують:

•процеси функціонування ІС:

•використання ресурсів ІС;

•діяльність персоналу ІС;

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

Адміністративні заходи включають:

•розробку правил обробки інформації в ІС;

•сукупність дій при проектуванні і устаткуванні обчислювальних центрів і інших об'єктів ІС (облік впливу стихії, пожеж, охорона приміщень і т.п.);

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

•організацію надійного пропускного режиму;

•організацію обліку, зберігання, використання і знищення документів і носіїв з конфіденційною інформацією;

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

•організацію прихованого контролю за роботою користувачів і персоналу ІС;

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

Важливо відзначити, що, поки не будуть реалізовані дієві заходи адміністративного захисту ЕОМ, інші заходи будуть неефективні.

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

2.3.2.5 Фізичні засоби захисту

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

2.3.2.6 Апаратно-програмні засоби захисту

П'ятим рубежем є апаратно-програмні засоби захисту.

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

•ідентифікацію (розпізнавання) і аутентифікацію (перевірка достовірності) суб'єктів (користувачів, процесів) ІС;

•розмежування доступу до ресурсів ІС;

•контроль цілісності даних;

•забезпечення конфіденційності даних;

•реєстрацію і аналіз подій, що відбуваються в ІС:

•резервування ресурсів і компонентів ІС.

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

2.4Принципи проектуванні ефективної системи захисту

До числа принципів проектування ефективної системи захисту відносяться наступні:

•економічна ефективність - вартість засобів захисту повинна бути менше ніж розміри можливого збитку.

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

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

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

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

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

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

•звітність і підконтрольність - система захисту повинна надавати докази коректності своєї роботи.

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

•ізоляція і розділення -об`єкти захисту доцільно розділяти на групи так, щоб порушення захисту в одній з груп не впливало на безпеку інших груп.

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

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

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

•залучення людини - найважливіші і критичні рішення повинно ухвалюватися людиною.

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

Лекція 2 Традиційні симетричні криптоалгоритми

Розглядається історія розвитку науки криптографії із стародавніх часів до середини 20го століття. Представлені алгоритми шифрування, що відносяться до методів перестановки, методів одноалфавітної і багатоалфавітної підстановки (заміни). Описуються механізми автоматизації процесу шифрування/розшифровки, що використовувалися наприкінці 19го століття в першій половині 20го століття (телеграф Вернама, машина Енігма).

Вступ

Більшість засобів захисту інформації базується на використовуванні криптографічних шифрів і процедур шифрованиярасшифрования. Відпові дно до стандарту ГОСТ 2814789 під шифром розуміє сукупність оборотних преобразований безліч відкритих даних на безліч зашифрованих даних, що задаються ключем і алгоритмом криптографічного перетворення.

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

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

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

•достатня криптостойкость (надійність закриття даних);

•простота процедур шифрування і расшифрования;

•незначна надмірність інформації за рахунок шифрування;

•нечутливість до невеликих помилок шифрування і ін.

Утій чи іншій мірі цим вимогам відповідають:

• шифри перестановок;

• шифри заміни;

• шифри гамування.

Шифрування перестановкою полягає в тому, що символи шифрованого тексту

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

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

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

4.1 Методи перестановки

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

Вступ

Шифруючі таблиці (маршрутна перестановка)

Зпочатку епохи Відродження (кінець XIV сторіччя) починає відроджуватися і криптографія.

Крок 2. Букви відкритого тексту заносяться в таблицю по стовпцях зверхувниз, взліванаправо.

Крок 3. Кожен стовпець нумерується у відповідності із значенням ключа Крок 4. Стовпці таблиці сортуються у відповідності з порядковим номером. Крок 5. З таблиці считуються букви по рядках взліванаправо, зверхувниз та

формується шифртекст.

Втаблиці 4.1.2.2 представлено вміст таблиці після кроку 4. Таблиця. 4.1.2.2 Перестановка стовпців таблиці

1	2	3	4	5	6	7
Р	О	К	_	К	Щ	Р
А	_	А	В	А	А	И
_	К	Ф	С	Ф	_	_
С	Р	Е	І	Е	З	_
П	А	Д	_	Д	А	_

Після кроку 5 шифртекст буде мати значення

РОК_КЩРА_АВААИ_КФСФ__СРЕІЕЗ_ПАД_ДА_

Алгоритм розшифровки має наступні кроки.

Крок 1. Взяти шифруючу таблицю деякої розмірності (може бути відкритим значенням).

Крок 2. Букви шифртексту заносяться в таблицю по рядках взліванаправо, зверху

вниз.

Крок 3. У відповідності із значенням елементів ключа виконується перестановка стовпців між собою за таким правилом: iй стовпець таблиці переходить на позицію, яку має елемент ключа зі значенням i

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

4.1.3 Подвійна перестановка за ключем

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

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

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

Алгоритм шифрування має наступні кроки.

Крок 1. Взяти шифруючу таблицю деякої розмірності (може бути відкритим значенням).

Крок 2. Букви відкритого тексту заносяться в таблицю по стовпцях зверхувниз, взліванаправо.

Крок 3. Кожен стовпець нумерується у відповідності із значенням першого ключа. Крок 4. Кожен рядок нумерується у відповідності із значенням другого ключа. Крок 5. Стовпці таблиці сортуються у відповідності з порядковим номером.

Крок 6. Рядки таблиці сортуються у відповідності з порядковим номером.

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

Для прикладу візьмемо повідомлення КАФЕДРА СПО КР АЩА ЗА ВСІ КАФЕДРИ. В якості ключа візьмемо: перший ключ 3126457, други й ключ 32154.

Втаблиці 4.1.3.1 показано заповнення текстом повідомлення і ключовим кодовим

словом.

Таблиця. 4.1.3.1 Заповнення ключовим словом та текстом

	3	1	2	6		4		5	7
3	К	Р	О	Щ		_		К	Р
2	А	А	_	А		В		А	И
1	Ф	_	К	_		С		Ф	_
5	Е	С	Р	З		І		Е	_
4	Д	П	А	А		_		Д	_
В таблиці 4.1.3.2 представлено вміст таблиці після кроку 5.
Таблиця. 4.1.2.2 Перестановка стовпців таблиці
	1	2	3	4		5		6	7
3	Р	О	К	_		К		Щ	Р
2	А	_	А	В		А		А	И
1	_	К	Ф	С		Ф		_	_
5	С	Р	Е	І		Е		З	_
4	П	А	Д	_		Д		А	_

В таблиці 4.1.2.3 представлено вміст таблиці після кроку 6.

Таблиця. 4.1.2.3 Перестановка стовпців таблиці

	1	2	3	4	5	6	7
1	_	К	Ф	С	Ф	_	_
2	А	_	А	В	А	А	И
3	Р	О	К	_	К	Щ	Р
4	П	А	Д	_	Д	А	_
5	С	Р	Е	І	Е	З	_

По завершенню роботи алгоритму шифртекст буде мати значення _КФСФ__А_АВААИРОК_КЩРПАД_ДА_СРЕІЕЗ_

Алгоритм розшифровки має наступні кроки.

Крок 1. Взяти шифруючу таблицю деякої розмірності (може бути відкритим значенням).

Крок 2. Букви шифртексту заносяться в таблицю по рядках взліванаправо, зверху

вниз.

Крок 3. У відповідності із значенням елементів ключа виконується перестановка рядків між собою за таким правилом: iй рядок таблиці переходить на позицію, яку має елемент другого ключа зі значенням i

Крок 4. У відповідності із значенням елементів ключа виконується перестановка стовпців між собою за таким правилом: iй стовпець таблиці переходить на позицію, яку має елемент першого ключа зі значенням i

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

Число варіантів подвійної перестановки швидко зростає при збільшенні розміру таблиці:

•для таблицы 3x3 36 варіантів;

•для таблицы 4x4 576 варіантів;

•для таблицы 5x5 14400 варіантів.

4.1.4Використання "магічних" квадратів

Всередньовіччі для шифрування перестановкою застосовувалися і "магічні" квадрати. Магічними квадратами квадратні таблиці з вписаними в їх клітини послідовними

натуральними числами, починаючи від 1, які дають в сумі по кожному стовпцю, кожному рядку і кожній діагоналі одне і те ж число.

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

Втаблиці 4.1.4.1 наведено приклад магічного квадрату 4x4 Таблиця 4.1.4.1 Приклад магічного квадрату 4x4

	16	3	2	13
	5	10	11	8
	9	6	7	12
	4	15	14	1

Текст повідомлення візьмемо з попереднього прикладу: СПЗ НАЙКРАЩА!. Для шифрування необхідно пронумерувати букви вхідного тексту у відповідності з їхнім порядковим номером, що відображено у таблиці 4.1.4.2.

С	П	З		Н	А	Й	К	Р	А	Щ	А	!	_	_	_
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16

Після внесення букв повідомлення у клітини таблиці, номер яких співпадає з порядковим номером букв, вміст таблиці буде мати вигляд як у таблиці 4.1.4.3.

Таблиця 4.1.4.3 Приклад заповнення магічного квадрата повідомленням

	_	З	П	!
	Н	А	Щ	К
	Р	А	Й	А
		_	_	С

Після считування з таблиці букви по стовпцях зверхувниз, взліванаправо формується шифртекст

_НРЗАА_ПЩЙ_!КАС

Число магічних квадратів швидко зростає із збільшенням розміру квадрата. Існує тільки один магічний квадрат розміром 3x3 (якщо не враховувати його повороти). Кількість магічних квадратів 4x4 складає вже 880, а кількість магічних квадратів 5x5 біля 250000.

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

4.2 Методи заміни

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

Вступ

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

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

шифрами одноалфавітної підстановки.

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

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

Багатоалфавітні шифри заміни запропонував і ввів в практику криптографії Леон Батист Альберті, який також був відомим архітектором і теоретиком мистецтва. Його книга "Трактат про шифр", написана в 1566 р. була першою в Європі науковою працею з криптології. Окрім шифру багатоалфавітної заміни, Альберті також детально описав пристрої

зколіс, що обертаються, для його реалізації. Криптологи всього світу почитають Л.Альберті основоположником криптології.

4.2.1Методи простої заміни

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

4.2.1.1.Полібіанській квадрат

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

Таблиця 4.2.1.1 Полібіанський квадрат 6X6 з українським алфавітом

	В	І	_		Ш
Г		А	И	Е	Ї
М	Б	С	Ч	П	Ж
У	К	Т	Д	Р	Є
Л	Х	З	Ю	О	Щ
Й	Н		Ф		Я

Алгоритм шифрування має наступні кроки.

Крок 1. Отримати ключ шифрування в якості полібіанського квадрату з випадковим

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

Наведемо приклад шифрування для повідомлення = КАФЕДРА. Процес заміни наведено на рисунку 4.2.1.1

Рис. 4.2.1.1 Процес зміни символів при шифруванні

Врезультаті шифрування сформовано шифртекст = ХС_ПЮОС Алгоритм рошифрування має наступні кроки.

Крок 1. Отримати ключ шифрування в якості полібіанського квадрату з випадковим

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

4.2.1.2 Система шифрування Цезаря

Шифр Цезаря є окремим випадком шифру простої заміни (одноалфавітної підстановки). Свою назва цей шифр одержав на ім'я римського імператора Гая Юлія Цезаря, який використовував цей шифр при листуванні з Цицероном (близько 50 р. до н.е.).

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

Наприклад, послання Цезаря VENI VID1 VICI (у перекладі на українську означає

"Прийшов, Побачив, Переміг") направлене його другові Амінтію після перемоги над понтійским царем Фарнаком, сином Мітрідата, виглядало б в зашифрованому вигляді так:

YHQL YLGL YLFL

Наведемо приклад шифрування для відкритого тексту = КАФЕДРА з K=3, окремі кроки якого представлено на рисунку 4.2.1.2

Рис. 4.2.1.2 Окремі кроки роботи алгоритму шифрування Цезаря

Перевагою системи шифрування Цезаря є простота шифрування і розшифрування. До недоліків системи Цезаря слід віднести наступні:

•підстановки, виконувані відповідно до системи Цезаря немакують частоту появи різних букв початкового відкритого тексту;

•зберігається алфавітний порядок в послідовності букв, що заміняються; при зміні значення К змінюються тільки початкові позиції такої послідовності;

•число можливих ключів К мало;

•шифр Цезаря легко розкривається на основі аналізу частот появи букв в

шифртексті.

4.2.1.3Афінна система підстановок Цезаря

Всистемі шифрування Цезаря використовувалися тільки адитивні властивості множини цілих Zm. Проте символи множини Zm можна також множити за модулем т. Застосовуючи одночасно операції складання і множення за модулем т над елементами множини Zm, можна отримати систему підстановок, яку називають афінною системою підстановок Цезаря.

Eab(t) = at + b (mod m), де а,b цілі числа, 0 < а,b < m, НЗД(а,m) = 1 (НЗД функція найбільшого загального дільника)

Потрібно помітити, що перетворення Eab(t) є взаємно однозначним відображенням на множині Zm тільки у тому випадку, якщо найбільший загальний дільник чисел а та m рівний одиниці, тобто а та m повинні бути взаємно простими числами.

Наприклад, нехай m = 26, а 3, b 5. Тоді, очевид но, НЗД (3,26) 1, і ми одержуємо відповідність між числовими кодами букв, яка представлена у таблиці 4.2.1.3.1

Таблиця 4.2.1.3.1

t	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21		22		23		24		25
3t+5	5	8	11	14	17	20	23	0	3	6	9	12	15	18	21	24	1	4	7	10	13	16		19		22		25		2

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

Таблиця 4.2.1.3.2

A

B

C

D

E

F

C

H

S

J

K

L

V

N

O

P

Q

R

S

T

И

V

W

X

Y

F

I

L

O

R

И

X

A

D

G

J

M

P

S

V

Y

B

E

H

K

N

Q

T

W

Z

Початкове повідомлення НОРЕ перетвориться в шифртекст AVYR

Перевагою афінної системи є зручне управління ключами ключі шифрування і розшифрування представляються в компактній формі в виді пари чисел (а, b).

Недоліки афінної системи аналогічні недолікам системи шифрування Цезаря. Аффінная система використовувалася на практиці декілька століть тому, а сьогодні її

вживання обмежується переважно ілюстраціями основних криптологічних положень.

4.2.1.4 Система Цезаря з ключовим словом

Система шифрування Цезаря з ключовим словом є одноалфавітною системою підстановки. Особливістю цієї системи є використання ключового слова для зсуву і зміни порядку символів в алфавіті підстановки.

4.2.1.8 Біграмний шифр Плейфейра

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

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

Плейфейр розширив метод Трісемуса, який першим помітив, що можна шифрувати по дві букви за раз. Такі шифри були названі біграмними.

Найбільш відомий шифр з біграмами називається Playfair. Він застосовувався Великобританією в Першу світову війну.

Алгоритм шифрування складається з наступних кроків.

Крок 1. Вписати в таблицю розміром, достатнім для розміщення всіх літер алфавіту, по рядках ключове слово, при цьому букви, що повторюються, відкидати.

Крок 2. Таблицю доповнити літерами алфавіту, що не увійшли до неї раніше. Крок 3. Відкритий текст розбити на пари букв (біграми).

Крок 4. Текст шифровки будувати за двома правилами:

1.Якщо обидві букви біграми відкритого тексту належать одному стовпцю таблиці, то буквами шифру вважати букви, які лежали під ними. Якщо буква відкритого тексту знаходилася в нижнем ряду, то для шифру бралася відповідна буква из верхнего ряда.

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

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

Шифруваннф біграмами різко посилило стійкість шифрів до розкриття..

4.2.2Методи складної заміни

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

4.2.2.1. Шифр Гронсфельда

Цей шифр складної заміни, названий шифром Гронсфельда, є модифікацією шифру Цезаря з числовим ключем.

Алгоритм шифрування складається з наступних кроків.

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

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

Алгоритм рошифрування складається з наступних кроків.

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

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

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

різними числовими ключами.

Шифр Гронсфельда є по суті окремим випадком системи шифрування Віжінера.

4.2.2.2 Система шифрування Віжінера

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

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

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

Таблиця 4.2.2.2 Таблиця Віжінера

Kлюч ki \

А

Б

В

Г

Д

Е

Ж

З

І

К

Л

...

Ю

Я

буква mi

А

Я

А

Б

В

Г

Д

Е

Ж

З

І

К

...

Ю

Б

Ю

Я

А

Б

В

Г

Д

Е

Ж

З

І

В

Г

...

Я

Математично перетворення в шифрі Віжінера можна представити у вигляді

Ci = (Mi + Ki ) mod n,

де Ci код зашифрованої iї букви тексту; Mi код iї букви відкритого тексту;

Ki код iї букви ключа;

nкількість букв алфавіту.

4.2.2.3 Шифр "подвійний квадрат" Уітстона

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

Назва шифр отримав по аналогії з полібіанським квадратом. На відміну від полібіанського, подвійний квадрат використовує відразу дві таблиці, які розташовані по горизонталі, а шифрування йде біграмами, як у шифрі Playfair. Ці, здавалося б і не такі вже значні зміни призвели до появи на світ нової криптографічної системи ручного шифрування. Вона виявилася така надійна і зручна, шо застосовувалася вже німцями навіть в роки другої світової війни. По відгуку її творця шифрування подвійним квадратом досить просте і цого "можна довірити навіть дипломатам". Приклад таблиць Уітстона представлено на рисунку 4.2.2.3

Рис. 4.2.2.3 Підвійний квадрат Уітстона

Алгоритм шифрування складається з наступних кроків. Крок 1 Для шифрування повідомлення розбити на біграми. Крок 2. Взяти поточну біграму.

Крок 3. Першу букву біграми знайти в лівій таблиці, а другу в правій. Крок 4. Визначити біграму шифртесту за правилом:

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

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

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

Лекція Основи криптоаналізу

1 Причини криптоаналізу

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

Рис.1 - Схема симетричної криптосистеми

Рис.2 - Схема асиметричної криптосистеми

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

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

2 Фундаментальне правило криптоаналізу

Фундаментальне правило криптоаналізу, вперше сформульоване голландцем А.Керкхоффом ще в XIX столітті, полягає в тому, що стійкість шифру (криптосистеми) повинна визначатися тільки секретністю ключа. Іншими словами, правило Керкхоффа полягає в тому, що весь алгоритм шифрування, окрім значення секретного ключа, відомий

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

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

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

3 Основні типи криптоаналітичних атак

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

Криптоаналітична атака за наявності тільки відомого шифртекста. Криптоаналітик має тільки шифртексти C1, C2 ...Сi декількох повідомлень, причому всі вони зашифровані з використанням одного і того ж алгоритму шифрування Ek. Робота криптоаналітика полягає в тому, щоб розкрити початкові тексти M1, M2 ..., Мi, по можливості більшості повідомлень або, ще краще, обчислити ключ К, використаний для шифрування цих повідомлень, з тим, щоб розшифрувати і інші повідомлення, зашифровані цим ключем.

Криптоаналітична атака за наявності відомого відкритого тексту. Криптоаналітик має доступ не тільки до шифртекстів C1, C2 ...Сi декількох повідомлень, але також до відкритих текстів M1, M2 ..., Мi цих повідомлень. Його робота полягає в знаходженні ключа K, що використовується при шифруванні цих повідомлень, або алгоритму расшифрования Dк будь-яких нових повідомлень, зашифрованих тим же самим ключем.

Криптоаналітична атака при нагоді вибору відкритого тексту. Криптоаналітик не тільки має доступ до шифртекстів C1, C2 ...Сi і пов'язаним з ними відкритим текстам M1, M2

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

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

Лекція Потокові криптоалгоритми

Наведено порівняльну характеристику блокових і потокових криптоалгоритмів. Розглядається створення потокових криптоалгоритмів на основі генераторів псевдовипадкових чисел. Описуються вимоги по створенню криптостойких генераторів. Представлено генератор на основі регістру зсуву з лінійними зворотними зв'язками (LFSR Linear Feedback Shift Register). Розглядаються потокові шифри на основі LFSR ( алгоритм A5 з системи GSM (Group Special Mobile)). Наведено алгоритм RC4.

1 Концепція проектування потокових криптоалгоритмів

1.1 Блокові і потокові криптоалгоритми

Блокові шифри володіють істотним недоліком вони р озмножують помилки, що виникають

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

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

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

1.2 Схема однократного використання Вернама

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

Для шифрування віткритого тексту формується mрозря дна випадкова послідовність ключ шифра.

Відправник виконує побітове складання за модулем два ключа k = k1 k2 k3 ... ki ... kn

та mрозрядною послідовністю m = m1 m2 m3 ...mi ... mn

яка відповідає шифртексту

ci = mi ki

де mi, ki, ci iй біт, відповідно, відкритого тексту, ключа та шиф ртексту, n число біт відкритого тексту

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

mi = ci ki

Схема однократного використання Вернама представлена на рисунку 7.1.2

Рис. 7.1.2 Схема однократного використання Вернама

1.3 Абсолютно криптостійкі шифри

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

Необхідні та достатні умови абсолютної стійкості шифру:

•повна випадковість ключа;

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

•однократне використання ключа.

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

Тому для побудови ефективної криптосистеми необхідно відмовитися від поняття абсолютної криптостійкости.

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

Гамування це процедура накладення за допомогою деякої функ ції F на вхідну послідовність гами шифру.

Гама шифру псевдовипадкова послідовність (ПСП), сформована генератором ПСП.

Схема роботи процедури гаммирования представлена на малюнку 7.1.3

Рис. 1.7.3 Схема роботи процедури гамування, Gg г енератор гами шифру, G гама шифру, F, F1 лінійна або нелінійна функція гамування і зворот на їй, відповідно.

2 Генератори псевдовипадкових чисел

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

Одержувані програмно з ключа, випадкові або псевдовипадкові ряди чисел називаються гамою, по назві букви грецького алфавіту, якій в математичних записах позначаються випадкові величини. Цікаво відзначити, що в книзі "Незнайомці на мосту", написаної адвокатом розвідника Абеля, наводиться термін гама, який фахівці ЦРУ помітили коментарем "музична вправа?", тобто в п'ятдесяті роки вони не знали його значення.

Фізичне моделювання випадковості за допомогою таких фізичних явищ, як радіоактивне випромінювання, шум дробу в електронній лампі або тунельний пробій напівпровідникового стабілітрона не дають справжніх випадкових процесів. Хоча відомі випадки вдалих вживань їх в генерації ключів, наприклад, в російському криптографічному пристрої КРИПТОН. Тому замість фізичних процесів для генерації гами застосовують програми для ЕОМ, які хоча і називаються генераторами випадкових чисел, але насправді видаючі детерміновані числові ряди, які тільки здаються випадковими по своїх властивостях. Від них вимагається, щоб, навіть знаючи закон формування, але не знаючи ключа у вигляді початкових умов, ніхто не зміг би відрізнити числовий ряд від випадкового, неначе він отриманий киданням ідеальних гральних кісток. Можна сформулювати три основні умови до криптографічного стійкого генератора псевдовипадкової послідовності або гамми:

1.Період гамми повинен бути достатньо великим для шифрування повідомлень різної довжини.

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

3.Генерація гами не повинна бути пов'язана з великими технічними і організаційними труднощами.

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

Друга проблема полягає в наступному: на підставі чого можна зробити висновок, що гамма конкретного генератора є непередбачуваною? Поки в світі немає ще універсальних і практично перевіряються критеріїв, що дозволяють затверджувати це. Невідома і загальна теорія криптоаналізу, яка могла б бути застосована для такого доказу, за винятком все зростаючої кількості конкретних елементів аналізу, вироблених для різних практичних цілей. Інтуїтивно випадковість сприймається як непередбачуваність. Щоб гама вважалася випадковою, як мінімум необхідно, щоб її період був дуже великим, а різні комбінації біт певної довжини рівномірно розподілялися по всій її довжині. Отже, друга вимога до ряду полягає в підтверджуваній статистично подібності його властивостей справжньої випадкової вибірки. Кожний порядок елементів гамми повинен бути так само випадковий, як і будьхто інший.

2.2 Найпростіші алгоритми генерації

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

Yn = Ent (a*n+b)

Найстародавніший обчислювальний спосіб генерації псевдовипадкових чисел на ЕОМ належить Джону фон Нейману і відноситься до 1946 року. Цей спосіб базувався на тому що кожне подальше випадкове число утворюється зведенням попереднього в квадрат і відкиданням цифр з обох кінців. Спосіб Неймана виявився ненадійним і дуже швидко від нього відмовилися.

Знайпростіших процедур, що імітують випадкові числа, найбільш вживаємим є так званий конгруентний спосіб, приписуваний Д.Х. Лемеру:

G(n+1)=KGn+C MOD M

Уньому кожне подальше псевдовипадкове число G(n+1) виходить з попереднього Gn множенням його на K, складанням із C і взяттям залишку від розподілу на М. Весь фокус тут в тому, щоб підібрати хороші значення К, С і М, на що були витрачені десятиріччя роботи математиків. Підбір майже ірраціональних К нічого не дає. Наприклад, вибравши закон генерації послідовності G(N+1)= Ent(sqr(2)*Gn) на IBM PC при форматі представлення чисел з плаваючою комою IEEE в 4 байти, одержимо псевдовипадкові ряди, що обов'язково закінчуються циклами з періодами завдовжки всього лише 1225 і 147 залежно від початкового заповнення.

3 Потокові шифри на основі генератора з LFSRрегіс тром

3.1 Генератор з LFSRрегістром

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

Здвиговий регістр із зворотнім зв'язком, представлений на рисунку 7.3.1, складається з двох частин:

•здвиговий регістр;

•функція зворотнього зв'язку.

Здвиговый регістр є послідовністю бітів. Кількість бітів визначається довжиною здвигового регістра.

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

Періодомздвигового регістра зветься довжина одержуваної послідовності до початку її повторення.

Рис.7.3.1 Здвиговый регістр із зворотнім зв`язком

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

Найпростішим виглядом здвигового регістром зі зворотнім зв'язком є лінійний здвиговий регістр зі зворотнім зв'язком (linear feedback shift register, або LFSR) представленній на рисунку 7.3.2. Зворотній зв'язок є просто

XOR окремих бітів регістра, перелік цих бітів зветься відводною послідовністю (tap sequence). Іноді такий регістр зветься конфігурацією Фібоначі.

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

Рис. 3.2 Здвиговий регістр с лінійними зворотніми зв'язками

На рисунку 3.3 показано 4бітовий LFSR з відведення м від першого і четвертого бітів.

Якщо його проініціалізувати значенням 1111, то до повторення регістр прийматиме наступні внутрішні полягання:

1 1 1 1

0 1 1 1

1 0 1 1

0 1 0 1

1 0 1 0

1 1 0 1

0 1 1 0

0 0 1 1

1 0 0 1

0 1 0 0

0 0 1 0

0 0 0 1

1 0 0 0

1 1 0 0

1 1 1 0

Рис. 3.3 4бітовий LFSR
Вихідною			послідовністю				буде		рядок		молодших			значущих		бітів:
1	1	1	1	0	1	0	1	1	0	0	1	0	0	0.	.	.	.

nбітовий LFSR може знаходитися в одному з 2 n 1 внутрішніх полягань. Це означає, що теоретично

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

Отриманий результат назівається Мпослідовністью .

Для того, щоб LFSR мав максимальний період, багаточлен утворений з від однієї послідовності і константи 1, повинен бути примітивним по модулю 2. Ступінь багаточлена є довжиною здвигового регістра. Примітивний багаточлен ступеня n це багаточлен, який, що не приводиться є дільником x2n1 +1, але не є дільником xd+1 для всіх d, що є дільниками

2n1. Наприклад, для LFSR з рисунку 7.3.3 примітивний багаточлен матиме вигляд:

F(x) = x4 + x + 1

Програмні реалізації LFSR повільні і швидше працюють, якщо написані на асемблері, а не на С.

Одним з рішень є використання паралельно 16 LFSR (або 32, в залежності від довжини слова комп'ютера). В цій схемі використовується масив слів, розмір якого дорівнює довжині LFSR,

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

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

Рис. 3.4 LFSR Галуа

Виграш полягає в тому, що всі XOR можна зробити за одну операцію. Ця схема також може бути розпаралеленою, а поліноми різних зворотніх звязків можуть бути різні. Така конфігурація Галуа може дати виграш і при апаратній реалізації, особливо у вигляді СБІС. Вообще, при використанні апаратури, яка добре виконує зсуви застосовуйте конфігурацію Фібоначі, якщо є можливість використати паралелізм, застосовуйте конфігурацію Галуа.

3.2 Алгоритм роботи потокового шифру

Алгоритм шифрування потоковим шифром містить наступну послідовність кроків Крок 1. Кодування букв відкритого тексту M = {m1, m2, m3, ..., mi, ..., mn}.

Крок 1.1 Вибір таблиці кодування.

Крок 1.2 Переклад букв відкритого тексту на основі таблиці кодування у коди десятичної системи числення.

Крок 1.3 Переклад у двійкову систему числення.

Крок 2. Вибір формули образуючого багаточлена. Крок 3. Вибір ключа шифрування.

Крок 4. Генерація гами шифра G = {g1, g2, g3, ..., gi, ..., gn}.

Крок 5. Шифрування букв відкритого тексту C = {c1, c2, c3, ..., ci, ..., cn}.

ci= gi mi

Алгоритм шифрування потоковим шифром містить наступну послідовність кроків Крок 1. Отримання формули образуючого багаточлена та ключа шифрування.

Крок 2. Генерація гами шифра G = {g1, g2, g3, ..., gi, ..., gn}.

Крок 3. Розшифрування букв шифртексту M= {m1, m2, m3, ..., mi, ..., mn}

mi= gi ci

Крок 4. Розкодування букв відкритого тексту M= {m1, m2, m3, ..., mi, ..., mn}. Крок 4.1 Отримання таблиці кодування.

Крок 4.2 Переклад двійкових кодів mi у десятичну систему числення

Крок 4.3 Переклад кодів mi на основі таблиці кодування у букви відкритого тексту.

3.3Приклад роботи алгоритму Умови задачі

Використовуючи поточний шифр, виконати процедуру шифрування/розшифрування

блока тексту M = {M1, M2, M3}, де Mi = код i+1 букви прізвища. Кодування букв прізвища провести у відповідності з таблицею

АБ … Я

1 2 … 32 При генерації гами шифру використовувати 5разрядни й здвиговий регістр зі зсувом

праворуч.

Нумерація бітів 0,1,2,3, 4 зправа на ліво. Значення вектора ініціалізації IV = код останньої букви прізвища.

Номер біта обратного зв`язку = (M4 mod 4) + 1. Рішення задачі

1. На підставі варіанту визначимо початкові дані.

Оскільки прізвище = "БАРАНОВСЬКІЙ", то необхідно виконати шифрування/розшифровку послідовності ‘АРА’.

Для здвигового регістра номер біта зворотнього зв'язку = (M4 mod 4) +1 = код(Н) mod 4 + 1= 2 +1 = 3

Вектор ініціалізації IV = код(“Й”)= 10 = 8 + 2 = 010102

2. Закодуємо послідовність:

А(1) БВГД(5) ЕЖЗІЙ(10) КЛМНО(15) ПРСТУ(20) ФХЦЧШ(25) Щ'ИЬЕ(30) ЮЯ(32)

2.Закодуємо послідовність, використовуючи таблицю кодування.

M1 = код(‘А’)= 1, M2 = код(‘Р’)= 17, M3 = код(‘А’)= 1.

Отриманий кодований блок початкового тексту М = {M1, M2, M3} = {1,17,1}

3.Представимо коди в двійковій системі числення: M1 = 1 = 000012

M2 = 17 = 16 + 1 = 100012

M3 = 1 = 000012

4.Використовуючи як ключ вектор ініціалізації здвигового регістра IV, побудуємо матрицю полягань здвигового регістра, з 15 зсувами, які забезпечують отримання трьох п'ятирозрядних значень гами шифру.

N	4	3	2	1	0
1	0	1	0	1	0
2	1	0	1	0	1
3	1	1	0	1	0
4	1	1	1	0	1
5	0	1	1	1	0
6	1	0	1	1	1
7	1	1	0	1	1
8	0	1	1	0	1
9	0	0	1	1	0
10	0	0	0	1	1
11	1	0	0	0	1
12	1	1	0	0	0
13	1	1	1	0	0
14	1	1	1	1	0
15	1	1	1	1	1

Врезультаті 15 зсувів регістра одержали наступну гаму шифру: Г = {Г1, Г2, Г3} = {01010, 10111, 10001}

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

підставі виразу

Ci = Mi (+) Гi:

C1 = M1 (+) Г1 = 00001 (+) 01010 = 01011 = 8 + 2 + 1 = 1110 C2 = M2 (+) Г2 = 10001 (+) 10111 = 00110 = 4 + 2 = 610

C3 = M3 (+) Г3 = 00001 (+) 10001 = 10000 = 1610

У результаті отримаємо зашифровану послідовність С = {11,6,16}

При розшифруванні необхідно сформувати гаму шифру по такому ж алгоритму, що і при шифруванні. Використовуючи в якості ключа вектор ініціалізації здвигового регістра IV, побудуємо матрицю полягань здвигового регістра, з 15 зсувами, які забезпечують отримання трьох п'ятирозрядних значень гамми шифру Г = {Г1 Г2, Г3} = {01010, 10111, 10001}

Для отримання початкового тексту по методу гаммирования здійснимий обчислення на підставі виразу

Mi = Ci (+) Гi

M1 = C1 (+) Г1 = 01011 (+) 01010 = 00001 M2 = C2 (+) Г2 = 00110 (+) 10111 = 10001

M3 = C3 (+) Г3 = 10000 (+) 10001 = 00001

В результаті отримаємо початкову послідовність M = {1,17,1}.

На підставі таблиці кодувань отримаємо букви початкового тексту ‘АРА’.

3.4 Алгоритм A5 в системі GSM (Group Special Mobile)

A5 це потоковий шифр, який використовується для ш ифрування GSM (Group Special Mobile). Це європейський стандарт для цифрових сотових мобільних телефонів.

Він використовується для шифрування каналу "телефон/базовая станція". Залишок каналу не шифрується, телефонна компания може легко слідкувати за розмовами.

Навкруги цього протокола ведуться дивні політичні ігри. Первоначально думалось, що криптографія GSM дозволить заборонити експорт телефона в деякі країни. Тепер ряд урядовців обговорює, чи не пошкодить A5 експортним продажам. З чуток в середині 80х різні секретні служби НАТО зчепилися за проблему, чи повинно шифрування GSM бути сильним або слабким. Німцям була потрібна сильна криптографія, оскільки поряд з ними знаходився Радянський Союз. Взяла вгору інша точка зору, тому A5 є французькою розробкою.

Більшість деталей в ньому відомі. Британська телефона компанія передала всю документацію Бредфордському университету (Bradford University), але примусила підписати угоду про нерозголошування. Інформарція десь просочилася і нарешті була опубликована в Internet.

A5 складається з трьох LFSR завдовжки 19, 22 і 23, всі многочлени зворотнього зв'язку прорежені, тобто мають невелику кількість ненульових елементів. Виходом є XOR трьох LFSR. В A5 використовується управлінням тим, що тактує. Кожний регістр тактується в залежності від свого середнього біта, потім виконується XOR із зворотньою пороговою функцією середних бітів всіх трьох регістрів. Звичайно на кожному етапі тактується два LFSR. Схема роботи шифру представлено на рисунку 7.3.4.1

Рис. 3.4.1 Схема роботи шифру A5

Якщо c1 = c2 = c3, то відбувається зсув всіх регістрів. Далі зсуваються тільки ті, для яких ci = cj.

Формули багаточленів роботи регістрів наступні:

		FLFSR1(x) = x19	+ x18	+ x17 + x14 + 1
		FLFSR2(x) = x22	+ x21	+ 1
		FLFSR3(x) = x23	+ x22	+ x21+ x8 + 1
Існує	тривіальне	вскриття,	яке		потребує	240	шифрувань.

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

4 Алгоритм RC4

RC4 це потоковий шифр із змінним розміром ключа, розроблений в 1987 році Роном Рівентом для RSA Data Security Inc. В продовж семи років він знаходився у приватній власності, і докладний опис алгоритму надавався тільки після підписання оголошення про нерозголошення.

Ввересні 1994 хтось анонімно опублікував код в списках разсилки "Киберпанкс" (Cypherpunks). Він швидко розповсюдився в телеконференції Usenet sci.crypt і через Internet по різних ftpсерверам в усім світі.

Поток ключей не залежить від відкритого тексту. Використовується Sблок розміром 8*8: S 0, S 1 . . ., S 255.

Елементи є перестановкою чисел від 0 до 255, а перестановка є функцією ключа змінної довжини. В алгоритмі застосовуються два лічильника, i і j, з нульовими початковими значеннями.

Для генерації випадкового байта виконується наступне: i = (i + 1) mod 256

j = (j + S i ) mod 256 поміняти місцями S i і Sj t = (S i + S j ) mod 256 K= S t

Байт K використовує операції XOR з відкритим текстом для отримання шифротекста або операції XOR з шифротекстом для отримання відкритого тексту. Шифрування 10 разів швидше, ніж DES.

Також нескладна і ініціалізація Sблоку.

Спочатку заповнюють його лінійно: S 0 = 0, S 1 = 1 . . ., S 255 = 255. Потім заповнюють ключем інший 256байтовий масив, при необхідності д ля заповнення всього масиву повторюючи ключ: К0, К1 . . ., К255. Встановимо значення індексу j рівним 0. Потім: for i = 0 to 255:

j = (j + S i + До i ) mod 256 поміняти місцями S i і S j

RSADSI затверджує, що алгоритм стійкий к дифференциальному и лінійному криптоаналізу.

RC4 може находиться приблизно в 21700 можливих станах.

Sблок поволі змінюється при використованні: i забе зпечується зміна кожного елементу, а j що елементи змінюються випадковим чином.

Лекція Стандартизація симетричних криптоалгоритмів

Розглядається один з перших міжнародних стандартів на криптографічне перетворення даних з використанням симетричних криптоалгоритмів. Представлена історія створення стандарту DES (Data Encryption Standart). Описуються основи роботи стандарту: мережа Файстеля, архітектура стандарту DES. Розглядається розвиток реалізацій DES-алгоритмів і алгоритми об'єднання блокових шифрів.

1 Принципи розсіювання і перемішування

На думку Клода Шеннона, основоположника теорії інформації, в практичних шифрах необхідно використовувати два загальні принципи:

•розсіювання;

•перемішування.

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

На рисунку 5.1.1 схематично зображено процес розсіювання.

Рис. 5.1.1 Схема процесу розсіювання

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

На рисунку 5.1.2 схематично зображено процес перемішування.

Рис. 5.1.2 Схема процесу перемішування

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

Ускладових шифрах в якості простих шифрів використовуються прості перестановки і підстановки.

2 Мережа Файстеля

2.1Історія створення мережі Файстеля

На початку 1970-х років, усвідомлюючи необхідність захисту електронної інформації при передачі даних в мережах ЕОМ (особливо бізнес-транзакцій при здійсненні грошових перекладів і передачі конфіденційних фінансових даних), компанія International Business Machines (відома у всьому світі як IBM) приступила до виконання власної програми наукових досліджень, присвячених захисту інформації в електронних мережах, у тому числі і криптографії. Так розвиток однієї передової технології спричинив за собою справжню революцію в іншій.

Оскількі у ряді університетів Сполучених Штатів (таких, як Станфордській університет і Массачусетський технологічний інститут) завжди існував інтерес до даної області дослідження, IBM постаралася привернути університетських фахівців до розробки методів захисту електронної інформації.

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

Команду розробників фірми IBM, що приступила до дослідження систем шифрування з симетричною схемою використання ключів, очолив доктор Хорст Файстель, що у той час вже став досить відомим криптографом.

Файстель до того моменту вже встиг тісно попрацювати з Клодом Шенноном в компанії Bell Laboratories. Ідеї Шеннона надихали багатьох дослідників на оригінальні винаходи. Свідоцтвом тому є досить велика кількість патентів, зареєстрованих і прийнятих в середині 60-х років Національним патентним бюро США (United States Patent and Trademark Office). Файстель активно співробітничав з Шенноном. На його рахунку як мінімум два патенти і декілька революційної статті в області криптографії і криптоаналізу.

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

Надо визнати, що результат виправдав очікування. Ним стала проведена в дослідницькій лабораторії IBM Watson Research Lab розробка нової оригінальної архітектури побудови симетричних шифрів на базі необоротних перетворень. Архітектура нового способу шифрування згодом була названа в класичній літературі архітектурою Файстеля (на даний момент в російській і зарубіжній криптографії існує термін, що більш встоявся - мережа Файстеля або Feistel's network). Пізніше, відповідно до розробленими принципами, був сконструйований шифр Люцифер (Lucifer) - перший серйозний блоковий шифр, опис якого з'явився в відкритій літературі і викликав нову хвилю інтересу фахівців до криптографії в цілому.

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

2.2Архітектура Файстеля

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

Файстель вирішив проблему таким чином.

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

абозбалансованоюмережеюФайстеля.

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

Запропонована Файстелем схема шифрування представлена на рисунку 5.2.2

Рис. 2.2 Схема шифрування Файстеля

На зображеній схемі буквами Li та Ri позначені ліва і права половинки початкових даних на i-му кроці слідовного перетворення. Кожний такий цілий крок називають раундом шифрування.

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

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

2.3Мережа Файстеля

Для збільшення криптостійкості шифрування з використанням мережі Файстеля описану у попередньому розділі схему слід використовувати у послідовності декілька разів.

Оскільки за один раз шифрування обробляється тільки одна половина вхідних даних, бажано, щоб число раундів було кратне двом. У такому разі є упевненість, що кожна з половинок буде оброблена однакове число разів. На рисунку 5.2.3.1 відображена мережа Файстеля з парним числом раундів.

Рис 2.3.1 Мережа Файстеля з декількома раундами

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

Li+1 = Ri

Ri+1 = Li F(Ri, ki)

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

Розбалансовану мережу Файстеля можна розглядати як узагальнення поняття мережі Файстеля. Стійкість криптосистеми, побудованої на основі мережі Файстеля, залежить цілком від результату виконання нелінійної функції гамування в декількох ітераціях. Тому для забезпечення достатньої надійності дані повинні бути перетворені з достатньо великим числом раундів.

Рис 2.3.2 Архітектура розбалансованої мережі Файстеля

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

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

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

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

3 Стандарт DES (Data Encryption Standart)

3.1Історія створення стандарту

Стандарт шифрування DES (Data Encryption Standard) було розроблений у 1970-х роках, він базується на алгоритмі DEA.

Початкові ідеї алгоритму шифрування даних DEA (data encryption algorithm) були запропоновані компанією IBM ще в 1960-х роках і базувалися на ідеях, описаних Клодом Шеноном в 1940-х роках. Спочатку ця методика шифрування називалася lucifer, назву DEA вона одержала лише у 1976 році. Lucifer був першим блоковим алгоритмом шифрування, він використовував блоки розміром 128 біт і 128-бітовий ключ. По суті цей алгоритм був прототипом DEA.

DEA оперує з блоками даних розміром 64 біти і використовує ключ завдовжки також 64 біти.

Розмір блоку у 64 біти було вибрано у звязку з необхідністю використання дешевої апартної бази.

Ключ був фактично завдовжки 56 біт, а останні 8 біт - біти контролю на парність (1 контррольний біт на один байт ключа). Довжина ключа дозволяла формувати 256 можливих варіантів, що забезпечувало до недавнього часу достатній рівень безпеки.

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

Ухвалення стандарту шифрування DES з'явилося могутнім поштовхом до широкого вживання шифрування в комерційних системах. Введення цього стандарту - відмінний приклад уніфікації і стандартизації засобів захисту. Прикладом системного підходу до створення єдиної великомасштабної системи захисту інформації є директива Міністерства фінансів США 1984 року, згідно якої всі суспільні і приватні організації, що вели справи з урядом США, зобов'язані були впровадити процедуру шифрування DES.

3.2Структурна схема реалізації алгоритму DEA

Перетворення вхідного блоку тексту починається з перестановки біт (IP – Initial Permutation) в 64-розрядному блоці.

Одержаний блок поділяється на дві 32-розрядні частини L0 та R0. Далі 16 разів повторюються наступні 4 процедури:

•перетворення ключа з урахуванням номера ітерації i (перестановки розрядів з видаленням 8 біт, в результаті виходить 48-розрядний ключ);

•за допомогою функції f(A,J) генерується 32-розрядний вихідний код,де A=Li, а J – перетворений ключ.

•виконується операція XOR для Ri f(A,J), результат позначається Ri+1.

•виконується операція привласнення Li+1=Ri.

Структурна схема реалізації алгоритму dea показана на рисунку 5.3.2

Рис. 3.2 Структурна схема реалізації алгоритму DEA

3.3Алгоритм початкової перестановки

Перетворення починається з перестановки біт (IP – Initial Permutation) в 64-розрядному блоці початкових даних. Матриця перестановки, за якою виконується перестановка, представлена в таблиці 5.3.3.

Таблиця 5.3.3 Матриця початкової перестановки бітів

Рис. 3.4.1 Приклад схеми розміщення бітів при розширенні

Для отриманого 48-розрядного коду і ключа виконується операція XOR. Результуючий 48- розрядний код перетвориться в 32-розрядний за допомогою S-блоків. Кожний S-блок -

матрицяперестновки. На виході S-матриц здійснюється перестановка згідно матриці, вміст якої показано в таблиці

3.4.2.В матриці числа - порядкові номери біт.

Таблиця 3.4.2 Матриця

	N	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	0	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
	1	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
	2	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
	3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

Початковий 48-розрядний код ділиться на 8 груп по 6 розрядів. Перший і останній розряд в групі використовується як адреса рядка, а середні 4 розряди – як адреса стовпця. Схема перетворення бітів для S-блоку представлена на рисунку 3.4.2

Рис. 3.4.2 Приклад схеми перетворення бітів для S-блоку

Врезультаті кожні 6 біт коду перетворяться в 4 біти, а весь 48-розрядний код в 32-розрядний (для цього потрібно вісім S-матриц). Загальна схема роботи фунції гамування представлена на рисунку

Рис. 3.4.3 Алгоритм роботи функції f

Існують розробки, що дозволяють виконувати шифрування в рамках стандарту DES

апаратним чином, що забезпечує досить високу швидкодію.

3.5Алгоритм обчислення підключей

Перетворення ключів Kn (n=1.,16; Kn = KS(n,key), де n – номер ітерації) здійснюються згідно алгоритму, показаному на рисунку 5.3.5.

Рисунок 5.3.5 Алгоритм обчислення послідовності ключів Kn

Для опису алгоритму обчислення ключів Kn (функція KS) достатньо визначити структуру «Вибір 1» і «Вибір 2», а також задати схему зсувів вліво (табл. 6.4.1.2). «Вибір 1» і «Вибір 2»

єперестановками бітів ключа (PC-1 і PC-2; табл. 5.3.5.1). При необхідності біти 8, 16., 64 можуть використовуватися для контролю парності.

Для обчислення чергового значення ключа таблиця ділиться на дві частини С0 і D0. В С0 ввійдуть біти 57, 49, 41., 44 і 36, а в D0 – 63, 55, 47., 12 і 4. Оскільки схема зсувів задана (табл. 5.3.5.2) C1,D1; Cn, Dn і так далі можуть бути легко одержані з C0 і D0. Так, наприклад, C3 і D3 виходять з C2 і D2 циклічним зсувом вліво на 2 розряди

Таблиця 6.4.1.1

	PC-1 (Вибір 1)				PC-2 (Вибір 2)
	57 49 41 33 25 17 9				14 17 11 24 1 5
	1 58 50 42 34 26 18				3 28 15 6 21 10
	10 2 59 51 43 35 27				23 19 12 4 26 8
	19 11 3 60 52 44 36				16 7 27 20 13 2
	63 55 47 39 31 23 15				41 52 31 37 47 55
	7 62 54 46 38 30 22				30 40 51 45 33 48
	14 6 61 53 45 37 29				44 49 39 56 34 53
	21 13 5 28 20 12 4				46 42 50 36 29 32
			Таблиця 6.4.1.2
		Номер ітерації		Число зсувів вліво
		1		1
		2		1

	3	2
	4	2
	5	2
	6	2
	7	2
	8	2
	9	1
	10	2
	11	2
	12	2
	13	2
	14	2
	15	2
	16	1

3.6Алгоритм кінцевої (інверсної) перестановки

Матриця кінцевої перестановки, за якою виконується перестановка 64 бітів, представлена в таблиці 5.3.6.

Таблиця 5.3.6 Матриця кінцевої перестановки бітів

	40	8	48	16	56	24	64	32
	39	7	47	15	55	23	63	31
	38	6	46	14	54	22	62	30
	37	5	45	13	53	21	61	29
	36	4	44	12	52	20	60	28
	35	3	43	11	51	19	59	27
	34	2	42	10	50	18	58	26
	33	1	41	9	49	17	57	25

Втаблиці номери відповідають номерам біт початкового 64-розрядного коду. В процесі перестановки відбувається перестановка біт відносно один одного. Наприклад, 40-й біт стає першим, 8-ий – другим і т.д. Приклад схемі перестановки бітів представлено на рисунку

5.3.6.

Рис. 5.3.6 Приклад схеми кінцевої перестановки бітів

4Розвиток реалізацій DES-алгоритмов

Одразу після прийняття стандарту DES, його стали впроваджувати у апаратні та програмні реалізації. Природно, що при таких реалізаціях було знайдено недоліки стандарту та запропоновано шляхи його розвитку. Деякі з них мають наступну назву: багатократний DES, DESX, CRYPT, Узагальнений DES, DES із зміненими S-блоками, DES із зміненими S- блоками, RDES, DES с S-блоками, зависящими от ключа

4.1Багатократний DES

Багатократний DES використовує інший алгоритм генерації підключів. Іншою можливістю

євикористання різних підключей на кожному етапі, не створюючи їх з одного 56- бітового ключа. Оскільки на кожному з 16 етапів використовується 48 бітів ключа, то довжина ключа для такого варіанту складе 768 бітів. Такий варіант різко збільшує складність розкриття алгоритму грубою силою, складність такого розкриття складає 2 768.

Проте можливе використання розкриття "зустріч посередині". Складність такого розкриття зменшується до 2384, що, проте, цілком достатньо для забезпечення будь-якої існуючої безпеки.

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

4.2 DESX

DESX - це варіант DES, розроблений RSA Data Security Inc., і включений в 1986 році в програму забезпечення безпеки електронної пошти MailSafe, а в 1987 році в набір BSAFE.

DESX використовує метод, який зветься вибілюванням, для маскування входів і виходів DES.

Вибілюванням (whitening) називається спосіб, при якому виконується XOR частини ключа з входом блокового алгоритму і XOR іншої частини ключа з виходом блочного алгоритму.

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

С= K3 EK2 (M K1), M = K1 DK2 (C K3),

Якщо K1 = K2, то для розкриття грубою силою буде потрібно 2n+m/p дій, де n - розмір ключа, m - розмір блоку, і p - кількість відомих відкритих текстів. Якщо K1 і K2 різні, то для розкриття грубою силою з трьома відомими відкритими текстами буде потрібно 2n+m+1 дій. Проти диференційного або лінійного криптоаналізу, такі заходи забезпечують захист тільки для декількох бітів ключа. Але з обчислювальної точки зору це дуже дешевий спосіб підвищити безпека блокового алгоритму.

Окрім 56-бітового ключа DES в DESX використовується додатковий 64-бітовий ключ вибілювання. Ці 64 біти використовуються для виконання операції XOR з блоком відкритого тексту перед першим етапом DES. Додаткові 64 біти, які є результатом вживання однонаправленої функції до повного 120-бітового ключа DESX, використовуються для виконання XOR з шифротекстом, одержаним в результаті останнього етапу. В порівнянні з DES вибілювання значно підвищує стійкість DESX до розкриття грубою силою, розкриття вимагає (2120 )/n операцій при n відомих відкритих текстах. Також підвищується стійкість до диференціального і лінійного криптоаналізу, для розкриття буде потрібно 261 вибраних и 2 60 відомих відкритих текстів, відповідно.

4.3 CRYPT

CRYPT представляє собою варіант DES, який використовується в операційних системах UNIX.

Він в основному використовується в якості однонаправленої функції для паролей, але іноді може бути використано і для шифрування.

Відміна між CRYPT та DES полягає в том, что у CRYPT включена незалежна від ключа перестановка з расширенням з 212 варіантами. Це зроблено для того, чтоб при створенні апаратного пристрою вскриття паролю неможливо було використати промислові мікросхеми DES.

4.4Узагальнений DES

Узагальнений DES (Generalized DES - GDES) був спроектований для прискорення DES і підвищення стійкості алгоритму. Загальний розмір блоку збільшився, а кількість обчислень залишилося незмінною.

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

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

GDES використовує змінне число етапів n. В останній етап внесена незначна зміна, щоб процеси шифрування і дешифрування відрізнялися тільки порядком підключей (точно також як в DES). Дійсно, якщо q,n = 16, то описаний алгоритм перетворюється в DES.

Біхам і Шамір показали, що диференціальний криптоаналіз розкриває GDES з q,n = 6 за допомогою всього шести вибраних відкритих текстів. При використовуванні незалежних підключей потрібно 16 вибраних відкритих текстів. GDES з q,n = 22 розкривається за допомогою всього 4 вибраних відкритих текстів, а для розкриття GDES з q,n = 31 потрібне всього 500000 вибраних відкритих текстів. Навіть GDES з q,n = 64 слабкіший, ніж DES - для його розкриття потрібно тільки 249 вибраних відкритих текстів.

Дійсно, будь-яка більш швидка, ніж DES, схема GDES є також і менш безпечною.

4.5DES із зміненими S-блоками

Інші модифікації DES пов'язані з S-блоками.

Вдеяких проектах використовується змінний порядок S-блоків. Інші розробники міняють зміст самих S-блоків.

Біхам і Шамір показали, що побудова S-блоков і навіть їх порядок оптимальні з погляду стійкості до диференційного криптоаналізу:

Зміна порядку восьми S-блоков DES (без зміни їх значень) також значно послаблює DES: DES з 16 етапами і конкретним зміненим порядком розкривається приблизно за 2 38 кроків.

... Доведено, що DES з випадковими S-блоками розкрити дуже легко. Навіть мінімальна зміна одного з елементів S-блоків DES може понизити стійкість DES до розкриття.

S-блоки DES не були оптимізовані проти лінійного криптоаналізу. Існують і кращі S-блоки, ніж пропоновані в DES, але бездумна заміна S-блоків новими - не сама краща ідея.

4.6 RDES

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

Кращою є ідея виконувати обмін місцями тільки в межах правої половини і на початку кожного етапу.

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

Існує множина можливих варіантів. В RDES-1 використовується залежна від даних перестановка 16-бітових слів на початку кожного етапу. В RDES-2 застосовується залежна від даних перестановка байтів на початку кожного етапу після 16-бітових перестановок, аналогічних RDES-1. Розвитком цієї ідеї є RDES-4, і т.д. RDES-1 стійкий і до диференційного, і до лінійного криптоаналізу.

4.7DES з S-блоками, залежними від ключа

Лінійний і диференційний криптоаналіз працюють тільки, якщо аналітику відома будова S- блоків.

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

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

1.Змінити порядок S-блоков DES: 24673158.

2.Вибрати 16 з бітів ключа, що залишилися. Якщо перший біт 1, обміняти місцями перші і останні два рядки S-блока 1. Якщо другий біт 1, обміняти місцями перші і останні вісім стовпців S-блока 1. Повторити те ж саме для третього і четвертого бітів і S-блока 2. Повторити те ж саме для S-блоков з 3 по 8.

3.Узяти 32 біти ключа, що залишилися. Виконати XOR перших чотирьох бітів з кожним елементом S-блока 1 XOR наступних чотирьох бітів з кожним елементом S-блока 2, і так далі.

Складність розкриття такої системи за допомогою диференційного криптоаналізу складе 251, за допомогою лінійного криптоаналізу - 253 . Складність вичерпного перебору складе 2102.

Що добре в цьому варіанті DES так це те, що він може бути реалізований у існуючій апаратурі. Різні постачальники мікросхем DES продають мікросхеми DES з можливістю завантаження S-блоков. Можна реалізувати будь-який спосіб генерації S-блоков зовні мікросхеми і потім завантажити їх в неї.

5 Об`єднання блокових шифрів

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

5.1Мета та переваги об`єднання блокових шифрів

Існує багато засобів об'єднати блокові алгоритми для отримання нових алгоритмів. Стимулом створювати подібні схеми є бажання підвищити безпеку, не пробираючись через тернії створення нового алгоритму. DES є безпечним алгоритмом, він піддавався криптоаналізу добрі 20 років і, тим не менше, якнайкращим засобом розкриття залишається груба сила. Проте його ключ дуже короткий. Хіба не погано б було використовувати DES в якості компоненту іншого алгоритму з довшим ключем? Це дозволило б одержати переваги довгого ключа з гарантією двох десятиріч криптоаналізу.

Одним із засобів об'єднання є багатократне шифрування - для шифрування одного і того ж блоку відкритого тексту алгоритм шифрування використовується кілька разів з декількома ключами.

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

5.2Подвійне шифрування

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

Рис. 5.5.2 Схема процесу шифрування (а) і розшифровки (b) при подвійному шифровании

С= Ek2(Ek1(M))

M = Dk1(Dk2(C))

Якщо блоковий алгоритм утворює групу, то завжди існує k3 для которого C = Ek2(Ek1(M)) = Ek3(M)

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

Але при розкритті з відомим відкритим текстом це не так. Меркл і Хеллман придумали спосіб обміняти пам'ять на час, який дозволяє розкрити таку схему подвійного шифрування за 2n+1 шифрувань, а не за 22n. (Вони використовували цю схему проти DES, але результати можна узагальнити на всі блокові алгоритми.)

Це розкриття зветься "зустріч посередині": з одного боку виконується шифрування, а з іншого - дешифрування, результати, що вийшли посередині, порівнюються.

В цьому розкритті криптоаналітику відомі M1,C1,M2 і C2, такі що

C1 = Ek2(Ek1(M1))

C2 = Ek2(Ek1(M2))

Для кожного можливого K(чи K1, або K2 ) криптоаналітик розраховує Ek(M1) і зберігає результат в пам'яті. Зібравши всі результати, він для кожного K обчислює D K(C 1 ) і шукає в пам'яті такий же результат. Якщо такий результат знайдений, то можливо, що поточний ключ - K2, а ключ для результату в пам'яті - K1. Потім криптоаналітик шифрує M1 з допомогою K1 і K2.

C= Ek1(Dk2(Ek1(M))) M = Dk1(Ek2(Dk1(M)))

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

Цікрвий варіант схеми шифрування-дешифрування раніше було розроблено IBM для сумісності з існуючими реалізаціями алгоритму: завдання двох однакових ключів еквівалентно одинарному шифруванню цим ключем. Схема шифрування-дешифрування- шифрування сама по собі не володіє ніякою безпекою, але цей режим був використаний для поліпшення алгоритма DES в стандартах X9.17 і ISO 8732.

Лекція Режими використання симетричних блокових алгоритмів

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

Вступ

Далі буде розглянуто п'ять режимів шифрування так, як вони відрекомендовані в документі, виданому NIST США і "Рекомендації для режимів шифрування з блоковим шифром". Це зовсім не єдиний документ виданий NIST відносно режимів шифрування. До цього був виданий документ, що описує чотири режими для блокового шифру DES, а також інший документ - для потрійного DES (Triple DES algorithm або TDEA), в якому описано сім режимів, три з яких є лише варіацією на тему тих же режимів, що були описані для DES. Основною перевагою останнього виданого документа є по-перше те, що його рекомендації відносяться до всіх схвалених NIST блокових шифру, і по-друге в ньому описано ще один режим шифрування - п'ятий. Ось ці режими:

•ECB (Electronic Code Book) - електронная кодова книга;

•CBC (Cipher Block Chaining) - зчеплення блоків по шифротексту;

•CFB (Cipher Feed Back) - зворотні завантаження шифротекста;

•OFB (Output Feed Back) - зворотні завантаження вихідних даних;

•CTR (Counter) - шифрування з лічильником.

1Режим "Електронна кодова книга"

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

шифруванні відповідає вживання до вхідним даним перетворення функцією , а при

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

Рис. 1 - Режим шифрування електронная кодова книга - ANB.

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

ECB шифрування: где j=1.n

ECB розшифрування: где j=1.n

де

Pj - черговий j-ий блок відкритого тексту;

Cj - черговий j-ий блок шифртексту.

Таким чином шифрування проходить блоками, відповідними розміру вхідних/вихідних

даних для функцій і .

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

ЦеєперевагоюрежимуЕСB. Недоліки режиму:

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

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

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

2Режим "Зчеплення шифров"

Врежимі шифрування CBC виконується "зчеплення" всіх блоків повідомлення по шифротексту. Як це досягається - видно з рисунку 2

Рис. 2 - Режим шифрування CBC - зчеплення блоків по шифротексту.

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

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

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

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

CBC шифрування:

CBC розшифрування:

В рівняннях прийняті наступні позначення:

IV - вектор ініціалізації;

Pj - черговий j-ий блок відкритого тексту.

Cj - черговий j-ый блок шифротексту.

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

одержано, функції цілком можна виконувати паралельно і незалежно для всіх блоків повідомлення. Це дає значний виграш за часом. В цьому режимі варто зупинитися ще на одній деталі. Річ у тому, що останній блок шифротекста який виходить на виході алгоритму режиму CBC залежить як від ключа блокового шифру і вектора ініціалізації, так і (що важливе в даному випадку) від всіх біт відритого тексту повідомлення. А це означає що цей останній блок шифротекста можна використовувати як свого роду ідентифікатор повідомлення. Такий ідентифікатор не дає сторонньому спостерігачу ніякої інформації про вміст всього повідомлення в цілому, і у той же час, практично однозначно визначає його (повідомлення). Більш того підроблювати цей ідентифікатор без знання ключа шифрування K так само важко, як і правильно вгадати сам ключ. Цей ідентифікатор широко використовується для аутентифікації повідомлень і відправників і носить назва MAC (Message Authentication Code), в україномовній літературі - КАП (код аутентификації повідомлень).

3 Режим "Зворотній зв'язок по шифру"

Валгоритмі режиму зворотній зв`язок по шифру черговий блок відкритого тексту підсумовується по модулю з блоком попереднього шифротекста але тільки після того, як цей шифротекст піддасться додатковій обробці функцією Ek . Так відбувається шифрування повідомлення в цьому режимі. Для розшифрування потрібно просто підсумовувати (природно по модулю 2) черговий блок шифротекста з попереднім, пропущеним знову-таки через функцію Ek. Робота шифру проілюстрована на рисунку 3 Зверніть увагу, що при шифруванні і розшифруванні в цьому режимі блоковий шифр використовується тільки в режимі зашифрування (тобто функції Dk немає взагалі).

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

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

Впотокових режимах шифрування можна застосувати трюк, який дозволяє згладити проблему доповнення останнього блоку повідомлення. Замість того, щоб згодовувати алгоритму режиму на кожній його ітерації повідомлення повними блоками, текст подається порціями завдовжки s < b, де b - довжина блоку в бітах. І далі, при підсумовуванні використовується тільки s старших біт вихідних даних функції Ek, інші просто відкидаються. Наступна ітерація режиму одержує на вході s біти шифротекста, які зсовують вліво на s біт вхідні дані функції Ek, що залишилися там з попередньої ітерації.

Рис. 3 - Шифрування в режимі CFB - зворотній зв`язок по шифру.

Рис. 4 - Розшифрування в режимі CFB - зворотній зв`язок по шифру.

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

Рівняння режиму шифрування CFB приведені нижче:

I1 = IV;

Ij = LSBb-s(Ij-1) | Cj-1, де j = 2, 3 ... n;

Oj = Ek(Ij), де j = 1, 2 ... n;

Cj = Mj MSBs(Oj), де j = 1, 2 ... n

IV - вектор ініціалізації;

Mj - черговий j-ий блок відкритого тексту.

Cj - черговий j-ий блок шифротекста.

LSBm (X) - m молодших біт (less significant bits) двійкового числа X

MSBm (X) - m старших біт (most significant bits) двійкового числа X

X | Y - конкатенция бітових рядків, представлених числами X і Y, наприклад: 01 | 1011 = 011011

Рівняння режиму розшифрування CFB приведені нижче:

I1 = IV;

Ij = LSBb-s(Ij-1 ) | Cj-1, де j = 2, 3 ... n;

Oj = Ek(Ij ), де j = 1, 2 ... n;

Mj = Cj MSBs(Oj ), де j = 1, 2 ... n

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

4 Режим "Зворотній зв'язок по виходу"

Режим OFB, як і CFB є потоковим, тобто функція Ek викликається в алгоритмі до підсумовування з порцією відкритого тексту. Але на цей раз на вхід Ek подається не шифротекст з попередньої ітерації, а просто її ж вихідні дані. Ілюстрація режиму приведена на рисунку 5 Тобто відбувається як би зациклення функції Ek. В такій ситуації стає важливим однократне використання вектора ініціалізації. Припустимося, що два різні повідомленя шифруються в режимі OFB з використанням одного і того ж вектора ініціалізації. Тоді, якщо супротивнику стає відомий який-небудь j-ий блок відкритого тексту першого повідомлення то, маючи j-ий блок шифротекста він легко може обчислити Oj - вихідні данні Ek а оскільки вони залежать тільки від вектора ініціалізації, який однаковий для обох повідомлень, то можна затверджувати, що і в другому повідомленні це буде той же Oj, звідси, маючи j-ий блок шифротекста другого повідомлення супротивник тутже одержить відкритий текст j-го блоку іншого повідомлення. Тому в алгоритмі OFB необхідно уникати не тільки повторення векторів ініціалізації, але і того, що б будь-який j-ий блок вхідних даних функції Ek для одного повідомлення не використовувався як вектор ініціалізації для іншого повідомлення.

Недолік OFB в тому, що він більш уразливий до атакам модифікації потоку повідомлень, ніж CFB.

Рис. 5 - Шифрування в режимі OFB

Рис. 6 - Розшифрування в режимі OFB

Рівняння режиму шифрування ОFB приведені нижче: I1 = IV;

Ij = Oj , де j = 2, 3 ... n;

Oj = Ek( Ij ), де j = 1, 2 ... n;

Cj = Mj Oj , де j = 1, 2 ... n-1

Cn = Mn MSBr(On)

де IV - вектор ініціалізації;

Mj - черговий j-ий блок відкритого тексту;

Cj - черговий j-ий блок шифротекста;

MSBr (X) - r старших біт (most significant bits) двійкового числа X;

X | Y - конкатенция бітових рядків, представлених числами X і Y, наприклад: 01 | 1011 = 011011

Рівняння режиму розшифрування ОFB приведені нижче:

I1 = IV;

Ij = Oj , де j = 2, 3 ... n;

Oj = Ek(Ij ), де j = 1, 2 ... n;

Mj = Cj Oj , де j = 1, 2 ... n-1

Mn = Cn MSBr(On)

Як можна помітити з рівнянь - проблема доповнення повідомлення для OFB розв'язується просто: її для цього режиму просто не існує. Для останнього, можливо неповного, блоку повідомлення використовується рівно стільки біт вихідних даних функції Ek, скільки біт в цьому блоці. Таким чином в цьому режимі, на відміну від попередніх довжина повідомлення залишається незмінною у процесі шифрування і, головне, при передачі.

5 Режим шифрування з лічильником

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

Таким чином шифротекст в алгоритмі режиму CTR виходить підсумовуванням по модулю 2 чергові блоки відкритого тексту з вихідними даними функції Ek. На вхід функції Ek подається чергове значення Tj лічильника блоків повідомлення. Розшифрування відбувається також шляхом підсумовування по модулю 2 чергового блоку шифротекста і результату перетворення функції Ek чергового значення лічильника Tj. Обидві операції шифрування і розшифровки в режимі CTR можна проводити паралельно і незалежне для всіх блоків, що видно з рисунків 7 та 8.

Рис. 7 - Шифрування в режимі CTR

Рис. 8 - Розшифрування в режимі CTR

В режимі CTR також відсутня проблема останнього блоку. Це видно з рівнянь режиму CTR:

Oj = Ek( Tj ), де j = 1, 2 ... n;

Cj = Mj Oj , де j = 1, 2 ... n-1

Cn = Mn MSBr(On)

де Mj - черговий j-ий блок відкритого тексту;

Cj - черговий j-ий блок шифротекста;

MSBr (X) - r старших біт (most significant bits) двійкового числа X;

Режим CTR володіє всіма перевагами режиму ЕСB (паралельне виконання, простота і можливість безпосереднього шифрування, розшифрування будь-якого блоку повідомлення по окремості і незалежно від інших блоків). Але крім того, режим CTR виправляє всі недоліки шифрування в режимі електронної кодової книги: однакові блоки відкритого тексту тепер вже не будуть перетворені в однакові блоки шифротекста; відпадає необхідність доповнення останнього блоку шифротекста. До того ж в цьому режимі (як в будь-якому потоковому режимі) використовується тілько функція зшифрування Ek, а для деяких

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

6 Накопичення помилок в різних режимах шифровання

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

Вбудь-якому режимі помилка в межах блоку (або порції - для CFB) шифротекста веде до неправильного розшифруванні цього блоку. Так, в режимах CFB, OFB і CTR помилковим на виході буде той же біт, решта біт залишиться неушкодженими. В режимах же ЕСB і CBC пошкодженим, залежно від сили перетворення використованого блокового шифру, може стати будь-який біт з вірогідністю пошкодження 1/2.

Врежимах ЕСB, OFB і CTR помилка в біті окремого блоку шифротекста не вплине на інші блоки при розшифруванні. В режимі CBC така помилка приведе до помилки в тому ж біті при розшифруванні наступного блоку повідомлення. Решти блоків ця помилка не торкнеться. Інша справа режим CFB: тут помилка в одному біті порції шифротекста розповсюдиться на b/s наступних порцій шифротекста (b - довжина блоку вхідних даних функції Ek; s - довжина порції шифротекста). До того ж при розшифруванні змінитися з

вірогідністю тепер може будь-який біт цих b/s порцій.

Врежимі CTR помилка в біті лічильника Tj приведе до можливості зміни будь-якого біта відповідного блоку шифротекста з вірогідністю 1/2.

Помилка в біті вектора ініціалізації також вплине на результати розшифруванні. Так, в режимі OFB помилка в одному біті вектора ініціалізації при розшифруванні приведе до повністю невірним результатам. В режимі ж CFB ця помилка при розшифруванні зачепить як мінімум першу порцію повідомлення, а як максимум b-i/s (де b,s - те ж, що раніше, а i – номер помилкового біта зліва) порцій повідомлення. Для обох цих режимів пошкодженим в блоках (порціях для CFB), що торкнулися, може виявитися будь-яким бітом з вірогідністю 1/2. В режимі CBC помилка в біті вектора ініціалізації призведе до неправильного розшифрування лише першого блоку та і то помилковим виявиться тільки один біт - інші залишаться непошкодженими. Звідси витікає, що режим CBC схильний до порушення захисти у разі навмисної зміни біта у векторі ініціалізації з метою змінити зміст повідомлення. Тому в цьому режимі необхідно забезпечити цілісність вектора ініціалізації. Режими OFB і CTR також схильні до порушення цілісності повідомлення, але для них це стає можливим вже при навмисній зміні біта будь-якого блоку шифротекста. Тому в цих режимах повинна бути забезпечена цілісність блоків шифротекста при передачі. Те ж торкається і режиму CFB, хоча в цьому режимі для будь-якої порції шифротекста (окрім останньої) порушення її цілісності може бути знайдено по виникненню помилок при расшифруванні наступних порцій шифротекста.

Таблица 1 відображає ефект розповсюдження помилки у всіх п'яти режимах шифрування.

Таблиця 1 - Ефект розповсюдження помилки

	Режим			Ефект від помилки в біті			Ефект від помилки в i-
	шифрування			шифротексту Cj			тому біті вектора
							ініціалізації IV
	ECB			ПББ при розшифруванні блоку			Не используется
				Cj
	CBC			ПББ при розшифруванні блоку			ПОБ при розшифруванні
				Cj			блоку C1
				ПОБ при розшифруванні блоку
				Cj+1
	CFB			ПОБ при розшифруванні блоку			ПББ при розшифруванні
				Cj			блоків C1, C2,...Cj, ,
				ПББ при розшифруванні блоків			де 1 <= j <= b - i/s
				Cj+1,... Cj+b/s
	OFB			ПОБ при розшифруванні блоку			ПББ при розшифруванні
				Cj			блоків C1, C2,...Cn
	CTR			ПОБ при розшифруванні блоку			Ошибка в лічильнику Tj веде
				Cj			до ПББ при розшифруванні
							блоку Cj

В таблиці прийняті наступні скорочення:

ПББ - помилка в будь-якому біті, тобто пошкодженим при розшифруванні з вірогідністю 1/2 може виявитися будь-який біт блоку (або порції).

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

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

Лекція Математичні основи проектування асиметричних криптоалгоритмів

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

Вступ

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

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

1 Принципи створення асиметричних криптосистем

Для шифрування даних використовується один ключ, а для розшифрування - інший ключ.

1.1Загальна схема роботи асиметричных криптосистем

Ефективними системами криптографічного захисту даних є асиметричні криптосистеми, які звуться також криптосистемами з відкритим ключем.

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

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

Узагальнена схема асиметричної криптосистеми з відкритим ключем показана на рисунку

9.1.1.В цій криптосистемі застосовують два різні ключі: Кв - відкритий ключ відправника А; kв - секретний ключ одержувача В. Генератор ключів доцільно розташовувати на стороні одержувача В (щоб не пересилати секретний ключ ke по незахищеному каналу). Значення ключів Кв і но залежать від початкового полягання генератора ключів.

Розкриття секретного ключа по відомому відкритому ключу Кв повинне бути обчислювально нерозв'язною задачею. Характерні особливості асиметричних криптосистем:

1.Відкритий ключ Кв і криптограма С можуть бути відправлені по незахищеним каналам, тобто супротивнику відомі Кв і С.

2.Алгоритми шифрування і розшифрування є відкритими.

1.2Умови створення криптоалгоритмів з двома ключами

Захист інформації в асиметричній криптосистемі заснований на секретності ключа Зв.

У.Діффі і М.Хеллман сформулювали вимоги, виконання яких забезпечує безпеку асиметричної криптосистеми:

1.Обчислення пари ключів (Ов, Зв) одержувачем В на основі початкової умови повинно бути простим.

2.Відправник А, знаючи відкритий ключ Ов і повідомлення М, може легко обчислити криптограму С=Еов(М)=Ев(М).

3.Отримувач В, використовуючи секретний ключ Кв і криптограму С, може легко відновити початкове повідомлення М = Dзв (С)

4.Супротивник, знаючи відкритий ключ Ов, при спробі обчислити секретний ключ Зв натрапляє на непереборну обчислювальну проблему.

5.Супротивник, знаючи пару (Ов, С), при спробі обчислити початкове повідомлення М натрапляє на непереборну обчислювальну проблему.

2 Теорія однонаправлених функцій. Задача факторизації великих чисел. Задача визначення дискретного логарифма

2.1Визначення однонаправленості функцій

Концепція асиметричних криптографічних систем з відкритим ключем заснована на вживанні однонаправлених функцій. Неформально однонаправлену функцію можна визначити таким чином. Хай Х і Y- деякі довільні множини.

Функция f : Х -> Y є однонаправленої, якщо для всіх х, що належать Х, можна легко обчислити функцію y=f(x), де y належить Y.

Ів той же час для більшості y, що належать Y, достатньо складно набути значення х, що належить Х, таке, що

f (х)=у

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

Основним критерієм віднесення функції f до класу однонаправлених функцій є відсутність ефективних алгоритмів зворотнього перетворення Y -> X.

2.2Факторизація великих чисел

Як перший приклад однонаправленої функції розглянемо цілочисельне множення.

Пряма задача - обчислення множини двох дуже великих цілих чисел Р і Q тобто знаходження значення N = P*Q, є відносно нескладною задачею для ЕОМ.

Зворотня задача - розкладання на множники великого цілого числа, тобто знаходження дільників Р і Q великого цілого числа N = P*Q, є практично нерозв'язною задачею при достатньо великих значеннях N.

По сучасним оцінкам теорії чисел при цілому N, розмір порівнює 2264 та розміри P і Q рівняться, для розкладання числа N буде потрібно близько 1024 операцій, тобто задача практично нерозв'язна на сучасних ЕОМ.

Наступний характерний приклад однонаправленої функції - це модульна експонента з фіксованими підставою і модулем.

Хай А і N- цілі числа, такі, что 1<=А< N. Визначимо множину ZN:

ZN={0, 1, 2 ..., N-1}.

Тоді модульна експонента з підставою А по модулю N представляє собою функцію

FA,N : ZN -> ZN

FA,N (x) =A x (mod N),

Де x-ціле число, 1 <= x <= N-1

2.3Задача дискретного логарифмування

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

FA,H(х).

Якщо y = Ах, то природно записати х = logA(у).Поэтому задачу обігу функції FA,H(х) називають задачею знаходження дискретного логарифма або задачею дискретного логарифмування.

Задача дискретного логарифмування формулюється таким чином. Для відомих цілих А, N, y знайти ціле число х, таке, что Аxmod N = y.

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

За сучасними оцінками теорії чисел при цілому числі A, розмір якого зрівнюється з 2664 , цілому числі, розмір якого зрівнюється з 2664, рішення задачі дискретного логарифмування (знаходження показника ступеня х для відомого y) потребує близько 1026 операцій тобто ця задача має в 103 разів більшу обчислювальну складність, ніж задача розкладання на множники. При збільшенні довжини чисел різниця в оцінках складності задач зростає.

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

2.4 Однонаправлені функції з "таємним ходом"

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

Функція F : X->Y відноситься до класу однонаправлених функцій з "таємним ходом" в тому випадку, якщо вона є однонаправленою і, крім того можливе ефективне обчислення зворотньої функції, якщо відомий "потайний хід" (секретне число, рядок, або інша інформація що асоціюється з даною функцією). Як приклад однонаправленої функції з ,,потайным ходом, можно вказати RSA модульну експоненту, що використовується в криптосистемі, з фіксованими модулями і показником ступеня. Змінна підстава модульної експоненти використовується для вказівки числового значення повідомлення М або криптограми С.

Лекція Алгоритм RSA

Розглядається один з перших і найвідоміших алгоритмів асиметричного шифрування даних, розроблений авторами Rivest, Shamir і Aldeman в 1978 році. Описуються супутні алгоритми визначення простих чисел, найбільшого загального дільника і швидкого зведення в ступінь.

1 Опис алгоритму

Першою і найвідомішою криптографічною системою з відкритим ключем була, запропонована у 1978 році так звана система RSA. Її назва походить від перших букв прізвищ авторів Rivest, Shamir і Aldeman, які придумали її під час сумісних досліджень в Массачусетському технологічному інституті у 1977 році. Вона заснована на труднощі розкладання дуже великих цілих чисел на прості співмножники. Міжнародна мережа електронного переліку платежів SWIFT вже вимагає від банківських установ, що користуються її послугами, вживання саме цієї криптографічної системи. Алгоритм роботи RSA складається з наступних трьох етапів:

1.етап генерації відкритого та закритого ключів

2.етап шифрування відкритого тексту

3.етап розшифрування шифртексту

Опишемо алгоритм, за яким відправник A передає відкритий текст M отримувачу B.

I етап. Генерація відкритого та закритого ключів отримувача В.

Крок 1. Вибір отримувачем В два дуже великі прості числа Р і Q.

Крок 2. Визначення отримувачем В значення модуля шифрування N=P*Q

Крок 3. Визначення отримувачем В значення функції Ейлєра F(N) = (P1)(Q1 ).

Крок 4. Вибір отримувачем В значення відкритого ключа Ов за наступними умовами:

•1 < Ов < F(N);

•НЗД(Ов, F(N)) = 1

Крок 5. Вибір отримувачем В значення закритого ключа kв за наступними умовами:

•(Зв * Ов) mod F(N) = 1;

•Зв <> Ов.

Крок 6. Передача пари чисел (N, Ов) до відправнику А.

Функція Ейлєра F(N) вказує на кількість чисел x: 1 < x < N, для яких НЗД(F(N), x) = 1. НЗД найбільший загальний дільник, тобто F(N)та x повинні бути взаємно простими числами.

Для рішення рівняння (Зв * Ов) mod F(N) = 1, можна виконати наступні перетворення: (Зв * Ов) mod F(N) = 1; =>

Зв = (k* F(N) + 1 ) / Ов, де k = 1, 2, 3 ...,; крім того значення kв повинно бути цілим числом.

I I етап. Шифрування відкритого тексту

Крок 7. Кодування відкритого тексту M = {m1, m2, ..., mi, ..., mn} з використанням таблиці кодування та умови:

1< mi < (N1)

Крок 8. Шифрування відкритого тексту з формуванням шифртексту C = {c1, c2, ..., ci, ..., cn}: ci = mi Оb mod(N)

Крок 9. Передача шифртексту C отримувачу B.

I I етап. Розшифрування шифртексту

Крок 10. Шифрування шифртексту C = {c1, c2, ..., ci, ..., cn} з формуванням відкритого тексту

M= {m1, m2, ..., mi, ..., mn}: mi = ci Зb mod(N)

Крок 11. Розкодування відкритого тексту M = {m1, m2, ..., mi, ..., mn} з використанням таблиці кодування.

10.2 Алгоритм визначення простих чисел

Мала теорема Ферма. Нехай p просте число. Тоді для всякого цілого чис ла b, відмінного від нуля, справедливе порівняння bp1 == 1 (mod p) .

Мала теорема Ферма є безпосереднім слідством теореми Лагранжа (порядок будьякого елементу групи ділить порядок групи) і того факту, що кільце Zp у разі простого p є полем, тобто всі його ненульові елементи належать групі оборотних елементів. Порядок групи оборотних елементів кільця Zp рівний p1 .

Найпростіший тест перевірки простоти числа m полягає в перевірці малої теореми Ферма. Виберемо довільне ціле число b (наприклад, b = 2), і піднесемо його до ступеня m 1 по модулю m. Якщо ми отримає не одиницю, то по малій теоремі Ферма число m складове. Проблема полягає в тому, що якщо

bm1 = = 1 (mod m), тоді нічого не можна сказати пр о m.

Стародавні греки помилково вважали, що всі числа m, що задовольняють обігу малої теореми Ферма для підстави 2, прості: якщо

2m1 = = 1 (mod m), тоді m просте число.

Мінімальний контрприклад до цього твердження був знайдений тільки в XVII столітті:

2340 = = 1 (mod 341)

але число 341 не просте, так як 341 = 11 * 31.

(Дійсно, 2340 = (210)34 = 102434, але 1024 = 3 * 341 + 1 == 1 (mod 341), тому 102434 == 1 (mod 341).)

Те, що 341 не задовольняє малій теоремі Ферма, може бути показане за допомогою інших підстав:

3340 == 56 (mod 341)

Проте існують числа, які не є простими, але які поводяться як прості в малій теоремі Ферма. Такі числа називаються кармайкловими.

Визначення. Число m називається кармайкловим, якщо воно не просте і для всякого b, взаємно простого з m, виконується твердження малої теореми Ферма:

bm1 == 1 (mod m).

Мінімальні кармайклові числа це 561, 1105, 1729 . ..

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

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

Тест Рабіна є вірогідністю. Це означає, що він використовує датчик випадкових чисел і, таким чином, працює не детерміновано. Для вхідного цілого числа m тест Рабіна може видати одну з наступних двох відповідей.

1.Число m є складовим.

2.Не знаю.

Уразі першої відповіді число m дійсно є складовим, тест Рабіна пред'являє доказ цього факту. Друга відповідь може бути видана як для простого, так і для складового числа m. Проте для будьякого складового числа m вірогідність другої відповіді не перевищує 1/4. Цінність тесту Рабіна полягає саме в нерівності, яка обмежує зверху вірогідність другої відповіді для довільного складового числа m.

Таким чином, якщо ми застосуємо 100 разів тест Рабіна до числа m і отримаємо 100 відповідей не "знаю", то можна з великою вірогідністю затверджувати, що число m простої. Більш точно, вірогідність отримання ста відповідей не "знаю" для складового числа m не перевищує (1/4) 100, тобто практично рівна нулю. Проте тест Рабіна не пред'являє доказу того, що число m просте.

Перейдемо безпосередньо до викладу тесту Рабіна. Ми перевіряємо простоту вхідного числа m. Припустимо, що число m непарне. (Існує тільки одне парне просте число 2 .) Тоді число

m1 парне. Відрекомендуємо його у вигляді m 1 = 2t * s де s непарне число. Виберемо випадкове число b таке, що

b =/= 0, b =/= 1 (mod m), 1 < b < m

При виборі b використовується датчик випадкових чисел.

Використовуючи алгоритм швидкого зведення в ступінь по модулю m, обчислимо наступну послідовність елементів кільця Zm:

x0 == bs (mod m)

x1 == x0 * x0 (mod m)

x2 == x1 * x1 (mod m)

...

xt == xt1 * xt1 == bm 1 (mod m)

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

Тест Рабіна видає відповідь 'm складове число ' у випадку, якщо

1)xt =/= 1 (mod m), або

2)у послідовності x0, x1, x2 ..., xt є фрагмент вигляду ... *, 1 ... де зірочкою позначено число, відмінне від одиниці або мінус одиниці по модулю m.

Інакше тест Рабіна видає відповідь не "знаю". Послідовність x0, x1 ..., xt в цьому "поганому" випадку або починається з одиниці, або містить (1) денебудь не в кінці.

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

2 <= b < 70ln2m

апотім перевірити, чи не є m ступенем простого числа. Проте його правильність залежить від недоведеної в даний час гіпотези Рімана.

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

3 Алгоритм визначення найбільшого загального дільника

Один з найважливіших результатів елементарної теорії чисел затверджує, що найбільший загальний дільник і n два цілі числа, хоча б одне з яких не дорівнює н улю. Тоді їх найбільший загальний дільник d = НЗД(m,n) виражається у вигляді двох цілих чисел виражається у вигляді їх лінійної комбінації з цілими коефіцієнтами. Нехай d = um+vn, де u і v деякі цілі числа.

Результат цей дуже важливий для практики, оскільки дозволяє обчислити зворотний елемент до n в кільці вирахувань по модулю m. Дійсно, хай числа m і n взаємно прості, тобто НЗД(m,n)= 1. Тоді 1 = um+vn

звідки слідує v*n = 1u*m

v*n = 1(mod m)

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

Для обчислення найбільшого загального дільника d і одночасно чисел u і v використовується так званий розширений алгоритм Евкліда. В звичному алгоритмі Евкліда пара чисел (а,b)в циклі замінюється на пару (b,r), де r залишок від розподілу а на b, при цьому найбільший загальний дільник біля обох пар однаковий. Початкові значення змінних а і b дорівнюють m і n, відповідно. Алгоритм закінчується, коли b стає рівним нулю, при цьому а міститиме значення найбільшого загального дільника.

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

Отже, в алгоритмі беруть участь змінні а, b, u1, v1, u2, v2, для яких виконується наступний інваріант циклу:

I(а, b, u1, v1, u2, v2): НЗД(а,b)= НЗД(m,n)

а= u1m+v1n b = u2m+v2n

Початкові значення цих змінних забезпечують виконання інваріанта:

а= m, b = n

u1 = 1, v1 = 0

u2 = 0, v2 = 1.

Умовою завершення циклу, як і в звичному алгоритмі Евкліда, є рівність нулю змінної b:

Q(а, b, u1, v1, u2, v2): b = 0.

Залишилося написати тіло циклу, що зберігає інваріант і зменшуюче абсолютну величину змінної b. Це неважко зробити, виходячи з інваріанта циклу. В звичному алгоритмі Евкліда пари (а,b) замінюється на (b,r), де r залишок від розподілу а на b.

а = gb+r |r| < |b|.

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

ціла частина(х)= ціла частина(x)

Наприклад, ціла частина(3,7)= 3. Це дозволяє прац ювати з негативними числами так само, як і з позитивними, тобто взагалі не стежити за знаком! Відзначимо також, що в більшості мов програмування вважається, що результат будьяко ї операції з цілими числами є цілим числом, наприклад, 8/3 = 2.

Змінна g обчислюється як ціла частина залишку від розподілу а на b:

g = ціла частина (а/b)

Виразимо залишок r у вигляді лінійної комбінації а і b:

r = аgb

Використовуючи інваріант циклу, можна виразити r через початкові числа m і n:

r = аgb = (u1m+v1n)g(u2m+v2)= (u1gu2)m+(v1gv2)

n.

Через u'1, v'1, u'2, v'2 позначаються нові значення змінних u1, v1, u2, v2. При заміні (а,b) (b,r) вони обчислюються таким чином:

u'1 = u2, v'1 = v2

u'2 = u1gu2, v'2 = v1gv2

По завершенню циклу відповідь знаходитиметься в змінних а (НЗД початкових чисел m і n), u1, v1 (коефіцієнти виразу НЗД через m і n).

Опишемо алгоритм на псевдоалгоримічній мові:

алгоритм Розширений алгоритм Евклида( вх: цілий m, цілий n

вых: цілий d, цілий u, цілий v

)

дано: цілі числа m, n, хоча б одне відмінне від нуля;

треба: обчислити d = НОД(m, n) і знайти u, v такі, що d = u * m + v * n;

початок алгоритму

цілий а, b, q, r, u1, v1, u2, v2;

цілий t;

// допоміжна змінна

//ініціалізація а := m; b := n;

u1 := 1; v1 := 0;

u2 := 0; v2 := 1;

твердження: НЗД(а, b)== НЗД(m, n) і

а == u1 * m + v1 * n і b == u2 * m + v2 * n;

цикл поки b != 0

інваріант: НЗД(а, b)== НЗД(m, n) і

а == u1 * m + v1	* n і
b == u2 * m + v2	* n;

q := а / b; // ціла частина залишку від розподілу а на b r := а % b; // залишок від розподілу а на b

а := b; b := r; // замінюємо пару (а, b) на (b, r)

// Обчислюємо нові значення змінних u1, u2

t := u2;		// запам'ятовуємо старе значення u2
u2	:= u1 q * u2; // обчислюємо нове значення u2
u1	:= t;	// нове значення u1 := старе

//значення u2

//Аналогічно знаходимо нові значення змінних v1, v2 t := v2;

v2 := v1 q * v2;

v1 := t; кінець циклу

твердження: b == 0 і НЗД(а, b)== НЗД(m, n) і

а== u1 * m + v1 * n;

//Видаємо відповідь

d := а;

u := u1; v := v1; кінець алгоритму

5 Алгоритм швидкого зведення в ступінь

Хай у нас є деяке число а, яке потрібне піднести до ступеня d (можливо, по модулю n). Можна просто помножити а саме на себе d раз, але при великих розмірах чисел це досить складна і повільна операція. Розглянемо алгоритм, обчислюючий dk за О(logk) операцій. В квадратних дужках вказані зміни, необхідні для обчислення ступеня по модулю.

Крок 1. Представимо d в двійковій системі счислення d = d02r + ... + dr1 2 + dr, де di, цифри в двійковому уявленні, рівні 0 або 1, d0=1.

Крок 2. Покладемо a0 =a і потім для i=1 ...,r обчислимо

ai = ai1 2 * adi [(mod n)].

Крок 3. ar є значення ad [(mod n)].

4 Інші асиметричні криптоалгоритми

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

4.1 Алгоритм ЭльГамаля

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

У1985 році ЕльГамаль запропонував новий алгоритм, криптостійкість якого базується лише на однонаправленності вирішення задачі дискретного логарифмування.

Алгоритм передачі відкритого тексту M від користувача A (відправник) до користувача B (отримувач) складається з наступної послідовності кроків.

Схема роботи алгоритма представлена на рисунку 4.1

Рис. 4.1 Схема роботи алгоритму ЕльГамаля

Крок 1. Відправник А і одержувач В домовляються про просте число Р та ціле число G: 1 < G < P.

Крок 2. Одержувач В вибирає закритий ключ випадко ве число Зв: 1 < Зв < P. Крок 3. Одержувач В обчислює значення відкритого ключа Oв = GЗвmod P Крок 4. Одержувач В відправляє відправнику А відкритий ключ Oв

Крок 5. Відправник А вибирає закритий ключ випадк ове число За за умовами: а) 1 < За < P; б) НЗД(За, P 1) = 1

Крок 6.	Відправник А обчислює відкритий ключ Oа = GЗа mod P
Крок 7.	Відправник А шифрує відкритий текст М: ci = mi ( ОвЗа mod P).
Формує шифртекст C = {c1, c2, ..., cn}
Крок 8.	Відправник А відправляє пару < Oа, C >
Крок 9.	Одержувач В розшифровує шифртекст:

mi = ci ( Оа Зв mod P)

Аналіз формул на кроку 7 та кроку 9, які використовують функцію , вказує на можливість розшифрування тільки при наступному рівнянні ( Ов mod P) = ( Оа Зв mod P). Перевіримо це

через наступні перетворення: ( ОвЗа mod P) = ( Оа Зв mod P)

(( GЗвmod P )Заmod P) = (( GЗа mod P)Зв mod P)) GЗвЗаmod P = GЗаЗв mod P

Усистемі ЕльГамаля ступінь захисту більше, ніж у алгоритмі RSA при одному розмірі N, що дозволяє майже на порядок прискорити швидкість шифрування та розшифрування. Криптостійкість системи ЭльГамаля заснована на тому, що можна легко обчислити ступінь цілого числа, тобто провести множення його самого на себе будьяке число разів так же, як і при операціях зі звичайними числами. Але складно знайти показчик ступеня, в який потрібно звести задане число, щоб одержати інше, теж задане. В загальному вигляді ця задача дискретного логарифмування здається більш складною, ніж розклад великих чисел на прості множники, на основі чого можна припустити, що складнощі розкриття систем RSA і ЕльГамаля будуть схожими.

4.3 Алгоритм ДіффіХелмана

В1976 году Діфі та Хеллман запропонували протокол відкритого розподілу ключів. Він обумовлює незалежну генерацію кожним з пари користувачів своего випадкового числа та перетворення його за допомогою деякої процедури, обмін перетвореними числами по відкритому каналу связку і обчислення загального секретного ключа на основі інформації, заполученої в процесі зв'язку між користувачами. Кожний такий ключ існує тільки протягом

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

Схема роботи алгоритма представлена на рисунку 4.3