Применение алгоритму RSA для шифрування потоків данных

СОДЕРЖАНИЕ |Запровадження |5 | | |10 | |1.Постановка завдання | | |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 століття) характерно використання будь-яких (зазвичай примітивних) способів заплутування противника щодо змісту шифруемых текстів. На початковому етапі знають за захистом інформації використовувалися методи кодування і стеганографии, які близькі, але тотожні криптографии.

Більшість із використовуваних шифрів полягали в перестановці чи моноалфавитной підстановці. Серед перших зафіксованих прикладів є шифр Цезаря, котра перебувала заміні кожної літери початкового тексту на іншу, віддалену від неї у алфавіті на певна кількість позицій. Інший шифр, полибианский квадрат, яке приписується грецькому письменнику Полібію, є спільною моноалфавитной підстановкою, яка здійснюється з допомогою випадково заповненою алфавітом квадратної таблицейдля грецького алфавіту розмір становить 5×5). Кожна літера вихідного тексту замінюється на букву, вартісну в квадраті знизу від нее.

Етап формальної криптографії (кін. 15 століття — поч. ХХ століття) пов’язані з появою формалізованих і щодо стійких до ручному криптоанализу шифрів. У країни це сталося добу Відродження, коли розвиток науку й торгівлі викликало попит на надійні засоби захисту інформації. Важлива роль цьому етапі належить Леону Батисте Альберти, італійському архітектору, який однією з перших запропонував многоалфавитную підстановку. Цей шифр, який одержав ім'я дипломата XVI століття Блеза Вижинера, перебував у послідовному «додаванні» літер вихідного тексту з ключем (процедуру можна полегшити з допомогою спеціальної таблиці). Його робота «Трактат про шифрі» (1466) вважається першої науковою працею по криптологии.

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

Простим але стійким способом многоалфавитной заміни (підстановки биграмм) є шифр Плейфера, який було відкрито початку ХІХ століття Чарльзом Уитстоном. Уитстону належить та найважливіше вдосконалення — шифрування «подвійним квадратом». Шифри Плейфера і Уитстона використовувалися до першої Першої світової, оскільки ніяк не піддавалися ручному криптоанализу.

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

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

Однією із перших подібних систем стала винайдена в 1790 року Томасом Джефферсоном, майбутнім президентом США механічна машина. Многоалфавитная підстановка з допомогою роторною машини реалізується варіацією взаємного становища обертових роторів, кожен із яких веде «прошиту» у ньому подстановку.

Практичне поширення роторні машини отримали лише на початку ХХ століття. Однією із перших практично використовуваних машин, стала німецька Enigma, розроблена в 1917 року Едвардом Хеберном і вдосконалена Артуром Кирхом. Роторні машини активно використовувалися під час другої Першої світової. Крім німецької машини Enigma використовувалися також устрою Sigaba (США), Турех (Великобританія), Red, Orange і Purple2 (Японія). Роторні системивершина формальної криптографії оскільки щодо просто реалізовували дуже стійкі шифри. Успішні криптоатаки на роторні системи відбуваються тільки з появою ЕОМ на початку 40-х годов.

Головна характерна риса наукової криптографії (30-ті - 60-ті роки XX століття) — поява криптосистем із суворим математичним обгрунтуванням криптостойкости. На початку 1930;х остаточно сформувалися розділи математики, є наукової основою криптологии: теорія ймовірностей і математична статистика, загальна алгебра, теорія чисел, почали активно розвиватися теорія алгоритмів, теорія інформації, кібернетика. Своєрідним вододілом стала робота Клода Шеннона «Теорія зв’язку в секретних системах» (1949), де сформульовані теоретичні принципи криптографічного захисту інформації. Шеннон ввів поняття «розсіювання» і «перемішування», обгрунтував можливість створення як завгодно стійких криптосистем.

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

Комп’ютерна криптографія (з 1970;х років ХХ століття) зобов’язана своїм появою обчислювальним засобам з продуктивністю, достатньої для реалізації критосистем, які забезпечують за високої швидкості шифрування на кілька порядків вищу криптостойкость, ніж «ручні» і «механічні» шифры.

Першим класом криптосистем, практичне застосування яких стали можливе з появою потужних і компактних обчислювальних коштів, стали блочні шифри. У роки розробили американський стандарт шифрування DES (прийнятий у 1978 року). Одне з авторів, Хорст Фейстел (співробітник IBM), описав модель блокових шифрів, з урахуванням якому було побудовано інші, стійкіші симетричні криптосистемы, зокрема вітчизняний стандарт шифрування ГОСТ 28 147–89.

З появою DES збагатився і криптоанализ, для атак на американський алгоритм був створено кілька нових видів криптоанализа (лінійний, диференціальний тощо.), практична реалізація яких знов-таки була можливе тільки з приходом потужних обчислювальних систем.

У 1970;х років стався справжній прорив у сучасної криптографії - поява асиметричних криптосистем, які вимагали передачі секретного ключа між сторонами. Тут відправною точкою прийнято вважати роботу, опубліковану Уитфилдом Диффи і Мартіном Хеллманом в 1976 року під назвою «Нові напрями у сучасної криптографії». У ньому вперше сформульовані принципи обміну шифрованою інформацією без обміну секретним ключем. Незалежно до ідеї асиметричних криптосистем підійшов Ральф Мерклі. Кількома роками пізніше Рон Ривест, Аді Шамир і Леонард Адлеман відкрили систему RSA, першу практичну асиметричну криптосистему, стійкість якої був полягає в проблемі факторизации великих простих чисел. Асиметрична криптографія відкрила відразу кількох нових прикладних напрямів, зокрема системи електронного цифрового підписи (ЭЦП) і електронних денег.

У 80−90-ті роки з’явилися цілком нові напрями криптографії: ймовірнісна шифрування, квантова криптографія та інші. Усвідомлення їх практичної цінності у майбутньому. Актуальною залишається завдання вдосконалення симетричних криптосистем. У 80−90 роки були розроблено нефейстеловские шифри (SAFER, RC6 та інших.), а 2000 року після відкритого міжнародного конкурсу ухвалили новий національний стандарт шифрування США — AES.

1. ПОСТАНОВКА ЗАДАЧИ.

Безпека передачі каналами телефонного зв’язку є актуальною. Сучасні комп’ютерні мережі не виняток. На жаль, в мережевих операційні системи (Windows NT/XP, Novell тощо.) іноземного виробництва, як наслідок, через експортних міркувань рівень алгоритмів шифрування помітно снижен.

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

2. АЛГОРИТМ RSA.

Праці Евкліда і Диофанта, Ферма і Эйлера, Гаусса, Чебишева і Эрмита містять дотепні і дуже ефективні алгоритми рішення диофантовых рівнянь, з’ясування разрешимости порівнянь, побудови великих за тими часів простих чисел, перебування найкращих наближень тощо. Останні двоє десятиліть, завдяки насамперед запитам криптографії і значному поширенню ЕОМ, дослідження з алгоритмическим питанням теорії чисел переживають період бурхливого і дуже плідного развития.

Обчислювальні машини та електронні засоби зв’язку проникли практично у всі сфери людської діяльності. Немислима без неї і сучасна криптографія. Шифрування і дешифрування текстів можна уявляти собі як процеси переробки цілих чисел з допомогою ЕОМ, а способи, якими виконуються ці операції, як функції, певні на безлічі цілих чисел. Усе це робить природним появу у криптографії методів теорії чисел. З іншого боку, стійкість низки сучасних криптосистем обгрунтовується лише складністю деяких теоретико-числовых задач.

Але можливості ЕОМ мають певні кордону. Доводиться розбивати довгу цифрову послідовність на блоки обмеженою довжини і шифрувати кожна така блок окремо. Ми вважатимемо надалі, що це шифруемые цілі числа неотрицательны за величиною менше деякого заданого (скажімо, технічними обмеженнями) числа m. Так само умовам будуть задовольняти і кількості, одержувані у процесі шифрування. Це дозволяє вважати й й інші числа елементами кільця відрахувань [pic]. Шифрующая функція у своїй може розглядатися як взаимнооднозначное відображення кілець вычетов.

[pic] а число [pic] є повідомлення [pic] в зашифрованому виде.

Найпростіший шифр що така — шифр заміни, відповідає відображенню [pic] попри деякий фіксованому цілому k. Такий шифр використав Юлій Цезар. Звісно, не кожне відображення [pic] адресований цілей надійного приховування информации.

У 1978 р. американці Р. Ривест, А. Шамир і Л. Адлеман (R.L.Rivest. A.Shamir. L. Adleman) запропонували приклад функції [pic], яка має поруч чудових достоїнств. На її основі було побудовано реально використовувана система шифрування, названа за першими літерами імен авторівсистема RSA. Ця функція така, что.

1) є досить швидкий алгоритм обчислення значень [pic];

2) є досить швидкий алгоритм обчислення значень зворотної функції [pic];

3) функція [pic] має деяким «секретом», знання якої дозволяє швидко вираховуватимуть значення [pic]; у протилежному випадку обчислення [pic] буває важко можливо розв’язати в обчислювальному відношенні завданням, що вимагає для свого вирішення таких чимало часу, що у его прошествии зашифрована інформація перестає цікавити осіб, використовують відображення [pic] як шифра.

Ще виходу друком статті копія доповіді в Массачусетському Технологічному інституті, присвяченого системі RSA. було послано відомому популяризаторові математики М. Гарднеру, що у 1977 р. в журналі Scientific American статтю посвящённую в цій системі шифрування. У російському перекладі заголовок статті Гарднера таке: Новий вид шифру, на розшифровку якого знадобляться мільйони. Саме ця стаття зіграла найважливішу роль поширенні інформацію про RSA, привернула до криптографії увагу широкого загалу нефахівців і фактично сприяла бурхливому прогресу цій галузі, подій у наступні 20 лет.

2.1. система шифрування RSA.

Нехай [pic] і [pic] натуральні числа. Функція [pic] реалізує схему RSA, влаштована наступним образом.

[pic].

(1) Для розшифровки повідомлення [pic] досить вирішити сравнение.

[pic]. (2) У певних умовах на [pic] і [pic] це порівняння має єдине рішення [pic].

А, щоб описати цих умов і пояснити, як знайти рішення, нам знадобиться одна теоретико-числовая функція, так звана функція Эйлера. Ця функція натурального аргументу [pic] позначається [pic] і дорівнює кількості цілих чисел на відрізку від 1 до [pic], взаємно простих з [pic]. Так [pic] і [pic] нічого для будь-якого простого числа [pic] і натурального [pic]. З іншого боку, [pic] для будь-яких натуральних взаємно простих [pic] і [pic]. Ці властивості дозволяють легко обчислити значення [pic], якщо відомо розкладання числа [pic] на прості сомножители.

Якщо показник ступеня [pic] порівняно (2) взаємно простий з [pic], то порівняння (2) має єдине рішення. А, щоб знайти його, визначимо ціла кількість [pic], що задовольнить условиям.

[pic]. (3) Таке число існує, оскільки [pic], до того ж єдино. Тут і далі символом [pic] буде позначатися найбільший загальний дільник чисел [pic] і [pic]. Класична теорема Эйлера, стверджує, що кожного числа [pic], взаємно простого з [pic], виконується порівняння [pic] і, следовательно.

[pic].

(4) Отже, в припущенні [pic], єдине рішення порівняння (2) то, можливо знайдено в виде.

[pic].

(5) Якщо додатково припустити, що кількість [pic] складається з різноманітних простих сомножителей, то порівняння (5) виконуватиметься і припущення [pic]. Справді, позначимо [pic] і [pic]. Тоді [pic] ділиться на [pic], та якщо з (2) слід, що [pic]. Подібно (4), тепер легко знаходимо [pic]. Крім того, маємо [pic]. Утворені порівняння з [pic] дають нам (5).

Функція (1), затверджена системі RSA, то, можливо обчислена досить швидко. Зворотний до [pic] функція [pic] обчислюється за тими самими правилам, що і [pic], лише заміняючи показника ступеня [pic] на [pic]. Отже, для функції (1) обіцяє вищезазначені властивості 1) і 2).

Для обчислення функції (1) досить знати лише числа [pic] і [pic]. Саме вони є відкритий ключ для шифрування. Для обчислення зворотної функції потрібно знати число [pic]. це й є «секретом», про який ішлося йде на пункті в). Здається. дуже легко. знаючи число [pic]. розкласти його за прості сомножители, обчислити потім за допомогою відомих правил значення [pic] і, нарешті, з допомогою (3) визначити потрібне число [pic]. Усі кроки цього обчислення можна реалізувати досить швидко, крім першого. Саме розкладання числа [pic] на прості множники і як найбільш трудомістку частина обчислень. Теоретично чисел попри багаторічну її пам’ятати історію та на дуже інтенсивні пошуки протягом останніх 20 років, ефективний алгоритм розкладання натуральних чисел на множники не знайдено. Звісно, можна, перебираючи все прості числа до [pic], і. ділячи ними [pic], знайти необхідну розкладання. Але, враховуючи, що кількість простих у тому проміжку, асимптотически одно [pic], знаходимо, що з [pic], записываемом 100 десятковими цифрами, знайдеться щонайменше [pic] простих чисел, куди доведеться ділити [pic] при розкладанні його за множники. Дуже грубі прикидки показують, що комп’ютера, виконує мільйон ділень в секунду, для розкладання числа [pic] у такий спосіб на прості сомножители знадобиться щонайменше, ніж [pic] років. Відомі й більш ефективні засоби розкладання цілих чисел на множники, ніж простий перебір простих делителей, але вони працюють дуже медленно.

Автори схеми RSA запропонували вибирати число [pic] як твори двох простих множників [pic] і [pic], однакових за величиною. Так как.

[pic],.

(6) то єдину умову вплинув на вибір показника ступеня [pic] в відображенні (1) есть.

[pic].

(7).

Отже, обличчя, був зацікавлений у організації шифрованою листування з допомогою схеми RSA, вибирає два досить великих простих числа [pic] і [pic]. Перемножая їх, воно знаходить число [pic]. Потім вибирається число [pic], що задовольнить умовам (7), обчислюється з допомогою (6) число [pic] і з допомогою (3) — число [pic]. Числа [pic] і [pic] публікуються, число [pic] залишається секретним. Тепер будь-хто може відправляти зашифровані з допомогою (1) повідомлення організатору цією системою, а організатор легко зможе розшифровувати з допомогою (5).

Для ілюстрації свого методу Ривест, Шамир і Адлеман зашифрували у такий спосіб деяку англійську фразу. Спочатку вона стандартним чином (а=01, b=02, … z=26, пробел=00) була як цілого числа [pic], та був зашифровано з допомогою відображення (1) при m=11 438 162 575 788 886 112 112 966 624 049 616 573 949 531 077 118 699 142 673 390 895 104.

6 935 245 733 897 829 916 253 312 581 564 096 129 393 186 210 847 132 133 359 616 і [pic]. Ці дві числа були опубліковані, причому додатково повідомлялося, що [pic]. де [pic] і [pic] - прості числа, записувані відповідно 64 і 65 десятковими знаками. Першому, хто розшифрує відповідне повідомлення [pic], пообіцяли нагорода в 100 $.

Ця історія завершилася через 17 років у 1994 р., коли D. Atkins, M. Graff, А. До. Lenstra і Р. З. Leyland повідомили про розшифровці фрази. Числа [pic] і [pic] виявилися рівними [pic], [pic].

Цей чудовий результат (розкладання на множники 129-значного десяткового числа) було досягнуто завдяки використанню алгоритму розкладання чисел на множники, званого методом квадратичного решета. Виконання обчислень зажадало колосальних ресурсів. Діяльність, очолюваній чотирма авторами проекту, і що тривала після попередньої теоретичної підготовки приблизно 220 днів, на добровільних засадах брали участь близько 600 чоловік і приблизно 1600 комп’ютерів, об'єднаних мережею Internet. Нарешті, відзначимо, що премія 100 $ була передано в Free Software Foundation.

2.2.Сложность теоретико-числовых алгоритмов.

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

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

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

Наступний алгоритм обчислює [pic] за [pic] арифметичних операцій. У цьому, звісно, передбачається, що натуральні числа [pic] і [pic] не перевершують за величиною [pic].

2.2.1. Алгоритм обчислення [pic] 1) Уявімо [pic] в двоичной системі числення [pic], де [pic], цифри в двоичном поданні, рівні 0 чи 1, [pic]. 2) Поклавши [pic] і далі для [pic] вычислим.

[pic].

3) [pic] є шуканий відрахування [pic].

Справедливість цього алгоритму випливає з сравнения.

[pic], легко доказуваного індукцією по [pic].

Оскільки кожне обчислення на кроці 2 вимагає трохи більше трьох умножений по модулю [pic] і це крок виконується [pic] раз, то складність алгоритму можна оцінити величиною [pic].

Другий алгоритм — це класичний алгоритм Евкліда обчислення найбільшого загального дільника цілих чисел. Ми вважаємо заданими два натуральних числа [pic] і [pic] і обчислюємо їх найбільший загальний дільник [pic].

2.2.2. Алгоритм Евкліда 1) Обчислимо [pic] - залишок від розподілу числа [pic] на [pic], [pic], [pic]. 2) Якщо [pic], то [pic] є дані число. 3) Якщо [pic], то замінимо пару чисел [pic] парою [pic] і перейдемо к шагу 1.

Теорему 1. При обчисленні найбільшого загального дільника [pic] з допомогою алгоритму Евкліда буде виконано трохи більше [pic] операцій розподілу з залишком, де [pic] є кількість цифр в десяткової записи меншого з чисел [pic] і [pic].

Доказ. Поклавши [pic] і визначимо [pic] - послідовність делителей, з’являються у виконання кроку 1 алгоритму Евкліда. Тогда.

[pic]. Нехай також [pic], [pic], [pic], [pic], — послідовність Фібоначчі. Індукцією по [pic] від [pic] до [pic] легко доводиться нерівність [pic]. Оскільки [pic], тут маємо нерівності [pic] і [pic].

Трохи підправивши алгоритм Евкліда, можна досить швидко вирішувати порівняння [pic] за умови, що [pic]. Це завдання рівносильна пошуку цілих рішень рівняння [pic].

2.2.3. Алгоритм рішення рівняння [pic].

0) Визначимо матрицю [pic].

1) Обчислимо [pic] - залишок від розподілу числа [pic] на [pic], [pic], [pic]. Якщо [pic], то другий стовпець матриці [pic] дає вектор [pic].

решений рівняння. 3) Якщо [pic], то замінимо матрицю [pic] матрицею [pic]. 4) Замінимо пару чисел [pic] парою [pic] і час торкнутися кроку 1.

Якщо позначити через [pic] матрицю [pic], виникає у процесі роботи алгоритму перед кроком 2 після [pic] ділень із залишком (крок 1), то позначеннях з докази теореми 1 на той час виконується векторное рівність [pic]. Оскільки числа [pic] і [pic] взаємно прості, маємо [pic], і це доводить, що алгоритм справді дає рішення рівняння [pic]. Буквою [pic] ми позначили кількість ділень із залишком, що у точності таку ж, як й у алгоритмі Евклида.

Три приведених вище алгоритму ставляться до розряду про полиномиальных алгоритмів. Цю саму назву носять алгоритми, складність яких оцінюється згори статечним чином у залежність від довжини записи вхідних чисел. Якщо найбільше з чисел, поданих на вхід алгоритму, не перевершує [pic], то складність алгоритмів цього оцінюється величиною [pic], де [pic] - деяка абсолютна стала. В усіх життєвих приведених вище прикладах [pic].

Полиномиальные алгоритми теоретично чисел — велика рідкість. Та й опенки складності алгоритмів найчастіше за все спираються на будь-які не доведені, але правдоподібні гіпотези, зазвичай які стосуються аналітичної теорії чисел.

Для деяких завдань ефективні алгоритми взагалі відомі. Іноді у разі таки можна знайти запропонувати послідовність дій, яка, «якщо поталанить», швидко призводить до необхідному результату. Існує клас про ймовірнісних алгоритмів, що дають правильний результат, але мають імовірнісного опеньку часу роботи. Зазвичай робота цих алгоритмів залежить від однієї чи навіть кількох параметрів. У щонайгіршому разі вони працюють який досить довго. Але вдалий вибір параметра визначає швидке завершення роботи. Такі алгоритми, якщо безліч «хороших» значень параметрів велике, практично працюють досить ефективно, хоча й мають хороших опеньок сложности.

Ми будемо іноді використовувати слова детермінований алгоритм, щоб відрізняти алгоритми у звичному значенні від ймовірнісних алгоритмов.

Свідченням, розглянемо імовірнісний алгоритм, дозволяє ефективно знаходити рішення полиномиальных порівнянь простим модулю. Нехай [pic] — просте число, яке передбачається великим, і [pic] - багаточлен, ступінь якої планується обмеженою. Завдання полягає у знаходженні рішень сравнения.

[pic].

(8) Наприклад, можна говорити про рішення квадратичных порівнянь, якщо ступінь багаточлена [pic] дорівнює 2. Інакше кажучи, ми повинні відшукати на полі [pic] все елементи, задовольняють рівнянню [pic].

Відповідно до малої теоремі Ферма, все елементи поля [pic] є однократными корінням багаточлена [pic]. Тому, зрозумівши найбільший загальний дільник [pic], знайдемо багаточлен [pic], безліч коренів що його полі [pic] збігаються з безліччю коренів багаточлена [pic], причому всі ці коріння однократны. Якщо з’ясується, що багаточлен [pic] має нульову ступінь, т. е. лежать у полі [pic], це означатиме, що порівняння (8) немає решений.

Для обчислення багаточлена [pic] зручно спочатку обчислити багаточлен [pic], користуючись алгоритмом, подібним описаного вище алгоритму спорудження до рівня (нагадаємо, що кількість [pic] передбачається великим). Ну, а потім з допомогою аналога алгоритму Евкліда обчислити [pic]. Усе це виконується за полиномиальное кількість арифметичних операций.

Отже, обговорюючи далі завдання перебування рішень порівняння (8), ми можемо припускати, що у кільці багаточленів [pic] справедливо равенство.

[pic].

2.2.4. Алгоритм перебування делителей багаточлена [pic] в кільці [pic].

1) Виберемо у спосіб елемент [pic]. 2) Обчислимо найбільший загальний дільник [pic]. 3) Якщо багаточлен [pic] виявиться власним делителем [pic], то многочлен.

[pic] распадётся на два множника і з кожним із них незалежно потрібно буде проробити усі фінансові операції, передбачені справжнім алгоритмом для багаточлена [pic].

4) Якщо з’ясується, що [pic] чи [pic], слід можливість перейти до кроку 1 і. обравши нового значення [pic], продовжити виконання алгоритма.

Кількість операцій на кроці 2 оцінюється величиною [pic], якщо обчислення проводити оскільки це вказувалося вище під час перебування [pic]. З’ясуємо де тепер, як довго доведеться вибирати числа [pic], перебувають у кроці 2 нічого очікувати знайдено власний дільник [pic]. Кількість рішень рівняння [pic] на полі [pic] не перевершує [pic]. Це означає, що підмножина [pic] елементів [pic], які відповідають условиям.

[pic], не менш, ніж із [pic] елементів. З огляду на тепер, кожен ненульовий елемент [pic] задовольняє одного з рівностей [pic], або [pic], укладаємо, що з [pic] одна з чисел [pic] буде коренем багаточлена [pic], а інше — немає. Для таких елементів [pic] багаточлен [pic], певний на кроці 2 алгоритму, буде власним делителем багаточлена [pic].

Отже, існує менш [pic] «вдалих» виборів елемента [pic], при яких кроці 2 алгоритму багаточлен [pic] распадётся у власних множника. Отже, при «випадковому» виборі елемента [pic], можливість, що багаточлен не розкладеться на множники після [pic] повторень кроків алгоритму 1−4. не перевершує [pic]. Можливість зі зростанням [pic] убуває нас дуже швидко. І це дійсно, практично цей алгоритм працює досить эффективно.

Зауважимо, що з опенке ймовірності ми використовували лише 2 кореня багаточлена [pic]. При [pic] ця можливість, звісно, ще менша. Більше тонкий аналіз з допомогою опеньок А. Вейля для сум характерів показує, що ймовірність для багаточлена [pic] не розпастися на множники при одноразовому проході кроків алгоритму 1−4. не перевершує [pic]. Тут стала в [pic] залежить від [pic].

Якщо порівнянні (8) замінити простий модуль [pic] складовим модулем [pic], то завдання перебування рішень відповідного порівняння стає набагато більше складної. Відомі алгоритми вирішення засновані на зведенні порівняння до сукупності порівнянь (8) за простими модулями — делителям [pic], і. отже, вони вимагають розкладання те на прості сомножители, що, як зазначалося, є дуже трудомісткою задачей.

3. ЯКІСНА ТЕОРІЯ АЛГОРИТМУ RSA.

Існує досить ефективний засіб переконатися, що заданий число є складовим, не розкладаючи їх кількість на множники. Відповідно до малої теоремі Ферма, якщо число [pic] просте, то тут для будь-якого цілого [pic], не делящегося на [pic], виконується сравнение.

[pic].

(9) Якщо навіть за якомусь [pic] це порівняння порушується, можна стверджувати, що [pic] - складене. Перевірка (9) не потребує великих обчислень, це потрібно з алгоритму 1. Ось тільки у цьому, як знайти для складеного [pic] ціле число [pic], не що задовольнить (9). Можна, наприклад, намагатися знайти необхідну кількість [pic], відчуваючи все цілі числа поспіль, починаючи з 2. Або спробувати вибирати ці числа випадково на відрізку [pic].

На жаль, такий який завжди дає те, що хотілося б. Є складові числа [pic], які мають властивістю (9) нічого для будь-якого цілого [pic] з умовою [pic]. Такі числа називаються числами Кармайкла. Розглянемо, наприклад, число [pic]. Оскільки 560 ділиться кожне з чисел 2, 10, 16, то з допомогою малої теореми Ферма легко перевірити, що 561 є число Кармайкла. Можна довести, що будь-який з чисел Кармайкла має вигляд [pic], де всі прості [pic] різні, причому [pic] ділиться кожну різницю [pic]. Лише недавно, було про нескінченності безлічі таких чисел.

У 1976 р. Міллер запропонував замінити перевірку (9) перевіркою кілька іншого умови. Якщо [pic] - просте число, [pic], де [pic] нечётно, то відповідно до малої теоремі Ферма кожному за [pic] з вимогою [pic] хоча б одне з скобок в произведении.

[pic] ділиться на [pic]. Звернення цього властивості можна використовувати, щоб відрізняти складові числа від простых.

Нехай [pic] - нечётное складене число, [pic], де [pic] нечётно. Назвемо ціла кількість [pic], [pic], «хорошим» для [pic], якщо порушується одне з цих двох условий:

1) [pic] не ділиться на [pic];

2) [pic] чи існує цілий [pic], [pic], таке, что.

[pic].

З сказаного раніше слід, що з простого числа [pic] не існує хороших чисел [pic]. Якщо ж [pic] складене число, те, як довів Рабин, існує щонайменше [pic].

Нині можна побудувати імовірнісний алгоритм, який відрізняє складові числа від простых.

3.1. Алгоритм, доводить непростоту числа 1) Виберемо випадково число [pic], [pic], і перевіримо для этого числа вищезазначені властивості 1) і 2) п. 2. 2) Коли б одне з яких порушується, то число [pic] складене. 3) Якщо виконані обидва умови 1) і 2) п. 2, повертаємося до кроку 1.

З сказаного вище варто, що складене число нічого очікувати визначено як складене після однократного виконання кроків 1−3 з імовірністю не більшої [pic]. А ймовірність не визначити її після [pic] повторень не перевершує [pic]. т. е. убуває дуже быстро.

Міллер запропонував детермінований алгоритм визначення складових чисел, має складність [pic], проте справедливість його результату залежить від недоведеною нині так званої розширеній гіпотези Рімана. Відповідно до цього алгоритму досить перевірити умови 1) і 2) п. 2 всім цілих чисел [pic], [pic]. Якщо за якомусь [pic] з зазначеного проміжку порушується одна з умов а) чи б), число [pic] складене. Інакше він буде простим чи ступенем простого числа. Остання можливість, звісно, легко проверяется.

Нагадаємо деякі поняття, необхідних формулювання розширеній гіпотези Рімана. Вони знадобляться нас і надалі. Нехай [pic] - ціле число. Функція [pic] називається характером Дирихле по модулю [pic], чи просто характером, Якщо ця функція періодична з періодом [pic], відрізняється від нуля лише з числах, взаємно простих з [pic], і мультипликативна, т. е. для будь-яких цілих [pic] виконується рівність [pic]. До кожного [pic] існує рівно [pic] характерів Дирихле. Вони утворюють групу з множенню. Одиничним елементом цієї групи є так званий головний характер [pic], рівний 1 усім числах, взаємно простих з [pic], і 0 на інших цілих числах. Порядком характеру називається його порядок як елемента мультипликативной групи характерів. Із кожним характером вочевидь пов’язана так звана [pic] - функція Дирихле — функція комплексного змінного [pic], певна рядом[pic]. Сума цього самого ряду аналитична у сфері [pic] і то, можливо аналітично продовжено протягом усього комплексну площину. Наступне співвідношення [pic] пов’язує L — функцію, відповідальну головному характеру, з дзета-функцией Рімана [pic]. Розширена гіпотеза Рімана стверджує, що комплексні нулі всіх Lфункцій Дирихле, які працюють у смузі [pic], лежать на прямий [pic]. Нині не доведено навіть найпростіша форма цієї гіпотези — класична гіпотеза Рімана, яким стверджується той самий факт про нулях дзетафункции.

У 1952 р. Анкени з допомогою розширеній гіпотези Рімана довів, що кожному за простого числа [pic] існує квадратичний невычет [pic], зрозумілу неравенствам [pic]. Константа 70 була обчислено пізніше. Саме ця затвердження Кабміном і є основою алгоритму Міллера. У 1957 р. Берджесс довів існування такого невычета без використання розширеній гіпотези Рімана, але з гіршій оцінкою [pic], справедливою при будь-якому позитивному [pic] і [pic], більшому деякою кордону, залежної от[pic].

Алгоритм Міллера принципово відрізняється від алгоритму 2.1., оскільки отримане з її допомогою твердження у тому, що кількість [pic] - складене, спирається на недоведену розширену гіпотезу Рімана і тому то, можливо неправильним. Тоді як імовірнісний алгоритм 2.1. дає цілком пошук правильної відповіді для складових чисел. Попри відсутність оцінок складності, практично він працює цілком удовлетворительно.

3.2. Перебування великих простих чисел.

Звісно ж, великі прості числа можна будувати порівняно швидко. У цьому можна забезпечувати їхню випадкове розподіл в заданому діапазоні величин. Інакше втрачала б всякий практичний сенс система шифрування RSA. Найбільш ефективним засобом побудови простих чисел є кілька модифікована мала теорема Ферма.

Теорему 2. Нехай [pic] - нечётные натуральні числа, [pic], причому кожному за простого дільника [pic] числа [pic] існує цілий число [pic] таке, что.

[pic]. (10) Тоді кожен простий дільник [pic] числа [pic] задовольняє сравнению.

[pic].

Доказ. Нехай [pic] - простий дільник числа [pic], a [pic] - певний дільник [pic]. З умов (10) слід, що у полі відрахувань [pic] справедливі соотношения.

[pic].

(11) Означимо буквою [pic] порядок елемента [pic] в мультипликативной групі поля [pic]. Перші дві з співвідношень (11) означають, що [pic] входить у розкладання на прості множники числа [pic] певною мірою той самий, як й у розкладання [pic], а останнє - що [pic] ділиться на [pic]. Отже, кожен простий дільник числа [pic] входить у розкладання [pic] певною мірою не меншою, ніж у [pic], отже [pic] ділиться на [pic]. З іншого боку, [pic] четно. Теорему 2 доказана.

Слідство. Якщо виконані умови теореми 2 і [pic], то [pic] - просте число.

Справді, нехай [pic] дорівнює твору щонайменше двох простих чисел. І з них, за твердженням теореми 2, незгірш від, ніж [pic]. Але тоді [pic]. Протиріччя і доводить следствие.

Покажемо тепер, як за допомогою останнього затвердження, маючи велике просте число [pic], можна побудувати істотно більше просте число [pic]. Виберемо при цьому випадково чётное число [pic] на проміжку [pic] і між іншим [pic]. Потім перевіримо число [pic] на відсутність малих простих делителей, розділивши його за малі прості числа; відчуємо [pic] певна кількість разом із допомогою алгоритму 5. Якщо за цьому з’ясується, що [pic] - складене число, слід вибрати нового значення [pic] і знову повторити обчислення. Так варто робити до того часу, поки що не знайдено число [pic], выдержавшее випробування алгоритмом 5 досить багаторазово. У цьому випадку з’являється надія те що, що [pic] - просте число, і треба спробувати довести простоту з допомогою тестів теореми 2.

І тому можна випадково вибирати число [pic], і перевіряти йому виконання соотношений.

[pic].

(12) Якщо за обраному [pic] ці співвідношення виконуються, відповідно до слідству з теореми 2, можна стверджувати, що кількість [pic] просте. Якщо ж цих умов порушуються, потрібно вибрати інше значення [pic] і повторювати ці операції до того часу, поки така кількість нічого очікувати обнаружено.

Припустимо, що побудоване число [pic] справді є простим. Постає запитання, як довго доведеться перебирати числа [pic], поки що не знайдено таке, котрій обіцяє умови (12). Зауважимо, що з простого числа [pic] першу умову (12), відповідно до малої теоремі Ферма, виконуватиметься завжди. Ті ж числа [pic], котрим порушується друге умова (12), задовольняють порівнянню [pic]. Як відомо, рівняння [pic] на полі відрахувань [pic] має більш [pic] рішень. Одне [pic]. Тому на згадуваній проміжку [pic] є трохи більше [pic] чисел, котрим вони не виконуються умови (12). Це означає, що, обираючи випадково числа [pic] на проміжку [pic], при простому [pic] з ймовірністю більшої, ніж [pic], знайти число [pic], для якого буде виконані умови теореми 2, і тих довести, що [pic] справді є простим числом.

Зауважимо, що побудоване у такий спосіб просте число [pic] буде задовольняти нерівності [pic], т. е. буде записуватися удвічі більшим кількістю цифр, ніж вихідне просте число [pic]. Замінивши тепер число [pic] на знайдене просте число [pic] і повторивши з цим новим [pic] все вищезазначені дії, можна побудувати ще більше просте число. Почавши з якогось простого числа, скажімо, записаного 10 десятковими цифрами (простоту може бути перевірити, наприклад, розподілом на маленькі табличні прості числа), і повторивши зазначену процедуру достатню кількість раз. можна побудувати прості числа потрібної величины.

Обговоримо тепер деякі теоретичні питання, що виникають у з перебуванням числа [pic], задовольняючого неравенствам [pic], і такої, що [pic] - просте число. Насамперед, відповідно до теоремі Дирихле, доведеною ще 1839 р., прогресія [pic], [pic] містить безліч простих чисел. Нас цікавлять прості числа, що лежать неподалік початку прогресії. Опенька найменшого простого вересня арифметичній прогресії отримали в 1944 р. Ю. У. Линником. Відповідна теорема стверджує, що найменше просте число в арифметичній прогресії [pic] не перевершує [pic], де [pic] - деяка досить велика абсолютна постоянная.

Отже, нині ніяких теоретичних гарантій для існування простого числа [pic] немає. Проте досвід обчислень на ЕОМ показує, що прості вересня арифметичній прогресії трапляються досить близько до її початку. Згадаємо у зв’язку гіпотезу про існуванні нескінченного кількості простих чисел [pic] з вимогою, що число [pic] також просте, т. е. простим вже є перший член прогрессии.

Дуже важливий у зв’язку з описуваних методом побудови простих чисел і питання відстань між сусідніми простими числами в арифметичній прогресії. Адже переконавшись, що з деякому [pic] число [pic] складене, можна таке значення [pic] взяти рівним [pic] і продовжує діяти таке інше, поки що не знайдено просте число [pic]. І особливо якщо відстань між сусідніми простими числами в прогресії велике, немає надії швидко побудувати багато [pic]. Перебір чисел [pic] доти, як ми наткнемося на просте число [pic] виявиться занадто довгим. У простому питанні відстані між сусідніми простими числами [pic] і [pic] в натуральному ряді доведено лише, що [pic], що, звісно, трохи зле нашим цілей. Разом про те існує так звана гіпотеза Крамера (1936 р.), що [pic], дає цілком прийнятну опеньку. Приблизно той самий результат випливає зі розширеній гіпотези Рімана. Обчислення на ЕОМ показують, що прості вересня арифметичних прогресіях розташовані досить плотно.

Як підсумку обговорення у цьому пункті підкреслимо таке: якщо прийняти на віру, що найменше просте число, і навіть відстань між сусідніми простими числами в прогресії [pic] при [pic] оцінюються величиною [pic], то описана схема побудови великих простих чисел має полиномиальную опеньку складності. З іншого боку, попри відсутність теоретичних опеньок часу роботи алгоритмів, отыскивающих прості числа в арифметичних прогресіях зі порівняно великий різницею, практично ці алгоритми працюють цілком задовільно. На звичайному персональному комп’ютері без особливих витрат часу будуються у такий спосіб прості числа порядку [pic].

Звісно, спосіб конструювання простих чисел від використання в схемою RSA може бути масовим, не бажаючи прості числа мали бути зацікавленими у якомусь сенсі добре распределёнными. Це вносить ряд додаткових ускладнень в роботу алгоритмов.

Нарешті, відзначимо, що є методи побудови великих простих чисел, використовують як прості делители [pic], а й делители чисел [pic]. У основі лежить використання послідовностей цілих чисел, які відповідають лінійним рекуррентным рівнянням різних порядків. Зазначимо, що послідовність [pic], члени якої є у формулюванні малої теореми Ферма, становить рішення рекуррентного рівняння першого порядку [pic].

3.3. Перевірка значної частини на простоту.

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

У пункті нам здається лише, що мені поставлено певна кількість [pic], наприклад, обраний випадково якомусь проміжку, і потрібно з’ясувати час його простоту, чи довести, що є складовим. Це завдання за полиномиальное кількість операцій вирішує вказаний у п. 3 алгоритм Міллера. Проте, справедливість отриманого з його допомогою затвердження залежить від недоведеною розширеній гіпотези Рімана. Якщо [pic] витримало випробування алгоритмом 5 для 100 різних значень параметра [pic], то, очевидно, можна стверджувати, що його є простим з імовірністю більшої, ніж [pic]. Ця ймовірність дуже близька до одиниці, проте усе ж таки залишає деяку тінь сумніву на простоті числа [pic]. Надалі у пункті вважатимемо, що заданий число [pic] є простим, а нам залишається лише довести это.

Нині відомі детермінований алгоритми різної складності як доказ простоти чисел. Ми зупинимося докладніше на одному їх, запропонованому 1983;го р. у роботі Адлемана. Померанця і Рамели. Аби довести простоти чи непростоты числа [pic] цей алгоритм вимагає [pic] арифметичних операцій. Тут [pic] - деяка позитивна абсолютна стала. Функція [pic] хоч і повільно, та все ж зростає зростанням [pic], тому алгоритм перестав бути полиномиальным. Але все-таки його практичні реалізації дозволяють досить швидко тестувати числа на простоту. Істотні удосконалення ОБСЄ і спрощення у початковий варіант алгоритму були внесені у роботах X. Ленстры й О. Коена. Ми називатимемо описуваний нижче алгоритм алгоритмом Адлемана — Ленстры.

У основі алгоритму лежить використання порівнянь типу малої теореми Ферма, але у кільцях цілих чисел кругових полів, т. е. полів. породжених над полем [pic] числами [pic] - корінням з 1. Нехай [pic] - просте нечётное число і [pic] — первообразный корінь по модулю [pic], т. е. утворюючий елемент мультипликативной групи поля [pic], яка пиклична. До кожного цілого числа [pic], не делящегося на [pic], можна визначити його індекс, [pic], званий також дискретним логарифмом, з допомогою порівняння [pic]. Розглянемо далі два простих числа [pic], [pic] з умовою, що [pic] ділиться на [pic], але з ділиться на [pic].

Наступна функція, певна на безлічі цілих чисел.

[pic] є характером по модулю [pic] і Порядок цього характеру дорівнює [pic]. Сумма.

[pic] називається сумою Гаусса. Формулируемая нижче теорема 3 є аналог малої теореми Ферма, вживаний у алгоритмі Адлемана — Ленстры.

Теорему 3. Нехай [pic] - парне просте число, [pic]. Тоді, у кільці [pic] виконується сравнение.

[pic].

Якщо за будь-яких числах [pic] порівняння з теореми 3 порушується. можна стверджувати, що [pic] складене число. Інакше, якщо порівняння виконується, воно дає деяку інформацію про можливі простих делителях числа [pic]. Зібравши таку інформацію щодо різноманітних [pic], зрештою вдається встановити, що [pic] має лише одне простий дільник і є простым.

Що стосується [pic] легко перевірити, що порівняння з теореми 3 рівносильне добре відомий в елементарної теорії чисел сравнению.

[pic], (13) де [pic] - так званий символ Якобі. Відомо також, що останнє порівняння виконується як простих [pic], але й будь-яких цілих [pic], взаємно простих з [pic]. Зауважимо також, що для обчислення символу Якобі існує швидкий алгоритм, заснований на законі взаємності Гаусса і. у сенсі, такий алгоритму Евкліда обчислення найбільшого загального дільника. Наступний приклад показує. як виконання кількох порівнянь типу (13) дає деяку інформацію про можливих простих делителях числа [pic].

Приклад (X. Ленстра). Нехай [pic] — натуральне число, [pic]. для якого виконані сравнения.

[pic], (14) крім того з певним цілим числом [pic] имеем.

[pic].

(15).

Як вказувалося, при простому [pic] порівняння (14) виконуються для будь-якого [pic], взаємно простого з [pic], а порівняння (15) означає, що [pic] є первообразный корінь по модулю [pic]. Кількість первообразных коренів одно [pic], т. е. дуже багато. Отже, число [pic] з умовою (15) при простому [pic] то, можливо знайдено досить швидко з допомогою випадкового вибору і наступного перевірки (15).

Доведемо, що з здійсненності (14−15) слід, кожен дільник [pic] числа [pic] задовольняє одного з сравнений.

[pic] чи [pic].

(16) Не зменшуючи спільності, вважатимуться, що [pic] - просте число. Введемо тепер позначення [pic], де [pic] і [pic] - нечётные числа. З (15) і порівняння [pic] слід, що [pic]. Далі, відповідно до (14). виконуються такі сравнения.

[pic], які означають (через те, що символ Якобі може рівнятися лише -1 чи +1), что.

[pic]. При [pic] це рівність означає, що [pic] при [pic], і, отже, [pic]. Якщо ж [pic], тут маємо [pic] і [pic]. Цим (16) доказано.

Інформація що така виходить у разі довільних простих чисел [pic] і [pic] з зазначеними вище свойствами.

Наведемо схему алгоритму Адлемана — Ленстры для перевірки простоти [pic]:

1) вибираються різні прості числа [pic] й різні прості нечётные [pic] такі, что.

1) кожному за [pic] все прості делители числа [pic] содержатся среди [pic] і [pic] не діляться на квадрат простого числа;

1) [pic]. 2) кожної пари вибраних чисел [pic], [pic] проводяться тести, подібні порівнянню з теореми 3. Якщо [pic] не задовольняє якомусь из этих тестів — воно складене. Інакше 3) визначається невідь що велике безліч чисел, із якими тільки і можуть бути можна порівняти прості делители [pic]. Як-от, кожен простий дільник [pic] числа [pic] повинен відповідати порівнянню вида.

[pic], [pic].

4) перевіряється, несе знайдене безліч делители [pic]. Якщо у своїй делители не виявлено, стверджується, що [pic] - простое число.

Якщо [pic] складене, воно обов’язково має простий дільник [pic], менший [pic], яка сама міститься серед можливих залишків. На цьому властивості грунтується застосування пункту 4) алгоритма.

Сума Якоби.

[pic] визначається обох характерів [pic] модулю [pic]. Якщо характери мають порядок [pic], то відповідна сума Якобі належить кільцю [pic]. Оскільки числа [pic], що у алгоритмі, порівняно невеликі, то обчислення з сумами Якобі виробляються в полях значно нижчою ступеня, ніж обчислення з сумами Гаусса. Це головне причина, через яку суми Якобі краще для обчислень. При [pic] виконується класичне соотношение.

[pic] що пов’язує суми Гаусса з сумами Якобі і що дозволяє переписати порівняння теореми 3 в термінах сум Якобі. Так. при [pic] і [pic] відповідне порівняння, справедливе простих [pic], відмінних 2,3,7, приймає вид.

[pic], де [pic] і [pic] - певний корінь кубічний з 1.

У 1984 р. внесли істотне вдосконалення в алгоритм, що дозволило позбутися вимоги неподільності чисел [pic] на квадрати простих чисел. Через війну, наприклад, обравши число [pic] й узявши [pic] рівним твору простих чисел [pic] з вимогою, що [pic] ділиться на [pic], одержимо [pic], що дозволяє доводити простоту чисел [pic], записуваних сотнею десяткових знаків. У цьому обчислення будуть проводитися в полях, породжених корінням з 1 ступенів 16, 9, 5 і 7.

Персональний комп’ютер з процесором Pentium-150. користуючись реалізацією цього алгоритму мовою UBASIC, довів простоту записываемого 65 десятковими знаками, більшого з простих чисел в прикладі Ривеста, Шаміра і Адлемана за 8 секунд. Порівняння цих 8 секунд і 17 років, потребовавшихся для розкладання на множники запропонованого в прикладі числа, звісно, впечатляет.

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

4. ПРАКТИЧНА РЕАЛІЗАЦІЯ АЛГОРИТМА.

Поданий вище алгоритм шифрування реалізували з допомогою інтегрованого пакета фірми Borland Delphi 5.0. Вибір даного мови програмування обгрунтований тим, що, він надає такі можливості, як объектно-ориентированный підхід до програмування, заснований на формах, інтеграція з програмуванням для Windows і компонентная технологія. Середовище візуального програмування Delphi 5 дозволяє собі з допомогою компонентного підходу при створенні додатків, швидко і здатні якісно «зібрати «інтерфейс програми розвитку й багато часу використати у складеного алгоритма.

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

Програмний продукт і двох додатків. Перше додаток є програму генерації ключів. Вона виводить все прості числа заданого діапазону, з яких вибираються числа [pic] і [pic]. Саме там перебувають відкритий і закритий ключі, які зберігаються на диску. Друге додаток, основна програма, виробляє з'єднання між двома комп’ютерами і, відправляючи повідомлення, шифрує його. Це додаток клієнт. Додаток сервер отримує повідомлення розшифровує його. Також на другий програмі міститься невеличка база даних абонентів, що зберігає у собі імена абонентів, IP адреси — й їх відкриті ключи.

4.1. Реалізовані алгоритмы.

У програмному продукті були реалізовані основні алгоритми схеми RSA. Функція ModDegree виробляє обчислення [pic]. Функція Prost знаходить все прості числа заданого діапазону. Функція Evklid реалізує алгоритм Евкліда і знаходить закритий ключ [pic]. Функція HOD виробляє обчислення найбільшого загального дільника і знаходить відкритий ключ [pic]. Перелічені вище функції представлені у додатку 1.

4.2. Аналіз результатов.

Результатом роботи створеної програми є зашифровані і розшифровані сообщения.

Для тестування програми використовувався приклад наведений в [11] [pic], [pic], [pic] і [pic]. Також [pic] і [pic].

5. ВЫВОДЫ.

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

5.1 Алгоритм.

Використаний алгоритм RSA має низку преимуществ:

1) алгоритм RSA є асиметричним, тобто. він полягає в поширенні відкритих ключів у мережі. Це дозволяє кільком користувачам обмінюватися інформацією, посылаемой по незахищеним каналам связи;

2) користувач сам може змінювати як числа [pic], [pic], і відкритий і закритий ключ на власний розсуд, потім він має поширити відкритий ключ у мережі. Це дозволяє домагатися користувачеві потрібної йому криптостойкости.

За всіх ці переваги даний алгоритм має суттєвий недолік — невисока швидкість роботи. Алгоритм RSA працює дуже в тисячу разів повільніше симетричного алгоритму DES.

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

5.2 Алгоритм і программа.

З опрацьованих даних, по побудованому алгоритму і створеному програмному продукту зроблено такі выводы:

1) побудований алгоритм, відповідно і створений його основі програмний продукт, повністю реалізує базові механізми схеми RSA і, в такий спосіб задовольняють основним поставленим задачам;

2) даний програмний продукт побудований за технології клиент/сервер і призначений зберігати конфіденційність передачі в сети.

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

ЗАКЛЮЧЕНИЕ

.

У межах даного дипломного проектування перед студентом Малышевым А. А. поставили завдання: з урахуванням алгоритму RSA для шифрування блоків даних, побудувати алгоритм і реалізувати програмний продукт для шифрування потоків данных.

У виконання дипломного проектування підготували принциповий алгоритм на вирішення поставленого завдання. Далі він був детализован і було реалізовано на ЕОМ. Наприкінці, провели аналіз отриманих результатів, і необхідні выводы.

За основу побудови алгоритму було прийнято алгоритм RSA для шифрування блоків даних, вивчена відповідна література за алгоритмом, і він побудований алгоритм і було реалізовано програмний продукт серед візуального програмування Delphi 5 під ОС типу Windows для IBM PC-совместимых компьютеров.

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

Наприкінці, після аналізу результатів було зроблено висновки, за якими алгоритм працює і застосуємо для поставленої задачи.

СПИСОК ВИКОРИСТАНИХ ИСТОЧНИКОВ.

1. Ященко У. У. Основні поняття криптографії // Математичне просвітництво. Сер. 3. № 2. 1998. З. 53−70. 2. Виноградов І. М. Основи теорії чисел. М.: Наука. 1972. 3. Карацуба А. А. Основи аналітичної теорії чисел. М.: Наука. 1983 р. 4. Батіг Д. Мистецтво програмування на ЕОМ. Т.2: Получисленные алгоритми. М.: Світ. 1977. 5. Ахо А. Хопкрофт Дж. Ульман Дж. Побудова і аналіз обчислювальних алгоритмів. М.: Світ. 1979. 6. Варновский М. П. Криптографія і теорія складності // Математичне просвітництво. Сер. 3. № 2. 1998. З. 71−86. 7. Василенко Про. М. Сучасні способи перевірки простоти чисел // Кібернетичний збірник, вип. 25. 1988. З. 162−188. 8. Прахар До. Розподіл простих чисел. М.: Світ. 1967. 9. Боревич З. И. Шафаревич І.Р. Теорія чисел. М.: Наука. 1964. 10. Кострикин А.І. Введення ЄІАС у алгебру. М.: Наука. 1977. 11. Брассар Дж. Сучасна криптология. Світ ПК. № 3. 1997.

ДОДАТОК 1.

Лістинг программы.

Модуль Key. pas Function Prost (n:integer):Boolean; var k: Boolean; i: integer; begin k:=true; if n2 then for i:=2 to trunc (sqrt (n))+1 do if (n/i)=trunc (n/i) then begin k:=False;

Break; end; Prost:=k; end; {________________________________________________________} Function Evklid (Num1,Num2:integer):integer; var r, q1, p1:array of integer; i, n, k:integer; begin if Num1>=Num2 then begin.

SetLength (r, 10); r[0]: =Num1; r[1]: =Num2; end else begin.

SetLength (r, 10); r[0]: =Num2; r[1]: =Num1; end; i:=1; while r[i]0 do begin inc (i); r[i]: =r[i-2] mod r[i-1]; end; n:=i-2; SetLength (q1,n+1); for i:=0 to n do q1[i]: =r[i] divx r[i+1]; SetLength (p1,n+2); p1[0]: =1; p1[1]: =q1[0]; k:=length (q1); if k>1 then for i:=2 to k do p1[i]: =q1[i-1]*p1[i-1]+p1[i-2]; Result:=trunc (power (-1,k-1))*p1[k-1] mod Num2; end; {________________________________________________________} Function HOD (Num1,Num2:integer):integer; var r: array of integer; i: integer; begin if Num1>=Num2 then begin.

SetLength (r, Num2); r[0]: =Num1; r[1]: =Num2; end else begin.

SetLength (r, Num1); r[0]: =Num2; r[1]: =Num1; end; i:=1; While r[i]0 do begin inc (i); r[i]: =r[i-2] mod r[i-1]; end; Result:=r[i-1]; end; {________________________________________________________} Function ModDegree (Num, Degree, n: integer):integer; var x: array of integer; i: integer; begin SetLength (x, n); x[1]: =Num mod n; for i:=2 to Degree do x[i]: =x[i-1]*Num mod n; Result:=x[Degree]; end;

ДОДАТОК 2.

Головна форма программы.

[pic].

ДОДАТОК 3.

Форма бази даних абонентов.

[pic].

ДОДАТОК 4.

Форма перебування простих чисел і генерації ключей.

[pic].