Практическая реализация RSA | MetodPro.ru

Реклама на сайте

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


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

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

В принципе в качестве 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 бит - для особо секретной информации.[4]

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

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

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



[1] Например, в нашумевшей программе PGP

[2] В браузерах Интернет от Microsoft и Netscape

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

[4] Данные оценки сделаны с учетом развития вычислительной техники вплоть до 2004 года.



Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем