Математики, шпионы и хакеры. Кодирование и криптография | страница 63

Конец криптографии?

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

Эта операция чрезвычайно трудоемкая, и пока не существует математической лазейки для ее решения. Может ли квантовой компьютер взять на себя задачу разложения числа на простые числа, которые использует шифр RSA? Американский ученый Питер Шор в 1994 г. дал на этот вопрос утвердительный ответ. Шор разработал алгоритм для квантового компьютера, способный разложить большие числа на множители за намного меньшее время, чем самый мощный обычный компьютер.

Если это поразительное устройство когда-либо будет построено, алгоритм Шора кирпичик за кирпичиком разрушит мощное криптографическое здание, построенное на RSA, и наступит день, когда вся самая тайная информация на планете станет явной. Все современные системы шифрования постигнет та же участь. Но, перефразируя Марка Твена, мы можем сказать, что слухи о смерти криптоанализа «сильно преувеличены».

Одной из основ квантовой механики является принцип неопределенности, открытый Вернером Гейзенбергом в 1927 г. Хотя его точная формулировка очень сложна, сам Гейзенберг обобщил его следующим образом: «Мы в принципе не можем знать настоящее во всех подробностях». Более точно: невозможно определить с любой степенью точности те или иные свойства частицы в любой момент времени. Возьмем, например, частицы света (фотоны). Одной из их основных характеристик является поляризация — технический термин, связанный с колебаниями электромагнитных волн. [Хотя фотоны поляризованы во всех направлениях, в нашем примере мы будем считать, что они имеют поляризацию четырех типов: вертикальную

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