[devel] RSA-2048 всё

[devel] RSA-2048 всё

[Andrey Savchenko]

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

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

Эллиптические алгоримы пока что не подвержены, но и для них есть
модификация алгоритма Шора, так что подобная оптимизация — лишь
вопрос времени. Действующие ассиметричные ГОСТы все на них.

Самое неожиданное, что решёточные постквантовые алгоритмы тоже
закопали, т.к. научились использовать шумящие кубиты.

Best regards,
Andrew Savchenko

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

Re: [devel] RSA-2048 всё

[Alexey V. Vissarionov]

On 2023-01-04 07:44:49 +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

Вообще-то для RSA уже лет 5 тому как минимальной длиной считается
4096, а рекомендуется 8192.

 > Эллиптические алгоримы пока что не подвержены, но и для них
 > есть модификация алгоритма Шора, так что подобная оптимизация
 > — лишь вопрос времени. Действующие ассиметричные ГОСТы все
 > на них.

В принципе, направление противодействия "вотпрямщас" понятно:
увеличение разрядности ценой времени выполнения и памяти на
обычных компутерах - для квантовых вычислителей это означает
экспоненциальный рост стоимости (в рублях) оборудования и
необходимого для работы электричества.

Но, разумеется, это не решает проблему в целом.

 > Самое неожиданное, что решёточные постквантовые алгоритмы
 > тоже закопали, т.к. научились использовать шумящие кубиты.

Вообще красота...


-- 
Alexey V. Vissarionov
gremlin ПРИ altlinux ТЧК org; +vii-cmiii-ccxxix-lxxix-xlii
GPG: 0D92F19E1C0DC36E27F61A29CD17E2B43D879005 @ hkp://keys.gnupg.net

Re: [devel] RSA-2048 всё

[Vitaly Chikunov]

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."

> 
> Самое неожиданное, что решёточные постквантовые алгоритмы тоже
> закопали, т.к. научились использовать шумящие кубиты.
> 
> Best regards,
> Andrew Savchenko



> _______________________________________________
> Devel mailing list
> Devel@lists.altlinux.org
> https://lists.altlinux.org/mailman/listinfo/devel

Re: [devel] RSA-2048 всё

[Andrey Savchenko]

[-- 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 --]

Re: [devel] RSA-2048 всё

[Andrey Savchenko]

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

On Wed, 4 Jan 2023 12:41:15 +0300 Alexey V. Vissarionov wrote:
> On 2023-01-04 07:44:49 +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
> 
> Вообще-то для RSA уже лет 5 тому как минимальной длиной считается
> 4096, а рекомендуется 8192.

Поддерживаю. Давайте тогда работать над переведением инфраструктуры
на RSA-8192 или выше в обозримом будущем: ключи разработчиков
(GnuPG-2 умеет RSA-8192), сборочницы, ssh-ключи (тут вообще нет
проблем). Даже в GnuPG-1 портирована поддержка RSA-8192. Так что
это больше вопрос административный: обновления ключей и проверок
сборочницы (сейчас она не разрешает 8192, насколько я помню).

Best regards,
Andrew Savchenko

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

Re: [devel] RSA-2048 всё

[Alexey Sheplyakov]

Здравствуйте!

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

Проще купить ключ у владельца за 1% стоимости этой игрушки.
А к особо упорным прислать пару мордоворотов с паяльником.
Что характерно - способ работает независимо от длины ключа
и алгоритма шифрования.

Всего доброго,
	Алексей

Re: [devel] RSA-2048 всё

[Paul Wolneykien]

9 января 2023 г. 18:33:55 GMT+03:00, Alexey Sheplyakov <asheplyakov@basealt.ru> пишет:
>Здравствуйте!
>
>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
>
>Проще купить ключ у владельца за 1% стоимости этой игрушки.
>А к особо упорным прислать пару мордоворотов с паяльником.
>Что характерно - способ работает независимо от длины ключа
>и алгоритма шифрования.

Что характерно, обе указанные атаки нельзя провести, не поставив в известность владельца ключа...

Re: [devel] RSA-2048 всё

[Vitaly Chikunov]

On Sat, Jan 07, 2023 at 01:31:30PM +0300, Andrey Savchenko wrote:
> 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 с комбинацией
> > > алгоритмов Шора и Шнорра.

https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html

Re: [devel] RSA-2048 всё

[Ilya Kurdyukov]

Какая вероятность что квантовые компьютеры смогут найти ключи к 
популярным криптовалютам и эти криптопузыри наконец вымрут?

Re: [devel] RSA-2048 всё

[Andrey Savchenko]

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

On Sun, 29 Jan 2023 20:54:52 +0700 Ilya Kurdyukov wrote:
> Какая вероятность что квантовые компьютеры смогут найти ключи к 
> популярным криптовалютам и эти криптопузыри наконец вымрут?

Тут всё зависит от конкретной криптовалюты и реализации её
кошельков.

Если говорить про биткоин, то стойкость блокчейна основана на
стойкости хеша sha256. С одной стороны, квантовые компьютеры не
сильно помогут сломать хеши: лучшее из мне известного, это сведение
N операций перебора к sqrt(N) с помощью алгоритма Гровера. Но с
другой стороны, sha1 уже сломан и sha256 отличается только длиной.

Ассиметричная криптография там используется в защите приватного
ключа кошелька. Судя по документации, там ecdsa 256-bit, что
с одной стороны пока что не сломано, с другой стороны имеет все
шансы стать руинами раньше длинных rsa.

Так что я думаю, что дни биткоина сочтены.

Best regards,
Andrew Savchenko

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