Криптосистема Ель-Гамаля
Криптосистема RSA
Широко відома криптографічна система RSA, що запропонована в 1978 році, є асиметричної криптосистемой, основаної на однобічній функції з лазівкою, в якості якої обрана степенева функція у кільці лишків цілих чисел по складеному (біпростому) модулю . Стійкість системи основана на складності задачі факторизации великих біпростих чисел.
Криптосистема RSA на кожному такті шифрування перетворює двійковий блок відкритого тексту довжини , що розглядається як ціле число, за допомогою піднесення до степеню за модулем : . Показник степеня і модуль є елементами відкритого ключа.
Лазівка забезпечується за рахунок секретного ключа , побудованого таким чином, що для усіх виконується співвідношення .
Побудову криптосистеми забезпечує одержувач повідомлень.
Спочатку випадковим образом вибираються два різних великих простих числа і . Обрані прості числа повинні задовільняти деяки додаткові умови. Потім обчислюється модуль , функція Эйлера від модуля , а також вибирається випадкове число , взаємно просте з .
Секретний ключ будується за допомогою розширеного алгоритму Евкліда, як число , що задовольняє порівнянню . Після цього всі дані, крім , включаючи дані проміжних обчислень, знищуються. Пара опубліковується як відкритий ключ.
Розшифрування забезпечується тим, що для з теореми Ейлера випливає і, крім того, для інших значень співвідношення також має місце, внаслідок властивостей модуля виду .
Розглянемо приклад побудови (навчальної) криптосистеми RSA.
1. , .
2.
3.
4.
5.
Відкритий ключ - .
Зашифруємо повідомлення з трьох блоків: 3,1,2.
, , .
Для розшифрування піднесемо кожен блок до степеня по модулі 33:
, , .
Секретний ключ для навчальної системи легко знайти перебором. На практиці це нездійсненно, тому що реальний розмір модуля (довжина бітового представлення) знаходиться в діапазоні від 512 до 4096 битов.
Криптосистема Ель-Гамаля є асиметричною. Для побудови пари ключів вибирається велике просте число і два псевдослучайных числа, менших . Одне з них, , повинно бути елементом великого порядку за модулем , скажемо, первісним коренем. Друге число, , вибирається як секретний ключ. Припускається, що повідомлення – лишки за модулем .
Відкритим ключем є трійка чисел .
Дискретна експонента поводиться як однобічна функція, але не як однобічна функція з лазівкою.
Тому для кожного повідомлення формуються додаткові дані, що грають роль лазівки для конкретного сеансу шифрування.
Для зашифрування повідомлення вибирається псевдовипадкове число (рандомізатор, разовий ключ) з умовою НОД . Рандомізаторы не повинні повторюватися і повинні утримуватися в секреті.
Потім обчислюються числа - лазівка і - шифротекст. Криптограмою є пара блоків даних: .
Для розшифрування досить одержати співмножник , що можна зробити за допомогою секретного ключа, обчисливши значення .
Дійсно, , тому .