Full Text

Введение. Основной особенностью описанного в [1, 2] нового стандарта электронной цифровой подписи (ЭЦП) является максимальная преемственность по отношению к действовавшему стандарту. Во-первых, предлагаемая схема представляет собой тот же вариант асимметричного алгоритма, адаптированный для использования вместо операций умножения и возведения в степень в конечном поле из p элементов аналогичных операций на эллиптической кривой над этим же полем. Во-вторых, она позволяет использовать действующий стандарт функции хеширования. В-третьих, длина подписи остается без изменений. Все это существенно облегчает модификацию многочисленных существующих программных и аппаратных реализаций, определяемых действовавшим ранее стандартом. Одним из основных параметров алгоритма ЭЦП является простое число p, представляющее собой модуль эллиптической кривой E и удовлетворяющее неравенству . Следующим параметром служит упомянутая эллиптическая кривая , задаваемая своим инвариантом или коэффициентами и . Эллиптической кривой , определенной над конечным простым полем , называется множество пар чисел , принадлежащих этому полю и удовлетворяющих тождеству , (1) где и Инвариантом эллиптической кривой называется величина , удовлетворяющая тождеству . Коэффициенты и кривой могут быть определены по известному инварианту следующим образом: и , где , причем и . Следующим параметром является целое число , представляющее собой порядок группы точек кривой . Пары , удовлетворяющие тождеству (1), называются точками кривой , а и - координатами точки. Точки кривой обозначим как . Две точки равны, если равны их соответствующие координаты. На множестве точек кривой введена операция сложения со следующими вариантами ее выполнения. Пусть координаты точек и удовлетворяют условию Тогда суммой этих точек называется точка , координаты которой определяются соотношениями: и , где . Если выполнены равенства и , то координаты точки определяются следующим образом: и , где . В случае, когда выполняется условие и , сумма точек и называется нулевой точкой, обозначаемой , а точка называется отрицанием точки . Относительно введенной операции сложения множество всех точек кривой вместе с нулевой точкой образует конечную коммутативную группу порядка , для которого выполнено неравенство: . При выборе должно быть выполнено условие: . Точка называется точкой кратности для некоторой точки , если выполняется равенство . Следующим параметром алгоритма является простое число , представляющее собой порядок циклической подгруппы точек кривой . При выборе должны быть выполнены следующие условия: , , для всех целых и . Еще одним параметром алгоритма является точка с координатами , удовлетворяющая равенству . В качестве одного из важнейших параметров алгоритма используется функция хеширования по ГОСТ Р34.11 [3] и её возможные модификации [4, 5, 6, 7]. Каждый пользователь этой схемы ЭЦП должен обладать ключом подписи, который представляет собой целое число , удовлетворяющее неравенству , и ключом проверки подписи, который представляет собой точку кривой с координатами , удовлетворяющую равенству . Описанные параметры используются при реализации алгоритма формирования ЭЦП, который представляется в виде следующей последовательности действий: 1. С помощь функции h осуществить хеширование сообщения Р и получить его хеш-значение . 2. Вычислить величину , двоичным представлением которой является хеш-значение и определить величину Если , то положить . 3. С помощью генератора псевдослучайных чисел выбрать число , удовлетворяющее условию . 4. Вычислить точку кривой , удовлетворяющую условию . Определить величину , где - -координата точки . Если , то следует выбрать новое значение . 5. Вычислить значение . Если s = 0, то следует выбрать новое значение . 6. Найти двоичные представления и , конкатенация которых и будет определять ЭЦП . При наличии выбранных параметров исходными данным для алгоритма формирования ЭЦП являются подписываемое сообщение и ключ подписи . Проверка или верификация ЭЦП осуществляется в следующем порядке: 1. Над принятой ЭЦП выполнить деконкатенацию, найти числа и , определить выполнение условий и . Если они не выполнены, то подпись отвергается. 2. С помощь функции осуществить хеширование принятого сообщения и получить его хеш-значение . 3. Вычислить величину , двоичным представлением которой является хеш-значение , и определить величину . 4. Вычислить величину . 5. Вычислить величины и . 6. Вычислить точку и определить величину . 7. Если , то подпись принимается, в противном случае она неверна. Исходными данным для алгоритма верификации являются принятое подписанное сообщение ЭЦП и ключ проверки . Таким образом, стандарт определяет только математические формулы для операций на эллиптической кривой и предлагает нижние границы для некоторых параметров, не устанавливая каких-либо конкретных алгоритмов выполнения этих операций. Выбор верхних границ параметров и конкретных вычислительных алгоритмов определяется в основном тремя взаимозависимыми факторами, к которым относятся требуемый уровень безопасности, допустимое время формирования и верификации ЭЦП и используемая аппаратная платформа. Так, например, нижней границей параметра p является . Из соображений безопасности в качестве минимальной верхней границы этого параметра целесообразно выбрать , если в указанном диапазоне разработанные вычислительные алгоритмы на применяемой аппаратной платформе выполняются за приемлемое время. 1. Постановка задачи. Анализ требований, предъявляемых стандартом к выбору параметров алгоритма формирования и верификации ЭЦП, позволяет сформулировать задачу выбора параметров в обобщенном виде как задачу выбора случайного (псевдослучайного) простого числа большой размерности из широкого диапазона. Простые числа встречаются довольно часто. Существует около 10151 простых чисел длиной от 1 до 512 бит включительно [8], а количество простых чисел, меньших 2512, приблизительно равно 2503 [8]. 2. Предлагаемое решение задачи. Один из способов формирования простых чисел базируется на следующей теореме [8, 9]. Пусть , где - нечетное простое число, - четное число и . Число является простым, если выполняются два условия: 1) ; 2) . Генерация простого числа с использованием этой теоремы осуществляется по несколько упрощенной в принятом стандарте схеме. Пусть требуется сформировать простое число длиной бит. С этой целью строится убывающая последовательность чисел , где , для которых , . Далее последовательно вырабатывается последовательность простых чисел , для всех . Генерация простого числа осуществляется с использованием следующей формулы: , где число удовлетворяет следующим условиям [12]: - четное; - такое, что длина числа в точности должна быть равна . Число получается с помощью генератора псевдослучайных чисел. Если полученное нечетно, то полагают . Число считается полученным, если одновременно выполнены следующие два условия: 1) где ; 2) . Если хотя бы одно из условий не выполняется, то значение числа увеличивается на 2, и вычисляется новое значение , которое снова проверяется по тем же условиям. Данный процесс продолжается до тех пор, пока не будет получено простое число , удовлетворяющее обоим условиям. При выборе случайного числа из заданного диапазона предполагается, что число выбирается равновероятным образом из заданного множества чисел, если не указано другого вероятностного распределения. Пусть - число элементов множества, из которого требуется выбрать случайный элемент. Для того чтобы обеспечить отсутствие смещения результирующего распределения вероятностей, следует воспользоваться методом проб и ошибок, суть которого применительно к данному случаю состоит в следующем. Необходимо выбрать , для которого , и определить , где - функция округления снизу, которая определяет ближайшее меньшее целое число. Далее следует выбрать из множества, число элементов в котором равно и получить окончательный результат как . Другими словами, этот метод предполагает, что для генерации равномерно распределенных случайных чисел, размер которых в битах не является степенью двух, необходимо отбросить от полученного результата несколько случайных бит, что при наличии современных генераторов псевдослучайных чисел не является проблемой. Далее требуется определить, является ли выбранное число действительно простым. Один из самых простых способов проверки числа на простоту состоит в последовательном делении числа на все нечетные числа, которые содержатся в интервале . Если в процессе деления получается целый результат, то число - составное. Если же при переборе всех нечетных чисел из интервала разделить число на эти числа нацело нельзя, то число - простое. Данный метод называется пробным делением [8]. Этот метод трудоемок по числу арифметических операций, и он используется в основном для проверки небольших простых чисел. Другой метод, называемый решетом Эратосфена, также достаточно эффективен, но требует для реализации большого объема памяти ЭВМ, однако для составления таблиц простых чисел он является наилучшим [8]. Более того, разрабатываются специальные процессоры, на которых операции «просеивания» выполняются очень эффективно. Малая теорема Ферма [10,11] утверждает, что если простое число, то выполняется условие: при всех имеет место сравнение . На основании этой теоремы построен вероятностный алгоритм проверки на простоту числа . Если для некоторого целого m из интервала [2, p] соотношение не выполняется, то число - составное. Если же теорема выполняется, то вывод о том, что число простое, сделать нельзя, так как теорема дает лишь необходимое условие. Поэтому, если для некоторого m имеет место соотношение , то считают, что число является псевдопростым по основанию u. Существует бесконечно много пар чисел u и , где - составное и псевдопростое. Вообще, для любого m > 1 существуют бесконечно много псевдопростых чисел по основанию m. Итак, справедливы следующие два утверждения: - если пара (2, ) удовлетворяет сравнению , то и пара чисел (2, 2p - 1) также ему удовлетворяет; - для любого простого числа и любого u > 2 такого, что (u2 - 1, ) = 1, число является псевдопростым по основанию u. Составные числа , для которых при всех основаниях выполняется сравнение , называются числами Кармайкла [12]. Здесь уместно заметить [12], что числа Кармайкла достаточно редки. Так, существуют всего 2163 чисел Кармайкла, которые не превосходят 25 000 000 000, и всего 16 чисел, которые не превосходят числа 100 000. Вероятностным тестом простоты, свободным от этого недостатка является тест Соловея-Штрассена [13]. Тест Соловея-Штрассена состоит из отдельных раундов. В каждом раунде выполняются следующие действия: 1. Случайным образом выбирается число и вычисляется . 2. Если , то выносится решение о том, что p составное. В противном случае проверяется соотношение: , (2) где - символ Якоби. Если соотношение (2) не выполнено, то p - составное. Если выполнено, то является свидетелем простоты числа p. Если после раундов найдено свидетелей простоты, то тест делает заключение о том, что p вероятно является простым числом. В каждом раунде вероятность отсеять составное число больше 1/2, поэтому через раундов тест Соловея-Штрассена определяет простое число с вероятностью ошибки, меньшей . В этом отношении он проигрывает тесту Миллера-Рабина, который за раундов имеет ошибку, меньшую . Для определения простоты числа может быть использован тест Рабина-Миллера [14, 15, 16], в основе которого лежит малая теорема Ферма, утверждающая, что для любого простого числа p и для всех справедливо соотношение . Число в этом случае называется базисом. Можно представить , где - нечетное число. Если требуется вычислить , можно найти и возвести полученный результат в квадрат раз, т.е. получить . Если , то многократное возведение в квадрат не изменит результата и можно записать . Если , то необходимо вычислять и анализировать последовательность (3) каждый элемент которой берется по модулю . Если p является простым числом, то согласно малой теореме Ферма последним элементом последовательности (3) должна быть единица. Если хотя бы при одном случайно выбранном базисе тест дает отрицательный результат, то принимается решение о том, что p является составным числом. Это свидетельствует о необходимости возврата к алгоритму проб и ошибок для выбора нового значения j. Если j успешно проходит тест при данном b, то следует повторить его, выбрав другой базис b, чем обеспечивается снижение вероятности получения неверного результата тестирования до приемлемой величины. Наиболее ресурсоемкой операцией в тесте Рабина-Миллера является операция . Для ее реализации предлагается так называемый двоичный алгоритм, коротко формулируемый в виде следующей рекурсии. Если , то . Если и является четным числом, то находится величина , и окончательный результат будет выглядеть . Если и является нечетным числом, то находится величина , и окончательный результат будет выглядеть так: . Если проанализировать описанные операции, то можно сделать вывод о том, что необходимый показатель степени формируется бит за битом, начиная от более значимой части двоичного представления показателя степени к наименее значимой его части. Если обозначить - число бит значения j, т.е. , то можно сказать, что данный алгоритм потребует не более операций умножения по модулю j. Такой объем работы доступен вычислительным возможностям большинства стандартных персональных компьютеров. Необходимость неоднократного тестирования с разными базисами объясняется существованием чисел Кармайкла, которые, будучи составными, успешно проходят тест Рабина-Миллера. Эксперты [17-21] рекомендуют ограничиться исследованием 5-10 базисов. Выводы. Таким образом, если учесть, что числа Кармайкла в области больших чисел встречаются крайне редко, а также то обстоятельство, что тест Соловея-Штрассена имеет большую вычислительную сложность, то более предпочтительным для поиска больших простых чисел представляется использование теста Миллера-Рабина. С учетом этого для практических приложений можно предложить следующую последовательность формирования параметра p: 1) сгенерировать псевдослучайное двоичное число p требуемой разрядности; 2) установить старший и младший биты полученного числа равными 1. Старший бит в этом случае гарантирует требуемую длину формируемого простого числа, а младший - его нечетность; 3) убедиться, что число p не делится на малые простые числа 3, 5, 7, 11 и т.д. Наиболее надежна проверка делимости на все простые числа, меньше 2000; 4) выполнить тест Рабина-Миллера для некоторого псевдослучайного числа . Если p проходит тест, то сгенерировать другое псевдослучайное число и повторить тест. Для практических приложений достаточно повторить тест Рабина-Миллера пять раз; 5) если p не проходит один из тестов, надо сгенерировать другое число p и повторить описанную последовательность действий. Другое число p, если оно оказалось непростым, можно получить, не генерируя новое, а последовательно перебирая все целые, начиная от p + 1, p + 2, и т.д., пока не найдется простое число. С помощью аналогичной процедуры предлагается осуществлять поиск и других параметров (b, m, q, y) стандартного алгоритма формирования ЭЦП.

About the authors

V. G Lanskikh

Vyatka state technical university

Yu. V Lanskikh

Perm state national research university

References

Statistics

Views

Abstract - 20

PDF (Russian) - 12

Refbacks

• There are currently no refbacks.