Реферат на тему:
RSA – алгоритмів кодування з відкритим ключем
Перший алгоритм кодування з відкритим ключем (Public Key Encryption, далі PKE) було запропоновано Вітфілдом Діффі та Мартіном Хелманом у Стендфордському університеті. Вони, а також незалежно від них Ральф Меркл, розробили основні його поняття у 1976 році. Перевага PKE полягає у відсутності потреби секретної передачи ключа.
PKE базується на нерозв’язності проблеми розкладу натурального числа на прості множники.
RSA схему шифрування було запропоновано у 1978 році та названо іменами трьох його винахідників: Роном Рівестом (Ron Rivest), Аді Шаміром (Adi Shamir) та Леонардом Адлеманом (Leonard Adleman). RSA належить до класу алгоритмів кодування з відкритим ключем.
У 80-х роках криптосистема переважно використовувалася для забезпечення секретності та достовірності цифрових даних. У сучасному світі RSA використовується в web – серверах та браузерах для зберігання таємності даних що передаються по мережі, .
Схема RSA базується на обчисленні виразів зі степенями. Відкритий текст шифрується блоками, довжина кожного із яких менша за деяке число n.
Алгоритм генерації ключа
A повинен згенерувати відкритий та секретний ключі:
1. Згенерувати два великих простих числа p та q приблизно однакової довжини;
2. Обчислити n = p * q, fi = (p – 1) * (q – 1);
3. Вибрати натуральне e, 1 < e < fi, взаємно просте з fi;
4. Використовуючи розширений алгоритм Евкліда, розв’язати рівняння
d * e 1 (mod fi).
Відкритий ключ: (n, e). Секретний ключ: d.
Схема шифрування RSA
B шифрує повідомлення m та надсилає A.
1. Шифрування. В робить наступні дії:
а) отримати відкритий ключ (n, e) від А;
б) представити повідомлення у вигляді натурального числа m з проміжку [1..n];
в) обчислити c = me mod n;
г) надіслати шифротекст cдо А.
2. Дешифрування. Для отримання повідомлення m із шифротксту c А робить наступні дії:
а) використовуючи секретний ключ d, обчислити m = cd mod n.
Теорема. Шифр c декодується правильно.
Оскільки p та q – прості числа, то (p * q) = (n) = (p - 1) * (q - 1), де – функція Ейлера. З умови вибору ключа d маємо: d * e mod (n) = 1, або d * e = (n) * k + 1 для деякого натурального k.
cd mod n = (me)d mod n = m (e * d) mod n = m ^ ( (n) * k + 1) mod n = (m (n) mod n) k * m = 1 k * m = m, оскільки за теоремою Ейлера m (n) mod n = 1.
Означення. RSAсистемою називають функцію RSAn,e(x) = xe mod n та обернену їй RSA-1n,e(y) = yd mod n, де e – кодуюча, а d – декодуюча експонента, x, y Zn*.
Приклад
1. Оберемо два простих числа: p = 17, q = 19;
2. Обчислимо n = 17 * 19 = 323, fi = (p - 1) * (q - 1) = 16 * 18 = 288;
3. Оберемо e = 7 (НСД(e, fi) = 1) та розв’яжемо рівняння 7 * d 1 (mod 288), звідки d = 247.
Побудовано RSA систему: p = 17, q = 19, n = 323, e = 7, d = 247.
Відкритий ключ: n = 323, e = 7, секретний ключ: d = 247.
1. m = 4. Кодування: 47 mod 323 = 234. Декодування: 234247 mod 323 = 4.
2. m = 123. Кодування: 1237 mod 323 = 251. Декодування: 251247 mod 323 = 123.
Циклічна атака За відомим шифром c (c = me mod n) злодій, маючи відкритий ключ e та n, бажає знайти повідомлення m. Він починає будувати послідовність чисел
c, ce, , , …
Оскільки обчислення відбуваються в групі Zn*, то елемпнти послідовності знаходяться в межах від 0 до n - 1. Отже існує таке натуральне k, що с = . Враховуючи що c = me mod n, маємо: me = або m = .
Таким чином для знаходження повідомлення m за його шифром c необхідно побудувати послідовність c, ce, , , …, , = c, і взяти її передостаннє число.
Приклад
Розв’язати рівняння: m7 mod 323 = 251.
e = 7, n = 323, c = 251.
k | |
0 | 251 |
1 | 310 |
2 | 47 |
3 | 4 |
4 | 234 |
5 | 123 |
6 | 251 |
З таблиці маємо: c = = 251. Оскільки me = , то m = = 123.
Атака методом осліплення
Припустимо, А має секретний ключ RSA системи, а Z – злодій, який перехопив шифр c і хоче декодувати його. При цьому А відмовляє видати Z вихідний текст m. Тоді Z обирає деяке значення b Zn*, обчислює c’ = be * c і просить А дешифрувати його. А погоджується дешифрувати c’ своїм секретним ключем d, оскільки зміст повідомлення c’ йому ні про що не говорить і виглядає невинним. Отримавши m’ = c’d mod n, злодій Zобчислює m = m’ / b і отримує шукане m. Шифром m дійсно є c, оскільки me = m’e / be = c’de / be = c’ / be = c.
Така атака можлива, оскільки А не знає повної інформації про шифр c’, який дає йому злодій Z.
Приклад. Нехай А має RSA систему: p =17, q = 19, n = 323, e = 7, d = 247.
Злодій Z перехопив шифр c = 234 і хоче знайти таке m, що m7 = 234 mod 323.
1. Z обирає b = 10 Z323*, обчислює c’ = 107 * 234 mod 323 = 14 і просить А дешифрувати його.
A обчислює m’ = 14247 mod 323 = 40 і передає його Z.
3. Z знаходить шукане повідомлення обчислюючи
m = 40 / 10 = 40 * 10-1 = 40 * 97 = 4 mod 323.
Таким чином 47 = 234 mod 323.
Прискорення дешифрування
За допомогою китайської теореми про лишки можна прискорити процес дешифрування, знаючи секретні прості числа p та q.
Алгоритм
Дешифрування. А має декодуючу експоненту d, а також p та q (n = p * q). А отримує від В шифр с та повинен виконати операцію cd (mod n).
1. Обчислити dp = d mod (p - 1), dq = d mod (q - 1)
2. Обчислити mp = mod p, mq = mod q.
3. Розв’язати систему лінійних порівнянь
Розв’язком системи буде декодоване повідомлення: m = cd (mod n).
Приклад
Нехай RSA система має вигляд: p = 17, q = 19, n = 323, e = 7, d = 247.
Для розв’язку рівняння m7 mod 323 = 251 (c = 251) обчислимо 251247 mod 323:
1. dp = 247 mod 16 = 7, dq = 247 mod 18 = 13;
2., mp = 2517 mod 17 = 4, mq = 25113 mod 19 = 9;
3. Розв’яжемо систему лінійних порівнянь
Розв’язуючи її методом Гауса, отримаємо m = 123.
Отже 1237 mod 323 = 251.
Мала декодуюча експонента
Приклад. Виберемо аовідомлення m = 13 та зашифруємо його трьома різними RSA системами.
1. p = 5, q = 17, n = 85, e = 3, d = 57,
m3 mod 85 = 72;
2. p = 11, q = 23, n = 253, e = 3, d = 169,
m3 mod 253 = 173;
3. p = 17, q = 23, n = 391, e = 3, d = 261,
m3 mod 391 = 242;
Для знаходження повідомлення m за відкритими ключами (ni, ei ) та перехопленими шифрами ci складемо систему порівнянь
Одним із її розв’язків буде x = 2197 = 133. Тобто шуканим повідомленням буде m = 13.
Неприховані повідомлення
Означення. Повідомлення m називається неприхованим, якщо його шифр дорівнює самому повідомленню, тобто me = m (mod n).
Наприклад, повідомлення m = 0 та m = 1 завжди є неприхованими для довільних значень e та m.
Твердження. Кількість неприхованих повідомлень в RSA системі дорівнює
(1 + НСД(e - 1, p - 1)) * (1 + НСД(e - 1, q - 1))
Оскільки значення e - 1, p - 1 та q - 1 – парні, то НСД(e - 1, p - 1) 2, НСД(e - 1, q - 1) 2, а отже кількість неприхованих повідомлень завжди не менша за 9.
Другие работы по теме:
Алгоритми Маркова
Нове уточнення поняття алгоритму вітчизняним математиком Марковим: 7 уточнених ним параметрів. Побудова алгоритмів з алгоритмів. Універсальний набір дій по управлінню обчислювальним процесом. Нормальні алгоритми Маркова. Правило розміщення результату.
Сучасні квантові криптографічні лінії зв’язку
Загальні відомості з квантової криптографії - науки винаходу кодів і шифрів. Аналіз симетричних і несиметричних криптографічних систем. Умови абсолютної захищеності симетричної системи. Волоконно-оптичні системи передавання з поляризаційним кодуванням.
Шифрування з секретним ключем
RSA як алгоритм асиметричної криптографії. Етап створення ключів для алгоритму RSA. Історія алгоритмів симетричного шифрування. Схема алгоритму ГОСТ 28147-89. Формування гами шифру в режимі гамування із зворотним зв'язком. Раунд алгоритму Rijndael.
Основні поняття й ознаки теорії складності
Основні підходи до визначення стійкості криптографічних систем і протоколів. Шифр Вернама з одноразовими ключами. Оцінка обчислювальної складності алгоритму. Криптосистема з відкритим ключем. Поняття поліноміального часу. Кількість арифметичних операцій.
Протоколи передавання квантового ключа
Винахід квантової криптографії в 1984 році. Генерація і передача послідовності випадково поляризованих фотонів. Етапи реалізації передачі, прийому й декодування біт квантового ключа в системі с поляризаційним кодуванням. Інтерферометри Маха-Цендера.
Криптографічні методи захисту інформації
Криптологія - захист інформації шляхом перетворення, основні положення і визначення. Криптографія - передача конфіденційної інформації через канали зв'язку у зашифрованому виді. Системи ідентифікації, характеристика алгоритмів шифрування; криптоаналіз.
Кодування файлу
Реалізація програми, яка буде забезпечувати шифрування і дешифрування будь-яких файлів по довільному алгоритму з використанням пароля. Можливість кодування та розкодування утиліти за простим алгоритмом Гамування, який базується на бітовій операції XOR.
Захищені протоколи
Одна з основних причин успіху віддалених атак на розподілені обчислювальні мережі полягає у використанні мережних протоколів обміну, які не можуть надійно ідентифікувати віддалені об’єкти, захистити з’єднання та дані, що передаються по ньому. Тому цілком природньо, що в процесі функціонування Internet були створені різні захищені мережні протоколи, що використовують криптографію як з закритим, так і з відкритим ключем.
Проектування ітераційних алгоритмів
Використання ітерацій для обчислення приблизних значень величин. Розробка ітераційних алгоритмів з перевіркою правильності введення даних. Побудова блок-схеми і програмування мовою Turbo Pascal обчислення значення функції, розкладеної в степеневий ряд.
СУБД "Такси города Москва"
СУБД "Такси города Москва" предназначена для быстрого и эффективного поиска такси. Схематическое изображения структуры СУБД "Такси города Москва". Таблицы описания полей. Функциональные части БД: панель администрирования и пользовательский каталог.
Розрахунок інформаційних характеристик каналу зв'язку
Програма розрахунку інформаційних характеристик каналу зв'язку. Побудова коду для передачі повідомлень. Процедури кодування, декодування та оцінка ефективності кодів. Програма на алгоритмічній мові Паскаль. Канальна матриця, що визначає втрати інформації.
Основи криптографії
Криптографія як область знань щодо перетворення повідомлень у незрозумілу для сторонніх осіб форму, а також перевірки істинності цих повідомлень. Класифікація шифрів, принципи частотного криптоаналізу. Таблиця заміни при шифруванні, приклади шифрування.
Будування плакатів та блок-схем
Особливості зображення плакатів у MSVisio. Будування блок-схем алгоритмів згідно варіантів. Віртуальна інфраструктура сервера. Структура центра управління сіттю AltegroSky. Взаємозв’язок операційної системи, віртуальної машини та користувача комп’ютера.
МПС цифрового оброблення сигналів
Сучасні системи ЦОС будуються на основі процесорів цифрових сигналів (ПЦС). Сигнальними мікропроцесорами (СМП) або процесорами цифрових сигналів є спеціалізовані процесори, призначені для виконання алгоритмів цифрової обробки сигналів у реальному часі.
Завадостійке кодування на основі циклічних кодів
Microsoft Visual Studio Solution File, Format Version 10.00 # Visual Studio 2008 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "CRC32", "CRC32CRC32.csproj", "{EE28F805-6DA0-4E7B-89A5-A3B245E1441D}" EndProject Global GlobalSection(SolutionConfigurationPlatforms) = preSolution Debug|Any CPU = Debug|Any CPU Release|Any CPU = Release|Any CPU EndGlobalSection GlobalSection(ProjectConfigurationPlatforms) = postSolution {EE28F805-6DA0-4E7B-89A5-A3B245E1441D}.Debug|Any CPU.ActiveCfg = Debug|Any CPU {EE28F805-6DA0-4E7B-89A5-A3B245E1441D}.Debug|Any CPU.Build.0 = Debug|Any CPU {EE28F805-6DA0-4E7B-89A5-A3B245E1441D}.Release|Any CPU.ActiveCfg = Release|Any CPU {EE28F805-6DA0-4E7B-89A5-A3B245E1441D}.Release|Any CPU.Build.0 = Release|Any CPU EndGlobalSection GlobalSection(SolutionProperties) = preSolution HideSolutionNode = FALSE
Математична модель вимірювальної системи в середовищі Delphi
Курсова робота Математична модель вимірювальної системи в середовищі Delphi АНОТАЦІЯ Опис програми містить загальний опис алгоритмів головної програми та допоміжних на рівні блок-схем, а також більш детальний опис розробленої програми на рівні програмного коду.
Допоміжні алгоритми
та тему: ДОПОМІЖНІ АЛГОРИТМИ Тема: Допоміжні алгоритми. Мета уроку: навчити учнів складати допоміжні алгоритми; виховати старанність, дисциплінованість;
Прикладна теорія цифрових автоматів 2
АНОТАЦІЯ Курсове проектування є завершальним етапом вивчення студентами спеціальних дисциплін, передбачених робочим планом за фахом АМ. Задачі курсового проектування - закріплення, систематизація, поглиблення і розвиток теоретичних і практичних знань, отриманих у процесі вивчення дисципліни, а також придбання ними практичних навичок самостійного рішення загальнотеоретичних, практичних і методичних питань проектування програмних продуктів.
Прикладна теорія цифрових автоматів 3
Міністерство освіти і науки України ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ Кафедра комп’ютерних інтелектуальних систем та мереж Курсове проектування
Відношення і схеми відношень
Міністерство освіти України Державний університет “Львівська політехніка” Кафедра ICM ВІДНОШЕННЯ І СХЕМИ ВІДНОШЕНЬ Виконала: студентка ФКТ
Криптографічні методи захисту інформації
План Основні положення та визначення криптографії Характеристика алгоритмів шифрування 1. Основні положення та визначення криптографії Проблемою захисту інформації шляхом її перетворення займається криптологія (kryptos - таємний, logos - повідомлення). Вона має два напрямки: криптографію і криптоаналіз.
Проектування керуючих автоматів Мура та Мілі за заданою граф-схемою алгоритму
Анотація Метою даної курсової роботи є закріплення основних теоретичних та практичних положень дисципліни комп`ютерна схемотехніка. В процесі розробки курсової роботи виконується синтез комбінаційної схеми, яка реалізує задану функцію п`яти змінних, та за результатами синтезу будується функціональна схема в заданому базисі.
Отношения /Укр./
Отношения и схемы отношений. Теоретическое объяснение. Практические примеры.
Спрощений Data Encryption Standart
Реферат на тему: Спрощений Data Encryption Standart На рисунку 1 наведена структура спрощеної схеми шифрування DES (Data Encryption Standart). На вхід схеми кодування подається 8 бітовий відкритий текст та 10 бітовий ключ. Результатом роботи схеми є 8 бітовий шифротекст. Схема декодування приймає на вхід 8 бітовий шифротекст та 10 бітовий ключ та виробляє на виході 8 бітовий відкритий текст.
Вивчення роботи пакета програм Microsoft Internet Explorer
Реферат Призначення програми Internet Explorer та її можливості. Для роботи в Iнтернеті необхідно мати простий і зрозумілий інструмент, який дозволив би використовувати всі можливості мережі. Одним з таких інструментів є пакет програм Internet Explorer(MIE), розроблений фірмою Microsoft . Зараз вже продається версія 5.0 цього пакету.
Огляд популярної поштової програми The Bat
РЕФЕРАТ на тему: «Огляд популярної поштової програми The Bat!» he Bat! дійсно могутній і зручний клієнт електронної пошти для Windows 95/98/Me/NT/2000 із приємним інтерфейсом і безліччю унікальних функцій, необхідних у роботі:
Типи алгоритмів
Способи запису алгоритмів. Блок-схеми і правила зображення блок-схеми. Типи алгоритмів. Складання блок-схем. Способи запису алгоритмів. Використовують такі способи подання (опису) алгоритмів:
Подання інформації в комп ютерах
Подання інформації в комп’ютерах” Системи числення. Проблема стискання та кодування інформації з’явилась набагато раніше ніж, власне, термін “інформація”. Згадаємо, що принаймні за часів Римсокої імперії армія використовувала метод шифрування повідомлень з метою її захисту від ворогів. Так званий шифр Цезаря став першим з відомих на сьогодні методів шифрування з таємним ключом.