SFLASH

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

SFLASH гораздо быстрее и проще, чем RSA, как и в создании, так и в проверке (верификации) подписи.Шаблон:Нет АИ

Введение

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

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

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

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

1. $K=F_{128}$ определяется как $K=F_2[X]/(X^7+X+1)$. Определим $\pi$ как биекцию между $\{0,1{\}}^7$ и K как: $\mathrm{\forall }b=(b_0,\mathrm{...},b_6)\in \{0,1{\}}^7,\pi (b)=(b_6{X}^6+\mathrm{...}+b_{1}X+b_0)mod{X}^7+X+1$
2. $\mathrm{\Phi }=K[X]/(x^{67}+X^5+X^2+X+1)$. Определим $\phi$ как биекцию между $K^{67}$ и $\mathrm{\Phi }$ как: $\mathrm{\forall }\omega =({\omega }_0,\mathrm{...},{\omega }_{66})\in K^{67},\phi (\omega )=({\omega }_{66}{X}^{66}+\mathrm{...}+{\omega }_{1}X+{\omega }_0)mod{X}^{67}+X^5+X^2+X+1$
3. $\mathrm{\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({\phi }^{-1}(F(\phi (s(X))))){]}_{0\to 391}$

F — это функция из $\mathrm{\Phi }$ в $\mathrm{\Phi }$ определенная как $\mathrm{\forall }A\in \mathrm{\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)Генерируем $\mathrm{\Delta }$

С помощью CSPRBG(Cryptographically Secure PseudoRandom Bit Generator) генерируем 80 случайных бит.

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

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

Схема генерации подписи в алгоритме SFLASH

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

$M_0=SHA-1(M)$,

$M_1=SHA-1(M_0\Vert 0x00)$,

$M_2=SHA-1(M_0\Vert 0x01)$,

$M_3=SHA-1(M_0\Vert 0x02)$,

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

$V=[M_1{]}_{0\to 159}\Vert [M_2{]}_{0\to 159}\Vert [M_3{]}_{0\to 71}$

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

$W=[SHA-1(V\Vert \mathrm{\Delta }){]}_{0\to 76}$

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

$Y=(\pi ([V{]}_{0\to 6}),\pi ([V{]}_{7\to 13}),\mathrm{...},\pi ([V{]}_{385\to 391}))$

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

$R=(\pi ([W{]}_{0\to 6}),\pi ([W{]}_{7\to 13}),\mathrm{...},\pi ([W{]}_{70\to 76}))$

6) Найдем B — элемент $\mathrm{\Phi }$ как:

$B=\phi (t^{-1}(Y\Vert R))$

7) Найдем A — элемент $\mathrm{\Phi }$ как:

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

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

$X=(X_0,\mathrm{...},X_{66})=s^{-1}({\phi }^{-1}(A))$

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

$S={\pi }^{-1}(X_0)\Vert \mathrm{...}\Vert {\pi }^{-1}(X_{66})$

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

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

Схема проверки(верификации) подписи в алгоритме SFLASH

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

$M_0=SHA-1(M)$,

$M_1=SHA-1(M_0\Vert 0x00)$,

$M_2=SHA-1(M_0\Vert 0x01)$,

$M_3=SHA-1(M_0\Vert 0x02)$,

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

$V=[M_1{]}_{0\to 159}\Vert [M_2{]}_{0\to 159}\Vert [M_3{]}_{0\to 71}$

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

$Y=(\pi ([V{]}_{0\to 6}),\pi ([V{]}_{7\to 13}),\mathrm{...},\pi ([V{]}_{385\to 391}))$

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

$Y^{\prime }=G(\pi ([S{]}_{0\to 6}),\pi ([S{]}_{7\to 13}),\mathrm{...},\pi ([S{]}_{385\to 391}))$

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

Литература

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

Ссылки

• Многомерная криптография