Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 08:56, 12 мая 2016.
__NUMBEREDHEADINGS__
Основные утверждения
Самая известная и наиболее используемая криптосистема. В РФ используется практически везде, например, в банкоматах, терминалах оплаты, банковских системах.
Зашифрование
Также система используется, как правило, для шифрования ключей. Трудоемкость возведения в степень
Расшифрование
Трудоемкость = , то есть полиномиальна[1], однако достаточно сложная.
 Теорема Утверждение
|
Если связаны соотношением:
, где - Функция Эйлера
то выполняется соотношение:
(в этом случае преобразования корректны)
|
Доказательство
|
Если выполняется :
|
|
 Пример Замечание
|
Если выбрать произвольный ключ зашифрования е, то для нахождение d надо решить , то есть сравнение первой степени ; оно имеет решение НОД
|
|
RSA - блочная экспоненциальная симметричная система.
Стойкость: основа - секретные ключи и открытый текст. В ГОСТ ключи зашифрования совпадают с ключами расшифрования, в RSA они связаны.
Криптосистемы типа RSA. Схема Полига - Хеллмана
Модуль - большое простое число.
- открытый ключ зашифрования, - закрытый ключ зашифрования.
Эта схема была известна до появления RSA.
Предложили взять - модуль как произведение двух больших простых чисел.Законный пользователь знает и расшифровывает все сообщения, которые к нему приходят. Найти никто не может быстрее, чем просто раскладывая на множители. Если бы факторизовали на :
расшифрование всего. Если есть только - сложная задача.
(злоумышленник) знает , хочет извлечь корень - пока не найдено способа быстрее. чем разложение на простые множители основа криптосистемы открытого шифрования.
 Пример Замечание
|
Однонаправленная функция с секретом: . При знании дополнительной информации, т.е. p и q, можно найти прообраз за полиномиальное время.
|
|
Задача факторизации имеет субэкспоненциальную [2] сложность.
- будет ли это что-то менять? Вероятность найти не взаимно простые с модулем точки: . Работает с очень большими простыми числами (порядка 1000 бит) очень маленькая.
Рассмотрим корректность . Это схема открытого шифрования; теперь рассмотрим схему цифровой подписи.
 Пример Замечание
|
Можно использовать такое соотношение: ,
- функция Кармайкла
|
|
Для этой функции справедливы теоремы Кармайкла:
Рассмотрим реализацию. Сначала разделим
В итоге уменьшился размер, уменьшилась степень возведения.
Теперь надо решить такое сравнение:
Все это - следствия Китайской теоремы об остатках.
(так как )
Таким образом, сложность меньше, чем
Атаки на схему 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 - число, которое факторизуется.
 Теорема Утверждение
|
|
Доказательство
|
очевидно (если умеем факторизовать, то и сразу вычислим)
Итого, зная находим .
|
|
 Лемма «Утверждение»
|
|
|
Бесключевое чтение
Дано:
Хотели получить многочлен для нахождения открытого текста.
Атака по времени (Timing Attack)
Если знаем, сколько вычисляется функция, можно предположить, много там 1 или мало.
Дискретное логарифмирование (Discrete Logarithm Attack)
Атака Винера (Wiener Attack)
 Лемма «Утверждение»
|
- несократимая дробь: , то Одна из подходящих дробей для разложения в непрерывную дробь
|
|
 Теорема Утверждение
|
Пусть
|
Доказательство
|
Итого,
|
|
Атака Боне и Дюрфи (Boneh, Durfee Attack)
подняли границу по сравнением с Винером.
Малые значения открытой экспоненты
Если е мало, то также легко извлекается корень. На практике используют
Атака Бляйхенбахера (Bleichebacher Attack)
Схема с общим модулем
Циркулярная связь:
Ц
Используется несколько раз, поскольку найти хорошие трудно.
НО: можно найти с помощью расширенного алгоритма Евклида
Метод DFA (Differential Fault Analysis)
Возник в 1997 году. Впервые был применен А. Шамиром (А. Shamir) против DES, затем применялся против ЦП RSA.
Дано: - открытый текст, - цифровая подпись.
ищем (по Китайской теореме об остатках).
Проверка цифровой подписи заключается в проверке выполнения равенства .
Пусть устройство делает ошибку, вычисляет не а и при этом одно и то же. Тогда:
так как вычислено корректно. Следовательно:
Однако: а так как то можно вычислить НОД
Таким образом, получен секретный параметр можно подписываться вместо законного пользователя.
Требования к выбору параметров схемы RSA
- схемы с одинаковыми длинами называются сбалансированными;
- Все числа: - должны иметь простые делители большой длины (~256 бит на сегодняшний день); если указанные величины не имеют простых делителей, то их можно относительно легко факторизовать.
- Чтобы бесключевое чтение не привело к успеху, надо выбрать: НОК где мультипликативный порядок. Данное условие выполняется, если: т.е. имеют простые делители, так, что: бит, а также
- Ограничение на (против атаки Винера и атаки Боне и Дюрфи).
Применение схемы RSA
Подпись вслепую (Blind Signature)
Схема RSA хороша своей многогранностью. Например, она применяется в схеме "Подпись вслепую".
Определить по исходный текст нельзя, но если подписать , то можно потом проверить, кому и когда подписывался .
Подпись вслепую состоит из нескольких этапов:
- Initializaion - подписывающий говорит каким видом подписи он будет подписывать документы;
- Requesting - подготовка запроса и запрос подписи - запрашивающий заменяет документ не зная по восстановить невозможно;
- Signing - передается на подпись и подписывается;
- Extracting - выделяем из полученной информации подпись.
Схема на базе RSA построена следующим образом:
Для того, чтобы это работало, необходимо
Cистема тайного электронного голосования (e-Voting)
Требования к системе голосования:
- Только имеющий права голоса может голосовать;
- Голосовать можно не более одного раза;
- Никто не может определить, кто конкретно за кого голосовал;
- Никто не может подменить чей-либо выбор;
- Проверка (ее сложно организовать);
- Кто голосовал.
Протокол
- Генерируется большое случайной число, добавляются туда "за", "против". Запечатываем его в конверт, хешируем документы, отправляем в избирательную комиссию.
- Избирательная комиссия проверяет подписи, подписывает вслепую.
- Получаем конверт, распечатываем его, смотрим все "за" и "против", подсчитываем голоса.
- Публикуем список "За" - "Против".
Протокол электронных платежей
Но есть проблемы.
- Проблема повторной траты (с одним чеком прийти к двум продавцам) - решается так: при оплате один раз анонимность плательщика сохраняется, при повторной оплате анонимность уже пропадает.
- Можно поставить любую сумму, ведь банк подписывает вслепую. Решение: Cut-and-Choose-Technique
- ↑ Класс P — Википедия https://ru.wikipedia.org/wiki/Класс_P
- ↑ Экспоненциальная сложность — Википедия https://ru.wikipedia.org/wiki/Экспоненциальная_сложность
ISSN 2542-0356
Следуй за Полисом
Оставайся в курсе последних событий
Лицензия
Если не указано иное, содержание этой страницы доступно по лицензии Creative Commons «Attribution-NonCommercial-NoDerivatives» 4.0, а примеры кода – по лицензии Apache 2.0. Подробнее см. Условия использования.