Трудоемкость алгоритма на примере RSA, квантовые компьютеры




RSA – алгоритм шифрования с открытым ключом

 

Всегда поднималась проблема о безопасной передаче информации. Любая линия, по которой идет передача информации может быть прослушана, и информация может попасть к злоумышленнику. Нужен был надежный алгоритм шифрования. Сообщение можно было зашифровать каким-либо ключом и передать сообщение, а затем и ключ, но при этом всё равно оставалось возможным перехватить ключ и расшифровать сообщение. В 1970-ых годах для решения этой проблемы были предложены системы шифрования, использующие два вида ключей для одно и того же сообщения: открытый (не требующий хранения в тайне) и закрытый (строго секретный). Открытый ключ служит для зашифровки сообщений, а закрытый для его дешифровки. Вы посылаете вашему корреспонденту открытый ключ, он с помощью него шифрует сообщение и отправляет его вам. Всё, что сможет сделать злоумышленник, перехватив ключ, - это зашифровать им своё письмо и отправить его кому либо. Но расшифровать переписку он не сможет, для этого необходим закрытый ключ. Как раз такая схема и применяется в алгоритме RSA. Причем для создания пары открытого и закрытого ключа используется следующая гипотеза. Если имеется два больших (требующих больше сотни десятичных цифр для своей записи) простых числа M и K, то найти их произведение N=M*K не составит большого труда. А вот решить обратную задачу, то есть зная число большое N разложить его на простые множители M и K (так называемая задача факторизации) – практически невозможно! Именно с этой проблемой сталкивается злоумышленник, решивший “взломать” алгоритм RSA и прочитать зашифрованную с помощью него информацию: чтобы узнать закрытый ключ, зная открытый, придется вычислить M или K.

Для проверки справедливости гипотезы о практической сложности разложения на множители больших чисел проводились и до сих пор проводятся конкурсы. Рекордом считается разложение 155-значного (512-битного) числа. Вычисления велись параллельно на многих компьютерах в течении семи месяцев 1999 года. Расчеты показывают, что с использованием даже тысячи современных рабочих станций и лучшего из известного на сегодня алгоритмов одно 250-значное число может быть разложено на множители примерно за 800 тысяч лет, а 1000 значное – за 1025 лет. (для сравнения возраст Вселенной ~ 1010 лет.).

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

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

По мере распространения компьютеров ученые, занимавшиеся квантовыми объектами, пришли к выводу о невозможности рассчитать состояние эволюционирующей системы, состоящей всего из десятков взаимодействующих частиц, например молекул метана. Объясняется это тем, что для полного описания сложной системы необходимо держать в памяти компьютера очень большое количество переменных, так называемых квантовых амплитуд. Возникла парадоксальная ситуация: зная уравнение эволюции, зная начальное состояние системы и все взаимодействия частиц, практически неважно вычислить её будущее, даже если система состоит из 30 электронов в потенциальной яме, а в распоряжении имеется суперкомпьютер с оперативной памятью, число битов которой равно числу атомов в видимой области Вселенной. И в то же время для исследования динамики такой системы можно просто поставить эксперимент с 30 электронами, поместив их в данные условия. Так и появилась идея использования квантовых процессов для практических вычислений. Первым эту проблему поднял русский математик Ю.И. Манин. Большое внимание к разработке квантовых компьютеров привлек лауреат Нобелевской премии Р.Фейнман. Благодаря его авторитетному призыву число специалистов, обративших внимание на квантовые вычисления, увеличилось во много раз.

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


Вывод

 

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


Литература

 

1. Гилл А. Введение в теорию конечных автоматов. М.: Наука, 1966.

2. Гэри М., Джонсон Д., Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

3. Кузнецов О.П., Адельсон-Вельский Г.М., Дискретная математика для инженера. М.: Энергоатомиздат, 1988.

4. Манин Ю.И. Вычислимое и невычислимое. М.: Сов.радио, 1964.

5. И.фон Нейман Математические основы квантовой механики. М.: Наука, 1964.

6. Р.Фейнман Моделирование физики на компьютерах. Квантовый компьютер и квантовые вычисления. Ижевск: РХД, 1999.

7. Р.Фейнман Квантово-механические компьютеры. Там же.

8. В.В.Белокуров, О.Д.Тимофеевский, А.О.Хрусталев Квантовая телепортация – обыкновенное чудо. Ижевск: РХД, 2000.

9. А.Китаев, А. Шеня, М.Вялый Классические квантовые вычисления. М.: МЦНМО-ЧеРо, 1999.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-10-17 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: