Факторинг не известен как NP-полный. Этот вопрос задавался о последствиях факторинга, являющегося NP-полным. Любопытно, что никто не спрашивал о последствиях факторинга в P (возможно, потому что такой вопрос тривиален).
Итак, мои вопросы:
- Какими будут теоретические последствия факторинга в P? Как такой факт повлияет на общую картину классов сложности?
- Каковы будут практические последствия факторинга в P? Пожалуйста, не говорите, что банковские операции могут быть под угрозой, я уже знаю это тривиальное следствие.
cc.complexity-theory
cr.crypto-security
conditional-results
factoring
Джорджо Камерани
источник
источник
Ответы:
Теоретическая сложность последствий факторинга в P. практически не имеет следствий сложности. Это означает, что нет веских оснований для того, чтобы факторинг был сложным, кроме того, что до сих пор никто не смог его взломать.
Факторинг за полиномиальное время позволил бы получить квадратные корни над (а также над гораздо более общим классом колец) и дать алгоритмы за полиномиальное время для ряда других теоретико-числовых задач, для которых узкое место в алгоритм в настоящее время факторинг.ZN
Что касается практических последствий, банковские операции, вероятно, не представляют особой проблемы - как только стало известно, что факторинг был в P, банки переключились бы на какую-то другую систему, что, вероятно, вызывало лишь краткий период задержек, пока это происходило. реализованы. Расшифровка прошлых банковских транзакций, вероятно, не вызовет серьезных проблем для банков. Гораздо более серьезная проблема заключается в том, что все сообщения, которые ранее были защищены RSA, теперь могут быть прочитаны.
источник
as soon as it was known that factoring was in P, the banks would switch to some other system
во многом желаемое за действительное. В декабре я обнаружил, что компания, которая ничего не делает, кроме обработки кредитных карт, использует вариант Vigenère с ключом, который короче, чем некоторые прогоны известного открытого текста. Хуже того, технический директор компании не поверил мне, что это небезопасно, пока я не отправил ему код атаки. MD5, несмотря на то, что его широко считают сломанным, все еще активно используется в банковской сфере.RSA является одной из наиболее важных схем шифрования / подписи, которая нарушается, если FACTORING находится в P. Однако есть еще много других. Некоторые (но не все) из них основаны на предположении о том, что различать квадраты и не квадраты по составному числу сложно :
И много других схем. Однако обратите внимание, что схемы, основанные на жесткости дискретного журнала (скажем, протокол Диффи-Хелмана или схема шифрования / подписи Эльгамаля ), будут по-прежнему безопасными.
источник
источник