Головна Головна -> Реферати українською -> Інформатика, комп'ютери, програмування -> Асиметричні алгоритми

Асиметричні алгоритми

Назва:
Асиметричні алгоритми
Тип:
Реферат
Мова:
Українська
Розмiр:
22,32 KB
Завантажень:
260
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8  9  10  11  12  13 
Асиметричні алгоритми
У 1976 р. відкрито новий етап розвитку криптографії. Для новітньої криптографії характерна поява принципово нових криптографічних задач, а також принципово нових методів розв'язування класичних задач. Тому часто говорять про революцію в галузі криптографії. Поступ, що відбувся, пов'язаний з іменами американських математиків Вайтфілда Діффі та Мартіна Хелмана, а також Ральфа Меркле, які розвинули ідеологію відкритого ключа.
Завдяки цьому з'явився цілком новий клас криптографічних систем, які назива-ють асиметричними, або двоключовими, системами. У цих системах для шифрування й дешифрування використовують різні ключі, пов'язані між собою певною залежністю. Ця залежність є такою, що визначити один ключ, знаючи інший, з обчислювального по-гляду дуже важко. Один з ключів може бути доступним для всіх, і в цьому випадку нема проблеми отримання загального ключа для зв'язку. Тому такі системи називають також криптосистемами з відкритим ключем.
Криптосистему з відкритим ключем характеризують три процедури: утворення
ключів, шифрування й дешифрування. Алгоритм утворення ключів є відкритим, кожен може подати йому на вхід відповідні дані й отримати пару ключів. Один з ключів публікують і називають відкритим, а інший, що зберігається в таємниці, називають таємним ключем. Алгоритми шифрування й дешифрування є такими, що коли до будь-якого відкритого тексту послідовно застосовують перший з них, а потім другий, то отримують початковий відкритий текст.
Теоретичні основи
Нехай n - довільне натуральне число, а х- ціле число. Для цілого числа х є Z
через х mod n позначимо залишок від ділення числа х на число n. Запишемо х?у(mod n), якщо х mod n ? y mod n, і казатимемо, що х і у конгруентні (порівняльні) за модулем n. Наприклад, 100 mod 11?l, -8 mod 10 ? 2. Множину (0, 1, ..., n- 1) усіх можливих невід'ємних залишків за модулем п позначимо через Zn. Уважаємо, що х є оберненим елементом до у за модулем п, якщо х?у (mod n). У цій ситуації запишемо x = y-1(mod n). Множину елементів із Zn, для яких існують обернені в Zn, позначимо через Z*n і назвемо ці елементи оборотними за модулем п. У множині Zn можна виконувати дві операції: х є сумою елементів у і z за модулем п, якщо у + z ? x(mod n); х є добутком елементів y і z за модулем п, якщо yz?x(mod n). Якщо п є складеним числом: n= pq, то добуток pq дорівнює нулю в Zn: pq ? 0(mod n). Позначення а Р b означає, що а ділить b. Для цілих чисел а і b через НСД(a, b) позначимо їхній найбільший спільний дільник - найбільше з-поміж таких с, що одно-часно с Р а і с Р b (хоча б одне із чисел а і b вважають відмінним від нуля). Найменше натуральне число, яке ділиться на кожне із невід'ємних цілих чисел р1,р2,…,pk, нази-вають їхнім найменшим спільним кратним і позначають
НСК(ри р2,..., рк).
Твердження 3.1. Такі умови еквівалентні:
1)х ? y(mod n);
2) х - у + kn, де k ціле число;
3)n(х-у).
Конгруенція має такі властивості:
якщо x1 ? y1(mod п) і х2 ? y2(mod n), то x1 + х2 ? y1 + y2(mod n);
якщо x1 ? y1(mod n) i x2 = y2(mod п), то х1 х2 = у1 y2(mod n).
Приклад 3.1. Довести, що число 73524 ділиться на 11.
Очевидно, що 10?-l(mod II). На підставі наведених вище властивостей конгру-енції отримуємо 100?l(mod 11), 1000 ? -1 (mod 11), 10000?l(mod 11). Звідси 20?-2(mod 11), 500?5(mod 11), 3000 ? -3(mod 11), 70000?7(mod 11). Послідовне дода-вання дає 73520?7(mod 11). Тоді 73520 + 4 ?1 + 4 ?0(mod 11).
Розглянемо алгоритм Евкліда (III ст. до н. є.) отримання найбільшого спільного дільника натуральних чисел а і b.
Алгоритм опирається на вирази
НСД(а, b) = НСД(a, a mod b) для a>b; (3.1)
НСД(а, 0) = а. (3.2)
Приклад 3. 2. Знайти НСД(211, 79). Послідовно застосуємо рівність (3.1), доки не отримаємо (3.2):
Отже, НСД(211, 79) = НСД(79, 53) = НСД(53, 26) = НСД(26, 1) = НСД(1, 0) = 1. У загальному випадку виконання алгоритму Евкліда можна описати так.
Кількість т кроків алгоритму Евкліда визначена нерівністю т < 2 log 2 b + 1. Під час виконання алгоритму Евкліда можна знайти такі цілі числа х, у, які задо-вольняють діофантове рівняння ах - by = 1, де а і b взаємно прості: НСД(а, Ь) = 1, а>0, b > 0.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8  9  10  11  12  13 



Реферат на тему: Асиметричні алгоритми

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок