Квантовые вычисления и шифрование

Ответ 1

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

Основной предпосылкой квантового вычисления является квантовая суперпозиция. Идея состоит в том, что квантовая система (например, квантовый бит или кубит, квантовый аналог нормального бита) может, как вы говорите, существовать не только в состояниях 0 и 1 (называемых вычислительными базисными состояниями системы), но и в любой комбинации двух (так что каждая из них имеет связанную с ней амплитуду). Когда система наблюдается кем-то, состояние кубита сворачивает в одно из его базовых состояний (вы, возможно, слышали о Schrödinger cat мысленный эксперимент, связанный с этим).

Из-за этого регистр n qubits имеет собственные состояния 2^n (это состояния, в которых вы можете наблюдать регистр, представляющий классическое n-разрядное целое число). Поскольку регистр может существовать в суперпозиции всех этих состояний одновременно, можно применить вычисление ко всем состояниям регистров 2^n, а не только одному из них. Это называется квантом parallelism.

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

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

Пример, который вы задаете, - это квантовый криптоанализ. Он думал, что квантовые компьютеры могут "разбить" определенные алгоритмы шифрования: в частности, алгоритм RSA, который опирается на трудность нахождения простых коэффициентов очень больших целых чисел. Алгоритм, который позволяет это, называется алгоритмом Shor, который может определять целые числа с полиномиальной временной сложностью. В отличие от лучший классический алгоритм для проблемы имеет (почти) экспоненциальную временную сложность, и поэтому проблема считается " неразрешимый".

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

Помимо: чтобы лучше понять идею квантовой суперпозиции, подумайте о вероятностях. Представьте, что вы переворачиваете монету и ловите ее на руке, чтобы она не видна. Как очень тонкая аналогия, монета может рассматриваться как находящаяся в суперпозиции голов и хвостов "состояний": каждая из них имеет вероятность 0,5 (и, естественно, поскольку существуют два состояния, эти вероятности составляют 1). Когда вы берете свою руку и наблюдаете за монеткой напрямую, она сворачивается в состояние головы или состояние хвостов, и поэтому вероятность этого состояния становится равной 1, а другая становится 0. Один из способов подумать об этом, я полагаю, представляет собой набор весов, который сбалансирован до наблюдения, и в этот момент он подсказывает одну сторону, когда наши знания о системе возрастают, и одно состояние становится "реальным" состоянием.

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

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

Ответ 2

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

На квантовом уровне законы, управляющие поведением, отличаются от законов на макроуровне.

Чтобы ответить на ваш вопрос, вам сначала нужно понять, как работает шифрование.

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

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

Эта атака медленная, и ее препятствует выбор больших и больших простых чисел. Вы слышите о размерах клавиш 40 бит, 56 бит, 128 бит и теперь 256,512 бит и выше. Эти размеры соответствуют размеру номера.

Алгоритм грубой силы (в упрощенных выражениях) может выглядеть как

for(int i = 3; i < int64.max; i++)
{
  if( key / i is integral)
  {
    //we have a prime factor
  }
}

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

Как квантовый бит-адрес это то, что они одновременно равны 0 и 1. Так скажите, что у вас есть 3 квантовых бита (без малейшего умения).

С 3 qbits ваша программа может иметь значения 0-7 simulatanously

(000,001,010,011 и т.д.)

который включает простые числа 3,5,7 в то же время.

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

0,1,2,3,4,5,6,7

в то же время.

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

Ответ 3

Статья в Википедии очень хорошо объясняет это.

Короче говоря, если у вас есть N бит, ваш квантовый компьютер может находиться в 2 ^ N состояниях одновременно. Аналогично концептуально, что обработка процессора 2 ^ N с традиционными битами (хотя и не совсем одинаковая).

Ответ 4

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

Ответ 5

Почти все наши шифры с открытым ключом (например, RSA) основаны исключительно на математике, полагаясь на трудность factorization или дискретные логарифмы. Оба они будут эффективно разрушены с помощью квантовых компьютеров (хотя даже после бакалавров в CS и Math и, пройдя несколько классов по квантовой механике, Я все еще не понимаю алгоритм).

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

Ответ 6

В самых основных терминах нормальный квантовый компьютер работает, работая на битах (sates on или off), генерируя логическую логику. Вы делаете это очень быстро для большого количества бит, и вы можете решить любую проблему в классе проблем, которые можно вычислить.

Однако они являются "ограничениями по скорости", а именно так называемой вычислительной сложностью. Это означает, что для данного алгоритма вы знаете, что время, затрачиваемое на выполнение алгоритма (и пространства памяти, необходимого для запуска алгоритма), минимальная граница. Например, алгоритм, который является O (n ^ 2), означает, что для размера данных n для n потребуется 2 раза.

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

Ответ 7

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

Во-вторых, прочитайте статью в википедии: http://en.wikipedia.org/wiki/Quantum_computer

В частности, "В общем случае квантовый компьютер с n кубитами может быть в произвольной суперпозиции до двух разных состояний одновременно (это сравнивается с обычным компьютером, который может находиться только в одном из этих 2 ^ n состояний при любое время).

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

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

Если такое возможно, это может быть конец криптографии, как мы ее знаем.

Ответ 8

квантовые компьютеры и т.д. вся ложь. Я не верю в эти научно-фантастические журналы. на самом деле система rsa основана на двух простых числах и их многообразии. p1, p2 - огромные простые числа p1xp2 = N модуль. Система rsa как это выберите простое число.. может быть небольшой его открытый ключ E (P1-1) * (Р2-1) = Р найти число D, которое делает E * D = 1 mod (R) мы делимся (E, N) данными как открытый ключ публично мы надежно сохраняем (D, N) как частные.

Чтобы решить эту систему взлома системы Rsa, необходимо найти простые коэффициенты N. * масса Вселенной ближе к 10 ^ 53 кг * масса электрона равна 9,10938291 × 10 ^ -31 кг если мы делим вселенную на электроны, мы можем создать 10 ^ 84 электронов. электроны имеют более низкие скорости, чем свет. его частота перемещения может составлять 10 ^ 26 , если кто-либо производит электронные размеры параллельных rsa простых множителей факторов из всей массы вселенной. все юниты могут обрабатывать (10 ^ 84) * (10 ^ 26) = 10 ^ 110 номеров в секунду.

rsa имеет предельные биты альтернативных простых чисел. возможно, 4096 бит 4096 бит rsa имеет 10 ^ 600 возможных простых чисел для грубой силы. поэтому ваш квантовый решатель вашей вселенной должен провести тесты в течение 10 500 лет.

rsa против квантовой вычислительной машины Вселенной 1 - 0

возможно, квантовый компьютер может сломать 64/128 бит паролей. потому что 128-битный пароль имеет 10 ^ 39 возможных узлов грубой силы.