Big-O для шифрования с открытым ключом

Question

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

Каковы эти алгоритмы Big-O в отношении шифрования с открытым ключом:

A) Зашифровать файл, состоящий из N символов, ключом длины L

B) Расшифровать тот же файл

C) Типичный алгоритм перебора для взлома зашифрованного файла с N символами ис максимальной длиной ключа L

Любые включенные нотации Big-O для более эффективных алгоритмов взлома шифрования приветствуются.Кроме того, ссылка на то, где можно найти этот материал.

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

Answer 1

Стандартные алгоритмы с открытым / закрытым ключом почти никогда не используются на больших входах, поскольку свойства безопасности этих алгоритмов, как правило, не подходят для массового шифрования.Наиболее распространенная конфигурация - использовать алгоритм открытого / закрытого ключа для шифрования небольшого (постоянного размера, обычно 128 - 256-битного) ключа, а затем использовать этот ключ для симметричного алгоритма шифрования.

При этомЯ буду использовать RSA в качестве контрольного примера для остальных вопросов:

A / B) За исключением генерации ключа, RSA шифрует и дешифрует в O(n) для размера сообщения.(Обратите внимание, что все сообщения должны иметь размер ключа, поэтому сообщения меньшего размера дополняются, а сообщения большего размера должны быть разбиты.) Точная скорость шифрования / дешифрования зависит от алгоритмов, используемых вашей реализацией RSA, но это полиномиальный размер ключа:

http://www.javamex.com/tutorials/cryptography/rsa_key_length.shtml

C) При наличии открытого ключа RSA может быть взломан с помощью факторинга открытого ключа, что в настоящее время лучше всего достигается с помощью GNFS (что составляет O(exp((7.1 b)^1/3 (log b)^1/3))).Я не верю, что есть много работы по взлому RSA на основе зашифрованных данных, так как открытый ключ - гораздо более полезная цель.