Рейтинг:9

Является ли шифрование каждого номера отдельно с помощью RSA безопасным?

флаг us

Предположим, что RSA считается «безопасным» методом шифрования. RSA предназначен для кодирования последовательности целых чисел base $27$. Если мы используем $n=pq$ это трудно учесть. Безопасно ли, если мы будем кодировать каждое целое число (букву) отдельно, а не всю фразу один раз?

Редактировать: я не ожидал получить такие отличные ответы. Всем спасибо!

флаг cn
На самом деле это настолько распространенная ошибка новичков, что ее преодоление является одной из классических задач легкого уровня, которые вы можете найти в CTF или вводных курсах.
Jonas avatar
флаг cm
https://xkcd.com/257/ — комикс, показывающий хороший пример
Рейтинг:17
флаг se

Учебник/Обычный RSA не следует использовать для прямого шифрования сообщений. Это связано с тем, что зашифрованный текст является детерминированным на основе сообщения. Учитывая подслушанный зашифрованный текст $c_i$. Эффективной атакой на вашу схему будет:

  1. Получить зашифрованные тексты $c_0, ..., c_{26}$ путем шифрования целых чисел 0-26 с использованием общедоступного модуля $n$ и экспонента $е$.
  2. За $j$ в [0,26], проверьте, $c_i=c_j$. Если мы найдем такой $j$, то ваше исходное сообщение было $j$.
Рейтинг:7
флаг ar

С соответствующей прокладкой (например, ОАЭП), использование RSA для шифрования отдельных байтов, символов или даже битов действительно безопасно*. Конечно, это также невероятно расточительно, так как вы превращаете каждые 8 ​​бит открытого текста в что-то вроде 2048 или более бит зашифрованного текста и тратите много процессорного времени на этот процесс, но неэффективность (обычно) не является проблемой безопасности.

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

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

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

  • $е$-я корневая атака: если публичный модуль $е$ маленький (например, $е = 3$) и открытый текст $м$ (после кодирования в виде числа) также достаточно мал, чтобы $ м ^ е < п $, то классическое шифрование RSA можно обойти, просто рассчитав $е$-й корень зашифрованного текста $c = m^e \bmod n$. Варианты этой атаки также могут работать, если $m^e <kn$ для некоторого небольшого целого числа $к$ (скажем, менее триллиона), просто проверяя грубой силой, если $е$-й корень из $c + jn$ является целым числом для всех $j$ от $0$ вплоть до $к$. Хотя эту атаку легко избежать (например,используя правильное заполнение шифрования и/или используя более крупный общедоступный показатель, такой как общий $e = 2^{16} + 1 = 65537$), как ни странно, многие наивные схемы RSA, разработанные любителями (или предназначенные для преднамеренного взлома, например, в CTF), могут попасть под его действие.


*) В смысле обеспечения конфиденциальности и семантическая безопасность против пассивного подслушивающего злоумышленника, предполагая, что ключ RSA правильно сгенерирован и имеет достаточную длину, чтобы противостоять факторинговым атакам, что генератор случайных чисел, используемый для OAEP, не скомпрометирован и что не было допущено других очевидных ошибок реализации, а также что существование и длина сообщения не является конфиденциальной. Даже в этом случае любая схема в стиле «ECB», шифрующая текст по одному символу за раз, конечно, очень податлива и, следовательно, уязвима для манипуляций со стороны активного злоумышленника.

флаг mg
Я просто влюблен в эту сноску.
Рейтинг:6
флаг in

Хотя RSA не предназначен для шифрования, можно использовать RSA для шифрования. Если кто-то использует TextBook RSA, это будет небезопасно, поскольку шифрование бесплатно, и любой злоумышленник может проверить значения. Мы называем это оракулом шифрования, и он бесплатен в системах с открытым ключом.


Простой оракул шифрования RSA игра...

def Ind_CPA_RSA (противник, цель):
    (e,n,d,...) = generate_RSA_key() // часть генератора ключей

    def RSA_encryption_oracle_PKCS#1_v1.5(открытый текст): //Шифрование оракула
        EM = PKCS#1_v1.5_padding(открытый текст)
        зашифрованный текст = EM^e mod n
        вернуть зашифрованный текст

    для каждого m в Possible_message_space: //запросы
        c = RSA_шифрование_оракул_PKCS#1_v1.5(м)
        если с == цель
            печать (цель)
            вернуть успех
    вернуть отказ

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

В учебнике RSA, если публичный показатель $е=3$ тогда атака кубического корня работает для всех сообщений, таких что $len(m) < \sqrt[3]{n}$.

Для всех других атак статья Дэна Бонеха является хорошей отправной точкой;


$$\textbf{Никогда не используйте Text Book RSA, если знаете, что делаете!}$$


Чтобы быть в безопасности, нужно использовать шифрование RSA с соответствующими дополнениями. ПККС#1 v1.5 (RSAES-PKCS1-v1_5) или ОАЭП (РГАЭС-ОАЭП). Эти дополнения добавляют рандомизацию для достижения вероятностного шифрования.

Каждый использует специальные кодировки для достижения этого, такие как заполнение PKCS # 1 v1.5;

ЭМ = 0x00 || 0x02 || ПС || 0x00 || М.

М это сообщение. PS состоит из части рандомизации

Сгенерировать строку октетов PS длины k - mLen - 3 состоящий из псевдослучайно сгенерированных ненулевых октетов. Длина PS будет не менее восьми октетов.

Например, для 2048-битного RSA; $к = 256$, $mLen=4$ тогда PS длина составляет 249 байт случайного выбора для одного сообщения размером с букву. Поэтому злоумышленник не может проверить значения с помощью оракула шифрования. Остальные атакуют проблема с RSA.

Точно так же OAEP имеет случайность, и доказано, что OAEP имеет безопасность IND-CCA1. Предпочитайте OAEP PKCS#1 v1.5, так как он имеет много атак из-за неправильной реализации.


Если кому-то нужна научная статья о показателях шифрования RSA, вот статья с платным доступом;

Рейтинг:6
флаг cn
Ray

Если каждый символ зашифрован независимо, то каждый раз, когда символ «а» появляется в открытом тексте, он сопоставляется с одним и тем же уникальным токеном любой длины (например, 0x157a05c8). И наоборот, каждый раз, когда вы видите 0x157a05c8 в зашифрованном тексте, он должен сопоставляться с «a» в открытом тексте. Наконец, независимо от длины выходных токенов, если входные данные зашифрованы по одному (8-битному) байту за раз, существует только 256 возможных выходных токенов, столько же, сколько и возможных входных токенов.

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

Ответить или комментировать

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