LINUX.ORG.RU
ФорумTalks

Квантовый брутфорс

 ,


0

2

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

Вот объясните. Если я в качестве ключа шифрования использую роман Федора Михайловича Достоевского «Преступление и наказание», 176 тысяч слов. Ну, либо текстовый вариант(пиксель+координат) какого-нибудь Чёрного моря от Айвазовского.

И гипотетически, этого романа нету в публичном доступе. То выходит квантовый компьютер, за N времени, должен будет сочинить целиком классическое произведение 19-го века? То есть, как логически это должно выглядеть, квантовый компьютер должен будет писать бесконечное множество литературных произведений, часть из которых чудесным образом окажется гениальной работой? Как можно сгенерировать по алгоритму нечто подобное, даже если учесть, что у компьютера практически неограниченные вычислительные ресурсы.



Последнее исправление: cheetah111v (всего исправлений: 1)

Если я в качестве ключа шифрования использую роман Федора Михайловича Достоевского «Преступление и наказание»

Не используешь. </thread>

t184256 ★★★★★
()

на пальцях для малют

https://ru.wikipedia.org/wiki/Квантовый_алгоритм

Ускорение на квантовом компьютере не связано с тактовой частотой процессора. Оно основано на квантовом параллелизме. Один шаг квантового вычисления совершает гораздо большую работу, чем один шаг классического. Однако было бы ошибкой приравнивать квантовое вычисление к распараллеленному классическому. Например, квантовый компьютер не может решить задачу перебора быстрее, чем за sqrt(Tclass), где Tclass - время работы детерминированного классического алгоритма перебора.

это значит что, гипотетически брутфорс ускоряется в квадратный корень раз.

с другой стороны, быстродейстие отдельных операций квантового кудахтера крайне мало.

и вот если в теории допустить, что скорости кудахтеров сравняются, то ты получишь выигрыш от квантового брутфорса.

типа вместо миллиарда переборов, сделать аж всего лишь 32тыщи.

n_play
()

способные взламывать ключи любой длины.

нужно иметь много кубит. с другой стороны, всегда можно увеличить длину ключа хотя бы в 2 раза. это не стоит ничего.

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

n_play
()

176 тысяч слов.

Допустим ты используешь английский перевод этого замечательного произведения русского писателя Ф. М. Достоевского. Допустим, в переводе такое же количество слов, как и в оригинале. Допустим, что в среднем слово в этом романе имеет длину в 8 символов. Добавим к нему пробельный символ и получим усреднённое слово длинной в 9 байт. Умножим это число на 176 тысяч и получим 1584000 байт или 12672000 бит.

Зададимся вопросом, какие алгоритмы могут оперировать настолько длинными ключами.

EXL ★★★★★
()
Ответ на: совсем от n_play

Нет, криптографией никогда серьёзно не интересовался.

Вот тот же шифр Вернама, где ключ (насколько я помню) должен быть равен по длине передаваемому сообщению, будет устойчив для брутфорса квантовым компьютером?

EXL ★★★★★
()

Даже, если ты по старинке используешь «дедовский» AES, квантовый взлом тебе не грозит, не говоря уже о шифроблокноте.

vvn_black ★★★★★
()
Ответ на: комментарий от EXL

Если ты про XOR, то квантовые компы его не ускорят.

t184256 ★★★★★
()
Ответ на: комментарий от vvn_black

Даже, если ты по старинке используешь «дедовский» AES, квантовый взлом тебе не грозит

Проблема в том, что он не использует AES в вакууме.

t184256 ★★★★★
()
Ответ на: комментарий от t184256

Проблема в том

что ТС считает квантовый компьютер обычным компьютером с неограниченными ресурсами. Отсюда и такой странный вопрос, как в ОП.

vvn_black ★★★★★
()

Квантовую физику не понимают даже сами физики. А ты тут с обывательской колокольни что-то захотел понять.

BceM_IIpuBeT ★★☆☆☆
()
Последнее исправление: BceM_IIpuBeT (всего исправлений: 1)
Ответ на: комментарий от vvn_black

Количество журналистов изнасилованных глупостью про «квантовые компьютеры производят суперпозицию всех возможных вычислений сразу» уже давно перешло критическую черту и переспорить ТСа в этом вопросе будет совершенно пустой тратой времени. Но! если заставить его рассказывать, как он пользуется традиционной криптографией, он может хоть в ней капельку разобраться, а это тоже профит. Хоть заподозрит, что не передаёт в гугл гигабайт ключа по выделенному защищенному каналу перед просмотром видео с ютубчика, а там и до прекращения шапочных вопросов недалеко =)

t184256 ★★★★★
()
Последнее исправление: t184256 (всего исправлений: 1)
Ответ на: комментарий от t184256

Изнасилованы не только журналисты, но и даже всем известный кот.

BceM_IIpuBeT ★★☆☆☆
()

Если я в качестве ключа шифрования использую роман Федора Михайловича Достоевского

Это вы «одноразовый шифроблокнот» описываете. Принципиально не взламываемая система. Потому что когда ключ >= длине сообщения - можно подобрать n ключей, которые по тому же шифротексту дадут другой открытый текст.

Фишка обычных шифров в том, что ключ короткий, он используется как затравка для эдакого специального генератора случайных чисел, которые генерируют такой поток данных налету вместо чтения Достоевского.

Собственно и взлом заключается в том, чтобы по шифротексту, зная алгоритм, найти стартовое значение этого генератора.

А в описанном вами случае просто нечего взламывать.

atrus ★★★★★
()

То выходит квантовый компьютер, за N времени, должен будет сочинить целиком классическое произведение 19-го века?

Роман это нечто большее чем просто набор цифровых символов, он ещё и смысл имеет, и то, что компьютер получит соответствующий роману набор символов не означает того, что он его сочинит.

torvn77 ★★★★★
()
Ответ на: комментарий от atrus

Да уж, если бы все было бы так просто, наша команда бы перепилась на радостях, а потом мы бы просто выключили половину алгоритмов по дефолту… Эх.

t184256 ★★★★★
()
Ответ на: комментарий от EXL

Кстати Bitbucket в этом году начал отклонять RSA-ключи как небезопасные и предлагает ed25519:

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

dimgel ★★★★★
()

То выходит квантовый компьютер, за N времени

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

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

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

Это у меня конечно предположение, но имхо оно вполне в духе природы какой мы её знаем.

torvn77 ★★★★★
()
Последнее исправление: torvn77 (всего исправлений: 1)
Ответ на: комментарий от dimgel

Если ручка мясорубки в десять раз более тугая, сложно быстро накрутить даже маленький портрет Иисуса на выходе.

t184256 ★★★★★
()
Ответ на: комментарий от dimgel

The book Practical Cryptography With Go suggests that ED25519 keys are more secure and performant than RSA keys

https://docs.gitlab.com/ee/ssh/index.html#ed25519-ssh-keys

Это говорит гитлаб.

Когда я выбирал ключ, то наткнулся на такую статью.

https://newbedev.com/is-it-bad-that-my-ed25519-key-is-so-short-compared-to-a-rsa-key

fernandos ★★★
()

Думаю нужно будет сделать квантовый компьютер размером с планету, и результат будет 42

michwill ★★★★★
()
Ответ на: комментарий от t184256

Что-то мне подсказывает, что зря так плохо думаешь про ТСа, и тема вообще не про криптографию, а про бесконечных обезьян.

WitcherGeralt ★★
()
Ответ на: комментарий от fernandos

А чего ты там выбирал, если в OpenSSH поддержку этой хрени добавили только пару лет как? Пока та версия не разъедется по всем стабильным дистрибутивам даже думать об этом смысла нет. То есть лет 5 ещё.

WitcherGeralt ★★
()
Ответ на: комментарий от WitcherGeralt

Про бесконечных обезьян тему не сделать, их нет и ответы все известны.

t184256 ★★★★★
()
Ответ на: комментарий от fernandos

Я вот весь из себя такой параноик в году хрен знает каком сгенерил себе ключ на 8192 бита. И он даже везде работал, хотя много где рекомендовалось использовать 2048 бит.

Речь про RSA, конечно. А ещё я был участником местного форума, где участники пытались сломать RSA 1024-bit (им был подписаны прошивки в телефонах Motorola) соединив свои компы в сеть, как же мы были тогда наивны.

А вот RSA-ключ кажется 128-битный или 256-битный от какой-то там консольки, вроде Panasonic 3DO на ПО для распределённых вычислений BOINC подобрали, помню хорошо эту новость.

EXL ★★★★★
()
Последнее исправление: EXL (всего исправлений: 2)
Ответ на: комментарий от EXL

Действительно. С версии 6.5 уже лет 6 или 7 прошло.

@fernandos, отзываю комментарий про целесообразность.

WitcherGeralt ★★
()
Ответ на: комментарий от atrus

This. Пример:

Вот вам шифро-текст (на самом деле случайная строка):

0x59b6cba0360b173e3707b1f2b41c5d122f04ccfb

А вот 8 различный ключей к нему (предположим, что найденых брут-форсом):

0x0bd9b8c5452b764c5227c397d032733c0f24ecdb
0x2fdfa4cc537f641e5675d4d2d6702877012ae2db
0x0ddeae80506a745b176bd899d13c247d5a76bfdb
0x3bd3a7cf586c641e436891a8db7373320f24ecdb
0x1dd9a587422b755b1774d096983c7d320f24ecdb
0x1091a7cc1669721e436fd480d13c297d402aecdb
0x17d9bf805f65374a5f629191d57b383e0f24ecdb
0x3bc3bf805a6a62595f6edf95947d2932566bb9d5

Какие 8 разных сообщений можно прочесть из шифро-текста? (Hint: xor)

Победителю печенька.

Bonus: если поменять шифро-текст и ключи местами, то это демонстрирует уязвимость пре-использования ключа одноразового блокнота.

beastie ★★★★★
()
Последнее исправление: beastie (всего исправлений: 1)

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

Кто говорит? Голоса в голове?

seiken ★★★★★
()
Ответ на: комментарий от EXL

хотя много где рекомендовалось использовать 2048 бит

До сих пор гитлаб предлагает создать 2048 ( а 4096 лежит в секции «Upgrade your RSA key pair to a more secure format»), хотя он через 9 лет будет считаться устаревшим.

fernandos ★★★
()

способные взламывать ключи любой длины

Ты про симметричные или асимметричные шифры?

TheAnonymous ★★★★★
()

Теоретически, если сделать квантовый компьютер из (сколько там букв в «Преступлении и наказании») кубитов у каждого из которых будет 33 возможных состояния, то после некоторого шаманства со схлопыванием теоретически можно получить текст произведения. Ну и до того, в таком компьютере неопределённо будет существовать «Преступление и наказание» Шрёдингера (не в смысле автора, а в смысле состояния).

Stanson ★★★★★
()
Ответ на: комментарий от Stanson

Теоретически

Чем это отличается от обычного компьютера? Сколько времени уйдёт на анализ одного семпла?

vvn_black ★★★★★
()
Ответ на: комментарий от vvn_black

Чем это отличается от обычного компьютера? Сколько времени уйдёт на анализ одного семпла?

Речь не про анализ, а про «может ли квантовый компьютер родить Преступление и наказание».

Stanson ★★★★★
()
Ответ на: комментарий от Stanson

Вот, по-моему мнению, не может, это же не простые множители раскладывать.

Речь не про анализ

А как без этого? Ну вот, «квантовый компьютер» выдал ответ "Родил «Преступление и наказание». Ну давай сюда, а не могу, всё время-ушло-связанность-пропала.

vvn_black ★★★★★
()
Последнее исправление: vvn_black (всего исправлений: 1)
Ответ на: комментарий от n_play

нужно иметь много кубит

А уже разобрались с технологическими ограничениями, мешающими достигнуть даже 50 кубит?

olegd ★★★
()

То есть, как логически это должно выглядеть, квантовый компьютер должен будет писать бесконечное множество литературных произведений, часть из которых чудесным образом окажется гениальной работой?

Бесконечное множество литературных произведений бесполезно, так как проверить их на наличие гениальности займет бесконечное число времени у хуманов)

goingUp ★★★★★
()
Ответ на: комментарий от EXL

…Допустим, что именно это издание содержит массу опечаток…

mark1
()
Ответ на: комментарий от dimgel

Вот объясните ламеру, каким образом алгоритм с в разы меньшим размером pubkey может быть безопаснее?

Дело не в длине ключа, а в умении им пользоваться^W^W^W количестве вычислений, необходимом для его подбора. Эллиптика вычислительно более сложная задача, по этому при меньшей длине ключа обеспечивает такую же сложность перебора, что и rsa с более длинным ключом.

atrus ★★★★★
()
Ответ на: комментарий от beastie

Bonus: если поменять шифро-текст и ключи местами, то это демонстрирует уязвимость пре-использования ключа одноразового блокнота.

Которое в определённом случае может стать преимуществом. Когда-то у меня была идея отрицаемых торрентов. Суть такова: Вы хотите раздать некий закопирайченный фильм, но вас за это могу побить по голове. Тогда вы генерируете файл со случайными значениями, равный по длине файлу фильма. Вы xor-ите файл фильма со случайным файлом и раздаёте случайный фал и по-xor-енный файл специальным торрент-клиентом так, чтобы половина пользователей скачала один файл, а половина второй.

Желающий посмотреть фильм скачивает обе половинки и объединяет.

Фишка в том, что доказать, что у конкретного пользователя не файл со случайными значениями становится невозможно. А значит запретить распространять его - нельзя. Ведь каждый сможет утверждать, что лично он раздаёт только случайные данные.

atrus ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.