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, но не был выбран, так как было показано, что линейный криптоанализ может быть эффективнее, чем атака перебором.

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

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

Шифрование

Введём обозначения. Пусть ${\displaystyle N=4n}$ — длина шифруемого блока открытого текста ${\displaystyle P=P_{3}P_{2}P_{1}P_{0}}$. ${\displaystyle KS_{i}}$ (start key) — выбирается по некоторому расписанию на основе ключа К. Побитово добавляется к исходному тексту: ${\displaystyle a_{0}b_{0}c_{0}d_{0}=P_{3}P_{2}P_{1}P_{0}\oplus KS_{0}KS_{1}KS_{2}KS_{3}}$ После этого происходит r-1 раундов, задаваемых следующими уравнениями, в которых ${\displaystyle KR_{i}}$ (Round subKey)- раундовые подключи, # — побитовая конъюнкция или дизъюнкция, выбирается в соответствии с расписанием, ${\displaystyle C_{i}}$, ${\displaystyle S_{i}}$ — известные константы, >>>j — циклический сдвиг вправо на j бит:

for i=1…(r-1)

${\displaystyle a_{i}=b_{i-1}}$

${\displaystyle b_{i}=((c_{i}\oplus (KR_{i-1}+C_{i-1}))+b_{i-l})>>>S_{i-1}}$

${\displaystyle c_{i}=d_{i-1}}$

${\displaystyle d_{i}=a_{i-1}+(b_{i}\#d_{i-l})}$

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

${\displaystyle a_{r}=a_{r-1}+(c_{r}\#d_{r-1})}$

${\displaystyle b_{r}=b_{r-1}}$

${\displaystyle c_{r}=((c_{r-1}\oplus (KR_{r-1}+C_{r-1}))+b_{r-1})>>>S_{r-1}}$

${\displaystyle d_{r}=d_{r-1}}$

Выход: зашифрованный блок ${\displaystyle M_{0}M_{1}M_{2}M_{3}=a_{r}b_{r}c_{r}d_{r}\oplus KF_{0}KF_{1}KF_{2}KF_{3}}$

Расшифрование

По общей формуле для обращения произведения операторов ${\displaystyle (AB)^{-1}=B^{-1}A^{-1}}$ строится и процедура расшифрования.

${\displaystyle a_{r}b_{r}c_{r}d_{r}=M_{0}M_{1}M_{2}M_{3}\oplus KF_{0}KF_{1}KF_{2}KF_{3}}$

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

${\displaystyle d_{r-1}=d_{r}}$

${\displaystyle b_{r-1}=b_{r}}$

${\displaystyle a_{r-1}=a_{r}-(c_{r}\#d_{r-1})}$

${\displaystyle c_{r-1}=c_{r}>>>(n-S_{r-1})}$ (${\displaystyle n=N/4}$ — длина ${\displaystyle c_{r}}$, можно производить циклический сдвиг влево на ${\displaystyle S_{r-1}}$)

${\displaystyle c_{r-1}=c_{r-1}-KR_{r-1}-b_{r-1}}$

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

for i=r-1…1

${\displaystyle d_{i-1}=c_{i}}$

${\displaystyle b_{i-1}=a_{i}}$

${\displaystyle a_{i-1}=d_{i}-(b_{i}\#c_{i-1})}$

${\displaystyle c_{i-1}=(b_{i}>>>(n-S_{i-1}))-KR_{i-1}-a_{i-1}}$

Комментарии

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

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

${\displaystyle R(a,b,c,d,k,s)=a_{1}b_{1}c_{1}d_{1}}$

${\displaystyle c_{1}=(c+k+b)>>>s}$

${\displaystyle a_{1}=a+c_{1}\#d}$

${\displaystyle b_{1}=b}$

${\displaystyle d_{1}=d}$

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

${\displaystyle R(a,b,c,d,k_{1},s_{1})}$

${\displaystyle R(b,c,d,a,k_{2},s_{2})}$

${\displaystyle R(c,d,a,b,k_{3},s_{3})}$

${\displaystyle R(d,a,b,c,k_{4},s_{4})}$

где ${\displaystyle k_{i}=k_{i}+C_{i}}$ — к итерационному ключу ${\displaystyle k_{i}}$ добавляется соответствующая константа ${\displaystyle C_{i}}$

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

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

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

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

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

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

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

Параметры

Константы ${\displaystyle C_{i}}$ и ${\displaystyle S_{i}}$

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

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

i	${\displaystyle C_{i}}$	i	${\displaystyle C_{i}}$	i	${\displaystyle C_{i}}$	i	${\displaystyle C_{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	${\displaystyle S_{i}}$	i	${\displaystyle S_{i}}$	i	${\displaystyle S_{i}}$	i	${\displaystyle S_{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-битных констант ${\displaystyle C_{i}}$ и 68 констант ${\displaystyle 0<=S_{i}<=31}$.

Длина блока 256 бит

При длине блока 256 бит проводится 132 раундов. Поэтому задаются 132 64-битных константы ${\displaystyle C_{i}}$ и 132 константы ${\displaystyle 0<=S_{i}<=63}$.

Расписание ключей

Ключ представляется в виде ${\displaystyle K=K_{0}K_{1}...}$ конкатенации N/4-битных слов. KS и KF задаются произвольным образом, а в качестве раундовых ключей по очереди используются все ${\displaystyle K_{i}}$

128-битный ключ

Блок в 64 бита

Ключ К делится на 8 слов ${\displaystyle KS_{0}=K_{4},\ KF_{0}=K_{3},\ KS_{1}=K_{5},\ KF_{1}=K_{2},}$ ${\displaystyle KS_{2}=K_{6},\ KF_{2}=K_{1},\ KS_{3}=K_{7},\ KF_{3}=K_{0},\ KR_{i}=K_{i\ mod\ 8},\ i=0...35}$

Блоки в 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

Для дальнейших итераций все повторяется: ${\displaystyle \#_{i}=\#_{i\ mod\ 64}}$

Быстродействие

В алгоритме отсутствуют операции с битовою сложностью выше, чем ${\displaystyle O(k)}$, где ${\displaystyle k}$ — битовая длина модуля или операндов (например, у произведения по модулю, нахождения обратного (по умножению) элемента или наибольшего общего делителя битовая сложность ${\displaystyle O(k^{2})}$, а у возведения в степень — ${\displaystyle O(k^{3})}$). Поэтому естественно ожидать высокой скорости работы алгоритма. Авторами приводятся следующие данные:

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

Безопасность

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

В своей статье «Линейный криптоанализ блочного шифра NUSH» они используют понятие сложности атаки ${\displaystyle \delta =(\varepsilon ,\ \eta )}$, где ${\displaystyle \varepsilon }$ характеризует потребности в памяти, а ${\displaystyle \eta }$ — в объёме вычислений.

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

Длина блока, бит	Длина ключа, бит	${\displaystyle \delta }$
64	128	${\displaystyle (2^{58},\ 2^{124}),\ (2^{60},\ 2^{78}),\ (2^{62},\ 2^{55})}$
	192	${\displaystyle (2^{58},\ 2^{157}),\ (2^{60},\ 2^{96}),\ (2^{62},\ 2^{58})}$
	256	${\displaystyle (2^{58},\ 2^{125}),\ (2^{60},\ 2^{78}),\ (2^{62},\ 2^{53})}$
128	128	${\displaystyle (2^{122},\ 2^{95}),\ (2^{124},\ 2^{57}),\ (2^{126},\ 2^{52})}$
	192	${\displaystyle (2^{122},\ 2^{142}),\ (2^{124},\ 2^{75}),\ (2^{126},\ 2^{58})}$
	256	${\displaystyle (2^{122},\ 2^{168}),\ (2^{124},\ 2^{81}),\ (2^{126},\ 2^{63})}$
256	128	${\displaystyle (2^{252},\ 2^{122}),\ (2^{254},\ 2^{119})}$
	192	${\displaystyle (2^{252},\ 2^{181}),\ (2^{254},\ 2^{177})}$
	256	${\displaystyle (2^{252},\ 2^{240}),\ (2^{254},\ 2^{219})}$

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

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

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

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

${\displaystyle a_{i}[0]\oplus b_{i}[0]\oplus d_{i}[0]=a_{i-1}[0]\oplus b_{i-1}[0]\oplus d_{i-1}[0]\oplus \theta }$, ${\displaystyle \theta ={\begin{cases}1,&{\mbox{if }}\#=OR\\0,&{\mbox{if }}\#=AND\end{cases}}}$

Это уравнение можно проверить, используя описание алгоритма, и учтя, что для последнего (младшего) разряда операции «+» и ${\displaystyle \oplus }$ совпадают. Действительно, имеем соотношение ${\displaystyle d_{i}[0]=a_{i-1}[0]\oplus b_{i}[0]\oplus d_{i-1}\oplus \theta \ \Leftrightarrow \ b_{i}[0]\oplus d_{i}[0]=a_{i-1}[0]\oplus d_{i-1}\oplus \theta }$. Добавив к обеим частя равенства соотношение ${\displaystyle a_{i}[0]=b_{i-1}[0]}$ получим требуемое.

Далее учитывая конкретные значения ${\displaystyle S_{i}}$ можно показать, что ${\displaystyle a_{2}[0]\oplus b_{2}[0]\oplus d_{2}[0]}$ зависит не от всех бит ключа и открытого текста, а именно:

${\displaystyle a_{2}[0]\oplus b_{2}[0]\oplus d_{2}[0]\ =\ f_{1}(P_{0}[0-7],P_{1}[0-11],P_{2}[0-11],P_{3}[0],KS_{0}[0],KS_{1}[0-11],KS_{2}[0-11],KS_{3}[0-7],KR_{0}[0-11],KR_{1}[0-7])}$

Рассмотрев 4 первых раунда дешифрования, можно установить, что ${\displaystyle a_{31}[0]\oplus b_{31}[0]\oplus d_{31}[0]\ =\ f_{2}(M_{0}[0-9],M_{1}[0-11],M_{2}[0-9,12],M_{3}[0,1],KF_{0}[0,1],KF_{1}[0-9,12],KF_{2}[0-11],KF_{3}[0-9],KR_{32}[0],KR_{33}[0],KR_{34}[0],KR_{35}[0-9])}$.

Используя Piling-up лемму, ${\displaystyle a_{2}[0]\oplus b_{2}[0]\oplus d_{2}[0]=a_{31}[0]\oplus b_{31}[0]\oplus d_{31}[0]}$ с вероятностью ${\displaystyle 0.5+2^{-30}}$. Получили связь между ${\displaystyle m_{0}}$ битами ключа и открытым и зашифрованным текстами.

Из расписания ключей можно получить, что если длина ключа составляет 128 или 256 бит, то ${\displaystyle m_{0}=78}$, если же ключ состоит из 192 бит, то ${\displaystyle m_{0}=96}$. Из этих данных оцениваем временную сложность атаки, задаваемой следующим алгоритмом:

• для каждого «ключа» ${\displaystyle K'^{i}\in [1...2^{m_{0}}]}$ считаем количество открытых текстов, удовлетворяющих найденному соотношению;
• находим максимальное из них;
• находим оставшиеся биты ключа: или похожим образом, находя соотношения, или путём перебора.

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

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

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

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

• потоковый шифр
• хеш-функция
• код аутентичности сообщения (MAC)
• асимметричное шифрование
• электронная цифровая подпись
• схемы аутентификации

Хеш-функция

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

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

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

• ${\displaystyle TEXT=[TEXT_{0}...TEXT_{l-1}]}$ — расширенный текст, представленный в виде ${\displaystyle l}$ блоков длины N.
• ${\displaystyle H=[H_{0}...H_{3}]}$, ${\displaystyle V=[V_{0}...V_{3}]}$ -регистры длины N, состоящий из 4 n-битовых слов
• ${\displaystyle T=[T_{0}...T_{15}]}$б ${\displaystyle M=[M_{0}...M_{15}]}$ -регистры длины 4N, состоящий из 15 n-битовых слов/

Начальные значения: ${\displaystyle T=[C_{0}...C_{15}]}$, ${\displaystyle M=[C_{16}...C_{31}]}$, где ${\displaystyle C_{i}}$ — константы, которые прибавляются во время шифрования к ключу KR, KS=KF=KR=0

For i = 0 to l-1

{

For j=0 to L/2-1 //L — число раундов для соответствующего вида NUSH

{

${\displaystyle C_{2j}=T_{jmod16}}$

${\displaystyle C_{2*j+1}=M_{jmod16}}$

}

${\displaystyle V=TEXT_{i}}$

H = NUSH(V) //Операция шифрования

${\displaystyle [H_{0}...H_{3}]+=[V_{0}...V_{3}]}$

For j=15 to 4

${\displaystyle T_{j}=T_{j-4}}$

${\displaystyle [T_{0}...T_{3}]=[H_{0}...H_{3}]}$

For j=15 to 4

${\displaystyle M_{j}=M_{j-4}}$

${\displaystyle [M_{0}...M_{3}]=[V_{0}...V_{3}]}$

}

For i= 0 to 3

{

For j=0 to L/2-1

${\displaystyle C_{2*j}=T_{jmod16}}$

H = NUSH(${\displaystyle M_{i}}$)

For j=15 to 4

${\displaystyle T_{j}=T_{j-4}}$

${\displaystyle [T_{0}...T_{3}]=[H_{0}...H_{3}]}$

}

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

Код аутентичности сообщения

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

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

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

Вариант 1

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

${\displaystyle SYNC=SYNC\oplus NUSH(SYNC)}$

For i =0 to COUNT −1

{

${\displaystyle GAMMA_{i}=NUSH(SYNC)}$

SYNC = (SYNC + 65257) mod ${\displaystyle 2^{N}}$

}

Вариант 2

Здесь N=LENGTH / 2, где соответственно LENGTH = 128, 256, 512. Пусть ${\displaystyle T=[T_{0}T_{1}T_{2}T_{3}]}$ — вектор длины N, SYNC=[SYNC_0SYNC_1] — вектор длины 2N T — временный регистр длины N=4n, ${\displaystyle C_{n}}$, ${\displaystyle C_{n+1}}$, ${\displaystyle C_{n+2}}$,${\displaystyle C_{n+3}}$ — соответствующие константы алгоритма NUSH.

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

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

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

For i =0 to COUNT −1

{

${\displaystyle [C_{n}C_{n+1}C_{n+2}C_{n+3}]=T}$

${\displaystyle GAMMA_{i}=NUSH(SYNC_{0})}$

${\displaystyle SYNC_{0}=(SYNC_{0}+65257)mod\ 2^{N}}$

T = (T + 127) mod ${\displaystyle 2^{N}}$

}

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

Выбор параметров

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

Умножение Монтгомери. Выберем простое число P длиной в n бит, число ${\displaystyle N\geq n}$ Для двух целых А и В произведением Монтгомери будет число: ${\displaystyle A\otimes B={\frac {AB+P(ABM\ mod\ 2^{N})}{2^{N}}}}$, где ${\displaystyle M=-P^{-1}\ mod\ 2^{N}}$. Под делением на ${\displaystyle 2^{N}}$ подразумевается игнорирование младших N бит числа. Групповая операция: ${\displaystyle A\diamondsuit B={\begin{cases}A\otimes B&A\otimes B<P\\A\otimes B-P&else\end{cases}}}$

${\displaystyle \otimes }$ вычисляется при N=n. А и В считаются равными, если отличаются или на Р, или на 0. Получена абелева мультипликативная группа G. Можно построить изоморфизм между G и приведенной системой вычетов по модулю P: ${\displaystyle \phi :G\ni m\rightarrow m\times 2^{N}\ mod\ P\in F_{P}^{*}}$

Группа строится с использованием простого числа P такого, что ${\displaystyle {P-1} \over 2}$ — тоже простое.

Криптостойкость алгоритма обеспечивается сложностью задачи дискретного логарифмирования. Сложность взлома оценивается как ${\displaystyle O(e^{{\frac {1}{3}}\times logP\times log^{2}P)})}$. В этой группе выбирается генератор a. Закрытый ключ: случайное равномерно распределенное на отрезке [0, P-2] целое число x. Открытый ключ: элемент группы G ${\displaystyle b=a^{x}}$.

Шифрование

• Выбирается случайное ${\displaystyle r\in [1,P-1]}$
• Вычисляется ${\displaystyle c=a^{x}\in G}$
• ${\displaystyle d=|b^{r}|}$, где |x|=x, если x<P и |x|=x-P иначе
• ${\displaystyle e=NUSH_{d}(M)}$, M — исходное сообщение

Выход: c||e

Расшифрование

• ${\displaystyle d=|b^{r}|}$
• ${\displaystyle M=NUSH_{d}^{-1}(e)}$

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

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

Открытый ключ

• числа P и Q
• g — генератор подгруппы ${\displaystyle H\subset G}$ порядка Q
• ${\displaystyle b=g^{x\circ 1}}$, где x — закрытый ключ.

Закрытый ключ

Любое число ${\displaystyle x\in [1,Q-1]}$. В идеале, выбираемое с равномерным распределением.

Подписание

• Для случайного ${\displaystyle r\in [1,Q-1]}$ вычислим ${\displaystyle c=|g^{r}|}$
• ${\displaystyle d=Hash_{m}(MESSAGE||c)}$ — строка длиной m бит (если необходимо, отбросим младшие биты значения хеш-функции) (напомню, что m — половина длины числа Q). Случайно может оказаться, что d=0. В этом случае нужно заново выбрать случайное r и проделать все вычисления.
• ${\displaystyle e=r-(x\circ d)\ mod\ Q}$
• подпись включает в себя пару d, состоящего из m бит, и e.

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

Подпись считается верной, если ${\displaystyle d=Hash_{m}(Message||\ |g^{e}\diamondsuit b^{d}|)}$ Приведу доказательство корректности схемы. Очевидно, что корректность алгоритма равносильна верности равенства ${\displaystyle c=|g^{e}\diamondsuit b^{d}|}$.

Полученное равенство можно переписать в виде степеней генератора g подгруппы H в следующим образом: ${\displaystyle |g^{r-x\circ d}\diamondsuit (g^{x\circ 1})^{d}|=|g^{r}|}$. ${\displaystyle A=|A|\ mod\ P}$ из определения. Откуда ${\displaystyle g^{r-(x\circ d)+d(x\circ 1)}=g^{r}\ mod\ P}$. Операция ${\displaystyle \circ }$ линейна по второму аргументу с точностью до взятия равенства по модулю Q. В самом деле, ${\displaystyle A\otimes (b_{1}+...+b_{k})={\frac {A(b_{1}+...+b_{k})+Q((A(b_{1}+...+b_{n})M\ mod\ 2^{N})}{2^{N}}}={\frac {Ab_{1}+Q((Ab_{1}M\ mod\ 2^{N})}{2^{N}}}+...+{\frac {Ab_{k}+Q((Ab_{n}M\ mod\ 2^{N})}{2^{N}}}=A\circ b_{1}+...+A\circ b_{k}\ mod\ Q}$. Следовательно, ${\displaystyle d(x\circ 1)=x\circ d\ mod\ Q}$. Откуда и следует доказываемое равенство, поскольку порядок элемента g равен Q.

Схемы аутентификации

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

• А генерирует случайное число ${\displaystyle r\in [1...Q-1]}$ и отсылает стороне B ${\displaystyle c=Hash_{m}(|g^{r}|)}$
• B посылает случайное число ${\displaystyle k\in [1...2^{t}-1],\ t<2m}$. Чем выше t, тем выше надежность системы.
• А вычисляет ${\displaystyle d=r-x\circ Hash_{m}(c||k)\ mod\ Q}$ и отсылает его стороне В
• Аутентификация считается пройденной, если ${\displaystyle Hash_{m}(|g^{d}\diamondsuit b^{Hash_{m}(c||k)}|)=c}$

Примечания

Ссылки

• NUSH в проекте NESSIE Архивная копия от 26 сентября 2007 на Wayback Machine
• Сайт компании Lan Crypto Архивная копия от 13 мая 2010 на Wayback Machine
• Криптоанализ (недоступная ссылка)
• Авторское описание алгоритма Архивная копия от 12 августа 2011 на Wayback Machine