3.Выберем в качестве секретного ключа d произвольное число взаимно простое с(n)=20, например, d=3.

4.Выберем открытый ключ е = 7. В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение

е· d mod (n) = 7·3 mod 20 = 1.

5.Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А=1, В=2, С=3. Тогда сообщение принимает вид (3,1,2). Зашифруем сообщение с помощью ключа {е=7, n=33}:

ШТ1 = (37) mod 33 = 2187 mod 33 = 9,

ШТ2 = (17) mod 33 = 1 mod 33 = 1,

ШТ3 = (27) mod 33 = 128 mod 33 = 29.

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

ИТ1 = (93) mod 33 = 729 mod 33 = 3, ИТ2= (13) mod 33 = 1 mod 33 = 1,

ИТ3 = (293) mod 33 = 24389 mod 33 = 2.

Надежность RSA. RSA многие годы противостоит интенсивному криптоанализу. Доказано, что раскрытие шифра RSA эквивалентно решению задачи факторизации больших (100-200 двоичных разрядов) чисел. Важно, что в этой задаче для любой длины ключа можно дать нижнюю оценку числа операций для раскрытия шифра, а с учетом производительности современных компьютеров оценить и необходимое на это время.

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

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

Данная система является альтернативой RSA и при равном значении ключа обеспечивает ту же криптостойкость. Однако общего мнения по поводу предпочтительности того или иного метода нет.

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

346

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

Основу системы составляют параметры p и g - числа, первое из которых p — простое, а второе (g Zp) — целое. Данные параметры не являются секретными и могут быть общими для группы пользователей. В реальных схемах шифрования необходимо использовать в качестве модуля большое целое простое число, имеющее в двоичном представлении длину 512...1024 бит.

Cекретный ключ x Zp-тест,1 генерируетcя случайным образом, а открытый ключ y вычисляется по формуле

y = gx mod p.

Для шифрования сообщения m сначала выбирается случайное число k, взаимно простое с p-тест,1, которое называют также сеансовым ключом.

Шифртекстом является пара чисел (a,b), вычисляемая по формулам: a = gk mod p и

b = yk m mod p.

Таким образом, шифртекст в два раза длиннее открытого текста. Для дешифрования вычисляется

m = abx mod p.

Преобразование обратимо, так как

аx= gkx mod p

и	b			yk m		g xk m	m mod p.
	ax			ax		ax

Число k называют также рандомизатором. Его использование означает, что здесь реализован мнозначный шифр замены. При этом для зашифрования различных блоков (чисел) открытого текста необходимо использовать различные значения рандомизатора. При использовании одного и того же значения соответсвующие шифртексты (a, b) и (a´, b´), полученные для блоков открытых текстов m и m´, связаны соотношением

b( b´) –1= m(m´) –1

и текст m´можно вычислить, если известен текст m.

Стойкость криптосистемы Эль Гамаля основана на сложности задачи логарифмирования в мультипликативной группе конечного простого поля. Эта криптосистема может быть обобщена для применения в любой конечной циклической группе. В качестве такой группы, помимо рассмотренной Z*p, чаще всего используется мультипликативная группа конечного

347

поля GF(2m) и группа точек на эллиптической кривой над конечным полем (см. приложение П.8).

Алгоритм не запатентован, но попадает под действие патента на метод экспоненциального ключевого обмена Диффи-Хеллмана, рассмотренный ниже. Преобразование шифрования/дешифрования Эль Гамаля по сути то же самое, что ключевой обмен по ДиффиХеллману, за исключением того, что y – это часть ключа, а при шифровании сообщение умножается на yk. Алгоритм цифровой подписи DSA, разработанный N),ключи).ВIST (N),ключи).Вational Institute of Standard and Technology USA) и являющийся частью стандарта DSS частично опирается на рассмотренный метод.

Комбинированный метод шифрования

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

Однако алгоритмы, лежащие в основе криптосистем с открытым ключом, имеют следующие недостатки:

•генерация секретных и открытых ключей основана на генерации больших простых чисел, а проверка простоты чисел занимает много процессорного времени;

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

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

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

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

каждый по паре асимметричных ключей шифрования 348

(КАо, КАс) и (КВо, КВс).

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

1.Создать (например, сгенерировать случайным образом) симметричный ключ, называемый в этом методе сеансовым ключом Ks.

2.Зашифровать сообщение m на сеансовом ключе Ks.

3.Зашифровать сеансовый ключ Ks на открытом ключе КВо пользователя В и своем секретном ключе КАс.

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

Действия пользователя В при получении зашифрованного сообщения и зашифрованного

сеансового ключа должны быть обратными:

5.Расшифровать на своем секретном ключе КВс и открытом ключе КАо пользователя А сеансовый ключ Ks.

6.С помощью полученного сеансового ключа Ks расшифровать и прочитать сообщение

m.

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

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

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

Таблица 3.1. Длины ключей для симметричных и асимметричных криптосистем при

		одинаковой их криптостойкости
Симметричные криптосистемы	56	64	80	112	128
Асимметричные криптосистемы	384	512	786	179	2304
				2

349