Alexander Grothendieck
апрель 2016.
5378

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

Ответить
Ответить
Комментировать
1
Подписаться
12
2 ответа
Поделиться

Квантовые компьютеры позволяют быстро разложить числа на простые множители, а также решить ряд похожих задач, например вычислить дискретный логарифм. Чуть сложнее, но все равно будут найдены алгоритмы вычисления логарифмов в более сложных группах, вроде точек на эллиптических кривых. Таким образом все известные на текущий момент криптографические алгоритмы связанные с электронно-цифровой подписью и обменом ключами будут скомпрометированы. Это касается таких алгоритмов как: RSA, Diffie-Hellman, DSA, ECDSA, ГОСТ Р 3410-1994, ГОСТ Р 3410-2001, ГОСТ Р 3410-2012 и т.д.

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

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

P.S. Следует учесть, что на текущий момент нет достаточного количества материала для анализа возможностей квантовых компьютеров. 5 кубитов не тоже самое что и 1024, а уж тем более 4096, требуемых для разложения на простые множители ключей банков. Компьютер, продемонстрированный Google'ом не является квантовой ЭВМ общего назначения, а умеет решать только одну задачу.

P.P.S. Поправлю себя: дискретный логарифм и факторизация (разложения на простые множители) больших чисел претенденты на NP-полные задачи, но пока это не доказано (и это сложная история). Тем не менее квантовые компьютеры потенциально все их решают.

21
0

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

0
Ответить

Сложно рассказать в рамках комментария. Простое описание можно найти в https://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D0%B0%D1%8F_%D0%BA%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F#.D0.9F.D1.80.D0.BE.D1.81.D1.82.D0.B5.D0.B9.D1.88.D0.B8.D0.B9_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC_.D0.B3.D0.B5.D0.BD.D0.B5.D1.80.D0.B0.D1.86.D0.B8.D0.B8_.D1.81.D0.B5.D0.BA.D1.80.D0.B5.D1.82.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BA.D0.BB.D1.8E.D1.87.D0.B0_.28BB84.29 

Если коротко, то нельзя узнать состояние частицы не испортив его. Поэтому Алиса может отправить последовательность частиц со случайными состояниями (например 0, 1, 1, 1, 0, 0, 1). Боб примет их и отправит Алисе обратно частицу в том же состоянии если нужно передать 1 и в другом если 0. Такая схема уязвима к атакам активного перехватчика, так как он может принять сигнал от Алисы и отправить Бобу новую последовательность и наоборот, схема описанная в Википедии по ссылке более точная, однако идея такая.

0
Ответить

Квантовые компьютеры позволяют быстро разложить числа на простые множители, а так как это NP-полная задача

В чем ее NP-полнота? Для того, чтобы разложить N = pq, мне в худшем случае надо перебрать O(N) вариантов

0
Ответить
Ещё 10 комментариев

Да, но в данном случае рассматривается разложение n-битного числа на простые множители. Типичный ключ RSA - 2048 бит, а за 2^2048 и даже 2^1024 шагов, так как надо только до корня квадратного из N, не перебрать никак. Поэтому есть возможность быстро проверить (за O(n^2) если наивно) выполняется ли pq = N, но найти p и q за полиномиальное время от их битовой размерности не получается.

+2
Ответить

хорошо, допустим, а есть доказательство что не получится? Для этого нужна сводимость из NP

+1
Ответить

Доказательства нет пока

0
Ответить

Если доказательства нет, то исправьте пожалуйста, что факторизация и дискретный логарифм NP-полные. Лучше их назвать претендентами в этот класс

0
Ответить

Да, согласен они претенденты.

+3
Ответить

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

0
Ответить

Как это не даст? А как вы себе представляете тогда доказательство? Доказательством и должен быть алгоритм который решит полиномиально NP-полную. Любая NPC известным алгоритмом полиномиально к ней сводится, значит итоговый алгоритм в виде их суперпозиции и будет решением

-1
Ответить

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

+2
Ответить

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

-2
Ответить

Не согласен. P=NP настолько крутая проблема, что тут не важно, конструктивом ты это выведешь или нет. Потому что запомнят первого. Так что как получится вывести, так и будет.

+2
Ответить
Прокомментировать

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

Многие методы криптографии основаны на разложении большого числа на простые множители, или на работе с часовой арифметикой и очень большими числами. Если мы говорим об одностороннем шифровании, вроде MD5 (Не кидайтесь клавиатурами, я знаю, что он морально устарел), то можно пропорционально увеличить выходную строку так, чтобы даже на квантовом компьютере было тяжело её раскодировать. Так как мы считаем, что в данном примере все уже давно работают на квантовых компьютерах, то и для шифрования и для расшифровки мы используем его мощности. (Напомню, что Google заявил о двухсотмиллионном превосходстве квантового компьютера над обычным). Так что мы условно говоря, усложним задачу в 200 000 000 раз, и тогда мы снова получим хороший, криптостойкий шифр. Правда есть шанс, что и весить он будет на несколько сот порядков больше.

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

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

Надеюсь, я ответил на ваш вопрос

18
-8

А можно поподробнее про предпоследний абзац?

+3
Ответить

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

Ну а про Гугл: они создали себе специальную задачу со специальными параметрами под те технологии (квантовый отжиг), которые купили (D-Wave), и на ней и показали такую скорость. По-большому счету, маркетинговый ход. D-Wave, хоть и использует какие-то квантовые эффекты, не является полноценным квантовым компьютером.

0
Ответить

А MD5 не связан с шифрованием вообще никак. Это хэш-функция. С простыми числами она никак не связана.

+3
Ответить
Прокомментировать
Ответить
Читайте также на Яндекс.Кью
Читайте также на Яндекс.Кью