Новый отечественный стандарт на ЭЦП

В 2001 году на конференции, проводившейся Ассоциацией документальной элект­росвязи и представителями ФАПСИ, было официально объявлено об утверждении нового стандарта на электронную цифровую подпись. Этот стандарт, основанный на методе эллиптических кривых, вступает в силу с 1 июля 2002 года. Он придет на сме­ну тому стандарту, который используется сейчас и который мы рассматривали выше. Новый стандарт будет иметь тот же номер, что и старый, за исключением того, что изменятся лишь цифры, обозначающие год.

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

Ввод в действие нового стандарта связан с тем, что, по словам гендиректора ФАПСИ, действующий стандарт уже к 2003 году не будет обеспечивать достаточный уровень защиты. И хотя для подделки одной ЭЦП, соответствующей старому ГОСТу, сегодня требуется около 10 лет работы 10 000 компьютеров, он же и существенно увеличивает длину обрабатываемых сообщений (в российском алгоритме использу­ются очень длинные ключи).

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

Сегодня работа стандартов ЭЦП основана, в основном, на:

– классической математике;

– эллиптических кривых, использующих теорию алгебраических чисел.

Если первый подход уже давно известен, то второй метод подразумевает более короткий ключ, при этом процедуры обоснования его надежности сложнее, поскольку экспертов в области эллиптических кривых гораздо меньше, чем специалистов по те­ории чисел. Ключи в алгоритме с использованием эллиптических кривых могут быть созданы в 100 раз быстрее и занимают гораздо меньше места, чем ключи в алгоритме RSA.

Совсем недавно для оценки криптостойкости алгоритма, основанного на методе эллиптических кривых, были предприняты попытки взлома шифра с 97-битным клю­чом. Эта задача, поставленная Французским национальным институтом информатики (INRIA), была решена командой энтузиастов под руководством ирландского матема­тика Роберта Харли (Robert Harley). Для этого потребовались 40-дневные объединен­ные усилия 195 добровольцев из 20 стран и 740 независимых компьютеров. По словам Роберта Харли, решить задачу шифрования с 97-битным" дискретным алгоритмом на основе эллиптических кривых труднее, чем взломать 512-битный несимметричный шифр RSA, который сегодня является промышленным стандартом.

Несколько позднее канадской компанией Certicom, занимающейся вопросами шиф­рования, которая хотела привлечь исследователей к тестированию уровня защиты, обеспечиваемого алгоритмом ЕСС (Elliptic Curve Cryptography), было инициировано исследование, посвященное анализу уже 109-разрядного ключа. Эта задача, получив­шая известность под кодовым наименованием ЕСС2К.108, была решена с помощью распределенной сети, включающей большое число компьютеров. В ее решении приня­ли участие 1300 человек из 40 стран, перебиравшие всевозможные комбинации клю­чей до тех пор, пока не был обнаружен искомый. Исходное тестовое сообщение было закодировано с помощью метода эллиптических кривых.

В своем проекте Certicom использовала свободно распространяемое программное обеспечение, которое Роберт Харли разработал для вычисления более 215 точек на эллиптической кривой, относящейся к классу кривых Коблитца. Данные о 2 млн «вы­деленных» точек были посланы на сервер AlphaServer в INRIA, где участники могли в реальном времени наблюдать за поиском ключа. Для взлома алгоритма использова­лись 9500 компьютеров в Internet. По данным INRIA, две трети вычислений пришлось на долю рабочих станций с операционной системой Unix, а одна треть — на компьюте­ры с Windows.

На решение такой задачи на одном компьютере с процессором Pentium II/450 МГц потребовалось бы примерно 500 лет. «Объем вычислений, проделанных нами, боль­ше, чем нужно для взлома системы, защищенной открытым ключом наподобие RSA длиной как минимум 600 разрядов», — отметил Эрьен Ленстра, вице-президент по технологиям подразделения Citibank в Нью-Йорке, который также принимал участие в проекте. И это с учетом того, что компания Certicom выбрала кривую, отличающую­ся свойствами, упрощающими задачу взлома кода, и была проделана примерно деся­тая часть всех вычислений, которые в обычных условиях должны потребоваться для взлома 109-разрядного ключа при шифровании по кривой. Проведенный проект пока­зал относительную уязвимость некоторых кривых с особыми свойствами и подтвер­дил тот факт, что произвольные кривые лучше подходят для оптимальной защиты.

Остановимся вкратце на рассмотрении метода эллиптических кривых, использо­ванного в новом стандарте на электронную цифровую подпись. Эллиптическая кривая описывается математическим уравнением вида:

у2 = x3 + ax + b,

где все вычисления выполняются по модулю выбранного просто числа р и 4aЗ + 27b2 = 0.

Этот случай называется нечетным, т.к. модуль р берется для некоторого числа нечетных значений р. Четный случай аналогичен, но вычисления при этом ведутся в конечном поле GF(2m) для некоторого целого числа т.

Проблему дискретного логарифма DLP (Discrete Logarithm Problem) кратко мож­но сформулировать так: «По заданному простому числу р, основанию g и значению gx(mod р) найти значение х». Причем проблема может быть сформулирована в огра­ниченной области.

Полезное для криптографии свойство эллиптических кривых состоит в том, что если взять две различных точки на кривой (рис. 4.37), то соединяющая их хорда пере­сечет кривую в третьей точке (так как мы имеем кубическую кривую). Зеркально отра­зив эту точку по оси X, мы получим еще одну точку на кривой (так как кривая симмет­рична относительно оси X). Это позволяет точно определить форму кривой. Если мы обозначим две первоначальные точки Р и Q, то получим последнюю (отраженную) точку P+Q. Представленное «сложение» удовлетворяет всем известным алгебраичес­ким правилам для целых чисел, позволяя определить единственную дополнительную точку, которая называется бесконечно удаленной точкой и выполняет роль нуля (на­чала отсчета) для целых чисел.

Другими словами, можно определить форму кривой по заданным точкам (плюс бесконечно удаленной точке), что является обычным алгебраическим действием. Вы­ражаясь математическими терминами, можно определить конечную абелеву группу (абстрактную группу с коммутативной бинарной операцией) на точках кривой, где нулем будет бесконечно удаленная точка. В частности, если точки Р и Q совпадут, то можно вычислить Р+Р. Развивая эту идею, можно определить kP для любого целого числа k, и, следовательно, определить значение Р и значение наименьшего целого чис­ла k, такого что kP = F, где F — бесконечно удаленная точка. Теперь можно сформули­ровать Проблему дискретного логарифма эллиптической кривой (Elliptic Curve Discrete Logarithm Problem, ECDLP), на которой основана рассматриваемая система:

– Для эллиптических кривых и базовых точек решение уравнений типа «Даны базо­вая точка Р и расположенная на кривой точка kP; найти значение k.» представляет весьма и весьма сложную задачу. С точки же зрения криптографии на основе эл­липтических кривых имеется возможность определить новую криптографическую систему (любая стандартная система, основанная на проблеме дискретного лога­рифма, аналогична системе основанной на ECDLP). Например, эллиптическая кривая DSA (ECDSA) уже стандартизована (ANSI X9.62), и на ее базе можно реализовать протокол открытого обмена ключами Diffie-Hellman.

– При определении системы эллиптической кривой требуются сама кривая и базовая точка Р. Эти элементы не являются тайной и могут быть одинаковыми для всех пользователей системы. Для данной кривой и точки несложно сгенерировать от­крытые и частные ключи для пользователей (частный ключ представляет просто случайное целое число k, а открытый ключ — точку kP на кривой). Однако чрезвы­чайно трудно создать подходящую кривую и точку. Главное — подсчитать количе­ство точек на кривой. Для этого необходимо выбрать подходящую базовую точку Р, координаты ко­торой должны иметь достаточно большое значение, чтобы гаранти­ровать трудность взлома ECDLP. Но координаты точки Р должны делиться на количество точек на кривой (точки вместе с бесконеч­но удаленной точкой образуют конечную группу). И весьма вероятно, что, найдя число точек на кривой, мы не сможем найти базовую точку. Суще­ствуют и другие ограничения, которые необходимо учесть при построении кривых.

Подводя итог вышеизложенному, можно утверждать, что создание кривых — зада­ча непростая. Пользователи могут применять «стандартные» кривые с помощью спе­циального программного обеспечения, либо создавать собственные кривые, что зани­мает, к сожалению, очень много времени.

Системы на основе эллиптической кривой используют ключи малых размеров. Это значительно снижает требования к вычислительным мощностям по сравнению с тре­бованиями систем на основе RSA. Как это влияет на скорость обработки, показывает табл. 4.10. В ней представлены сравнительные характеристики алгоритмов RSA и ECDSA (нечетный случай) при создании и проверке цифровых подписей. Оба алго­ритма тестировали на параллельных процессорах Motorola 56303 DSP (66 МГц). При этом функция проверки подписи RSA использует е = 65 537.

Таблица 4.10. Сравнительные характеристики алгоритмов RSA и ECDSA (нечетный случай)при создании и проверки цифровой подписи

Алгоритм (длина ключа, бит)	Время выполнения, мс
	Создание подписи	Проверка подписи
RSA (1024)		< 2
ECDSA (160)
RSA (2048)
ECDSA (216)

Как видно из табл. 4.10, при увеличении размеров ключа создание подписей с помо­щью ECDSA производится значительно быстрее, чем в системах RSA. Это различие в еще большей степени проявляется для однопроцессорных систем. С другой стороны, проверка подписи с помощью ECDSA, делается намного медленнее, чем эта же проце­дура в системах RSA и опять же различие усиливается для систем с одним процессором.

Обработка ECDSA может несколько ускориться в «четном» случае. Мощность процессора, затраченная на проверку подписи, при использовании, скажем, ECDSA может замедлить выполнение других приложений в системе. Множество систем име­ют много удаленных устройств, соединенных с центральным сервером, и время, зат­раченное удаленным устройством для создания подписи (несколько секунд), не влия­ет на производительность системы в целом, но сервер должен также и подтверждать подписи, причем очень быстро. В некоторых случаях системы RSA (даже использую­щие большие ключи) возможно, будут более приемлемы, чем криптосистемы на осно­ве эллиптической кривой. Тем не менее, криптосистемы на основе эллиптической кри­вой получают все большее распространение скорее как альтернатива, а не замена систем RSA, поскольку системы ECDLP имеют некоторые преимущества, особенно при ис­пользовании в устройствах с маломощными процессорами и/или маленькой памятью. Типичные области применения алгоритма на основе эллиптической кривой:

– m-commerce (мобильная торговля) (например, WAP, сотовые телефоны, карман­ные компьютеры);

– смарт-карты (например, ЕМУ);

– e-commerce (электронная торговля) и банковские операции (например, SET);

– Internet-приложения (например, SSL).

Из-за очевидной трудности взлома алгоритм ECDLP можно применять для высоко защищенных систем, обеспечивая достаточно высокий уровень безопасности. Как уже говорилось выше, в рассматриваемом алгоритме используются ключи значительно меньшего размера, чем, например, в алгоритмах RSA или DSA. В табл. 4.11 сравнива­ются приблизительные параметры эллиптических систем и RSA, обеспечивающих одинаковую стойкость шифра, которая рассчитывается на основе современных мето­дов решения ECDLP и факторинга (поиска делителей) для больших целых чисел.

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

Длина ключа, бит
Система на основе эллиптической кривой (базовая точка Р)	RSA (длина модуля п)

Из табл.4.11 видно, что, используя эллиптические кривые, можно строить хорошо защищенные системы с ключами явно меньших размеров по сравнению с аналогичны­ми «традиционными» системами типа RSA или DSA. В частности, такие системы ме­нее требовательны к вычислительной мощности и объему памяти оборудования и по­тому удобны, например, для смарт-карт или портативных телефонов.

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

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

– реальная безопасность таких систем все еще недостаточно исследована;

– трудность генерации подходящих кривых;

– несовместимость с другими системами;

– относительно медленная проверка цифровой подписи.

Системами электронного документооборота с использованием ЭЦП оснащены администрация президента и представительства президента в федеральных округах. Сертифицированные средства используют Внешторгбанк (система «Верба»), Сбер­банк, Министерство по налогам и сборам, Пенсионный фонд, внедрена система ЭЦП в аппарате правительства РФ.

Сертификацией средств электронно-цифровой подписи занимается ФАПСИ. Се­годня существуют две сертифицированные системы — «Криптон» фирмы «Анкад» и

«Крипто-про CSP» компании «Крипто-про». Действие сертификата ФАПСИ на систе­му «Верба» производства МО ПНИЭИ фактически закончилось.

По Указу Президента, применение сертифицированных ФАПСИ средств ЭЦП се­годня обязательно для государственных организаций, однако в действительности эта норма легко обойти (например, применение ЭЦП можно назвать «защитой информа­ции»). Так, не сертифицированные в ФАПСИ средства применяются в ФСБ, МИДе и отчасти в Центробанке. Однако по новому закону использование сертифицированных ФАПСИ алгоритмов электронно-цифровой подписи в госорганах планируется сделать строго обязательным.

Дата добавления: 2014-01-07