WikiSort.ru - Не сортированное

Параметры схемы цифровой подписи

• простое число ${\displaystyle p}$  — модуль эллиптической кривой такой, что ${\displaystyle p>2^{255}}$
• эллиптическая кривая ${\displaystyle E}$ задаётся своим инвариантом ${\displaystyle J(E)}$ или коэффициентами ${\displaystyle a,b\in F_{p}}$ , где ${\displaystyle F_{p}}$  — конечное поле из p элементов. ${\displaystyle J(E)}$ связан с коэффициентами ${\displaystyle a}$ и ${\displaystyle b}$ следующим образом

${\displaystyle J(E)=1728{\frac {4a^{3}}{4a^{3}+27b^{2}}}{\pmod {p}}}$ , причём ${\displaystyle 4a^{3}+27b^{2}\not \equiv 0{\pmod {p}}}$ .

• целое число ${\displaystyle m}$  — порядок группы точек эллиптической кривой, ${\displaystyle m}$ должно быть отлично от ${\displaystyle p}$
• простое число ${\displaystyle q}$ , порядок некоторой циклической подгруппы группы точек эллиптической кривой, то есть выполняется ${\displaystyle m=nq}$ , для некоторого ${\displaystyle n\in \mathbb {N} }$ . Также ${\displaystyle q}$ лежит в пределах ${\displaystyle 2^{254}<q<2^{256}}$ .
• точка ${\displaystyle P=(x_{P},\;y_{P})}$ эллиптической кривой ${\displaystyle E}$ , являющаяся генератором подгруппы порядка ${\displaystyle q}$ , то есть ${\displaystyle q\cdot P=\mathbf {0} }$ и ${\displaystyle k\cdot P\neq \mathbf {0} }$ для всех k = 1, 2, …, q-1, где ${\displaystyle \mathbf {0} }$  — нейтральный элемент группы точек эллиптической кривой E.
• ${\displaystyle h(M)}$  — хеш-функция (ГОСТ Р 34.11-2012), которая отображает сообщения M в двоичные векторы длины 256 бит.

Каждый пользователь цифровой подписи имеет личные ключи:

• ключ шифрования ${\displaystyle d}$  — целое число, лежащее в пределах ${\displaystyle 0<d<q}$ .
• ключ расшифрования ${\displaystyle Q=(x_{Q},\;y_{Q})}$ , вычисляемый как ${\displaystyle Q=d\cdot P}$ .

Дополнительные требования:

• ${\displaystyle p^{t}\neq 1{\pmod {q}}}$ , ${\displaystyle \forall t=1..B}$ , где ${\displaystyle B\geq 31}$
• ${\displaystyle J(E)\neq 0}$ и ${\displaystyle J(E)\neq 1728}$

Двоичные векторы

Между двоичными векторами длины 256 ${\displaystyle {\bar {h}}=(\alpha _{255},...,\alpha _{0})}$ и целыми числами ${\displaystyle z\leq 2^{256}}$ ставится взаимно-однозначное соответствие по следующему правилу ${\displaystyle z=\sum _{i=0}^{255}\alpha _{i}2^{i}}$ . Здесь ${\displaystyle \alpha _{i}}$ либо равно 0, либо равно 1. Другими словами, ${\displaystyle {\bar {h}}}$  — это представление числа z в двоичной системе счисления.

Результатом операции конкатенации двух векторов ${\displaystyle {\bar {h_{1}}}=(\alpha _{255},...,\alpha _{0})}$ и ${\displaystyle {\bar {h_{2}}}=(\beta _{255},...,\beta _{0})}$ называется вектор длины 512 ${\displaystyle ({\bar {h_{1}}}|{\bar {h_{2}}})=(\alpha _{255},...,\alpha _{0},\beta _{255},...,\beta _{0})}$ . Обратная операция — операция разбиения одного вектора длины 512 на два вектора длины 256.

Формирование цифровой подписи

Блок-схемы:

• 
  Формирование цифровой подписи
• 
  Проверка цифровой подписи

1. Вычисление хеш-функции от сообщения М: ${\displaystyle {\bar {h}}=h(M)}$
2. Вычисление ${\displaystyle e=z\,{\bmod {\,}}q}$ , и если ${\displaystyle e=0}$ , положить ${\displaystyle e=1}$ . Где ${\displaystyle z}$  — целое число, соответствующее ${\displaystyle {\bar {h}}.}$
3. Генерация случайного числа ${\displaystyle k}$ такого, что ${\displaystyle 0<k<q.}$
4. Вычисление точки эллиптической кривой ${\displaystyle C=kP}$ , и по ней нахождение ${\displaystyle r=x_{c}\,{\bmod {\,}}q,}$ где ${\displaystyle x_{c}}$  — это координата ${\displaystyle x}$ точки ${\displaystyle C.}$ Если ${\displaystyle r=0}$ , возвращаемся к предыдущему шагу.
5. Нахождение ${\displaystyle s=(rd+ke)\,{\bmod {\,}}q}$ . Если ${\displaystyle s=0}$ , возвращаемся к шагу 3.
6. Формирование цифровой подписи ${\displaystyle \xi =({\bar {r}}|{\bar {s}})}$ , где ${\displaystyle {\bar {r}}}$ и ${\displaystyle {\bar {s}}}$  — векторы, соответствующие ${\displaystyle r}$ и ${\displaystyle s}$ .

Проверка цифровой подписи

1. Вычисление по цифровой подписи ${\displaystyle \xi }$ чисел ${\displaystyle r}$ и ${\displaystyle s}$ , учитывая, что ${\displaystyle \xi =({\bar {r}}|{\bar {s}})}$ , где ${\displaystyle r}$ и ${\displaystyle s}$  — числа, соответствующие векторам ${\displaystyle {\bar {r}}}$ и ${\displaystyle {\bar {s}}}$ . Если хотя бы одно из неравенств ${\displaystyle r<q}$ и ${\displaystyle s<q}$ неверно, то подпись неправильная.
2. Вычисление хеш-функции от сообщения М: ${\displaystyle {\bar {h}}=h(M).}$
3. Вычисление ${\displaystyle e=z\,{\bmod {\,}}q}$ , и если ${\displaystyle e=0}$ , положить ${\displaystyle e=1}$ . Где ${\displaystyle z}$  — целое число соответствующее ${\displaystyle {\bar {h}}.}$
4. Вычисление ${\displaystyle \nu =e^{-1}\,{\bmod {\,}}q.}$
5. Вычисление ${\displaystyle z_{1}=s\nu \,{\bmod {\,}}q}$ и ${\displaystyle z_{2}=-r\nu \,{\bmod {\,}}q.}$
6. Вычисление точки эллиптической кривой ${\displaystyle C=z_{1}P+z_{2}Q}$ . И определение ${\displaystyle R=x_{c}\,{\bmod {\,}}q}$ , где ${\displaystyle x_{c}}$  — координата ${\displaystyle x}$ точки ${\displaystyle C.}$
7. В случае равенства ${\displaystyle R=r}$ подпись правильная, иначе — неправильная.