NUSH

NUSH («Наш») — блочный алгоритм симметричного шифрования, разработанный Анатолием Лебедевым и Алексеем Волчковым для российской компании LAN Crypto.

NUSH
Создатель Анатолий Лебедев, Алексей Волчков
Создан 1999 г.
Опубликован 2000 г.
Размер ключа 128, 192, 256 бит
Размер блока 64, 128, 256 бит
Число раундов 36, 68, 132

NUSH имеет несколько различных вариантов, имеющих разный размер блока (64, 128, 256 бит), различное число раундов (в зависимости от размера блока равно 36, 128 или 132 раунда) и использует длину ключа в 128, 192 или 256 бит. Алгоритм не использует S-блоки, а только такие операции, как AND, OR, XOR, сложение по модулю и циклические сдвиги. Перед первым и после последнего раунда проводится «отбеливание» ключа.

Данный алгоритм был выдвинут в проекте NESSIE, но не был выбран, так как было показано, что линейный криптоанализ может быть эффективнее, чем атака перебором.

На основе алгоритма шифрования можно построить и другие алгоритмы. Несколько из них изложены в настоящей статье.

Описание алгоритмаПравить

ШифрованиеПравить

Введём обозначения. Пусть   — длина шифруемого блока открытого текста  .   (start key) — выбирается по некоторому расписанию на основе ключа К. Побитово добавляется к исходному тексту:   После этого происходит r-1 раундов, задаваемых следующими уравнениями, в которых   (Round subKey)- раундовые подключи, # — побитовая конъюнкция или дизъюнкция, выбирается в соответствии с расписанием,  ,   — известные константы, >>>j — циклический сдвиг вправо на j бит:

for i=1…(r-1)

 

 

 

 

Последняя итерация отличается от основных только отсутствием перестановки после вычисления выражений в правых частях равенств:

 

 

 

 

Выход: зашифрованный блок  

РасшифрованиеПравить

По общей формуле для обращения произведения операторов   строится и процедура расшифрования.

 

Выполняется одна итерация по расшифрованию:

 

 

 

  (  — длина  , можно производить циклический сдвиг влево на  )

 

После этого основной цикл расшифрования, состоящий из итераций, также несущественно отличающихся от предыдущей:

for i=r-1…1

 

 

 

 

КомментарииПравить

В некоторых источниках считают, что процедура шифрования состоит из в 4 раза меньшего числа раундов, состоящих из 4 итераций приведённого выше типа (без начального и конечного сложения по модулю 2). Так, сами авторы шифра записывали свой алгоритм следующим образом:

  • Определяли функцию R — «итерацию»:

 

 

 

 

 

  • Описывали начальное преобразование (сложение («+») с KS)
  • Говорили, что раунд состоит из 4 итераций:

 

 

 

 

где   — к итерационному ключу   добавляется соответствующая константа  

  • Описывали конечное преобразование (сложение («+») с KF).

Алгоритмы аналогичны, поскольку операция «+» определена авторами отдельно от основного описания метода шифрования. Следует отметить, что расписание операций «+» можно изменить, выбирая обратимые бинарные операции над векторами длины  . Нелинейная операция обычного сложения с игнорированием переполнения призвана усложнить линейный криптоанализ. А операция XOR помогают избежать дифференциального криптоанализа. В дальнейшем будет рассматриваться первое описание алгоритма, приведённое в статье китайских математиков, произведших линейный криптоанализ алгоритма.

Выбор операций «+» был произведён по итогам исследований распараллеливания вычислений на процессорах типа Pentium. Выбор изменения порядка регистров a, b, c, d от раунда к раунду ускоряет появление диффузии и конфузии. Базовые операции (XOR, сложение по модулю  , OR, AND) и их порядок ускорили выполнение алгоритма, реализованного на языке С на большинстве платформ, а имплементация алгоритма на ассемблере достаточно короткая.

Простота реализацииПравить

Из приведённого описания видно, что для реализации алгоритма необходимо:

  • Определить константы  
  • Знать расписание операций #, ключей.
  • Реализовать:
    • побитовый сдвиг вправо,
    • сложение и вычитание целых чисел,
    • побитовое исключающее ИЛИ,
    • побитовые дизъюнкцию и конъюнкцию.

При этом отсутствуют таблицы подстановок, присутствующие, например, в ГОСТе, а раунд состоит из 6 операций. То, что сдвиг осуществляется на заранее известную величину, не зависящую ни от открытого текста, ни от ключа, существенно упрощает реализацию алгоритма на микросхемах. Простота алгоритма позволяет легко проверить, что в конкретной имплементации отсутствует так называемый «черный ход».

ПараметрыПравить

Константы   и  Править

Длина N блока составляет 64 битаПравить

Проводится 36 раундов

i   i   i   i  
0 ac25 9 6a29 18 96da 27 d25e
1 8a93 10 6d84 19 905f 28 a926
2 243d 11 34bd 20 d631 29 1c7b
3 262e 12 a267 21 aa62 30 5f12
4 f887 13 cc15 22 4d15 31 4ecc
5 c4f2 14 04fe 23 70cb 32 3c86
6 8e36 15 b94a 24 7533 33 28db
7 9fa1 16 df24 25 45fc 34 fc01
8 7dc0 17 40ef 26 5337 35 7cb1
i   i   i   i  
0 4 9 2 18 5 27 13
1 7 10 9 19 1 28 12
2 11 11 4 20 2 29 3
3 8 12 13 21 4 30 6
4 7 13 1 22 12 31 11
5 14 14 14 23 3 32 7
6 5 15 6 24 9 33 15
7 4 16 7 25 2 34 4
8 8 17 12 26 11 35 14

Длина блоков 128 битПравить

При длине блока 128 бит проводится 68 раундов. Поэтому задаются 68 32-битных констант   и 68 констант  .

Длина блока 256 битПравить

При длине блока 256 бит проводится 132 раундов. Поэтому задаются 132 64-битных константы   и 132 константы  .

Расписание ключейПравить

Ключ представляется в виде   конкатенации N/4-битных слов. KS и KF задаются произвольным образом, а в качестве раундовых ключей по очереди используются все  

128-битный ключПравить

Блок в 64 битаПравить

Ключ К делится на 8 слов    

Блоки в 128 бит и 256 битПравить

Ключ К делится на 4 и 2 слова соответственно, поэтому раундовые ключи повторяются с периодом 4 или 2. В последнем случае среди KS и KF есть одинаковые.

192-битный ключПравить

В зависимости от длины блока ключ делится на 12, 6, и 3 n-битных частей, что определяет период повторения раундовых ключей.

256-битный ключПравить

Здесь ключ является объединением 16, 8 или 4 двоичных слов.

Расписание операции #Править

I # i # i # i #
0 AND 16 OR 32 OR 48 AND
1 OR 17 OR 33 OR 49 AND
2 AND 18 AND 34 AND 50 AND
3 OR 19 AND 35 OR 51 AND
4 OR 20 AND 36 OR 52 AND
5 OR 21 AND 37 AND 53 AND
6 OR 22 AND 38 OR 54 OR
7 OR 23 OR 39 AND 55 AND
8 AND 24 AND 40 OR 56 OR
9 OR 25 OR 41 AND 57 OR
10 OR 26 OR 42 AND 58 OR
11 AND 27 OR 43 OR 59 AND
12 OR 28 AND 44 OR 60 AND
13 AND 29 OR 45 AND 61 AND
14 OR 30 AND 46 AND 62 OR
15 OR 31 AND 47 AND 63 OR

Для дальнейших итераций все повторяется:  

БыстродействиеПравить

В алгоритме отсутствуют операции с битовою сложностью выше, чем  , где   — битовая длина модуля или операндов (например, у произведения по модулю, нахождения обратного (по умножению) элемента или наибольшего общего делителя битовая сложность  , а у возведения в степень —  ). Поэтому естественно ожидать высокой скорости работы алгоритма. Авторами приводятся следующие данные:

Размер блока, бит Программа на С Программа на ассемблере
Тактов на блок Тактов на байт Тактов на блок Тактов на байт
64 180 23 130 17
128 340 22 250 16

БезопасностьПравить

Главной причиной отсеивания алгоритма NUSH в конкурсе NESSIE стала найденная Ву Венлингом и Фенгом Денго уязвимость алгоритма к линейному криптоанализу.

В своей статье «Линейный криптоанализ блочного шифра NUSH» они используют понятие сложности атаки  , где   характеризует потребности в памяти, а   — в объёме вычислений.

Для N=64 и N=128 бит предложено 3 вида атак, а для N=256 — два. Сложности соответствующих атак:

Длина блока, бит Длина ключа, бит  
64 128  
192  
256  
128 128  
192  
256  
256 128  
192  
256  

Для некоторых случаев версия с 192-битным ключом существенно надежнее, чем с более длинным ключом. Также можно заметить, что есть случаи, когда сложности атак шифра с самой маленькой длиной ключа и самой большой практически совпадают. Кроме того, увеличение длины ключа сказывается не так сильно на сложности атаки, как хотелось бы.

Таким образом, существуют атаки на шифр NUSH эффективнее полного перебора. Поэтому есть вероятность улучшения этих атак или достижения вычислительной техникой уровня, достаточного для взлома шифра в разумное время.

Криптоанализ алгоритмаПравить

В качестве примера рассмотрим вторую атаку на шифр с длиной блока N=64 бита. Криптоанализ основан на построении зависимостей между битами ключа, исходного и зашифрованного текста, справедливых с вероятностью, отличающейся от 1/2. Эти соотношения строятся на основе уравнения, справедливого с вероятностью 3/4

 ,  

Это уравнение можно проверить, используя описание алгоритма, и учтя, что для последнего (младшего) разряда операции «+» и   совпадают. Действительно, имеем соотношение  . Добавив к обеим частя равенства соотношение   получим требуемое.

Далее учитывая конкретные значения   можно показать, что   зависит не от всех бит ключа и открытого текста, а именно:

 

Рассмотрев 4 первых раунда дешифрования, можно установить, что  .

Используя Piling-up лемму,   с вероятностью  . Получили связь между   битами ключа и открытым и зашифрованным текстами.

Из расписания ключей можно получить, что если длина ключа составляет 128 или 256 бит, то  , если же ключ состоит из 192 бит, то  . Из этих данных оцениваем временную сложность атаки, задаваемой следующим алгоритмом:

  • для каждого «ключа»   считаем количество открытых текстов, удовлетворяющих найденному соотношению;
  • находим максимальное из них;
  • находим оставшиеся биты ключа: или похожим образом, находя соотношения, или путём перебора.

Сложность по объёму хранимой информации оценивается как  . Именно стольким количеством пар открытый-шифрованный текст должен обладать криптоаналитик. При этом тексты отнюдь непроизвольные. Из приведенных соотношений видно, что   зависят не от всех битов входного и выходного блоков. Соответственно, среди выборки блоков открытого и зашифрованных текстов должны быть блоки с отличающимися соответствующими битами. Работа алгоритма с меньшим числом известных текстов возможна, но тогда с меньшей вероятностью найденное «максимальное» число на втором этапе будет действительно соответствовать настоящему ключу в виду непревышения корня из дисперсии числа событий «уравнение выполняется» над мат. ожиданием разницы чисел этого события и ему противоположного (можно рассмотреть схему Бернулли, где вероятность «успеха» равна вероятности выполнения соотношения).

Другие предложенные в той же статье атаки отличаются анализом на последней стадии соотношений для других раундов и самостоятельного интереса не представляют.

Другие алгоритмы на основе NUSHПравить

На основе NUSH можно построить другие алгоритмы. В частности:

Хеш-функцияПравить

Перед началом хеширования происходит удлинение текста:

  • Добавить к тексту единичный бит
  • Добавить столько нулей, чтобы получился текст с длиной, кратной N (эти два этапа можно не выполнять, если исходная длина текста уже кратна N)
  • Приписать N-битовое представление начальной длины LEN (в битах) текста
  • Приписать результат побитового XOR между всеми N-битовыми блоками полученного на предыдущем шаге текста

В функции используются следующие переменные:

  •   — расширенный текст, представленный в виде   блоков длины N.
  •  ,   -регистры длины N, состоящий из 4 n-битовых слов
  •  б   -регистры длины 4N, состоящий из 15 n-битовых слов/

Начальные значения:  ,  , где   — константы, которые прибавляются во время шифрования к ключу KR, KS=KF=KR=0

For i = 0 to l-1

{

For j=0 to L/2-1 //L — число раундов для соответствующего вида NUSH
{
 
 
}
 
H = NUSH(V) //Операция шифрования
 
For j=15 to 4
 
 
For j=15 to 4
 
 

}

For i= 0 to 3

{

For j=0 to L/2-1
 
H = NUSH( )
For j=15 to 4
 
 

}

Значение хеш-функции длиной t*n (t<16) бит — первые t n-битовых слов регистра T

Код аутентичности сообщенияПравить

На основе хеш-функции может быть построена процедура аутентификации сообщения. От предыдущего алгоритма отличается только использованием ненулевого ключа.

Синхронный поточный шифр «NUSH Stream»Править

Пусть SYNC — известный двоичный вектор длины LENGTH. Есть два варианта этого шифра.

Вариант 1Править

Пусть N = LENGTH — длина блока, используемого при шифровании алгоритмом NUSH (LENGTH = 64, 128, 256) Пусть   — вектор из COUNT N-битовых слов, который будет складываться с исходным текстом и с шифротекстом для шифрования и расшифрования соответственно.

 

For i =0 to COUNT −1

{

 
SYNC = (SYNC + 65257) mod  

}

Вариант 2Править

Здесь N=LENGTH / 2, где соответственно LENGTH = 128, 256, 512. Пусть   — вектор длины N, SYNC=[SYNC_0SYNC_1] — вектор длины 2N T — временный регистр длины N=4n,  ,  ,  ,  — соответствующие константы алгоритма NUSH.

Производимые вычисления:

SYNC[0] = SYNC[0] ^ NUSH(SYNC[0])

SYNC[1] = SYNC[1] ^ NUSH(SYNC[1]) T=SYNC[1]

For i =0 to COUNT −1

{

 
 
 
T = (T + 127) mod  

}

Асимметричное шифрованиеПравить

Выбор параметровПравить

Вводится специфическая группа G c определенной авторами алгоритма операцией на основе умножения Монтгомери (Montgomery multiplication).

Умножение Монтгомери. Выберем простое число P длиной в n бит, число   Для двух целых А и В произведением Монтгомери будет число:  , где  . Под делением на   подразумевается игнорирование младших N бит числа. Групповая операция:  

  вычисляеся при N=n. А и В считаются равными, если отличаются или на Р, или на 0. Получена абелева мультипликативная группа G. Можно построить изоморфизм между G и приведенной системой вычетов по модулю P:  

Группа строится с использованием простого числа P такого, что   — тоже простое.

Криптостойкость алгоритма обеспечивается сложностью задачи дискретного логарифмирования. Сложность взлома оценивается как  . В этой группе выбирается генератор a. Закрытый ключ: случайное равномерно распределенное на отрезке [0, P-2] целое число x. Открытый ключ: элемент группы G  .

ШифрованиеПравить

  • Выбирается случайное  
  • Вычисляется  
  •  , где |x|=x, если x<P и |x|=x-P иначе
  •  , M — исходное сообщение

Выход: c||e

РасшифрованиеПравить

  •  
  •  

Электронная цифровая подписьПравить

Данный алгоритм построен на основе описанной ранее хеш-функции. Пусть Q — простое число длиной 2m бит, являющееся делителем числа P-1. Под операцией   мы будем понимать уже введеную ранее операцию  , где в качестве простого числа используется Q.

Открытый ключПравить

  • числа P и Q
  • g — генератор подгруппы   порядка Q
  •  , где x — закрытый ключ.

Закрытый ключПравить

Любое число  . В идеале, выбираемое с равномерным распределением.

ПодписаниеПравить

  • Для случайного   вычислим  
  •   — строка длиной m бит (если необходимо, отбросим младшие биты значения хеш-функции) (напомню, что m — половина длины числа Q). Случайно может оказаться, что d=0. В этом случае нужно заново выбрать случайное r и проделать все вычисления.
  •  
  • подпись включает в себя пару d, состоящего из m бит, и e.

Проверка подписиПравить

Подпись считается верной, если   Приведу доказательство корректности схемы. Очевидно, что корректность алгоритма равносильна верности равенства  .

Полученное равенство можно переписать в виде степеней генератора g подгруппы H в следующим образом:  .   из определения. Откуда  . Операция   линейна по второму аргументу с точностью до взятия равенства по модулю Q. В самом деле,  . Следовательно,  . Откуда и следует доказываемое равенство, поскольку порядок элемента g равен Q.

Схемы аутентификацииПравить

Процесс аутентификации похож на схему цифровой подписи. Открытый и закрытый ключи выбираются абсолютно аналогично. Закрытый ключ хранится у того, кто хочет подтвердить свою «подлинность» (пусть это сторона А). В процессе аутентификации можно выделить четыре стадии:

  • А генерирует случайное число   и отсылает стороне B  
  • B посылает случайное число  . Чем выше t, тем выше надежность системы.
  • А вычисляет   и отсылает его стороне В
  • Аутентификация считается пройденной, если  

ПримечанияПравить

СсылкиПравить