47.        Проблемы и перспективы развития криптографических методов защиты. Криптосистемы на основе эллиптических кривых. Алгоритм электронной подписи на основе  эллиптических кривых ECDSA

Проблемы и перспективы развития криптографических систем:

Шифрование больших сообщений и потоков данных:

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

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

Наиболее распространенным является потоковое шифрование данных. Этот тип шифрования предусматривает зашифровку информации в процессе е╠ передачи. Наиболее простым способом является побитовое сложение входящей последовательности (сообщения) с некоторым бесконечным или периодическим ключом, получаемым, например, с помощью генератора ПСЧ. Примером стандарта потокового шифрования является RC4, разработанный Ривестом. Однако, технические подробности этого алгоритма держатся в секрете. Другим, иногда более эффективным методом потокового шифрования, является шифрование блоками, т.е. накапливается фиксированный объ╠м информации, а затем, преобразованный некоторым криптографическим методом, он передается в канал связи.

Использование блуждающих ключей:

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

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

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

Шифрование, кодирование и сжатие информации:

Эта тема крайне интересна в наше время, когда информации настолько много, что существенную роль играет и ее объем. Отличными вариантами является комбинирование таких аспектов этого вопроса, как кодирование и шифрование, или комбинирование алгоритмов шифрования и сжатия информации. Это обеспечивает снижение объема полученной после кодирования информации, что значительно облегчает ее хранение. Наиболее популярными алгоритмами сжатия являются RLE, коды Хаффмана, алгоритм Лемпеля-Зива. Для сжатия графической и видеоинформации используются алгоритмы JPEG и MPEG. Главное достоинство алгоритмов сжатия с точки зрения криптографии состоит в том, что они изменяют статистику входного текста в сторону ее выравнивания. Так, в обычном тексте, сжатом с помощью эффективного алгоритма, все символы имеют одинаковые частотные характеристики, и даже использование простых систем шифрования сделают текст недоступным для криптоанализа. Разработка и реализация таких универсальных методов - перспектива современных информационных систем.

Реализация криптографических методов:

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

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

Большинство зарубежных серийных средств шифрования основано на американском стандарте DES. Отечественные же разработки, такие как, например, устройство КРИПТОН, использует отечественный стандарт шифрования.

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

В последнее время стали появляться комбинированные средства шифрования, так называемые программно-аппаратные средства. В этом случае в компьютере используется своеобразный "криптографический сопроцессор" - вычислительное устройство, ориентированное на выполнение криптографических операций (сложение по модулю, сдвиг и т.д.). Меняя программное обеспечения для такого устройства, можно выбирать тот или иной метод шифрования. Такой метод объединяет в себе достоинства программных и аппаратных методов.

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

Криптосистемы на основе эллиптических кривых:

Эллиптические кривые - математический объект, который может быть определен над любым полем. В криптографии обычно используются конечные поля. Эллиптическая кривая есть множество точек (x,y), удовлетворяющее уравнению y2 = x3 + ax + b, а также бесконечно удаленная точка. Для точек на кривой довольно легко вводится операция сложения, которая играет ту же роль, что и операция умножения в криптосистемах RSA и Эль-Гамаля. На практике, в криптосистемах такого рода используется уравнение y2 = x3 + ax + b mod p, где р - простое.

Проблема дискретного логарифма на эллиптической кривой состоит в следующем: дана точка G на эллиптической кривой порядка r (количество точек на кривой) и другая точка Y на этой же кривой. Нужно найти единственную точку x такую, что Y = xG, то есть Y есть х-я степень G.

Эллиптические кривые и новый стандарт на электронную подпись

 «Эллиптической кривой» называют множество пар точек (X,Y), удовлетворяющих уравнению:

y2 = ax3 + bx + c

Можно наложить ограничения на множество значений переменных х, y, и коэффициентов a, b, c. Ограничивая область определения уравнения значимым для приложений числовым множеством (полем) мы получим эллиптическую кривую, заданную над рассматриваемым полем. На рис. 2 изображен общий вид эллиптической кривой, определенной на множестве действительных чисел.

В приложении к криптографии (и в новом стандарте на цифровую подпись) эллиптическая кривая над конечным простым полем GF(p) определяется как множество пар (x,y), таких что x,y ≡ GF(p), удовлетворяющих уравнению:

y2 = x3 +ax +b (mod p), a, b ≡ GF(p)

Пары (x,y) будем называть «точкой». Точки эллиптической кривой можно «складывать». «Сумма» двух точек, в свою очередь, тоже «лежит» на эллиптической кривой.

Кроме точек, лежащих на эллиптической кривой, рассматривается также «нулевая точка». Считается, что сумма двух точек A с координатами (XA, YA) и B с координатами (XB,YB) равна O, если XA = XB, YA = –YB (mod p). Нулевая точка не лежит на эллиптической кривой, но, тем не менее, участвует в вычислениях; ее можно рассматривать как бесконечно удаленную от кривой.

Множество точек эллиптической кривой вместе с нулевой точкой и с введенной операцией сложения будем называть «группой». Для каждой эллиптической кривой число точек в группе конечно, но достаточно велико. Оценка порядка (числа элементов) группы точек эллиптической кривой m такова:

где р — порядок поля, над которым определена кривая. Если в схеме Эль-Гамаля рекомендуется использовать число р порядка 2512, то в случае эллиптической кривой достаточно взять p > 2255.

Важную роль в алгоритмах подписи с использованием эллиптических кривых играют «кратные» точки. Точка Q называется точкой кратности k, если для некоторой точки P k раз выполнено равенство:

P = Q + Q + Q + … + Q = kQ

Если для некоторой точки P существует такое число k, что kP = 0, это число называют порядком точки P.

Кратные точки эллиптической кривой являются аналогом степеней чисел в простом поле. Задача вычисления кратности точки эквивалентна задаче вычисления дискретного логарифма. Собственно, на сложности вычисления «кратности» точки эллиптической кривой и основана надежность цифровой подписи. Хотя эквивалентность задачи дискретного логарифмирования и задачи вычисления кратности и доказана, вторая имеет большую сложность. Секретным ключом, как и раньше, положим некоторое случайное число x. Открытым ключом будем считать координаты точки на эллиптической кривой P, определяемую как P = xQ, где Q — специальным образом выбранная точка эллиптической кривой («базовая точка»). Координаты точки Q вместе с коэффициентами уравнения, задающего кривую, являются параметрами схемы подписи и должны быть известны всем участникам обмена сообщениями.

Выбор точки Q зависит от используемых алгоритмов и весьма непрост. Так, стандарт ГОСТ 34.10-2001 определяет, что точка Q должна иметь порядок q, где q — простое число с «хорошими алгебраическими свойствами». Число q довольно велико (2254 < q < 2256). При построении конкретного алгоритма, реализующего вычисление цифровой подписи, американский стандарт предполагает использование алгоритма DSA. Новый российский стандарт использует модифицированную версию старого ГОСТ Р 34.10-94.

15.1. Цифровая подпись на эллиптических кривых

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

15.1.1. Начальные параметры алгоритма цифровой подписи

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

Эллиптическая кривая задается уравнением

у² = х³ + ах + b.

Таким образом, задание кривой состоит в выборе двух элементов а, b из поля, которые определяют это уравнение. Различные пары параметров (а,Ь) могут определять изоморфные эллиптические кривые. При выборе эллиптиче­ской кривой можно сначала задать j-инвариант этой кривой, а затем по нему построить коэффициенты а и b.

Точка G на эллиптической кривой определяется парой элементовиз

 . Эта точка выбирается случайно. Один из способов выбора — зафиксировать случайное χ и затем найти у как корень второй степени из х³ + ах + Ъ в поле, если он существует. Существование корня проверяется

путем вычисления символа Лежандра  

Для получения криптографически стойкой системы цифровой подписи должны выполняться следующие требования:

1)  порядок точки G должен быть равен простому числу ;

2).                                кривая не должна быть суперсингулярной;

3)                                 всех , где С настолько велико, что вычис­лить дискретный логарифм в   за приемлемое время невозможно (обычно берут С = 20);

4) т.е. кривая не должна быть аномальной.

Заметим, что условие 3 подразумевает условие 2.

Выбор эллиптической кривой подразумевает решение ряда трудоемких вспо­могательных задач. Прежде всего — это подсчет количества точек на эллипти­ческой кривой (об этом речь пойдет в конце главы). После того как порядок N кривой определен, требуется найти большой простой делитель η порядка кри­вой. Такой делитель может, в принципе, не существовать, и тогда потребуется повторять процедуру выбора кривой до тех пор, пока не выполнятся все требуе­мые условия. Поиск числа η может потребовать как разложения на множители числа Ν, так и доказательства простоты полученного множителя п.

Точку G можно выбрать следующим образом. Найдем случайную точку  и вычислим [см. формулу (15.2.1)]. Будем повторять эту

операцию до тех пор, пока точка G не станет отличной от точки О.

Ключ подписи (секретный ключ) — это случайное число d в интервале 0 < d < п.

Ключ проверки подписи (открытый ключ) — это точка на эллиптической кривой Q = [d] G.

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

15.1.2. Генерация и проверка цифровой подписи

Алгоритм 15.1.1 (генерация подписи). Входные данные: сообщение т, ис­ходные параметры и ключ подписи. Выходные данные: подпись (r,s).

1)  Выбрать случайное число к в интервале

2)  Вычислить

3)  Вычислить

4)  Если r = 0, то вернуться к шагу 1.

5)  Вычислить

6)  Вычислить

7)  Вычислить

8)  Если s = 0, то вернуться к шагу 1.

9)  Вывести пару (r,s) — подпись к т.

Алгоритм 15.1.2 (проверка подписи). Входные данные: сообщение т, ис­ходные параметры, ключ проверки подписи и подпись к т. Выходные данные: утверждение, что подпись действительная или фальшивая.

1)  Если условиянарушаются, то вывести «подпись фальши­вая» и завершить работу алгоритма.

2)  Вычислить

3)  Вычислить

4)  Вычислить

5)  Вычислить

6)  Вычислить

7)  Если то вывести «подпись действительная», иначе — «под­пись фальшивая», и завершить работу алгоритма.

Корректность алгоритма генерации подписи. Докажем, что любая подпись, сгенерированная по алгоритму 15.1.1, будет «действительной» согласно алго­ритму проверки подписи 15.1.2.

Прежде всего заметим, что параметры r u s, получаемые в алгоритме 15.1.1, не превосходят n -1, как остатки при делении на η целых чисел. С другой сто­роны, выполняется проверка того, что r,на шагах 4 и 8 алгоритма 15.1.1. Следовательно, условия шага 1 алгоритма проверки подписи будут выполнены всякий раз, когда r, s получены по алгоритму генерации подписи.

Далее, согласно шагам 5 и 7 алгоритма генерации подписи, имеем  Посколькуmod n (шаг 3 алгоритма проверки подписи), то к =we + wrd(mod η). Так как точка G имеет порядок п, то

[к] G = [we + wrd] G = [we] G + [wr][d] G =

 = [we] G + [wr] Q = [U_i ] G + [u₂] Q = X.

Таким образом, точка X, получаемая на шаге 6 алгоритма проверки подписи, совпадет с точкой [k]G, сгенерированной при получении подписи по алго­ритму генерации. Первая координата X будет равна х₁, и ее остаток mod n бу­дет равен r (согласно шагу 3 алгоритма генерации подписи). Корректность доказана.