ШТ2 = (f) (mod 33) = 1 (mod 33) = 1, ШТЗ = (2) (mod 33) = 128 (mod 33) = 29.

6. Расшифруем полученное зашифрованное сообщение (9,1,29) на основе закрытого ключа {3,33}:

ИТ1 = (9) (mod 33) = 729 (mod 33) = 3,

ИТ2= (1) (mod 33) = 1 (mod 33) = 1,

ИТЗ = (29) (mod 33) = 24389 (mod 33) = 2.

Итак, в реальных системах алгоритм RSA реализуется следующим образом: каждый пользователь выбирает два больших простых числа, и в соответствии с описанным выше алгоритмом выбирает два простых числа е и <i. Как результат умножения первых двух чисел (р и ) устанавливается п.

(е,п} образует открытый ключ, а (d,n} - закрытый (хотя можно взять и наоборот).

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

Практическая реализация RSA

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

Средств в популярных приложениях .

Важная проблема практической реализации - генерация больших простых чисел. Решение задачи «в лоб» - генерация случайного большого числа п (нечетного) и проверка его делимости на множители от 3 вплоть до п. В случае неуспеха следует взять п+2 и так далее.

В принципе в качестве р и q можно использовать «почти» простые числа, то есть числа для которых вероятность того, что они простые, стремится к 1. Но в случае, если использовано составное число, а не простое, криптостойкость RSA падает. Имеются неплохие алгоритмы, которые позволяют генерировать

О-100

«почти» простые числа с уровнем доверия 2

Другая проблема - ключи какой длины следует использовать!

Для практической реализации алгоритмов RSA полезно знать оценки трудоемкости разложения простых чисел различной длины, сделанные Шроппе-лем.

Например, в наплумевшей программе PGP В браузерах Интернет от Microsoft и Netscape

° В теории чисел показано, что вероятность того, что число порядка п будет простым составляет 1/1п п

в конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного ключа. Для этого с помош,ью сети Интернет было задействовано 1600 компьютеров.

Сами авторы RSA рекомендуют использовать следующие размеры модуля

• 768 бит - для частных лиц;

• 1024 бит - для коммерческой информации;

• 2048 бит - для особо секретной информации.

Третий немаловажный аспект реализации RSA - вычислительный. Ведь приходится использовать аппарат длинной арифметики. Если используется ключ длиной к бит, то для операций по открытому ключу требуется О(к) операций, по закрытому ключу - О(к) операций, а для генерации новых ключей требуется 0(к) операций.

Криптографический пакет BSAFE 3.0 (RSA D.S.) на компьютере Pentium-90 осуществляет шифрование со скоростью 21.6 Кбит/с для 512-битного ключа и со скоростью 7.4 Кбит/с для 1024 битного. Самая «быстрая» аппаратная реализация обеспечивает скорости в 60 раз больше.

По сравнению с тем же алгоритмом DES, RSA требует в тысячи и десятки тысяч раз большее время.

Криптосистема Эль-Гамаля

Данная система является альтернативой RSA и при равном значении клю-

ча обеспечивает ту же криптостойкость .

В отличие от RSA метод Эль-Гамаля основан на проблеме дискретного логарифма. Этим он похож на алгоритм Диффи-Хелмана. Если возводить число в степень в конечном поле достаточно легко, то восстановить аргумент по значению (то есть найти логарифм) довольно трудно.

Основу системы составляют параметры /? и g - числа, первое из которых -простое, а второе - целое.

Александр генерирует секретный ключ а и вычисляет открытый ключ у = mod p. Если Борис хочет послать Александру сообщение т, то он выбирает случайное число к, меньшее р и вычисляет

yi = gmodp и У2 = т® /,

" Данные оценки сделаны с учетом развития вычислительной техники вплоть до 2004 года. Однако общего мнения по поводу предпочтительности того или иного метода нет.

где © означает побитовое сложение по модулю 2. Затем Борис посылает (У1,У2) Александру.

Александр, получив зашифрованное сообш,ение, восстанавливает его:

т = (у/" mod р)@у2.

Алгоритм цифровой подписи DSA, разработанный NIST (National Imtitute of Standard and Technology) и являюш,ийся частью стандарта DSS частично опирается на рассмотренный метод.

Криптосистемы на основе эллиптических уравнений

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

У = X + ах + Ь,

а также бесконечно удаленная точка. Для точек на кривой довольно легко вводится операция сложения, которая играет ту же роль, что и операция умножения в криптосистемах RSA и Эль-Гамаля.

В реальных криптосистемах на базе эллиптических уравнений используется уравнение

у = X + ах + b mod р,

где р - простое.

Проблема дискретного логарифма на эллиптической кривой состоит в следующем: дана точка G на эллиптической кривой порядка г (количество точек на кривой) и другая точка Y на этой же кривой. Нужно найти единственную точку X такую, что Y = xG, то есть Y есть х-я степень G.