SFLASH

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

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

Введение

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

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

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

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

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

Так же алгоритм SFLASH использует две афинные биекции s и t из [math]\displaystyle{ K^{67} }[/math] в [math]\displaystyle{ K^{67} }[/math]. Каждое из которых составляет скрытые линейные [math]\displaystyle{ S_L, T_L }[/math] (матрицы 67*67) и постоянные [math]\displaystyle{ S_C, T_C }[/math](столбец 67*1) соответственно.

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

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

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

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

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

1)Генерируем [math]\displaystyle{ S_L }[/math]: Для генерации инвертированной 67x67 матрицы [math]\displaystyle{ S_L }[/math] могут быть использованы два метода:

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

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

Используем LU-разложение, где [math]\displaystyle{ L_S }[/math] — нижняя треугольная матрица 67x67, а [math]\displaystyle{ U_S }[/math] — верхняя треугольная матрица 67x67. После нахождения матриц [math]\displaystyle{ L_S }[/math] и [math]\displaystyle{ U_S }[/math], определяем [math]\displaystyle{ S_L=L_S\times U_S. }[/math] :

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)Генерируем [math]\displaystyle{ S_C }[/math]: Используем CSPRBG для нахождения новых 67 элементов K(от верхней к нижней части столбца матрицы). Каждый элемент K находится с помощью функции:

[math]\displaystyle{ \pi }[/math](next_7bit_random_string)

3)Генерируем [math]\displaystyle{ T_L }[/math]: Аналогично как и матрицу [math]\displaystyle{ S_L }[/math].
4)Генерируем [math]\displaystyle{ T_C }[/math]: Аналогично как и столбец [math]\displaystyle{ S_C }[/math].
5)Генерируем [math]\displaystyle{ \Delta }[/math]: С помощью CSPRBG(Cryptographically Secure PseudoRandom Bit Generator) генерируем 80 случайных бит.

Создание подписи

Пусть M — это наше сообщение, для которого мы хотим найти подпись S. Создание подписи S имеет следующий алгоритм:

1) Пусть [math]\displaystyle{ M_0, M_1, M_2, M_3 }[/math] — это строки определяющиеся с помощью алгоритма криптографического хеширования SHA-1:

[math]\displaystyle{ M_0=SHA-1(M) }[/math],

[math]\displaystyle{ M_1=SHA-1(M_0\|0x00) }[/math],

[math]\displaystyle{ M_2=SHA-1(M_0\|0x01) }[/math],

[math]\displaystyle{ M_3=SHA-1(M_0\|0x02) }[/math],

2) Найдем V — 392 битную строку как:

[math]\displaystyle{ V=[M_1]_{0\rightarrow159}\|[M_2]_{0\rightarrow159}\|[M_3]_{0\rightarrow71} }[/math]

3) Найдем W — 77 битную строку как:

[math]\displaystyle{ W=[SHA-1(V\|\Delta)]_{0\rightarrow76} }[/math]

4) Найдем Y — строку из 56 элементов K как:

[math]\displaystyle{ Y=(\pi([V]_{0\rightarrow6}),\pi([V]_{7\rightarrow13}),...,\pi([V]_{385\rightarrow391})) }[/math]

5) Найдем R — строку из 11 элементов K как:

[math]\displaystyle{ R=(\pi([W]_{0\rightarrow6}),\pi([W]_{7\rightarrow13}),...,\pi([W]_{70\rightarrow76})) }[/math]

6) Найдем B — элемент [math]\displaystyle{ \Phi }[/math] как:

[math]\displaystyle{ B=\varphi(t^{-1}(Y\|R)) }[/math]

7) Найдем A — элемент [math]\displaystyle{ \Phi }[/math] как:

[math]\displaystyle{ A=F^{-1}(B) }[/math], где F — функция из [math]\displaystyle{ \Phi }[/math] в [math]\displaystyle{ \Phi }[/math] определенная как: [math]\displaystyle{ \forall A\in\Phi, F(A)=A^{128^{33}+1} }[/math]

8) Найдем [math]\displaystyle{ X=(X_0,...,X_{66}) }[/math] — строка 67 элементов K:

[math]\displaystyle{ X=(X_0,...,X_{66})=s^{-1}(\varphi^{-1}(A)) }[/math]

9) Подпись S — 469 битная строка полученная как:

[math]\displaystyle{ S=\pi^{-1}(X_0)\|...\|\pi^{-1}(X_{66}) }[/math]

Проверка (верификация) подписи

Даны сообщение M (строка бит) и подпись S (256-битовая строка). Следующий алгоритм используется для определения валидности подписи S сообщения M:

1) Пусть [math]\displaystyle{ M_0, M_1, M_2, M_3 }[/math] — это строки определяющиеся с помощью алгоритма криптографического хеширования SHA-1:

[math]\displaystyle{ M_0=SHA-1(M) }[/math],

[math]\displaystyle{ M_1=SHA-1(M_0\|0x00) }[/math],

[math]\displaystyle{ M_2=SHA-1(M_0\|0x01) }[/math],

[math]\displaystyle{ M_3=SHA-1(M_0\|0x02) }[/math],

2) Найдем V — 392 битную строку как:

[math]\displaystyle{ V=[M_1]_{0\rightarrow159}\|[M_2]_{0\rightarrow159}\|[M_3]_{0\rightarrow71} }[/math]

3) Найдем Y — строку из 56 элементов K как:

[math]\displaystyle{ Y=(\pi([V]_{0\rightarrow6}),\pi([V]_{7\rightarrow13}),...,\pi([V]_{385\rightarrow391})) }[/math]

4) Найдем Y' — строку из 56 элементов K как:

[math]\displaystyle{ Y'=G(\pi([S]_{0\rightarrow6}),\pi([S]_{7\rightarrow13}),...,\pi([S]_{385\rightarrow391})) }[/math]

5) Сравниваем получившиеся строки Y и Y'. Если они равны, то подпись принимается, в противном случае — отклоняется.

Литература

«Nicolas T.Courtois, Louis Goubin and Jacques Patarin. SFLASHv3, a fast asymmetric signature scheme, 2003» Архивная копия от 13 июля 2007 на Wayback Machine, Спецификация алгоритма от разработчиков
«Vivien Dubois, Pierre-Alain Fouque, Adi Shamir and Jacques Stern, Practical Cryptanalysis of SFLASH» Архивная копия от 7 июня 2011 на Wayback Machine, описание действующих атак на SFLASH

Ссылки

Многомерная криптография (Multivariate cryptography)