Криптосистема Ель-Гамаля

Криптосистема RSA

Широко відома криптографічна система RSA, що запропонована в 1978 році, є асиметричної криптосистемой, основаної на однобічній функції з лазівкою, в якості якої обрана степенева функція у кільці лишків цілих чисел по складеному (біпростому) модулю. Стійкість системи основана на складності задачі факторизации великих біпростих чисел.

Криптосистема RSA на кожному такті шифрування перетворює двійковий блок відкритого тексту довжини, що розглядається як ціле число, за допомогою піднесення до степеню за модулем:. Показник степеня і модуль є елементами відкритого ключа.

Лазівка забезпечується за рахунок секретного ключа, побудованого таким чином, що для усіх виконується співвідношення.

Побудову криптосистеми забезпечує одержувач повідомлень.

Спочатку випадковим образом вибираються два різних великих простих числа і. Обрані прості числа повинні задовільняти деяки додаткові умови. Потім обчислюється модуль, функція Эйлера від модуля, а також вибирається випадкове число, взаємно просте з.

Секретний ключ будується за допомогою розширеного алгоритму Евкліда, як число, що задовольняє порівнянню. Після цього всі дані, крім, включаючи дані проміжних обчислень, знищуються. Пара опубліковується як відкритий ключ.

Розшифрування забезпечується тим, що для з теореми Ейлера випливає і, крім того, для інших значень співвідношення також має місце, внаслідок властивостей модуля виду.

Розглянемо приклад побудови (навчальної) криптосистеми RSA.

1.,.

2.

3.

4.

5.

Відкритий ключ -.

Зашифруємо повідомлення з трьох блоків: 3,1,2.

,,.

Для розшифрування піднесемо кожен блок до степеня по модулі 33:

,,.

Секретний ключ для навчальної системи легко знайти перебором. На практиці це нездійсненно, тому що реальний розмір модуля (довжина бітового представлення) знаходиться в діапазоні від 512 до 4096 битов.

Криптосистема Ель-Гамаля є асиметричною. Для побудови пари ключів вибирається велике просте число і два псевдослучайных числа, менших. Одне з них,, повинно бути елементом великого порядку за модулем, скажемо, первісним коренем. Друге число,, вибирається як секретний ключ. Припускається, що повідомлення – лишки за модулем.

Відкритим ключем є трійка чисел.

Дискретна експонента поводиться як однобічна функція, але не як однобічна функція з лазівкою.

Тому для кожного повідомлення формуються додаткові дані, що грають роль лазівки для конкретного сеансу шифрування.

Для зашифрування повідомлення вибирається псевдовипадкове число (рандомізатор, разовий ключ) з умовою НОД. Рандомізаторы не повинні повторюватися і повинні утримуватися в секреті.

Потім обчислюються числа - лазівка і - шифротекст. Криптограмою є пара блоків даних:.

Для розшифрування досить одержати співмножник, що можна зробити за допомогою секретного ключа, обчисливши значення.

Дійсно,, тому.

Дата добавления: 2014-10-15