Сучасні асиметричні криптосистеми. Концепція криптосистеми з відкритим ключем. Односпрямовані функції. Криптосистема шифрування даних RSA. Процедури шифрування і розшифрування в криптосистемі RSA. Безпека і швидкодія криптосистеми RSA. Криптоаналіз

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

Міністерство науки і освіти України

Криворізький національний університет

Кафедра автоматики, комп'ютерних наук і технологій

РОЗРАХУНКОВА РОБОТА

з дисципліни «Захист інформації в автоматизованих системах»

на тему:Сучасні асиметричні криптосистеми. Концепція криптосистеми з

відкритим ключем. Односпрямовані функції. Криптосистема шифрування даних RSA. Процедури шифрування і розшифрування в криптосистемі RSA. Безпека і швидкодія криптосистеми RSA. Криптоаналіз.

Виконав

Студентгрупи АКІТ-17

Виноградов М.Г.

підпис

Керівник

доцент, к.т.н. кафедри АКНТ

Тиханський М.П.

підпис

Кривий Ріг

2020



ЗМІСТ

ВСТУП

1. ТЕОРЕТИЧНА ЧАСТИНА

1.1 Сучасні асиметричні криптосистеми

1.2 Односпрямовані функції

1.3 Криптосистема шифрування даних RSA

1.4 Безпека і швидкодія криптосистеми RSA

1.6 Криптоаналіз

ВИСНОВКИ

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ



ВСТУП

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

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

Термін був введений американським криптографом Вільямом Ф. Фрідманом в 1920 році.

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

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

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



1. ТЕОРЕТИЧНА ЧАСТИНА

1.1 Сучасні асиметричні криптосистеми

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

Узагальнена схема асиметричної криптосистеми з відкритим ключем наведена на рис. 1.1. В цій криптосистемі застосовують два різних ключі: КВ - відкритий ключ відправника А; kB - секретний ключ отримувача В. Генератор ключів доцільно розміщувати на стороні отримувача В (щоб не пересилати секретний ключ kB по незахищеному каналу).

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

Рис. 1.1 - Узагальнена схема асиметричної криптосистеми з відкритим ключем

Значення ключів КВ та kB залежать від початкового стану генератора ключів. Розкриття секретного ключа kB за відомим відкритим ключем КВ повинно бути задачею, яку неможливо розв'язати розрахунковими методами.

Наведемо характерні особливості асиметричних криптосистем:

Відкритий ключ КВ та криптограма С можуть бути відправлені по незахищеним каналам (супротивнику відомі КВ та С).

Алгоритми шифрування та розшифровування

EB:M>C,

DB:C>M

є відкритими.

Захист інформації в асиметричній криптосистемі базується на секретності ключа kB. У. Діффі та М. Хелман сформулювали вимоги, виконання яких забезпечує безпеку асиметричної криптосистеми :

Генерація пари ключів (КВ, kB) отримувачем В на основі початкової умови повинна бути простою.

Відправник А, знаючи відкритий ключ КВ та повідомлення М, може легко генерувати криптограму

.

Отримувач В, використовуючи секретний ключ kB та криптограму С, може легко відновити вихідне повідомлення

.

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

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

1.2 Односпрямовані функції

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

f:X>Y

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

y=f(x), де yY.

І в той же час для більшості yY досить складно отримати значення xX, таке, що f(x)=y (при цьому вважають, що існує по крайній мірі одне таке значення х). Основним критерієм віднесення функції fдо класу однона правлених функцій є відсутність ефективних алгоритмів оберенного перетворення Y>X.

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

N=P*Q,

є відносно нескладною задачею для ЕОМ.

Обернена задача - факторизація великого цілого числа (знаходження дільників P та Q великого цілого числа N=P*Q), є задачею, яку практично неможливо розв'язати засобами сучасних ЕОМ при достатньо великих значеннях N. За сучасними оцінками теорії чисел при цілому N?2664 та P?Q для факторизації числа N знадобиться біля 1023 операцій.

Іншим характерним прикладом однонаправленої функції є модульна експонента з фіксованими основою та модулем. Нехай A та N - цілі числа, такі, що 1?A?N. Визначимо множину ZN:

ZN={0,1,2,...,N-1}.

Тоді модульна експонента з основою А по модулю N являє собою функцію

fA,N:ZN>ZN,

fA,N(x)=Ax(modN),

де Х - ціле число, 1?x?N-1.

Існують ефективні алгоритми, які дозволяють досить швидко розрахувати значення функції fA,N(x). Якщо y=Ax, то природно записати x=logA(y). Тому задачу знаходження функції оберненої до функції fA,N(x) називають задачею знаходження дискретного алгоритму чи задачею дискретного логарифмування. Задача дискретного логарифмування формулюється наступним чином. Для відомих цілих A, N, yзнайти ціле число x, таке, що

AxmodN=y.

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

За сучасними оцінками теорії чисел при цілих числах A2664 та N2664 розв'язання задачі дискретного логарифмування (знаходження показника степеня x для відомого y) потребує біля 1026 операцій - задача має в 1000 раз більшу обчислювальну складність, ніж задача розкладання на множники . При збільшенні довжини чисел різниця в оцінках складності задач зростає. Слід зазначити, що поки не вдалося довести, що не існує ефективного алгоритму обчислення дискретного логарифму за прийнятний час. У зв'язку з цим, модульна експонента віднесена до однонаправлених функцій умовно, що, проте, не заважає з успіхом застосовувати її на практиці.

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

f:X>Y

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

1.3 Криптосистема шифрування даних RSA

Алгоритм RSA було запропоновано в 1978 році трьома авторами: Р. Райвестом (Rivest), А. Шаміром (Shamir) та А. Алдеманом (Aldeman) . Алгоритм названо за першими буквами прізвищ його авторів. Алгоритм RSAстав першим повноцінним алгоритмом з відкритим ключем, який може працювати як у режимі шифрування даних, так і в режимі електронного цифрового підпису.

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

ZN={0,1,2,...,N-1},

де N - модуль:

N=P*Q

Тут P і Q - випадкові великі прості числа. Для забезпечення максимальної безпеки Pі Q вибирають однакової довжини і зберігають в секреті. Множина ZN з операціями додавання та множення по модулю N утворює арифметику по модулю N.

Відкритий ключ KB вибирають відкритим чином так, щоб виконувалися умови:

1<KB(N), НСД(KB,(N))=1,

(N)=(P-1)(Q-1)

криптосистема функція алгоритм ейлер

де (N) - функція Ейлера.

Функція Ейлера вказує кількість додатніх цілих чисел в інтервалі від 1 до N, які є взаємно простими з N. Друга із вказаних вище умов означає, що відкритий ключ KB та функція Ейлера (N) повинні бути взаємно простими (їх найбільший спільний дільник (НСД) повинен бути рівним 1). Далі, використовуючи розширений алгоритм Евкліда, розраховують секретний ключ kB, який задовольняє наступній умові:



kB*KB1(mod(N)),

або

kB=KB-1(mod(P-1)(Q-1)).

Цей ключ легко розрахувати, оскільки отримувач знає пару простих чисел (P,Q) і може легко розрахувати (N). Нагадаємо, що kB та N повинні бути взаємно простими.

Відкритий ключ KB використовують для шифрування даних, а секретний ключ kB - для розшифровування. Перетворення шифрування визначає криптограму С через пару (відкритий ключ KB, повідомлення М) відповідно до формули:

.

Знаходження функції, оберненої до (визначення значення М за відомими значеннями C, KBтаN), є практично нездійсненною задачею при N2512.

Проте обернену задачу - розшифровування криптограми С, - можна розв'язати, використовуючи пару - секретний ключ kB та криптограма С за формулою:

.

Таким чином, якщо криптограму



піднести до степеня kB, то в результаті відновлюється вихідний відкритий текст М, оскільки

Таким чином, отримувач, який створює криптосистему, захищає два параметри: 1) секретний ключ kB та 2) пару чисел (P,Q), добуток яких дає значення N. З іншої сторони, отримувач відкриває значення модуля N та відкритий ключ KB.

Противнику відомі тільки значення KB та N. Якщо б він зміг розкласти число N на множники P та Q, він зміг би обчислити значення функції Ейлера

(N)=(P-1)(Q-1)

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

1.4 Безпека і швидкодія криптосистеми RSA

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

Розкладання величини Nна прості множники Pта Q дозволяє обчислити функцію (N)=(P-1)(Q-1) та визначити секретне значення kB, використовуючи рівняння:

KB*kB1(mod(N)).

Іншим можливим способом криптоаналізу алгоритму RSA є безпосереднє обчислення чи підбір значення функції (N)=(P-1)(Q-1). Якщо визначено значення (N), то співмножники P та Q обчислюються досить просто, проте така задача не простіша за факторизацію модуля N.

Задача факторизації є складною задачею для великих значень модуля N. Спочатку автори алгоритму RSAпропонували для обчислення модуля Nвибирати прості числа P та Q випадковим чином по 50 десяткових розрядів кожне. Вважалося, що такі великі числа N досить складно розкласти на прості множники. Один із авторів алгоритму RSA, Р.Райвест вважав, що для розкладання на прості множники числа із майже 130 десяткових цифр, наведеного у їх публікації, знадобиться більше 40 квадрільйонів років машинного часу. Проте цей прогноз не виправдався у зв'язку з відносно швидким прогресом комп'ютерів та їх обчислювальної потужності, а також покращення алгоритмів факторизації.

Один із найшвидших алгоритмів факторизації, відомих в наш час, - алгоритм NFS (NumberFieldSieve) може виконати факторизацію великого числа N (з кількістю десяткових розрядів більше 120) за кількість кроків, яка оцінюється величиною

.

В 1994 році було факторизовано число із 129 десятковими знаками. Це вдалося здійснити математикам А.Ленстра та М.Манассі з використанням організації розподілених обчислень на 1600 комп'ютерах, об'єднаних в мережу, на протязі восьми місяців. На думку А.Ленстра та М.Манассі, їх робота компрометує криптосистеми RSAта створює велику загрозу їх подальшим застосуванням. Тепер розробники криптоалгоритмів з відкритим ключем на базі RSA змушені уникати використання чисел довжиною менше 200 десяткових розрядів (таке число було факторизовано в 2005 році). Останні публікації пропонують застосовувати для цього числа довжиною не менше 250-300 десяткових розрядів.

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

Таблиця 1.1 - Оцінки довжини ключів для асиметричних криптосистем, біт

Рік	Окремі користувачі	Корпорації	Державні організації
1995	768	1280	1536
2000	1024	1280	1536
2005	1280	1536	2048
2010	1280	1536	2048
2015	1536	2048	2048

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

1.5 Криптоаналіз

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

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

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

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

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

Криптоаналітична атака при наявності відомого відкритого тексту. Криптоаналітик має доступ не тільки до шифротекстів С1, С2, … Сі кількох повідомлень, а й до відкритих текстів М1, М2, … Мі цих повідомлень. Його робота полягає у знаходженні ключа К, що використовується при шифруванні цих повідомлень, чи алгоритму розшифровування DK будь-яких нових повідомлень, зашифрованих тим же самим ключем.

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

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

Криптоаналітична атака з використанням вибраного шифротексту. Криптоаналітик може вибрати для розшифровування різні шифротексти С1, С2, … Сі та має доступ до розшифрованих відкритих текстів М1, М2, … Мі. Наприклад, криптоаналітик отримав доступ до захищеного від несанкціонованого доступу блоку, який виконує автоматичне розшифровування. Завдання криптоаналітика полягає в знаходженні ключа. Цей тип криптоаналізу представляє особливий інтерес для розкриття алгоритмів з відкритим ключем.

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

Існують і інші, менш розповсюджені криптоаналітичні атаки.



ВИСНОВОК

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

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

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

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

В ході виконання розрахунково-графічної роботи було розглянуто та вивчено криптоаналіз.



СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. Щеглов А.Ю. Защита компьютерной информации от несанкционированного доступа. - СПб.: Наука и техника, 2004. - 384 с.

2. Соколов А.В., Степанюк О.М. Защита от компьютерного терроризма. Справочное пособие. - СПб.: БХВ-Петербург - Арлит, 2002. - 496 с.

3. Леонтьев В.П. Безопасность в сети Интернет. - М.: ОЛМА Медиа Групп, 2008. - 256 с.

4. Гульев И.А. Компьютерные вирусы, взгляд изнутри. - М.: ДМК, 1998. - 304 с.

5. Защита компьютерной информации/ Терехов А.В., Чернышов В.Н., Селезнев А.В., Рак И.П. - Тамбов: Изд-во ТГТУ, 2003. - 49 с.

6. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях/ Под ред. В.Ф.Шаньгина. - 2-е изд., перераб. И доп. - М.: Радио и связь, 2001. - 376 с.

7. Щербаков Л.Ю., Домашев А.В. Прикладная криптография. Использование и синтез криптографических интерфейсов. - М.: Русская редакция, 2003. - 416 с.

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

...