Русская Википедия:SFLASH
Шаблон:Нет сносок SFLASH — асимметричный алгоритм цифровой подписи рекомендованный проектом NESSIE European в 2003 году. SFLASH основан на Matsumoto-Imai(MI) схеме, так же называемой C*. Алгоритм принадлежит к семейству многомерных схем с открытым ключом, то есть каждая подпись и каждый хеш сообщения представлен элементами конечного поля K. SFLASH был разработан для очень специфичных приложений, где затраты на классические алгоритмы (RSA, Elliptic Curves, DSA и другие) становятся чрезвычайно высокими: они очень медленные и имеют большой размер подписи. Таким образом SFLASH был создан, чтобы удовлетворять потребностям дешевых смарт-карт.
SFLASH гораздо быстрее и проще, чем RSA, как и в создании, так и в проверке (верификации) подписи.Шаблон:Нет АИ
Введение
Во всей статье будут использоваться следующие обозначения:
- <math>\|</math> — определяет оператор конкатенации.
- <math>[\lambda]_{r \rightarrow s} </math> — оператор, который определяется следующим образом: <math>[\lambda]_{r \rightarrow s}=(\lambda_r, \lambda_{r+1},...,\lambda_{s-1},\lambda_s) </math>, где <math>\lambda =(\lambda_1,...,\lambda_m) </math>, а целые числа r и s должны удовлетворять: <math>0\leq r\leq s \leq m</math>.
Параметры алгоритма
Алгоритм SFLASH использует два определенных поля:
- <math>K=F_{128}</math> определяется как <math>K=F_2[X]/(X^7+X+1)</math>. Определим <math>\pi</math> как биекцию между <math>\{0,1\}^7 </math> и K как: <math>\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>\Phi=K[X]/(x^{67}+X^5+X^2+X+1)</math>. Определим <math>\varphi</math> как биекцию между <math>K^{67}</math> и <math>\Phi</math> как: <math>\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>\Delta</math> — 80 битная скрытая строка.
Так же алгоритм SFLASH использует две афинные биекции s и t из <math>K^{67}</math> в <math>K^{67}</math>. Каждое из которых составляет скрытые линейные <math>S_L, T_L</math> (матрицы 67*67) и постоянные <math>S_C, T_C</math>(столбец 67*1) соответственно.
Открытые параметры
Открытый ключ заключается в функции G из <math>K^{67}</math> в <math>K^{56}</math> определенную как: <math>G(X)=[t(\varphi^{-1}(F(\varphi(s(X)))))]_{0\rightarrow391}</math>
F — это функция из <math>\Phi </math> в <math>\Phi </math> определенная как <math>\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>S_L</math>
- Для генерации инвертированной 67x67 матрицы <math>S_L</math> могут быть использованы два метода:
- Будем заполнять матрицу по одному элементу до тех пор, пока не заполним всю матрицу:
for i=0 to 66 for j=0 to 66 S_L[i,j]=pi(next_7bit_random_string)
- Используем LU-разложение, где <math>L_S</math> — нижняя треугольная матрица 67x67, а <math>U_S</math> — верхняя треугольная матрица 67x67. После нахождения матриц <math>L_S</math> и <math>U_S</math>, определяем <math>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>S_C</math>
- Используем CSPRBG для нахождения новых 67 элементов K(от верхней к нижней части столбца матрицы). Каждый элемент K находится с помощью функции:
<math>\pi</math>(next_7bit_random_string)
- 3)Генерируем <math>T_L</math>
- Аналогично как и матрицу <math>S_L</math>.
- 4)Генерируем <math>T_C</math>
- Аналогично как и столбец <math>S_C</math>.
- 5)Генерируем <math>\Delta</math>
- С помощью CSPRBG(Cryptographically Secure PseudoRandom Bit Generator) генерируем 80 случайных бит.
Создание подписи
Пусть M — это наше сообщение, для которого мы хотим найти подпись S. Создание подписи S имеет следующий алгоритм:
1) Пусть <math>M_0, M_1, M_2, M_3</math> — это строки определяющиеся с помощью алгоритма криптографического хеширования SHA-1:
- <math>M_0=SHA-1(M)</math>,
- <math>M_1=SHA-1(M_0\|0x00)</math>,
- <math>M_2=SHA-1(M_0\|0x01)</math>,
- <math>M_3=SHA-1(M_0\|0x02)</math>,
2) Найдем V — 392 битную строку как:
- <math> V=[M_1]_{0\rightarrow159}\|[M_2]_{0\rightarrow159}\|[M_3]_{0\rightarrow71}</math>
3) Найдем W — 77 битную строку как:
- <math>W=[SHA-1(V\|\Delta)]_{0\rightarrow76} </math>
4) Найдем Y — строку из 56 элементов K как:
- <math>Y=(\pi([V]_{0\rightarrow6}),\pi([V]_{7\rightarrow13}),...,\pi([V]_{385\rightarrow391}))</math>
5) Найдем R — строку из 11 элементов K как:
- <math>R=(\pi([W]_{0\rightarrow6}),\pi([W]_{7\rightarrow13}),...,\pi([W]_{70\rightarrow76}))</math>
6) Найдем B — элемент <math>\Phi</math> как:
- <math>B=\varphi(t^{-1}(Y\|R))</math>
7) Найдем A — элемент <math>\Phi</math> как:
- <math>A=F^{-1}(B)</math>, где F — функция из <math>\Phi</math> в <math>\Phi</math> определенная как: <math>\forall A\in\Phi, F(A)=A^{128^{33}+1} </math>
8) Найдем <math>X=(X_0,...,X_{66})</math> — строка 67 элементов K:
- <math>X=(X_0,...,X_{66})=s^{-1}(\varphi^{-1}(A))</math>
9) Подпись S — 469 битная строка полученная как:
- <math>S=\pi^{-1}(X_0)\|...\|\pi^{-1}(X_{66})</math>
Проверка (верификация) подписи
Даны сообщение M (строка бит) и подпись S (256-битовая строка). Следующий алгоритм используется для определения валидности подписи S сообщения M:
1) Пусть <math>M_0, M_1, M_2, M_3</math> — это строки определяющиеся с помощью алгоритма криптографического хеширования SHA-1:
- <math>M_0=SHA-1(M)</math>,
- <math>M_1=SHA-1(M_0\|0x00)</math>,
- <math>M_2=SHA-1(M_0\|0x01)</math>,
- <math>M_3=SHA-1(M_0\|0x02)</math>,
2) Найдем V — 392 битную строку как:
- <math> V=[M_1]_{0\rightarrow159}\|[M_2]_{0\rightarrow159}\|[M_3]_{0\rightarrow71}</math>
3) Найдем Y — строку из 56 элементов K как:
- <math>Y=(\pi([V]_{0\rightarrow6}),\pi([V]_{7\rightarrow13}),...,\pi([V]_{385\rightarrow391}))</math>
4) Найдем Y' — строку из 56 элементов K как:
- <math>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» Шаблон:Wayback, Спецификация алгоритма от разработчиков
- «Vivien Dubois, Pierre-Alain Fouque, Adi Shamir and Jacques Stern, Practical Cryptanalysis of SFLASH» Шаблон:Wayback, описание действующих атак на SFLASH
Ссылки