Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ШИФРУВАННЯ ТА РОЗШИФРУВАННЯ ІНФОРМАЦІЇ ЗА ДОПОМОГОЮ АЛГОРИТМУ RSA
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Криптографічні системи та протоколи
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ШИФРУВАННЯ ТА РОЗШИФРУВАННЯ ІНФОРМАЦІЇ ЗА ДОПОМОГОЮ АЛГОРИТМУ RSA.
МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 5
З ДИСЦИПЛІНИ “КРИПТОГРАФІЧНІ СИСТЕМИ ТА ПРОТОКОЛИ”
для студентів базового напряму
6.170101 “Безпека інформаційних і комунікаційних систем”
Затверджено на засiданнi кафедри
“Безпека інформаційних технологій”,
протокол № від 2012 р.
Львів – 2012
Шифрування та розшифрування інформації за допомогою алгоритму RSA: Методичні вказівки до лабораторної роботи №5 з дисципліни “Криптографічні системи та протоколи” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем” /Укл.: А.Е.Лагун, А.В.Петришин - Львів: НУЛП 2012. - 11 с.
Укладачі:
А.Е.Лагун, к.т.н., доцент
А.В.Петришин, асистент
Відповідальний за випуск:
Л.В. Мороз, к.т.н., доцент.
Рецензент:
В.М.Максимович, д.т.н., професор.
Мета роботи – вивчити математичні основи побудови алгоритму шифрування RSA, методи криптоаналізу та вимоги до стійкості алгоритму RSA, навчитися розробляти програмне забезпечення для шифрування та цифрового підпису з використанням алгоритму RSA.
1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Безпека RSA базується на складності розкладу на множники великих чисел. Відкритий та закритий ключі є функціями двох великих (більше двохсот десяткових розрядів) простих чисел. Відновлення відкритого тексту за шифротекстом і відкритим ключем еквівалентне розкладу на множники двох великих чисел.
Для генерації двох ключів використовуються два великих випадкових простих числа p і q однакової довжини. Розширений алгоритм Евкліда використовується для обчислення ключа розшифрування d такого, що
ed=1(mod(p-1)(q-1)). (1)
Іншими словами
d=e-1mod((p-1)(q-1)) (2)
d і n=pq є взаємно простими числами. Числа e і n – це відкритий ключ, а число d – закритий. Для шифрування повідомлення m воно спочатку розбивається на цифрові блоки, які менші за n (для двійкових даних вибирається найбільший степінь числа 2, менший за n). А саме, якщо p і q – 100-розрядні прості числа, то n буде мати приблизно 200 розрядів і кожен блок повідомлення mi повинен мати також приблизно 200 розрядів. Зашифроване повідомлення c буде складатися з блоків ci такої ж довжини. Формула шифрування має вигляд:
ci=mie mod n (3)
Для розшифрування повідомлення береться кожен зашифрований блок ci і обчислюється
mi=cid mod n (4)
Оскільки
cid=(mie)d=mied=mik(p-1)(q-1)+1=mimik(p-1)(q-1)=mi*1=mi
то формула відновлює повідомлення.
Для піднесення до степеня за модулем n використовується бінарний алгоритм:
Задано: .
Обчислити: .
Вважається, що d < n. Алгоритм у вигляді прямолінійної програми для обчислення функції має вигляд.
Показник подається у двійковій системі числення: , де і . Присвоюється . Тоді -та команда задається так:
Всього команд . Результатом виконання останньої є
Всього витрачається множень.
Нехай p=47, q=71. Тоді
N=pq=3337.
Ключ e не повинен мати спільних множників
(p-1)(q-1)=46*70=3220
Вибираємо випадково e, наприклад, 79. Тоді d=79-1mod 3220=1019.
Під час обчислення використаний розширений алгоритм Евкліда. Зробимо e і n загальнодоступними, а d збережемо в секреті. Відкидаємо p і q. Для шифрування повідомлення m=6882326879666683 спочатку розбиваємо його на малі блоки. Для розглянутого випадку використовуємо трибуквенні блоки. Повідомлення розіб’ється на шість блоків mi.
m1=688
m2=232
m3=687
m4=966
m5=668
m6=003
Перший блок шифрується 68879 mod 3337=1570=c1.
Виконуючи такі самі операції для наступних бітів, одержимо шифротекст повідомлення:
c=1570 2756 2091 2276 2423 158
Для розшифрування потрібно виконати операцію піднесення до степеня, використовуючи ключ розшифрування 1019:
15701019 mod 3337 =688 =m1
Аналогічно відновлюється інша частина повідомлення.
Швидкодія RSA.
Апаратно RSA приблизно в 1000 разів повільніший за алгоритм симетричного шифрування DES. Програмно DES приблизно в 100 разів швидший, ніж RSA.
Безпека RSA.
Безпека RSA залежить від проблеми розкладу на множники великих чисел. Також можна зламати RSA, вгадавши значення (p-1)(q-1). Найбільш ймовірним засобом зламування RSA алгоритму є розклад n на множники. Будь-який супротивник зможе одержати відкритий ключ e і модуль n. Щоб знайти ключ розшифрування d супротивник повинен розкласти n на множники. На цей час, завдяки розвитку сучасних технологій, можливий розклад числа, що містить 130 десяткових цифр. Тому n мусить бути більшим за таке значення.
Також для зламу можна перебирати всі можливі d, доки не знайдеться потрібне значення. Проте таке розкриття грубою силою менш ефективна, ніж спроба розкладу n на множники.
Розкриття з вибраним шифротекстом проти RSA.
Деякі розкриття працюють проти реалізацій RSA. Вони розкривають не сам базовий алгоритм, а надбудований над ним протокол. Саме використання RSA не забезпечує безпеку. Можливі випадки.
Сценарій 1.
Зловмисник, який прослуховує лінію зв’язку, перехопив повідомлення c, яке зашифроване за допомогою RSA відкритим ключем і хоче прочитати повідомлення. Потрібно знайти m, для якого
m=cd.
Для розкриття m спочатку вибирають перше випадкове число r, яке менше за n. За допомогою відкритого ключа e обчислюють
x=re mod n
y=xc mod n
t=r-1 mod n.
Якщо x=re mod n, то r=xd mod n.
Далі зловмисник вимагає відправника підписати y закритим ключем, таким чином розшифрувавши y. Відправник посилає
u=yd mod n
Тоді зловмисник обчислює
tu mod n = r-1yd mod n= r-1xd cd mod n= cd mod n=m
і одержує повідомлення m.
Сценарій 2.
Нехай існує комп’ютер-нотаріус. Якщо адресат хоче завірити документ, то відправляє його нотаріусу, який підписує його цифровим підписом RSA і відправляє назад (нотаріус не використовує однонаправлені хеш-функції, а шифрує все повідомлення своїм закритим ключем).
Адресат хоче, щоб нотаріус підписав таке повідомлення, яке звичайно він ніколи не підпише, наприклад якась фальшива часова мітка. Позначимо це повідомлення m’.
Спочатку адресат вибирає довільне значення x і обчислює y=xe mod n. e він одержує як відкритий ключ нотаріуса, який повинен бути опублікований для перевірки підпису нотаріуса. Тепер адресат обчислює m=ym’ mod n і посилає нотаріусу для підпису. Нотаріус повертає md mod n. Потім адресат обчислює (md mod n)x-1 mod n, яке дорівнює nd mod n і є підписом m’.
Сценарій 3.
Адресат1 хоче щоб Адресат 2 підписав m3 і створює два повідомлення m1 і m2 такі, що
m3=m1m2(mod n)
Якщо Адресат 1 зможе заставити Адресата 2 підписати m1 і m2, то зможе обчислити підпис для m3:
m3d=(m1d mod n)(m2d mod n)
З наведених сценаріїв можна зробити висновок, що не можна користуватися алгоритмом RSA для підпису випадкових документів. Необхідно спочатку використати однонаправлену хеш-функцію.
Розкриття спільного модуля RSA.
Під час реалізації RSA можна спробувати роздати всім користувачам однаковий модуль n, проте різні значення степеня e і d. Найбільша проблема в тому, що якщо одне повідомлення колись шифрувалося різними показниками степеня і ці два показники взаємно прості числа, то відкритий текст можна розкрити без жодного ключа розшифрування.
Нехай m – відкритий текст повідомлення, e1 і e2 – два ключі шифрування, n – спільний модуль. Шифротекстами повідомлення є
c1=me1 mod n
c2=me2 mod n
Криптоаналітик знає n, e1, e2, c1, c2.
Оскільки e1 і e2 взаємно прості числа, то з розширеного алгоритму Евкліда існують r і s, для яких
re1+se2=1
Вважаючи r від’ємним, можна використати розширений алгоритм Евкліда для обчислення с1-1. Тоді
(c1-1)-r *c2s=m mod n
Таким чином, не можна робити один спільний модуль для групи користувачів.
Розкриття малого показника шифрування RSA.
Інше розкриття запропоноване Майклом Вінером і розкриває d, якщо d не перевищує четвертої частини розміру модуля n, а e менше за n. Під час випадкового вибору e і d це зустрічається рідко і ніколи не станеться, якщо значення e мале, тому потрібно вибирати велике значення показника степеня d.
З проведеного аналізу можна сформулювати такі вимоги до стійкості алгоритму RSA:
1) знання однієї пари показників шифрування-розшифрування для даного модуля дозволяє зламуючому розкласти модуль на множники.
2) знання однієї пари показників шифрування-розшифрування для даного модуля дозволяє зламуючому обчислити інші пари показників, не розкладаючи модуль на множники.
3) в протоколах мереж зв’язку, що використовують RSA, не повинен використовуватися спільний модуль.
4) для запобігання розкриттю малого показника шифрування повідомлення мають бути доповнені випадковими значеннями.
5) показник розшифрування повинен бути великим.
2. ЗАВДАННЯ
2.1. Домашня підготовка до роботи
1) Вивчити математичні основи, принципи побудови та вразливості алгоритму шифрування RSA.
2) Скласти блок-схеми алгоритмів та програму для реалізації шифрування та розшифрування відкритого тексту за допомогою алгоритму шифрування RSA. Забезпечити введення ключів з клавіатури. Для виконання операції піднесення до степеня за модулем використати бінарний алгоритм.
2.2. Робота в лабораторії
1) Ввести в комп'ютер програми згідно із завданням.
2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками.
3) Остаточні версії блок-схем, програм та отримані результати оформити у звіті з лабораторної роботи.
4) Здати звіт з лабораторної роботи.
3. ЗМІСТ ЗВІТУ
1) Номер і назва лабораторної роботи.
2) Повний текст завдання.
3) Остаточні версії блок-схем алгоритмів.
4) Список ідентифікаторів констант, змінних, процедур і функцій, використаних у блок-схемах алгоритмів і програм, та їх пояснення.
5) Остаточні версії програм.
6) Результати роботи програм.
4. КОНТРОЛЬНІ ЗАПИТАННЯ
1. На якій проблемі ґрунтується безпека алгоритму RSA?
2. Що є відкритим і закритим ключем в алгоритмі шифрування RSA?
3. Поясніть суть бінарного алгоритму піднесення до степеня.
4. Які існують способи зламування алгоритму RSA?
5. Наведіть можливі сценарії розкриття з вибраним шифротекстом алгоритму RSA.
6. Як відбувається розкриття спільного модуля RSA?
7. Cформулюйте вимоги до стійкості алгоритму RSA.
СПИСОК ЛІТЕРАТУРИ
О.Н.Василенко, Теоретико-числовые алгоритмы в криптографии. – М.: Изд-во МГУ, 2000
К.Шеннон. Теория связи в секретных системах. В Работы по теории информации и кибернетике, стр. 333-402. М., Изд. Иностр. Лит., 1963.
М.Вельшенбах. Криптография на Си и С++ в действии. М., Триумф, 2004.
Б.Шнайер. Прикладная криптография, 2-е издание: протоколы, алгоритмы, исходные тексты на языке Си. М., Триумф, 2002.
Навчальне видання
Шифрування та розшифрування інформації за допомогою алгоритму RSA: Методичні вказівки до лабораторної роботи №5 з дисципліни “Криптографічні системи та протоколи” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем”.
Укладачі:
Лагун Андрій Едуардович
Петришин Андрій Васильович
19.01.2013 21:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора