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 требует в тысячи и десятки тысяч раз большее время.


 

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

3469. Основы МКТ 20.42 KB
  Основы МКТ Основные положения МКТ. Все тела состоят из частиц: молекул, атомов, ионов и т.д. Частицы вещества хаотически движутся. Частицы взаимодействуют между собой. Характер взаимодействия зависит от расстояния между молекулами. Идеальный газ. Ид...
3470. Исследования оптического квантового генератора (лазера) 48 KB
  Исследования оптического квантового генератора (лазера). Изучения принципа работы и устройства квантового генератора (ОКГ). Освоения электроскопического метода определения состава возбужденной среды. Измерения параметров и характеристик вынужденного...
3471. Система воспитательного процесса 39.47 KB
  Система воспитательного процесса, Структура и система воспитательного процесса. Закономерности и принципы процесса воспитания Цели и задачи воспитания Содержание воспитания Основные понятия: система, структура процесса воспита...
3472. Коррекция детских страхов у детей дошкольного возраста 93.93 KB
  Введение В ситуации социальной нестабильности на современного ребенка обрушивается множество неблагоприятных факторов, способных не только затормозить развитие потенциальных возможностей личности, но и повернуть процесс ее развития вспять. Поэтому б...
3473. Ботаніка як наука про рослини і їх клітинну будову 157.01 KB
  Вступ. Визначення ботаніки як науки про рослини. 2.Основні розділи ботаніки: - морфологія - анатомія рослин - цитологія - фізіологія рослин - систематика рослин - екологія рослин - геогра...
3475. Государственное регулирование занятости и трудоустройства молодежи на рынке труда (на примере Агинского Бурятского Округа Забайкальского края) 97.6 KB
  Объектом исследования стала молодежь в возрасте от 16 до 30 лет. Предметом исследования является государственное регулирование занятости и трудоустройства молодежи на рынке труда в Агинском Бурятском округе.