Компьютерная безопасность. Криптографические методы защиты - Петров А.А.
ISBN 5-89818-064-8
Скачать (прямая ссылка):
Вместе с тем необходимо отметить, что стойкость большинства современных асимметричных алгоритмов базируется на двух математических проблемах, которые на данном этапе являются трудновычисляемыми даже для метода «грубой силы»:
• дискретное логарифмирование в конечных полях;
• факторизация больших чисел.
Поскольку на сегодняшний день не существует эффективных алгоритмов решения данных задач либо их решение требует привлечения больших вычислительных ресурсов или временных затрат, эти математические задачи нашли широкое применение в построении асимметричных алгоритмов. Их стойкость рассматривается как возможность свести проблему вскрытия алгоритмов к решению одной из вышеперечисленных математических головоломок.
Асимметричные алгоритмы шифрования
55
1.3.2. Стандарт асимметричного шифрования RSA
Самым распространенным алгоритмом асимметричного шифрования является алгоритм RSA, названный по первым буквам имен его создателей (Rivest, Shamir, Adleman). Разработчикам данного алгоритма удалось эффективно воплотить идею односторонних функций с секретом. Стойкость RSA базируется на сложности факторизации больших целых чисел.
В 1993 году метод RSA был обнародован и принят в качестве стандарта (PKCS # 1: RSA Encryption Standard). RSA можно применять как для зашифрования/расшифрования, так и для генерации/проверки электронно-цифровой подписи (ЭЦП).
Генерация ключей
Каждый участник информационного обмена генерирует пару ключей (открытый и секретный) в соответствии со следующими правилами:
1. Выбираются два больших простых целых числа р и q приблизительно одинакового размера. Выбор чисел р и q определяется следующими соображениями:
-увеличение порядка чисел ведет к замедлению операции зашифрования/расшифрования;
- увеличение порядка чисел р и q ведет к увеличению стойкости алгоритма, поэтому при выборе чисел следует руководствоваться практической необходимостью. Так, например, при реализации RSA в интеллектуальных карточках с точки зрения скоростных параметров системы не следует выбирать слишком большие р и q в связи с ограниченными вычислительными возможностями, заложенными в данных устройствах. На практике обычно рекомендуется выбирать числа, содержащие порядка 150-200 десятичных знаков.
2. Вычисляется модуль системы n = pq и ф(п) = (р- l)(q- 1) - функция Эйлера.
3. Выбирается достаточно большое число е, удовлетворяющее условию 1 < е < ф(п), и взаимно простое с (р(п).
4. Используя расширенный алгоритм Евклида, вычисляется большое целое число d, отвечающее условию:
ed = 1 (mod ф(п)) 1 < d < ф(п)
Таким образом, секретным ключом является пара чисел (n, d), а открытым - пара чисел (п, е). Открытый ключ помещается в общедоступный
56
Общие сведения по классической криптографии
справочник (детально этот процесс будет описан ниже). В соответствии с PKCS # 1 формат представления ключей имеет следующий вид:
RSAPublicKey := Sequence {
modulus Integer, п (модуль n)
public Exponent Integer, e (открытая экспонента
шифрования)
}
Формат RSAPublicKey и RSAPrivateKey представлен в соответствии с ASN.1 (Х.208 CCITT) . Секретный ключ имеет вид: RSAPrivateKey: = Sequence version Version
modulus Integer, n public Exponent Integer, e
private Exponent Integer, d
prime 1 Integer, p prime 2 Integer, q exponentl Integer, d mod (p-1)
exponent 2 Integer, d mod (q-1) coefficient Integer, (inverse of q)
mod p
{
Идентификатор версии предназначен для совместимости с последующими версиями. Модуль п.
Открытая экспонента зашифрования е. Секретная экспонента расшифрования d. Простое целое р. Простое целое q. Данные экспоненты используются для обеспечения эффективности работы алгоритма.
Инверсия q (q'Mmod р) , удовлетворяющая условию qq"1 = 1 (mod р) . }
Version := Integer
Зашифрование/расшифрование
После выбора параметров системы (n, е, d) абонент готов к приему зашифрованных сообщений. Их передача состоит из следующих шагов:
1. Входное сообщение разбивается на блоки mi( их размер определяется целым к, соответствующим неравенству 10ы < п < 10к.
2. Вычисляется значение с; = mfmod п.
3. Значение с„ которое является зашифрованным блоком сообщения, посылается по открытым каналам передачи данных.
Асимметричные алгоритмы шифрования
57
Расшифрование заключается в вычислении значения Ta1 = cfmod п.
Доказательством того факта, что расшифрование выполняется только абонентом, знающим секретную экспоненту зашифрования d, является Cjd mod n = mi0 d mod n, с учетом, что ed = 1 (mod Ф(п)). При этом получаем ed = 1 + k(p(n), где к - целое число, удовлетворяющее этому равенству. Поскольку т/ (m)mod п - единичный элемент группы относительно операции умножения, элемент гщ тоже принадлежим к данной группе. В этом случае:
cd mod n = mjirif^mod п = тг /.3.3. Стойкость алгоритма RSA
Очевидно, что стойкость RSA и асимметричных алгоритмов в целом зависит от сложности обращения односторонних функций, лежащих в основе данного типа алгоритмов. В RSA сложность обращения односторонней функции F(x) - ху (mod п) зависит от сложности разложения на множители модуля п. При этом следует иметь в виду, что это утверждение является всего лишь предположением, поскольку строгих математических доказательств эквивалентности данных проблем пока не существует.
