Наука: Проблемы 2000 года: гипотеза Римана

8 августа 1900 года на 2-м Международном конгрессе математиков в Париже один из величайших математиков современности Давид Гильберт сформулировал двадцать три задачи, которые во многом предопределили развитие математики XX столетия. В 2000 году специалисты из Clay Mathematics Institute решили, что грешно входить в новое тысячелетие, не наметив новую программу развития, -тем более что от двадцати трех проблем Гильберта остались лишь две[Еще две считаются слишком расплывчатыми или нематематическими, еще одна была решена частично, а по поводу еще одной — знаменитой континуум-гипотезы — консенсус пока не достигнут (подробнее об этом)].

В результате появился знаменитый список из семи задач, за полное решение любой из которых обещан миллион долларов из специально учрежденного фонда. Чтобы получить деньги, нужно опубликовать решение и подождать два года; если в течение двух лет никто его не опровергнет (будьте уверены — попытаются), вы получите миллион вожделенных зеленых бумажек.

Я попытаюсь изложить суть одной из этих задач, а также постараюсь (в меру своих скромных сил) объяснить ее сложность и важность. Настойчиво рекомендую зайти на официальный сайт конкурса www.claymath.org/millennium; опубликованные там описания проблем полны и интересны, и именно они стали главным источником при написании статьи.

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

1 + 2 + 3 + 4 + 5 + … = —1/12.

Нет, занятие не было посвящено гипотезе Римана, и узнал я о ней вовсе не от Николая Александровича. Но формула, тем не менее, имеет к гипотезе самое прямое отношение. И что удивительно — это кажущееся абсурдным равенство действительно верно. Точнее сказать, не совсем оно, но дьявол деталей тоже вскоре будет удовлетворен.

В 1859 году Бернард Риман (Bernhard Riemann) опубликовал статью (или, как тогда выражались, мемуар), которой была суждена очень долгая жизнь. В ней он изложил совершенно новый метод асимптотической оценки распределения простых чисел. В основе метода лежала функция, связь которой с простыми числами обнаружил еще Леонард Эйлер, но которая все же получила имя математика, продолжившего ее на всю комплексную плоскость: так называемая дзета-функция Римана. Определяется она очень просто:

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

Рассматривать формулу для отрицательных s кажется дурной шуткой: ну какой смысл складывать, например, все положительные целые числа или, тем более, их квадраты или кубы? Однако комплексный анализ — упрямая наука, и свойства дзета-функции таковы, что ее можно продолжить на всю плоскость. Это и было одной из идей Римана, изложенных в мемуаре 1859 года. У полученной функции только одна особая точка (полюс): s = 1, а, например, в отрицательных вещественных точках функция вполне определена. Именно значение аналитически продолженной дзета-функции в точке —1 и выражает формула, с которой я начал этот раздел.

(Специально для патриотов и неравнодушных к истории науки людей отмечу в скобках, что, хотя мемуар Бернарда Римана внес в теорию чисел много свежих идей, он не был первым исследованием, в котором распределение простых чисел изучалось аналитическими методами. Впервые это сделал наш соотечественник Пафнутий Львович Чебышёв, 24 мая 1848 года прочитавший в петербургской Академии наук доклад, в котором изложил ставшие классическими асимптотические оценки количества простых чисел.)

Но вернемся к Риману. Ему удалось показать, что распределение простых чисел — а это центральная проблема теории чисел — зависит от того, где дзета-функция обращается в нуль. У нее есть так называемые тривиальные нули — в четных отрицательных числах (—2, —4, —6, …). Задача состоит в том, чтобы описать все остальные нули дзета-функции.

Этот орешек вот уже полторы сотни лет не могут разгрызть самые талантливейшие математики планеты.

Правда, мало кто сомневается в том, что гипотеза Римана верна. Во-первых, численные эксперименты более чем убедительны; о последнем из них рассказывает статья Хавьера Гурдона (Xavier Gourdon), название которой говорит само за себя: «Первые 10 13 (10 в 13-ой) нулей дзета-функции Римана и вычисление нулей на очень большой высоте» (вторая часть названия означает, что предложен метод вычисления не только первых нулей, но и некоторых, пусть и не всех, более далеких, вплоть до нулей с номером около 10 24 (10 в 24-ой)). Эта работа пока венчает более чем столетнюю историю попыток проверки гипотезы Римана для некоторого количества первых нулей. Разумеется, контрпримеров к гипотезе Римана не найдено. Кроме того, строго установлено, что больше 40% нулей дзета-функции гипотезе удовлетворяют.

Второй аргумент напоминает одно из доказательств существования Бога, опровергнутых еще Иммануилом Кантом. Если Риман все же ошибся, то неверной станет очень много красивой и правдоподобной математики, построенной в предположении, что гипотеза Римана правильна. Да, этот аргумент не имеет научного веса, но все же… математика — это наука, где красота играет ключевую роль. Красивое, но неверное доказательство сплошь и рядом оказывается полезнее, чем верное, но некрасивое. Так, например, из неудачных попыток доказать великую теорему Ферма выросло не одно направление современной алгебры. И еще одно эстетическое замечание: теорема, аналогичная гипотезе Римана, была доказана в алгебраической геометрии. Получившаяся теорема Делиня (Deligne) по праву считается одним из самых сложных, красивых и важных результатов математики XX столетия.

Итак, гипотеза Римана, по всей видимости, верна — но не доказана. Кто знает, возможно, сейчас этот журнал читает человек, которому суждено войти в историю математики, доказав гипотезу Римана. В любом случае, как и со всеми остальными великими задачами, сразу предупреждаю: не пытайтесь повторить эти трюки дома. Иными словами, не пытайтесь решать великие проблемы, не поняв теории, которая их окружает. Сэкономите нервы и себе, и окружающим.

На десерт — еще немного интересного о дзета-функции. Оказывается, у нее есть и практические применения, и даже физический смысл. Более того, и гипотеза Римана (точнее говоря, ее обобщение, считающееся столь же сложным, сколь и она сама) имеет прямые практические следствия. Например, одной из важных вычислительных задач является проверка чисел на простоту (дано число, нужно сказать, простое оно или нет). Самый теоретически быстрый на данный момент алгоритм решения этой задачи — тест Миллера-Рабина (Miller-Rabin test) — работает за время O(log n), где n — данное число (соответственно log n — длина входа алгоритма). Однако доказательство того, что он работает так быстро, опирается на гипотезу Римана.

Впрочем, тест на простоту — не слишком сложная проблема с точки зрения теории сложности (в 2002 году был разработан не зависящий от гипотезы Римана алгоритм, который медленнее теста Миллера-Рабина, но тоже полиномиален). Раскладывать числа на простые сомножители гораздо интереснее (и прямые криптографические приложения налицо — стойкость схемы RSA зависит от того, можно ли быстро разложить число на простые), и здесь гипотеза Римана тоже является необходимым условием для доказательства оценок времени работы некоторых быстрых алгоритмов.

Обратимся к физике. В 1948 году голландский ученый Хендрик Казимир (Hendrik Casimir) предсказал эффект, носящий теперь его имя[Эффект Казимира долгое время оставался лишь изящной теоретической идеей; однако в 1997 году Стив Ламоро (Steve K. Lamoreaux), Умар Мохидин (Umar Mohideen) и Анушри Руа (Anushri Roy) смогли провести подтверждающие предшествующую теорию эксперименты]. Оказывается, если сблизить две незаряженные металлические пластины на расстояние в несколько атомных диаметров, они притянутся друг к другу за счет флуктуаций расположенного между ними вакуума — постоянно рождающихся пар частиц и античастиц. Этот эффект чем-то напоминает притяжение подплывших слишком близко друг к другу судов в океане (еще больше он напоминает теорию Стивена Хокинга [Stephen Hawking] о том, что черные дыры все же излучают энергию, — впрочем, тут трудно сказать, кто кого напоминает). Расчеты физической модели этого процесса показывают, что сила, с которой притягиваются пластины, должна быть пропорциональна сумме частот стоячих волн, возникающих между пластинами. Вы уже догадались — эта сумма сводится к сумме 1+2+3+4+…. И более того — правильным значением этой суммы для расчетов эффекта Казимира является именно —1/12.

Но и это еще не все. Некоторые исследователи считают, что дзета-функция играет важную роль… в музыке! Возможно[Я пишу «возможно», потому что единственный источник, который мне удалось разыскать, это переписка в usenet-конференции sci.math. Если вы (читатели) сможете найти более авторитетные источники, мне будет очень интересно об этом услышать], максимумы дзета-функции соответствуют значениям частот, которые могут служить хорошей основой для построения музыкальной шкалы (такой, как наш нотный стан). Что ж, Герман Гессе в своей «Игре в бисер» не зря объявил Игру комбинацией математики и музыки: между ними и впрямь много общего…

ОПЫТЫ: Хорошо ли защищены ваши данные?

Во многих организациях руководство полагает, что раз денег на защиту данных выделяется немало, то и защищены данные качественно, то есть для их взлома нужно нанимать хакеров редкой квалификации, платить им немалые суммы, идти на контакт с криминалом и вообще быть гораздо умнее конкурентов (потенциальных заказчиков кражи).

Кроме того, принято считать, что хакерской атаки можно не опасаться, ибо хакеров мало. Олигарху еще есть какой-то смысл бояться, что их наймут конкуренты, а среднему и малому бизнесу — нет.

Эти стереотипы не соответствуют действительности. Ниже мы опишем несколько реальных заказов на аудит компьютерной безопасности[Как сообщил нам автор, описанные ниже ситуации относятся в основном к 2003 году. — Прим. ред.].

Заказчик Куваев (здесь и далее фамилии и информация, позволяющая идентифицировать фамилии, изменены) — сотрудник крупнооптовой фирмы-импортера компьютерных комплектующих, работает старшим менеджером по закупкам в США. Традиционно бо,льшая часть переговоров Куваева с партнерами происходит по ICQ.

Руководство фирмы прочитало в газете «Известия», что программа ICQ — ненадежная. Учитывая, что список американских компаний, у которых закупается товар, есть информация конфиденциальная, цены и объемы закупок — средне-конфиденциальная, а из фирмы недавно со скандалом ушел один из ключевых сотрудников, руководство решило провести аудит компьютерной безопасности. Перед экспертом был поставлен вопрос: что может сделать враг с бюджетом в $1000?

Изучение ситуации показало, что ICQ-номер Куваева зарегистрирован больше семи лет назад. При регистрации нужно было указывать e-mail-адрес. Вероятно, в тот момент у Куваева не было e-mail-адреса или он не хотел его давать, — так или иначе, был указан адрес qwert@lkjlkj.asdfsdfs.com. Предположительно, Куваев набрал на клавиатуре случайную последовательность символов, выглядящую как e-mail-адрес (даже доменного имени asdfsdfs.com не существовало).

Атака состояла в регистрации доменного имени asdfsdfs.com, создании в домене компьютера lkjlkj.asdfsdfs.com и заведении на нем пользователя qwert; после этого в фирму Mirabilis (владельцы системы ICQ) была направлена просьба выслать якобы утраченный пароль на адрес, указанный при регистрации, что и было выполнено.

Зная пароль, можно его сменить (то есть сделать невозможным пользование данным номером для легального адресата), а можно и получать всю текущую информацию от многочисленных поставщиков.

Если бы атака была проведена врагом, как подсказал нам Куваев, враг мог уведомлять соединяющихся по ICQ поставщиков об изменении адреса склада в Финляндии и просить их срочно перенаправить поток грузов по новому адресу. Учитывая объемы поставок и принятую в этом бизнесе оплату с отсрочкой 60 суток после получения товара, враг мог неплохо поживиться и создать немало проблем организации, в которой работает Куваев…

Демонстрация уязвимости была осуществлена за двое суток, расходы по осуществленному пути составили $150. В Москве есть десятки организаций, способных осуществить такую атаку[Здесь и далее формулировки взяты из официальных отчетов. — Прим. ред].

Специфика работы заказчика была такова, что клиенты в офис не приходили, а деятельность в целом носила сугубо конфиденциальный характер. Перед аудитором был поставлен вопрос: может ли враг, располагающий суммой в $5000, украсть какие-либо данные. Персонал заказчика о мероприятиях уведомлен не был.

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

Удачной оказалась следующая атака:

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

Сообщения Чхеидзе в форумах были проанализированы. Выяснилось, что он разочарован имеющимися в Рунете музыкальными серверами, уделяющими недостаточное, на его взгляд, внимание песням народов Мексики.

Был создан русский сайт, полностью посвященный мексиканским песням (усилиями внешнего специалиста была переведена часть известного испаноязычного сайта, а также сделаны два изменения, соответствующие критике Чхеидзе в адрес существующих сайтов).

На Чхеидзе была осуществлена социальная атака — плакат с рекламой сайта был трижды опущен ему в почтовый ящик, повешен на дверь подъезда, положен под дворник лобового стекла машины, ему был послан спам с рекламой сайта. Аналогичные меры были предприняты в отношении девушки, которая, как предполагалось, имела виды на Чхеидзе.

Чхеидзе с рабочего компьютера зашел на созданный под него сайт. Основной удар планировался по линии продажи ему, как «первому правильно ответившему на все три вопроса», за $20 слегка модифицированного «фирменного» диска, которого в продаже в России не было и о цене которого в США ($110) Чхеидзе не раз сожалел в форумах. Но аудитору повезло — удалось обойтись более простыми средствами. На рабочем компьютере Чхеидзе был установлен Internet Explorer 5.01, хоть и с SP1, но без заплатки Q275609. Поэтому, пока Чхеидзе наслаждался музыкой и переписывал с сайта файлы, сайт переписал несколько файлов с сетевых дисков заказчика.

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

Демонстрация уязвимости была осуществлена за девять суток, прямые расходы по осуществленному пути составили $1200. В Москве есть организации, способные осуществить такую атаку.

Заказчик Петренко — работающий индивидуально консультант по таможенным вопросам. Важную информацию к клиентам и от них он, не доверяя Интернету, переносил в наручных часах, в которые было встроено устройство с энергонезависимой flash-памятью и USB-интерфейсом (далее — флэшка). Данные на флэшке — сугубо конфиденциальны. Содержимое шифровалось идущим в комплекте с флэшкой программным обеспечением. Перед экспертом был поставлен вопрос: насколько такой способ гарантирует сокрытие данных в случае потери или физического изъятия флэшки при бюджете врага $2000?

Изучение ситуации показало, что Петренко неправильно оценивает слабое место в системе.

К одному из своих клиентов Петренко сел в машину, благодаря чему выяснилось, что клиента зовут Вахитов Сергей Рустемович.

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

На следующий день ничего не подозревающему Петренко были предъявлены и пароль, и все его файлы. Удивленный, он лишь огорченно вымолвил: «Черт возьми, я так и думал, что она не просто так на ночь старалась остаться. Но как ей удалось открыть сейф?!»

Демонстрация уязвимости была осуществлена за шесть суток, прямые расходы по осуществленному пути составили $800. В Москве есть десятки организаций, способных осуществить такую атаку.

Заказчик Левитов — руководитель фирмы, занимающейся финансовыми консультациями. Перед экспертом был поставлен общий вопрос о слабых местах в компьютерной безопасности фирмы. Сотрудники Левитова были уведомлены о предстоящей экспертизе.

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

Также исследование показало, что один из компьютеров без ведома Левитова использовался в качестве сервера для хранения и распространения фотографий и видеозаписей порнографического содержания. Кто именно организовал порносервер, выяснить не удалось, но счета за Интернет оплачивал Левитов.

Российская компания, обслуживавшая компьютерный парк крупного корпоративного клиента, использовала программный комплекс автоматизации предприятий, поставляемый одной из ведущих немецких софтверных фирм. Руководство компании обдумывало поступившее от немецкой стороны предложение стать их эксклюзивными представителями на территории России и стран СНГ по системам САПР, дававшее возможность выйти с этими продуктами на рынок других корпоративных клиентов. План предусматривал значительные затраты как в виде платежей немецкой стороне, так и в виде вложений в России. Руководство компании поставило перед экспертом вопрос: верно ли утверждение немецкой стороны о невозможности взлома защиты данной программы и записи ее на пиратский CD?

Бюджет врага был оставлен на усмотрение эксперта и задан как «типичный для пирата».

Исследование показало, что уровень цен на базовый модуль САПР данной фирмы в Германии составляет около 15000 евро (лицензия на десять пользователей), и каждый дополнительный модуль стоит от 700 до 4000 евро. Для домашнего пользователя программа интереса не представляет. Отсюда был сделан вывод о малой вероятности попадания программы к пиратам путем ее закупки и взлома легальной версии. Однако вероятным является приобретение крупной компанией лицензии на десять пользователей, взлом защиты усилиями своих или сторонних специалистов и установка программы внутри компании на значительное число компьютеров. После этого при неблагоприятном стечении обстоятельств можно ожидать появления взломанного дистрибутива и у пиратов.

Исходя из этого, бюджет проекта был оценен в $5000.

Изучение предоставленного заказчиком дистрибутива показало, что для защиты используется комплекс, состоящий из двух частей: программной защиты, сделанной специалистами фирмы-разработчика, и ключа HASP фирмы Aladdin для LPT-порта. Как известно, некий хакер из Санкт-Петербурга еще в 2000 году написал низкоуровневый драйвер ключа HASP, который устанавливается на место стандартного драйвера и самостоятельно обрабатывает вызовы к ключу. Однако фирма-разработчик либо не знала об этом, либо не сочла возможным приобрести новую версию HASP (для которой общеизвестного пути взлома по состоянию на сегодняшний день нет).

Изучение программной защиты, написанной специалистами фирмы-разрабочика, показало, что она заключается в привязке к MAC-адресу сетевой карты (MAC-адрес представляет собой уникальный шестнадцатеричный серийный номер, назначаемый каждому сетевому устройству Ethernet для идентификации его в сети, например 12:34:56:78:90:AB). Атака на эту защиту состояла в установке второй сетевой карты, в которой можно изменять MAC-адрес (такие, вопреки стандарту и общественному мнению, существуют).