GOST3410 (1014224), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Задаются число х₀ с условием 0 < x₀ < 2¹⁶ и нечетное число с условием 0 < c < 2¹⁶.

Процедура вычисления включает в себя следующие шаги:

1. По процедуре А получить простое число q длины t_q битов.

2. По процедуре А получить простое число Q длины 512 битов, при этом пункт 1 процедуры А не выполнять, а сохранить значение у₀, полученное в конце работы шага 1.

ГОСТ Р 34.10-94

3. Вычислить последовательность (у₁, ....,у₆₄) по рекурсивному правилу у_i+1 = (19381 у₁+ с) (mod 2¹⁶)

4. Вычислить у = у₁2¹⁶¹

5. у₀ := у₆₄

6. Вычислить

N =2^{t -1} /(qQ) + (2^{t -1} у)/( qQ2¹⁰²⁴)

Если N нечетно, то N := N+1

7. k := 0

8. Вычислить р = qQ(N + k) + 1

9/ Tckb p > 2^t , то перейти к шагу 3.

10. Проверить условия:

2^qQ(N+k)(mod p ) = 1,

2^q(N+k)(mod p) 1

Если оба условия выполнены, то р и q - искомые простые числа.

Если хотя бы одно не выполнено. то k := k + 2 и перейти к шагу 8.

последовательность шагов повторить до выполнения условий на шаге 10.

7.4 Процедура В’

процедура позволяет получать простые числа р длины t_p= 1021 1024 битов с делителем q длины t_q = 255  256 битов числа р-1.

Задаются число х₀ с условием 0 < x₀ < 2³² и нечетное число с с условием 0 < c < 2³².

Процедура вычисления включает в себя следующие шаги:

1. По процедуре А’ получить простое число q длины t_q битов.

ГОСТ Р 34.10-94

2. По процедуре А’ получить простое число Q длины 512 битов, при этом пункт 1 процедуры А’ не выполнять, а сохранить значение у₀, полученное в конце работы шага 1.

3. Вычислить последовательность (у₁, ...,у₃₂) по рекурсивному правилу у_i+1= (97781173 у_i+ c) (mod 2³²)

4. Вычислить у=  у₁ 2³²¹

5. у₀ := у₃₂

6. Вычислить

N = 2^{t -1} /(qQ) + (2^{t -1} y) / ( qQ2¹⁰²⁴)

Если N нечетно, то N := N + 1.

7. k := 0.

8. Вычислить р = qQ(N+k) + 1

9. Если р > 2^t , то перейти к шагу 3

10. Проверить условия:

2^qQ(N+k)(mod p ) = 1,

2^q(N+k)(mod p)  1

Если оба условия выполнены , то р и q - искомые простые числа.

Если хотя бы одно из условий не выполнено, то k := k + 2 и перейти к шагу 8.

Последовательность шагов повторить до выполнения условий на шаге 10.

ГОСТ Р 34.10-94

7.5 Процедура С

Процедура позволяет получить число а при заданных р и q.

1. Произвольно выбирать число d, 1 < d < p-1.

2. Вычислить f = d^p-1/q(mod p)

3. Если f = 1, то перейти к шагу 1.

Если f = 1, то а := f

Конец оаботы алгоритма.

Проверочные примеры для вышеизложенных процедур получение чисел р,q и а , выработки и проверки подписи приведены в приложении А.

ГОСТ Р 34.10-94

ПРИЛОЖЕНИЕ А

(справочное)

ПРОВЕРОЧНЫЕ ПРИМЕРЫ

Значение параметров х₀, c, d, x, y, k, указанные в приложении, рекомендуется использовать только в проверочных примерах для настоящего стандарта.

А.1 Представление чисел и векторов

Длины чисел и векоров, а также элементы последовательности t записывают в десятичной системе счисления.

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

А.2 Примеры к процедурам получения чисел р, q и числа а для реализации ЭЦП

А.2.1 Процедура А

Необходимо получить простое число р длины 512 битов с простым делителем q длины 256 битов числа р-1.

Задают числа х₀ = 5EC9 и с = 7341

Вычисляют последовательность t = (512, 256, 128, 64, 32, 16)

ГОСТ Р 34.10-94

Тогда в процессе выполнения процедуры будет получена последовательность простых чисел :

t₅ = 16, p₅ = 8003

t₄ = 32, p₄ = AD4BOFAB

t₃ = 64, p₃ = B25D28A7 1A62D775

t₂ = 128, p₂ = 9C992766 8E6E4908 964A9AE1 3773AE75

t₁ = 256, p₁ = 98915E7E C8265EDF CDA31E88 F24809DD

B064BDC7 285DD50D 7289FOAC 6F49DD2D

t₀ = 512, p₀ = EE8172AE 8996608F B69359B8 9EB82A69

854510E2 977A4D63 BC97322C E5DC3386

EA0A12B3 43E9190F 23177539 84583978

6BB0C345 D165976E F2195EC9 B1C379E3

p₁ и р₀ - искомые числа q и р соответсвенно.

А.2.2 Процедура А’

Необходимо получить простое число р длины 512 битов с простым делителем q длины 256 битов числа р-1.

Задаются числа х₀ = 3DFC46F1 и c=D.

Вычисляют последовательность t = (512, 256, 128, 64, 32).

Тосда в процессе выполнения процедуры будет получена последовательность простых чисел:

t₄ = 32, p₄ = 8000000B

t₃ = 64, p₃ = 9AAA6EBE 4AA58337

t₂ = 128, p₂ = C67CE4AF 720F7BBA B5FEBF37 B9E74807

p₁ и p₀ - искомые числа q и p соответсвенно.

ГОСТ Р 34.10-94

А.2.3 Процедура В

Необходимо получить простое число р длины 1024 битов с простым делителем q длины 256 битов числа р-1.

Задают начальные значения х₀ = A565 и с = 538B.

С помощью процедуры А получают простое число q длиной 1 = 256 битов:

Затем вновь с помощью процедуры А получают простое число Q длиной 1 = 512 битов:

И, наконец, получают простое число р длиной 1 = 1024 битов:

А.2.4 Процедура B’

Необходимо получить простое число р длины 1024 битов с простым делителем q длины 256 битов числа р-1.

Задают начальные значение х₀ = 3DFC46F1 и c = D.

С помощью процедуры А получают простое число q длиной 1 = 256 битов:

ГОСТ Р 34.10-94

Затем вновь с помощью процедуры А получают простое число Q длиной 1 = 512 битов:

И, наконец, получают простое число р длиной 1 = 1024 битов:

А.2.5 Процедура С

Пусть заданы числа р и q, полученные в А.2.1 по процедуре А:

Выбирают число d = 2.

Вычисляют

Так как f  1, то f - искомое число

a := f

ГОСТ Р 34.10-94

А.3 Примеры процедур выработки и проверки ЭЦП на базе асимметричного криптографического алгоритма

Пусть по процедуре А с начальными условиями х₀ = 5EC9 и с = 7341 выработаны числа р, q и а :

А.3.1 Процедура подписи собщения

- секретный ключ, М - подписываемое сообщение, причем значение хэш-функции h от сообщения М есть

Пусть целое число

Тогда

ГОСТ Р 34.10-94

Таким образом, цифровая подпись для сообщения М есть

А.3.2 Процедура проверки подписи

Характеристики

Список файлов стандарта