Патент на изобретение №2369972

(54) СПОСОБ ФОРМИРОВАНИЯ И ПРОВЕРКИ ПОДЛИННОСТИ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ, ЗАВЕРЯЮЩЕЙ ЭЛЕКТРОННЫЙ ДОКУМЕНТ

(57) Реферат:

Изобретение относится к области криптографических устройств. Технический результат заключается в уменьшении размера коллективной электронной цифровой подписи (ЭЦП) без снижения ее уровня стойкости. Сущность изобретения заключается в том, что способ генерации и проверки ЭЦП включает следующую последовательность действий: генерируют совокупность из n2 секретных ключей в виде многоразрядных двоичных чисел (МДЧ) x₁, x₂, , x_n, по секретным ключам формируют n открытых ключей Y₁, Y₂, , Y_n в виде матриц МДЧ размерности w×w, где 2w32, принимают, по крайней мере, один электронный документ (ЭД), представленный МДЧ Н, в зависимости от принятого электронного документа и от значения, по крайней мере, двух секретных ключей формируют ЭЦП Q в виде двух МДЧ, генерируют коллективный открытый ключ в зависимости от m открытых ключей ,

где ось ₁, ₂, , _m – натуральные числа, 2mn, _jn и j=i, 2, , m, в зависимости от ЭЦП и ЭД формируют первое А и второе В проверочные МДЧ, причем, по крайней мере, одно из проверочных МДЧ формируют в зависимости от коллективного открытого ключа. Сравнивают МДЧ А и В. При совпадении их параметров делают вывод о подлинности электронной цифровой подписи. 4 з.п. ф-лы.

Текст описания приведен в факсимильном виде.

Формула изобретения

1. Способ генерации и проверки подлинности электронной цифровой подписи, заверяющей электронный документ, заключающийся в том, что генерируют совокупность из n2 секретных ключей в виде многоразрядных двоичных чисел x₁, x₂, , x_n, по секретным ключам формируют n открытых ключей Y₁, Y₂, , Y_n, соответственно, принимают, по крайней мере, один электронный документ, представленный многоразрядным двоичным числом Н, в зависимости от принятого электронного документа и от значения, по крайней мере, одного секретного ключа формируют электронную цифровую подпись Q в виде двух многоразрядных двоичных чисел, в зависимости от электронного документа и электронной цифровой подписи формируют первое А и второе В проверочные многоразрядные двоичные числа, сравнивают их и при совпадении их параметров делают вывод о подлинности электронной цифровой подписи, отличающийся тем, что открытые ключи Y₁, Y₂, , Y_n формируют в виде матриц многоразрядных двоичных чисел размерности w×w, где 2w32, дополнительно генерируют коллективный открытый ключ в зависимости от m открытых ключей , где ₁, ₂, , _m – натуральные числа, 2mn, a_jn и j=1, 2, , m, причем, по крайней мере, одно из проверочных многоразрядных двоичных чисел формируют в зависимости от коллективного открытого ключа.

2. Способ по п.1, отличающийся тем, что открытые ключи Y₁, Y₂, , Y_n генерируют в виде матриц многоразрядных двоичных чисел размерности 2×2, определитель каждой из которых по модулю многоразрядного двоичного числа р равен 1, для чего генерируют матрицу многоразрядных двоичных чисел G, имеющую порядок q, причем открытые ключи Y₁, Y₂, , Y_n формируют по формуле , где i=1, 2, , n, принимают m электронных документов, представленных многоразрядными двоичными числами H₁, Н₂, , H_m, а электронную цифровую подпись формируют в виде пары многоразрядных двоичных чисел е и s, для чего генерируют m случайных многоразрядных двоичных чисел , генерируют m матриц многоразрядных двоичных чисел по формуле , генерируют матрицу многоразрядных двоичных чисел R по формуле , после чего формируют первое многоразрядное двоичное число е электронной цифровой подписи по формуле е=а mod , где а=(а₁₁||а₁₂) – многоразрядное двоичное число, равное конкатенации многоразрядных двоичных чисел первой строки матрицы многоразрядных двоичных чисел R, и – вспомогательное простое многоразрядное двоичное число, затем генерируют m многоразрядных двоичных чисел по формуле , после чего генерируют второе многоразрядное двоичное число s электронной цифровой подписи по формуле причем коллективный открытый ключ генерируют в виде матрицы многоразрядных двоичных чисел Y, вычисляемой по формуле , а первое и второе проверочные многоразрядные двоичные числа А и В формируют по формулам A=r’mod и В=е, где r’=(r’₁₁||r’₁₂) – многоразрядное двоичное число, равное конкатенации многоразрядных двоичных чисел первой строки матрицы многоразрядных двоичных чисел R’, вычисленной по формуле R’=Y^eG^s(mod р), а второе проверочное многоразрядное двоичное число В формируют по формуле В=е.

3. Способ по п.1, отличающийся тем, что открытые ключи Y₁, Y₂, , Y_n генерируют в виде матриц многоразрядных двоичных чисел размерности 2×2, определитель каждой из которых по модулю многоразрядного двоичного числа р равен 1, для чего генерируют матрицу многоразрядных двоичных чисел G, имеющую порядок q, причем открытые ключи Y₁, Y₂, , Y_n формируют по формуле , где i=1, 2, , n, принимают электронный документ, представленный многоразрядным двоичным числом Н, а электронную цифровую подпись формируют в виде пары многоразрядных двоичных чисел е и s, для чего генерируют m случайных многоразрядных двоичных чисел , генерируют m матриц многоразрядных двоичных чисел по формуле , генерируют матрицу многоразрядных двоичных чисел R по формуле , после чего формируют первое многоразрядное двоичное число е электронной цифровой подписи по формуле е=аН mod , где a=(a₁₁||a₁₂) – многоразрядное двоичное число, равное конкатенации многоразрядных двоичных чисел первой строки матрицы многоразрядных двоичных чисел R, – и – вспомогательное простое многоразрядное двоичное число, затем генерируют m многоразрядных двоичных чисел по формуле после чего генерируют второе многоразрядное двоичное число s электронной цифровой подписи по формуле причем коллективный открытый ключ формируют в виде матрицы многоразрядных двоичных чисел Y, вычисляемой по формуле , а первое и второе проверочные многоразрядные двоичные числа А и В формируют по формулам А=r’H mod и В=е, где r’=(r’₁₁||r’₁₂) – многоразрядное двоичное число, равное конкатенации многоразрядных двоичных чисел первой строки матрицы многоразрядных двоичных чисел R’, вычисленной по формуле R’=Y^eG^s(mod р).

4. Способ по п.1, отличающийся тем, что открытые ключи Y₁, Y₂, , Y_n генерируют в виде матриц многоразрядных двоичных чисел размерности 3×3, определитель каждой из которых по модулю многоразрядного двоичного числа р равен 1, для чего генерируют матрицу многоразрядных двоичных чисел G, имеющую порядок q, причем открытые ключи Y₁, Y₂, , Y_n формируют по формуле , где i=1, 2, , n, принимают электронный документ, представленный многоразрядным двоичным числом Н, а электронную цифровую подпись формируют в виде пары многоразрядных двоичных чисел е и s, для чего генерируют m случайных многоразрядных двоичных чисел, генерируют m матриц многоразрядных двоичных чисел по формуле генерируют матрицу многоразрядных двоичных чисел R по формуле после чего формируют первое многоразрядное двоичное число е электронной цифровой подписи по формуле е=аH mod , где а=(a₁₁||а₁₂||а₁₃) – многоразрядное двоичное число, равное конкатенации многоразрядных двоичных чисел первой строки матрицы многоразрядных двоичных чисел R, и – вспомогательное простое многоразрядное двоичное число, затем генерируют m многоразрядных двоичных чисел по формуле после чего генерируют второе многоразрядное двоичное число s электронной цифровой подписи по формуле , причем коллективный открытый ключ генерируют в виде матрицы многоразрядных двоичных чисел Y, вычисляемой по формуле а первое и второе проверочные многоразрядные двоичные числа А и В формируют по формулам A=r’H mod и В=е, где r’=(r’₁₁||r’₁₂||r’₁₃) – многоразрядное двоичное число, равное конкатенации многоразрядных двоичных чисел первой строки матрицы многоразрядных двоичных чисел R’, вычисленной по формуле R’=Y^-eG^s(mod р).

5. Способ по п.1, отличающийся тем, что открытые ключи Y₁, Y₂, , Y_n генерируют в виде матриц многоразрядных двоичных чисел размерности 3×3, определитель каждой из которых по модулю многоразрядного двоичного числа р равен 1, для чего генерируют матрицу многоразрядных двоичных чисел G, имеющую порядок q, причем открытые ключи Y₁, Y₂, , Y_n формируют по формуле , где i=1, 2, , n, принимают m электронных документов, представленных многоразрядными двоичными числами H₁, H₂, , H_m, a электронную цифровую подпись формируют в виде пары многоразрядных двоичных чисел е и s, для чего генерируют m случайных многоразрядных двоичных чисел генерируют m матриц многоразрядных двоичных чисел по формуле , генерируют матрицу многоразрядных двоичных чисел R по формуле , после чего формируют первое многоразрядное двоичное число е электронной цифровой подписи по формуле е=а mod , где а=(а₁₁||а₁₂||а₁₃) – многоразрядное двоичное число, равное конкатенации многоразрядных двоичных чисел первой строки матрицы многоразрядных двоичных чисел R, и – вспомогательное простое многоразрядное двоичное число, затем генерируют m многоразрядных двоичных чисел по формуле , после чего генерируют второе многоразрядное двоичное число s электронной цифровой подписи по формуле , причем коллективный открытый ключ генерируют в виде матрицы многоразрядных двоичных чисел Y, вычисляемой по формуле а первое и второе проверочные многоразрядные двоичные числа А и В формируют по формулам A=r’ mod и В=е, где r’=(r’₁₁||r’₁₂||r’₁₃) – многоразрядное двоичное число, равное конкатенации многоразрядных двоичных чисел первой строки матрицы многоразрядных двоичных чисел R’, вычисленной по формуле R’=Y^-eG^s(mod р).

РИСУНКИ

HE4A – Изменение адреса для переписки с обладателем патента Российской Федерации на изобретение

Новый адрес для переписки с патентообладателем:

199178, Санкт-Петербург, 14-я линия, В.О., 39, СПИИРАН, Н.А.Молдовяну

Извещение опубликовано: 10.11.2009 БИ: 31/2009