Насколько плох 3 как общедоступный показатель RSA

Я создаю приложение, в котором мне нужно использовать RSA для шифрования некоторых вещей с использованием открытого ключа. Я хочу, чтобы это шифрование было действительно быстрым. Сначала я попробовал 2048-битный ключ с F4 (= 65537) в качестве показателя степени, но это недостаточно быстро. Итак, сейчас я рассматриваю следующие 2 варианта:

  1. Модуль 2048 бит, e=3
  2. 1024-битный модуль, e=65537

Оба удовлетворяют моим требованиям к производительности, но какой из них обеспечивает лучшую безопасность? Я также должен отметить, что я использую схему заполнения PKCS#1.


person safsaf32    schedule 28.12.2009    source источник


Ответы (7)


Если вы используете случайное заполнение, такое как OAEP в PKCS # 1, большинство (все?) известных недостатков, связанных с использованием низких показателей степени, больше не актуальны.

Также вы пытались использовать e = 17? Нет правила, говорящего, что вы должны выбрать либо 3, либо 65537.

person Mark Byers    schedule 28.12.2009
comment
Если вы возьмете кредитную карту и возведете в степень, вы не сможете заполнить 2048 бит. 17 также не следует использовать. - person Chandra Patni; 28.12.2009
comment
Ты прав. Просто я использую openssl для генерации ключа, и с версии 0.9.8 он не поддерживает использование каких-либо других показателей. - person safsaf32; 28.12.2009
comment
Имейте также в виду, что теоретическое аппаратное устройство под названием TWIRL, описанное Шамиром и Тромером в 2003 году, поставило под сомнение безопасность 1024-битных ключей. В настоящее время рекомендуется, чтобы n имел длину не менее 2048 бит. en.wikipedia.org/wiki/RSA#Security_and_practical_considerations - person Mark Byers; 28.12.2009
comment
Я только что узнал, что ключи openssh (сгенерированные с помощью ssh-keygen) используют e=35 (что на самом деле необычно, поскольку 35 не является простым числом). Это означает, что малая экспонента, вероятно, не такая уж большая проблема (когда используется хорошая схема заполнения). - person safsaf32; 28.12.2009

При условии, что вы используете хорошую схему заполнения, тогда нет никакой известной причины, по которой e=3 должен иметь худшую безопасность, чем любой другой общедоступный показатель. Использование короткой экспоненты имеет проблемы, если вы также не используете хорошую схему заполнения, но проблема больше заключается в схеме заполнения, чем в экспоненте.

«Интуиция» многих исследователей заключается в том, что e=3 не лучше, чем любой другой общедоступный показатель, и e=3 может оказаться немного слабее в какой-то неустановленный момент в будущем, хотя ничто не указывает на это. такая слабость сейчас.

Длина ключа имеет гораздо большее практическое влияние на безопасность. Недавно был взломан 768-битный ключ RSA (это было непросто! Четыре года работы с большими компьютерами и большими мозгами). 1024-битный ключ считается достаточным для краткосрочной перспективы, но долгосрочное использование (например, зашифрованные данные имеют высокую ценность и должны оставаться конфиденциальными в 2030 году) требует чего-то большего, например. 2048 бит. См. этот сайт для получения дополнительной информации о том, как можно оценить криптографическую стойкость и как оценивали различные исследователи и организации.

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

person Thomas Pornin    schedule 22.01.2010

Хотя в настоящее время нет известных атак на использование правильного заполнения, небольшие показатели с большей вероятностью приведут к эксплойтам в случае ошибок реализации. И ошибки реализации, к сожалению, все еще представляют угрозу. Например. это — довольно популярная уязвимость. (Обратите внимание, это для сигнатур. Я просто хочу показать, что даже в коммерческом программном обеспечении могут быть серьезные ошибки.)

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

Если вы выберете небольшой (1024 бит) модуль, вы не можете рассчитывать на то, что ваши данные будут храниться в тайне десятилетиями.

Если вы выберете маленькую экспоненту, вы можете быть более восприимчивы к ошибкам реализации.

В первом случае вы в значительной степени знаете, когда ваши секреты в опасности, так как довольно легко следить за прогрессом, достигнутым в факторинге. (Это, конечно, предполагает, что агентства, которые не публикуют, например, АНБ, не являются вашими врагами). Во втором случае (ошибки реализации) вы не знаете, когда допустили ошибку. Вы могли бы быть в безопасности, используя e=3, или вы могли бы сделать большую ошибку. т.е. в одном случае у вас есть довольно хороший способ оценить свой риск, а в другом — нет.

Поэтому я бы рекомендовал вообще не использовать e=3. Я бы использовал больший запас прочности против тех угроз, которые трудно предсказать, чем те угрозы, которые широко освещаются.

person Accipitridae    schedule 27.01.2010

В своей книге «Практическая криптография' Брюс Шнайер и Нильс Фергюсон предлагают использовать из 3 для подписи и 5 для шифрования. Вы должны перепроверить другие критерии, которые они рекомендуют, чтобы избежать катастроф. В разделе 13.4 рассматривается это (p229ff) и обсуждается не очень сложное требование, согласно которому при n = pq (где p и q — случайные простые числа) ни (p-1), ни (q-1) не могут быть кратны 3 или 5. , Но все же дважды проверьте книгу для деталей.

(Я полагаю, что должно выйти новое издание этой книги. вышел в 2010 году.)

person Jonathan Leffler    schedule 28.12.2009

Чтобы процитировать статью Дона Копперсмита 1997 года «Небольшие решения полиномиальных уравнений и уязвимости RSA с низким показателем степени»:

Шифрование RSA с показателем степени 3 уязвимо, если противник знает две трети сообщения.

Хотя это может не быть проблемой, если используется схема заполнения RSA-OAEP, схема заполнения PKCS#1 (которую использует оператор) уязвима, если используется общедоступная экспонента 3.

person FaST4    schedule 01.02.2018
comment
схема заполнения PKCS # 1 (которую использует оператор) уязвима, если используется общедоступный показатель степени 3. Это не так, как объяснили другие ответы здесь. - person President James K. Polk; 26.06.2018
comment
Ссылка в моем ответе указывает на конкретную атаку. Пожалуйста, покажите, где Дон (и, следовательно, я) ошибся. Повторение ложного утверждения не делает его правдой. - person FaST4; 27.06.2018
comment
Достаточно справедливо, поскольку OP не указал, шифровал ли он ключи или что-то еще, нет гарантии, что он получит достаточно случайного заполнения с помощью PKCS # 1. - person President James K. Polk; 27.06.2018

К вашему сведению, см. немного истории: http://chargen.matasano.com/chargen/2006/9/18/rsa-signature-forgery-explained-with-nate-lawson-part-iv.html

person Yuhong Bao    schedule 08.06.2011

Если ваш показатель степени низкий, а значение m * e ‹ модуля, вы можете просто взять корень eth из зашифрованного текста для расшифровки.

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

Кто-то, кто больше хочет заниматься математикой, может дать вам лучшее объяснение, почему.

person Ritwik Bose    schedule 28.12.2009