Устройство для генерации псевдослучайной последовательности двоичных чисел с использованием эллиптических кривых

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

 

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

Известно устройство для генерации случайных чисел [Tezuka S. Pseudorandom number generator. Патент US №5046036 от 3.09.1991 г., кл. G 06 F 007/38], в котором для вычисления значений псевдослучайных наборов чисел используют совокупность преобразования синхропосылки с помощью генератора так называемых M-последовательностей и трех видов преобразования полученных последовательностей:

умножения вектора Р со значениями, полученными из генератора М-последовательностей на изначально заданную матрицу G, сложения по модулю 2 двух выходных битов генератора М-последовательностей; битовых подстановок S_i результата умножения вектора Р на матрицу G.

Однако устройство имеет недостатки, заключающиеся в невысокой криптостойкости операций генератора (из-за использования генераторов M-последовательностей, которые не обладают достаточной криптостойкостью [Иванов М.А., Чугунков И.В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей. М.: Кудиц-образ, 2003 - 240 с.]), а также необходимости наличия действительно случайного значения синхропосылки, с помощью которой производится вычисление M-последовательностей [Аграновский А.В., Хади Р.А. Практическая криптография: алгоритмы и их программирование. М.: Солон-Пресс, 2002 - 256 с.], что существенно для использования данного устройства на практике.

Известно также другое устройство для генерации псевдослучайной последовательности бит [Mark, J.G., Tazartes D.A., Tazartes D.I., Wiener D.P. Fiber-optic gyro utilizing pseudorandom-bit-sequence light modulation. Патент US №6130755 от 10.10.2000 г., кл. G 01 C 019/72], работа которого основана на выборе 0 или 1 в качестве следующего бита псевдослучайной последовательности в зависимости от результатов проверки предыдущих битов последовательности на соответствие изначально заданным критериям. Принцип работы устройства основан на двух типах критериев - если удовлетворяется одна группа критериев (так называемые "0-критерии"), выбирается нулевое значение следующего выходного бита последовательности, если же удовлетворяется вторая группа критериев (так называемые "1-критерии"), то в качестве выходного бита выбирается единица. Сущность критериев заключается в измерении свойств цепочки предыдущих выходных битов достаточной длины. В качестве следующего бита вычисляемой псевдослучайной последовательности выбирается очередной бит, полученный другим более произвольным методом (например, сложением последних j (j=1, 2, 3...) бит по модулю 2).

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

Наиболее близким по технической сущности к предлагаемому является устройство для генерации псевдослучайных последовательностей [DeBellis R.S., Smith R.M., Yeh P.C. Pseudorandom number generator with backup and restoration capability. Патент US №6104810 от 15.08.2000 г., кл. G 01 C 019/72], принятое за прототип. Принцип действия устройства основан на том, что для вычисления значений псевдослучайного набора двоичных чисел используется вычислительное преобразование входных неслучайных данных для получения выходной псевдослучайной двоичной последовательности. В прототипе значения псевдослучайной последовательности вычисляют при помощи применения заведомо криптостойкой функции к значению, зависящему от текущего времени, и секретному параметру, затем полученные биты подают на вход хэш-функции MDC-4 [Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. СПб: Триумф, 2002 г. - 816 с.], а ее результат сохраняется как значение псевдослучайной последовательности. Значение секретного параметра регулярно обновляется при помощи вычисления хэш-функции от совокупности текущего значения секретного параметра и текущего значения времени. Алгоритм работы устройства также предусматривает сохранение резервных значений секретного параметра, используемых в случае перезапуска системы. Таким образом уменьшается вероятность повторного вычисления уже использованной последовательности псевдослучайных чисел после перезапуска устройства.

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

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

Данный технический результат достигается благодаря тому, что устройство для генерации псевдослучайной последовательности двоичных чисел с использованием эллиптических кривых состоит из блока 1 - блока памяти для хранения параметров используемой эллиптической кривой и текущего значения секретного параметра S_y (блок 1 имеет один вход для обновления секретного параметра S_y и четыре выхода: выход 1 - для считывания параметра S_y, выход 2 - для считывания параметров эллиптической кривой, выходы 3 и 4 - для считывания координат примитивного элемента В группы точек эллиптической кривой), блока 2 (блока таймера, который имеет один выход, с которого считывает текущее значение таймера в виде последовательности бит), операционных блоков 3.1 и 3.2, вычисляющих значения хэш-функции MD5 (блоки имеют по одному входу, на которые подается последовательность бит, и одному выходу, с которого считывается значение хэш-функции MD5 от поданной на блок входной информации в виде последовательности бит), операционного блока 4, преобразующего последовательность бит в пару последовательностей бит, представляющих собой координаты точки эллиптической кривой (блок имеет два входа: вход 1, на который подается последовательность бит, и вход 2, на который подается значение параметров эллиптической кривой в виде последовательности бит, а также два выхода, с которых считываются координаты получаемой точки эллпитической кривой в виде последовательностей бит), вычислительного блока 5, производящего перемножение двух точек эллиптической кривой, координаты которых поступают на вход в виде последовательностей бит (блок 5 имеет входы 1, 2, 3 и 4, на которые подаются координаты операндов умножения в виде последовательностей бит - по одному входу на координату каждого операнда, а также вход 5, на который подаются параметры эллиптической кривой в виде последовательности бит, и выход 1, из которого считывается последовательность бит, представляющая собой y-координату результата перемножения), операционных блоков 6.1 и 6.2, производящих конкатенацию поступающих на вход блоков двух последовательностей бит (каждый из блоков имеет по два входа 1 и 2 для входных последовательностей бит и по одному выходу, с которого считывается результат конкатенации входных последовательностей), блока памяти 7, накапливающего выходную псевдослучайную последовательность бит (блок имеет один вход для принятия накапливаемой двоичной информации и один выход для ее считывания), при этом выход 1 блока 1 соединен с входом 2 блока 6.1; выход 2 блока 1 соединен с входом 2 блока 4 и входом 5 блока 5; выход 3 блока 1 соединен с входом 3 блока 5; выход 4 блока 1 соединен с входом 4 блока 5; выход 1 блока 2 соединен с входом 1 блока 6.1 и входом 2 блока 6.2; выход 1 блока 3.1 соединен с входом 1 блока 4; выход 1 блока 3.2 соединен с входом 1 блока 7; выход 1 блока 4 соединен с входом 1 блока 5; выход 2 блока 4 соединен с входом 2 блока 5; выход 1 блока 5 соединен с входом 1 блока 6.2; выход 1 блока 6.1 соединен с входом 1 блока 3.1; выход 1 блока 6.2 соединен с входом 1 блока 3.2.

Принцип действия устройства основан на вычислениях в мультипликативной группе точек эллиптической кривой вида Е(Х)={(х,y)|y²=х³+а*x+b} над полем GF(p,n). Устройство работает следующим образом. В блок 1 загружаются данные инициализации (параметры р и n, а и b, примитивный элемент В группы точек кривой Е, секретный параметр S_y). Дальнейшая работа проходит следующим образом. Блок 6.1, входы которого соединены с выходом блока 2 и выходом 1 блока 1, производит конкатенацию битовой последовательности, полученной на выходе таймера 2 и битовой последовательности, представляющей текущее значение S_y. Блок 3.1, вход 1 которого соединен с выходом 1 блока 6.1, производит вычисление значения хэш-функции от полученного при работе блока 6.1 последовательности бит. Блок 4, вход 1 которого соединен с выходом 1 блока 3.1, а вход 2 - с выходом 2 блока 1, производит преобразование выходных данных блока 3.1 в координаты точки эллиптической кривой Е над полем GF(p,n), считывая информацию о Е, р, n из блока 1. Блок 5 (его входы 1 и 2 соединены с выходами 1 и 2 блока 4, входы 3, 4, 5 - с выходами 3, 4, 2 блока 1 соответственно) вычисляет произведение точки эллиптической кривой Е, полученной на предыдущем шаге и примитивного элемента группы точек Е (информация об а, b, р, n и координатах точки В считывается из блока 1 через его выходы 2, 3, 4), и выдает на выходе значение y-координаты полученной точки. Результат записывается в соответствующие ячейки блока 1 (его вход 1 соединен с выходом). Блок 6.2 производит конкатенацию значения, полученного в блоке 5, и выходного значения блока 2. Блок 3.2 вычисляет значение хэш-функции от результата работы блока 6.2. Полученное значение передается в накопитель 7.

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

Для описания работы устройства введем следующие обозначения:

- параметры p и n, позволяющие описать поле Галуа GF(p,n);

- параметры а и b эллиптической кривой Е, представимой уравнением

E(X)={(x,y)|y²=x³+a*x+b}, где Х - точка кривой Е, а и b - переменные, х и y являются координатами X;

- примитивный элемент В мультипликативной группы точек кривой Е;

- секретный параметр S_y, являющийся y-координатой точки эллиптической кривой Е;

- целочисленная переменная Т;

- выходная двоичная последовательность Q переменной длины.

Для генерации псевдослучайной последовательности двоичных чисел используется вычислительное преобразование неслучайных данных для получения выходной псевдослучайной двоичной последовательности. В качестве вычислительного преобразования используют алгоритм вычисления с эллиптической кривой вида Е(Х)={(x,y)|y²=x³+a*x+b}, в котором пользователем задается значение секретного параметра S_y равным y-координате точки В в случае первого преобразования данных либо происходит загрузка сохраненного ранее значения S_y, производится очистка двоичной последовательности Q для хранения выходной последовательности значений; целочисленной переменной Т присваивается значение текущего времени в виде количества секунд, прошедших с 1970 года до текущего момента времени, секретному параметру S_y присваиваются значения y-координаты точки В*e(h(S_y|T)), где е(х) - функция, преобразующая число в точку эллиптической кривой Е, функция h(х) представляет собой хэш-функцию MD5, S_y - текущее значение секретного параметра - сохраняется для последующего использования, к двоичной последовательности Q дописывают значение h(T|S_y), при необходимости действия по вычислению нового значения параметра S_y и дополнению последовательности Q повторяются, выходной последовательностью считается двоичная последовательность Q.

Для реализации работы используют входные данные о поле Галуа GF(p,n), параметрах эллиптической кривой Е, имеющей над полем GF(p,n) не менее 30*2¹²⁸ точек, и примитивном элементе В мультипликативной группы точек эллиптической кривой Е.

Функция h(x) согласно [Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. СПб: Триумф, 2002 г. - 816 с.] принимает на вход двоичную последовательность произвольной длины и вычисляет хэш-значение, представленное в виде двоичной последовательности фиксированной длины, равной 128 битам.

Функция е(x) преобразует двоичную последовательность x длиной 128 бит в точку на эллиптической кривой Е. Значение е(x) вычисляется по следующему алгоритму. Выбирается целое число 1≤j≤30. Между числами вида 30*x+j из интервала [0, (2¹²⁸-1)*30] и частью множества элементов поля GF(p,n) устанавливают взаимнооднозначное соответствие (известный из уровня техники метод установления такого соответствия состоит в трактовке цифр р-ичной записи числа Х в качестве коэффициентов многочлена над соответствующим полем - см., например [Коблиц И. Курс теории чисел и криптографии. М.: Научное издательство ТВП, 2001 - 254 с.]). Затем вычисляют значение , из полученного V извлекают квадратный корень; если корень удалось извлечь, принимают за результат точку с координатами (, sqrt(V)), иначе присваивают переменной j другое целое значение из интервала [1, 30] и повторяют вычисления до тех пор, пока число V не станет полным квадратом. Вероятность того, что применение этого алгоритма не даст результата, составляет приблизительно 2^-30.

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

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