Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
НЕСИМЕТРИЧНИЙ АЛГОРИТМ ШИФРУВАННЯ RSA.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра Телекомунікацій
Інформація про роботу
Рік:
2001
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Захист інформації в телекомунікаційних системах
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
Кафедра “Телекомунікації”
НЕСИМЕТРИЧНИЙ АЛГОРИТМ ШИФРУВАННЯ RSA
Методичні вказівки до циклу лабораторних робіт № 8, 9 та 10
з курсу «Захист інформації в телекомунікаційних системах»
для студентів спеціальності «Інформаційні мережі зв'язку»
Львів 2001
“Несиметричний алгоритм шифрування RSA”. Методичні вказівки до циклу лабораторних робіт № 8, 9 та 10 з курсу “Захист інформації в телекомунікаційних системах” для студентів спеціальності 7.092402 - “Інформаційні мережі зв'язку”. - Львів 2001. – 15 с.
Автори: доцент Коваль Б.В.
доцент Ящишин Є.М.
Рецензенти: доцент, д.т.н. Тимченко О.В.
доцент, к.т.н. Оборжицький В.І.
У цикл лабораторних робіт “Несиметричний алгоритм шифрування RSA” увійшли 3 роботи:
№ 8. Дослідження алгоритму генерації ключів для шифру RSA.
№ 9. Дослідження алгоритму шифрування RSA.
№10.Дослідження шифрування різнотипної інформації симетричними і несиметричними алгоритмами.
Методичні вказівки затверджено на засіданні кафедри “Телекомунікації” Національного університету “Львівська політехніка” 04.04.2001 р., протокол № 8.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Запропонована 1977 року система RSA є чи не найпопулярнішою криптосистемою з відкритим ключем. Назва системи утворена з перших літер імен її винахідників - Рональда Райвеста, Аді Шаміра та Леонарда Адллемана.
Історія розвитку RSA.
До початку 70-тих років дослідження в області криптографії проводились виключно в військових цілях і жодні публікації про досягнення в цій галузі науки не публікувались.
На той час в США існувала NSA яка в певній мірі систематизувала розробки для військових цілей і не існувало жодних координуючих організацій в області криптографії вмілому.
В кількох країнах існували кілька невеликих підприємств, які власноруч створювали криптосистеми для захисту інформації. Але існувала велика проблема, а саме - ці криптосистеми порозумітись між собою не могли - різноманітні алгоритми і формати представлення даних. Крім того, не існувало ніякого аналізу якості криптосистем, і жодна людина не могла сказати з якоюсь впевненістю, що саме ця криптосистема краща за іншу, і тим більше ніхто не міг показати, чим же ж вона краща.
В 1972 NBS (зараз NIST) розпочало програму, ціллю якої було забезпечення безпеки комп’ютерних даних, що пересилаються. Як частина цієї програми, було запропоновано опрацювати єдиний, стандартизований криптографічний алгоритм для забезпечення секретності передачі цифрових даних і секретності їх зберігання. Такий єдиний алгоритм можна було б протестувати і сертифікувати його безпечність і надійність. Крім того, за його допомогою могли б створюватись різноманітні криптографічні системи. Результат роботи повинен був бути якомога дешевшим в плані впровадження і легким для розуміння.
15 травня 1977 року NBS оприлюднив в Federal Register вимоги, що виставлялись до проектів стандартизованого криптографічного алгоритму. Критерії проекту були наступними:
Алгоритм повинен забезпечувати високу ступінь безпеки.
Алгоритм повинен бути повністю описаний і легко зрозумілий.
Безпека алгоритму повинна базуватись на безпеці ключа і не повинна залежати від безпеки самого алгоритму.
Алгоритм повинен бути доступним для всіх користувачів.
Алгоритм повинен мати можливість адаптації, що робило б його доступним для реалізації в інших комп’ютерних системах.
Алгоритм повинен давати можливість економічної, електронної реалізації.
Алгоритм повинен бути ефективним у вжитку.
Алгоритм повинен давати можливість переконатись
в правильності роботи.
Алгоритм повинен відповідати умовам експорту.
Кількість запропонованих проектів свідчила про велику зацікавленість у появі єдиного стандарту, але через практичну відсутність досвіду в створенні криптографічних алгоритмів жодна з надісланих пропозицій не була навіть близькою до поставлених вимог.
NBS прийшлось ще раз оголошувати конкурс в Federal Regіster 27 серпня 1974 року. В кінці кінців було отримано кандидата, який вмілому відповідав поставленим вимогам - він базувався на опрацьованому на IBM на початку 70-тих років алгоритмі під назвою Lucifer. Цей алгоритм використовував тільки прості операції над малими групами бітів і міг бути дуже ефективно реалізований як апаратна, так і програмно.
NBS попросив NSA про допомогу в визначенні ступеня безпечності алгоритму і визначення ймовірності його використання як федерального стандарту. В той же час IBM запатентувала цей алгоритм, але була згідна надавати цю свою інтелектуальну власність з ціллю продукування, реалізації і використання.
NBS і NSA виробили спільні умови і отримали остаточну ліцензію, що була вільна від сплати за авторські права на виробництво і продажу апаратури, в якій буде застосовуватись алгоритм.
В результаті, 17 березня 1975 року, NBS надрукувала в федеральному реєстрі опис алгоритму. В іншому повідомленні від 1 серпня 1975 року було запрошено всіх зацікавлених осіб надсилати свої коментарі щодо алгоритму.
В 1976 році NBS організувало дві наукові конференції для оцінки запропонованого стандарту. В рамках першої конференції алгоритм обговорювався з математичної точки зору і можливості існування в ньому западні, використання якої могло б звести нанівець зусилля алгоритму по наданню даним конфіденційності. Під час другої конференції розглядались питання можливої зміни довжини ключа алгоритму і вплив довжини ключа на надійність алгоритму. На обидві конференції були запрошені автори алгоритму, експерти, виробники, продавці, споживачі і критики.
Опис алгоритму.
Алгоритм складається з трьох етапів :
Генерація ключів.
Шифрування.
Дешифрування.
Процес створення пари ключів.
Вибирають два досить великі прості числа p і q . Для їх добутку n=p*q значення функції Ойлера дорівнює
(n)=(p-1)*(q-1)=n-p-q+1. (4.1)
Далі випадковим чином вибирають елемент e, що не перевищує значення (n) і взаємно простий з ним.
Іншими словами e є випадковим елементом із множини Z*(n). Для е за алгоритмом Евкліда знаходимо елемент d, обернений до е в Z*(n), тобто такий, що
d<(n) і ed1(mod(n)). (4.2)
EMBED Word.Picture.6
Рис.1. Блок схема алгоритму генерації ключів.
Як результат покладають :
Відкритий ключ : e,n.
Таємний ключ : d,n.
Блок схему генерації ключів показано на рис. 3.
Як видно з рисунка в даному алгоритмі використовується наступні під алгоритми :
знаходження простих чисел див. Рисунку 4.2.
знаходження найменшого спільного дільника (NDS) дивися рисунок 4.3.
знаходження числа D за алгоритмом Евкліда (MOD) дивися рисунок 4.4.
Шифрування
Шифрування відбувається блоками. Для цього повідомлення записують у цифровій формі і розбивають на блоки так, що кожен блок позначає число, яке не перевищує n.
Скажімо, якщо блок записаний у вигляді війкового слова довжини m, то повинна виконуватись нерівність 2m<n. Блок M розглядається як елемент кільця Zn і як такий може підноситись до степеня за модулем n.
Алгоритм шифрування E у системі RSA полягає у піднесенні M до степеня e, дивися рисунок 4.5. Записуємо це так
E(M)=Memod(n). (4.3)
В результаті отримується блок криптотексту C=E(M), який також є цифровим записом якогось елемента кільця Zn.
DX(EX(M))= EX(DX(M))=M. (4.4)
EMBED Word.Picture.6
Рис. 2. Блок схема алгоритму знаходження простих чисел.
Аутентифікація повідомлення.
В алгоритмі шифрування RSA кожен абонент X має пару ключів - загальновідомий відкритий (nX,eX) і таємний dX, який знає лише X і ніхто інший. Таким чином, будь хто може скористатись алгоритмом шифрування EX абонента X, але тільки він сам володіє алгоритмом дешифрування DX. Важливим є виконання таких співвідношень для довільного повідомлення M. Ці співвідношення зводяться до рівностей :
(MeX)dX=(MdX)eX=M в ZnX (4.5)
І виражають той факт, що шифруюче відображення EX та дешифруюче DX є взаємно оберненими.
Припустимо, що абонент А хоче переслати повідомлення M абонентові Б таким чином, щоб той був певен, що повідомлення справді послане абонентом А, а не опонентом. Для цього пропонується такий протокол, в якому (Ea,Da) та (Eb,Db) - алгоритми шифрування да дешифрування абонентів А та Б.
Абонент А обчислює C=Eb(Da(M)) і посилає C абоненту Б
Абонент Б отримавши C, обчислює M=Ea(Db(C)).
Коректність протоколу зводиться до рівності :
EA(DB(EB(DA(M))))=M, (4.6)
яка випливає із співвідношення (4.5).
EMBED Word.Picture.6
Рис. 3. Блок схема алгоритму знаходження найменшого спільного дільника (NDS).
EMBED Word.Picture.6
Рис. 4. Блок схема алгоритму знаходження числа D за алгоритмом Евкліда (MOD).
Ефективність. Абоненти А та Б використовують ефективні алгоритми шифрування та дешифрування криптосистеми RSA. Зауважимо, що абонент А використовує свій приватний алгоритм Da та відомий всім алгоритм Eb. Те ж саме із абонентом Б - він використовує особистий алгоритм Db і загальновідомий алгоритм Ea.
EMBED Word.Picture.6
Рис. 5. Блок схема алгоритму шифрування та дешифрування.
Конфіденційність. Під конфіденційністю цього протоколу ми розуміємо його надійність як звичайної криптосистеми для пересилання повідомлень. В такому розумінні конфіденційність є досить інтуїтивним фактом, що грунтується на надійності алгоритму RSA.
Перед опонентом, який перехопив криптотекст C, виникає завдання визначити M із Eb(Da(M)). Припустимо, що опонент знає навіть набагато більше, а саме приватний алгоритм Da абонента А. Тоді визначення M для опонента рівносильне визначенню Da(M). Але визначення Da(M) із Eb(Da(M)) є нічим іншим, як задачею зламу RSA.
Розподіл ключів.
Традиційна симетрична система захисту конфіденційності інформації та листування грунтується на наявності надійного каналу для обміну таємними ключами. Цей канал може бути набагато повільнішим, ніж канал для обміну повідомленнями, але безумовно він повинен бути захищеним від посягань суперника(опонента). У типовому класичному випадку такий канал реалізується з допомогою кур'єра, який доставляє ключ від одного користувача до іншого. В асиметричних криптосистемах проблеми пересилання ключа не існує, адже таємний ключ є особистою власністю кожного абонента мережі, а відкритий ключ перебуває у відкритому доступі. Зазначимо однак, що з появою асиметричних криптосистем симетричні системи не вийшли зі вжитку з тої причини, що останні є набагато швидшими. Фактор же швидкості криптування/декріптування стає визначальним при пересиланні великих обсягів інформації. Проте асиметричні криптосистеми відкривають нові можливості для обміну ключами при використанні симетричних криптосистем. Наприклад, практичним є пересилання ключа тим же каналом зв'язку, що і звичайних повідомлень, але зашифрованого за допомогою асиметричної криптосистеми. И хоча швидкодія криптосистеми з відкритим ключем нижча, для цієї мети вона достатня, адже ключ має невеликі розміри та буде пересилатися значно рідше, ніж звичайні повідомлення.
Характеристики безпеки RSA.
Будь-яку асиметричну криптосистему можна зламати, вказавши ефективний спосіб визначення таємного ключа за відкритим. У нашому випадку це означає, розкриття RSA зводиться до задачі :
Знаходження таємного ключа для RSA
Задано : e, n, де n = p*q і НСД(e,(n))=1
Знайти : d таке, що xed x(mod n) для всх x.
З алгоритму генерування ключів безпосередньо випливає, що остання задача зводиться до обчислення значення функції Ойлера (n). Як легко пересвідчитись, обчислення функції Ойлера від аргументів такого типу є задачею еквівалентною до знаходження співмножників p і q числа n. Отже, спроба факторизувати модуль n=p*q є найочевиднішим шляхом до розкриття RSA. На даний час це є безнадійна справа для n порядку 10200. Тому при генеруванні ключа, p і q рекомендується вибирати із приблизно сотнею десяткових цифр кожне. Вибір таких чисел повинен бути справді випадковим, щоб уникнути можливої факторизації якимось із вузько-спеціальних методів.
Порівняльна статистичних характеристик алгоритмів RSA та IDEA.
Порівняння характеристик алгоритмів здійснюється на основі порівняння статистичних параметрів певного вибраного тестового файлу. Для наглядності обираємо графічний файл розміром 100 на 100 пікселів. Статистичні параметри файла до шифрування :
Розмір файла 8922 байт;
Алфавіт файла 249;
Ентропія 7.38945;
EMBED Word.Picture.6
На рисунку 4.6. представлено вхідний графічний файл. Параметри шифрування алгоритму RSA :
Просте число D:275
Просте число E:347
Просте число N:493
Рис.4.6. Тестовий графічний файл.
Після шифрування алгоритмом RSA отримано наступні статистичні параметри:
Розмір файла 11078 байт;
Алфавіт файла 256 символів;
Ентропія 7.64228;
EMBED Word.Picture.6
На рисунку 4.7. представлено графічний файл після шифрування алгоритмом RSA.
Рис. 4.7. Тестовий графічний файл зашифрований алгоритмом RSA.
Після шифрування алгоритмом IDEA отримано наступні статистичні параметри:
Розмір файла 11078 байт;
Алфавіт файла 256 символів;
Ентропія 7.64228;
EMBED PBrush
На рисунку 4.8. представлено графічний файл після шифрування алгоритмом IDEA.
Рис. 4.8. Тестовий графічний файл зашифрований алгоритмом IDEA.
Як видно з приведених результатів шифрування криптографічний алгоритм RSA поступається перед типовим представником симетричних алгоритмів таким як IDEA.
Лабораторний практикум
Лабораторна робота № 8
Дослідження алгоритму генерації ключів для шифру RSA
Мета роботи
Дослідити принципи формування пари ключів в алгоритмі RSA.
Хід роботи
Ознайомитись з теоретичними відомостями.
Запустити програму PGP_DPL.exe та ознайомитись з оболонкою.
Зайти в лабораторну роботу №2.
Дати відповідь на контрольні запитання.
Встановити максимальну границю для генерації чисел.
Встановити систему числення.
Пройти процес генерації ключів покроково за допомогою кнопки "Далі".
Отримані результати записати у звіт.
Зробити висновки, і дати відповідь на контрольні запитання.
Контрольні запитання.
Що називається простим числом ?
Що означає що числа є взаємо простими ?
Опишіть суть алгоритму Евкліда ?
Який етап в генерації ключів є найбільш тривалим і чому?
Як пов’язані між собою числа E і D що використовуються в таємному та явному ключах ?
Лабораторна робота № 9
Дослідження алгоритму шифрування RSA
Мета роботи
Зрозуміти роботу алгоритму шифрування та дешифрування в RSA.
Хід роботи.
Ознайомитись з теоретичними відомостями.
Запустити програму PGP_DPL.exe та ознайомитись з оболонкою.
Зайти в лабораторну роботу №4.
Дати відповідь на контрольні запитання.
Встановити максимальну границю для генерації чисел.
Встановити систему числення.
Пройти процес генерації ключів покроково за допомогою кнопки "Далі".
Отримані результати записати у звіт.
Зробити висновки, і дати відповідь на контрольні запитання.
Контрольні запитання.
За рахунок чого забезпечується односторонність алгоритму при шифруванні та аутентифікації ?
Чому він відноситься до несиметричних алгоритмів ?
Чим відрізняється процес шифрування від процесу дешифрування ?
Чи відрізняється швидкість обробки при шифруванні та дешифруванні і якщо так то чому ?
Лабораторна робота № 10
Дослідження шифрування різнотипної інформації
симетричними і несиметричними алгоритмами
Мета роботи
Порівняти шифрування текстових та графічних файлів зашифрованих IDEA, DES з RSA.
Хід роботи.
Ознайомитись з теоретичними відомостями.
Запустити програму PGP_DPL.exe та ознайомитись з оболонкою.
Зайти в лабораторну роботу №5.
Дати відповідь на контрольні запитання.
Вибрати будь-який текстовий файл.
Зашифрувати файл. Проглянути як змінилися: розподіл символів у файлі, ентропія та алфавіт файла.
Зашифрувати цей же файл алгоритмом DES і IDEA, переглянути результати і зробити порівняння файлів.
Перейти до шифрування графічних файлів за допомогою алгоритму RSA.
Зашифрувати початковий файл алгоритмом DES,IDEA.
Отримані результати порівняти.
Знайти в розділі допомоги формулу, якій рахується ентропія.
Контрольні запитання.
Що таке ентропія, від чого вона залежить ?
Що таке алфавіт джерела ?
За якою формулою рахується ентропія ?
При шифруванні файлу довжина змінюється і якщо так то чому ?
Література
Вербіцький О.В. Вступ до криптології. - Видавництво наук.-техн. літератури. - Львів, 1998.
Столлингс Вильям. Криптография и защита сетей: принципы и практика, 2-е изд.: Пер. с англ. – М. : Издательский дом “Вильямс”, 2001. – 672 с.
Домарев В.В. Защита информации и безопасность компьютерных систем. – К. Издательство «Диасофт», 1999. – 480 с.
Підписано до друку 14.05.2001. Папір офсетний. Друк офсетний.
Умов.-друк. арк. 0.93. Формат 60х84 1/16. Наклад 100 прим. Зам. 1022.
Віддруковано в НВМ Поліграфічного технікуму УАД
79008, м. Львів, пл. Митна, 1
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора