Если P = NP, существуют ли криптосистемы, которые требуют n ^ 2 времени для взлома?

Если P равен NP, все еще возможно ли будет спроектировать криптосистему, в которой оптимальный алгоритм криптоанализа занимает, скажем, квадрат времени, занимаемый законными алгоритмами шифрования и дешифрования? Есть ли такие алгоритмы уже существуют?

Да, на самом деле самый первый алгоритм с открытым ключом, который был изобретен за пределами спецслужб, работал именно так! Первое издание , которое предложило криптографию с открытым ключом было «Secure Communications по небезопасным каналам» от Ralph Merkle , где он предложил использовать «головоломку» . Это ключевой протокол соглашения.

1. Алиса отправляет зашифрованных сообщений (называемых головоломками), каждое из которых содержит уникальный идентификатор I i и сеансовый ключ K i , причем ключи для каждого сообщения выбираются из набора из n ключей. Это занимает O ( n ) время ( O ( 1 ) за сообщение).$n$$I_i$$K_i$$n$$O(n)$$O(1)$
2. Боб расшифровывает одно из сообщений грубой силой и отправляет обратно зашифрованный с помощью K i . Это занимает O ( n ) время ( O ( 1 ) на клавишу, умноженное на n возможных клавиш).$I_i$$K_i$$O(n)$$O(1)$$n$
3. Алиса пытается все ключи расшифровать сообщение. Это займет снова время.$O(n)$

Каждая сторона требует только вычислений, но соглядатай , кто хочет найти K я должна попробовать половину головоломки в среднем рассчитать правильный ключ (перехватчик не знает , какое сообщение Боб выбрал для дешифрования), так подслушиватель требует вычисления Θ ( n 2 ) в среднем.$O(n)$$K_i$$\Theta(n^2)$

После того, как Меркл изобрел свои загадки, Диффи и Хеллман опубликовали протокол соглашения о ключах, основанный на проблеме дискретного логарифма . Этот протокол все еще используется сегодня.

Проблема с загадками Меркля или чем-то еще, когда объем работы, выполняемой злоумышленником, только увеличивается как квадрат законной стороны, заключается в том, что для достижения приемлемого запаса прочности требуются огромные размеры ключей и объем вычислений.

В любом случае, не ясно, что простое доказательство того, что P = NP, сделает недействительными существующие криптографические алгоритмы. Если полиномиальное увеличение достаточно велико, на практике это может не иметь большого значения. См. Как нужно менять безопасность, если P = NP? , Можно ли сказать , что если P = NP = АЭС не существует CPA не обеспечить шифрование с открытым ключом? , P = NP и современные криптографические системы ,…

https://en.m.wikipedia.org/wiki/One-time_pad

One Time Pad безопасен вне зависимости от сложности, если ваши числа действительно случайны.

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

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