Криптография с открытым ключом

 

Традиционно криптография основывалась на том, что отправитель и получатель сообщения знали и использовали один и тот же секретный ключ. Отправитель с его помощью шифровал сообщение, а получатель – расшифровывал. Этот метод называется криптографией с секретным ключом (secret-key cryptography), или симметричная криптография (symmetric cryptography). Главная проблема такого метода заключается в том, чтобы получатель и отправитель использовали один и тот же ключ, который должен быть неизвестен всем остальным. Если они находятся на большом расстоянии друг от друга, им приходится доверять курьеру, телефону или другой системе передачи сообщений, скрывая то, что передается секретный ключ. Создание, передача и хранение ключей называется распределением ключей (key management). Все криптосистемы должны выполнять распределение ключей, однако при использовании метода симметричной криптографии этот процесс имеет весьма сложный характер.

В 1976 г. был разработан метод криптографии с открытым ключом (public-key cryptography), или несимметричной криптографии (asymmetric cryptography). Этот метод предполагает наличие двух ключей – открытого и личного (закрытого, секретного). Открытый ключ можно разглашать, а личный необходимо хранить в тайне. При обмене сообщениями пересылается только открытый ключ. Таким образом, пользуясь данным методом, можно не беспокоиться о надежности каналов передачи информации. Более того, криптография с открытым ключом, в отличие от криптографии с секретным ключом, может применяться не только для секретности (шифрование), но и для аутентификации (например, на основе применения электронной подписи).

Основная схема шифрования на основе использования открытого ключа следующая. Если я хочу послать сообщение адресату А., я нахожу в справочнике открытый ключ А., использую его для кодирования сообщения и отправляю письмо. Получив мое послание, А. с помощью своего личного ключа расшифровывает и читает мое сообщение. Таким образом, любой может послать А. закодированное сообщение, но только А. может прочесть его. Между открытым и закрытым ключами существует определенная связь, базирующаяся на достаточно сложной математической зависимости. Естественно, жесткое требование к такому методу – исключение возможности получения личного ключа из соответствующего открытого ключа.

Применение криптографии с открытым ключом при аутентификации рассматривается ниже в подразделе 2.5.2.

Алгоритм RSA, предложенный в 1977 гг. Р.Ривестом (Ron Rivest), А.Шамиром (Adi Shamir) и Л.Эдлеманом (Leonard Adleman), предназначен для шифрования и электронной подписи. В настоящее время RSA является наиболее распространенной криптосистемой – стандартом де-факто для многих криптографических приложений в криптографии с открытым ключом. Позднее алгоритм RSA был включен в принятые ранее национальные криптографические стандарты.

Из всех предложенных за эти годы алгоритмов с открытыми ключами RSA проще всего понять и реализовать. Алгоритм RSA многие годы противостоит интенсивному криптоанализу. Безопасность RSA основана на трудности разложения на множители больших чисел, известного под названием задачи факторизации. Открытый и закрытый ключи являются функциями двух больших (100 – 200 разрядов или даже больше) простых чисел. Итак, для генерации двух ключей используются два больших случайных простых числа: p и q. Их выбор может быть осуществлен с использованием датчика псевдослучайных чисел. Для максимальной безопасности нужно выбирать p и q равной длины. Рассчитывается произведение:

n = p*q

Затем случайным образом выбирается ключ шифрования е, такой что е и (p - 1)*(q - 1) являются взаимно простыми числами (то есть числами, не имеющими общих делителей). Наконец, расширенный алгоритм Евклида используется для вычисления закрытого ключа d, такого, что:

e*d = 1(mod(p - 1)(q - 1))

Другими словами, d = e-1mod((p - 1)(q - 1)).

При этом d и n – также взаимно простые числа. Числа е и n – это открытый ключ, а число d – закрытый. Два простых числа p и q хранятся в секрете. Они должны быть отброшены, но не должны быть раскрыты.

Напоминаю, что знак mod означает определение остатка от деления числа перед этим знаком на число в скобках после этого знака. Правило выполнения этой операции в данном случае соответствует расширенному  алгоритму Евклида.

Для шифрования сообщения m необходимо выполнить его разбивку на цифровые блоки, каждый из которых меньше n (для двоичных данных выбирается самая большая степень числа 2, меньшая n). То есть если p и q – 100-разрядные простые числа, то n будет содержать около 200 разрядов, и каждый блок сообщения mi должен быть около 200 разрядов в длину. Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, чтобы гарантировать, что блоки всегда будут меньше n. Зашифрованное сообщение с будет состоять из блоков сi той же самой длины. Формула шифрования выглядит так:

ci = mei mod n

Для расшифровки сообщения необходимо взять каждый зашифрованный блок ci и вычислить

mi = cdi mod n

Параметры криптосистемы и процедуры шифрования и расшифровывания сведены в табл. 2.14.

Таблица 2.14

Шифрование RSA

Параметры криптосистемы Формулы вычисления Открытый ключ  п произведение двух простых чисел р и q (р и q должны храниться в секрете) е число, взаимно простое с (р - 1)*(q - 1) Закрытый ключ d е ^-1mоd ((р - 1)(q - 1)) Шифрование с = т^етоd п Расшифровывание т = с^dтоd п

 

Сообщение может быть зашифровано с помощью е и n, а расшифровано с помощью d.

Быстродействие аппаратной реализации системы шифрования с открытым ключом RSA примерно в 1000 раз ниже, чем быстродействие аппаратной реализации системы шифрования с секретным ключом DES. Программная реализация DES примерно в 100 раз быстрее RSA. Эти оценки могут незначительно отличаться при изменении технологии, но RSA никогда не достигнет скорости симметричных алгоритмов. В табл. 2.15 приведены примеры программной реализации RSA для 8-битовой экспоненты шифрования и различной разрядности модуля.

Для взлома ключей системы RSA необходимо разложить модуль N на простые множители. Из-за большой популярности этой системы в настоящее время в этой области криптоанализа работает очень много ученых и, необходимо отметить, не без успеха. Рекомендуется использовать RSA-ключи с длиной верхних границ, которые приводятся в табл. 2.16.

Несмотря на пониженную скорость реализации алгоритма RSA уязвимость этой системы достаточно низка. Кроме того, она обладает рядом удобств и гарантий безопасности.

Таблица 2.15

Эффективность программной реализации RSA (в секундах на SPARC[8] II)

Операция	512 битов	768 битов	1024 бита
Шифрование	0,03	0,05	0,08
Расшифровывание	0,16	0,48	0,93
Вычисление подписи	0,16	0,52	0,97
Проверка подписи	0,02	0,07	0,08

 

 

Таблица 2.16

Длина верхних границ RSA-ключей

Принадлежность ключа	Максимальная длина, байт
Аутентификация (модуль)	248
Ключ эмитента (модуль)	247
Ключ карты (модуль)	128

 

Несмотря на сложность «бескомпьютерной» демонстрации примеров реализации алгоритмов криптографии с открытым ключом в виду большой размерности получаемых чисел, мы приведем все же один пример.

Для простоты предположим, что текст сообщения на русском языке содержит слова, записанные только заглавными буквами. Первый шаг состоит в замене каждой буквы сообщения числом. Пусть таблица замен в данном случае имеет вид (табл. 2.17).

 

Таблица 2.17

Номера букв при осуществлении замены

 

А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С
10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
Т	У	Ф	X	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
28	29	30	31	32	33	34	35	36	37	38	39	40	41

 

Пробел между словами будем заменять числом 99.

Обратим внимание на то, что в этом примере каждая буква кодируется двузначным числом. Это сделано для предотвращения неоднозначности. Если пронумеровать буквы не по порядку, начиная с 1, т.е. А соответствует 1, Б соответствует 2 и т.д., то будет непонятно, что обозначает блок 12: пару букв АБ или букву Л, двенадцатую букву алфавита. Конечно, для кодирования можно использовать любые однозначные соответствия между буквами и числами, например ASCII-кодировку, что чаще всего и делается.

Далее предположим, что открытый текст – это девиз «ПОЗНАЙ СЕБЯ». Тогда его цифровое представление имеет вид: 2524172310199927151141.

Пусть в нашем примере р = 149, q = 157, тогда n = 23393. Поэтому цифровое представление открытого текста нужно разбить на блоки, меньшие чем 23393. Одно из таких разбиений выглядит следующим образом:

2524 - 1723 - 10199 - 9271 - 511 - 41.

Конечно, выбор блоков неоднозначен, но и не совсем произволен. Например, во избежание двусмысленностей на стадии расшифровки не следует выделять блоки, начинающиеся с нуля.

Теперь нужно выбрать число е, взаимно простое с 23088. Наименьшее простое число, не имеющее общих делителей с 23088, равно 5. Положим е = 5. Зашифруем первый блок сообщения: вычисляем 2524⁵ mod 23393 = 22752; далее по остальным блокам:

1723⁵ mod 23393 = 6198,

10199⁵ mod 23393= 14204,

9271⁵ mod 23393 = 23191,

511⁵ mod 23393 = 10723,

41⁵ mod 23393 = 14065.

Теперь шифрованный текст имеет вид 22752619814204231911072314065.

В нашем примере n = 23393, е = 5. Применив расширенный алгоритм Евклида к числам (p - 1)(q - 1) = 23088 и е = 5, найдем d = е^-1 mod 23088 = 13853.

Зашифрованный текст разделяем на блоки, полученные при шифровании. Для расшифровки блоков шифротекста необходимо возвести каждый блок в степень 13853 и выполнить расчет по модулю 23393. В примере первый блок шифротекста – число 22752, тогда получим 22752¹³⁸⁵³ mod 23393 = 2524, что соответствует первым двум буквам исходного текста – «ПО…».

 

Управление ключами

 

Кроме выбора подходящей для конкретной ИС криптографической системы, важная проблема – управление ключами. Как бы ни была сложна и надежна сама криптосистема, она основана на использовании ключей. Если для обеспечения конфиденциального обмена информацией между двумя пользователями процесс обмена ключами тривиален, то в ИС, где количество пользователей составляет десятки и сотни, управление ключами – серьезная проблема.

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

Управление ключами – информационный процесс, включающий в себя три элемента:

• генерацию ключей;

• накопление ключей;

• распределение ключей.

Рассмотрим, как они должны быть реализованы для того, чтобы обеспечить безопасность ключевой информации в ИС.

Генерация ключей.

Необходимо подчеркнуть, что не стоит использовать неслучайные ключи с целью легкости их запоминания. В серьезных ИС используются специальные аппаратные и программные методы генерации случайных ключей. Как правило, используют датчики ПСЧ. Однако степень случайности их генерации должна быть достаточно высокой. Идеальными генераторами являются устройства на основе “натуральных” случайных процессов. Например, появились серийные образцы генерации ключей на основе белого радиошума [9]. Другим случайным математическим объектом являются десятичные знаки иррациональных чисел, например π или е, которые вычисляются с помощью стандартных математических методов.

В ИС со средними требованиями защищенности вполне приемлемы программные генераторы ключей, которые вычисляют ПСЧ как сложную функцию от текущего времени и (или) числа, введенного пользователем.

Из предыдущего материла известно, что в ряде случаев генерируются не ключи, а исходные данные для их расчета. Например, в алгоритме несимметричной криптографии RSA генерируются простые числа, на основании которых определяются ключи (см. выше подраздел 2.5.10).

Накопление ключей.

Под накоплением ключей понимается организация их хранения, учета и удаления.

Поскольку ключ является самым привлекательным для злоумышленника объектом, открывающим ему путь к конфиденциальной информации, то вопросам накопления ключей следует уделять особое внимание.

Секретные ключи никогда не должны записываться в явном виде на носителе, который может быть считан или скопирован.

В достаточно сложной ИС один пользователь может работать с большим объемом ключевой информации, и иногда даже возникает необходимость организации мини-баз данных по ключевой информации. Такие базы данных отвечают за принятие, хранение, учет и удаление используемых ключей. При этом каждая информация об используемых ключах должна храниться в зашифрованном виде. Ключи, зашифровывающие ключевую информацию, называются мастер-ключами. Желательно, чтобы мастер-ключи каждый пользователь знал наизусть, и не хранил их вообще на каких-либо материальных носителях.

Очень важным условием безопасности информации является периодическое обновление ключевой информации в ИС. При этом переназначаться должны как обычные ключи, так и мастер-ключи. В особо ответственных ИС обновление ключевой информации желательно делать ежедневно.

Вопрос обновления ключевой информации связан и с третьим элементом управления ключами – распределением ключей.

Распределение ключей.

Распределение ключей – самый ответственный процесс в управлении ключами. К нему предъявляются два требования:

1. Оперативность и точность распределения.

2. Скрытность распределяемых ключей.

В последнее время заметен сдвиг в сторону использования криптосистем с открытым ключом, в которых проблема распределения ключей, если и не отпадает полностью, то не является уже критичной. Тем не менее, распределение ключевой информации в ИС требует новых эффективных решений.

Распределение ключей между пользователями реализуются двумя разными подходами:

1. Путем создания одного или нескольких центров распределения ключей. Недостаток такого подхода состоит в том, что в центре распределения известно, кому и какие ключи назначены. Возможные злоупотребления существенно влияют на защиту информации.

2. Прямой обмен ключами между пользователями информационной системы. В этом случае проблема состоит в том, чтобы надежно удостоверить подлинность субъектов.

В обоих случаях должна быть гарантирована подлинность сеанса связи. Это можно обеспечить двумя способами:

1. Механизм запроса-ответа, который состоит в следующем. Если пользователь А желает быть уверенным, что сообщения, которые он получает от В, не являются ложными, он включает в посылаемое для В сообщение непредсказуемый элемент (запрос). При ответе пользователь В должен выполнить некоторую операцию над этим элементом (например, добавить 1). Это невозможно осуществить заранее, так как не известно, какое случайное число придет в запросе. После получения ответа с результатами действий пользователь А может быть уверен, что сеанс является подлинным. Недостатком этого метода является возможность установления довольно сложной закономерности между запросом и ответом.

2. Механизм отметки времени ("временной штемпель"). Он подразумевает фиксацию времени для каждого сообщения. В этом случае каждый пользователь ИС может знать, насколько “старым” является пришедшее сообщение.

В обоих случаях следует использовать шифрование, чтобы быть уверенным, что ответ послан не злоумышленником и штемпель отметки времени не изменен.

При использовании отметок времени встает проблема допустимого временного интервала задержки для подтверждения подлинности сеанса. Ведь сообщение с “временным штемпелем” в принципе не может быть передано мгновенно. Кроме этого, компьютерные часы получателя и отправителя не могут быть абсолютно синхронизированы. Тем не менее, в системах оплаты кредитных карточек, используется именно второй механизм установления подлинности и защиты от подделок. Используемый интервал составляет от одной до нескольких минут. В то же время большое число известных способов кражи электронных денег основано на “вклинивании” в этот промежуток подложных запросов на снятие денег.

Для обмена ключами можно использовать криптосистемы с открытым ключом, используя тот же алгоритм RSA. Ниже в подразделе 2.5.12 этот вопрос рассматривается на примере усиленной электронной подписи.

Весьма эффективным оказался алгоритм Диффи-Хеллмана, позволяющий двум пользователям без посредников обменяться ключом, используя незащищенный от прослушивания канал связи, который может быть использован затем для симметричного шифрования. Схема открытого распределения ключей, предложенная Диффи и Хеллманом, произвела настоящую революцию в мире шифрования, так как снимала основную проблему классической криптографии – проблему распределения ключей.

 

2.5.12. Электронная цифровая подпись (электронная подпись) [10]

 

Общие положения.

При обмене электронными документами в информационно-телекоммуникационной сети существенно снижаются затраты на обработку и хранение документов, ускоряется их поиск. Но при этом возникает проблема аутентификации автора документа и самого документа, т.е. установления подлинности автора и отсутствия изменений в полученном документе.

Целью аутентификации электронных документов является их защита от возможных видов злоумышленных действий, к которым относятся:

· Активный перехват – нарушитель, подключившийся к сети, перехватывает документы (файлы) и изменяет их;

· Маскарад – абонент С посылает документ абоненту В от имени абонента А;

· Регенегатство – абонент А заявляет, что не посылал сообщения абоненту В, хотя на самом деле послал;

· Подмена –абонент В изменяет или формирует новый документ и заявляет, что получил его от абонента А;

· Повтор – абонент С повторяет ранее переданный документ, который абонент А посылал абоненту В.

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

При обработке документов в электронной форме непригодны традиционные способы установления подлинности по рукописной подписи и оттиску печати на бумажном документе. Принципиально новым решением является электронная цифровая подпись (ЭЦП) или, что одно и то же, электронная подпись (ЭП).

Видами электронных подписей, отношения в области использования которых регулируются Федеральным закон от 06.04.2011 г. № 63-ФЗ «Об электронной подписи», являются простая электронная подпись и усиленная электронная подпись. Различаются усиленная неквалифицированная электронная подпись ( далее – неквалифицированная электронная подпись) и усиленная квалифицированная электронная подпись ( далее – квалифицированная электронная подпись).

Несимметричные криптографические алгоритмы используются только в связи с применением усиленной электронной подписи. При применении простой электронной подписи криптографические преобразования не производятся.