Re: [devel] RSA-2048 всё

[Andrey Savchenko <bircoph@altlinux.org>]

[-- Attachment #1: Type: text/plain, Size: 3155 bytes --]

On Wed, 4 Jan 2023 15:46:20 +0300 Vitaly Chikunov wrote:
> On Wed, Jan 04, 2023 at 07:44:49AM +0300, Andrey Savchenko wrote:
> > https://arxiv.org/pdf/2212.12372.pdf
> > 
> > TL;DR 372 кубит достаточно для взлома RSA-2048 с комбинацией
> > алгоритмов Шора и Шнорра.
> > 
> > Уже существует машина на 443 кубита:
> > https://newsroom.ibm.com/2022-11-09-IBM-Unveils-400-Qubit-Plus-Quantum-Processor-and-Next-Generation-IBM-Quantum-System-Two
> 
> "But I would hope that IBM would demonstrate at least a small handful of
>  perfect logical qubits in Osprey. Maybe six or seven."
> 
> "In my personal view, IBM will need to demonstrate five to eight logical
>  qubits with quantum error correction and six nines of qubit fidelity for
>  logical qubits later this year to maintain any sense of technical
>  credibility.
> 
> Based on reading some IBM papers, the possibilities would be:
> 
>  6 logical qubits. If 65 physical qubits are needed for each logical qubit.
>  7 logical qubits. If 57 physical qubits are needed for each logical qubit."
> 
> "No documented attempt to implement quantum error correction (QEC) or
>  logical qubits."
> 
> > 
> > Эллиптические алгоримы пока что не подвержены, но и для них есть
> > модификация алгоритма Шора, так что подобная оптимизация — лишь
> > вопрос времени. Действующие ассиметричные ГОСТы все на них.
> 
> "Estimates for the number of physical qubits required to break 256-bit
>  ECC in one hour (and these physical qubits would still be to a high
>  engineering specification, perhaps beyond that of Condor) is 317*10^6 per
>  work by Webber et al. Similarly, they quote 13*10^6 physical qubits of
>  this high quality to solve this problem inside a day."

Откуда эти цитата? Они явно некорректны, начиная с того, что
декогеренция наступает намного быстрее, чем за час.

А вообще, вот оценка числа кубит для атаки на ECC и RSA без учёта
алгоритма Шнорра: https://arxiv.org/pdf/quant-ph/0301141.pdf стр. 26

ECC-256: 1500÷1800 кубит 
RSA-3072: ~6144 кубит
(там и для других длин ключей есть значения)

В классическом криптоанализе ECC-256 примерно эквивалентно RSA-
3072. И как видно, кубит для ECC нужно меньше и ECC падёт раньше
RSA.

Даже без алгоритма Шнорра IBM уже в этом году обещает 1000 кубит,
что не так уж далеко от 1500. 

Если смогут адаптировать Шнорра для ECC, как это сделали для
алгоритма Шора в статье выше, то ECC сразу труп.

Best regards,
Andrew Savchenko

[-- Attachment #2: Type: application/pgp-signature, Size: 833 bytes --]