Аналіз і стійкість криптографічних систем в системах штучного інтелекту

Размещено на http://www.allbest.ru/

Аналіз і стійкість криптографічних систем в системах штучного інтелекту

Реферат

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

Робота складається з 3-х розділів, кожен з яких присвячено певній системі шифрування. В роботі розглянуто такі відомі шифри, як DЕS, що використовувався в якості міжнародного стандарту шифрування з 1977 по 1994 р., та RSА, принцип дії якої ґрунтується на певних фактах з теорії чисел. Для кожної вибраної системи наведено короткі історичні відомості, опис принципу дії та теоретична база, приклад програми, що реалізує дану систему та результат її роботи. А також спроби атаки на даний шифр та аналіз отриманих результатів.

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

1. Вступ

1.1 Що таке криптографія?

Як передати певну інформацію певному адресату таємно від інших? Існують три основні шляхи вирішення цієї проблеми.

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

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

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

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

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

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

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

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

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

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

Введемо ще деякі поняття.

Атака на шифр - спроба злому шифру.

Стійкість шифру - здатність шифру протистояти різноманітним атакам на нього.

1.2 Криптографічні системи

Історично криптографічні методи розроблялись або окремими вченими - як цікаві задачі (напр., решітка Кардано), або дипломатами та політиками - як нагальна необхідність для передачі секретної інформації (напр., «шифр Цезаря»), тому мали розрізнену структуру та індивідуальне застосування. Ситуація змінилась з виходом у світ в 1946 р. праць К. Шеннона, якій узагальнив напрацьований до нього криптографічний досвід, та заклав основи для розвитку криптографії як математичної науки. Зокрема, він показав, що складні шифри можуть бути представлені комбінацією двох найпростіших - шифру заміни та шифру підстановки. Надзвичайно важливою для подальшого розвитку криптографії була також обґрунтована Шенноном теорема про існування і єдність абсолютно стійкого шифру.

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

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

· можливості користувача щодо захисту секретної інформації;

· можливості ймовірного противника щодо атаки на шифр;

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

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

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

· час від часу змінювати шифр, змінюючи тільки ключ;

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

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

Таким чином, процес шифрування / дешифрування передбачає наявність наступних об'єктів:

1) Р - скінчена множина можливих відкритих текстів;

2) С - скінчена множина можливих шифрованих текстів;

3) К - ключовий простір, скінчена система можливих ключів;

4) F - множина функцій шифрування f_k: РК-С, що перетворюють відкритий текст хР на шифроване повідомлення s= f_k (х), sС з використанням деякого ключа kК;

5) D - множина функцій дешифрування d_k: С-Р, що здійснюють зворотне перетворення.

Сукупність означених об'єктів {Р, С, К, F, D}, така, що kК f_kF, d_kD:

(d_k f_k) (х)= (f_k d_k) (х)=х,

називають криптосистемою, або системою шифрування.

Зауважимо, що скінченність вказаних множин зумовлена скінченністю алфавіту - множини символів, що використовуються для їх запису; проте не треба думати, що цей факт спрощує задачу противника - так, наприклад, система шифрування, що працює з 64-символьними блоками, записаними двійковою системою, має 2 ⁶⁴ можливих слів, а кількість можливих ключів становить (2 ⁶⁴)!, що практично унеможливлює атаку методом простого підбору ключів (див. далі розділ 2.1. Блокові шифри).

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

І один і інший тип криптосистем мають низку переваг та недоліків. Далі ми розглянемо їх більш детально на прикладі відомих та широко застосовних систем шифрування, як стандарт DЕS та RSА.

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

2.1 Загальні відомості про блокові шифри

Під N - розрядним блоком будемо розуміти послідовність із нулів і одиниць довжиною N:

x = (x_0. x_1,…., x_N-1) Z_2,N

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

x^N-i-1

Блоковим шифром будемо називати елемент

SYM (Z_2.N): : x y = (x),

де x = (x_0. x_1,…., x_N-1), y=(y₀, y_1, …., y_N-1).

Вираз:

у = {к, х}

будемо використовувати для позначення N-розрядного блока шифрованого тексту, отриманого в результаті шифрування N-розрядного блока вихідного тексту х із використанням підстановки {k, що відповідає ключу kК.

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

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

Формально F-функцію можна подати у вигляді відображення

F: Z_{2, N/2} Z_2,k Z_{2, N/2}

де N - довжина перетворюваного блока тексту (повинна бути парною), k - довжина використовуваного блока ключової інформації.

Нехай М - блок тексту, зобразимо його у вигляді двох підблоків однакової довжини М = {А, В. Тоді один цикл (ітерацію) мережі Фейстеля визначають так:

M_i+1 = B_i¦(F(B_i, k_i)A_i),

де M_i = A_i, B_i, ¦ - операція конкатенації, а - побітне виключаюче АБО.

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

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

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

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

2.2 Особливості стандарту DES

Найпопулярніша сучасна схема шифрування базується на стандарті DES (Data Encryption Standard - стандарт шифрування даних), прийнятому в 1977 р. Відповідно до цього стандарту дані шифрують 64-бітовими блоками з використанням 56-бітного ключа. Багатошаровий алгоритм перетворює 64-бітові блоки тексту, які надходять на вхід у 64-бітні блоки шифрованого тексту. Цей же алгоритм і з тим же ключем служить для зворотного перетворення шифрованого тексту у відкритий.

Але перш ніж стати офіційним стандартом, запропонований IBM алгоритм зазнав жорстокої критики, яка не вщухає до сьогодні. Нападок зазнають, в основному, дві особливості шифру. По-перше, в початковому алгоритмі LUCIFER фірми IBM використовувалися ключі довжиною 128 бітів, а в запропонованому стандарті довжина ключа зменшена до 56 бітів. Критики побоювалися (і побоюються досі), що такий розмір ключа занадто малий для того, щоб шифр міг гарантовано протистояти спробам криптоаналізу з простим перебором всіх можливих варіантів (сьогодні, з бурхливим розвитком комп'ютерної техніки, реалізація такої атаки стала фактом). Другий серйозний випад критиків спрямований проти фактів засекреченості внутрішньої структури DES, а саме структури S-матриць. Тому користувачі не могли бути впевнені в тому, що у внутрішній структурі DES немає якихось дефектів, за допомогою яких спеціалісти АНБ могли б розшифрувати повідомлення, не маючи ключа. Подальші дослідження, зокрема, останні праці з різницевого криптоаналізу, дозволяють з більшою впевненістю стверджувати, що DES має досить надійну внутрішню структуру. Більше того, за ствердженнями учасників проекту з боку ІВМ, єдиними змінами, внесеними в представлений ними проект стандарту, були запропоновані АНБ зміни в структурі S-матриць із метою укріплення імовірних слабких місць алгоритму, знайдених у ході оцінки проекту.

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

2.3 S-DES

10-бітний ключ

8-бітний блок 8-бітний блок

шифрованого тексту шифрованого тексту

Рис. 2.1. Схема спрощеного алгоритму S-DES

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

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

Алгоритм шифрування передбачає послідовне виконання п'яти операцій: початкової перестановки IP; раундової функції, що складається з перестановок і підстановок; перестановки SW, коли дві половинки блока по 4 біти переставляються місцями; ще одного застосування раундової функції; і, нарешті, перестановки ІР-1 оберненої до початкової. Послідовне використання кількох перестановок і підстановок значно ускладнюють криптоаналіз.

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

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

2.3.1 Процедура генерування раундових підключів

1. Спочатку біти ключа переставляються так. Якщо 10-бітний ключ подати у вигляді k₁, k₂,…., k₁₀ то перестановка РК_10 задається таблицею:

РК_10
3	5	2	7	4	10	1	9	8	6

Ця таблиця символізує позицію біта вхідних даних у вихідній послідовності: першим стає 3-й біт; другим - 5-й, третім - 2-й і т.д. Наприклад, ключ (1010011110) відповідно до цієї перестановки перетворюється в послідовність (1001001111).

Ключ розділяється на дві 5-бітні половини. Окремо перша половина й окремо друга піддаються циклічному зсуву ліворуч на одну позицію. У нашому прикладі в результаті буде отримана послідовність (00100 11110).

Отримана послідовність піддається перестановці РК_8, у результаті якої з 10-бітного ключа обирається 8-бітна послідовність за таким правилом:

РК_8
6	3	7	4	8	5	10	9

У результаті цієї операції ми отримуємо перший раундовий підключ (К1). У нашому прикладі він буде мати вигляд (11101001).

Для генерування другого раундового підключа К2, необхідно повернутися на крок назад, до двох 5-бітних рядків до застосування Р8 та виконати для кожного з цих рядків циклічний зсув праворуч на дві позиції. У нашому прикладі значення підключів (00001 11000) перетворяться у (01001 00111).

2. Нарешті, застосувавши до цієї послідовності перестановку РК_8, отримаємо другий раундовий підключ К2 Для нашого прикладу результатом буде (00001111).

2.3.2 Шифрування S-DES

1. Початкова і кінцева перестановки (IP та IP-1). На вхід алгоритму подається 8-бітний блок відкритого тексту, до якого застосовується початкова перестановка IP:

IP
2	6	3	1	4	8	5	7

Можна пересвідчитися, що ці дві таблиці дійсно обернені одна до одної, тобто ІР-1 (ІР(М)) = М.

2. Раундова функція FK. Розіб'ємо вхідний блок тексту після ІР-перестановки на два 4-бітні підблоки. Лівий 4-бітний блок позначимо L, а правий - R. Тоді циклову функцію можна записати у вигляді формули

FK(L, R) = (LF (R, Kі), R). (2.1)

Тут Kі означає цикловий підключ, К1, або К2; - по бітне XOR.

Тепер опишемо саму циклову функцію. На вході вона отримує 4-бітне значення (n1, n2, n3, n4), тобто праву половину вхідного блока. Перша операція - операція розширення та перестановки. Її можна також зобразити таблицею

Розширення з перестановкою
4	1	2	3	2	3	4	1

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

n₄ n₁ n₂ n₃

n₂ n₃ n₄ n₁

До цього значення додається 8-бітний підключ за допомогою операції XOR. Це можна зобразити так:

n4+k1 n1+k2 n2+k3 n3+k4

п2+k5 п3+k6 n4+k7 n1+k8.

Перейменуємо отримані елементи:

p₀₀ p₀₁ p₀₂ p₀₃

p₁₀ p₁₁ p₁₂ p₁₃

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

Модулі S_0 і S_1 задаються так:

S_0=	1	0	3	2	S_1=	1	1	2	0
	1	2	1	0		2	0	1	3
	0	2	1	3		3	0	1	0
	1	0	3	1		3	1	0	2

Рядки та стовпчики нумеруються, починаючи з нуля.

Ці модулі заміни працюють так. Перший і четвертий біти вхідної послідовності вважаються двійковим представленням номера рядка, а другий і третій - номерами стовпця. Елемент, що знаходиться на перетині цих рядка і стовпця, задає двобітне вихідне значення. Наприклад, якщо (p₀₀, p₀₃) = (00) та (р₀₁, p₀₂)=(10), то вихідні два біти задаються значенням, яке знаходиться на перетині 0-го рядка та 3-го стовпця, тобто це буде число 1, а у двійковому представленні -01.

Аналогічну операцію виконують і з другим рядком р₁₀ р₁₁ р₁₂ р₁₃

Після застосування матриць заміни результат піддають перестановці Р_4 за таким законом:

Р_4
2	4	3	1

Результат перестановки Р4 і буде результатом функції F_K. Отримана послідовність бітів додається за модулем 2 з лівою половиною L вхідного блока і буде новою лівою половиною. Права половина передається на вихід циклу без змін.

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

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

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

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

2.3.3 Програмна реалізація

Приклад 2.1. Нехай маємо 8-бітовий блок відкритого тексту а =10010111, зашифруємо його в системі S-DЕS з параметрами, вказаними вище.

Код програми:

# include <iostream>

# include <string.h>

# include <conio.h>

# include <math.h>

using namespace std;

int IP[8]={2,6,3,1,4,8,5,7}; // застосовані перестановки і блоки

int IP_1 [8]={4,1,3,5,7,2,8,6}; вводяться як масиви

int P_rozsh[8]={4,1,2,3,2,3,4,1};

int S_0 [4] [4]={1,0,3,2,1,2,1,0,0,2,1,3,1,0,3,1};

int S_1 [4] [4]={1,1,2,0,2,0,1,3,3,0,1,0,3,1,0,2};

int P_4 [4]={2,4,3,1};

int K[10]={1,0,1,0,0,1,1,1,1,0};

int PK_10 [10]={3,5,2,7,4,10,1,9,8,6};

int PK_8 [8]={6,3,7,4,8,5,10,9};

class Shifr_object

{

private:

int *Massiv[];

int *Shifr_a[];

int razr, r, j, s;

public:

Shifr_object (int x);

~Shifr_object();

int F (int a);

int IP (int a, int k);

};

Shifr_object: Shifr_object (int x)

{

int razr=x;

int *Shifr_a=new int[razr];

int *Massiv=new int [2*razr];

}

Shifr_object:~Shifr_object()

{

delete [] Massiv;

delete [] Shifr_a;

}

int Shifr_object:F (int a) // раундова функція

{

int r=a;

cout<<endl<<«F:vhid: «<<a;

for (j=razr-1; j>=0; j-)

{

Shifr_a[j]=r % 2;

r=r/2;

}

for (j=0; j<2*razr; j++) // перестановка з розширенням

{

r=P_rozsh[j] - 1;

Massiv[j]=Shifr_a[r];

}

cout<<endl;

for (j=0; j<2*razr; j++)

{

Massiv[j]=(Massiv[j]+K[j])%2;

}

s=S_0 [Massiv[0]*2+Massiv[1]] [Massiv[2]*2+Massiv[3]]; // блок S_0

Massiv[0]=s/2;

Massiv[1]=s % 2;

s=S_1 [Massiv[4]*2+Massiv[5]] [Massiv[6]*2+Massiv[7]]; // блок S_1

Massiv[2]=s/2;

Massiv[3]=s % 2;

cout<<endl<< «F:vuhod:»;

s=0;

for (j=0; j<razr; j++) // перестановка Р_4

{

r=P_4 [j] - 1;

Shifr_a[j]=Massiv[r];

cout<<Shifr_a[j]<<»»;

s=(s+Shifr_a[j])*10;

}

return s;

}

int Shifr_object:IP (int a, int k) // функція, що реалізує підстановки

{IР та IР_1

int r, s, i;

r=a; i=k;

cout<<endl<< «IP_"<<i<<»:»;

for (j=2*razr-1; j>=0; j-)

{

Massiv[j]=r % 2;

r=r/2;

}

s=0;

for (int j=0; j<2*razr; j++)

{

if(! i) r=IP[j] - 1;

else r=IP_1 [j] - 1;

s=(s+Massiv[r])*10;

}

cout<<endl<<s;

return s;

}

int GEN_kluch (int i) // фунція генерації ключів

{

int k_1, k_2, r;

int *k=new int[10];

for (int j=0; j<10; j++) // перестановка РК_10

{

r=PK_10 [j] - 1;

k[j]=K[r];

}

k_1=0; k_2=0;

for (int j=0; j<5; j++) // виділення лівої

{

r=PK_10 [j] - 1;

k_1=(k_1+k[r])*10;

}

for (int j=0; j<5; j++) // та правої частин ключа

{

r=PK_10 [5+j] - 1;

k_2=(k_2+k[r])*10;

}

if(! i)

{

k_1<<1; k_2<<1;

}

else

{

k_1>>1; k_2>>1;

}

for (int j=4; j>=0; j-)

{

k[j]=k_1% 2;

k_1=k_1/2;

}

for (int j=4; j>=0; j-)

{

k [j+5]=k_2% 2;

k_2=k_2/2;

}

for (int j=0; j<8; j++) // перестановка РК_8

{

r=PK_8 [j] - 1;

K[j]=k[r];

}

delete [] k;

return 0;

}

int XOR (int a, int b) // функція побітного ХОR

{

int r, x, y, razr;

r=0; x=a; y=b; razr=1;

while (x||y)

{

r=r+(x % 2^y % 2)*razr;

x=x/10;

y=y/10;

razr*=10;

}

return r;

}

int main()

{

int a, a_l, a_r, i, j, r;

a=10010111;

cout<<«Vidkrute chislo: «<<a<<endl;

Shifr_object Ob_1 (4);

a=Ob_1.IP (a, 0); // виклик функції підстановки IР

for (int i=0; i<2; i++)

{

a_l=a/10000;

a_r=a % 10000;

j=GEN_kluch(i); // генерація i-го ключа

a_l=Ob_1.F (a_l); // виклик раундової функції

a=a_r*10000+XOR (a_l, a_r);

cout<<endl<<i+1<<» - uj raynd: «<<a;

}

a=Ob_1.IP (a, 1); // виклик функції підстановки IР_1

cout<<endl<<«Shifrovane chislo: «<<a;

getch();

return 0;

}

Результат роботи програми:

Vidkrute chislo: 10010111

IP_0: 01011101

F:vhid: 0101

F:vuhid: 1110

1-uj raynd: 11010011

F:vhid: 1101

F:vuhid: 1100

2-uj raynd:001111111

IP_1: 10111011

Shifrovane chislo: 10111011

2.3.4 Розшифрування зашифрованого тексту

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

Результат роботи програми:

Shifrovane chislo: 10111011

IP_0: 00111111

F:vhid: 0011

F:vuhid: 1010

1-uj raynd: 11110101

F:vhid: 1111

F:vuhid: 1000

2-uj raynd:01011101

IP_1: 10010111

Vidkrute chislo: 10010111

2.4 Криптоаналіз блокових шифрів

Припустимо, що противнику:

· відомий простір ключів К;

· відомий алгоритм визначення підстановки (к) за значенням ключа к;

· невідомо, який саме ключ к обрав користувач.

На основі цих даних противник може:

· отримати ключ унаслідок недбалості користувача і чи користувача j;

· перехопити (шляхом перехоплення телефонних і комп'ютерних повідомлень) шифрований текст у, який передається: користувачу j користувачем і, і використовувати всі можливі ключі з К до отримання повідомлення вихідного тексту;

· отримати відповідний вихідний і шифрований тексти (ху) і скористатися методом проби на ключ;

· отримати відповідний вихідний і шифрований тексти та дослідити співвідношення вихідного тексту х і шифрованого тексту у для визначення ключа k;

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

- лістинг на мові асемблера характеризується сильно вираженим структурованим форматом;

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

Припустимо, що N = 64 і кожен елемент SYM(Z_2,N) може бути використаний як підстановка, так що К = SYM(Z_2,N). Тоді існує 2 ⁶⁴ 64-розрядних блоки; противник не може підтримувати каталог із 2⁶⁴ ? 1,8*10 ¹⁹ рядками; проба на ключ за кількості ключів, що дорівнює (2⁶⁴)!, практично неможлива; відповідність вихідного і шифрованого текстів деяких N-розрядних блоків {к, х_і} = у_і, 0 ?і<т, не дає противнику інформації відносно значення {к, х для х {х_і}.

Системи шифрування з блоковими шифрами, алфавітом Z_2,64 i простором ключів К = SYM(Z_2,64) неподільні в тому розумінні, що підтримання каталогу частот появи букв для 64-розрядних блоків чи проба на ключ при кількості ключів 2⁶⁴ виходять за межі можливостей противника.

Отже, вимоги для якісного блокового шифру формуються так:

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

2. Необхідний досить великий простір ключів, аби уникнути можливості підбору ключа.

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

3. Система шифрування RSA

3.1 Опис RSА

Будь-яку інформацію досить просто (наприклад, через існуючу систему кодів ASCII) можна представити у вигляді послідовності цілих чисел. Тоді способи шифрування і дешифрування можна представити як деякі функції, задані на множині цілих чисел. Будемо вважати надалі, що всі числа, що підлягають шифруванню, та отримані в результаті, невід'ємні і менше деякого межового (вибраного, наприклад, з технічних міркувань) числа m. Тоді можемо розглядати їх як елементи кільця Z/mZ, а шифруючу функцію - як взаємооднозначне відображення

f: Z/mZ - Z/mZ.

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

f: х - х+k (mоd m),

де k - деяке фіксоване ціле.

В 1978 р. американці Р.Рівест, А. Шамір і Л. Адлеман (R.L. Rivest, A. Shamir, L. Adelman) запропонували функцію f з наступними властивостями:

а) існує досить швидкий алгоритм обчислення значень f(х);

б) існує досить швидкий алгоритм обчислення значень оберненої функції f^-1(х);

в) функція f(х) містить певний «секрет», знання якого дозволяє досить швидко обчислити значення f^-1(х); інакше обчислення f^-1(х) перетворюється на досить складну задачу, яка вимагає стільки часу для розв'язання, що по його закінченню зашифрована інформація втрачає свою цінність.

На основі цієї функції була створена діюча система шифрування, названа за першими літерами імен своїх творців - RSA. Функція f діє на деяке повідомлення х за таким правилом:

f: х -х^е(mоd m), е, m (3.1.1)

тоді дешифрування повідомлення а=f(х) зводиться до розв'язання конгруенції

х^е а (mоd m). (3.1.2)

Якщо показник степеня в (3.1.2) є взаємно простим з (m), тобто

НСД (е,(m))=1, (3.1.3)

то (3.1.2) має єдиний розв'язок. Тут (m) - функція Ейлера, кількість натуральних чисел від 1 до (m-1), взаємно простих з m. Зазначимо деякі властивості (m), відомі з курсу Теорії чисел, які будемо застосовувати далі:

(1)=1, (3.1.4)

(р)=р-1, де р - просте, (3.1.5)

(аb)=(а)(b), (3.1.6)

якщо а і b - взаємно прості, тому

(р^r)=р^r-1(р-1), де р - просте, r - натуральне. (3.1.7)

З (3.1.3-6) бачмо, що (m) визначається просто, якщо ми маємо розкладення m на прості множники. Далі, визначаємо d, таке, що:

dе1 (mоd (m)), 1?d(m) (3.1.8)

(так як е і (m) взаємопрості, то таке d існує і єдине). Далі, за теоремою Ейлера, х, взаємопростого з (m), виконується х^(m)1 (mоd m), тому

а^d х^dе х (mоd m). (3. 1.9)

Отже, вимагаючи ще, щоб (а, m)=1, отримуємо єдиний розв'язок конгруенції (3.1.2) у вигляді х=а^d(mоd m).

Зауважимо, що вимога (а, m)=1 не обов'язкова у випадку, коли m є добутком різних простих множників. Тому творці RSА запропонували використовувати таке m, що:

m=рq, де р, q - досить великі прості числа, тоді, згідно (3.1. 5,6):

(m)=(рq)=(р)(q)=(р-1) (q-1),

а умова (3.1.3) набуває виду:

НСД (е, р-1)= НСД (е, q-1)=1. (3. 1.10)

Пара Р=(е, m) є відкритим, тобто відомими всім користувачам, ключем системи. Будь-хто може посилати організатору повідомлення, шифровані функцією f, вказаною в (3.1.1), які організатор читає з допомогою закритого ключа S=(d, m), вибраного за умовою (3.1.8).

Якщо припусти, що супротивнику відомі відкриті числа та принцип шифрування, то при m невеликої розмірності (наприклад, 8 розрядів) досить просто знайти усі прості дільники числа m, перебравши всі числа від 1 до vm. А потім, обчисливши (m), знайти ключ d з умови (3.1.8). Проте із ростом m кількість простих чисел, які потрібно перевірити асимптотично дорівнює 2m (ln m)^-1. Так, для m, записаного сотнею десяткових знаків, не менше 4*10⁴² простих чисел, що можуть бути його дільниками. Найшвидші з відомих алгоритмів розкладу числа на прості множники не дають результату за прийнятний час - принаймні, за умов використання одного комп'ютера. Тому всі вдалі атаки на систему RSА були здійснені за допомогою розподілу розрахунків.

Для ілюстрації свого методу творці RSА зашифрували деяке повідомлення функцією (3.1), взявши в якості m 129-значне число. Отримана криптограма була опублікована разом з відкритими параметрами шифрування, першому, хто дешифрує її, була обіцяна премія в 100 $. Було також додатково вказано, що m є добутком двох простих чисел розрядністю 64 та 65 знаків, проте минуло 17 років, перш ніж шифр було розкрито. Не враховуючи підготовку, тільки до обчислення було залучено близько 600 добровольців та 1600 комп'ютерів, що працювали впродовж 220 днів.

3.2 Алгоритми та програмна реалізація системи

Далі наведемо алгоритми, використані безпосередньо при написанні коду програми.

3.2.1 Обчислення а^d(mоd m)

1. записуємо число d у двійковій системі числення:

d=d₀2^r+ d₁2^r-1+ … + d_r-12+ d_r,

де d_i - 0 або 1, d₀=1.

2. Покладемо а₀=а, кожне наступне а_i обчислюємо за формулою



3. а^r і є шуканим значенням а^d(mоd m).

Справедливість цього алгоритму випливає з наступної формули:

.

3.2.2 Алгоритм Евкліда пошуку НСД (а, b)

1. Обчислюємо r - остачу від ділення а на b (не порушуючи загальності, можемо вважати аb).

2. Якщо r=0, то b і є шукане число.

3. Якщо r0, то замінюємо пару (а, b) на (b, r) і повторюємо спочатку.

3.2.3 Генератор простих чисел

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

Теорема. Нехай N, S - непарні натуральні числа, такі, що N-1=S*R, причому простого дільника q числа S таке натуральне а, що:

.

Тоді простий дільник р числа N задовольняє

р 1 (mоd 2S).

Наслідок. Якщо виконані умови теореми і R?4S+2, то N - просте число.

Маємо наступний алгоритм:

1. Обираємо S - деяке просте число та R - парне з проміжку S?R?4S+2.

2. Перевіряємо число N=RS+1: якщо N не просте, то обираємо інше R, поки не знайдемо просте число. Побудоване таким чином, NS², а значить - має вдвічі більший розряд.

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

Цей спосіб реалізується досить просто і дозволяє на персональному комп'ютері отримувати прості числа порядку 10¹⁰.

3.3 Криптоаналіз RSА

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

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

m=(х-у)*(х+у),

тоді m=х²-у², звідки у²=х²-m.

Починаємо з х=[], і, збільшуючи на 1, шукаємо таке х, що х²-m є повним квадратом. В результаті отримуємо

m=(х-)*(х+), (3.3.1)

якщо m - просте, то (3.3.1) дає тривіальний розклад.

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

Атака: обчислення закритого ключа d. Ґрунтується на теоремі Вінера:

Нехай m=рq, де qр2q, d. Тоді, якщо відома пара (е, m), де е задовольняє (8), то існує ефективний спосіб обчислення d.

Захист: таким чином, якщо розмір m, наприклад, 1024 біти, потрібно обирати d розміром не менше як 256 бітів.

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

Захист: для кожного користувача генерувати власне значення m.

Атака Хастада: в системі з кількох користувачів повідомлення шифруються за індивідуальними параметрами для кожного користувача. Користувач В відсилає повідомлення х k адресатам А₁, А₂,… А_k, зашифроване з параметрами (е_і, m_і), і=1..k відповідно. Противник перехоплює k f_і(х) - шифрованих повідомлень. Якщо е_і=е і=1..k, то противник може відновити повідомлення х, якщо k?е. Навіть якщо х_і для і-того користувача є деякою фіксованою перестановкою вихідного повідомлення, наприклад,

х_і=і*2^m+х, (2.3.2)

все одно противник може отримати х при досить великому k.

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

Взагалі, для підвищення стійкості криптосистеми RSА рекомендовано використовувати досить великі значення е, наприклад е=2¹⁶+1=65537.

Атака Франкліна-Рейтера: нехай х, х₁ - два вихідних повідомлення, такі, що

х₁=g(х) (mоd m),

де g(х)= ах+b (mоd m), b0 - деякий лінійний многочлен, і f(х), f(х₁) - результат шифрування х, х₁ системою RSА з відкритим ключем (е, m). При е=3 противник, знаючи е, m, f(х), f(х₁) і g(х) зможе відновити х, х₁.

Захист: при е3 час злому шифру росте пропорційно е², тому така атака має успіх лише при невеликих значеннях е.

Як бачимо, підвищення безпеки досягається за рахунок накладення певних обмежень на вибір простих дільників основи системи m та збільшення розмірів ключа. Остання вимога обумовлена також стрімким ростом можливостей обчислювальної техніки впродовж останніх десятиріч. Запропонована Ріверстом, Шаміром та Адлеманом система зі 129-значною основою залишалась нерозкритою впродовж 17 років - на сьогодні надійною вважається система на основі RSА з m не менше 1024 бітів. В 2009 р. група вчених з Швейцарії, Франції, Нідерландів, Германії та США після трьох-річної праці отримала дані, зашифровані за допомогою коду RSА з модулем m довжиною 768 біт. За їх прогнозами, система з 1024-значною основою може бути розкрита в найближчі 3-4 роки.

3.2.4 Програмна реалізація

Код програми:

# include <iostream>

# include <string.h>

# include <conio.h>

# include <math.h>

using namespace std;

unsigned long Stepen (int a, int d, int M)… // функція піднесення а^d(mоd m),

{реалізує алгоритм 3.2.1.

unsigned long r;

int razr=0;

r=d;

while(r)

{

r=r/2;

razr++;

}

int *d_dv=new int[razr];

r=d;

for (int i=0; i<razr; i++) // цикл для представлення степеня в

{2-вій системі

d_dv[i]=r % 2; // тут і далі «%» - оператор, що повертає остачу від ділення, тільки для типу «іnt»

r=r/2; // для типу «іnt» - цілочислене

ділення

}

r=1;

for (int i=razr-1; i>=0; i-)

{

if (d_dv[i]) r=r*r*a;

else r*=r;

r=r % M;

}

delete d_dv;

return r;

}

int Evkl (int x, int y) // функція реалізує алгоритм

Евкліда 3.2.2.

{

int r, a, b;

a=x; b=y;

do

{

if (a>b)

{

r=a % b;

a=r;

}

else

{

r=b % a;

b=r;

}

}

while(r);

if (a>b) b=a;

return b;

}

int main()

{

unsigned long int x, f_x, M, fi_M;

int d, e, p, q;

p=11; q=13; // генерація параметрів шифрування

M=p*q; fi_M=(p-1)*(q-1); по заданим простим числам р і q

e=2;

while (Evkl(e, fi_M)!=1) e++;

cout<<«Vvedit povidomlennya, ne bilsche «<<M<<»:«<<endl;

cin>>x;

f_x=Stepen (x, e, M); // виклик функції піднесення до степеня е

по модулю m

cout<<endl<<«Vidcrituj kluch sustemu: (e, m)=(«<<e<<», «<<M<<»)«<<endl<<«Shifrovane povidomlennya: «<<f_x;

getch();

cout<<endl<<endl<<«Otrymane shifrovane povidomlennya: «<<f_x;

cout<<endl<<«Perevirka klucha…«<<endl;

d=fi_M/e;

while (e*d % fi_M!=1) d++; // підбір ключа, що задовольняє

умову 3.1.8

if((e*d)%fi_M!=1) cout<<endl<< «Kluch ne virnuj.»;

else

{

cout<<endl<< «Kluch virniy.»;

cout<<endl<<«Povidomlennya: «<<Stepen (f_x, d, M);

}

cout<<endl<<endl<< «Dlya vuhody natusnit Enter…»;

getch();

return 0;

}

Код програми написано мовою Dеv-С++.

Приклад 3.2.1. Візьмемо, для наочності, р=11, q=13. Повідомленням буде натуральне число з проміжку [0; m-1]. Тоді результат програми виглядатиме наступним чином:

Vvedit povidomlennya, ne bilsche 143: // Введіть повідомлення, не

більше…

115

Vidcrituj kluch sustemu: (e, m)=(7, 143) // Відкритий ключ системи:

Shifrovane povidomlennya: 80 // Шифроване повідомлення:

Otrymane shifrovane povidomlennya: 80 // Отримане шифроване повідомлення:

Perevirka klucha… // Перевірка ключа…

Kluch virniy. // Ключ вірний.

Povidomlennya: 115 // Повідомлення:

Dlya vuhody natusnit Enter… // Для виходу натисніть Enter…

Приклад 3.2.2. За тих самих умов спробуємо тепер збільшити вихідні прості числа, для чого скористаємось генератором простих чисел (алгоритм 3.2.3).

# include <iostream>

# include <string.h>

# include <conio.h>

# include <math.h>

using namespace std;

int Proverka_Deleniem (int N)

{

int d, r;

d=2; r=1;

while((r!=0)&&(d<N))

{

r=N % d;

d++;

}

if(! r) return 0;

else return N;

}

int Prostoe_chislo()

{

int i, N, R, S;

do

{

cout<<endl<< «Vvedite isxodnoe prostoe:»;

cin>>S;

}

while (! Proverka_Deleniem(S));

i=1; N=0; R=(S-3)*2;

while(i)

{

R=R+4;

N=R*S+1;

if (Proverka_Deleniem(N))

{

cout<<endl<< «N="<<N<<» - prostoe. Prodolzit? Press 1 (YES) or 0 (NO)»;

cin>>i;

S=N;

}

else i++;

if (i>N/4)

{

cout<<endl<<«Sdelano «<<i<< «popytok. Prodolzit? Press 1 (YES) or 0 (NO)»;

cin>>i;

}

}

getch();

return N;

}

int main()

{

int p=Prostoe_chislo();

int q=Prostoe_chislo();

cout<<endl<< «Poluchenu chisla: p="<<p<<» q="<<q;

getch();

return 0;

}

Результат роботи програми:

Vvedite isxodnoe prostoe: 11

N=353-prostoe. Prodolzit? Press 1 (YES) or 0 (NO) 0

Vvedite isxodnoe prostoe: 31

N=1861-prostoe. Prodolzit? Press 1 (YES) or 0 (NO) 0

Poluchenu chisla: p=353 q=1861

Тоді програма шифрування дасть наступний результат:

Vvedit povidomlennya, ne bilsche 656933:

111111

Vuberit e: 999

NOD (999, fi_М)=3

Vuberit e: 997

NOD (997, fi_М)=1

Vidcrituj kluch sustemu: (e, m)=(997, 656933)

Shifrovane povidomlennya: 599639

Otrymane shifrovane povidomlennya: 599639

Perevirka klucha…

Kluch virniy.

Povidomlennya: 111111

Dlya vuhody natusnit Enter…

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

Список літератури

криптографія шифр зашифрований генерування

1. Введення в криптографію. - під редакцією Ященко В.В., - М. 1998 р.-272 с.

2. Остапов С.Е., Валь Л.С. Основи криптографії: навчальний посібник. - Чернівці, 2008. - 188 с.

3. Шилдт Г. Довідник програміста по С/С++. - М.2006.-432 с.

4. http://ru.wikipedia.org/wiki/RSA

Размещено на Allbest.ru