БезопасностьТехнологии будущего

Квантовые компьютеры: конец криптографии?

Квантовые компьютеры: конец криптографии?

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

Квантовое вычисление как идея существует уже некоторое время — теоретическая возможность была впервые представлена ​​Юрием Маниным и Ричардом Фейнманом в 1982 году. Однако в последние несколько лет эта область становилась все более приближающейся к практичности.

Такие компании, как Google и Microsoft, а также правительственные учреждения, такие как АНБ, все годами лихорадочно занимаются квантовыми компьютерами. Компания под названием D-Wave произвела и продает устройства, которые (хотя они не являются правильными компьютерами и могут выполнять только несколько алгоритмов) используют квантовые свойства и являются еще одним шагом на пути к полностью полному по Тьюрингу « квантовая машина.

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

Так почему же весь интерес? Почему ты должен заботиться? Компьютеры становятся все быстрее и быстрее. — что такого особенного в квантовых компьютерах?

Чтобы объяснить, почему эти машины так важны, нам нужно сделать шаг назад и выяснить, что такое квантовые компьютеры и почему они работают. Для начала поговорим о концепции, называемой «сложность во время выполнения».

Что такое сложность во время выполнения?

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

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

Как правило, эти классы сложности выражаются в виде функций. Алгоритм, который пропорционально усложняется, когда увеличивается набор данных, над которым он работает (например, простая функция подсчета), называется функцией со сложностью времени выполнения, равной « ( т. Е. Для обработки n точек данных требуется n единиц времени ).

С другой стороны, это может быть названо «линейным», потому что когда вы строите график, вы получаете прямую линию. Другие функции могут быть n ^ 2 или 2 ^ n или n! (n факториал). Это полиномиальные и экспоненциальные. В последних двух случаях экспоненциальные растут так быстро, что почти во всех случаях их невозможно решить ни для чего, кроме очень тривиальных примеров.

Сложность выполнения и криптография

Если вы слышите этот материал впервые, и он звучит бессмысленно и загадочно, давайте попробуем обосновать это обсуждение. Сложность во время выполнения критически важна для криптографии, которая делает процесс дешифрования намного проще для людей, которые знают секретный ключ, чем для тех, кто не знает. В идеальной криптографической схеме дешифрование должно быть линейным, если у вас есть ключ, и 2 ^ k (где k — количество бит в ключе), если у вас его нет.

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

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

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

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

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

Самый известный алгоритм деления больших чисел на их простые составляющие называется ситом поля общего числа и имеет сложность во время выполнения, которая растет немного медленнее, чем 2 ^ n . Как следствие, ключи должны быть примерно в десять раз длиннее, чтобы обеспечить аналогичную безопасность, что люди обычно терпят как расходы на ведение бизнеса. Плохая новость заключается в том, что все игровое поле меняется, когда в смесь попадают квантовые компьютеры.

Квантовые компьютеры: изменение криптографии

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

Для получения дополнительной информации о квантовых компьютерах, посмотрите нашу недавнюю статью на тему !

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

В качестве конкретного примера, алгоритм Шора, который может быть выполнен только на квантовом компьютере, может учитывать большие числа в log (n) ^ 3 раз, что значительно лучше, чем лучшая классическая атака. Использование сита поля общего числа для вычисления числа с 2048 битами занимает около 10 ^ 41 единиц времени, что составляет более триллиона триллионов триллионов. Используя алгоритм Шора, та же проблема занимает всего около 1000 единиц времени.

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

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

Тем не менее, их роль в криптографии будет катастрофической. Технологии шифрования, которые позволяют нашему миру функционировать, зависят от проблемы целочисленной факторизации, которую трудно решить. RSA и связанные схемы шифрования позволяют вам доверять тому, что вы находитесь на нужном веб-сайте, что загружаемые файлы не пронизаны вредоносными программами, и что люди не шпионят за вашим интернет-браузером (если вы используете Tor).

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

Итак, неизбежен ли квантовый апокалипсис? Мы можем с этим что-нибудь сделать? Как оказалось… да.

Постквантовая криптография

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

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

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

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

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

Вы обеспокоены небезопасной криптографией для квантовых компьютеров? Что вы берете? Поделитесь своими мыслями в комментариях ниже!

Кредиты изображений: бинарный шар Via Shutterstock

Похожие посты
Безопасность

Лучшие 36 сочетаний клавиш для Microsoft Edge и IE 11

Технологии будущего

Почему мой автомобильный аккумулятор продолжает умирать?

Безопасность

Управляйте браузером Firefox с помощью команд «О программе»

Безопасность

Microsoft Security Essentials Бесплатное антивирусное программное обеспечение