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

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

Введение

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

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

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

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

1. ${\displaystyle K=F_{128}}$ определяется как ${\displaystyle K=F_{2}[X]/(X^{7}+X+1)}$ . Определим ${\displaystyle \pi }$ как биекцию между ${\displaystyle \{0,1\}^{7}}$ и K как: ${\displaystyle \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}$
2. ${\displaystyle \Phi =K[X]/(x^{67}+X^{5}+X^{2}+X+1)}$ . Определим ${\displaystyle \varphi }$ как биекцию между ${\displaystyle K^{67}}$ и ${\displaystyle \Phi }$ как: ${\displaystyle \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}$
3. ${\displaystyle \Delta }$ — 80 битная скрытая строка.

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

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

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

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

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

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

1)Генерируем ${\displaystyle S_{L}}$

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

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

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

• Используем LU-разложение , где ${\displaystyle L_{S}}$ — нижняя треугольная матрица 67x67, а ${\displaystyle U_{S}}$ — верхняя треугольная матрица 67x67. После нахождения матриц ${\displaystyle L_{S}}$ и ${\displaystyle U_{S}}$ , определяем ${\displaystyle 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)Генерируем ${\displaystyle S_{C}}$

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

${\displaystyle \pi }$ (next_7bit_random_string)

3)Генерируем ${\displaystyle T_{L}}$

Аналогично как и матрицу ${\displaystyle S_{L}}$ .

4)Генерируем ${\displaystyle T_{C}}$

Аналогично как и столбец ${\displaystyle S_{C}}$ .

5)Генерируем ${\displaystyle \Delta }$

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

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

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

1) Пусть ${\displaystyle M_{0},M_{1},M_{2},M_{3}}$ — это строки определяющиеся с помощью алгоритма криптографического хеширования SHA-1 :

${\displaystyle M_{0}=SHA-1(M)}$ ,

${\displaystyle M_{1}=SHA-1(M_{0}\|0x00)}$ ,

${\displaystyle M_{2}=SHA-1(M_{0}\|0x01)}$ ,

${\displaystyle M_{3}=SHA-1(M_{0}\|0x02)}$ ,

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

${\displaystyle V=[M_{1}]_{0\rightarrow 159}\|[M_{2}]_{0\rightarrow 159}\|[M_{3}]_{0\rightarrow 71}}$

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

${\displaystyle W=[SHA-1(V\|\Delta )]_{0\rightarrow 76}}$

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

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

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

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

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

${\displaystyle B=\varphi (t^{-1}(Y\|R))}$

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

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

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

${\displaystyle X=(X_{0},...,X_{66})=s^{-1}(\varphi ^{-1}(A))}$

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

${\displaystyle S=\pi ^{-1}(X_{0})\|...\|\pi ^{-1}(X_{66})}$

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

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

1) Пусть ${\displaystyle M_{0},M_{1},M_{2},M_{3}}$ — это строки определяющиеся с помощью алгоритма криптографического хеширования SHA-1 :

${\displaystyle M_{0}=SHA-1(M)}$ ,

${\displaystyle M_{1}=SHA-1(M_{0}\|0x00)}$ ,

${\displaystyle M_{2}=SHA-1(M_{0}\|0x01)}$ ,

${\displaystyle M_{3}=SHA-1(M_{0}\|0x02)}$ ,

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

${\displaystyle V=[M_{1}]_{0\rightarrow 159}\|[M_{2}]_{0\rightarrow 159}\|[M_{3}]_{0\rightarrow 71}}$

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

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

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

${\displaystyle Y'=G(\pi ([S]_{0\rightarrow 6}),\pi ([S]_{7\rightarrow 13}),...,\pi ([S]_{385\rightarrow 391}))}$

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

Литература

• от 13 июля 2007 на Wayback Machine , Спецификация алгоритма от разработчиков
• от 7 июня 2011 на Wayback Machine , описание действующих атак на SFLASH

Ссылки

Для улучшения этой статьи желательно : Исправить статью согласно стилистическим правилам Википедии . Оформить статью по правилам . После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.