Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Лабораторная работа. Исследование ассиметричных систем шифрования
|
|
Исследование ассиметричных систем шифрования
Цель работы: исследование структуры алгоритма и методики практической реализации криптосистемы шифрования RSA и Эль-Гамаля.
1. Основные положения
Как известно, алгоритмы симметричного шифрования используют ключи относительно небольшой длины и поэтому могут быстро шифровать большие объёмы данных.
При использовании алгоритма симметричного шифрования отправитель и получатель применяют для шифрования и расшифрования данных один и тот же секретный ключ. Таким образом, алгоритмы симметричного шифрования основываются на предположении о том, что зашифрованное сообщение не сможет прочитать никто, кроме того кто обладает ключом для его расшифрования. При этом если ключ не скомпрометирован, то при расшифровании автоматически выполняется аутентификация отправителя, т.к. только он имеет ключ, с помощью которого можно зашифровать сообщение. Таким образом, для симметричных криптосистем актуальна проблема безопасного распределения симметричных секретных ключей. В связи с этим без эффективной организации защищенного распределения ключей использование обычной системы симметричного шифрования в вычислительных сетях практически невозможно.
Решением данной проблемы является использование асимметричных алгоритмов шифрования, называемых криптосистемами с открытым ключом. В них для зашифрования данных используется один ключ, называемый «открытым» а для расшифрования - другой называемый «закрытым или секретным». Следует иметь в виду, что ключ расшифрования не может быть определён из ключа зашифрования.
В асимметричных криптосистемах отрытый ключ и криптограмма могут быть отправлены по незащищённым каналам. Концепция таких систем основана на применении однонаправленных функций.
В качестве примера однонаправленной функции может служить целочисленное умножение. Прямая задача - вычисление произведения двух больших целых чисел р и q, п = p*q. Это относительно несложная задача для ЭВМ.
Обратная задача - факторизация или разложение на множители большого целого числа практически неразрешима при достаточно больших значениях п.
Например, если р ≈ q их произведение n ≈ 2664, то для разложения этого числа на множители потребуется 223 операций, что практически невозможно выполнить за приемлемое время на современных ЭВМ.
Другим примером однонаправленной функции является модульная экспонента с фиксированным основанием и модулем.
Например, если у = ах, то естественно можно записать, что х = loga(у).
Задача дискретного логарифмирования формулируется следующим образом. Для известных целых а, n, у следует найти такое число при котором ах (mod п) = у. Например, если а = 2664 и п = 2664 нахождение показателя степени х для известного у потребует около 10 26 операций, что также невозможно выполнить на современных ЭВМ.
В связи с тем, что в настоящее время не удалось доказать, что не существует эффективного алгоритма вычисления дискретного логарифма за приемлемое время, то модульная экспонента также условно отнесена к однонаправленным функциям.
Другим важным классом функций, используемых при построении криптосистем с открытым ключом являются, так называемые, однонаправленные функции с секретом. Функция относится к данному классу при условии, что она является однонаправленной и, кроме того, возможно эффективное вычисление обратной функции, если известен секрет.
В данной лабораторной работе исследуется криптосистема RSA, а также криптосистемы шифрования Эль Гамаля.
Схема алгоритма шифрования данных RSA
1) Определение открытого «е» и секретного «d» ключей
- Выбор двух взаимно простых больших чисел р и q
- Определение их произведения: п= р* q
- Определение функции Эйлера: φ (п) = (p-1)(q-1)
- Выбор открытого ключа e с учётом условий:
1 < е ≤ φ (п), НОД (е, φ (п)) = 1
- Определение секретного ключа d, удовлетворяющего условию
е * d ≡ (mod φ (п)), где d < n
2) Алгоритм шифрования сообщения М (действия отправителя)
- Разбивает исходный текст сообщения на блоки M1, M2,..., Mn, (Mi=0, 1, 2,..., п)
- Шифрует текст сообщения в виде последовательности блоков:
Ci = Mie (mod п)
- Отправляет получателю криптограмму: С1, С2,... Сn
- Получатель расшифровывает криптограмму с помощью секретного ключа d по формуле: Mi = Сid (mod п)
3) Процедуру шифрования данных рассмотрим на следующем примере (для простоты и удобства расчётов в данном примере использованы числа малой разрядности):
- Выбираем два простых числа р и q, p = 5, q =11;
- Определяем их произведение (модуль) n = p*q = 33;
- Вычисляем значение функции Эйлера φ (п) =(p-1)(q-1)
φ (п) = 2*10 = 20
- Выбираем случайным образом открытый ключ с учётом выполнения условий
1 < е ≤ φ (п) и НOД(е, φ (п)) = 1, е = 7;
- Вычисляем значение секретного ключа d, удовлетворяющего условию
е *d ≡ (mod φ (п)), 7*d ≡ 1 (mod 20); d = 3;
- Отправляем получателю пару чисел (п=33, е= 7). Представляем шифруемое сообщение M как последовательность целых чисел 312.
- Разбиваем исходное сообщение на блоки M1 = 3, M2 = 1, M3 = 2;
- Шифруем текст сообщения, представленный в виде после- довательности блоков: Mi = Сid (mod п)
С1 = 37 (mod 33) = 2187 (mod 33) = 9,
C2 = 17 (mod 33) = 1 (mod 33) =1,
C3 = 27 (mod 33) = 128(mod 33) =29.
- Отправляем криптограмму С1 = 9, С2 = 1, C3 = 29.
- Получатель расшифровывает криптограмму с помощью секретного ключа d по формуле: Mi = Сid (mod п)
М1 = 93 (mod 33) = 729 (mod 33) = 3
М2 = 13 (mod 33) = 1 (mod 33) = 1
М3 = 293 (mod 33) = 24389 (mod 33) = 2.
Полученная последовательность чисел 312 представляет собой исходное сообщение M.
Схема алгоритма шифрования данных Эль Гамаля
1) Определение открытого «y» и секретного «x» ключей
- Выбор двух взаимно простых больших чисел р и q, q < р
- Выбор значения секретного ключа х, х< р
- Определение значения открытого ключа у из выражения:
у = qx (mod р)
2) Алгоритм шифрования сообщении М
- Выбор случайного числа k, удовлетворяющего условию:
0 ≤ k < р-1 и НОД(k, р-1) = 1
- Определение значения а из выражения: а = qk(mod р)
- Определение значения b из выражения: b =ук М (mod р)
- Криптограмма С, состоящая из a и b, отправляется получателю. Получатель расшифровывает криптограмму с помощью выражения:
М аx = b (mod р)
3) Процедуру шифрования данных рассмотрим на следующем примере (для удобства расчётов в данном примере использованы числа малой разрядности):
- Выбираем два взаимно простых числа р = 11и q = 2;
- Выбираем значение секретного ключа x: (х < р), х = 8;
- Вычисляем значение открытого ключа у из выражения
у = qx (mod р) = 28 (mod 11) = 256 (mod 11) =3
- Выбираем значение открытого сообщения M = 5;
- Выбираем случайное число k = 9; НОД (9, 10) = 1;
- Определяем значение а из выражения:
a = qk (mod р) =29 (mod 11)=512 (mod 11) = 6;
- Определяем значение b из выражения:
b =уk М (mod р) = 39*5 (mod 11) = 98415 (mod 11) = 9.
Таким образом, получаем зашифрованное сообщение как (а, b) = (6, 9)и отправляем получателю.
- Получатель расшифровывает данный шифротекст, используя секретный ключ х и решая следующее сравнение:
М*а ≡ b (mod р) = 5*68 ≡ 9 (mod 11) = 8398080 ≡ 9 (mod 11)
Вычисленное значение сообщения M = 5 представляет собой заданное исходное сообщение.
2. Выполнение работы
Задачи лабораторной работы
1) Разработать приложения, в котором вводимый текст шифруется и дешифруется с помощью криптоалгоритма RSA и Эль-Гамаля.
2) Привести сравнительную характеристику алгоритма шифрования RSA и Эль-Гамаля. Описать их преимущества и недостатки.
3. Контрольные вопросы
1. Дайте определение асимметричного шифрования (с открытым ключом) и сформулируйте основные требования к нему.
2. Изложите схему организации секретной связи с использованием системы шифрования с открытым ключом.
3. Назовите и охарактеризуйте методы шифрования с открытым ключом.
4. Расскажите, каким образом можно организовать передачу цифровых сообщений, с помощью криптосистемы RSA. Приведите примеры.
5. Расскажите, каким образом можно организовать передачу цифровых сообщений, с помощью криптосистемы Эль-Гамаля. Приведите примеры.
6. Сравните наиболее распространенные стандарты шифрования кроме RSA и эль-Гамаля.
|