Применение эллиптических кривых в криптографии. Жданов О.Н - 22 стр.

UptoLike

ВУЗ: 

СибГАУ | Красноярск

Составители: 

Рубрика: 

§ 3. Алгоритм цифровой подписи, основанный
на группе точек эллиптической кривой
Электронная цифровая подпись (ЭЦП).
Цифровая подпись для сообщения является числом, зависящим от самого сообще-
ния и от секретного, известного только подписывающему субъекту ключа. При этом под-
пись должна быть легко проверяемой без знания секретного ключа. При возникновении
спорной ситуации, связанной с отказом подписавшего от факта подписи им некоторого
сообщения либо с попыткой подделки подписи, третья
независимая сторона (арбитр)
должна иметь возможность разрешить спор.
Применение ЭЦП позволяет решить следующие задачи:
• осуществить аутентификацию источника сообщения;
• установить целостность сообщения;
• обеспечить невозможность отказа от факта подписи конкретного сообщения.
В настоящее время используются различные схемы ЭЦП. Их можно разделить на
три класса:
• схемы на основе симметричных систем шифрования;
• схемы на основе систем шифрования с открытыми ключами;
• схемы со специально разработанными алгоритмами вычисления и проверки
подписи.
Замечание.
Распространенной практикой является формирование ЭЦП не для само-
го сообщения, а для его хеш-образа при соответствующем выборе хеш-функции.
Цифровая подпись на эллиптических кривых.
В качестве международного стандарта принят американский алгоритм цифровой
подписи на эллиптических кривых (ECDSA). В этом стандарте используются эллиптиче-
ские кривые над полем характеристики 2. Однако криптографически стойких кривых над
полем такой характеристики сравнительно мало. Поэтому мы рассмотрим ЭЦП на эллип-
тических кривых, заданных над полем большей характеристики.
Замечание.
В России официально принят стандарт ЭЦП на эллиптических кривых
над полем большей характеристики – ГОСТ 34.10-2001 «Информационная технология.
Криптографическая защита информации. Процессы формирования и проверки электрон-
ной цифровой подписи» (текст стандарта приведен в Приложении 1).
Выбор кривой и точки на ней подразумевает решение ряда вспомогательных задач.
Прежде всего, это подсчет количества точек на
кривой. Если N – количество точек на
(
)
p
FE , то должны выполняться следующие условия:
()
⎪
⎩
⎪
⎨
⎧
=⋅⇒∈
++≤≤−+
)2(.
)1(,2121
OGNFEG
ppNpp
p
Таким образом, чтобы отсеять лишние числа из интервала
(
)
pppp 21,21 ++−+ , можно проверять условие (2) для разных точек G. Единственное
оставшееся число и будет искомым порядком кривой.
Замечание.
Существует несколько методов оптимизации нахождения порядка кри-
вой, например, метод больших-малых шагов, метод Шуфа. Познакомиться с ними можно
по книгам, приведенным в списке литературы.
Для получения криптографически стойкой системы ЭЦП должны выполняться сле-
дующие условия:
1)
Порядок точки G, используемой в системе ЭЦП, должен быть простым числом
n,
{
}
pn 4,2max
160
> .
2)
pN ≠
и
1+≠ pN
, где N – порядок кривой.

Страницы