Тест числа на простоту

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

скачати

Тема: Алгоритм Міллера-Рабіна і мала теорема Ферма

У багатьох випадках потрібно з'ясувати, чи є велике число n простим. Наприклад, у системі відкритого ключа RSA і різних системах, заснованих на задачі дискретного логарифмування в кінцевих полях, нам потрібно знайти велику "випадкове" просте число.
Тест на простоту є критерій того, що число n не є простим. Якщо n "проходить" цей тест, то вона, можливо, просте число. Якщо воно "проходить" цілий набір тестів на простоту, то дуже ймовірно, що воно дійсно є простим. З іншого боку, якщо n не проходить хоча б одного тесту на простоту, то воно зовсім виразно є складовим. Однак при цьому залишається невирішеною важке завдання знаходження простих дільників числа n (задача факторизації). У загальному випадку для розкладання на множники великого числа, про який відомо, що воно складене (оскільки вона не пройшла тесту на простоту), потрібно приблизно величини. Надійність криптосистеми RSA грунтується на тому припущенні, що значно легше знайти два надзвичайно великих простих числа n і q, ніж, знаючи n = p * q, але не p або q, знайти дільники числа n.

Псевдопростие числа

Нехай n - велике непарне число, і ми хочемо визначити чи є n простим.
Теорема (Ферма). Якщо n - просте число, то згідно малої теореми Ферма для будь-якого такого b, що НОД (b, n) = 1, . (1)
Якщо n - не просте число, то (1) теж може виконуватися (хоча це малоймовірно).
Визначення. Якщо n - непарне складене число, b - ціле число, НОД (n, b) = 1, і (1) виконується, то n називається псевдопростим числом по підставі b.
Іншими словами, "псевдопростое" число - це число n, яке "претендує" бути простим, проходячи тест (1).
Приклад 1. число n = 91 - псевдопростое по підставі b = 3, так як . Однак, 91 не є псевдопростое число за основою 2, так як . Якщо б ми ще не знали, що 91 складене число, то співвідношення довело б нам це.
Сильно псевдопростое число. Розглянемо тепер ще один вид критеріїв простоти, що у певному сенсі навіть краще тесту Соловея - Штрассе, заснованого на визначенні псевдо простати за Ейлера. Це тест Міллера-Рабіна, заснований на вводиться нижче понятті "сильно псевдо простати". Припустимо, що n - велике непарне натуральне число і . Нехай, далі, n - псевдопростое по підставі b, тобто . Ідея критерію сильної псевдо простати така. Нехай , T - непарне. Якщо послідовно обчислювати , То при простому n першим елементом, відмінним від 1, повинен бути елемент
1, так як при простому n єдиними рішеннями порівняння є +1 і-1. практично дії виконуються "у зворотному напрямку". Вважаємо , T - непарне. Обчислюємо за модулем n. Якщо , Зводимо в квадрат за модулем n, отримуємо , Потім знову зводимо в квадрат і т.д. до тих пір, поки не отримаємо 1: . Тоді, якщо n - просте, попереднім числом має бути - 1, у противному випадку ми отримуємо доказ того, що n складене.
Визначення. Нехай n - непарне складене число і n-1 = 2 s t, t - непарне. Нехай . Якщо n і b задовольняють одну з умов:
1) ;
2) існує таке r, , Що
(2)
то n називає сильно псевдопростим по підставі b.
Тест Міллера-Рабіна. Припустимо, що ми хочемо визначити, є велика натуральне число n простим або складним. Уявімо n-1 у вигляді , T непарній, і виберемо випадкове ціле число b, 0 <b <n. Спочатку обчислюємо за модулем n. Якщо виходить , То висновком, що n пройшло тест (2) при даному b, і виробляємо новий випадковий вибір b. В іншому випадку зводимо в квадрат за модулем n, результат знову підносимо до квадрат за модулем n і продовжуємо так до тих пір, поки не отримаємо - 1. Якщо це відбуватиметься, то ми вважаємо, що n пройшло тест. Якщо ж це не відбуватися, тобто якщо ми отримуємо , У той час як , То n не проходити тест, і це доводить, що n - складене число. Якщо ми k раз випадково вибирали різні підстави b і n кожен раз проходило відповідний тест, то число n має не більше шансу бути складеним.
Застосування цих теорем можна побачити в наступних алгоритмах:

Алгоритм RSA

RSA (від прізвищ криптографів Rivest, Shamir і Adleman) криптографічний алгоритм шифрування з відкритим ключем і цифровим підписом.
Криптографічні системи з відкритим ключем використовують односпрямовані функції, які мають властивість:
Якщо х відомо, то f (x) обчислити відносно просто
Якщо відомо y = f (x), то для x немає простого шляху обчислення
Під одне спрямованістю розуміється практична неможливість обчислити зворотне значення, використовуючи сучасні обчислювальні засоби, за малий інтервал часу.
В основу криптографічної системи з відкритим ключем RSA ставиться завдання множення і розкладання складених чисел на прості множники, яка є обчислювально односпрямованої завданням.
У криптографічного системі з відкритим ключем у кожного абонента є відкритий ключем (public key) і секретний ключем (secret key). Кожен ключ частину інформації. У криптографічного системі RSA кожен ключ складається з пари цілих чисел. Кожен абонент набирає свій відкритий і секретний ключ самостійно. Секретні ключі секретними, відкриті ключі можна повідомляти. Відкритий і секретний ключі кожного абонента обміну повідомленнями взаємно зворотні.

Алгоритм створення відкритого і секретного ключів

Вибираються два випадкових простих числа p і q заданого розміру (наприклад, 512 бітів кожне).
Обчислюється їх добуток n = pq
Обчислюється значення функції Ейлера від числа n:


Вибирається ціле число e, взаємно просте зі значенням функції . e - прості числа, які містять невелику кількість одиничних бітів в двійковій запису. Наприклад, прості числа Ферма 17, 257, 65537.
Обчислюється число d, мультиплікативно зворотне до числа e по модулю , Т. е число, яке задовольняє порівнянні:
;
тобто , Де k будь-яке натуральне число (0, 1, 2 ...).
Пара G = (e, n) публікується в якості відкритого ключа RSA (RSA public key).
Пара N = (d, n) грає роль секретного ключа RSA (RSA secret key) і тримається в секреті.
Число n називається модулем, а числа e і d - відкритою й секретною експонентами, відповідно.
Припустимо абонент В хоче послати повідомлення абоненту В за комутаційного каналу.
Повідомленням є цілі числа лежать від 0 до n-1, .
Алгоритм шифрування:
Береться відкритий ключ (e, n) сторони A, вставляється відкритий текст L, передається шифроване повідомлення:

Алгоритм дешифрування:
Приймається зашифроване повідомлення С, для розшифровки повідомлення застосовується секретний ключ (d, n):

Цифровий підпис

Система RSA може використовуватися не тільки для шифрування, але і для цифрового підпису.
Припустимо, що абонентові A потрібно відправити абоненту B відповідь L 1, підтверджений цифровим підписом.
Алгоритм підпису
Взяти відкритий текст L 1, потім створюємо цифровий підпис wc допомогою секретного ключа (d, n).

Далі передаємо (L 1, w), яка складається з повідомлення і підпису.
Алгоритм перевірки справжності підпису
Прийняти (L 1, w), беремо відкритий ключ (e, n) абонента А, перевіряємо справжність підпису
підпис вірна
Оскільки цифровий підпис забезпечує як аутентифікацію автора повідомлення, так і підтвердження цілісності вмісту підписаного повідомлення, вона служить аналогом підпису, зробленого від руки в кінці рукописного документа.
Важлива властивість цифрового підпису полягає в тому, що її може перевірити кожен, хто має доступ до відкритого ключа її автора. Один з учасників обміну повідомленнями після перевірки справжності цифрового підпису може передати підписане повідомлення ще комусь, хто теж в змозі перевірити цей підпис.
Зауважимо, що підписане повідомлення L 1 не зашифровано. Воно пересилається в початковому вигляді і його вміст не захищено. Шляхом спільного застосування представлених вище схем шифрування і цифрового підпису в системі RSA можна створювати повідомлення, які будуть і зашифровані, і містити цифровий підпис. Для цього автор спочатку повинен додати до повідомлення свою цифровий підпис, а потім - зашифрувати вийшла в результаті пару (що складається з самого повідомлення та підписи до нього) за допомогою відкритого ключа належить одержувачу. Одержувач розшифровує отримане повідомлення за допомогою свого таємного ключа. Якщо проводити аналогію з пересилкою звичайних паперових документів, то цей процес схожий на те, як якщо б автор документа поставив під ним свій друк, а потім поклав його в паперовий конверт і запечатав, з тим щоб конверт був роздрукований тільки тією людиною, кому адресоване повідомлення .

RSA

Приклад
Спочатку потрібно згенерувати ключ
Вибираємо два простих ключа p = 13, q = 41
Обчислюємо модуль n = p * q = 13 * 41 = 533
Обчислюємо функцію Ейлера φ (n) = (p-1) * (q-1) = (13-1) * (41-1) = 480
Вибираємо відкритий показник е = 13
Обчислюємо секретний показник d = 37
Відкритий ключ (e, n) = (13, 533)
Секретний ключ (d, n) = (37, 533)
Шифрування
Вибираємо відкритий текст L = 4545
Обчислюємо шифротекст G (L) = L e mod n = 99
Розшифрування
Обчислюємо вихідне повідомлення
N (C) = С d mod n = 4545

Алгоритм Ель-Гамаля

Схема Ель-Гамаля (Elgamal) - криптосистема, запропонована в 1984 році. Схема Ель-Гамаля лежить в основі стандартів електронного цифрового підпису в США і Росії.
Генерація ключів
Генерується випадкове просте число p довжини n.
Вибирається довільне ціле число g, є первісною коренем за модулем p.
Вибирається випадкове число x з інтервалу (1, p), взаємно просте з p-1.
Обчислюється
Відкритим ключем є трійка (p, g, y), закритим ключем - число x.
Робота в режимі шифрування виглядає наступним чином:
шифрується повідомлення М
Вибирається випадкове секретне число k, взаємно просте з p - 1.
Обчислюється a = g k (mod p), b = y k M (mod p), де M - вихідне повідомлення.
Пара чисел (a, b) є шифротекст.
Довжина шіфротекста у схемі Ель-Гамаля довше вихідного повідомлення M вдвічі.
Розшифрування повідомлення здійснюється наступним чином
Знаючи закритий ключ x, вихідне повідомлення можна обчислити з шіфротекста (a, b) за формулою:

і

Режим підпису повідомлення

При роботі в режимі підпису передбачається наявність фіксованого хеш-функції h, значення якої лежать в інтервалі (1, p - 1).

Підпис повідомлень

Для підпису повідомлення M виконуються наступні операції:
Обчислюється дайджест повідомлення M: m = h (M).
Вибирається випадкове число 1 <k <p - 1 взаємно просте з p-1 і обчислюється .
За допомогою розширеного алгоритму Евкліда обчислюється число s, яке задовольняє порівнянні:

Підписом повідомлення M є пара (r, s).

Перевірка підпису

Знаючи відкритий ключ (p, g, y), підпис (r, s) повідомлення M перевіряється наступним чином:
Перевіряється здійснимість умов: 0 <r <p і 0 <s <p - 1. Якщо хоча б одна з них не виконується, то підпис вважається невірною.
Обчислюється дайджест m = h (M).
Підпис вважається вірною, якщо виконується порівняння:
.
DSS (Digital Signature Standard) цифровий підпис
Алгоритм:
вибирається просте число q приблизно в 160 біт (для цього використовуються генератор випадкових чисел і тест на простату)
вибирається інше просте число р, порівнянне з 1 по модулю q розміром приблизно в 512 біт
вибирається породжує елемент, для цього обчислюється для випадкового цілого g 0, якщо g ≠ 1, то він і буде породжує елементом
вибирається секретний ключ як випадкове ціле число х з діапазону 0 <x <q. В якості відкритого ключа береться .
Приклад. Нехай А хоче підписати повідомлення. Спочатку А приймає своєму ВІД хеш функцію і отримує ціле число h з діапазону 0 <h <q. Потім А вибирає випадкове ціле k з того ж діапазону і обчислює . Нехай r - найменший невід'ємних відрахування по модулю q останнього вираз. Значить, g k спочатку обчислюється за модулем р, а результат проводитись по меншій простому модулю q. Нарешті, А знаходить таке ціле s, що . Пара (r, s) відрахувань по модулю q є її підписом.
Щоб перевірити підпис, одержувач У обчислює і . Потім він обчислює . Якщо результат порівнянний з r по модулю q, то підпис вважається справжньою.

Література

1. Дж. Андерсон, Дискретна математика і комбінаторика, М.: Вільямс - 2003.
2. Н. Коблиц, Курс теорії чисел та криптографії, М.: наукове вид-во ТВП, 2001.
3. http://ru. wikipedia.org
Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Реферат
32.8кб. | скачати


Схожі роботи:
Перевірка великих чисел на простоту
Тест з гістології
Тест на продажність
Контрольна тест з культурології
Тест Малюнок сім`ї
Параметричний тест Гольдфельда-Квандта
Рисунковий тест як метод психоаналізу
Тест не тісто сама не підніметься
Рисунковий тест-як метод психоаналізу
© Усі права захищені
написати до нас