Я начинаю серию легких для чтения ежедневных постов о постквантовой безопасности. Но у меня нет представления, сколько дней это продлится :). Так что, посмотрим. ДЕНЬ 1: Алгоритм Шора и Квантовый Апокалипсис(?) Большая часть нашего стека безопасности — RSA, ECC, Диффи-Хеллман — основывается на одном предположении: разложение на множители и дискретные логарифмы "сложны". На классическом кремнии это так. Чтобы взломать RSA-2048, вам нужно просто больше времени, чем возраст вселенной. Но это не физический закон. Это ограничение классических вычислений. В 1994 году Питер Шор показал, что их можно эффективно решить на квантовом компьютере. Алгоритм Шора не просто перебирает ключи; он использует Квантовое Преобразование Фурье (QFT [Не квантовая теория поля, лол]), чтобы найти период функции f(x) = a^x mod N. Как только у вас есть период, у вас есть множители. А как только у вас есть множители, закрытый ключ мертв. Потому что закрытый ключ можно восстановить из открытого ключа. Сдвиг сложности — это настоящий "апокалипсис". Мы переходим от субэкспоненциального времени к полиномиальному времени O((log N)^3). Мы не говорим о 10-кратном ускорении; мы говорим о переходе от триллионов лет к нескольким часам на CRQC. Подобно RSA, ECC (криптография на эллиптических кривых) также НЕ безопасна. Из-за своей эффективной алгебраической структуры группы, взлом 256-битного ECC ключа на самом деле требует меньше логических кубитов, чем RSA-2048. --- Спасибо за чтение! Завтра мы обсудим, почему угроза HNDL (собрать-сейчас-расшифровать-позже) означает, что переход к постквантовой безопасности должен произойти сейчас. (Визуализация: Питер Шор)