 |
|
Схема шифрования с открытым ключом
Пусть K — пространство ключей, а e и d — ключи шифрования и расшифрования соответственно. Ee — функция шифрования для произвольного ключа e 
K, такая что:
Ee(m) = c
Здесь c C, где C — пространство шифротекстов, а m M, где M — пространство сообщений.
Dd — функция расшифрования, с помощью которой можно найти исходное сообщение m, зная шифротекст c :
Dd(c) = m
{Ee: e K} — набор шифрования, а {Dd: d K} — соответствующий набор для расшифрования. Каждая пара (E,D) имеет свойство: зная Ee, невозможно решить уравнение Ee(m) = c, то есть для данного произвольного шифротекста c C, невозможно найти сообщение m M. Это значит, что по данному e невозможно определить соответствующий ключ расшифрования d. Ee является односторонней функцией, а d — лазейкой.
Ниже показана схема передачи информации лицом А лицу В. Они могут быть как физическими лицами, так и организациями и так далее. Но для более лёгкого восприятия принято участников передачи отождествлять с людьми, чаще всего именуемыми Алиса и Боб. Участника, который стремится перехватить и расшифровать сообщения Алисы и Боба, чаще всего называют Евой.
1. Боб выбирает пару (e,d) и шлёт ключ шифрования e (открытый ключ) Алисе по открытому каналу, а ключ расшифрования d (закрытый ключ) защищён и секретен (он не должен передаваться по открытому каналу).
2. Чтобы послать сообщение m Бобу, Алиса применяет функцию шифрования, определённую открытым ключом e: Ee(m) = c, c — полученный шифротекст.
3. Боб расшифровывает шифротекст c, применяя обратное преобразование Dd, однозначно определённое значением d.
Виды ассиметричных шифров:
1. Криптосистема RSA
Название криптосистемы образовано из первых букв фамилий предложивших ее авторов (Rivest R., Shamir A., Adleman L.).
Система относится к блочным экспоненциальным системам, так как каждый блок М открытого текста рассматривается как целое число в интервале (0,..., n-1) и преобразуется в блок С следующим открытым преобразованием
C = E (e,n) (M) = Me (mod n),
где E(e,n) - преобразование, а (e,n) - ключ зашифрования.
При расшифровании блок открытого текста М восстанавливается таким же преобразованием, но с другим показателем степени.
M = D (d,n) (C) = Cd (mod n),
где D(d,n) - преобразование, а (d,n) - ключ расшифрования.
Числа e и d связаны с n определенной зависимостью и существуют рекомендации по выбору ключевых элементов на основе простых чисел. Если взять два простых числа p и g, определить n = p х q, то можно определить пару чисел e и d, удовлетворяющих заданным условиям. Если сделать открытыми числа e и n, а ключ d (и обязательно p и g) держать в секрете - то предложенная система является RSA-криптосистемой открытого шифрования. Очевидно, ее стойкость определяется сложностью операции извлечения из С корня степени е по модулю n.
Рассмотрим основные этапы реализации алгоритма RSA.
1. Отправитель вычисляет n = p х q и M=(p-1)(q-1).
2. Затем он выбирает случайное целое число e, взаимно простое с М и вычисляет d, удовлетворяющее условию
ed = 1 (mod M).
Напомним, что два числа являются взаимно простыми, если их HOD =1. Числа а и b имеют HOD d, если d делит и а и b и максимальный среди таких чисел.
3. После этого он публикует е и n как свой открытый ключ шифрования, сохраняя d, как закрытый (секретный) ключ.
4. Рассмотрим теперь числа e и d. Предположим, что мы знаем одно из них и знаем соотношение, которым они связаны. Мы могли бы легко вычислить второе число, однако мы не знаем чисел p и q. Следовательно можно одно из чисел подарить кому-нибудь вместе с n и попросить его посылать нам сообщения следующим образом.
5. Сообщение представить как векторы (блоки) длины l
X= (x1,x2...,xl)
0<xi< M;
6. Каждое xi возвести в степень e по mod n.
7. Прислать нам Y=(x1e (mod n), x2e (mod n),...,xle (mod n)).
Обозначим t=yi =хie (mod n) и рассмотрим расшифрование полученной информации. Для этого возведем полученное число t в степень второго числа пары - d:
R=td(mod n) = xe (mod n)d(mod n) = xed (mod n).
В соответствие с п.2 соотношение ed=1(mod M). а это означает, что ed-1 делится нацело на (p-1)(q-1), т.е. ed=1+a(p-1)(q-1), где а - целое число.
Утверждается, что хed(mod n) =x.
Действительно, xed(mod n) = x1+a(p-1)(q-1) (mod n)
Учитывая,что
xp-1 = 1 mod p, xq-1 = 1 mod q (эти соотношения доказываются как малая теорема Ферма, например в /10/) получим
x(p-1)(q-1) = 1(mod pq)
x1+a(p-1) (g-1)(mod n) = x, т.к.
xa(p-1) (q-1) = 1(mod pq), из-за того,
что x(p-1) (q-1) = 1(mod pq),
x mod n = x, так как x<M.
Что и требовалось доказать.
Пример:
Установим p=3, q=7. Тогда n=p*q=21. Выбираем d как 5. Из формулы (e*5) mod 12=1 вычисляем e=17. Открытый ключ 17, 21, секретный - 5, 21.
Зашифруем последовательность «12345»:
C(1)= 117 mod 21= 1
C(2)= 217 mod 21 =11
C(3)= 317 mod 21= 12
C(4)= 417 mod 21= 16
C(5)= 517 mod 21= 17
Криптотекст - 1 11 12 16 17.
Проверим расшифровкой:
M(1)= 15 mod 21= 1
M(2)= 115 mod 21= 2
M(3)= 125 mod 21= 3
M(4)= 165 mod 21= 4
M(5)= 175 mod 21= 5 Как видим, результат совпал.
2. Цифровая (электронная) подпись
Одним из основных применений криптосистем с открытым ключом является их использование при создании так называемой цифровой или электронной подписи. Впервые идея цифровой подписи была высказана в работе Диффи и Хеллмана.
Один из вариантов изложения принципа электронной подписи выглядит так. Требуется, чтобы существовали взаимообратные преобразования Ek и Dk, для которых выполняется
Ek[Dk(M)] =M для любого открытого текста М.
Тогда Dk считается секретным преобразованием, с помощью которого пользователь может зашифровать исходный текст C=Dk(M) и послать это значение в качестве цифровой подписи к сообщению М другим пользователям, обладающим знанием открытого преобразования Ek. Определение Dk при знании Ek должно быть вычислительно неразрешимой задачей.
Система RSA широко используется в системе цифровой подписи, так как ее преобразования обладают всеми необходимыми свойствами. Использование цифровой подписи предполагает существование двух процедур: подписывания и проверки.
Процедура подписывания сообщения M – это возведение числа M в степень d по mod n:
S = Md (mod n).
Число S есть цифровая подпись, которую может выработать только владелец секретного ключа.
Процедура проверки подписи S , соответствующей сообщению M – это возведение числа S в целую степень e по mod n:
M’= Se (mod n).
Если M’= M, то сообщение M признается подписанным пользователем, который предоставил ранее открытый ключ e.
В реализации для сокращения времени подписывания и размера подписи, в качестве источника для подписи служит не само исходное сообщение М (произвольной длины), а некоторая производная от него (фиксированной длины). Для ее получения используется общеизвестная функция Н, отображающая любое сообщение М в сообщение Н(М) фиксированного малого размера, которое далее преобразуется в цифровую подпись. Функция Н называется функцией хеширования (hash function), в простейшем случае это может быть, например, функция вычисления контрольной суммы текста сообщения по модулю 232, размер приведенного для электронного подписывания сообщения тогда будет равен 32 двоичным разрядам (четырем байтам).
Список литературы:
1. Составитель Л.К.Бабенко методическое пособие,Введение в специальность «Организация и технология защиты информации». Таганрог: Изд-во ТРТУ, 1999.54с.
2. А. П. Алфёров, А. Ю. Зубов, А. С. Кузьмин, А. В. Черёмушкин «Основы криптографии».
3. Ященко В.В.
4. Молдовян А.А., молдовян Н.А., Советов Б.Я. «Криптография».- СПб.: Издательство «Лань», 2001.- 224 с.