Программная реализация LFSR
Программные реализации LFSR медленны и быстрее работают, если они написаны на ассемблере, а не на C. Одним из решений является использование параллельно 16 LFSR (или 32, в зависимости от длины слова вашего компьютера). В этой схеме используется массив слов, размер которого равен длине LFSR, а каждый бит слова массива относится к своему LFSR. При условии, что используются одинаковые многочлены обратной связи, это может дать заметный выигрыш производительности. Вообще, лучшим способом обновлять сдвиговые регистры является умножение текущего состояния на подходящие двоичные матрицы [901].
Схему обратной связи LFSRможно модифицировать. Получающийся генератор не будет криптографически более надежным, но он все еще будет обладать максимальным периодом, и его легче реализовать программно [1272]. Вместо использования для генерации нового крайнего левого бита битов отводной последовательности выполняется XOR каждого бита отводной последовательности с выходом генератора и замена его результатом этого действия, затем результат генератора становится новым крайним левым битом (см. Рис. 16-5). Иногда эту модификацию называют конфигурацией Галуа. На языке C это выглядит следующим образом:
#define mask 0x80000057
static unsigned long ShiftRegister=1;
void seed_LFSR (unsigned long seed)
{
if (seed == 0) /* во избежание беды */
seed = 1 ;
ShiftRegister = seed;
}
int modified_LFSR (void)
{
if (ShiftRegister & 0x00000001) {
ShiftRegister = (ShiftRegister ^ mask >> 1) | 0x8000000 ;
return 1;
} else {
ShiftRegister >>= 1;
return 0;
}
}
Рис. 16-5. LFSR Галуа.
Выигрыш состоит в том, что все XOR можно сделать за одну операцию. Эта схема также может быт распараллелена, а полиномы различных обратных связей могут быть различны. Такая конфигурация Галуа может дать выигрыш и при аппаратной реализации, особенно в виде СБИС. Вообще, при использовании аппаратуры, которая хорошо выполняет сдвиги применяйте конфигурацию Фиббоначи, если есть возможность использовать параллелизм, применяйте конфигурацию Галуа.
Дата добавления: 2021-01-26; просмотров: 377;