id: Гость   вход   регистрация
текущее время 14:21 23/11/2017
Автор темы: alexor1234, тема открыта 19/03/2016 03:26 Печать
Категории: криптография
https://www.pgpru.com/Форум/Криптография/БудущееАссиметричнойКриптографии
создать
просмотр
ссылки

Будущее ассиметричной криптографии


Как известно, квантовые компьютеры всё-таки были успешно созданы, правда пока они несовершенны, но это дело времени, и наверно не очень большого.


Сейчас последняя модель это D-Wave 2X с тысячей кубитов (правда не очень тесно квантово-скоррелированных между собой).


Как известно, существует алгоритм Шора для квантового компьютера, который позволяет взломать ассиметричный алгоритм RSA, причём за полиномиальное время (практически мгновенно). Также под угрозу попадает ассиметричная криптография на эллиптических кривых, да и вообще любая ассиметрика (как утверждается).


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


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


Как Вы считаете, что ждёт в будущем ассиметричную криптографию?


 
Комментарии
— SATtva (19/03/2016 11:39)   профиль/связь   <#>
комментариев: 11514   документов: 1035   редакций: 4046

D-Wave — не квантовый компьютер. Это классический компьютер с симуляцией квантовых эффектов, он пригоден только для узкого класса квантовых алгоритмов (и даже с ними непонятно, есть ли какой-то существенный прирост скорости решения по сравнению с классическими). У нас это неоднократно обсуждалось. Регистры реальных квантовых компьютеров всё ещё не превышают пары-тройки десятков кубитов.


Отсюда и до конца.
— alexor1234 (19/03/2016 17:58)   профиль/связь   <#>
комментариев: 13   документов: 4   редакций: 1
D-Wave — не квантовый компьютер.

Да, он пока не полноценен, многие считают, что он не чисто квантовый.

Регистры реальных квантовых компьютеров всё ещё не превышают пары-тройки десятков кубитов.

Так это и настораживает, всё сначала начинается с малого.


Вообщем, время покажет)
— pgprubot (20/03/2016 23:34, исправлен 20/03/2016 23:39)   профиль/связь   <#>
комментариев: 511   документов: 2   редакций: 70

И пары-тройки кубитов логических.



По сети гуляет манифест 2016-го, где попытались выжать максимум оптимизма, при котором ещё можно просить


Member States and the European Commission to launch a €1 billion Flagship-scale Initiative

но при этом не сгореть от стыда до тла. Timline (стр. 17) получился таким:


Medium-term goals (5-10 years)
  • Solve problems in chemistry and materials science with special-purpose quantum computers operating at high speeds beyond one hundred physical qubits.


Long-term goals (>10 years)

  • Build a universal quantum computer able to demonstrate the resolution of a problem that, with current techniques on a supercomputer, would take longer than the age of the universe.

Первое — это специализированные компьютеры типа D-Wave, которые дают некоторый speedup по сравнению с классическими, т.е. ограниченно полезны в своём узком круге задач, но при этом не экспоненциально быстрее классических. Второе — то, что нужно для взлома криптографии.

— alexor1234 (21/03/2016 00:37)   профиль/связь   <#>
комментариев: 13   документов: 4   редакций: 1
Ага, т. е. как я понимаю, создать полноценный КК вообще невозможно?
— SATtva (21/03/2016 10:42)   профиль/связь   <#>
комментариев: 11514   документов: 1035   редакций: 4046

Очевидно, что раз уже создаются устройства из десятков кубитов, то принципиально возможно. Но так же очевидно, что построение практически полезных устройств из тысяч кубитов, сохраняющих когеретное состояние достаточно долго, чтобы выполнять нужные вычисления — чрезвычайно сложная научно-инженерная задача с горизонтом на десятилетия.
— alexor1234 (21/03/2016 14:51)   профиль/связь   <#>
комментариев: 13   документов: 4   редакций: 1
Очевидно, что раз уже создаются устройства из десятков кубитов, то принципиально возможно. Но так же очевидно, что построение практически полезных устройств из тысяч кубитов, сохраняющих когеретное состояние достаточно долго, чтобы выполнять нужные вычисления — чрезвычайно сложная научно-инженерная задача с горизонтом на десятилетия.

Может быть, я не знаю, но частота процессоров например остановилась из-за фундаментальных ограничений, может также и рост когерентности не сможет подняться например больше 64 связанных кубитов из-за неустранимых шумов.
— SATtva (21/03/2016 15:03)   профиль/связь   <#>
комментариев: 11514   документов: 1035   редакций: 4046

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


Этого я не знаю. Может быть, наш штатный квантовый физик сможет прокомментировать, маячат ли там на горизонте какие-нибудь фундаментальные преграды.
— unknown (22/03/2016 21:02, исправлен 22/03/2016 21:14)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

На правах внештатного криптографа по последним данным симметричная криптография имеет шансы проследовать туда же. Случайный оракул в квантовом мире приобретает более реальные очертания.



В этом сезоне моден алгоритм Саймона, адаптированный для симметрики и это не единственное направление, «из которого можно выжать максимум оптимизма», чтобы было на что просить.

— alexor1234 (22/03/2016 21:15, исправлен 23/03/2016 00:42)   профиль/связь   <#>
комментариев: 13   документов: 4   редакций: 1

Я слабо себе представляю, что КК может угрожать хешированию, насколько мне известно, хеширование квантово-устойчиво, я это видел несколько раз на сайтах, а сам Алгоритм Саймона появился очень давно.


1. Можно поподробнее про Алгоритм Саймона и про ( https://eprint.iacr.org/2016/197 ) своими словами?


(!) 2. А как хеширование, например SHA-3 512 бит (Keccak), что будет с ним?


3. А как же предел Бремерманна, что скорость не более 1.36 * 10^50 бит в секунду на килограмм для любой материальной структуры?


(!) 4. Угрожает ли Алгоритм Саймона при использовании SHA-3 (Keccak) 512 бит для создания Message Auth Code, при длине ключа также 512 бит?
Напомню, он вычисляется там достаточно просто – MAC = Hash(Key + Data).


– - – - – - – - – - – - – -


Я нашёл на одном сайте следующее про Алгоритм Гровера:

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

Ещё нашёл комментарий на geektimes.ru от 10 декабря 2015 года:

Майнер не получится, равно как и взлом симметричных шифров. Эти задачи решаются только в лоб — что на кванте, что на классике. Угроза криптографии со стороны квантовых компьютеров — прежде всего угроза асимметрике: то, что может стать решаемой задача получения закрытого ключа из открытого. Так что… майнить будет нечего — любой системе, в основе которой квантово нестойкая асимметрика, кранты сразу. В том числе и битку.

К слову, на Википедии про Алгоритм Гровера написано следующее:

Доказано, что GSA является оптимальным в следующих отношениях:
1. Константу pi/4 нельзя улучшить.
2. Большего квантового ускорения, чем квадратичное, нельзя получить для неисчезающей доли всех возможных черных ящиков f.

Это универсальный алгоритм перебора для чёрного ящика, дающего лишь квадратичное ускорение. Условие 2 означает, что не существует никакого алгоритма перебора хеш-значений, быстрее, чем Алгоритм Гровера?

— unknown (23/03/2016 20:44, исправлен 23/03/2016 20:55)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Всё, что вы изложили — это примерный консенсус на данный момент. Но во вполне официальной науке есть те, кто считает, что это уже не так и эти сведения могут устареть.


Классически, любой брутфорс симметрики — это перебор всех значений, одного за одним. А любое квантовое вычисление (если очень грубо) — это когда вместо конкретных значений функции ей скармливают квантовую суперпозицию сразу многих значений из большого интервала (уж извините за дикую безграмотность в терминологии и примитивное понимание вопроса). И можно быстро получить ответ, есть ли в интервале решение или нет. Если нет — ищем на другом интервале, если есть — разбиваем интервал на части и быстро находим. Чем больше по размеру интервал можно скормить за раз — тем лучше.


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


Теоретически это было предсказано как раз для псевдослучайных функций (хэшей и MAC) года три-четыре назад. Теперь под это подводят конкретные квантовые алгоритмы, пока со слабыми возможностями и слабыми различителями. В режимах шифрования вот поковырялись. В будущем планируют уже учитывать свойства конкретных алгоритмов. Вот, к примеру, если раунд AES или Keccak описывается замкнутой алгебраической функцией, кто поручится, что она не решается как-нибудь хитро квантовым способом? А якобя неалгебраические алгоритмы решаются алгебраическими методами ещё эффективнее. Чисто теоретически. На практике то оно в классике недостижимо. А что там в квантах?


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



Переименовываете транскомпьютационные проблемы в транскомпьютационный криптоанализ, придумываете терминологию (наподобие трансфинитных вычислений), создаём математический аппарат для проведения соответствующих вычислительный операций, добавляем по вкусу уничтожение тёмной материи в чёрных дырах и замыканиях петель времени, и всё, вы — основоположник очередного прорывного направления ;)

— alexor1234 (23/03/2016 22:17, исправлен 23/03/2016 22:22)   профиль/связь   <#>
комментариев: 13   документов: 4   редакций: 1

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

— unknown (23/03/2016 22:56, исправлен 23/03/2016 23:01)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Если кроме алгоритма Гровера работает алгоритм Саймона или что-то ещё, то это уже не так. И это пока до внутренней структуры криптоалгоритмов ещё даже не добрались. RSA/DH/EC — это цельные естественные математические группы и поля, а симметрика — синтетические составные структуры, полного строгого описания свойств которых нет. Как их там можно вертеть в квантовом мире — никто пока достоверно не скажет. Просто описание конкретной симметрики на языке квантовых вычислений — сложная задача и пока их рассматривают только как чёрные ящики с некоторыми свойствами.


Лучше уж надеяться, что требуемый QC так и не построят.

— alexor1234 (24/03/2016 00:59, исправлен 24/03/2016 01:38)   профиль/связь   <#>
комментариев: 13   документов: 4   редакций: 1
Лучше уж надеяться, что требуемый QC так и не построят.

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


Итак, пока я заметил на горизонте лишь такие атаки на криптографию:
1. Математические атаки на сам шифр или хеш
2. Угроза со стороны КК


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


Кстати, а может ли вообще существовать принципиально другой компьютер, кроме классического или квантового?


Посмотрим что время нам покажет...


Но не будем о грустном):

У криптографов есть такая традиция: каждые сто лет они собираются все вместе и уничтожают все квантовые компьютеры на планете.

: ) :

— ВасВас (20/08/2016 01:23)   профиль/связь   <#>
комментариев: 1   документов: 0   редакций: 0
Кстати, а может ли вообще существовать принципиально другой компьютер, кроме классического или квантового?
– Может: механический.
Важное отличие механических логических элементов от электрических – могут работать одновременно и прямо и обратно.
Значит можно собрать из них например алгоритм умножения и если подать на выход факторизуемое число то входные встанут в среднее положение ("суперпозиция"). Теперь если начать дёргать по очереди входы в 0 или 1 то некоторые остальные будут вставать в 0 или 1 в зависимости существует ли решение или нет, если решений не существует то ни один входной бит не удасться до конца поставить в 0 или в 1. Также не получиться выставить несуществующее решение.
Это похоже на квантовый компьютер только механический :)
— Гость_ (22/08/2016 09:13)   профиль/связь   <#>
комментариев: 434   документов: 6   редакций: 9
Суперпозиции недостаточно, ещё нужно соотношение неопределённости.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3