Лекции ЗИ_Э. Самарский государственный архитектурностроительный университет
 Скачать 1.6 Mb.
|
4.5. Асимметричные криптосистемы4.5.1. Принципы асимметричного шифрованияНаряду с вычислительной простотой и интуитивной понятностью симметричных криптосистем, они обладают рядом серьезных недостатков. К основным недостаткам симметричных криптосистем относят проблему распространения симметричных ключей и проблему их хранения [2]. При использовании симметричных криптосистем для шифрования информации между пользователями криптографической сети необходимо обеспечить безопасную передачу ключей шифрования между всеми доверенными пользователями (участниками криптографического обмена). При этом передача ключа шифрования обязательно должна осуществляться по закрытому каналу, так как перехват злоумышленником данного ключа ведет к компрометации всей криптографической сети. В связи с этим, использование симметричных алгоритмов предполагает наличие взаимного доверия сторон. Вероятность компрометации ключей тем выше, чем большее количество пользователей входит в криптографическую сеть. Это является большим недостатком симметричных криптосистем. В отличие от симметричных криптосистем, асимметричные криптосистемы используют различные ключи для шифрования и дешифрования сообщений. Ключи в асимметричных криптосистемах всегда генерируются парами и состоят из двух частей – открытого ключа (ОК) и секретного ключа (СК).
Открытый ключ используется для шифрования информации, является доступным для всех пользователей и может быть опубликован в общедоступном месте для использования всеми пользователями криптографической сети. Дешифрование информации с помощью открытого ключа невозможно. Секретный ключ является закрытым и не может быть восстановлен злоумышленником из открытого ключа. Этот ключ используется для дешифрования информации и хранится только у одного пользователя – сгенерировавшего ключевую пару. Функциональная схема взаимодействия участников асимметричного криптографического обмена представлена на рис. 4.5. В данной схеме участвует получатель секретного сообщения А и отправитель секретного сообщения B. ОКА – открытый ключ пользователя А, СКА – секретный ключ пользователя А. Ключевая пара (ОКА, СКА) сгенерирована на стороне получателя А, после чего открытый ключ данной пары ОКА отправляется по открытому каналу пользователю B. Предполагается, что злоумышленнику также известен открытый ключ ОКА.  Рис. 4.5. Функциональная схема асимметричной криптосистемы Отправитель B, зная открытый ключ получателя А, может зашифровать на данном ключе открытый текст и переслать его пользователю А. Пользователь А с помощью своего секретного ключа, соответствующего ОКА, может дешифровать присланное пользователем B сообщение. Злоумышленник, зная ОКА и закрытый текст, не может получить доступ не к СКА, не к открытому тексту. Рис 4.5 отражает только одностороннюю схему взаимодействия в рамках асимметричных криптосистем. Для реализации двустороннего обмена необходима реализация следующих шагов: 1. Пользователь A генерирует ключевую пару (ОКА,СКА). 2. Пользователь B генерирует ключевую пару (ОКB,СКB). 3. Пользователи A и B должны обменяться своими открытыми ключами. Пользователь А передает свой открытый ключ ОКА пользователю B, пользователь B передает свой открытый ключ ОКB пользователю A. 4. Пользователь А шифрует информацию для пользователя B на ключе ОКB, пользователь B шифрует информацию для пользователя A на ключе ОКA. 5. Пользователь А дешифрует информацию, присланную ему от пользователя B, на ключе СКА, пользователь B дешифрует информацию, присланную ему от пользователя A, на ключе СКB. Обмен открытыми ключами в современных криптографических сетях, насчитывающих десятки и даже сотни тысяч пользователей более удобно реализовывать, используя специально выделенные для этого центры распределения ключей. Пользователь A может выложить на центр распределения ключей свой открытый ключ и любой другой пользователь, желающий шифровать информацию для A, может обратиться в данный центр и забрать его открытый ключ. Схема распределения ключей в данном случае может выглядеть следующим образом (рис. 4.6).  Рис. 4.6. Схема распределения ОК с использованием центра распределения ключей В настоящее время все более распространенным подходом к распределению ключей становится подход, основанный на реализации инфраструктуры открытых ключей PKI и удостоверяющих центров (УЦ). У. Диффи и М. Хеллман сформулировали требования, выполнение которых обеспечивает безопасность асимметричной криптосистемы [13]: 1. Вычисление ключевой пары (ОК, СК) должно быть достаточно простым. 2. Отправитель, зная открытый ключ получателя, может легко получить шифротекст. 3. Получатель, используя свой секретный ключ, может легко из шифротекста восстановить исходное сообщение. 4. Знание открытого ключа злоумышленником не должно влиять на криптостойкость системы. При попытке вычислить злоумышленником закрытый ключ по открытому, он должен наталкиваться на непреодолимую вычислительную проблему. 5. Злоумышленник, зная шифротекст и открытый ключ, на котором осуществлялось шифрование, при попытке восстановить исходный текст должен наталкиваться на трудно преодолимую вычислительную проблему. 4.5.2. Однонаправленные функцииРеализация асимметричных криптосистем основана на использовании однонаправленных функций. Пусть X и Y – некоторые произвольные множества. Функция  называется однонаправленной функцией, если для любого элемента  можно легко вычислить его образ  , однако, зная элемент  , достаточно сложно получить его прообраз  , хотя такой элемент x однозначно существует, хотя бы один.Одним из основных критериев, по которому функцию f можно считать однонаправленной, является отсутствие эффективных алгоритмов обратного преобразования  для ряда математических функций, что не позволяет обратить данную функцию за приемлемое время.Рассмотрим несколько примеров однонаправленных функций, имеющих большое значение для криптографии. Целочисленное умножение Вычисление произведения двух очень больших целых чисел P и Q (N=P*Q) является несложной задачей для ЭВМ. Однако, решение обратной задачи, заключающейся в нахождении делителей P и Q большого числа N (в особенности, когда P и Q – большие простые числа), является практически неразрешимой задачей. Если N264 и PQ, то задача факторизации не разрешима за приемлемое время на современных ЭВМ. Поэтому целочисленное умножение является однонаправленной функцией. Модульная экспонента Возведение очень большого числа A в очень большую степень x (  ), то есть вычисление  , где модуль M тоже большое число, является несложной задачей для ЭВМ. Однако решение обратной задачи – нахождения степени x по известным у, A, M такой, что  (задача дискретного логарифмирования,  ), практически не разрешима за приемлемое время на современных ЭВМ (эффективного алгоритма вычисления дискретного логарифма пока не найдено). Поэтому модульная экспонента является однонаправленной функцией.Рассмотрим простую интерпретацию сказанного. Пусть задано: А=2, х=2, М=4. Тогда = 0. Пусть А=2, х=3, М=4. Тогда = 0. Отсюда видно, что по у вычислить х можно только полным перебором всех вариантов даже, если известны А и М.Кроме однонаправленных функций важное значение для криптографии с открытым ключом имеют однонаправленные функции с «потайным входом», эффективное обращение которых возможно, если известен секретный «потайной ход» (секретное число или другая информация, ассоциируемая с функцией). 4.5.3. Алгоритм шифрования RSAАлгоритм RSA был предложен в 1978 году Р.Райвестом, А. Шамиром, А. Адлеманом и был назван по первым буквам фамилий его авторов. Данный алгоритм стал первым алгоритмом шифрования с открытым ключом. Надежность данного алгоритма основывается на трудности факторизации больших чисел и вычисления дискретных логарифмов [14,2]. В криптосистеме RSA открытый ключ ОК, секретный ключ СК, исходное сообщение М и шифротекст С являются целыми числами от 0 до N-1, где N – модуль. Пусть пользователь А является получателем сообщения, которое ему должен переслать отправитель B. Пользователь A должен вначале сгенерировать ключевую пару RSA, это он делает следующим образом. Алгоритм формирования ключевой пары пользователем А 1. Выбираем случайные большие простые числа P и Q. Для обеспечения максимальной безопасности P и Q выбирают примерно равной длины и хранят в секрете. 2. Вычисляем модуль  . Формируем функцию Эйлера  .3. Открытый ключ ОКА выбирается случайно таким образом, чтобы выполнялись следующие условия:
4. Секретный ключ СКA находится по сформированному открытому ключу так, что
Здесь функция mod - взятия остатка от деления. Пользователь A может легко сформировать СКА, используя расширенный алгоритм Евклида, зная числа P и Q, а значит и  .Любой другой пользователь не может, зная открытый ключ ОКА вычислить СКА, так как ему не известны числа P и Q. Для их нахождения ему потребуется факторизовать известное ему большое число N, что является вычислительно сложной задачей. Шифрование и дешифрование сообщений в криптосистеме RSA Для того, чтобы зашифровать открытое сообщение M, отправитель B должен возвести его в степень открытого ключа пользователя А по модулю N. То есть шифрование выполняется в соответствие с формулой
Обращение данной функции, то есть определение значения M по известным значениям С, ОКА, N практически не осуществимо при больших N(  ).Однако знание секретного ключа СКА позволяет обратить данную функцию, то есть решить задачу дешифровки криптограммы C. Для дешифровки криптограммы С необходимо возвести ее в степень секретного ключа пользователя А по модулю N. Таким образом, дешифрование сообщения выполняется в соответствие с формулой
Получатель А, который создает ключевую пару (ОКА,СКА) защищает два параметра:
Рассекречивание данных чисел приводит к тому, что злоумышленник сможет вычислить , а значит и вычислить секретный ключ СКА согласно (4.10).Открытыми в криптосистеме RSA являются только значения ОКА и N. В настоящее время разработчики криптоалгоритмов с открытым ключом на базе RSA предлагают применять в качестве чисел P,Q,N – числа длиной не менее 200-300 десятичных разрядов. Пример 4.7 Зашифруем сообщение DAC по алгоритму RSA. Для простоты вычислений будем оперировать с небольшими числами P и Q. Действия получателя А 1. Выберем P = 5 и Q = 13 2. Найдем  3.  .4. В качестве ОКА необходимо выбрать значение, удовлетворяющее условиям  ,  . Пусть ОКА = 5.5. Необходимо найти СКА, такой что  . Этому условию удовлетворяет число СКА=29, определяемое подбором. Оно не единственно. Действительно,  .6. Отправляем пользователю B пару чисел по открытому каналу связи (N=65, ОКА=5) Действия отправителя B 1. Представим отправляемое сообщение в виде последовательности целых чисел от 0 до 63. Присвоим букве А номер 1, букве B – 2, С – 3, D – 4 и т.д. Тогда открытый текст DAC запишется в виде последовательности чисел 413, то есть M1=4, M2=1, M3=3. 2. Сформируем шифротекст по формуле 4.8:  ,  , .
Действия пользователя A 1. Раскрываем шифротекст по формуле 4.11:  ,  , .Таким образом, восстановлено исходное сообщение M1=4=D, M2=1=A, M3=3=C. Исходное сообщение – DAC. | ||||||||||||
