1) симетричне шифрування <# «justify"> На даний момент асиметричне шифрування на основі відкритого ключа RSA (розшифровується, як Rivest, Shamir and Aldeman - творці алгоритму) використовує більшість продуктів на ринку інформаційної безпеки.
Його крипостійкість грунтується на складності розкладання на множники великих чисел, а саме - на винятковій складності завдання визначити секретний ключ на підставі відкритого, так як для цього буде потрібно вирішити завдання про існування дільників цілого числа. Найбільш криптостійкі системи використовують 1024-бітові і великі числа.
3. Алгоритм RSA шифрування
). Вибирають взаємно прості числа p і q.
). За ним обчислюють
;
- це перша частина ключа.
). Визначають - функцію Ейлера від аргументу n, тобто кількість чисел, взаємно простих з n і менших n. Легко бачити, що в даному випадку
.
). Вибирають число e - взаємно просте з, e - друга частина відкритого ключа.
Відкритий ключ - пара чисел (n, e).
). Обчислюють число d таке, що
,
де k - ціле число.
Число d - секретна частина ключа.
6). Шифрування здійснюється за схемою:
.
). Дешифрування виконується за схемою (рис. 3.1):
.
Прості дільники p і q можна або знищити, або зберегти разом з секретним ключем.
Якби існували ефективні методи розкладання на співмножники, то, розклавши n на множники p і q, можна було б отримати секретний ключ d.
Таким чином, надійність криптосистеми RSA заснована на важковирішуваною - практично нерозв'язною - завданню розкладання n на співмножники, так як в даний час ефективного способу пошуку співмножників не існує.
У розглянутому прикладі всі вхідні числа невеликі. На практиці числа p і q можуть містити близько 50 - 100 значущих цифр у десяткового запису. Отже, при реалізації методу RSA необхідно залучати кошти «довгої арифметики».
Оскільки генерація ключів відбувається значно рідше операцій, що реалізують шифрування, розшифрування, а також створення і перевірку цифрового підпису, задача обчислення дешифрування, наприклад:
представляє основну обчислювальну складність.
Це завдання може бути вирішена за допомогою алгоритму швидкого зведення в ступінь <# «justify"> 4. Подання довгих чисел
Для більшості додатків надаються процесором базових типів цілком вистачає. Однак зустрічається багато завдань, вихідні дані яких занадто великі (наприклад, алгоритм RSA). Число з 1000 цифр не поміститься ні в один регістр. Тому комп'ютерне подання таких чисел і операції над ними доводиться реалізовувати самостійно. При цьому час виконання зовнішнього алгоритму, що використовує такі числа, дуже сильно залежить від ефективності їх реалізації.
Один з варіантів зберігання довгих чисел можна реалізувати у вигляді масиву цілих чисел, де кожен елемент - це одна цифра числа в b -й системі числення.
Цифри будуть зберігатися в масиві в такому порядку, що спочатку йдуть найменш значущі цифри (тобто, наприклад, одиниц...
