- Однонаправленные хэш-функции на основе симметричных блочных алгоритмов
- 3 обозначения
- 3 определения и обозначения
- 5 математические соглашения
- 7 процедуры получения чисел р, q и а
- В россии введут уголовную ответственность за неправильную выдачу электронной подписи
- Приложение б (справочное). контрольный пример
Однонаправленные хэш-функции на основе симметричных блочных алгоритмов
Однонаправленную хэш-функцию можно
построить, используя симметричный блочный алгоритм. Наиболее очевидный подход
состоит в том, чтобы шифровать сообщение М посредством блочного алгоритма в
режиме СВС или СFВ с помощью фиксированного ключа и некоторого вектора
инициализации IV.
Последний блок шифртекста можно рассматривать в качестве
хэш-значения сообщения М. При таком подходе не всегда возможно построить
безопасную однонаправленную хэш-функцию, но всегда можно получить код
аутентификации сообщения МАС (Message Authentication Code).
Более безопасный вариант хэш-функции
можно получить, используя блок сообщения в качестве ключа, предыдущее
хэш-значение – в качестве входа, а текущее хэш-значение – в качестве выхода.
Реальные хэш-функции проектируются еще более сложными. Длина блока обычно
определяется длиной ключа, а длина хэш-значения совпадает с длиной блока.
Поскольку большинство блочных алгоритмов являются 64-битовыми, некоторые
схемы хэширования проектируют так, чтобы хэш-значение имело длину, равную двойной длине блока.
Если принять, что получаемая
хэш-функция корректна, безопасность схемы хэширования базируется на безопасности
лежащего в ее основе блочного алгоритма. Схема хэширования, у которой длина
хэш-значения равна длине блока, показана на рис.3. Ее работа описывается
выражениями:
Н0 = Iн,
Нi = ЕA(В) Å С,
где
Å
– сложение по модулю 2 (исключающее ИЛИ);
Iн
– некоторое случайное начальное значение;
А, В, С
могут принимать значения
Мi,
Нi-1, (МiÅ
Нi-1)
или быть константами.
Рис.3. Обобщенная схема формирования хэш-функции
Сообщение М разбивается на блоки
Мi принятой длины, которые обрабатываются поочередно.
Три различные переменные А, В, С
могут принимать одно из четырех возможных значений, поэтому в принципе можно
получить 64 варианта общей схемы этого типа. Из них 52 варианта являются либо
тривиально слабыми, либо небезопасными. Остальные 12 схем безопасного хэширования,
у которых длина хэш-значения равна длине блока перечислены в табл.1.
Таблица 1 | ||||||||||||||||||||||||||
|
Первые четыре схемы хэширования,
являющиеся безопасными при всех атаках, приведены на рис.4.
Рис.4. Четыре схемы безопасного хэширования
Недостатком хэш-функций, спроектированных на основе блочных алгоритмов, является несколько
заниженная скорость работы. Дело в том, что ту же самую стойкость относительно двух основных
требований к хэш-функции можно обеспечить за гораздо меньшее количество операций над входными
данными.
Но для этого алгоритм необходимо изначально проектировать специально, исходя из
тандема требований (стойкость, скорость). Далее рассмотрены три самостоятельных алгоритма
криптостойкого хэширования, получивших наибольшее распространение на сегодняшний день.
Алгоритм MD5 (Message Digest №5) разработан Роналдом Риверсом.
MD5 использует 4 многократно повторяющиеся преобразования над тремя 32-битными величинами
U, V и W:
f(U,V,W)=(U AND V) OR ((NOT U) AND W) g(U,V,W)=(U AND W) OR (V AND (NOT W)) h(U,V,W)=U XOR V XOR W k(U,V,W)=V XOR (U OR (NOT W)).
В алгоритме используются следующие константы:
- начальные константы промежуточных величин –
H[0]=6745230116, H[1]=EFCDAB8916, H[2]=98BADCFE16, H[3]=1032547616;
- константы сложения в раундах –
y[j]=HIGHEST_32_BITS(ABS(SIN(j 1))) j=0...63,
где функция HIGHEST_32_BITS(X) отделяет 32 самых старших бита из двоичной записи
дробного числа X, а операнд SIN(j 1) считается взятым в радианах; - массив порядка выбора ячеек в раундах –
z[0...63] = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 5, 8, 11, 4, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2, 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9);
- массив величины битовых циклических сдвигов влево –
s[0...63] = (7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21).
На первоначальном этапе входной блок данных дополняется одним битом “1”. Затем к нему
добавляется такое количество битов “0”, чтобы остаток от деления блока на 512 составлял 448.
Наконец, к блоку добавляется 64-битная величина, хранящая первоначальную длину документа.
Получившийся входной поток имеет длину кратную 512 битам.
Каждый 512-битный блок, представленный в виде 16 32-битных значений
X[0]…X[15], проходит через сжимающую функцию, которая перемешивает его
со вспомогательным блоком (H[0],H[1],H[2],H[3]):
(A,B,C,D) = (H[0],H[1],H[2],H[3]) цикл по j от 0 до 15 T = (A f(B,C,D) x[z[j]] y[j]) ROL s[j] (A,B,C,D) = (D,B T,B,C) конец_цикла цикл по j от 16 до 31 T = (A g(B,C,D) x[z[j]] y[j]) ROL s[j] (A,B,C,D) = (D,B T,B,C) конец_цикла цикл по j от 32 до 47 T = (A h(B,C,D) x[z[j]] y[j]) ROL s[j] (A,B,C,D) = (D,B T,B,C) конец_цикла цикл по j от 48 до 63 T = (A k(B,C,D) x[z[j]] y[j]) ROL s[j] (A,B,C,D) = (D,B T,B,C) конец_цикла (H[0],H[1],H[2],H[3]) = (H[0] A,H[1] B,H[2] C,H[3] D)
После того, как все 512-битные блоки прошли через процедуру перемешивания, временные
переменные H[0],H[1],H[2],H[3], а 128-битное значение подается на выход хэш-функции.
Алгоритм MD5, основанный на предыдущей разработке Роналда Риверса MD4, был призван
дать еще больший запас прочности к криптоатакам. MD5 очень похож на MD4. Отличие состоит в
простейших изменениях в алгоритмах наложения и в том, что в MD4 48 проходов основного
преобразования, а в MD5 – 64.
Несмотря на большую популярность, MD4 “медленно, но верно” был
взломан. Сначала появились публикации об атаках на упрощенный алгоритм. Затем было заявлено о
возможности найти два входных блока сжимающей функции MD4, которые порождают одинаковый
выход.
Наконец, в 1995 году было показано, что найти коллизию, т.е. “хэш-двойник” к
произвольному документу, можно менее чем за минуту, а добиться “осмысленности” фальшивого
документа (т.е. наличия в нем только ASCII-символов с определенными “разумными” законами
расположения) – всего лишь за несколько дней.
Алгоритм безопасного хэширования SНА
(Secure Hash Algorithm) разработан НИСТ и АНБ США в рамках стандарта безопасного
хэширования SHS (Secure Hash Standard) в 1992 г. Алгоритм хэширования SНА
предназначен для использования совместно с алгоритмом цифровой подписи DSА.
При вводе сообщения М произвольной
длины менее 264 бит алгоритм SНА вырабатывает 160-битовое выходное
сообщение, называемое дайджестом сообщения МD (Message Digest). Затем этот
дайджест сообщения используется в качестве входа алгоритма DSА, который
вычисляет цифровую подпись сообщения М.
Такой же дайджест сообщения должен
вычисляться пользователем, проверяющим полученную подпись, при этом в качестве
входа в алгоритм SНА используется полученное сообщение М.
Алгоритм хэширования SНА назван
безопасным, потому что он спроектирован таким образом, чтобы было вычислительно
невозможно восстановить сообщение, соответствующее данному дайджесту, а также
найти два различных сообщения, которые дадут одинаковый дайджест.
Рассмотрим подробнее работу алгоритма
хэширования SНА. Прежде всего исходное сообщение М дополняют так, чтобы оно
стало кратным 512 битам. Дополнительная набивка сообщения выполняется следующим
образом: сначала добавляется единица, затем следуют столько нулей, сколько
необходимо для получения сообщения, которое на 64 бита короче, чем кратное 512,
и наконец добавляют 64-битовое представление длины исходного
сообщения.
Инициализируется пять 32-битовых переменных в виде:
А = 0х67452301 В = 0хЕFСDАВ89 С = 0х98ВАDСFЕ D = 0x10325476 Е = 0хС3D2Е1F0
Затем начинается главный цикл
алгоритма. В нем обрабатывается по 512 бит сообщения поочередно для всех
512-битовых блоков, имеющихся в сообщении. Первые пять переменных А, В, С, D, Е
копируются в другие переменные a, b, с, d, е:
а = А, b = В, с = С, d = D, е = Е
Главный цикл содержит четыре цикла по
20 операций каждый. Каждая операция реализует нелинейную функцию от трех из пяти
переменных а, b, с, d, е, а затем производит сдвиг и сложение.
Алгоритм SНА имеет следующий набор
нелинейных функций:
ft (Х, Y, Z) = (X Ù Y) Ú ((Ø X) Ù Z) для t = 0...19, ft (Х, Y, Z) =Х Å Y Å Z для t = 20...39, ft (Х, Y, Z) = (X Ù Y) Ú (X Ù Z) Ú (Y Ù Z) для t = 40...59, ft (Х, Y, Z) = Х Å Y Å Z для t = 60...79,
где
t
– номер операции.
В алгоритме используются также четыре константы:
Кt = 0х5А827999 для t = 0...19, Кt = 0х6ЕD9ЕВА1 для t = 20...39, Кt = 0х8F1ВВСDС для t = 40...59, Кt = 0хСА62С1D6 для t = 60...79.
Блок сообщения преобразуется из шестнадцати 32-битовых слов
(М0…М15) в восемьдесят 32-битовых слов
(W0…W79) с помощью следующего алгоритма:
Wt = Мt для t = 0...15, Wt = (Wt-3Å Wt-8Å Wt-14Å Wt-16) <<< 1 для t = 16...79,
где
t
– номер операции,
Wtt
-й субблок расширенного сообщения,
<<<
S
– циклический сдвиг влево на
S
бит.
С учетом введенных обозначений главный цикл из восьмидесяти операций можно
описать так:
цикл по t от 0 до 79 ТЕМР = (а <<< 5) ft (b, c, d) е Wt Кt е = d d = с с = (b <<< 30) b = а а = ТЕМР конец_цикла
Схема выполнения одной операции показана на рис.5.
Рис.5. Схема выполнения одной операции алгоритма SHA
После окончания главного цикла
значения а, b, с, d, е складываются с А, В, С, D, Е соответственно, и
алгоритм приступает к обработке следующего 512-битового блока данных. Окончательный выход
формируется в виде конкатенации значений А, В, С, D, Е.
Отличия SHA от MD5 состоят в следующем:
- SНА выдает 160-битовое хэш-значение, поэтому он более устойчив к атакам
полного перебора и атакам “дня рождения”, чем MD5, формирующий 128-битовые хэш-значения. - Сжимающая функция SHA состоит из 80 шагов, а не из 64 как в MD5.
- Расширение входных данных производится не простым их повторение в другом порядке, а
рекуррентной формулой. - Усложнен процесс перемешивания
3 обозначения
В настоящем стандарте используются следующие обозначения.
– множество всех конечных слов в алфавите = {0,1}.
|А| – длина слова
(2) – множество всех бинарных слов длины k.
z (mod n) – наименьшее по значению неотрицательное число, сравнимое с z по модулю числа n.
<N> – слово длины k, содержащее двоичную запись вычета N (mod 2) неотрицательного целого числа N.
– неотрицательное целое число, имеющее двоичную запись
(2) – множество всех бинарных слов длины k.
z (mod n) – наименьшее по значению неотрицательное число, сравнимое с z по модулю числа n.
<N> – слово длины k, содержащее двоичную запись вычета N (mod 2) неотрицательного целого числа N.
– неотрицательное целое число, имеющее двоичную запись
А||В – конкатенация слов A,
A – конкатенация k экземпляров слова
A – конкатенация k экземпляров слова
М – передаваемое сообщение,
М – полученное сообщение,
М – полученное сообщение,
________________________
Отправляемые и получаемые последовательности, в том числе сообщения и подписи, могут отличаться друг от друга из-за случайных или преднамеренных искажений.
h – хэш-функция, отображающая сообщение М в слово
р – простое число, 2 < p < 2 либо 2 < p < 2.
q – простое число, 2< q < 2и q является делителем для (р – 1).
а – целое число, 1 < а < р – 1, при этом а(mod p) = 1.
k – целое число, 0 < k < q.
[d] – наименьшее целое число, не меньшее чем d.
[d] – наибольшее целое число, не большее чем d.
e: = g – присвоение параметру е значения g.
х – секретный ключ пользователя для формирования подписи, 0 < x < q.
у – открытый ключ пользователя для проверки подписи, у = a (mod р).
3 определения и обозначения
3.1 ОпределенияВ настоящем стандарте использованы следующие термины:
3.1.1 дополнение (appendix): Строка бит, формируемая из цифровой подписи и произвольного текстового поля (ИСО/МЭК 148881-1 [3]).
3.1.2 ключ подписи (signature key): Элемент секретных данных, специфичный для субъекта и используемый только данным субъектом в процессе формирования цифровой подписи (ИСО/МЭК 14888-1 [3]).
3.1.3 ключ проверки (verification key): Элемент данных, математически связанный с ключом подписи и используемый проверяющей стороной в процессе проверки цифровой подписи (ИСО/МЭК 14888-1 [3]).
3.1.4 параметр схемы ЭЦП (domain parameter): Элемент данных, общий для всех субъектов схемы цифровой подписи, известный или доступный всем этим субъектам (ИСО/МЭК 14888-1 [3]).
3.1.5 подписанное сообщение (signed message): Набор элементов данных, состоящий из сообщения и дополнения, являющегося частью сообщения.
3.1.6 последовательность псевдослучайных чисел (pseudo-random number sequence): Последовательность чисел, полученная в результате выполнения некоторого арифметического (вычислительного) процесса, используемая в конкретном случае вместо последовательности случайных чисел (ИСО 2382-2 [1]).
3.1.7 последовательность случайных чисел (random number sequence): Последовательность чисел, каждое из которых не может быть предсказано (вычислено) только на основе знания предшествующих ему чисел данной последовательности (ИСО 2382-2 [1]).
3.1.8 процесс проверки подписи (verification process): Процесс, в качестве исходных данных которого используются подписанное сообщение, ключ проверки и параметры схемы ЭЦП и результатом которого является заключение о правильности или ошибочности цифровой подписи (ИСО/МЭК 14888-1 [3]).
3.1.9 процесс формирования подписи (signature process): Процесс, в качестве исходных данных которого используются сообщение, ключ подписи и параметры схемы ЭЦП, а в результате формируется цифровая подпись (ИСО/МЭК 14888-1 [3]).
3.1.10 свидетельство (witness): Элемент данных, представляющий соответствующее доказательство достоверности (недостоверности) подписи проверяющей стороне (ИСО/МЭК 14888-1 [3]).
3.1.11 случайное число (random number): Число, выбранное из определенного набора чисел таким образом, что каждое число изданного набора может быть выбрано с одинаковой вероятностью (ИСО 2382-2 [1]).
3.1.12 сообщение (message): Строка бит ограниченной длины (ИСО/МЭК 9796 [2]).
3.1.13 хэш-код (hash-code): Строка бит, являющаяся выходным результатом хэш-функции (ИСО/МЭК 148881-1 [3]).
3.1.14 хэш-функция (hash-function): Функция, отображающая строки бит в строки бит фиксированной длины и удовлетворяющая следующим свойствам:
1) по данному значению функции сложно вычислить исходные данные, отображенные в это значение;
2) для заданных исходных данных трудно найти другие исходные данные, отображаемые с тем же результатом;
3) трудно найти какую-либо пару исходных данных с одинаковым значением хэш-функции.Примечание – Применительно к области ЭЦП свойство 1 подразумевает, что по известной ЭЦП невозможно восстановить исходное сообщение;
свойство 2 подразумевает, что для заданного подписанного сообщения трудно подобрать другое (фальсифицированное) сообщение, имеющее ту же ЭЦП, свойство 3 подразумевает, что трудно подобрать какую-либо пару сообщений, имеющих одну и ту же подпись.
3.1.15 [электронная] цифровая подпись (digital signature): Строка бит, полученная в результате процесса формирования подписи. Данная строка имеет внутреннюю структуру, зависящую от конкретного механизма формирования подписи.Примечание – В настоящем стандарте в целях сохранения терминологической преемственности с действующими отечественными нормативными документами и опубликованными научно-техническими изданиями, установлено, что термины “цифровая подпись” и “электронная цифровая подпись (ЭЦП)” являются синонимами.
В настоящем стандарте использованы следующие обозначения:
– множество всех двоичных векторов длиной 256 бит;
– множество всех двоичных векторов произвольной конечной длины;
Z – множество всех целых чисел;
– простое число, >3;
– конечное простое поле, представляемое как множество из целых чисел {0, 1, … , -1};
– сообщение пользователя,
– сообщение пользователя,
, – коэффициенты эллиптической кривой;
– порядок группы точек эллиптической кривой;
– порядок подгруппы группы точек эллиптической кривой;
– нулевая точка эллиптической кривой;
– точка эллиптической кривой порядка ;
– целое число – ключ подписи;
– точка эллиптической кривой – ключ проверки;
– цифровая подпись под сообщением .
5 математические соглашения
Для определения схемы цифровой подписи необходимо описать базовые математические объекты, используемые в процессах ее формирования и проверки. В данном разделе установлены основные математические определения и требования, накладываемые на параметры схемы цифровой подписи.
5.1 Математические определения
Пусть задано простое число >3. Тогда эллиптической кривой , определенной над конечным простым полем , называется множество пар чисел (, ), , , удовлетворяющих тождеству
(1)
где (1)
где
Инвариантом эллиптической кривой называется величина , удовлетворяющая тождеству
Инвариантом эллиптической кривой называется величина , удовлетворяющая тождеству
(2)
Коэффициенты , эллиптической кривой , по известному инварианту , определяются следующим образом
(3)
Пары (, ), удовлетворяющие тождеству (1), называются точками эллиптической кривой ; и – соответственно – и -координатами точки.
Точки эллиптической кривой будем обозначать (3)
Пары (, ), удовлетворяющие тождеству (1), называются точками эллиптической кривой ; и – соответственно – и -координатами точки.
Точки эллиптической кривой будем обозначать
На множестве всех точек эллиптической кривой введем операцию сложения, которую будем обозначать знаком ” “. Для двух произвольных точек
Пусть координаты точек и удовлетворяют условию
(4)
Если выполнены равенства
(5)
В случае, когда выполнено условие
(6)
где – произвольная точка эллиптической кривой .
Относительно введенной операции сложения множество всех точек эллиптической кривой , вместе с нулевой точкой, образуют конечную абелеву (коммутативную) группу порядка , для которого выполнено неравенство
(6)
где – произвольная точка эллиптической кривой .
Относительно введенной операции сложения множество всех точек эллиптической кривой , вместе с нулевой точкой, образуют конечную абелеву (коммутативную) группу порядка , для которого выполнено неравенство
(7)
Точка называется точкой кратности , или просто кратной точкой эллиптической кривой , если для некоторой точки выполнено равенство
(8)5.2 Параметры цифровой подписи
Параметрами схемы цифровой подписи являются:
– простое число – модуль эллиптической кривой, удовлетворяющее неравенству (8)5.2 Параметры цифровой подписи
Параметрами схемы цифровой подписи являются:
– простое число – модуль эллиптической кривой, удовлетворяющее неравенству
– эллиптическая кривая , задаваемая своим инвариантом или коэффициентами ,
– целое число – порядок группы точек эллиптической кривой ;
– простое число – порядок циклической подгруппы группы точек эллиптической кривой , для которого выполнены следующие условия:
– целое число – порядок группы точек эллиптической кривой ;
– простое число – порядок циклической подгруппы группы точек эллиптической кривой , для которого выполнены следующие условия:
(9)
– точка
-хэш-функция (·):
-хэш-функция (·): ГОСТ Р 34.11.
Каждый пользователь схемы цифровой подписи должен обладать личными ключами:
– ключом подписи – целым числом , удовлетворяющим неравенству 0<<;
– ключом проверки – точкой эллиптической кривой с координатами (
На приведенные выше параметры схемы цифровой подписи накладываются следующие требования:
– должно быть выполнено условие
– должно быть выполнено неравенство
– должно быть выполнено неравенство
– инвариант кривой должен удовлетворять услови ю
5.3 Двоичные векторыДля определения процессов формирования и проверки цифровой подписи необходимо установить соответствие между целыми числами и двоичными векторами длины 256 бит.Рассмотрим следующий двоичный вектор длиной 256 бит, в котором младшие биты расположены справа, а старшие – слева
(10)
где , =0,…, 255 равно либо 1, либо 0. Будем считать, что число (10)
где , =0,…, 255 равно либо 1, либо 0. Будем считать, что число
(11)
Для двух двоичных векторов и , соответствующих целым числам и , определим операцию конкатенации (объединения) следующим образом. Пусть
(11)
Для двух двоичных векторов и , соответствующих целым числам и , определим операцию конкатенации (объединения) следующим образом. Пусть
(12)
тогда их объединение имеет вид
(13)
и представляет собой двоичный вектор длиной 512 бит, составленный из коэффициентов векторов и .
С другой стороны, приведенные формулы определяют способ разбиения двоичного вектора длиной 512 бит на два двоичных вектора длиной 256 бит, конкатенацией которых он является.
7 процедуры получения чисел р, q и а
Получение простых чисел осуществляется с использованием линейного конгруэнтного датчика по модулю 2 или по модулю 2 (х= bx с). При этом пользователь должен задавать начальное состояние х и параметр датчика с.
Заданные величины необходимо зафиксировать (запомнить) для возможности проведения проверки того, что простые числа получены по установленной процедуре.
Ниже изложены процедуры получения параметров р, q и а.
7.1 Процедура А
Процедура позволяет получать простые числа р длины t17 битов с простым делителем q длины [t/] битов числа р-1.
Получение чисел осуществляется с использованием линейного конгруэнтного датчика х= (19381 х с) (mod 2).
Задаются число х с условием 0 < х< 2 и нечетное число с с условием 0 < с < 2.
Процедура вычисления включает в себя следующие шаги:
1 y: = x
2 Вычислить последовательность чисел (t, t, …, t) по правилу:
t: = t.
Если t17, то t =[t/2],
Если t < 17, то s: = i.
3 Найти наименьшее простое число р, длины t битов.
4 m: = s – 1
5 Вычислить r =[t/16].
6 Вычислить последовательность (у, …, у) по рекурсивному правилу у = (19381 у с) (mod 2).
7 Вычислить
8 y: = y.
9 Вычислить N = [2m/p] [(2mY)/( p2].
Если N нечетно, то N : = N 1.
10 k : = 0.
11 Вычислить p = p (N k) 1.
12 Если р > 2m, то перейти к шагу 6.
13 Проверить условия:
2
2(mod p) 1.
Если хотя бы одно из условий не выполнено, то k : = k 2 и перейти к шагу 11.
Если оба условия выполнены, то m : = m – 1.
14 Если m 0, то перейти к шагу 5.
Если m < 0, то р – искомое простое число р и p – искомое простое число q.
7.2 Процедура А’
Процедура позволяет получать простые числа р длины t 33 битов с простым делителем q длины [t/2] битов числа р-1.
Получение числа осуществляется с использованием линейного конгруэнтного датчика х = (97781173 х с) (mod 2).
Задаются число х с условием 0 < Х < 2 и нечетное число с с условием 0 < с < 2.
Процедура вычисления включает в себя следующие шаги:
1 у: = х
2 Вычислить последовательность чисел (t, t, …, t) пo правилу:
t : = t.
Если t33, то t = [t/2],
Если t < 33, то s : = i
3 Найти наименьшее простое число р длины t битов.
4 m : = s – 1.
5 Вычислить r = [t /32].
6 Вычислить последовательность (y, …, y) по рекурсивному правилу y= (97781173 y c) mod (2).
7 Вычислить 8 y : = y.
9 Вычислить N = [2m/p] [(2mY)/(p2)].
Если N нечетно, то N : = N 1.
10 k : = 0.
11 Вычислить p = p (N k) 1.
12 Если р > 2m, то перейти к шагу 6.
13 Проверить условия:
2
2(mod p) 1.
Если хотя бы одно из условий не выполнено, то k : = k 2 и перейти к шагу 11.
Если оба условия выполнены, то m : = m – 1.
14 Если m 0, то перейти к шагу 5.
Если m < 0, то р – искомое простое число р и p – искомое простое число q.
7.3 Процедура B
Процедура позволяет получать простые числа р длины t= 10211024 битов с делителем q длины t= 255256 битов числа р – 1.
Задаются число х с условием 0 < х < 2 и нечетное число с с условием 0 < с < 2.
Процедура вычисления включает в себя следующие шаги:
1 По процедуре А получить простое число q длины t битов.
2 По процедуре А получить простое число Q длины 512 битов, при этом пункт 1 процедуры А не выполнять, а сохранить значение у, полученное в конце работы шага 1.
3 Вычислить последовательность (y, …, y) по рекурсивному правилу y= (19381 y c) (mod 2).
4 Вычислить
2(mod p) 1.
Если хотя бы одно из условий не выполнено, то k : = k 2 и перейти к шагу 11.
Если оба условия выполнены, то m : = m – 1.
14 Если m 0, то перейти к шагу 5.
Если m < 0, то р – искомое простое число р и p – искомое простое число q.
7.3 Процедура B
Процедура позволяет получать простые числа р длины t= 10211024 битов с делителем q длины t= 255256 битов числа р – 1.
Задаются число х с условием 0 < х < 2 и нечетное число с с условием 0 < с < 2.
Процедура вычисления включает в себя следующие шаги:
1 По процедуре А получить простое число q длины t битов.
2 По процедуре А получить простое число Q длины 512 битов, при этом пункт 1 процедуры А не выполнять, а сохранить значение у, полученное в конце работы шага 1.
3 Вычислить последовательность (y, …, y) по рекурсивному правилу y= (19381 y c) (mod 2).
4 Вычислить 5 y : = y.
6 Вычислить
N = [2p/(qQ)] [(2pY)/(qQ2)].
Если N нечетно, то N : = N 1.
7 k : = 0.
8 Вычислить p = qQ (N k) 1.
9 Если р > 2p, то перейти к шагу 3.
10 Проверить условия:
2
2
2
Если оба условия выполнены, то р и q – искомые простые числа.
Если хотя бы одно из условий не выполнено, то k : = k 2 и перейти к шагу 8.
Последовательность шагов повторить до выполнения условий на шаге 10.
7.4 Процедура В’
Процедура позволяет получать простые числа р длины t = 10211024 битов с делителем q длины t = 255256 битов числа р – 1.
Задаются число х с условием 0 < х < 2 и нечетное число с с условием 0 < с < 2.
Процедура вычисления включает в себя следующие шаги:
1 По процедуре А’ получить простое число q длины t битов.
2 По процедуре A’ получить простое число Q длины 512 битов, при этом пункт 1 процедуры А’ не выполнять, а сохранить значение у, полученное в конце работы шага 1.
3 Вычислить последовательность (y, …, у) по рекурсивному правилу y = (97781173 у с) (mod 2).
4 Вычислить 5 y : = y.
6 Вычислить
N = [2p/ (qQ)] [(2pY)/(qQ2)].
Если N нечетно, то N : = N 1.
7 k : = 0.
8 Вычислить p = qQ (N k) 1.
9 Если р > 2, то перейти к шагу 3.
10 Проверить условия:
2
2
2
Если оба условия выполнены, то р и q – искомые простые числа.
Если хотя бы одно из условий не выполнено, то k : = k 2 и перейти к шагу 8.
Последовательность шагов повторить до выполнения условий на шаге 10.
7.5 Процедура СПроцедура позволяет получить число а при заданных р и q.
1 Произвольно выбрать число d, 1 < d < p -1.
2 Вычислить
3 Если f = 1, то перейти к шагу 1.
Если f 1, то a : = f.
Конец работы алгоритма.
Проверочные примеры для вышеизложенных процедур получения чисел р, q и а, выработки и проверки подписи приведены в приложении А.
В россии введут уголовную ответственность за неправильную выдачу электронной подписи
8 июля 2021 года стало известно, что Министр экономического развития Максим Орешкин выступил за скорейшее принятие законопроекта, ужесточающего требования к удостоверяющим центрам электронной подписи. Соответствующее заявление министр сделал в ходе парламентских слушаний в Госдуме, посвященных вопросам Цифровой экономики.
В Госдуму были внесены сразу два законопроекта с поправками в Закон «Об электронной подписи». Первый из них разработан сенаторами Владимиром Кравченко, Любовью Глебовой и Михаилом Пономаревым, второй – сенатором Людмилой Боковой.
Закон «Об электронно-цифровой подписи» был принят в России в 2003 г. К документу было множество нареканий, и в 2021 г. его заменили новым Законом – «Об электронной подписи».
В законе упоминается электронная подпись трех видов: простая, усиленная и квалифицированная. Усиленная электронная подпись выдается удостоверяющим центром, квалифицированная – удостоверяющим центром, прошедшим аккредитацию в Минкомсвязи.
Изначально закон требовал, что для аккредитованных удостоверяющих центров минимальный размер чистых активов должен составлять 1 млн руб., а минимальный размер финансового обеспечения для покрытия возможных убытков третьим лицам 1,5 млн руб.
В 2021 г. по инициативе Минкомсвязи законодатели увеличили минимальный размер чистых активов до 7 млн руб., а минимальный размер финансового обеспечения – до 30 млн руб. Но власти хотели и дальше ужесточать требования к удостоверяющим центрам. Так, в 2021 г.
В представленных законопроектах речь идет о дальнейшем ужесточении требований к аккредитованным удостоверяющим центрам. Согласно обоим документам, минимальный размер чистых активов предлагается увеличить до 1 млрд руб., либо, если у удостоверяющего центра есть филиалы в как минимум двух третях российских регионов, до 500 млн руб.
Минимальный размер финансовой гарантии предлагается увеличить до 200 млн руб. Если число мест осуществления лицензируемого вида деятельности превышает 10, то за каждое такое место необходима дополнительная финансовая гарантия в размере 500 тыс. руб., но не более 300 млн руб. в совокупности.
Срок аккредитации удостоверяющих центров сокращается с пяти до трех лет. За нарушения в работе удостоверяющих центров технического характера вводится административная ответственность.
За заведомо умышленные действия сотрудников удостоверяющих центров помимо административной, вводится еще и уголовная ответственность.
Также вводятся требования к деловой репутации руководителей удостоверяющих центров и лиц, владеющих в них не менее чем 10% капитала. Если аккредитация удостоверяющего центра была отозвана, то центр сможет обратиться за новой аккредитацией не ранее чем через три года.
Другое важное требование состоит в использовании юридическими лицами электронных подписей, причем здесь подходы обоих документов расходятся. Законопроект Кравченко, Глебовой и Пономарева предполагает обязать использовать только квалифицированные электронные подписи, выданные удостоверяющим центром Федеральной налоговой службы (ФНС).
В случаях с кредитными организациями, некредитными финансовыми организациями и платежными системами будут применять квалифицированные электронные подписи, выданные удостоверяющими центрами Центробанка. В случаях с органами государственной власти и местного самоуправления, а также их должностными лицами будут применяться квалифицированные электронные подписи, выданные удостоверяющими центрами Федерального казначейства.
Законопроект Боковой более либерален. Он позволит юридическим лицами продолжить использовать квалифицированные электронные подписи от любых аккредитованных удостоверяющих центров. ФНС сможет отзывать сертификаты электронных подписей юридических лиц и индивидуальных предпринимателей.
Аналогичным образом, Центробанк сможет отзывать сертификаты электронных подписей кредитных организаций, некредитных финансовых организаций и платежных систем. Как и в другом законопроекте, законопроект Боковой также требует от органов госвласти и их должностных лиц получать квалифицированные электронные подписи только в удостоверяющем центре Федерального казначейства.
В случае принятия обоих законопроектов они вступят в силу в течение 120 дней с момента их подписания. Сертификаты квалифицированных электронных подписей и аккредитации удостоверяющих центров, выданные до опубликования данного закона, будут действительны до конца срока их действия, но не более двух лет.
Норма законопроекта Кравченко, Глебовой и Пономарева об использовании юридическими лицами квалифицированных электронных подписей, выданных удостоверяющим центром ФНС и Центробанком, вступит в силу через два года после опубликования соответствующих законов.
В то же время есть и некоторые послабления. Удостоверяющие центры смогут привлекать третьих лиц для приема заявлений на выдачу сертификатов электронных подписей и вручению данных сертификатов.
Кроме того, удостоверяющие центры смогут хранить ключи проверки электронных подписей, и по поручению их владельцев, создавать с их помощью электронные подписи. Как пояснил Орешкин, речь идет о возможности использования облачной электронной подписи.
Законопроект вводит понятие доверенной третей стороны. Она будет проверять подлинность электронной подписи в электронных документах в конкретный момент и проверять подлинность электронных подписей, выданных за рубежом. Доверенные третьи лица должны будут проходить аккредитацию в Минкомсвязи. Ожидается, что в России появится около 20 таких лиц.
В связи с этим вводится еще одно понятие – метка доверенного времени. Это достоверная информация в электронной форме о дате и времени подписания электронного документа электронной подписью, создаваемая и проверяемая доверенной третьей стороной, удостоверяющим центров либо операторов информационной системы.
Удостоверяющие центры должны будут выдавать сертификаты электронных подписей по цене, не превышающей установленное Правительством значение. Лицам, получившим сертификаты, безвозмездно должна быть предоставлена возможность зарегистрироваться в Единой системе идентификации и аутентификации.
Авторы законопроектов утверждают, что предложенные ими документы решат еще одну проблему. На июль 2021 года госведомства требуют наличия в сертификатах квалифицированных электронных подписей наличия тех или иных полномочий, закрепляемых за пользователем в рамках конкретной информационной системы.
В результате сертификаты, выданные аккредитованными удостоверяющими центрами, не могут быть использованы в некоторых информационных системах, и удостоверяющие центры вынуждены предлагать квалифицированные электронные подписи для работы в конкретных информационных системах.[11]
Приложение б (справочное). контрольный пример
ПРИЛОЖЕНИЕ Б(справочное)
Данное приложение носит справочный характер и не является частью стандарта. Приводимые ниже значения параметров , , , , , , а также значения ключей подписи и проверки и рекомендуется использовать только для проверки корректной работы конкретной реализации алгоритмов, описанных в настоящем стандарте.
Все числовые значения приведены в десятичной и шестнадцатеричной записи. Нижний индекс в записи числа обозначает основание системы счисления. Символ “\” обозначает перенос числа на новую строку. Например, запись
12345\
67890499602D2
представляет целое число 1234567890, соответственно, в десятичной и шестнадцатеричной системах счисления.
Б.1 Параметры схемы цифровой подписиДля формирования и проверки цифровой подписи должны быть использованы следующие параметры (см.5.2).
Б.1.1 Модуль эллиптической кривой
В данном примере параметру присвоено следующее значение:
=57896044618658097711785492504343953926\634992332820282021728792003956564821041р=8000000000000000000000000000000000000000000000000000000000000431Б.1.2 Коэффициенты эллиптической кривой
В данном примере параметры и принимают следующие значения:
=43308876546767276905765904595650931995\942111794451039583252968842033849580414=5FBFF498AA938CE739B8E022FBAFEF40563F6E6A3472FC2A514C0CE9DAE23B7EБ.1.3 Порядок группы точек эллиптической кривой
В данном примере параметр принимает следующее значение:
=5789604461865809771178549250434395392\7082934583725450622380973592137631069619=8000000000000000000000000000000150FE8A1892976154C59CFC193ACCF5B3Б.1.4 Порядок циклической подгруппы группы точек эллиптической кривой
В данном примере параметр принимает следующее значение:
=5789604461865809771178549250434395392\7082934583725450622380973592137631069619=8000000000000000000000000000000150FE8A1892976154C59CFC193ACCF5B3Б.1.5 Коэффициенты точки эллиптической кривой
В данном примере координаты точки принимают следующие значения:
=40189740565390375033354494229370597\75635739389905545080690979365213431566280=8E2A8A0E65147D4BD6316030E16D19\C85C97F0A9CA267122B96ABBCEA7E8FC8Б.1.6 Ключ подписи
В данном примере считается, что пользователь обладает следующим ключом подписи :
=554411960653632461263556241303241831\96576709222340016572108097750006097525544=7A929ADE789BB9BE10ED359DD39A72C\11B60961F49397EEE1D19CE9891EC3B28Б.1.7 Ключ проверки
В данном примере считается, что пользователь обладает ключом проверки , координаты которого имеют следующие значения:
=57520216126176808443631405023338071\176630104906313632182896741342206604859403=7F2B49E270DB6D90D8595BEC458B5\0C58585BA1D4E9B788F6689DBD8E56FD80B=17614944419213781543809391949654080\031942662045363639260709847859438286763994=26F1B489D6701DD185C8413A977B3\CBBAF64D1C593D26627DFFB101A87FF77DA
Б.2 Процесс формирования цифровой подписи (алгоритм I)Пусть после выполнения шагов 1-3 по алгоритму I (6.1) были получены следующие числовые значения:
=2079889367447645202113406156150827013\0637142515379653289952617252661468872421=2DFBC1B372D89A1188C09C52Е0EE\
C61FCE52032AB1022E8E67ECE6672B043EE5=538541376773484637314038411479966192\41504003434302020712960838528893196233395=77105C9B20BCD3122823C8CF6FCC\7B956DE33814E95B7FE64FED924594DCEAB3При этом кратная точка
Параметр
Параметр
=297009809158179528743712049839382569\90422752107994319651632687982059210933395=41AA28D2F1AB148280CD9ED56FED\A41974053554A42767B83AD043FD39DC0493
Параметр
=57497340027008465417892531001914703\8455227042649098563933718999175515839552=1456C64BA4642A1653C235A98A60249BCD6D3F746B631DF928014F6C5BF9C40
Б.З Процесс проверки цифровой подписи (алгоритм II)Пусть после выполнения шагов 1-3 по алгоритму II (6.2) было получено следующее числовое значение:
=2079889367447645202113406156150827013\0637142515379653289952617252661468872421=2DFBC1B372D89A1188C09C52E0EE\C61FCE52032AB1022E8E67ECE6672B043EE5
При этом параметр
=176866836059344686773017138249002685\62746883080675496715288036572431145718978=271A4EE429F84EBC423E388964555BB\29D3BA53C7BF945E5FAC8F381706354C2
Параметры
=176866836059344686773017138249002685\62746883080675496715288036572431145718978=271A4EE429F84EBC423E388964555BB\29D3BA53C7BF945E5FAC8F381706354C2
Параметры
=376991675009019385568410572935126561\08841345190491942619304532412743720999759=5358F8FFB38F7C09ABC782A2DF2A\3927DA4077D07205F763682F3A76C9019B4F=141719984273434721125159179695007657\6924665583897286211449993265333367109221=3221B4FBBF6D101074EC14AFAC2D4F7\EFAC4CF9FEC1ED11BAE336D27D527665
Точка
=376991675009019385568410572935126561\08841345190491942619304532412743720999759=5358F8FFB38F7C09ABC782A2DF2A\3927DA4077D07205F763682F3A76C9019B4F=141719984273434721125159179695007657\6924665583897286211449993265333367109221=3221B4FBBF6D101074EC14AFAC2D4F7\EFAC4CF9FEC1ED11BAE336D27D527665
Точка
=2970098091581795287437120498393825699\0422752107994319651632687982059210933395=41AA28D2F1AB148280CD9ED56FED\A41974053554A42767B83AD043FD39DC0493=3284253527868466347709466532251708450\6804721032454543268132854556539274060910=489С375А9941А3049ЕЗЗВ34361DD\204172AD98C3E5916DE27695D22A61FAE46E
Тогда параметр
=2970098091581795287437120498393825699\0422752107994319651632687982059210933395=41AA28D2F1AB148280CD9ED56FED\A41974053554A42767B83AD043FD39DC0493
Поскольку выполнено равенство , то цифровая подпись принимается.