ЕЦП країн СНД на Python

image
Привіт!
Я вже писав на Хабре про своєї реалізації блокових шифрів країн СНД. Видалася ще одна вільна тиждень в результаті чого до симетричним стандартам додалися алгоритми електронного цифрового підпису: російський ГОСТ 34.10-2012, український ДСТУ 4145-2002 і білоруський СТБ 34.101.45-2013.
Всі три алгоритми засновані на еліптичних кривих. Але реалізація кожного із стандартів має свої тонкощі, про яких я хочу коротко розповісти в цій статті.


ГОСТ 34.10-2012

Отже, починаємо з російського стандарту. Тут все досить просто, у тексті стандарту прописано все необхідне і наведені наочні приклади. Алгоритм працює з групою точок еліптичної кривої(ЕК) над полем великого простого числа p. Не зайвим буде нагадати, що ЕК над кінцевим простим полем – це набір точок, описывающихся рівнянням Вейерштрассе:

Відповідно при використанні алгоритму спершу необхідно визначитися з параметрами ЕК, а саме вибрати числа a, b, n і базову точку P, з порядком рівним великим простого числа q. Це означає, що якщо множити точку на числа менші, ніж q, то кожен раз будуть виходити абсолютно різні точки.
Після вибору параметрів можна приступати до генерації пари секретний-публічний ключ.
Секретний ключ d – велике випадкове число задовольняє нерівності 0<d<q.
Публічний ключ – точка еліптичної кривої Q оцінка Q = d*P.

Процес формування ЕЦП виконується за наступним алгоритмом:
  1. Обчислити хеш повідомлення M: H=h(M);
  2. Обчислити ціле число α, двійковим поданням якого є H;
  3. Визначити e=α mod q, якщо e=0, вказати e=1;
  4. Згенерувати випадкове число k, що задовольняє умові 0<k<q;
  5. Обчислити точку еліптичної кривої C=k*P;
  6. Визначити r = xC mod q, де xC — x-координата точки C. Якщо r=0, то повернутися до кроку 4;
  7. Обчислити значення s = (rd+ke) mod q. Якщо s=0, то повернутися до кроку 4;
  8. Повернути значення r||s в якості цифрового підпису.
Для перевірки підпису потрібно виконати наступні кроки:
  1. За отриманою підпису відновити числа r і s. Якщо не виконані нерівності 0<r<q 0<s<q, тоді повернути «підпис не вірна»;
  2. Обчислити хеш повідомлення M: H=h(M);
  3. Обчислити ціле число α, двійковим поданням якого є H;
  4. Визначити e=α mod q, якщо e=0, вказати e=1;
  5. Обчислити v = e-1 mod q;
  6. Обчислити значення z1 = s*v mod q і z2 = -r*v mod q;
  7. Обчислити точку еліптичної кривої C = z1*G + z2*Q;
  8. Визначити R = xc mod q, де xc — x-координата точки C;
  9. Якщо R=r, то підпис вірний. В іншому випадку підпис не приймається.
Для перевірки алгоритму можна скористатися прикладами з тексту стандарту.
Приклад використання ГОСТ:
def test_gost_sign():
p = 57896044618658097711785492504343953926634992332820282019728792003956564821041
a = 7
b = 43308876546767276905765904595650931995942111794451039583252968842033849580414
x = 2
y = 4018974056539037503335449422937059775635739389905545080690979365213431566280
q = 57896044618658097711785492504343953927082934583725450622380973592137631069619
gost = DSGOST(p, a, b, q, x, y)
key = 55441196065363246126355624130324183196576709222340016572108097750006097525544
message = 20798893674476452017134061561508270130637142515379653289952617252661468872421
k = 53854137677348463731403841147996619241504003434302020712960838528893196233395
sign = gost.sign(message, key, k)

def test_gost_verify():
p = 57896044618658097711785492504343953926634992332820282019728792003956564821041
a = 7
b = 43308876546767276905765904595650931995942111794451039583252968842033849580414
x = 2
y = 4018974056539037503335449422937059775635739389905545080690979365213431566280
q = 57896044618658097711785492504343953927082934583725450622380973592137631069619
gost = DSGOST(p, a, b, q, x, y)
message = 20798893674476452017134061561508270130637142515379653289952617252661468872421
sign = (29700980915817952874371204983938256990422752107994319651632687982059210933395,
574973400270084654178925310019147038455227042649098563933718999175515839552)
q_x = 57520216126176808443631405023338071176630104906313632182896741342206604859403
q_y = 17614944419213781543809391949654080031942662045363639260709847859438286763994
public_key = ECPoint(q_x, q_y, a, b, p)
is_signed = gost.verify(message, sign, public_key)


Переконуємося, що всі результати збіглися з наведеними прикладами і переходимо до наступного стандарту.

СТБ 34.101.45-2013

Білоруський стандарт дуже схожий на ГОСТ. Еліптична крива і базова точка визначаються параметрами a, b, n, P і q.
Як закритого ключа використовується число d. У той час як відкритим ключем служить крапка Q = d*P.

Для формування підпису виконуються наступні кроки:
  1. Встановити H ← ℎ(H).
  2. Виробити k ← {1, 2,..., q − 1}.
  3. Встановити R ← kP.
  4. Встановити S0 ← |belt-hash(OID(ℎ) ‖ |R|2l ‖ H)|l.
  5. Встановити S1 ← |(k − H − (S0 + 2l)d) mod q|2l.
  6. Встановити S ← S0 ‖ S1.
  7. Повернути S.
Процедура перевірки підпису виглядає так:
  1. Уявити S у вигляді S = S0 ‖ S1, де S0 ∈ {0, 1}l, S1 ∈ {0, 1}2l.
  2. Якщо S1 > q, то повернути НЕМАЄ.
  3. Встановити H ← ℎ(X).
  4. Встановити R ← (︀(S1 + H) mod q)︀P + (S0 + 2l)Q.
  5. Якщо R = O, то повернути НЕМАЄ.
  6. Встановити t ← |belt-hash(OID(ℎ) ‖ |R|2l ‖ H)|l.
  7. Якщо S0 != t, то повернути НЕМАЄ.
  8. Повернути ТАК.
Де l – рівень стійкості в бітах (для схем на Еліптичних кривих цей показник дорівнює приблизно половині довжини ключа).
H – хеш-функція.
OID – ідентифікатор використовуваного алгоритму хешування. При використанні belt-hash це значення завжди дорівнює 0x 06092A7000020022651F51.
|R|l — перші l біт числа R.
|| — конкатенація двох бітових послідовностей.
Як бачите в стандарті жорстко прописано використання хеш-функції belt-hash, без якої не можна буде перевірити правильність реалізованого алгоритму.
Благо в основі функції лежить стандарт блочного шифрування Республіки Білорусь Belt, реалізацію якого на Python можна знайти тут. Допилив алгоритм хешування можна приступати до реалізації самої ЕЦП. Однак при цьому слід врахувати ще одну особливість стандарту СТБ 34.101.45-2013. Всі числа в прикладах наведено в little-endian нотації, і для того щоб результати зійшлися з наведеними в стандарті необхідно перевести їх до big-endian.
Перевіривши приклади з стандарту
def test_stb_sign():
p = 0x43FFFFFFFFFFFFFFFFFFFFFFFFFFFFffffffffffffffffffffffffffffffffff
p = reverse(p)
a = 0x40FFFFFFFFFFFFFFFFFFFFFFFFFFFFffffffffffffffffffffffffffffffffff
a = reverse(a)
b = 0xF1039CD66B7D2EB253928B976950F54cbefbd8e4ab3ac1d2eda8f315156cce77
b = reverse(b)
q = 0x07663D2699BF5A7EFC4DFB0DD68E5Cd9ffffffffffffffffffffffffffffffff
q = reverse(q)
y = 0x936A510418CF291E52F608C4663991785d83d651a3c9e45c9fd616fb3cfcf76b
y = reverse(y)
d = 0x1F66B5B84B7339674533F0329C74F21834281fed0732429e0c79235fc273e269
d = reverse(d)
stb = STB(p, a, b, q, y, 128)
message = 0xB194BAC80A08F53B366D008E58
k = 0x4C0E74B2CD5811AD21F23DE7E0FA742c3ed6ec483c461ce15c33a77aa308b7d2
k = reverse(k)
signature = stb.sign(message, d, k)

def test_stb_verify():
p = 0x43FFFFFFFFFFFFFFFFFFFFFFFFFFFFffffffffffffffffffffffffffffffffff
p = reverse(p)
a = 0x40FFFFFFFFFFFFFFFFFFFFFFFFFFFFffffffffffffffffffffffffffffffffff
a = reverse(a)
b = 0xF1039CD66B7D2EB253928B976950F54cbefbd8e4ab3ac1d2eda8f315156cce77
b = reverse(b)
q = 0x07663D2699BF5A7EFC4DFB0DD68E5Cd9ffffffffffffffffffffffffffffffff
q = reverse(q)
y = 0x936A510418CF291E52F608C4663991785d83d651a3c9e45c9fd616fb3cfcf76b
y = reverse(y)
message = 0xB194BAC80A08F53B366D008E584A5De48504fa9d1bb6c7ac252e72c202fdce0d5be3d61217b96181fe6786ad716b890b
q_x = 0xBD1A5650179D79E03FCEE49D4C2BD5ddf54ce46d0cf11e4ff87bf7a890857fd0
q_x = reverse(q_x)
q_y = 0x7AC6A60361E8C8173491686D461B2826190c2eda5909054a9ab84d2ab9d99a90
q_y = reverse(q_y)
s = (0x47A63C8B9C936E94B5FAB3D9CBD78366, 0x290F3210E163EEC8DB4E921E8479D4138f112cc23e6dce65ec5ff21df4231c28)
pub_key = (q_x, q_y)
stb = STB(p, a, b, q, y, 128)
is_signed = stb.verify(message, pub_key, s)


переходимо до ДСТУ 4145-2002.

ДСТУ 4145 – 2002

На відміну від двох попередніх стандартів, ДСТУ 4145-2002 ґрунтується на еліптичних кривих над полями характеристики 2. Це означає, що для них працює зовсім інша математика. Основна відмінність полягає в тому, що арифметичні дії виконуються над числами, а над многочленами. У стандарті наведено два варіанти реалізації математичних операції: в поліноміальному базисі і в оптимальному нормальному базисі. Я реалізував перший варіант.
Алгоритм задається наступними параметрами:
A, B – коефіцієнти рівняння ЕК image
k, m – кількість членів і старша ступінь основного многочлена, по модулю якого виконуються всі арифметичні операції. Приміром, k=5, m=5 задає такий многочлен: x^5+x^3+x^2+x+1.
P – Базова точка порядку n.
Пара ключів складається з секретного ключа d і публічного ключа Q = -d*P.

Процедура формування підпису наступна:
  1. Генеруємо число e, таке що 1<e<n.
  2. Обчислюємо точку R = e * P.
  3. Обчислюємо многочлен f_r = R_x * h(M), де R_x – x-координата точки R; h(M) – хеш від підписуваного повідомлення M.
  4. Представляємо f_r як число r.
  5. Обчислюємо число s = (e + d * r) mod n.
  6. Повертаємо пару (r, s) як підпис.


Для перевірки підпису:
  1. Представляємо підпис як пару числі (r, s).
  2. Обчислюємо точку ЕК R = s * P + r * Q.
  3. Обчислюємо елемент основного поля f_r = h(M) * R_x.
  4. Представляємо f_r як число r1.
  5. Якщо виконується рівність r1 = r, підпис вірний
Запускаємо тестові приклади
def test_dstu_sign():
dstu_x = 0x72D867F93A93AC27DF9FF01AFFE74885c8c540420
dstu_y = 0x0224A9C3947852B97C5599D5F4AB81122adc3fd9b
dstu_a = 0x1
dstu_b = 0x5FF6108462A2DC8210AB403925E638a19c1455d21
dstu_p = 0x800000000000000000000000000000000000000c9
dstu_n = 0x400000000000000000002BEC12BE2262d39bcf14d
dstu = DSTU4145(dstu_p, dstu_a, dstu_b, dstu_x, dstu_y, dstu_n)
message = 0x03A2EB95B7180166DDF73532EEB76Edaef52247ff
dstu_d = 0x183F60FDF7951FF47D67193F8D073790c1c9b5a3e
dstu_e = 0x1025E40BD97DB012B7A1D79DE8E12932d247f61c6
signature = dstu.sign(message, dstu_d, dstu_e)

def test_dstu_verify():
dstu_x = 0x72D867F93A93AC27DF9FF01AFFE74885c8c540420
dstu_y = 0x0224A9C3947852B97C5599D5F4AB81122adc3fd9b
dstu_a = 0x1
dstu_b = 0x5FF6108462A2DC8210AB403925E638a19c1455d21
dstu_p = 0x800000000000000000000000000000000000000c9
dstu_n = 0x400000000000000000002BEC12BE2262d39bcf14d
dstu = DSTU4145(dstu_p, dstu_a, dstu_b, dstu_x, dstu_y, dstu_n)
message = 0x03A2EB95B7180166DDF73532EEB76Edaef52247ff
dstu_d = 0x183F60FDF7951FF47D67193F8D073790c1c9b5a3e
dstu_Q = dstu.gen_keys(dstu_d)[1]
signature = (0x274EA2C0CAA014A0D80A424F59ADE7a93068d08a7, 0x2100D86957331832B8E8C230F5BD6A332b3615aca)
is_signed = dstu.verify(message, signature, dstu_Q)


і отримуємо очікувані результати.

p.s.

Ах так, исходники. Вихідні коди на Python всіх описаних вище алгоритмів ви можете знайти на GitHub.

Посилання

  1. Текст стандарту ГОСТ 34.10-2012.
  2. Текст стандарту СТБ 34.101.45-2013.
  3. Текст стандарту ДСТУ 4145 – 2002(українською мовою, містить помилки у формулах, що описують додавання точок ЕК).
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.