§ 3. Использование стандартных кривых

Ввиду того что формирование случайных кривых, особенно выполнение этапа подсчета количества точек на кривой, может быть слишком трудной задачей (даже с применением описанного выше алгоритма Шуфа), на практике часто бывает достаточным использовать кривые, предлагаемые различными стандартами или другими источниками. Например, в американском стандарте FIPS186-2 приводятся параметры эллиптических кривых для различных длин модулей. Вообще говоря, нет никаких ограничений на использование всеми одной хорошо выбранной кривой. Однако такая кривая, при широком ее использовании, становит­ся слишком притягательной для злоумышленников. Не исключено, что со временем они смогут найти какие-либо эффективные атаки именно на эту кривую, используя ее характерные особенности, не принятые ранее во внимание. Но все это лишь возможность, вероятность осуществления которой считается многими специалистами ничтожно малой.

Приведем пример реальной кривой, рекомендуемой в FIPS186-2 (CurveР-256). Обратным «слэшем» (\) обозначим продолжение числа на следующей строке. Предполагается, что кривая задана уравнением , число точек на кривой , точка является генератором подмножества мощности q точек, где q – простое число. Нижний индекс после записи числа означает основание системы счисления (десятичная или шестнадцатеричная):

;

;

(простое число);

;

;

.

Мы видим, что p и q вряд ли можно назвать случайно выбранными числами и вся «случайность» кривой определяется случайным выбором параметра b (это считается вполне обоснованным).

Первый вопрос, который возникает, когда мы видим кривую, подобную вышеприведенной: нет ли ошибки в записи параметров? Три проверки могут быть сделаны для выяснения этого вопроса.

1. Проверяем, является ли число p простым.

2. Проверяем, удовлетворяет ли точка уравнению кривой.

3. Удостоверяемся в том, что n – это действительно количество точек на кривой. Заметим, что такую проверку целесообразно делать и в том случае, когда мы сами вычисляем n, например, с помощью алгоритма Шуфа. В общем случае , где h – небольшое число, a q – простое. Прежде всего путем последовательного деления и проверки на простоту следует убедиться, что n соответствует заявленной форме. Затем выбираем случайно точку на кривой P (можно взять , где k – случайно выбранное число). Число n гарантированно является числом точек на кривой, если одновременно и . При невыполнении этого условия возможны два варианта. Если , то n – это не число точек. Если же (вероятность этого крайне мала), то нужно взять другую точку P.

Второй вопрос, который возникает, когда нам предъявляют «го­товую» кривую: действительно ли она была сгенерирована случайным образом? Этот вопрос вообще актуален для многих задач криптографии. Возможно, предложенная кривая обладает каким-либо редким свойством, позволяющим «взламывать» криптосистему, и человек, изготовивший эту кривую, может в дальнейшем получить доступ, скажем, к информации, зашифрованной при помощи этой кривой. Задача доказательства отсутствия заранее заданных специальных свойств кривой сводится к задаче подобного же доказательства для случайно выбираемых параметров. Например, для рекомендованной выше кривой мы должны доказать случайность выбора параметра b. Эту задачу можно решить следующим образом. Пусть – криптографически стойкая хеш-функция. Чтобы сгенерировать число b, вначале выбираем число s, а затем вычисляем и предъявляем оба числа: b и s.Если хеш-функция удовлетворяет всем требованиям стойкости, то b не может иметь никаких заранее заданных свойств, и мы можем спокойно им пользоваться. Число s является «сертификатом», доказывающим «чи­стоту» числа b. Приведенная выше эллиптическая кривая имеет по­добный сертификат, основанный на хеш-функции SHA-1, и стандарт оговаривает процедуру использования этого сертификата. Так что мы можем быть уверены в том, что кривая была сформирована действительно случайным образом.