Было бы наивно ожидать, что криптосистемы на эллиптических кривых, столь похожие на дискретное логарифмирование, не поддадутся квантовому компьютеру. И действительно, алгоритм Шора можно без особого труда модифицировать так, чтобы он взламывал описанный выше протокол, а равно и другие аналоги классических криптосистем, основанные на эллиптических кривых.
Но бояться этого, по моему личному мнению, не следует. Квантовые компьютеры сейчас находятся в самом начале своего пути. Пока никто не может предсказать, удастся ли построить квантовый компьютер хоть сколько-нибудь интересного с практической точки зрения размера (текущие рекорды - семь кубитов, одиннадцать кубитов - как-то не впечатляют). А для работы алгоритма Шора, например, нужен квантовый компьютер на стольких кубитах, сколько классических битов в раскладываемом простом числе; на меньшем числе просто ничего не получится. Скорее всего, в ближайшие десятилетия квантовые компьютеры, способные взломать даже сегодняшние шифры, не появятся. А если и появятся - уже существует и активно развивается так называемая квантовая криптография.
Суть криптосистемы Диффи-Хеллмана в том, чтобы перед началом коммуникации с секретным ключом об этом самом ключе договориться (этот процесс в криптографии называют «протоколом key agreement»; кстати, в реальных приложениях криптография с открытым ключом очень часто используется именно для этой цели). Иными словами, цель не в том, чтобы передать сообщение от одного участника к другому, а в том, чтобы у обоих участников в конце концов обнаружилось одно и то же число, которое можно будет использовать как секретный ключ [Есть и «настоящая» криптосистема с открытым ключом, основанная на той же идее - так называемая система ElGamal; она немногим сложнее Диффи-Хеллмана, но описание ее более громоздко, и поэтому для иллюстрации Диффи-Хеллман подходит лучше]. Делается это так: Алиса и Боб выбирают простое число p, по модулю которого будут проводиться все вычисления, и основание g, которое они потом будут возводить в степень. Затем Алиса выбирает число a (никому его не показывая) и передает Бобу (g^a mod p), а Боб выбирает число b и передает Алисе (g^b mod p). Теперь Алисе достаточно возвести полученное число в степень a, а Бобу - в степень b, и у них обоих будет один и тот же ключ, так как, разумеется, g^ab mod p = g^ba mod p. Как видите, ничего сложного. Почему же этот шифр трудно разгадать? Стойкость этой криптосистемы тесно связана с вычислительной трудностью операции дискретного логарифмирования - зная g^a mod p, g и p (все эти числа в принципе доступны противнику), вычислить a. Отметим, что взлом Диффи-Хеллмана вовсе не обязательно решит задачу дискретного логарифмирования - этот вопрос еще остается открытым, но если научатся эффективно вычислять искать дискретные логарифмы, то и Диффи-Хеллман падет тут же.
Редакция благодарит профессора Колледжа Лафайет (Lafayette College) Клиффорда Рейтера (Clifford Reiter) за предоставленные изображения множеств Жюлиа.
ПИСЬМОНОСЕЦ: Прикол в пространстве Лобачевского!
Живу в глуши, Интернет через дайлап, качаю да читаю «Компьютерру»! Красота! Да, о чем это я? Ах, да! Жил был один англичанин и состряпал сайт на миллион!!! Долларов почему-то, а не фунтов. Ну да ладно, это мелочи, я о своем. О сайте в смысле. Состряпал я сайт www.historyinternet.ru , и вот сижу и думаю, будет у меня миллион рублей или нет? Ну там рублем больше, рублем меньше. Ну почему больше - ответ на сайте. В общем там больше чем 1 000 000. Думаю, программисты меня поймут. Ну вот и все!
Вывод: читай «КТ» - разбогатеешь! Как разбогатеешь - подели… э-э-э… напиши в «КТ»! Ждите.
P.S. Я, конечно, понимаю, что это здорово смахивает на ПИАР (или как там это называется?), но если опубликуете, представляете, сколько народу придет… [на сайт в смысле, а не ко мне за деньгами]). Заранее спасибо, приза не надо.
Алексей Ефанов aka LevaSoft
ОТ РЕДАКЦИИ: Глушь, природа, дайлап - вот это жизнь! Как там у Есенина - «Дайлап мне, Джим, на счастье мне…», что-то путаю, но неважно. Насчет денег - Алексей, если честно, шансов мало. Народ у нас прожженный, он хочет никогда не отдавать деньги, а всегда их получать, поэтому наш с вами ПИАР приведет только к массовому размножению аналогичных проектов.
Мощно звучит: Microsoft FEAR Play. Уж не знаю - шутите вы или нет. А эта приписка в «Письмоносце»: «Из отпуска вернулся…» Рад, что из отпуска люди возвращаются довольными, веселыми, отдохнувшими.
Желаю успехов.
С уважением,Сергей
ОТ РЕДАКЦИИ: С «Майкрософтом» мы никогда не шутим, ибо, как учил еще Козьма Прутков, «эти шутки глупы и неприличны». То, что вы обнаружили, - обычная опечатка. Имели в виду ПЕАР - ну, как в предыдущем письме.
Сделайте тему номера не о редакторах и проч. А о самой редакции. То есть о самом помещении (такого на моей памяти еще не было). Например - вот здесь вот у нас то-то, вот здесь то-то.
С уважением Алексей .
ОТ РЕДАКЦИИ: Алексей, никакого «то-то» у нас нет. При входе всегда сидит охрана (за железной дверью с огромным замком). Сразу налево - длинный коридор, кое-где переходящий в холл. Заканчивается тупиком, других входов нет. По бокам - двери в комнаты. Когда-то, в разгар пузыря доткомов, на верстке стояла веб-камера - в духе времени. Но потом верстальщики постепенно вытеснили ее из зоны видимости, и теперь заглянуть извне в редакцию стало совсем трудно. На всех окнах, Алексей, - сигнализация, и охрана ночью не спит!
Конничива, «Компьютерра».
В статье Ваннаха «Младший хирург с “Гремучей змеи”» автор пишет, что определить пол ежа может только другой еж, - в принципе это именно так, поскольку редкий колючий не сворачивается, если его взять на руки, однако есть весьма остроумный альтернативный способ: положить ежа на горизонтально лежащее
