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


 

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

29362. Генерация объектного кода по семантическому дереву 52.5 KB
  Существует 3 формы объектного кода1. Чтобы показать процесс генерации кода можно рассмотреть теоретическую вычислительную машину с одним сумматором и неограниченной памятью.Генерация кода осуществляется для программы представленной в некоторой внутренней форме наиболее удобной из которых для генерации кода является список тетрад.
29363. Машинно – зависимая оптимизация объектного кода в языковых процессорах САПР 25 KB
  В самом простом случае машиннозависимая оптимизация заключается в удалении из сформированной последовательности команд избыточных команд загрузки и чтения. Если сложение является коммутативной операцией то последовательность команд LOAD OP1 можно заменить LOAD OP2 ADD OP2 = ADD OP1 2. Если умножение является коммутативной операцией то последовательность команд LOAD OP1 можно заменить LOAD OP2 MULT OP2 = MULT OP1 Эти 2 правила основаны на свойстве коммутативности операций и обеспечивают перестановку местами операндов в соответствующих...
29364. Хеш – адресация в информационных таблицах 51.5 KB
  В основе организации таблиц с хешадресацией лежит процедура хеширования. Хеширование – преобразование символьного имени идентификатора в числовой индекс элемента таблицы с помощью простых арифметических и логических операций.Конкретный способ хеширования задает хешфункция.
29365. Методы вычисления хеш-функции 24 KB
  Хорошая хешфункция распределяет вычисляемые индексы элементов в таблице равномерно по всей таблице чтобы уменьшить количество возникающих коллизий. Лучший результат дает использование в качестве хешфункции кода последнего символа имени.В трансляторах хешфункция является более сложной и зависит как от кодов внутреннего представления символов имени так и от его длины.
29366. Разрешения коллизий в хеш-таблицах методом рехеширования 31.5 KB
  Является не пустым возникает коллизия которую надо устранить путём выбора другой ячейки таблицы для имени S. Выбор такой ячейки производится:h1 = h p1mod N p1 – некоторое приращение. Если элемент таблицы h1 тоже не пустой то рассматривается новый элемент:h2 = h p2mod N hi = h pimod N до тех пор пока не будет найден элемент таблицы что1 элемент пустой тогда имя S в таблице отсутствует и записывается в таблице под инд. элементами таблицы должно быть минимальным. p1 = 1 p2 = 2 pi =...
29367. Реализация операций поиска и записи в хеш-таблицах по методу цепочек 27 KB
  на размер таблицы т. ситуация переполнения таблицы отсутствует.Для реализации метода цепочек необходимо следующее: таблица имён с дополнительным полем связи которое может содержать либо 0 либо адреса других элементов этой же таблицы. последнего записанного элемента таблицы.
29369. зыки проектирования как составная часть лингвистического обеспечения САПР 29.5 KB
  Языки проектирования – языки предназначенные для описания информации об объекте и процессе проектирования. а Входные языки предназначены для задания исходной информации об объектах и целях проектирования. Эти языки представляют собой совокупность языков описания объектов описания заданий и описания процессов.
29370. Определение формальной грамматики 49 KB
  Конечное множество символов неделимых в данном рассмотрении в теории формальных грамматик называется словарем или алфавитом а символы входящие в множество буквами алфавита. Последовательность букв алфавита называется словом или цепочкой в этом алфавите. Если задан алфавит A то обозначим A множество всевозможных цепочек которые могут быть построены из букв алфавита A. Формальной порождающей грамматикой Г называется следующая совокупность четырех объектов: Г = { Vт VA I VA R } где Vт терминальный алфавит словарь; буквы этого...