Linear transformation in GOST R 34.12-2015
Hello!
I want to write an implementation of the recently adopted symmetric block encryption algorithm "Grasshopper". Now I'm studying the standard, trying to count each step of the algorithm "on my fingers" to confirm my understanding, and one point does not agree with the test example.
The text of GOST is presented on the website of TC 26: http://tc26.ru/standard/gost/GOST_R_3412-2015.pdf
About what speech?
The problem is in the transformation R, which converts a 16-byte array, or rather, in l, which receives only one byte of data from this array.
R(a[]) = l(a[]) & a[15] & a[14] & .. & a[1]
l(a[]) = 148 * a[15] + 32 * a[14] + ... + 1 * a[0]
The addition and multiplication operations are performed in the field F, and the constants are elements of the field in the sense indicated earlier.
As I understand it, it is about addition and multiplication modulo 255:
F end field GF(2) [x]∕p(x), where p (x) = x8 + x7 + x6 + x + 1 ∈ GF(2)[x]
What happened?
The appendix to the standard provides control examples for the transformations used in the encryption algorithm, including R.
R(00000000000000000000000000000100) = 94000000000000000000000000000001
R(94000000000000000000000000000001) = a5940000000000000000000000000000
Hexadecimal numbers are a representation of an array of 16 bytes, with the first (or rather, zero) element at the end of the string.
So, R(a[]) = l(a[]) & a[15] & ... & a[1]
In the first example, everything is well:
l(a[]) = 148 * a[1] = 148 = 0x94
R(a[]) = 0x94 & a[15..1] = 0x94, 0x00, ... 0x01
In the second case, everything is more complicated. If I understood correctly about addition and multiplication, voiced above, then:
l(a[]) = 148 * a[15] + 1 * a[0]
= (148 * 148) mod 255 + 1 * 1
= 229 + 1 = 230 = E6
R(a[]) = 0xE6, 0x94, 0x00, ...
Stop! In the control example, the highest bytes are 0xA5, 0x94!
What to do?
Actually, here is the question itself :)
In what place in my stream of consciousness did the error creep in and the result of the function in the l() second example was not what it should be, and what should I do to make it end ok?
Update №1
As it turned out, multiplication in the field is not "just multiply and take the remainder of the division", but a whole procedure described in detail in GF(256) finite field multiplication function in C#.
Moreover, the addition in the field GF(2^n) turned out to be a simple XOR.
The total for the second example was:
l(a[]) = (148 * 0x94) + (1 * 0x01) = 0x91 + 0x01 = 0x90
Which is still a long way from A5.
Here is the calculation code l():
byte[] l_mul = { 1, 148, 32, 133, 16, 194, 192, 1, 251, 1, 192, 194, 16, 133, 32, 148 };
public byte l (byte[] a) {
byte p = 0x00;
for (int i = 0; i < 16; i++) {
p ^= gf.Mul(l_mul[i], a[i]);
}
return p;
}
1 answers
In general, the problem was in the multiplication procedure in the field. If the result of multiplying the polynomials is too large and is not included in GF(256), then its we must divide by some irreducible polynomial.
In the example from Wikipedia and the previously mentioned question on Stack Overflow, the polynomial is used x^8 + x^4 + x^3 + x + 1 (100011011b = 0x11b or 0x1b), which is used in AES.
In the case of GOST from the definition of the field F, you must use another polynomial: x^8 + x^7 + x^6 + x + 1 = 0x1c3 or 0xc3. Now everything fits together with the control examples :)
public byte MulSlow (byte a, byte b) {
byte p = 0;
byte counter;
byte hi_bit_set;
for (counter = 0; counter < 8 && a != 0 && b != 0; counter++) {
if ((b & 1) != 0)
p ^= a;
hi_bit_set = (byte)(a & 0x80);
a <<= 1;
if (hi_bit_set != 0)
a ^= 0xc3; /* x^8 + x^7 + x^6 + x + 1 */
b >>= 1;
}
return p;
}