Тема: Алгоритм Міллера-Рабіна і мала теорема Ферма
У багатьох випадках потрібно з'ясувати, чи є велике число n простим. Наприклад, у системі відкритого ключа RSA і різних системах, заснованих на задачі дискретного логарифмування в кінцевих полях, нам потрібно знайти велику "випадкове" просте число.Тест на простоту є критерій того, що число n не є простим. Якщо n "проходить" цей тест, то вона, можливо, просте число. Якщо воно "проходить" цілий набір тестів на простоту, то дуже ймовірно, що воно дійсно є простим. З іншого боку, якщо n не проходить хоча б одного тесту на простоту, то воно зовсім виразно є складовим. Однак при цьому залишається невирішеною важке завдання знаходження простих дільників числа n (задача факторизації). У загальному випадку для розкладання на множники великого числа, про який відомо, що воно складене (оскільки вона не пройшла тесту на простоту), потрібно приблизно величини. Надійність криптосистеми RSA грунтується на тому припущенні, що значно легше знайти два надзвичайно великих простих числа n і q, ніж, знаючи n = p * q, але не p або q, знайти дільники числа n.
Псевдопростие числа
Нехай n - велике непарне число, і ми хочемо визначити чи є n простим.Теорема (Ферма). Якщо n - просте число, то згідно малої теореми Ферма для будь-якого такого b, що НОД (b, n) = 1,
Якщо n - не просте число, то (1) теж може виконуватися (хоча це малоймовірно).
Визначення. Якщо n - непарне складене число, b - ціле число, НОД (n, b) = 1, і (1) виконується, то n називається псевдопростим числом по підставі b.
Іншими словами, "псевдопростое" число - це число n, яке "претендує" бути простим, проходячи тест (1).
Приклад 1. число n = 91 - псевдопростое по підставі b = 3, так як
Сильно псевдопростое число. Розглянемо тепер ще один вид критеріїв простоти, що у певному сенсі навіть краще тесту Соловея - Штрассе, заснованого на визначенні псевдо простати за Ейлера. Це тест Міллера-Рабіна, заснований на вводиться нижче понятті "сильно псевдо простати". Припустимо, що n - велике непарне натуральне число і
1, так як при простому n єдиними рішеннями порівняння
Визначення. Нехай n - непарне складене число і n-1 = 2 s t, t - непарне. Нехай
1)
2) існує таке r,
то n називає сильно псевдопростим по підставі b.
Тест Міллера-Рабіна. Припустимо, що ми хочемо визначити, є велика натуральне число n простим або складним. Уявімо n-1 у вигляді
Застосування цих теорем можна побачити в наступних алгоритмах:
Алгоритм RSA
RSA (від прізвищ криптографів Rivest, Shamir і Adleman) криптографічний алгоритм шифрування з відкритим ключем і цифровим підписом.Криптографічні системи з відкритим ключем використовують односпрямовані функції, які мають властивість:
Якщо х відомо, то f (x) обчислити відносно просто
Якщо відомо y = f (x), то для x немає простого шляху обчислення
Під одне спрямованістю розуміється практична неможливість обчислити зворотне значення, використовуючи сучасні обчислювальні засоби, за малий інтервал часу.
В основу криптографічної системи з відкритим ключем RSA ставиться завдання множення і розкладання складених чисел на прості множники, яка є обчислювально односпрямованої завданням.
У криптографічного системі з відкритим ключем у кожного абонента є відкритий ключем (public key) і секретний ключем (secret key). Кожен ключ частину інформації. У криптографічного системі RSA кожен ключ складається з пари цілих чисел. Кожен абонент набирає свій відкритий і секретний ключ самостійно. Секретні ключі секретними, відкриті ключі можна повідомляти. Відкритий і секретний ключі кожного абонента обміну повідомленнями взаємно зворотні.
Алгоритм створення відкритого і секретного ключів
Вибираються два випадкових простих числа p і q заданого розміру (наприклад, 512 бітів кожне).Обчислюється їх добуток n = pq
Обчислюється значення функції Ейлера від числа n:
Вибирається ціле число e, взаємно просте зі значенням функції
Обчислюється число d, мультиплікативно зворотне до числа e по модулю
тобто
Пара 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 біт
вибирається породжує елемент, для цього обчислюється
вибирається секретний ключ як випадкове ціле число х з діапазону 0 <x <q. В якості відкритого ключа береться
Приклад. Нехай А хоче підписати повідомлення. Спочатку А приймає своєму ВІД хеш функцію і отримує ціле число h з діапазону 0 <h <q. Потім А вибирає випадкове ціле k з того ж діапазону і обчислює
Щоб перевірити підпис, одержувач У обчислює
Література
1. Дж. Андерсон, Дискретна математика і комбінаторика, М.: Вільямс - 2003.2. Н. Коблиц, Курс теорії чисел та криптографії, М.: наукове вид-во ТВП, 2001.
3. http://ru. wikipedia.org