[RSA] почему схема с шифрованием данных напрямую не является «практически надёжной»?

Question

[one_question]

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

Данная схема на практике не используется по причине того, что она не является практически надёжной (semantically secured). Действительно, односторонняя функция E(m) является детерминированной — при одних и тех же значениях входных параметров (ключа и сообщения) выдаёт одинаковый результат —, а это значит, что не выполняется необходимое условие практической (семантической) надёжности шифра.

Можете объяснить что это значит?

Answer 1

[Rsa97]

Пусть стороны для шифрования постоянно используют одну и ту же пару ключей (не обязательно RSA), а мы перехватываем их трафик. Даже не зная самих ключей мы можем заметить, что каждый раз, когда Алиса начинает диалог с Бобом, к нам попадает один и тот же зашифрованный блок. Можно предположить, что это приветствие, и перебрав варианты "Привет", "Здравствуй" и т.п., получить возможные ключи, которые проверяются на других блоках.
Именно поэтому обязательной частью шифрованного обмена является периодическая смена ключей, и фиксированные персональные ключи используют только для обмена неповторяющимися сеансовыми ключами.

Comments

[one_question]

Но ведь это обычный перебор ключей. Едва ли это имеет смысл, особенно с 2048-битным ключом.
Т.е. я правильно понимаю, что никакого теоретического способа ослабить шифрование или подобрать ключ таким образом не существует?

[one_question]

С 2048-битным ключом RSA, например.

[Rsa97]

one_question: Это не простой перебор. Кроме перехваченного зашифрованного блока мы можем предположить его исходное содержимое. Имея такую пару и зная алгоритм шифрования найти ключ гораздо проще, чем имея только зашифрованный блок.
Ну и, поскольку ключ остаётся неизменным долгое время, у нас есть это самое время на поиск ключа. А однажды найденным ключом можно будет расшифровать как уже перехваченный трафик, так и то, что удастся перехватить в дальнейшем.

[Deerenaros]

Rsa97: Простите, а каким раком симметричный шифр обходит оное?

[Deerenaros]

Rsa97: Про "любой" тоже нескромное замечание - McEliece и вовсе рандомизирует выход.

[Saboteur]

Deerenaros: >Простите, а каким раком симметричный шифр обходит оное?
Грубо говоря примерно так:
В процессе создания сеанса, генерится новый рандомный ключ для этого сеанса.
Именно он шифруется RSA и передается, с противоположной стороны расшифровывается парным ключом, и обе стороны имеют этот сеансовый ключ, дальнейший обмен данных шифруется сеансовым ключом. Таким образом, злоумышленник не может перехватить повторяющиеся данные, на основании которых упростить задачу подбора.

[Deerenaros]

Saboteur: Ну так это на уровне сессий. Вообще тут не причём, сессия может быть и условно-вечной. Что до упрощения перебора, то для взлома RSA потребуется в порядках 2^1000 бит данных, что ну ни разу не подъёмно. Иначе мощность вероятных данных настолько огромная, что возможен практически любой осмысленный текст.

[Rsa97]

Deerenaros: Симметричный ключ может задаваться не только в начале сессии, но и через определённое количество сообщений или через заданное время.

[Deerenaros]

Rsa97: Ну... Не то, чтобы сомнительно, просто тогда мы получаем много сообщений с одним и тем же ключём. То есть их количество возрастает на порядок, а соответственно и срок годности уменьшается на порядок. Тем более, что передаётся только сервисная информация и можно произвести атаку на структуру. Другими словами не просто так безопасностью занимаются профессионалы ;) Хотя, по нику, может Вы из оных.

Answer 2

[Deerenaros]

С моей колокольни я вижу бред. На самом деле RSA не используется для прямого шифрования ровно по двум причинам.

Дорого. Дороговизна обусловлена высокой стоимостью операций. Взятие по модулю и возведение в степень - не самые простые операции для CPU, сложнее (из примитивных) разве что деление. К тому же, используя самые эффективные алгоритмы, сложность шифрования где-то O(n log(n)), возможно даже выше, но даже так на огромных данных логарифм портит всю малину. Как следствие - низкая производительность. Тут даже специализированные схемы не очень помогает, ибо их сложность слишком большая и стоимость производства - также высокая. Можно вспомнить про кредитные карты, которые есть почти у всех, но их производительность очень низкая, просто её хватает, но едва.

Неудобно. Все операции происходят в поле по очень и очень большому простому числу. Это не делает ей никакой чести, абсолютно никакой (некоторое число атак даже эксплуатируют эту проблему). Сделать полное отображение 2048 бит в поле огромного числа банально невозможно, поэтому данные просто обрубают. Учитывая просто громаднейший размер ключа это и незаметно, но проблема всё равно существует.

В любом случае, смысл использовать один и тот же ключ - отсутствует. Абсолютно аналогичный результат можно получить, используя симметричный шифр. Намного интереснее, если ключ меняется от блока к блоку, тогда можно невозбранно получить стойкость одноразового блокнота (точнее - генератора случайных чисел, да и число простых чисел всё-таки ограничено, но это мелочи). Так что это полный бред, что прямой RSA - бесполезен. Но предыдущие две причины практически полностью решили его судьбу, как шифр для симметричного ключа или хеша.

Answer 3

[Владимир Дубровин]

Проиллюстрировать можно примерно так: представьте что у вас есть огромный файл из нулей, в котором имеется очень малое (в процентном соотношении) количество единиц. Напрямую зашифровав блоки RSA вы легко увидите блоки состоящие только из нулей, и блоки содержащие единицы. А если распределение единиц не равномерно и известно, то накопив некоторую статистику вы сможете различать в какой позиции блока находится единица и сможете полностью декодировать текст.
Поэтому для шифрования большого объема данных обычно используются потоковые шифры (или блочные в специальном режиме, защищающими от подобных атак - гаммированние с обратной связью) с уникальной гаммой (ключом). А с помощью RSA шифруются только либо одноразовые уникальные случайные либо не секретные данные.

Comments

[Deerenaros]

А в чём проблема сделать обратную связь для RSA? Хотя да, я тут же бред горожу. Давайте лучше переместимся на пару тысяч лет вперёд и увидим повсеместное использование кодовых ассиметричных шифров.

[Владимир Дубровин]

Deerenaros: тем что только обратной связи не достаточно, тем более при большом размере блока. Необходима гамма, а это практически и есть случайный симметричный ключ. В результате и получается то, что используется сейчас - симмаетричный ключ кодируется RSA, а данные кодируются симметричным ключом.

[Deerenaros]

Владимир Дубровин: Ну это банально неправильный подход. Есть тот же RSAES-OAEP, который вполне себе используется для небольших сообщений. Ну, а разбить большое сообщение на небольшие - дело техники. А для паддинга - SHA-256 или даже bcrypt какой, вместе с каким-нибудь генератором Маска. И не нужны никакие зацепления, стойкость высокая, а ключ - один. И никакой фантастики, секьюрность даже выше, и ассиметричность позволяет творить организационные чудеса, однако она, конечно, много много много медленнее, да и на сообщение на четверть увеличивается. Как всегда - экономика правит балом. Ну и ключей мало, тоже определённая проблема. Не то, чтобы их совсем мало, всё таки ключи чрезвычайно жирные, однако их мощность множества простых чисел, очевидно, много-много ниже мощности множества любых чисел. Насколько - это уже проблема Римана, до сих пор не решённая.

[Владимир Дубровин]

Deerenaros: да, все так, но суть опять в том, что к шифруемым данным добавляется случайная составляющая, потому что шифрование напрямую не является практически надежным.

[Deerenaros]

Владимир Дубровин: Нуууууу. Товарищ, думается мне это ложь, да ещё и наглая. Впрочем, вся криптография - ложь, да ещё и наглая. Вот есть абсолютно стойкий шифр. Но их использовали только советы с американцами, ну может до сих пор используют ;) А так, понятное дело стойкость ограничивается областью перебора, причём путём хитрых и не очень манипуляций его можно сокращать. Вот и вся наука, довольно простая, но рутинная. Собственно, здесь и ключи больше, и простые числа никто не знает как искать, а даже если и знают - потенциально область перебора всё равно очень большая (ну даже если 2^200 простых среди 2048 битовых чисел, которых в общем-то 2^2048 - всё не так плохо; это число не просто космическое, его даже в астрономии не используют). Да и случайность никак горя криптоаналитиков не разбавляет - банально нет понимания с какой вообще стороны подойти. А ведь это сверху можно ещё каким-нибудь кузнечиком (ни ключ, ни производительность сравнительно не упадёт) обмазать, там совсем будет страх и ненависть в лаборатории.

[Владимир Дубровин]

Deerenaros: ложь в чем? Использовать SHA-256 для паддинга нельзя, это не снимет проблему, т.к. на одинаковых данных получится одинаковый паддинг.

[Deerenaros]

Владимир Дубровин: Так используется не только SHA-256. Оный нужен для решения проблемы с нулями. Алсо, для атаки на "одинаковые данные" потребуется овердохрена закрытого текста, да и хоть что-то про него всё равно потребуется знать (впрочем, с засильем стандартов сделать структурную атаку не является достаточно сложным).

А вот ещё вариант - кодируем энтропийным кодом (арифметическим, например), после чего используем простейший перестановочный шифр. Любой криптоаналитик будет в таком диком замешательстве что ну ничего не сможет сделать.