О криптографии

[gul_kiev]

Ещё из Оливера Сакса. Он невролог, и книжка про невропатологии, но один отрывок может быть любопытен в разрезе современного шифрования. Если всё так (а он всё-таки учёный, который вряд ли будет прибегать к столь грубым фальсификациям), это заставляет вспомнить теории о том, что мозг в своей работе использует квантовые эффекты, и алгоритм Шора,

Comments

[vgarnick]

- совсем не все алгоритмы ассиметричного шифрования основаны на трудностях факторизации
- биткоин как раз основан на эллиптических кривых, а не на трудностях факторизации
- есть алгоритмы ассиметричного шифрования стойкие к взлому на квантовых компьютерах
- таблица простых чисел до 10**10 - это ~455 миллионов чисел, пусть по 1000 чисел на страницу - это будет 455 томов по 1000 страниц - обычное дело для неврологов держать дома пол-тысячи томов простых чисел, и таскать их с собой по больницам

[gul_kiev]

Спасибо, вы правы. Я почему-то думал, что факторизация упрощает нахождение приватного ключа по публичному и для эллиптических кривых, но я заблуждался.

Вот только насчёт стойких к квантовому компьютеру алгоритмов асимметричного шифрования - есть сомнения. Вроде бы, квантовый компьютер в любом случае облегчает взлом или теоретически может его облегчить, но от этого защищаются просто увеличением длины ключа, чем и достигается устойчивость к взлому. Или я и тут ошибаюсь?

[vgarnick]

Да, в реальности в постквантовых алгоритмах ключи на порядки длиннее. Но устойчивость всё-таки алгоритмическая, а не просто из-за длины ключа. Тот случай когда количество переходит в качество. Иначе и RSA можно назвать нестойким на обычных компьютерах и что его устойчивость только из-за длины ключа.

[gul_kiev]

На двоичные порядки, предполагаю.

Я имею ввиду вот что. Насколько мне известно, не найдено стойких к квантовым компьютерам алгоритмов в том смысле, что про эти алгоритмы доказано, что квантовый компьютер не даст преимуществ в расшифровке, или даст не больше какой-то определённой. Вообще, с доказательством стойкости в асимметричном шифровании всё плохо даже без квантовых компьютеров. Поэтому сейчас речь, разве что, о том, что для каких-то алгоритмов шифрования не найдено методов взлома квантовым компьютером со сложностью меньше какой-то, а значит, ключ такой-то длины защитит. От известных алгоритмов.

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

[livelight]

Что самое интересное, он там же добавляет, что как раз считать-то они и не умели толком

[e_1_off]

А с чего вы решили, что они выполняли факторизацию? И с чего вы решили, что если они ее выполняли, то выполняли ее последовательно

[gul_kiev]

> саванты не "рассчитывают" при помощи факторизации, является ли число простым. Они "узнают" простое число

[e_1_off]

Нейросеть не "угадывает" результат, а ищет (и иногда даже находит) корреляции между разными свойствами данных. Если такая коррелляция есть - нейросеть ее со значительной вероятностью найдет

[gul_kiev]

Дело не в том, какие свойства мозга задействуются