Geekly Articles each Day
📜 ⬆️ ⬇️

EDS of CIS countries in Python

image
Hello!
I already wrote on Habré about my implementation of block ciphers of the CIS countries. Another free week was issued, as a result of which digital signature algorithms were added to the symmetric standards: Russian GOST 34.10-2012, Ukrainian DSTU 4145-2002 and Belarusian STB 34.101.45-2013.
All three algorithms are based on elliptic curves . But the implementation of each of the standards has its own subtleties, which I want to briefly describe in this article.


GOST 34.10-2012


So, we begin with the Russian standard. It's all quite simple, the text of the standard spelled out all the necessary and illustrative examples. The algorithm works with a group of points of an elliptic curve (EC) over a field of a large prime number p . It would not be superfluous to recall that EC over a finite simple field is a set of points, described by the Weierstrass equation:

Accordingly, when using the algorithm, it is first necessary to determine the parameters of the EC, namely, choose the numbers a, b, n and the base point P , with an order equal to a large prime number q . This means that if you multiply a point by numbers smaller than q , then each time you get completely different points.
After selecting the parameters, you can start generating the secret-public key pair.
The secret key d is a random large number satisfying the inequality 0 <d <q .
The public key is the point of an elliptic curve Q calculated as Q = d * P.

The process of forming a digital signature is performed according to the following algorithm:
  1. Calculate the message hash M: H = h (M);
  2. Calculate the integer α, the binary representation of which is H;
  3. Define e = α mod q, if e = 0, set e = 1;
  4. Generate a random number k satisfying the condition 0 <k <q;
  5. Calculate the point of an elliptic curve C = k * P;
  6. Determine r = x C mod q, where x C is the x-coordinate of point C. If r = 0, then go back to step 4;
  7. Calculate the value s = (rd + ke) mod q. If s = 0, then go back to step 4;
  8. Return the value of r || s as a digital signature.

To verify the signature, follow these steps:
  1. According to the received signature, restore the numbers r and s. If the inequalities 0 <r <q and 0 <s <q are not satisfied, then return “the signature is not true”;
  2. Calculate the message hash M: H = h (M);
  3. Calculate the integer α, the binary representation of which is H;
  4. Define e = α mod q, if e = 0, set e = 1;
  5. Calculate v = e -1 mod q;
  6. Calculate the values ​​of z1 = s * v mod q and z2 = -r * v mod q;
  7. Calculate the point of an elliptic curve C = z1 * G + z2 * Q;
  8. Determine R = x c mod q, where x c is the x-coordinate of point C;
  9. If R = r, then the signature is correct. Otherwise, the signature is not accepted.

To test the algorithm, you can use examples from the text of the standard.
An example of using GOST:
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)


We are convinced that all the results coincided with the examples given and move on to the following standard.
')

STB 34.101.45-2013


The Belarusian standard is very similar to GOST. The elliptic curve and base point are determined by the parameters a, b, n, P and q .
The d key is used as the private key. While the public key is the point Q = d * P.

The following steps are taken to generate a signature:
  1. Set H ← ℎ (H).
  2. Generate k ← {1, 2, ..., q - 1}.
  3. Install R ← kP.
  4. Set S 0 ← belt-hash (OID (ℎ) | R | 2l ‖ H) | l .
  5. Set S 1 ← | (k - H - (S 0 + 2 l ) d) mod q | 2l .
  6. Install S ← S 0 ‖ S 1 .
  7. Return S.

The signature verification procedure is as follows:
  1. Present S as S = S 0 ‖ S 1 , where S 0 ∈ {0, 1} l , S 1 ∈ {0, 1} 2l .
  2. If S 1 > q, then return NO.
  3. Set H ← ℎ (X).
  4. Set R ← (︀ (S 1 + H) mod q) ︀P + (S 0 + 2 l ) Q.
  5. If R = O, then return NO.
  6. Set t ← | belt-hash (OID (ℎ) ‖ | R | 2l ‖ H) | l .
  7. If S 0 ! = T, then return NO.
  8. Return YES.

Where l is the level of durability in bits (for circuits on Elliptic curves, this indicator is approximately equal to half the key length).
H is a hash function.
OID - identifier of the hashing algorithm used. When belt-hash is used, this value is always 0x 06092A7000020022651F51.
| R | l - the first l bits of the number R.
|| - concatenation of two bit sequences.
As you can see, the standard strictly states the use of the hash function belt-hash, without which it will not be possible to verify the correctness of the implemented algorithm.
Fortunately, the function is based on the Belt block encryption standard of the Republic of Belarus, whose implementation in Python can be found here . Having finished the hashing algorithm, you can start implementing the EDS itself. However, this should take into account another feature of the standard STB 34.101.45-2013. All the numbers in the examples are given in little-endian notation, and in order for the results to converge with those given in the standard, you need to translate them to big-endian.
Checking examples from the standard
 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)


go to DSTU 4145-2002.

DSTU 4145-2002


Unlike the two previous standards, DSTU 4145-2002 is based on elliptic curves over fields of characteristic 2. This means that completely different mathematics works for them. The main difference is that arithmetic operations are performed not on numbers, but on polynomials. The standard provides two options for the implementation of mathematical operations: in a polynomial basis and in an optimal normal basis. I implemented the first option.
The algorithm is defined by the following parameters:
A, B - coefficients of the EK equation image
k, m is the number of members and the highest power of the main polynomial, modulo which all arithmetic operations are performed. For example, k = 5, m = 5 defines the following polynomial: x ^ 5 + x ^ 3 + x ^ 2 + x + 1 .
P - Base point of order n .
The key pair consists of the secret key d and the public key Q = -d * P.

The signature generation procedure is as follows:
  1. We generate number e, such that 1 <e <n.
  2. Calculate the point R = e * P.
  3. We calculate the polynomial f_r = R_x * h (M), where R_x is the x-coordinate of the point R; h (M) - the hash from the message M.
  4. We represent f_r as r.
  5. We calculate the number s = (e + d * r) mod n.
  6. We return a pair (r, s) as a signature.


To verify the signature:
  1. We represent the signature as a pair of (r, s).
  2. Calculate the point of EC R = s * P + r * Q.
  3. We calculate the element of the main field f_r = h (M) * R_x.
  4. We represent f_r as r1.
  5. If the equality r1 = r holds, the signature is true.

We start test examples
 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)


and get the expected results.

PS


Oh yeah, the source. Python source codes for all the above algorithms can be found on GitHub .

Links


  1. The text of the standard GOST 34.10-2012 .
  2. The text of the standard STB 34.101.45-2013 .
  3. The text of the standard DSTU 4145-2002 (in Ukrainian, contains an error in the formulas describing the addition of points of EC).

Source: https://habr.com/ru/post/301048/

More articles:


All Articles