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


 

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

69124. Поняття архітектури комп’ютера. Архітектура комп’ютера фон Неймана. Типи комп’ютерів. Програмне забезпечення 192 KB
  Поняття архітектури обчислювальних систем є одним з основних в інформатиці. Уперше термін «архітектура комп’ютера» був введений фірмою IBM при розробці обчислювальних систем серії IBM 360 і застосований до тих засобів, які може використовувати програміст під час написання програм на рівні машинних команд.
69125. Засоби створення програм. Класифікація мов програмування. Технологія створення программ 74 KB
  Основна функція всіх мов програмування крім машинної полягає у тому щоб надати програмісту засоби абстрагування від характеристик та особливостей апаратного забезпечення на якому виконуватимуться програми. Такий спосіб написання програм називається програмуванням у числових кодах...
69126. Поняття алгоритму й основні алгоритмічні структури. Властивості та способи опису алгоритму. Алгоритмічна структура розгалуження і перетворення 56.5 KB
  Одним з базових понять інформатики є поняття алгоритму. Алгоритм вказує, які операції, пов’язані з обробкою даних, і в якій послідовності треба виконати, щоб отримати розв’язок задачі. Алгоритм розрахований на певного виконавця, з погляду котрого вказівки мають бути елементарними...
69127. Робота у середовищі Borland Pascal 7.0 202.5 KB
  Інтегроване середовище розробки Borland Pascal 7.0 - далі IDE (Integrated Development Environment) Borland Pascal 7.0 - складається з текстового редактора, компілятора, компонувальника, налагоджувача і довідкової системи. Стандартна поставка IDE Borland Pascal 7.0 являє собою...
69128. Словник мови та загальна структура програми. Алфавіт та словник мови 58 KB
  У будь-якій мові програмування програма — це набір зрозумілих компілятору команд. Для створення програм треба знати синтаксис мови, тобто правила запису команд і використання лексичних одиниць мови. Знайомство з мовою розпочнемо з алфавіту.
69129. Прості типи даних. Операції над даними 93 KB
  Поняття типу даних є одним із фундаментальних понять програмування. Тип даних визначає: множину допустимих значень яких може набувати змінна або константа зазначеного типу; множину допустимих операцій що застосовуються до даних певного типу; спосіб зображення даних...
69130. Константи, змінні, вирази. Найпростіші оператори. Процедури введення, виведення 126.5 KB
  Будь-які значення, що використовуються у програмі, - це або значення змінних, або константи. Принципова відмінність між змінними і константами полягає у тому, що для зберігання значень змінних під час виконання програми відводяться ділянки...
69131. Алгоритмічний вибір альтернатив. Вкладеність конструкцій вибору 48 KB
  Під час програмування деяких розгалужень виникає потреба у використанні операторних блоків що розглядатимуться у розділі 3. У цьому ж розділі буде пояснено як орієнтуватися в коді великих програм що містять численну кількість конструкцій вибору та операторних блоків.
69132. Алгоритмічна конструкція повторення. Цикл з передумовою, постумовою, лічильником. Переривання циклу 83.5 KB
  У заголовку циклу зазначається умова завершення циклу а тіло циклу являє собою блок операторів що повторюються. Кожне виконання операторів тіла циклу супроводжується перевіркою умови завершення циклу і називається його ітерацією.