Как выполнить сложение по модулю 2^512?

Question

[Николай Ким]

Здравствуйте! Необходимо выполнить операцию сложения по модулю 2^512 для алгоритма хэширования "Стирибог", описываемого стандартом ГОСТ 34.11-2012. Складываются два 512-битных числа.

Я изучил найденные примеры реализаций этой операции, однако все они используют побитовый сдвиг, которого нет в используемом языке. Например, на JavaScript это выглядит так:

/* https://github.com/rudonick/crypto/blob/670cef467fc4ed19896baee6044710779a0843fb/gostR3411.js#L184 */
function add512(x, y) {
    var CF = 0, w0, w1;
    for (var i = 0; i < 16; i++) {
        w0 = (x[i] & 0xffff) + (y[i] & 0xffff) + (CF || 0);
        w1 = (x[i] >>> 16) + (y[i] >>> 16) + (w0 >>> 16);
        x[i] = (w0 & 0xffff) | (w1 << 16);
        CF = (w1 >>> 16);
    }
}

Или на C:

/* https://github.com/okazymyrov/stribog/blob/master/C/standard/stribog.c */
void AddModulo512(const unsigned char *a,const unsigned char *b,unsigned char *c)
{
  int i = 0, t = 0;

  for(i=63;i>=0;i--)
  {
    t = a[i] + b[i] + (t >> 8);
    c[i] = t & 0xFF;
  }
}

Вопрос:

• Есть ли способ выполнить такое сложение без операции побитового сдвига?
  
• Может быть, есть способ выразить побитовый сдвиг через другие операции?
  

Answer 1

[Армянское Радио]

Побитовый сдвиг вправо на 1 бит - это деление на 2 с отбрасыванием дробной части.
Побитовый сдвиг влево на 1 бит - это умножение на 2.

Про GMP знаете?

Answer 2

[jcmvbkbc]

Я изучил найденные примеры реализаций этой операции, однако все они используют побитовый сдвиг

Но зачем? Для определения было ли переполнение или нет? Но это можно определить просто сравнив результат сложения (беззнаковый) с любым из слагаемых: в случае переполнения сумма меньше любого слагаемого.
Т.е. имея массивы представляющие 32-битные части слагаемых и результата можно написать так (C):

void AddModulo512(const uint32_t *a,const uint32_t *b, uint32_t *c)
{
    unsigned carry = 0;
    unsigned i;
    for (i = 0; i < 16; ++i) {
        c[i] = a[i] + b[i] + carry;
        carry = a[i] + carry < carry || c[i] < b[i];
    }
}

Answer 3

[Sumor]

Неизвестно какие возможности вашего языка программирования.
Можно поизвращаться и переписать код на C без использования сдвига:

void AddModulo512(const unsigned char *a,const unsigned char *b,unsigned char *c)
{
	int i = 0, t = 0;
	unsigned char * pResult = (unsigned char *)(&t);
	unsigned char * pNext = pResult + 1;

	for(i=63;i>=0;i--)
	{
		t = a[i] + b[i] + *pNext;
		c[i] = *pResult;
	}
}

Смысл в том, что вы смотрите на число, как на массив из 4 байт. В старшем будет результат сложения двух байт, а во втором байте результат переполнения, который перейдёт на следующий байт результата.
Есть подозрение, что работа с указателями будет работать медленнее, чем работа с числами. Хотя всё зависит от компилятора.