ЗМІСТ
Введення
5
1.Постановка завдання
10
2. Алгоритм RSA
11
2.1. Система шифрування RSA
12
2.2.Сложность теоретико-числових алгоритмів
16
2.2.1. Алгоритм обчислення
17
2.2.2. Алгоритм Евкліда
18
2.2.3. Алгоритм рішення рівняння
18
2.2.4. Алгоритм знаходження дільників многочлена в кільці
21
3. Якісна теорія алгоритму RSA
23
3.1. Алгоритм, доводить непростоту числа
24
3.2. Знаходження великих простих чисел
26
3.3. Перевірка великого числа на простоту
30
4. Практична реалізація алгоритму
37
4.1. Реалізовані алгоритми
37
4.2. Аналіз результатів
38
5. Висновки
39
5.1 Алгоритм
39
5.2 Алгоритм і програма
39
Висновок
41
Список використаних джерел
42
Додаток 1. Лістинг програми
43
Додаток 2. Головна форма програми
46
Додаток 3. Форма бази даних абонентів
47
Додаток 4. Форма знаходження простих чисел і генерації ключів
48
ВСТУП
Проблема захисту інформації шляхом її перетворення, ис-лягає її прочитання стороннім особою, хвилювала че-ловеческого розум з давніх часів. Історія криптографії - Ровес-ница історії людського мови. Більше того, спочатку писемність сама по собі була своєрідною кріптографіче-ської системою, так як у древніх суспільствах нею володіли тільки обрані. Священні книги стародавнього
Єгипту, стародавній Індії тому приклади.
Історія криптографії умовно можна розділити на 4 етапи.
1) наївна криптографія.
2) формальна криптографія.
3) наукова криптографія.
4) комп'ютерна криптографія.
Для наївною криптографії (до нач. XVI століття) характерно використання будь-яких (зазвичай примітивних) способів запути-вання супротивника щодо змісту шіфруемих тек-стів. На початковому етапі для захисту інформації використан-лись методи кодування і стеганографії , які родствен-ни, але не тотожні криптографії.
Більшість з використовуваних шифрів зводилися до пере-становленнЯ або моноалфавитной підстановці . Одним з перших зафіксованих прикладів є шифр Цезаря, складається в заміні кожної букви вихідного тексту на іншу, відстоїть від неї в алфавіті на певний число позицій. Інший шифр, полибианский квадрат, авторство якого приписує-ся грецькому письменникові Полібію, є загальною моноалфа-Вітні підстановкою, яка проводиться за допомогою випадково заповненої алфавітом квадратною табліцейдля грецького алфавіту розмір становить 5x5). Кожна літера вихідного тек-ста замінюється на букву, вартісну в квадраті знизу від неї.
Етап формальної криптографії (кін. XV століття - поч. XX століття) пов'язаний з появою формалізованих і щодо стійких до ручного криптоанализу шифрів. У європейських країнах це сталося в епоху Відродження, коли розвиток науки і торгівлі викликало попит на надійні способи захисту інформації. Важлива роль на цьому етапі належить Леону Батисті Альберті, італійському архітекторові, який одним з перших запропонував многоалфавитной підстановку . Даний шифр, який отримав ім'я дипломата XVI століття Блеза Вижинера, складався в послідовному В«ДодаванніВ» букв вихідного тексту з ключем (процедуру можна полегшити за допомогою спеціальної таблиці). Його робота В«Трактат про шифрі В»(1466) вважається пер-вої науковою роботою по криптології.
Однією з перших друкованих робіт, в якій узагальнені та сформульовані відомі на той момент алгоритми шифр-вания є праця В«ПоліграфіяВ» (1508 р.) німецького абата Йоганна Трісемуса. Йому належать два невеликих, але важ-них відкриття: спосіб заповнення полибианского квадрата (перші позиції заповнюються за допомогою легко запоминаемого ключового слова, інші - Залишилися літерами алфавіту) і шифрування пар букв (биграмм).
Простим але стійким способом многоалфавитной заміни (підстановки биграмм) є шифр Плейфера, який був відкритий на початку XIX століття Чарльзом Уитстоном. Уїтстона при-належить і важливе вдосконалення - Шифрування В«Подвій-ним квадратом В». Шифри Плейфера і Уитстона використовувалися аж до першої світової війни, так як з працею піддавалися ручного криптоанализу.
У XIX столітті голландець Керкхоффом сформулював головна вимога до криптографічних системам, яке залишається актуальним і понині: секретність шифрів повинна бути осно-вана на секретності ключа, але не алгоритму.
Нарешті, останнім словом в донаучной криптографії, ко-лось забезпечили ще більш високу кріптостойкосіть, а так-же дозволило автоматизувати (В сенсі механізувати) процес шифрування стали роторні криптосистеми .
Однією з перших подібних систем стала винайдена в 1790 році Томасом Джефферсоном, майбутнім президентом США механічна машина. Многоалфавитная підстановка за допомогою роторної машини реалізується варіацією взаємного положення обертаються роторів, кожен з яких здійснює В«ПрошитуВ» в ньому підстановку.
Практичне поширення роторні машини отримали тільки на початку XX століття. Однією з перших практично використовуваних машин, стала німецька Enigma, розроблена в 1917 році Едвардом Хеберном і вдосконалена Артуром Кирхом. Роторні машини активно використовувалися під час другої світової війни. Крім німецької машини Enigma використовувалися також пристрої Sigaba (США), Турех (Великобританія), Red, Orange і Purple2 (Японія). Роторні системи -Вершина формальної криптографії так як щодо просто реалізовували дуже стійкі шифри. Успішні кріптоатакі на роторні системи стали можливі тільки з появою ЕОМ на початку 40-х років.
Головна відмінна риса наукової криптографії (30-ті - 60-ті роки XX століття) - Поява криптосистем із суворим математичним обгрунтуванням криптостійкості. До початку 30-х років остаточно сформувалися розділи математики, є науковою основою криптології: теорія ймовірностей і математична статистика, загальна алгебра, теорія чисел, почали активно розвиватися теорія алгоритмів, теорія інформації, кібернетика. Своєрідним вододілом стала робота Клода Шеннона В«Теорія зв'язку в секретних системах В» (1949), де сформульовані теоретичні принципи криптографічного захисту інформації. Шеннон ввів поняття В«розсіюванняВ» і В«перемішуванняВ», обгрунтував можливість створення наскільки завгодно стійких криптосистем.
У 60-х роках провідні криптографічні школи підійшли до створення блокових шифрів, ще більш стійких в порівнянні з роторними криптосистемами, проте допускають практичну реалізацію тільки у вигляді цифрових електронних пристроїв.
Комп'ютерна криптографія (З 70-х років XX століття) зобов'язана своїм появою обчислювальним засобам з продуктивністю, достатньою для реалізації крітосістем, забезпечують при великій швидкості шифрування на кілька порядків більше високу криптостійкість, ніж В«ручніВ» і В«механічніВ» шифри.
Першим...
