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

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

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

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

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

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

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

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

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

Источник: thequestion.ru

Комментарии: