Я починаю серію легких для читання щоденних дописів про постквантову безпеку. Але я не знаю, скільки днів це триватиме :). Отже, давайте подивимось. ДЕНЬ 1: Алгоритм Шора та квантовий апокаліпсис(?) Більшість нашого стеку безпеки — RSA, ECC, Diffie-Hellman — базується на одному припущенні: факторизація цілих чисел і дискретні журнали є «складними». На класичному кремнії — так. Щоб зламати RSA-2048, потрібно просто більше часу, ніж вік Всесвіту. Але це не фізичний закон. Це обмеження класичних обчислень. У 1994 році Пітер Шор показав, що їх можна ефективно розв'язати на квантовому комп'ютері. Алгоритм Шора не просто переборює клавіші; він використовує квантове перетворення Фур'є (QFT [не квантова теорія поля, лол]) для визначення періоду функції f(x) = a^x mod N. Коли у вас є менструація, у вас є фактори. І коли у вас є фактори, приватний ключ мертвий. Тому що приватний ключ можна відтворити з публічного. Зміна складності — справжній «апокаліпсис». Переходимо від субекспоненціального часу до поліноміального часу O((log N)^3). Ми не говоримо про 10-кратне прискорення; йдеться про перехід від трильйонів років до кількох годин на CRQC. Подібно до RSA, ECC (криптографія еліптичних кривих) також НЕ є безпечною. Завдяки ефективній алгебраїчній груповій структурі розрив 256-бітного ключа ECC фактично потребує менше логічних кубітів, ніж RSA-2048. --- Дякую за прочитання! Завтра ми обговоримо, чому загроза HNDL (збирання зараз-розшифровки-пізніше) означає, що постквантовий перехід має відбутися саме зараз. (Візуально: Пітер Шор)