91627

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

Доклад

Информатика, кибернетика и программирование

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

Русский

2015-07-21

39.16 KB

0 чел.

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

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

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

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

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

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

log10 n 

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

Примечания

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.) на компьютере Рentium-90 осуществляет шифрование со скоростью 21.6 Кбит/c для 512-битного ключа и со скоростью 7.4 Кбит/c для 1024 битного. Самая <<быстрая>> аппаратная реализация обеспечивает скорости в 60 раз больше.

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


 

А также другие работы, которые могут Вас заинтересовать

64991. ПРОБЛЕМЫ АРХЕОЛОГИИ ЗОЛОТОЙ ОРДЫ 35.5 KB
  Цель спецкурса: на основе анализа археологических материалов познакомить слушателей с основными аспектами истории культуры зоны степей между Иртышом и Дунаем в монгольскую эпоху. Курс охватывает период между...
64993. Родословные легендарных потомков Огуз-кагана по спискам Махмуда Кашгари, Рашид ад-Дина и Абу-л-Гази хана Хивинского 55 KB
  В древности слова туркмен (туркман) не было; все кочевые племена, по внешнему виду похожие на тюрков, называли обобщено тюрками, но у каждого племени было определенное имя и прозвище. В то время когда эти племена Огуза пришли из своих областей в страны Мавераннахра...
64996. О татарах, монголах и о том, как Темучин стал Чингисханом 122.5 KB
  Не в последнюю очередь он видимо вызван тем что в 2006 году исполняется восемьсотлетие образования первого монгольского государства у истоков которого стоял Чингисхан.
64998. ИМЯ ЧИНГИСХАНА В ТАНГУТСКОЙ ПЕСНЕ 69.5 KB
  Последний поход Чингисхана против тангутов 1226-1227 оказался роковым для обеих сторон согласно источникам Чингисхан умер на территории тангутского государства в августе 1227 г. Однако среди разноязычных источников описывающих жизнь и смерть Чингисхана нет текстов на тангутском языке.