С другой сложной для решения проблемой - дискретным логарифмированием - связана так называемая криптосистема Диффи-Хеллмана (Diffie-Hellman), которая появилась даже раньше, чем RSA, - в 1976 году [Кстати, сам Мартин Хеллман утверждает, что по справедливости ее нужно было бы называть криптосистемой Диффи-Хеллмана-Меркле; Ральф Меркле (Ralph Merkle) фактически был автором идеи криптографии с открытым ключом. К сожалению, криптосистема, которая все-таки была названа его именем - основанная на «задаче о рюкзаке» система Меркле-Хеллмана, - оказалась криптографически нестойкой и, как следствие, не приобрела популярности]. Ее краткое математическое описание см. во врезке на следующей странице.
Здесь стоит немного порассуждать о том, что значит «вычислительно трудно». В применении к только что перечисленным задачам математически это не значит ровным счетом ничего - никаких доказательных утверждений о вычислительной трудности разложения простых чисел или дискретного логарифмирования не существует. Однако много лет подряд криптографы всего мира пытались найти эффективные алгоритмы для решения этих задач - и не преуспели. Криптографы стараются использовать как можно больше задач, для которых еще не найдены эффективные алгоритмы [В этом смысле примечательно, что до сих пор неизвестны криптографические протоколы, основанные на NP-трудных задачах. Разумеется, такие протоколы были бы надежнее любых других - разложение чисел на простые множители или дискретный логарифм отлично укладываются в NP, и более того - дешифровка любой криптосистемы должна укладываться в NP, ведь при наличии секретного ключа, играющего роль подсказки, расшифровать сообщение должно быть возможно. Поиск связанных с NP-трудными задачами протоколов или обоснование (не путать с доказательством) того, что построить их невозможно, - одна из самых интересных задач современной криптографии, заслуживающая отдельного разговора]. В рамках этой концепции и были разработаны криптосистемы, основанные на эллиптических кривых.
Начнем сразу с определения. Эллиптические кривые - это кривые вида y^2 =x^3 +ax+b. [В полях размера 2m («полях характеристики 2»; к ним относится и привычное программистам поле из двух элементов) определения становятся чуть более сложными, а стандартные доказательства и рассуждения перестают работать; в алгебре и алгебраической геометрии случай характеристики 2 всегда стоит особняком и требует более изощренной техники, нежели все остальные. Поэтому в дальнейшем мы не будем его рассматривать]
Они занимают промежуточную нишу между коническими сечениями и кривыми более высоких порядков - про них известно не все, но многое. О том, что это серьезный объект для исследований, говорит хотя бы то, что именно теория эллиптических кривых привела Эндрю Уайлса к доказательству великой теоремы Ферма. Но нас будут интересовать куда менее эзотеричные материи.
Хотя примеры, изображенные на стр. 58, нарисованы на плоскости, то есть на множестве пар вещественных чисел (x, y), в криптографии все структуры, разумеется, должны быть дискретными. Поэтому решения уравнения ищутся над конечными полями. Чтобы конечное множество могло стать полем, его размер должен иметь вид p^m , где p - простое число. Конечное поле с простым количеством элементов (m=1) можно представлять как множество неотрицательных целых чисел, меньших p, в котором все алгебраические операции производятся «по модулю p» (то есть с переходом к остатку от деления результата на p). В криптографии используются конечные поля двух типов - с простым количеством элементов (m=1) и «поля характеристики два» (у которых 2 m элементов); мы ограничимся первым случаем. Кстати, термин «эллиптическая кривая» над конечным полем в изрядной степени теряет смысл - какая же это кривая, если это конечное множество точек? Но о терминах спорить - последнее дело, особенно в математике, где белая лошадь, в полном соответствии с Гунсунь Лун-цзы, может оказаться вовсе не лошадью.Ранее мы говорили, что сложность криптосистемы Диффи-Хеллмана связана с дискретным логарифмированием. Однако конструкция, аналогичная использованной в этой системе, может быть реализована над любым множеством, где есть похожая на умножение операция (например, сложение), подчиняющаяся своим естественным законам (такое множество называется в математике группой). Суть применения эллиптических кривых в криптографии сводится к тому, что группа чисел по простому модулю (как было в криптосистеме Диффи-Хеллмана) заменяется группой решений уравнения y^2 = x^3+ax+b. Осталось лишь указать, как складывать друг с другом решения такого уравнения.
На плоскости это делается так, как показано на рисунке выше. Чтобы сложить две точки на эллиптической кривой, нужно провести через них прямую. Она пересечет кривую в третьей точке. Эту третью точку мы будем считать суммой первых двух со знаком минус; чтобы получить собственно сумму, отразим полученную точку относительно оси X. Можно проверить, что такое сложение будет ассоциативным. Остается только один вопрос: что делать, когда третьей точки нет? Например, если нужно сложить точку с самой собой, то для этого нужно провести касательную в этой точке. Если мы проведем касательную в точке (0, 0), она будет направлена вертикально вверх; казалось бы, никакой третьей точки уже не получится. Это затруднение решается просто: к множеству решений эллиптического уравнения добавляют еще одну точку O, о которой проще всего думать как о бесконечности (бесконечные значения x и y действительно удовлетворяют уравнению). Сумма двух точек (0, 0) в нашем примере будет равна O. O играет роль нуля в этом своеобразном сложении. Мы уже говорили, что обратный элемент получится, если отразить точку относительно оси X; если теперь соединить прямой точку и ее обратную, прямая будет вертикальной, и третьей точкой как раз будет бесконечность:
P+(-P)=O.
Над конечными полями таких картинок не нарисуешь, но если выразить эти операции алгебраически, то все сойдется.
Вот, собственно, и все. Эллиптический аналог криптосистемы Диффи-Хеллмана выглядит так. Алиса и Боб выбирают (и сообщают всем) эллиптическую кривую, поле и точку B, лежащую на этой кривой. Затем Алиса секретно выбирает число a и подсчитывает точку aB (складывает B с самой собой a раз), а Боб выбирает число b и вычисляет bB. Затем они обмениваются полученными результатами, и их общим секретным ключом становится точка abB. Чтобы взломать этот шифр, нужно научиться по aB и B вычислять a - это в точности аналог дискретного логарифмирования!
В чем же преимущество шифров, основанных на эллиптических кривых? В том, что в них можно использовать меньшие по величине простые числа, чем в классических системах с открытым ключом.
Напоследок поговорим о том, что многим кажется серьезной угрозой для современной криптографии, - квантовых компьютерах и их возможностях. Прежде всего напомню, что квантовая информатика фактически ведет свою историю с того, что Питер Шор (Peter Shor) в 1994 году представил алгоритмы, которые за полиномиальное время раскладывали числа на простые множители и подсчитывали дискретные логарифмы - на квантовом компьютере, разумеется.
Секретный ключ Алисы в RSA - это два простых числа p и q. Чем больше эти числа, тем шифр надежнее. Именно поэтому многие организации готовы платить деньги за большие простые числа; давно существуют онлайн-проекты распределенных вычислений по поиску простых чисел. Алиса публикует произведение этих чисел N=pq. Ключевое предположение, на котором основана RSA, - то, что большое число трудно разложить на множители. То есть N можно распространять, а p и q все равно никто не узнает.
Кроме собственно N в открытый ключ входит также число e, которое должно быть меньше числа ? (N)=(p-1)(q-1) и взаимно просто с ним.[ ?(N) - это функция Эйлера, играющая очень важную роль в теории чисел; здесь, правда, используется ограниченный частный случай; в общем случае функция Эйлера от n равна количеству чисел, меньших n и взаимно простых с ним. ] Секретный же ключ - такое число d, что de ? 1 mod ? (N). Алиса может с легкостью вычислить d, но никто другой на это не способен - ведь если трудно разложить N на множители, то трудно и подсчитать функцию Эйлера. Боб теперь, желая зашифровать свое сообщение m, вычисляет y ? m e mod N и передает его Алисе (и всем желающим). Алиса может расшифровать его, вычислив y d ? m ed ? m mod N (последнее сравнение выполняется благодаря малой теореме Ферма - не путать с заметкой на полях «Арифметики»; доказательство малой теоремы достаточно просто и входит в любой базовый учебник теории чисел).
Было бы наивно ожидать, что криптосистемы на эллиптических кривых, столь похожие на дискретное логарифмирование, не поддадутся квантовому компьютеру. И действительно, алгоритм Шора можно без особого труда модифицировать так, чтобы он взламывал описанный выше протокол, а равно и другие аналоги классических криптосистем, основанные на эллиптических кривых.
Но бояться этого, по моему личному мнению, не следует. Квантовые компьютеры сейчас находятся в самом начале своего пути. Пока никто не может предсказать, удастся ли построить квантовый компьютер хоть сколько-нибудь интересного с практической точки зрения размера (текущие рекорды - семь кубитов, одиннадцать кубитов - как-то не впечатляют). А для работы алгоритма Шора, например, нужен квантовый компьютер на стольких кубитах, сколько классических битов в раскладываемом простом числе; на меньшем числе просто ничего не получится. Скорее всего, в ближайшие десятилетия квантовые компьютеры, способные взломать даже сегодняшние шифры, не появятся. А если и появятся - уже существует и активно развивается так называемая квантовая криптография.
Суть криптосистемы Диффи-Хеллмана в том, чтобы перед началом коммуникации с секретным ключом об этом самом ключе договориться (этот процесс в криптографии называют «протоколом 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. Уж не знаю - шутите вы или нет. А эта приписка в «Письмоносце»: «Из отпуска вернулся…» Рад, что из отпуска люди возвращаются довольными, веселыми, отдохнувшими.
Желаю успехов.
С уважением, Сергей
ОТ РЕДАКЦИИ: С «Майкрософтом» мы никогда не шутим, ибо, как учил еще Козьма Прутков, «эти шутки глупы и неприличны». То, что вы обнаружили, - обычная опечатка. Имели в виду ПЕАР - ну, как в предыдущем письме.
Сделайте тему номера не о редакторах и проч. А о самой редакции. То есть о самом помещении (такого на моей памяти еще не было). Например - вот здесь вот у нас то-то, вот здесь то-то.
С уважением Алексей.
ОТ РЕДАКЦИИ: Алексей, никакого «то-то» у нас нет. При входе всегда сидит охрана (за железной дверью с огромным замком). Сразу налево - длинный коридор, кое-где переходящий в холл. Заканчивается тупиком, других входов нет. По бокам - двери в комнаты. Когда-то, в разгар пузыря доткомов, на верстке стояла веб-камера - в духе времени. Но потом верстальщики постепенно вытеснили ее из зоны видимости, и теперь заглянуть извне в редакцию стало совсем трудно. На всех окнах, Алексей, - сигнализация, и охрана ночью не спит!
Конничива, «Компьютерра».
В статье Ваннаха «Младший хирург с “Гремучей змеи”» автор пишет, что определить пол ежа может только другой еж, - в принципе это именно так, поскольку редкий колючий не сворачивается, если его взять на руки, однако есть весьма остроумный альтернативный способ: положить ежа на горизонтально лежащее стекло и выбрать для наблюдения позицию снизу - все становится очевидно…
Гоменнасаюсь, что пишу непосредственно в редакцию, хотя куда же еще - демиург статьи адреса для виртуальной корреспонденции не указывает…
Ответ Михаила Ваннаха: Ура!!! Впервые отзыв по делу!!! И остроумный!!! Есть же квалифицированные природоведы! А ежа еще можно на сканер посадить - так удобнее! Не лил бы ливень, доехал бы до леса и ежа поймал…
ОТ РЕДАКЦИИ: Дзя на, господа! Что в переводе означает «японский - это стильно».
Из переписки на форуме «КТ» по статье Сергея Николенко «Проблемы 2000 года: гипотеза Пуанкаре».
- Объясните, пожалуйста, как можно практически применить это открытие, то есть как оно повлияет на развитие науки и техники.
- Решение Перельманом этой гипотезы подводит жирную черту под проблемой создания антигравитационной тяги, а также прокола пространства Лобачевского и отрицания мира Минковского.
doctor
ОТ РЕДАКЦИИ: В последние дни сенсационный отказ Григория Перельмана, доказавшего гипотезу Пуанкаре, приехать за присужденной ему Филдсовской медалью (см. новость «Потерянный гений» в этом номере), привлек внимание широкой публики не только к личности сорокалетнего питерского математика, но и к самой этой гипотезе. Неожиданно выяснилось - из наблюдений за ссылками в блогах, из переписки с коллегами, - что онлайновый вариант статьи Сергея Николенко в «КТ» #621 стал едва ли не самым востребованным ресурсом по этой теме в Рунете - из серьезных, конечно. А вот обсуждение статьи на форуме самой «КТ» как-то незаслуженно осталось в тени. Приведенный выше отрывок показывает, что там обнаружились пассажи, по непостижимости далеко превосходящие саму свежедоказанную гипотезу. Единственная гипотеза, которую редакция может выдвинуть по поводу «прокола пространства Лобачевского», - может, это все-таки прикол? Заметим, что тайну слова «прикол» раскрыл в «Письмоносце» «КТ» #636 читатель под псевдонимом СЛОН.
USB-адаптер Planet получает Алексей - за живой интерес к нашему скромному прибежищу. Приз предоставлен Торговым Домом «Бурый Медведь».
Здесь стоит немного порассуждать о том, что значит «вычислительно трудно». В применении к только что перечисленным задачам математически это не значит ровным счетом ничего - никаких доказательных утверждений о вычислительной трудности разложения простых чисел или дискретного логарифмирования не существует. Однако много лет подряд криптографы всего мира пытались найти эффективные алгоритмы для решения этих задач - и не преуспели. Криптографы стараются использовать как можно больше задач, для которых еще не найдены эффективные алгоритмы [В этом смысле примечательно, что до сих пор неизвестны криптографические протоколы, основанные на NP-трудных задачах. Разумеется, такие протоколы были бы надежнее любых других - разложение чисел на простые множители или дискретный логарифм отлично укладываются в NP, и более того - дешифровка любой криптосистемы должна укладываться в NP, ведь при наличии секретного ключа, играющего роль подсказки, расшифровать сообщение должно быть возможно. Поиск связанных с NP-трудными задачами протоколов или обоснование (не путать с доказательством) того, что построить их невозможно, - одна из самых интересных задач современной криптографии, заслуживающая отдельного разговора]. В рамках этой концепции и были разработаны криптосистемы, основанные на эллиптических кривых.
Эллиптические кривые
Начнем сразу с определения. Эллиптические кривые - это кривые вида y^2 =x^3 +ax+b. [В полях размера 2m («полях характеристики 2»; к ним относится и привычное программистам поле из двух элементов) определения становятся чуть более сложными, а стандартные доказательства и рассуждения перестают работать; в алгебре и алгебраической геометрии случай характеристики 2 всегда стоит особняком и требует более изощренной техники, нежели все остальные. Поэтому в дальнейшем мы не будем его рассматривать]
Хотя примеры, изображенные на стр. 58, нарисованы на плоскости, то есть на множестве пар вещественных чисел (x, y), в криптографии все структуры, разумеется, должны быть дискретными. Поэтому решения уравнения ищутся над конечными полями. Чтобы конечное множество могло стать полем, его размер должен иметь вид p^m , где p - простое число. Конечное поле с простым количеством элементов (m=1) можно представлять как множество неотрицательных целых чисел, меньших p, в котором все алгебраические операции производятся «по модулю p» (то есть с переходом к остатку от деления результата на p). В криптографии используются конечные поля двух типов - с простым количеством элементов (m=1) и «поля характеристики два» (у которых 2 m элементов); мы ограничимся первым случаем. Кстати, термин «эллиптическая кривая» над конечным полем в изрядной степени теряет смысл - какая же это кривая, если это конечное множество точек? Но о терминах спорить - последнее дело, особенно в математике, где белая лошадь, в полном соответствии с Гунсунь Лун-цзы, может оказаться вовсе не лошадью.Ранее мы говорили, что сложность криптосистемы Диффи-Хеллмана связана с дискретным логарифмированием. Однако конструкция, аналогичная использованной в этой системе, может быть реализована над любым множеством, где есть похожая на умножение операция (например, сложение), подчиняющаяся своим естественным законам (такое множество называется в математике группой). Суть применения эллиптических кривых в криптографии сводится к тому, что группа чисел по простому модулю (как было в криптосистеме Диффи-Хеллмана) заменяется группой решений уравнения y^2 = x^3+ax+b. Осталось лишь указать, как складывать друг с другом решения такого уравнения.
P+(-P)=O.
Над конечными полями таких картинок не нарисуешь, но если выразить эти операции алгебраически, то все сойдется.
Вот, собственно, и все. Эллиптический аналог криптосистемы Диффи-Хеллмана выглядит так. Алиса и Боб выбирают (и сообщают всем) эллиптическую кривую, поле и точку B, лежащую на этой кривой. Затем Алиса секретно выбирает число a и подсчитывает точку aB (складывает B с самой собой a раз), а Боб выбирает число b и вычисляет bB. Затем они обмениваются полученными результатами, и их общим секретным ключом становится точка abB. Чтобы взломать этот шифр, нужно научиться по aB и B вычислять a - это в точности аналог дискретного логарифмирования!
В чем же преимущество шифров, основанных на эллиптических кривых? В том, что в них можно использовать меньшие по величине простые числа, чем в классических системах с открытым ключом.
Квантовый взлом
Напоследок поговорим о том, что многим кажется серьезной угрозой для современной криптографии, - квантовых компьютерах и их возможностях. Прежде всего напомню, что квантовая информатика фактически ведет свою историю с того, что Питер Шор (Peter Shor) в 1994 году представил алгоритмы, которые за полиномиальное время раскладывали числа на простые множители и подсчитывали дискретные логарифмы - на квантовом компьютере, разумеется.
Математика системы RSA
Секретный ключ Алисы в RSA - это два простых числа p и q. Чем больше эти числа, тем шифр надежнее. Именно поэтому многие организации готовы платить деньги за большие простые числа; давно существуют онлайн-проекты распределенных вычислений по поиску простых чисел. Алиса публикует произведение этих чисел N=pq. Ключевое предположение, на котором основана RSA, - то, что большое число трудно разложить на множители. То есть N можно распространять, а p и q все равно никто не узнает.
Кроме собственно N в открытый ключ входит также число e, которое должно быть меньше числа ? (N)=(p-1)(q-1) и взаимно просто с ним.[ ?(N) - это функция Эйлера, играющая очень важную роль в теории чисел; здесь, правда, используется ограниченный частный случай; в общем случае функция Эйлера от n равна количеству чисел, меньших n и взаимно простых с ним. ] Секретный же ключ - такое число d, что de ? 1 mod ? (N). Алиса может с легкостью вычислить d, но никто другой на это не способен - ведь если трудно разложить N на множители, то трудно и подсчитать функцию Эйлера. Боб теперь, желая зашифровать свое сообщение m, вычисляет y ? m e mod N и передает его Алисе (и всем желающим). Алиса может расшифровать его, вычислив y d ? m ed ? m mod N (последнее сравнение выполняется благодаря малой теореме Ферма - не путать с заметкой на полях «Арифметики»; доказательство малой теоремы достаточно просто и входит в любой базовый учебник теории чисел).
Было бы наивно ожидать, что криптосистемы на эллиптических кривых, столь похожие на дискретное логарифмирование, не поддадутся квантовому компьютеру. И действительно, алгоритм Шора можно без особого труда модифицировать так, чтобы он взламывал описанный выше протокол, а равно и другие аналоги классических криптосистем, основанные на эллиптических кривых.
Но бояться этого, по моему личному мнению, не следует. Квантовые компьютеры сейчас находятся в самом начале своего пути. Пока никто не может предсказать, удастся ли построить квантовый компьютер хоть сколько-нибудь интересного с практической точки зрения размера (текущие рекорды - семь кубитов, одиннадцать кубитов - как-то не впечатляют). А для работы алгоритма Шора, например, нужен квантовый компьютер на стольких кубитах, сколько классических битов в раскладываемом простом числе; на меньшем числе просто ничего не получится. Скорее всего, в ближайшие десятилетия квантовые компьютеры, способные взломать даже сегодняшние шифры, не появятся. А если и появятся - уже существует и активно развивается так называемая квантовая криптография.
Математика криптосистемы Диффи-Хеллмана
Суть криптосистемы Диффи-Хеллмана в том, чтобы перед началом коммуникации с секретным ключом об этом самом ключе договориться (этот процесс в криптографии называют «протоколом 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. Уж не знаю - шутите вы или нет. А эта приписка в «Письмоносце»: «Из отпуска вернулся…» Рад, что из отпуска люди возвращаются довольными, веселыми, отдохнувшими.
Желаю успехов.
С уважением, Сергей
ОТ РЕДАКЦИИ: С «Майкрософтом» мы никогда не шутим, ибо, как учил еще Козьма Прутков, «эти шутки глупы и неприличны». То, что вы обнаружили, - обычная опечатка. Имели в виду ПЕАР - ну, как в предыдущем письме.
Сделайте тему номера не о редакторах и проч. А о самой редакции. То есть о самом помещении (такого на моей памяти еще не было). Например - вот здесь вот у нас то-то, вот здесь то-то.
С уважением Алексей.
ОТ РЕДАКЦИИ: Алексей, никакого «то-то» у нас нет. При входе всегда сидит охрана (за железной дверью с огромным замком). Сразу налево - длинный коридор, кое-где переходящий в холл. Заканчивается тупиком, других входов нет. По бокам - двери в комнаты. Когда-то, в разгар пузыря доткомов, на верстке стояла веб-камера - в духе времени. Но потом верстальщики постепенно вытеснили ее из зоны видимости, и теперь заглянуть извне в редакцию стало совсем трудно. На всех окнах, Алексей, - сигнализация, и охрана ночью не спит!
Конничива, «Компьютерра».
В статье Ваннаха «Младший хирург с “Гремучей змеи”» автор пишет, что определить пол ежа может только другой еж, - в принципе это именно так, поскольку редкий колючий не сворачивается, если его взять на руки, однако есть весьма остроумный альтернативный способ: положить ежа на горизонтально лежащее стекло и выбрать для наблюдения позицию снизу - все становится очевидно…
Гоменнасаюсь, что пишу непосредственно в редакцию, хотя куда же еще - демиург статьи адреса для виртуальной корреспонденции не указывает…
Ответ Михаила Ваннаха: Ура!!! Впервые отзыв по делу!!! И остроумный!!! Есть же квалифицированные природоведы! А ежа еще можно на сканер посадить - так удобнее! Не лил бы ливень, доехал бы до леса и ежа поймал…
ОТ РЕДАКЦИИ: Дзя на, господа! Что в переводе означает «японский - это стильно».
Из переписки на форуме «КТ» по статье Сергея Николенко «Проблемы 2000 года: гипотеза Пуанкаре».
- Объясните, пожалуйста, как можно практически применить это открытие, то есть как оно повлияет на развитие науки и техники.
- Решение Перельманом этой гипотезы подводит жирную черту под проблемой создания антигравитационной тяги, а также прокола пространства Лобачевского и отрицания мира Минковского.
doctor
ОТ РЕДАКЦИИ: В последние дни сенсационный отказ Григория Перельмана, доказавшего гипотезу Пуанкаре, приехать за присужденной ему Филдсовской медалью (см. новость «Потерянный гений» в этом номере), привлек внимание широкой публики не только к личности сорокалетнего питерского математика, но и к самой этой гипотезе. Неожиданно выяснилось - из наблюдений за ссылками в блогах, из переписки с коллегами, - что онлайновый вариант статьи Сергея Николенко в «КТ» #621 стал едва ли не самым востребованным ресурсом по этой теме в Рунете - из серьезных, конечно. А вот обсуждение статьи на форуме самой «КТ» как-то незаслуженно осталось в тени. Приведенный выше отрывок показывает, что там обнаружились пассажи, по непостижимости далеко превосходящие саму свежедоказанную гипотезу. Единственная гипотеза, которую редакция может выдвинуть по поводу «прокола пространства Лобачевского», - может, это все-таки прикол? Заметим, что тайну слова «прикол» раскрыл в «Письмоносце» «КТ» #636 читатель под псевдонимом СЛОН.
USB-адаптер Planet получает Алексей - за живой интерес к нашему скромному прибежищу. Приз предоставлен Торговым Домом «Бурый Медведь».