SFLASH (SFLASH)

SFLASH — асимметричный алгоритм цифровой подписи рекомендованный проектом NESSIE European в 2003 году. SFLASH основан на Matsumoto-Imai(MI) схеме, так же называемой C*. Алгоритм принадлежит к семейству многомерных схем с открытым ключом, то есть каждая подпись и каждый хеш сообщения представлен элементами конечного поля K. SFLASH был разработан для очень специфичных приложений, где затраты на классические алгоритмы (RSA, Elliptic Curves, DSA и другие) становятся чрезвычайно высокими: они очень медленные и имеют большой размер подписи. Таким образом SFLASH был создан, чтобы удовлетворять потребностям дешевых смарт-карт.

SFLASH гораздо быстрее и проще, чем RSA, как и в создании, так и в проверке (верификации) подписи.^{[источник не указан 3520 дней]}

Введение

Во всей статье будут использоваться следующие обозначения:

$\|$ — определяет оператор конкатенации.
$[\lambda ]_{r\rightarrow s}$ — оператор, который определяется следующим образом: $[\lambda ]_{r\rightarrow s}=(\lambda _{r},\lambda _{r+1},...,\lambda _{s-1},\lambda _{s})$ , где $\lambda =(\lambda _{1},...,\lambda _{m})$ , а целые числа r и s должны удовлетворять: $0\leq r\leq s\leq m$ .

Параметры алгоритма

Алгоритм SFLASH использует два определенных поля:

$K=F_{128}$ определяется как $K=F_{2}[X]/(X^{7}+X+1)$ . Определим $\pi$ как биекцию между $\{0,1\}^{7}$ и K как: $\forall b=(b_{0},...,b_{6})\in \{0,1\}^{7},\pi (b)=(b_{6}X^{6}+...+b_{1}X+b_{0})\mod X^{7}+X+1$
$\Phi =K[X]/(x^{67}+X^{5}+X^{2}+X+1)$ . Определим $\varphi$ как биекцию между $K^{67}$ и $\Phi$ как: $\forall \omega =(\omega _{0},...,\omega _{66})\in K^{67},\varphi (\omega )=(\omega _{66}X^{66}+...+\omega _{1}X+\omega _{0})\mod X^{67}+X^{5}+X^{2}+X+1$
$\Delta$ — 80 битная скрытая строка.

Так же алгоритм SFLASH использует две афинные биекции s и t из $K^{67}$ в $K^{67}$ . Каждое из которых составляет скрытые линейные $S_{L},T_{L}$ (матрицы 67*67) и постоянные $S_{C},T_{C}$ (столбец 67*1) соответственно.

Открытые параметры

Открытый ключ заключается в функции G из $K^{67}$ в $K^{56}$ определенную как: $G(X)=[t(\varphi ^{-1}(F(\varphi (s(X)))))]_{0\rightarrow 391}$

F — это функция из $\Phi$ в $\Phi$ определенная как $\forall A\in \Phi ,F(A)=A^{128^{33}+1}$

Формирование ключа

Обозначим next_7bit_random_string строку из 7 бит, которая формируется путём вызова CSPRBG(Cryptographically Secure PseudoRandom Bit Generator) 7 раз. Сначала мы получаем первый бит строки, потом второй и так до седьмого.

1)Генерируем $S_{L}$: Для генерации инвертированной 67x67 матрицы $S_{L}$ могут быть использованы два метода:

Будем заполнять матрицу по одному элементу до тех пор, пока не заполним всю матрицу:

for i=0 to 66 
    for j=0 to 66 
        S_L[i,j]=pi(next_7bit_random_string)

Используем LU-разложение, где $L_{S}$ — нижняя треугольная матрица 67x67, а $U_{S}$ — верхняя треугольная матрица 67x67. После нахождения матриц $L_{S}$ и $U_{S}$ , определяем $S_{L}=L_{S}\times U_{S}.$ :

for i=0 to 66
    for j=0 to 66
    {
        if (i<j) then
                 {U_S[i,j]=pi(next_7bit_random_string); L_S[i,j]=0;};
        if (i>j) then
                 {L_S[i,j]=pi(next_7bit_random_string); U_S[i,j]=0;};
        if (i=j) then
                 {repeat (z=next_7bit_random_string)
                         until z!=(0,0,0,0,0,0,0);
                 U_S[i,j]=pi(z);
                 L_S[i,j]=1;};
    };

2)Генерируем $S_{C}$: Используем CSPRBG для нахождения новых 67 элементов K(от верхней к нижней части столбца матрицы). Каждый элемент K находится с помощью функции:

$\pi$ (next_7bit_random_string)

3)Генерируем $T_{L}$: Аналогично как и матрицу $S_{L}$ .
4)Генерируем $T_{C}$: Аналогично как и столбец $S_{C}$ .
5)Генерируем $\Delta$: С помощью CSPRBG(Cryptographically Secure PseudoRandom Bit Generator) генерируем 80 случайных бит.