Interested Article - SFLASH

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

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

Введение

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

  1. — определяет оператор конкатенации .
  2. — оператор, который определяется следующим образом: , где , а целые числа r и s должны удовлетворять: .

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

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

  1. определяется как . Определим как биекцию между и K как:
  2. . Определим как биекцию между и как:
  3. — 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 имеет следующий алгоритм:

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

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:

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

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

,
,
,
,

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

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

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

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

Литература

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

Ссылки

Источник —

Same as SFLASH