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

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

Дело было в годы Второй мировой войны, когда электронщик и математик Клод Шеннон сначала, в 1940 году, защитил докторскую диссертацию по неожиданной теме «Алгебра для теоретической генетики», а несколько позже сумел уложить в общее русло строгой математической теории и науку о сохранении информации, и науку о ее шифровании. Дальнейшие же обстоятельства почему-то сложились так, что за полвека исследований чуть ли не все наиболее важные результаты относительно этих взаимосвязей были получены в одном месте – знаменитых Bell Labs, научно-исследовательском комплексе лабораторий американской индустрии связи.

Клод Шеннон начал работать в Bell Labs с 1941 года, когда из-за вступления США в войну исследования здесь были сосредоточены на радиотехнических системах наведения для ПВО, средствах защиты коммуникаций, криптографии и прочих подобных приложениях. Как известно, несколько лет интенсивной работы Шеннона над этими задачами в итоге привели его к созданию двух эпохальных трудов – «Математическая теория криптографии»[1] и «Математическая теория связи»[2]. Открытая публикация этих работ в первые послевоенные годы произвела подлинную революцию в науке об информации и ее кодировании, открыв эру систематического освоения цифровых инфотехнологий.

*

Публикации Шеннона оказались самым ярким, но, конечно, далеко не единственным важным итогом среди работ ученых и инженеров Bell Labs в военное время. Какие-то из этих трудов вскоре были рассекречены, другие же, носившие прикладной военный характер, так и остались на долгие годы неизвестными широкой публике, осев в секретных архивах. Об одной из таких работ за 1944 год, невзрачно озаглавленной «Финальный отчет по проекту C43» [3], стало известно лишь полвека спустя. Да и то не в США, а в Европе, когда британская спецслужба GCHQ предала, наконец, гласности долго сохранявшуюся в тайне историю о создании ее сотрудниками методов «несекретного шифрования» на рубеже 1960-70-х годов [4]. Чуть позже те же самые вещи стали знамениты под названием «криптография с открытым ключом», когда их повторно и независимо изобрели несколько математиков открытого академического сообщества – Диффи, Хеллман, Райвест, Шамир и Эдлеман.

В секретном же сообществе англо-американских криптослужб первооткрывателем стал сотрудник GCHQ Джеймс Эллис, которого натолкнул на революционную идею тот самый военного времени отчет о «проекте C43». В работе Bell Labs описывалась новаторская и весьма остроумная идея засекречивания телефонной связи. А именно, предлагалось, чтобы получатель маскировал речь отправителя путем добавления в линию шума. Сам получатель в процессе приема мог вычитать этот шум, поскольку он же его и добавлял, а следовательно знал, что тот собой представляет. Правда, существенные практические неудобства данной системы в те годы помешали ее реальному воплощению в жизнь, однако сама идея содержала несколько интересных особенностей.

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

Но вернемся к основной теме, волновым взаимодействиям и передаче информации. Суть системы Bell Labs была в том, что у получателя здесь нет никакого криптоключа или другого секрета, обычно необходимых для получения зашифрованного послания. Единственное, что требуется, это чтобы получатель тоже – наряду с отправителем – принимал участие в организации защищенного канала связи. И тогда неприятель-перехватчик, даже зная все об устройстве этой системы, не сможет получить доступа к засекреченной информации. Именно эту простую и одновременно великую идею, но уже совсем на другом уровне математических формул и компьютерных операций над очень большими числами в 1970-е годы практически реализовали изобретатели криптографии с открытым ключом.

**

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

По этой причине очень многие из работающих в данной области ученых пишут алгоритмы и программы для устройств, которых, можно сказать, пока еще не существует в действительности. Тем не менее, даже на бумаге полученные исследователями результаты выглядят очень впечатляюще. Два наиболее знаменитых достижения из этого ряда появились в середине 1990-х годов благодаря ученым Bell Labs. Алгоритм Питера Шора [5] способен раскладывать огромные числа на множители и таким образом вскрывать шифр RSA в миллиарды раз быстрее, чем методы традиционных компьютеров. Другой же квантовый алгоритм, или поисковая машина Лова Гровера [6], теоретически демонстрирует возможность обследовать все закоулки Интернета примерно за полчаса.

Но прежде, чем познакомиться поближе с необычной волновой природой этих алгоритмов, понадобится хотя бы в общих чертах понять суть принципиальных отличий в устройстве компьютеров квантовых и обычных. Потому что уменьшение элементов памяти или логики вычислителя до размеров молекул, ионов и электронов – это далеко не все. И даже не самое главное. Куда важнее, что эти элементы работают по законам квантовой, а не классической физики. Для хранения бита информации, «0» или «1», можно использовать, скажем, квантованные состояния спина электрона, Down и Up. Как и в обычном компьютере, эти биты тоже можно переключать, то есть изменять состояние «вниз» (0) на состояние «вверх» (1), просто прикладывая к квантовой системе немного энергии.

При этом существенно, что согласно правилам квантовой механики, будет изменяться не состояние спина, а вероятность наблюдения спина в том или ином положении. Можно сказать, частица находится одновременно в обоих состояниях спина – скажем, на 70 процентов «вверх» и на 30 процентов «вниз». Такая суперпозиция состояний с определенными вероятностями сохраняется до тех пор, пока не произведено измерение. И лишь операция измерения, или «наблюдения», заставляет частицу однозначно выбрать одно из двух возможных состояний. Поскольку электрон (ион, атом, иная частица) может пребывать в двух состояниях сразу, то набор таких квантовых битов, или кубитов – это далеко не обычный компьютерный регистр, а нечто совершенно новое. Здесь вычисления можно осуществлять уже не последовательно, а, в некотором смысле, обсчитывать все сразу и одновременно.

***

Естественным следствием данной концепции является то, что квантовые компьютеры в принципе могут работать намного быстрее компьютеров классических и вполне способны решать те задачи, к которым обычные компьютеры и подступиться пока не могут. В частности, математик из AT&T (ранее Bell) Labs Питер Шор в 1994 году открыл квантовый алгоритм факторизации, позволяющий раскладывать большие числа на простые множители почти с такой же скоростью, какая свойственна перемножению чисел. Для классического компьютера, надо подчеркнуть, сложность задач перемножения и факторизации различается самым радикальным образом, на чем и построена стойкость RSA, известной криптосхемы с открытым ключом. Алгоритм же Шора для квантового компьютера чрезвычайно остроумно оперирует «волнами вероятностей», проходящими через кубиты регистра, и как бы сводит математическую задачу факторизации к задаче физической – определению периодичности кристаллической решетки.

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

Еще один интереснейший алгоритм более общего назначения был открыт Ловом Гровером, другим исследователем из Bell Labs, в 1996 году. Алгоритм Гровера использует принципы квантового компьютера для очень быстрого поиска в неупорядоченных базах данных вроде Интернета. Здесь, естественно, также используется волновая природа вероятностей у состояний суперпозиции. Сам Гровер описывает суть алгоритма как «бросание камешков в пруд таким способом, чтобы волны от них накладывались и взаимодействовали вполне определенным образом». Алгоритм Гровера устанавливает сразу несколько траекторий вычислений, чтобы волны результатов, получаемых в квантовой системе одновременно, начали интерферировать друг с другом. Тогда нежелательные ответы сами себя гасят, а верные ответы, накладываясь, усиливают друг друга. В некотором смысле, квантовый компьютер – это «обратное вычисление»: предполагается, что компьютеру уже известны все возможные ответы, и алгоритму остается лишь отыскать верный.

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

←Ранее

↑На уровень вверх↑

Далее→

[1] C. E. Shannon, «Communication Theory of Secrecy Systems», Bell System Technical Journal, vol.28(4), page 656-715, 1949. (An earlier version of this research in the classified report: CE Shannon, «A Mathematical Theory of Cryptography», Memorandum MM 45-110-02, Sept. 1, 1945, Bell Laboratories)

[2] C. E. Shannon, «A mathematical theory of communication,» Bell System Technical Journal, vol. 27, pp. 379-423 and 623-656, July and October, 1948

[3] «Final Report on Project C43», Bell Laboratories, October 1944, p. 23

[4] James H. Ellis, «The Story Of Non-Secret Encryption», 1987 (Official open publication by CESG in December 1997)

[5] Peter W. Shor, «Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer», Proceedings, 35th Annual Symposium on Foundations of Computer Science, Nov. 20-22, 1994 (arXiv:quant-ph/9508027)

[6] Grover L.K.»A fast quantum mechanical algorithm for database search», Proceedings, 28th Annual ACM Symposium on the Theory of Computing, May 1996, p. 212 (arXiv:quant-ph/9605043)