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

 

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

Реферат

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

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

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

1. Вступ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сукупність означених обєктів {Р, С, К, F, D}, така, що " kÎК $ fkÎF, dkÎD:

(dk ° fk) (х)= (fk ° dk) (х)=х,

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

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

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

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

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

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

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

= (x0. x1,…., xN-1)Î Z2,N

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

N-i-1

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

p Î SYM (Z2.N): p: x ® y = p (x),

де x = (x0. x1,…., xN-1), y=(y0, y1, …., yN-1).

Вираз:

у = p{к, х}

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

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

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

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

: Z2, N/2 ´Z2,k ® Z2, N/2

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

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

i+1 = Bi?(F(Bi, ki)ÅAi),

де Mi = {Ai, Bi}, ? - операція конкатенації, а Å - побітне виключаюче АБО.

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

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

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

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

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

-бітний ключ

-бітний блок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-бітний ключ подати у вигляді k1, k2,…., k10 то перестановка РК_10 задається таблицею:

РК_1035274101986

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

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

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

РК_8637485109

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

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

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

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

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

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

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

FK(L, R) = (LÅF (R, Kі), R). (2.1)

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

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

Розширення з перестановкою41232341

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

4 n1 n2 n32 n3 n4 n1

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

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

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

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

p00 p01 p02 p0310 p11 p12 p13

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

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

S_0=1032S_1=1120121020130213301010313102

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

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

Аналогічну операцію виконують і з другим рядком р10 р11 р12 р13

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

Р_42431

Результат перестановки Р4 і буде результатом функції FK. Отримана послідовність бітів додається за модулем 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>namespace std;IP[8]={2,6,3,1,4,8,5,7}; // застосовані перестановки і блокиIP_1 [8]={4,1,3,5,7,2,8,6}; вводяться як масивиP_rozsh[8]={4,1,2,3,2,3,4,1};S_0 [4] [4]={1,0,3,2,1,2,1,0,0,2,1,3,1,0,3,1};S_1 [4] [4]={1,1,2,0,2,0,1,3,3,0,1,0,3,1,0,2};P_4 [4]={2,4,3,1};K[10]={1,0,1,0,0,1,1,1,1,0};PK_10 [10]={3,5,2,7,4,10,1,9,8,6};PK_8 [8]={6,3,7,4,8,5,10,9};Shifr_object

{:*Massiv[];*Shifr_a[];razr, r, j, s;:_object (int x);

~Shifr_object();F (int a);IP (int a, int k);

};_object: Shifr_object (int x)

{razr=x;*Shifr_a=new int[razr];*Massiv=new int [2*razr];

}_object:~Shifr_object()

{[] Massiv;[] Shifr_a;

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

{r=a;<<endl<<«F:vhid: «<<a;(j=razr-1; j>=0; j-)

{_a[j]=r % 2;=r/2;

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

{=P_rozsh[j] - 1;[j]=Shifr_a[r];

}<<endl;(j=0; j<2*razr; j++)

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

}=S_0 [Massiv[0]*2+Massiv[1]] [Massiv[2]*2+Massiv[3]]; // блок S_0[0]=s/2;[1]=s % 2;=S_1 [Massiv[4]*2+Massiv[5]] [Massiv[6]*2+Massiv[7]]; // блок S_1[2]=s/2;[3]=s % 2;<<endl<< «F:vuhod:»;=0;(j=0; j<razr; j++) // перестановка Р_4

{=P_4 [j] - 1;_a[j]=Massiv[r];<<Shifr_a[j]<<»»;=(s+Shifr_a[j])*10;

}s;

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

{IР та IР_1r, s, i;=a; i=k;<<endl<< «IP_"<<i<<»:»;(j=2*razr-1; j>=0; j-)

{[j]=r % 2;=r/2;

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

{(! i) r=IP[j] - 1;r=IP_1 [j] - 1;=(s+Massiv[r])*10;

}<<endl<<s;s;

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

{k_1, k_2, r;*k=new int[10];(int j=0; j<10; j++) // перестановка РК_10

{=PK_10 [j] - 1;[j]=K[r];

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

{=PK_10 [j] - 1;_1=(k_1+k[r])*10;

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

{=PK_10 [5+j] - 1;_2=(k_2+k[r])*10;

}(! i)

{_1<<1; k_2<<1;

}

{_1>>1; k_2>>1;

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

{[j]=k_1% 2;_1=k_1/2;

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

{[j+5]=k_2% 2;_2=k_2/2;

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

{=PK_8 [j] - 1;[j]=k[r];

}[] k;0;

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

{r, x, y, razr;=0; x=a; y=b; razr=1;(x||y)

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

}r;

}main()

{a, a_l, a_r, i, j, r;=10010111;<<«Vidkrute chislo: «<<a<<endl;_object Ob_1 (4);=Ob_1.IP (a, 0); // виклик функції підстановки IР(int i=0; i<2; i++)

{_l=a/10000;_r=a % 10000;=GEN_kluch(i); // генерація i-го ключа_l=Ob_1.F (a_l); // виклик раундової функції=a_r*10000+XOR (a_l, a_r);<<endl<<i+1<<» - uj raynd: «<<a;

}=Ob_1.IP (a, 1); // виклик функції підстановки IР_1<<endl<<«Shifrovane chislo: «<<a;();0;

}

Результат роботи програми:chislo: 10010111_0: 01011101:vhid: 0101:vuhid: 1110

-uj raynd: 11010011:vhid: 1101:vuhid: 1100

-uj raynd:001111111_1: 10111011chislo: 10111011

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

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

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

chislo: 10111011_0: 00111111:vhid: 0011:vuhid: 1010

-uj raynd: 11110101:vhid: 1111:vuhid: 1000

-uj raynd:01011101_1: 10010111chislo: 10010111

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 Опис RSА

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

: Z/mZ -> Z/mZ.

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

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

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

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

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

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

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

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

: х ->хе(mоd m), е, mÎN (3.1.1)

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

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

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

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

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

j(1)=1,(3.1.4)

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

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

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

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

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

еº1 (mоd j(m)), 1?d<j(m)(3.1.8)

(так як е і j(m) взаємопрості, то таке d існує і єдине). Далі, за теоремою Ейлера, "х, взаємопростого з j(m), виконується хj(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, що:

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

j(m)=j(рq)=j(р)j(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 до ?m. А потім, обчисливши j(m), знайти ключ d з умови (3.1.8). Проте із ростом m кількість простих чисел, які потрібно перевірити асимптотично дорівнює 2m (ln m)-1. Так, для m, записаного сотнею десяткових знаків, $ не менше 4*1042 простих чисел, що можуть бути його дільниками. Найшвидші з відомих алгоритмів розкладу числа на прості множники не дають результату за прийнятний час - принаймні, за умов використання одного компютера. Тому всі вдалі атаки на систему 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 у двійковій системі числення:

=d02r+ d12r-1+ … + dr-12+ dr,

де di - 0 або 1, d0=1.

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

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

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

.

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

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

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

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

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

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

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

.

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

р 1 (mоd 2S).

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

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

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

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

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

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

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

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

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

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

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

Починаємо з х=[], і, збільшуючи на 1, шукаємо таке х, що х2-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 адресатам А1, А2,… Аk, зашифроване з параметрами (еі, mі), і=1..k відповідно. Противник перехоплює k fі(х) - шифрованих повідомлень. Якщо еі=е "і=1..k, то противник може відновити повідомлення х, якщо k?е. Навіть якщо хі для і-того користувача є деякою фіксованою перестановкою вихідного повідомлення, наприклад,

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

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

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

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

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

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

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

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

Як бачимо, підвищення безпеки досягається за рахунок накладення певних обмежень на вибір простих дільників основи системи 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>namespace std;long Stepen (int a, int d, int M)… // функція піднесення аd(mоd m),

{реалізує алгоритм 3.2.1.long r;razr=0;=d;(r)

{=r/2;++;

}*d_dv=new int[razr];=d;(int i=0; i<razr; i++) // цикл для представлення степеня в

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

ділення

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

{(d_dv[i]) r=r*r*a;r*=r;=r % M;

}d_dv;r;

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

Евкліда 3.2.2.

{r, a, b;=x; b=y;

{(a>b)

{=a % b;=r;

}

{=b % a;=r;

}

}(r);(a>b) b=a;b;

}main()

{long int x, f_x, M, fi_M;d, e, p, q;=11; q=13; // генерація параметрів шифрування=p*q; fi_M=(p-1)*(q-1);по заданим простим числам р і q=2;(Evkl(e, fi_M)!=1) e++;<<«Vvedit povidomlennya, ne bilsche «<<M<<»:«<<endl;>>x;_x=Stepen (x, e, M); // виклик функції піднесення до степеня е

по модулю m<<endl<<«Vidcrituj kluch sustemu: (e, m)=(«<<e<<», «<<M<<»)«<<endl<<«Shifrovane povidomlennya: «<<f_x;();<<endl<<endl<<«Otrymane shifrovane povidomlennya: «<<f_x;<<endl<<«Perevirka klucha…«<<endl;=fi_M/e;(e*d % fi_M!=1) d++; // підбір ключа, що задовольняє

умову 3.1.8((e*d)%fi_M!=1) cout<<endl<< «Kluch ne virnuj.»;

{<<endl<< «Kluch virniy.»;<<endl<<«Povidomlennya: «<<Stepen (f_x, d, M);

}<<endl<<endl<< «Dlya vuhody natusnit Enter…»;();0;

}

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

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

більше…

kluch sustemu: (e, m)=(7, 143) // Відкритий ключ системи:povidomlennya: 80 // Шифроване повідомлення:shifrovane povidomlennya: 80 // Отримане шифроване повідомлення:klucha… // Перевірка ключа…virniy. // Ключ вірний.: 115 // Повідомлення:vuhody natusnit Enter… // Для виходу натисніть Enter…

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

# include <iostream>

# include <string.h>

# include <conio.h>

# include <math.h>namespace std;Proverka_Deleniem (int N)

{d, r;=2; r=1;((r!=0)&&(d<N))

{=N % d;++;

}(! r) return 0;return N;

}Prostoe_chislo()

{i, N, R, S;

{<<endl<< «Vvedite isxodnoe prostoe:»;>>S;

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

{=R+4;=R*S+1;(Proverka_Deleniem(N))

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

}i++;(i>N/4)

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

}

}();N;

}main()

{p=Prostoe_chislo();q=Prostoe_chislo();<<endl<< «Poluchenu chisla: p="<<p<<» q="<<q;();0;

}

Результат роботи програми:isxodnoe prostoe: 11=353-prostoe. Prodolzit? Press 1 (YES) or 0 (NO) 0isxodnoe prostoe: 31=1861-prostoe. Prodolzit? Press 1 (YES) or 0 (NO) 0chisla: p=353 q=1861

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

e: 999(999, fi_М)=3e: 997(997, fi_М)=1kluch sustemu: (e, m)=(997, 656933)povidomlennya: 599639shifrovane povidomlennya: 599639klucha…virniy.: 111111vuhody natusnit Enter…

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

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

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

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

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

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

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

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

Больше работ по теме: