> Насколько я помню, уже много лет как, США выпустили документ в котором
> в связи с квантовой угрозой рекомендуется отказаться от элептических кривых и
> использовать обычный RSA с длинным размером ключа.

Чокаво? RSA первое что будет раздолбано если (квантовый) алгоритм Шора работает. Потому что изначально как раз про факторизацию чисел и сформулировано. RSA и без этого то пару раз хорошенько шатали на этом, достаточно вспомнить атаку на мелкие экспоненты. Изначально не было сказано что так нельзя. И вроде все работало. А потом это с треском разломали и стало можно подделиывать дофига секурбутов и сертификатов, лол. Более того - у RSA возможны "неудачные ключи" и проч. Отсев таковых сильно отдельный квест. В этом смысле 25519 куда проще, любой 32-байтовый рандом является валидным ключом, из него делается публичный. Конечно брать приватный ключ вида key[32] = {0} не совсем удачная идея, атакующий может догадаться до него, но тут уже вопрос в не очень рандомном рандоме, 32 ноля - не очень случайное число :)

Однако в конечном итоге вон то может затронуть весь класс проблем P != NP. Эллиптика в него тоже в конечном итоге входит. Как и многие иные варианты алгоритмов диффи-хеллмана (если не все известные). И потому есть обоснованные опасения что и там возможны квантовые версии алгоритмов сильно повышающие эффективность атак с тем же результатом что и для RSA, т.е. аннулирование схемы.

Для симметричного крипто это не очень работает: хучший сценарий для симметричных алго оценивается как ополовинивание длины ключа. Если 128 битное крипто с сложностью 2^64 пролетит, то вот 256-битное... 2^128 операций слишком дофига, это удержится. Поэтому симметричное крипто с 256-бит ключом (или более) таки не боится квантовых компьютеров даже в теории. Если конечно устойчивое по другим критериям, RC4 намекает что и обычные компьютеры могут раскрякать за минуту - если отклонения от идеала есть.

> До того момента как не будут разработаны устойчивые к квантам алгоритмы.

В случае point-to-point VPN можно юзать PSK с симметричным крипто - и оно удержится хоть там что. Свойства частично деградируют (может отвалиться PFS или plausible deniabilty) - но атакующий собравший траф его все же не расшифрует.

> Думаю у них там в дефенс не дураки сидят.

Эти недураки помнится dual EC DRBG помнится через нист пытались как стандарт протолкать. И еще мутные эллиптические кривые от NIST - выбранные хз как, кем, и без мощного публичного аудита независимыми криптографами. За что собссно NISTовская эллиптика и выпала из фавора. Особенно после обнаружения что Dual EC DRBG оказывается с бэкдором.