RSA (криптосистема)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 08:56, 12 мая 2016.

__NUMBEREDHEADINGS__



Основные утверждения

Самая известная и наиболее используемая криптосистема. В РФ используется практически везде, например, в банкоматах, терминалах оплаты, банковских системах.

Зашифрование

Также система используется, как правило, для шифрования ключей. Трудоемкость возведения в степень

Расшифрование

Трудоемкость = , то есть полиномиальна[1], однако достаточно сложная.

TemplateTheoremIcon.svg Теорема Утверждение
Если связаны соотношением:

, где - Функция Эйлера

то выполняется соотношение:

(в этом случае преобразования корректны)
Доказательство

Если выполняется :


TemplateExampleIcon.svg Пример Замечание
Если выбрать произвольный ключ зашифрования е, то для нахождение d надо решить , то есть сравнение первой степени ; оно имеет решение НОД


RSA - блочная экспоненциальная симметричная система. Стойкость: основа - секретные ключи и открытый текст. В ГОСТ ключи зашифрования совпадают с ключами расшифрования, в RSA они связаны.

Криптосистемы типа RSA. Схема Полига - Хеллмана

Модуль - большое простое число.

- открытый ключ зашифрования, - закрытый ключ зашифрования.

Эта схема была известна до появления RSA.

Предложили взять - модуль как произведение двух больших простых чисел.Законный пользователь знает и расшифровывает все сообщения, которые к нему приходят. Найти никто не может быстрее, чем просто раскладывая на множители. Если бы факторизовали на :

расшифрование всего. Если есть только - сложная задача.

(злоумышленник) знает , хочет извлечь корень - пока не найдено способа быстрее. чем разложение на простые множители основа криптосистемы открытого шифрования.

TemplateExampleIcon.svg Пример Замечание
Однонаправленная функция с секретом: . При знании дополнительной информации, т.е. p и q, можно найти прообраз за полиномиальное время.


Задача факторизации имеет субэкспоненциальную [2] сложность.

- будет ли это что-то менять? Вероятность найти не взаимно простые с модулем точки: . Работает с очень большими простыми числами (порядка 1000 бит) очень маленькая.

Рассмотрим корректность . Это схема открытого шифрования; теперь рассмотрим схему цифровой подписи.

TemplateExampleIcon.svg Пример Замечание
Можно использовать такое соотношение: , - функция Кармайкла


Для этой функции справедливы теоремы Кармайкла:

Рассмотрим реализацию. Сначала разделим

В итоге уменьшился размер, уменьшилась степень возведения.

Теперь надо решить такое сравнение:

Все это - следствия Китайской теоремы об остатках.

(так как )

Таким образом, сложность меньше, чем

Атаки на схему RSA

Атака при малой энтропии открытого текста

небольшое множество ОТ(например, тексты платежей).

Противник имеет:

Считаем находим М.

Значит, энтропию надо повышать. Для этого существуют различные способы, например, схема OAEP-RSA(optimal Asymmetric Encryption Padding).

Преобразование случайный вектор.

Точно также с ЦП - перед подписью надо добавить случайный вектор. Параметры: . Генерация ЦП:

- то, что будет подписывать.

Генерация простых чисел

- проверяем, выполняется ли. Если , то можно опробовать правую часть, прибавить к ней n и проверить, является ли квадратом. Поэтому требуется, чтобы

Факторизация

Раскладывает . Самая естественная атака, позволяет полностью заменить законного получателя. Табличная (ЕС2000):

Decimals Date Algorythm MIPS, years
RSA-110 1992 QS 75
RSA-129 1994 QS 5000
RSA-130 1996 NFS 1000
RSA-140 1999 NFS 2000
RSA-155 1999 NFS 5000

QS - Quadratic Sieve(Квадратичное решето)

NFS - Number Field Sieve

Формула, полученная из таких таблиц(год, в котором будет разложено число из D знаков(десятичных)):

Субэкспоненциальная оценка:

где n - число, которое факторизуется.

TemplateTheoremIcon.svg Теорема Утверждение
Доказательство

очевидно (если умеем факторизовать, то и сразу вычислим)

Итого, зная находим .


TemplateLemmaIcon.svg Лемма «Утверждение»


Бесключевое чтение

Дано:

Хотели получить многочлен для нахождения открытого текста.

Атака по времени (Timing Attack)

Если знаем, сколько вычисляется функция, можно предположить, много там 1 или мало.

Дискретное логарифмирование (Discrete Logarithm Attack)

Атака Винера (Wiener Attack)

TemplateLemmaIcon.svg Лемма «Утверждение»
- несократимая дробь: , то Одна из подходящих дробей для разложения в непрерывную дробь


TemplateTheoremIcon.svg Теорема Утверждение
Пусть
Доказательство

Итого,


Атака Боне и Дюрфи (Boneh, Durfee Attack)

подняли границу по сравнением с Винером.

Малые значения открытой экспоненты

Если е мало, то также легко извлекается корень. На практике используют

Атака Бляйхенбахера (Bleichebacher Attack)

Схема с общим модулем

Циркулярная связь:

Ц

Используется несколько раз, поскольку найти хорошие трудно.

НО: можно найти с помощью расширенного алгоритма Евклида

Метод DFA (Differential Fault Analysis)

Возник в 1997 году. Впервые был применен А. Шамиром (А. Shamir) против DES, затем применялся против ЦП RSA.

Дано: - открытый текст, - цифровая подпись.

ищем (по Китайской теореме об остатках).

Проверка цифровой подписи заключается в проверке выполнения равенства .

Пусть устройство делает ошибку, вычисляет не а и при этом одно и то же. Тогда:

так как вычислено корректно. Следовательно:

Однако: а так как то можно вычислить НОД

Таким образом, получен секретный параметр можно подписываться вместо законного пользователя.

Требования к выбору параметров схемы RSA

  1. схемы с одинаковыми длинами называются сбалансированными;
  2. Все числа: - должны иметь простые делители большой длины (~256 бит на сегодняшний день); если указанные величины не имеют простых делителей, то их можно относительно легко факторизовать.
  3. Чтобы бесключевое чтение не привело к успеху, надо выбрать: НОК где мультипликативный порядок. Данное условие выполняется, если: т.е. имеют простые делители, так, что: бит, а также
  4. Ограничение на (против атаки Винера и атаки Боне и Дюрфи).

Применение схемы RSA

Подпись вслепую (Blind Signature)

Схема RSA хороша своей многогранностью. Например, она применяется в схеме "Подпись вслепую".

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

Подпись вслепую состоит из нескольких этапов:

  1. Initializaion - подписывающий говорит каким видом подписи он будет подписывать документы;
  2. Requesting - подготовка запроса и запрос подписи - запрашивающий заменяет документ не зная по восстановить невозможно;
  3. Signing - передается на подпись и подписывается;
  4. Extracting - выделяем из полученной информации подпись.

Схема на базе RSA построена следующим образом:

Для того, чтобы это работало, необходимо

Cистема тайного электронного голосования (e-Voting)

Требования к системе голосования:

  1. Только имеющий права голоса может голосовать;
  2. Голосовать можно не более одного раза;
  3. Никто не может определить, кто конкретно за кого голосовал;
  4. Никто не может подменить чей-либо выбор;
  5. Проверка (ее сложно организовать);
  6. Кто голосовал.

Протокол

  1. Генерируется большое случайной число, добавляются туда "за", "против". Запечатываем его в конверт, хешируем документы, отправляем в избирательную комиссию.
  2. Избирательная комиссия проверяет подписи, подписывает вслепую.
  3. Получаем конверт, распечатываем его, смотрим все "за" и "против", подсчитываем голоса.
  4. Публикуем список "За" - "Против".

Протокол электронных платежей

Dfa-1.PNG

Но есть проблемы.

  1. Проблема повторной траты (с одним чеком прийти к двум продавцам) - решается так: при оплате один раз анонимность плательщика сохраняется, при повторной оплате анонимность уже пропадает.
  2. Можно поставить любую сумму, ведь банк подписывает вслепую. Решение: Cut-and-Choose-Technique
Dfa-2.PNG
  1. Класс P — Википедия https://ru.wikipedia.org/wiki/Класс_P
  2. Экспоненциальная сложность — Википедия https://ru.wikipedia.org/wiki/Экспоненциальная_сложность