Асимметричная криптография на эллиптических кривых
В сентябре текущего года группа из 200 человек при помощи 740 компьютеров сумела взломать сообщение, зашифрованное 97-битовым ключом на эллиптических кривых. Задача отняла 16.000 MIPS-лет вычислений, что почти вдвое больше, чем потребовалось команде, взломавшей недавно 512-битовый шифровальный ключ RSA. Компания Certicom, спонсор этого мероприятия, объявила результат доказательством того, что криптография на эллиптических кривых более надёжна, чем RSA. Давайте взглянем на это заявление чуть более предметно.
Все алгоритмы с открытым ключом, будь то алгоритмы для распределения ключей, шифрования или цифровой подписи, базируются на одной из следующих математических проблем: проблеме разложения на множители и проблеме дискретного логарифмирования. (В научной среде есть и другие алгоритмы, но они слишком громоздки, чтобы применять их для реальных прикладных задач.) Защищённость RSA проистекает из сложности разложения на множители (факторизации) больших чисел. Стойкие реализации RSA используют 1024-битовые и даже бóльшие числа. Защищённость большинства других алгоритмов с открытым ключом – Эльгамаля, DSA и т.д. – основана на проблеме дискретного логарифмирования. Обе проблемы очень похожи, и все современные алгоритмы факторизации можно применять к расчёту дискретных логарифмов мультипликативной группы в конечном поле. При грубом сравнении, факторизация числа определённой длины и расчёт его дискретного логарифма потребуют равного объёма работы. Из этого следует, что ключи RSA, Эльгамаля, DSA равной длины будут примерно одинаково надёжны. (Это не совсем верно, но для темы настоящей статьи такое округление сойдёт.)
Для использования всех этих алгоритмов нужно нечто, называемое "алгебраической группой". Когда криптография с открытым ключом была только изобретена, алгоритмы применялись в простейшей алгебраической группе – в группе чисел по модулю n. Например, шифрование RSA – это me mod n, а открытый ключ Диффи-Хеллмана – это gy mod n. Как оказалось, подойдёт любая алгебраическая группа; эллиптические кривые – это просто иная алгебраическая группа.
В криптосистемах на эллиптических кривых открытые и закрытые ключи обозначаются как точки на математическом объекте, называемом эллиптической кривой (не беспокойтесь: что это в действительности такое, не столь уж важно). Дополнение – это операция, объединяющая две точки, чтобы получить третью. Алгоритм выглядит так же, но в математических деталях сильно отличен. Но если все алгебраические группы равно применимы, зачем вообще кого-то волнуют эллиптические кривые? Дело в том, что для дискретно-логарифмического алгоритма на эллиптических кривых мы, по-видимому, можем использовать ключи меньших размеров. (Это не так для RSA, вот почему варианта RSA на эллиптических кривых вам никогда не увидеть.)
Самые быстрые алгоритмы дискретного логарифмирования – квадратичное решето и решето числового поля – используют то, что называется индексным исчислением, а также свойство чисел по модулю n, именуемое гладкостью. В группе эллиптических кривых нет определения гладкости и, следовательно, чтобы взломать основанный на них алгоритм, вы должны прибегать к устаревшим методикам, например, к rho-алгоритму Полларда. Таким образом, нам достаточно использовать ключи, длины которых хватит для защиты от подобных устаревших медленных техник. В итоге, наши ключи оказываются короче. Причём намного короче! Незадолго до упоминавшегося взлома Certicom рекомендовала 163-битовые ключи. Сравните это с рекомендациями к длинам ключей традиционных дискретно-логарифмических алгоритмов, которые составляют по меньшей мере 1024 бита.
Есть ли в рекомендациях Certicom смысл, зависит от того, удастся ли когда-нибудь найти более быстрые алгоритмы для работы с эллиптическими кривыми. Зададимся вопросом: является ли отсутствие гладкости фундаментальным свойством эллиптических кривых или же это просто следствие белых пятен в наших познаниях о них? Или, в более общем смысле, является ли сложность дискретного логарифмирования в группе эллиптических кривых их внутреприсущим качеством или мы в конце концов обнаружим способ, как это делать с той же эффективностью, что и для чисел по модулю n? Если вы полагаетесь на первое, эллиптические кривые всегда будут более надёжны (при равной длине ключа), чем числа по модулю n. Если же вы верите в последнее, то это лишь вопрос времени, прежде чем они будут взломаны.
Certicom бы очень хотелось, чтобы вы верили в первое. Они произносят фразы, наподобие: "Эллиптические кривые как алгебраический / геометрический объект подвергались интенсивному изучение в течение последних 150 лет. Эти работы образовали глубокую и богатую теоретическую базу". Исходя из этого они заключают, что мы можем иметь твёрдую уверенность – новые подвижки в алгебраической теории не принесут разрушительный эффект. По мне, это похоже на выдавание желаемого за действительное. Было бы здорово, если б мы имели 150-летнюю историю работы над криптографическими свойствами эллиптических кривых. Однако у нас этого нет. Всё, что мы имеем – это 150 лет работы над теми свойствами кривых, которые волнуют математиков и которые едва затрагивают то, что интересует криптологов. Криптография на эллиптических кривых была изобретена только в 1985 году, а действительно серьёзно изучалась всего лишь несколько последних лет. Даже сегодня большая часть исследования кривых на типичной математической кафедре университета в основном не связана с криптологией. Разумеется, часть из полученных результатов может по случайности помочь нам в понимании стойкости эллиптических алгоритмов, но изначально это почти никогда не было целью математических научных работ. В последнее время это начинает меняться, но очень медленно. Более того, область работы над эффективными эллиптическими алгоритмами очень нова. Само понятие эффективных алгоритмов даже не возникало до 60х-70х годов, а алгоритмическая теория чисел обрела популярность лишь в два последних десятилетия. До появления компьютеров это всё не имело смысла.
Настоящий ответ на предложенный выше вопрос – "мы не знаем". Мы не знаем, существуют ли эффективные способы вычисление дискретных логарифмов в группе эллиптических кривых. Мы не знаем, есть ли определение гладкости, которое позволит нам применить решето числового поля к эллиптическим кривым. Мы не знаем, сможете ли вы в долгосрочной перспективе использовать короткие ключи с алгоритмами на эллиптических кривых. На ближайшее будущее рекомендации Certicom вполне обоснованны. На сегодняшний день мы не можем вычислять дискретные логарифмы в группе эллиптических кривых столь же эффективно, как с числами по модулю n; в криптосистемах на эллиптических кривых могут использоваться ключи меньших размеров. Но как будет дальше, нам неизвестно.
Есть и другие нюансы, требующие рассмотрения. Сверка подписи на эллиптических кривых – по-прежнему большая проблема, в сравнении с проверкой цифровой подписи RSA. Также все пользователи системы должны использовать общую на всех кривую (в ином случае вы потеряете большинство достоинств эллиптических ключей), однако это негативно сказывается на безопасности: становится проще взломать ключ произвольного пользователя системы, нежели взломать определённый конкретный ключ. Мне бы хотелось видеть углубление анализа по этому аспекту эллиптических кривых.
Я советую, если ваша рабочая среда накладывает ограничения на длину ключей – как в смарт-картах, некоторых мобильных телефонах и пейджерах, где крупные ключи просто не поместятся, – используйте эллиптические кривые. Если выбор стоит между тем, использовать эллиптические кривые или не использовать асимметричные алгоритмы совсем, – используйте эллиптические кривые. Но если у вас нет таких ограничений, используйте RSA. Если вам требуется защита на десятилетия (чего нет практически ни в каких системах) – используйте RSA. Имейте в виду, что однажды – через год, через десять лет, через сто – кто-то может выяснить, как определять гладкость или что-нибудь ещё более полезное для эллиптических кривых. Если подобное произойдёт, вам придётся использовать ключ тех же размеров, что и для устоявшихся дискретно-логарифмических алгоритмов, и тогда вообще пропадёт всякая потребность в эллиптических кривых.
P. S. Те же самые размышления относятся и к факторизации. RSA Security, Inc. любит кормить нас разговорами о многовековой истории математической проблемы разложения на множители и о том, как это должно укреплять нашу уверенность в безопасности RSA. Да, проблема изучалась веками, но лишь недавно исследования подошли хотя бы в непосредственную близость к области криптографии. Более того, до самого последнего времени исследования в факторизации не были благодарной сферой работы; прежде это считалось всего лишь эксцентрическим хобби. А эффективные алгоритмы факторизации изучаются только последние пару десятков лет. По правде говоря, мы даже не имеем представления, насколько в действительности сложна проблема факторизации.
Правда в том, что компании имеют привычку рекламировать свои разработки. Прежде чем делать выбор в пользу того или иного криптоалгоритма, пользователям следует оценить множество различных независимых мнений (мнений сторон, не имеющих прямой финансовой выгоды от результатов сделанного выбора) о том, что они собираются покупать.
Комментарий
Алгоритмы шифрования и подписи на эллиптических кривых в течение последних лет считаются достаточно перспективными. А в последние годы они начали относительно широко применяться на практике. Началось все с единичных экспериментальных и коммерческих продуктов, сейчас дело идет к государственной стандартизации и массовому внедрению. Идут разговоры о полном вытеснении RSA и его аналогов. Стандарты на эллиптические алгоритмы разрабатываются во многих странах. Россия уже в течении нескольких лет использует такой стандарт на электронную подпись – ГОСТ Р 34.10-2001.
Несмотря на все опасения, заметного прогресса во взломе эллиптических алгоритмов достигнуто не было, в то время как стойкость ключей, основанных на традиционных методах, непрерывно снижается из-за успехов в целочисленной факторизации и дискретном логарифмировании. Но, сдругой стороны, не было получено и убедительных теоретических обоснований стойкости эллиптических алгоритмов. Их стойкость все еще обоснована хуже, чем у RSA и аналогов.
Но так ли уж безоблачна стала ситуация за последнее время? Эллиптические алгоритмы оказались очень сложны, разнородны и неоднозначны. Было продемонстрировано большое число атак на ошибки в их реализации. Некоторые ошибки даже чуть не попали в стандарты. Неправильный выбор точек или вспомогательных параметров приводит к нестойкости схемы, в то время как анализ таких схем очень сложен, а выбор многих параметров неочевиден. Следует вспомнить, что и на первые реализации RSA было предложено множество атак, прежде чем был накоплен необходимый опыт.
Наверное, использование принципиально новых алгоритмов может быть оправдано там, где они действительно незаменимы. Речь в первую очередь идет о миниатюрных устройствах, таких как web-сервер размером с монету и памятью в 4 килобайта. Миниатюрные и мобильные устройства, смарт-карты, серверы, обрабатывающие очень большие потоки коммерческих транзакций, – здесь везде баланс от долговременной безопасности смещен впользу экономичности, и работы по внедрению новых алгоритмов идут очень интенсивно.
А выиграют ли от внедрения таких алгоритмов обычные пользователи программ шифрования? Едва ли. Скорость работы с традиционными ассиметричными ключами на современных персональных компьютерах (даже на портативных) достаточно высока. Размер ключей тоже не имеет особого значения. А вот выигрыш в криптостойкости может оказаться призрачным. В первую очередь из-за ошибок в реализации. Здесь разумнее проявить некоторый консерватизм и использовать алгоритмы проверенные временем.
Но тем, кто мыслит в государственных масштабах, всегда хочется иметь единый стандарт. Так, чтобы один алгоритм работал и на сверхминиатюрном устройстве, и на суперкомпьютере. И часто ради этого идут на риск, принося безопасность и проверенность алгоритма в жертву универсальности. И во многом такой подход выигрывает: легче изучать стойкость схем, построенных на едином стандарте. Кроме того, это способствует более быстрому прогрессу в данной области. Так что, скорее всего, если все пойдет удачно, эллиптические кривые смогут заменить давно используемые алгоритмы с открытым ключем. Но, наверное, спешить с этим не стоит.