SFLASH — асимметричный алгоритм цифровой подписи рекомендованный проектом NESSIE European в 2003 году. SFLASH основан на Matsumoto-Imai(MI) схеме, так же называемой C*. Алгоритм принадлежит к семейству многомерных схем с открытым ключом, то есть каждая подпись и каждый хеш сообщения представлен элементами конечного поля K. SFLASH был разработан для очень специфичных приложений, где затраты на классические алгоритмы (RSA, Elliptic Curves, DSA и другие) становятся чрезвычайно высокими: они очень медленные и имеют большой размер подписи. Таким образом SFLASH был создан, чтобы удовлетворять потребностям дешевых смарт-карт.
SFLASH гораздо быстрее и проще, чем RSA, как и в создании, так и в проверке (верификации) подписи.
Введение Во всей статье будут использоваться следующие обозначения: — определяет оператор конкатенации. — оператор, который определяется следующим образом: , где , а целые числа r и s должны удовлетворять: .
Параметры алгоритма Алгоритм SFLASH использует два определенных поля: определяется как . Определим как биекцию между и K как: . Определим как биекцию между и как: — 80 битная скрытая строка. Так же алгоритм SFLASH использует две афинные биекции s и t из в . Каждое из которых составляет скрытые линейные (матрицы 67*67) и постоянные (столбец 67*1) соответственно.
Открытые параметры Открытый ключ заключается в функции G из в определенную как:
F — это функция из в определенная как
Формирование ключа Обозначим next_7bit_random_string строку из 7 бит, которая формируется путём вызова CSPRBG(Cryptographically Secure PseudoRandom Bit Generator) 7 раз. Сначала мы получаем первый бит строки, потом второй и так до седьмого.
1)Генерируем Для генерации инвертированной 67x67 матрицы могут быть использованы два метода: Будем заполнять матрицу по одному элементу до тех пор, пока не заполним всю матрицу: for i=0 to 66 for j=0 to 66 S_L[i,j]=pi(next_7bit_random_string) Используем LU-разложение, где — нижняя треугольная матрица 67x67, а — верхняя треугольная матрица 67x67. После нахождения матриц и , определяем : 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)Генерируем Используем CSPRBG для нахождения новых 67 элементов K(от верхней к нижней части столбца матрицы). Каждый элемент K находится с помощью функции:
(next_7bit_random_string)
3)Генерируем Аналогично как и матрицу . 4)Генерируем Аналогично как и столбец . 5)Генерируем С помощью CSPRBG(Cryptographically Secure PseudoRandom Bit Generator) генерируем 80 случайных бит.
Создание подписи Пусть M — это наше сообщение, для которого мы хотим найти подпись S. Создание подписи S имеет следующий алгоритм:
1) Пусть — это строки определяющиеся с помощью алгоритма криптографического хеширования SHA-1:
,
,
,
,
2) Найдем V — 392 битную строку как:
3) Найдем W — 77 битную строку как:
4) Найдем Y — строку из 56 элементов K как:
5) Найдем R — строку из 11 элементов K как:
6) Найдем B — элемент как:
7) Найдем A — элемент как: , где F — функция из в определенная как:
8) Найдем — строка 67 элементов K:
9) Подпись S — 469 битная строка полученная как:
Проверка (верификация) подписи Даны сообщение M (строка бит) и подпись S (256-битовая строка). Следующий алгоритм используется для определения валидности подписи S сообщения M:
1) Пусть — это строки определяющиеся с помощью алгоритма криптографического хеширования SHA-1:
,
,
,
,
2) Найдем V — 392 битную строку как:
3) Найдем Y — строку из 56 элементов K как:
4) Найдем Y' — строку из 56 элементов K как:
5) Сравниваем получившиеся строки Y и Y'. Если они равны, то подпись принимается, в противном случае — отклоняется.
Литература «Nicolas T.Courtois, Louis Goubin and Jacques Patarin. SFLASHv3, a fast asymmetric signature scheme, 2003» , Спецификация алгоритма от разработчиков «Vivien Dubois, Pierre-Alain Fouque, Adi Shamir and Jacques Stern, Practical Cryptanalysis of SFLASH» , описание действующих атак на SFLASH
Ссылки Многомерная криптография
Категория:Криптография с открытым ключом Категория:Электронная подпись