Главная / Каталог

Баричев С. Криптография без секретов

Выберем p=3 и q=11.

Определим n=3*11=33.

Найдем (p-1)(q-1)=20. Следовательно, в качестве d, взаимно простое с 20, например, d=3.

Выберем число е. В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение (е*3) (mod 20) = 1, например 7.

Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А(1, В(2, С(3. Тогда сообщение принимает вид (3,1,2). Зашифруем сообщение с помощью ключа {7,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.

Расшифруем полученное зашифрованное сообщение (9,1,29) на основе закрытого ключа {3,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 реализуется следующим образом: каждый пользователь выбирает два больших простых числа, и в соответствии с описанным выше алгоритмом выбирает два простых числа e и d. Как результат умножения первых двух чисел (p и q) устанавливается n.

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

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

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

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

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

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

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

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

log10 n

Число операций

Примечания

50

1.4*1010

Раскрываем на суперкомпьютерах

100

2.3*1015

На пределе современных технологий

200

1.2*1023

За пре​де​ла​ми со​вре​мен​ных тех​но​ло​гий

400

2.7*1034

Тре​бу​ет су​ще​ст​вен​ных из​ме​не​ний в тех​но​ло​гии

800

1.3*1051

Не раскрываем

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

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

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

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

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

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

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

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

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

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

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