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

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

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

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

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

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

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

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


cryptography public-key-encryption big-o
person Porthos3    schedule 03.10.2011    source источник
comment
Я почти уверен, что все операции будут O (N). В случае A) и B) N представляет собой длину обрабатываемых данных. В случае C N представляет перестановки ключа длины L.   -  person Eric J.    schedule 04.10.2011
comment
Я хотел бы ссылку на какую-то документацию или что-то в этом роде, если это вообще возможно. И реальный ответ, чтобы я мог его принять. ;)   -  person Porthos3    schedule 04.10.2011
comment
Кроме того, меня бы удивило, если бы шифрование/дешифрование было только порядка N. Мое понимание общей безопасной криптографии (которое не является обширным, я могу ошибаться) состоит в том, что каждый зашифрованный символ зависит от нескольких символов в исходном файле (не преобразование символа в символ или простое манипулирование ASCII). Разве это не подразумевало бы, по крайней мере, алгоритм порядка N * log (N)?   -  person Porthos3    schedule 04.10.2011

Ответы (1)


arrow_upward
5
arrow_downward

Стандартные алгоритмы с открытым/закрытым ключом почти никогда не используются для больших входных данных, так как свойства безопасности этих алгоритмов обычно не подходят для массового шифрования. Наиболее распространенная конфигурация заключается в использовании алгоритма открытого/закрытого ключа для шифрования небольшого ключа (постоянного размера, обычно 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 на основе зашифрованных данных, поскольку открытый ключ является гораздо более полезной целью.

person Community    schedule 03.10.2011
comment
Если бы RSA был бы экспоненциальным по размеру ключа, он был бы слишком медленным (и не намного медленнее, чем перебор). Предложение, выделенное на связанной странице, больше похоже на квадратичное (это будет фактор 4) и кубическое (множитель восемь). - person Paŭlo Ebermann; 04.10.2011
comment
сумраквафф 19:07 4 окт 2011 GNFS [is] O(exp((7.1 b)^1/3 (log b)^1/3))) Извиняюсь за тупость, но что такое 'b'? Например, значение открытого ключа или длина открытого ключа в битах (что в приведенном выше вопросе обозначается буквой «L») или что-то совершенно другое? - person TomRoche; 10.07.2014
comment
На странице википедии уверен, что b - это длина ключа в битах. Он довольно хорошо согласуется с переменной n сложности L-нотации. Но хотелось бы и подтверждения. @TomRoche - person Patrick M; 27.04.2015