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


 

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

66573. Створення завантажувальних дискет, CD/DVD-дисків, флеш-накопичувачів 112.5 KB
  Діючи в рамках закону про авторські права, корпорація MicroSoft не може включити в аварійний комплект програми сторонніх розробників. Тому, завантажувальна дискета, автоматично створюється Windows, задовольняє лише тих, хто не розбирається ні в системі команд MS-DOS...
66574. Освоєння технології структурного та модульного програмування при розробці й створенні програми мовою Турбо Паскаль при реалізації на ПЕОМ задач з використанням процедур 118 KB
  Дослідити роботу операторів процедур мови Паскаль; знати призначення, форму запису та особливості вживання процедур. Освоїти методику складання, відладки та розв’язання Паскаль-програм (ПП) з використанням процедур на ПЕОМ.
66575. Преддипломная практика на предприятии Красноярский информационно-вычислительный центр структурное подразделение Главного вычислительного центра - филиала ОАО «РЖД» 293 KB
  Проведение преддипломной практики ставит следующие цели: приобретение профессиональных навыков работы менеджера; сбор, систематизация и обработка исходных практических материалов для дипломного проекта. Для достижения целей практики ставятся следующие задачи: ознакомиться с организационной структурой предприятия...
66578. Проблема принципиала-агента, и ее роль в теории фирмы, и в теории государства 382.5 KB
  Используются различные определения лояльности, разнообразные способы взаимодействия между принципалом, получающим выигрыш от лояльности, и агентом, выбирающим быть ли ему лояльным. Рост размеров фирмы влечет за собой увеличение затрат принципала на контроль над действиями возросшего числа агентов
66579. Дирекция социальной сферы филиал ОАО «РЖД» 265.5 KB
  Дирекция руководствуется в своей деятельности Конституцией Российской Федерации, федеральными законами, иными нормативными правовыми актами Российской Федерации, нормативными правовыми актами субъектов Российской Федерации, уставом открытого акционерного общества...