NUSH

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

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

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

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

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

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

Шифрование

Введём обозначения. Пусть <math>N=4n</math> — длина шифруемого блока открытого текста <math>P=P_3P_2P_1P_0</math>. <math>KS_i</math> (start key) — выбирается по некоторому расписанию на основе ключа К. Побитово добавляется к исходному тексту: <math>a_0b_0c_0d_0=P_3P_2P_1P_0 \oplus KS_0KS_1KS_2KS_3</math> После этого происходит r-1 раундов, задаваемых следующими уравнениями, в которых <math>KR_i</math> (Round subKey)- раундовые подключи, # — побитовая конъюнкция или дизъюнкция, выбирается в соответствии с расписанием, <math>C_i</math>, <math>S_i</math> — известные константы, >>>j — циклический сдвиг вправо на j бит:

for i=1…(r-1)

<math>a_i = b_{i-1}</math>

<math>b_i = ((c_i \oplus (KR_{i-1} + C_{i-1})) + b_{i-l})>>>S_{i-1}</math>

<math>c_i = d_{i-1}</math>

<math>d_i = a_{i-1} + ( b_i \# d_{i-l} )</math>

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

<math>a_r = a_{r-l} + (c_r \# d_{r-l} )</math>

<math>b_r = b_{r-1}</math>

<math>c_r=((c_{r-1} \oplus (KR_{r-1} +C_{r-1}))+b_{r-1})>>>S_{r-1}</math>

<math>d_r = d_{r-1}</math>

Выход: зашифрованный блок <math>M_0M_1M_2M_3=a_rb_rc_rd_r \oplus KF_0KF_1KF_2KF_3</math>

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

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

<math>a_rb_rc_rd_r=M_0M_1M_2M_3 \oplus KF_0KF_1KF_2KF_3</math>

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

<math>d_{r-1} = d_r</math>

<math>b_{r-1} = b_r</math>

<math>a_{r-1} = a_r - (c_r \# d_{r-1})</math>

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

<math>c_{r-1} = c_{r-1} - KR_{r-1} - b_{r-1}</math>

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

for i=r-1…1

<math>d_{i-1} = c_i</math>

<math>b_{i-1} = a_i</math>

<math>a_{i-1} = d_i - (b_i \# c_{i-1})</math>

<math>c_{i-1} = (b_i >>> (n-S_{i-1}))-KR_{i-1}-a_{i-1}</math>

Комментарии

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

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

<math>R(a,b,c,d,k,s)=a_1b_1c_1d_1</math>

<math>c_1 = (c + k + b)>>>s</math>

<math>a_1 = a+ c_1 \# d</math>

<math>b_1 = b</math>

<math>d_1 = d</math>

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

<math>R(a, b, c, d, k_1, s_1)</math>

<math>R(b, c, d, a, k_2, s_2)</math>

<math>R(c, d, a, b, k_3, s_3)</math>

<math>R(d, a, b, c, k_4, s_4)</math>

где <math>k_i=k_i+C_i</math> — к итерационному ключу <math>k_i</math> добавляется соответствующая константа <math>C_i</math>

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

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

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

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

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

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

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

Параметры

Константы <math>C_i</math> и <math>S_i</math>

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

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

i	<math>C_i</math>	i	<math>C_i</math>	i	<math>C_i</math>	i	<math>C_i</math>
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	<math>S_i</math>	i	<math>S_i</math>	i	<math>S_i</math>	i	<math>S_i</math>
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-битных констант <math>C_i</math> и 68 констант <math>0<=S_i<=31</math>.

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

При длине блока 256 бит проводится 132 раундов. Поэтому задаются 132 64-битных константы <math>C_i</math> и 132 константы <math>0<=S_i<=63</math>.

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

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

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

Блок в 64 бита

Ключ К делится на 8 слов <math>KS_0=K_4,\ KF_0= K_3,\ KS_1=K_5,\ KF_1=K_2,</math> <math>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</math>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<math>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</math>, <math>\theta = \begin{cases}

 1,  & \mbox{if } \#=OR\\
 0, & \mbox{if } \#=AND

\end{cases}</math>

Это уравнение можно проверить, используя описание алгоритма, и учтя, что для последнего (младшего) разряда операции «+» и <math>\oplus</math> совпадают. Действительно, имеем соотношение <math>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</math>. Добавив к обеим частя равенства соотношение <math>a_i[0]=b_{i-1}[0]</math> получим требуемое.

Далее учитывая конкретные значения <math>S_i</math> можно показать, что <math>a_2[0]\oplus b_2[0] \oplus d_2[0]</math> зависит не от всех бит ключа и открытого текста, а именно:

<math>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])</math>

Рассмотрев 4 первых раунда дешифрования, можно установить, что <math>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])</math>.

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

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

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

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

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

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

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

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

Хэш-функция

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

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

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

• <math>TEXT=[TEXT_0...TEXT_{l-1}]</math> — расширенный текст, представленный в виде <math>l</math> блоков длины N.
• <math>H=[H_0...H_3]</math>, <math>V=[V_0...V_3]</math> -регистры длины N, состоящий из 4 n-битовых слов
• <math>T=[T_0...T_{15}]</math>б <math>M=[M_0...M_{15}]</math> -регистры длины 4N, состоящий из 15 n-битовых слов/

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

For i = 0 to l-1

{

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

{

<math>C_{2j} = T_{j mod 16}</math>

<math>C_{2*j+1} =M_{j mod16}</math>

}

<math>V = TEXT_i</math>

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

<math>[H_0...H_3]+=[V_0...V_3]</math>

For j=15 to 4

<math>T_j = T_{j-4}</math>

<math>[T_0...T_3]=[H_0...H_3]</math>

For j=15 to 4

<math>M_j = M_{j-4}</math>

<math>[M_0...M_3]=[V_0...V_3]</math>

}

For i= 0 to 3

{

For j=0 to L/2-1

<math>C_{2*j} = T_{j mod 16}</math>

H = NUSH(<math>M_i</math>)

For j=15 to 4

<math>T_j = T_{j-4}</math>

<math>[T_0...T_3]=[H_0...H_3]</math>

}

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

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

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

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

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

Вариант 1

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

<math>SYNC = SYNC \oplus NUSH(SYNC)</math>

For i =0 to COUNT −1

{

<math>GAMMA_i= NUSH(SYNC)</math>

SYNC = (SYNC + 65257) mod <math>2^N</math>

}

Вариант 2

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

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

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

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

For i =0 to COUNT −1

{

<math>[C_nC_{n+1}C_{n+2}C_{n+3}]=T</math>

<math>GAMMA_i= NUSH(SYNC_0)</math>

<math>SYNC_0 = (SYNC_0 + 65257 ) mod\ 2^N</math>

T = (T + 127) mod <math>2^N</math>

}

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

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

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

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

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

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

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

Шифрование

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

Выход: c||e

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

• <math>d=|b^r|</math>
• <math>M=NUSH^{-1}_d(e)</math>

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

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

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

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

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

Любое число <math>x \in [1, Q-1]</math>. В идеале, выбираемое с равномерным распределением.

Подписание

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

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

Подпись считается верной, если <math>d=Hash_m(Message||\ |g^e \diamondsuit b^d|)</math> Приведу доказательство корректности схемы. Очевидно, что корректность алгоритма равносильна верности равенства <math>c=|g^e \diamondsuit b^d|</math>.

Полученное равенство можно переписать в виде степеней генератора g подгруппы H в следующим образом: <math>|g^{r-x \circ d} \diamondsuit (g^{x \circ 1})^d|=|g^r|</math>. <math>A=|A|\ mod\ P</math> из определения. Откуда <math>g^{r-(x \circ d)+d(x \circ 1)} = g^r\ mod\ P</math>. Операция <math>\circ</math> линейна по второму аргументу с точностью до взятия равенства по модулю Q. В самом деле, <math>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_1M\ mod\ 2^N)}{2^N}+...+\frac {Ab_k+Q((Ab_nM\ mod\ 2^N)}{2^N}=A \circ b_1+...+A \circ b_k\ mod\ Q</math>. Следовательно, <math>d(x \circ 1) = x \circ d\ mod\ Q</math>. Откуда и следует доказываемое равенство, поскольку порядок элемента g равен Q.

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

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

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

Ссылки

• [www.cosic.esat.kuleuven.be/nessie/reports/phase1/uibwp3-007b.pdf NUSH в проекте NESSIE]
• [www.lancrypto.com/ Сайт компании Lan Crypto]
• [www.springerlink.com/content/rgj3472q78580088/fulltext.pdf Криптоанализ]
• [www.cosic.esat.kuleuven.be/nessie/workshop/submissions/nush.zip Авторское описание алгоритма]

Отрывок, характеризующий NUSH

Бородинское сражение с последовавшими за ним занятием Москвы и бегством французов, без новых сражений, – есть одно из самых поучительных явлений истории.
Все историки согласны в том, что внешняя деятельность государств и народов, в их столкновениях между собой, выражается войнами; что непосредственно, вследствие больших или меньших успехов военных, увеличивается или уменьшается политическая сила государств и народов.
Как ни странны исторические описания того, как какой нибудь король или император, поссорившись с другим императором или королем, собрал войско, сразился с войском врага, одержал победу, убил три, пять, десять тысяч человек и вследствие того покорил государство и целый народ в несколько миллионов; как ни непонятно, почему поражение одной армии, одной сотой всех сил народа, заставило покориться народ, – все факты истории (насколько она нам известна) подтверждают справедливость того, что большие или меньшие успехи войска одного народа против войска другого народа суть причины или, по крайней мере, существенные признаки увеличения или уменьшения силы народов. Войско одержало победу, и тотчас же увеличились права победившего народа в ущерб побежденному. Войско понесло поражение, и тотчас же по степени поражения народ лишается прав, а при совершенном поражении своего войска совершенно покоряется.
Так было (по истории) с древнейших времен и до настоящего времени. Все войны Наполеона служат подтверждением этого правила. По степени поражения австрийских войск – Австрия лишается своих прав, и увеличиваются права и силы Франции. Победа французов под Иеной и Ауерштетом уничтожает самостоятельное существование Пруссии.
Но вдруг в 1812 м году французами одержана победа под Москвой, Москва взята, и вслед за тем, без новых сражений, не Россия перестала существовать, а перестала существовать шестисоттысячная армия, потом наполеоновская Франция. Натянуть факты на правила истории, сказать, что поле сражения в Бородине осталось за русскими, что после Москвы были сражения, уничтожившие армию Наполеона, – невозможно.
После Бородинской победы французов не было ни одного не только генерального, но сколько нибудь значительного сражения, и французская армия перестала существовать. Что это значит? Ежели бы это был пример из истории Китая, мы бы могли сказать, что это явление не историческое (лазейка историков, когда что не подходит под их мерку); ежели бы дело касалось столкновения непродолжительного, в котором участвовали бы малые количества войск, мы бы могли принять это явление за исключение; но событие это совершилось на глазах наших отцов, для которых решался вопрос жизни и смерти отечества, и война эта была величайшая из всех известных войн…
Период кампании 1812 года от Бородинского сражения до изгнания французов доказал, что выигранное сражение не только не есть причина завоевания, но даже и не постоянный признак завоевания; доказал, что сила, решающая участь народов, лежит не в завоевателях, даже на в армиях и сражениях, а в чем то другом.
Французские историки, описывая положение французского войска перед выходом из Москвы, утверждают, что все в Великой армии было в порядке, исключая кавалерии, артиллерии и обозов, да не было фуража для корма лошадей и рогатого скота. Этому бедствию не могло помочь ничто, потому что окрестные мужики жгли свое сено и не давали французам.
Выигранное сражение не принесло обычных результатов, потому что мужики Карп и Влас, которые после выступления французов приехали в Москву с подводами грабить город и вообще не выказывали лично геройских чувств, и все бесчисленное количество таких мужиков не везли сена в Москву за хорошие деньги, которые им предлагали, а жгли его.

Представим себе двух людей, вышедших на поединок с шпагами по всем правилам фехтовального искусства: фехтование продолжалось довольно долгое время; вдруг один из противников, почувствовав себя раненым – поняв, что дело это не шутка, а касается его жизни, бросил свою шпагу и, взяв первую попавшуюся дубину, начал ворочать ею. Но представим себе, что противник, так разумно употребивший лучшее и простейшее средство для достижения цели, вместе с тем воодушевленный преданиями рыцарства, захотел бы скрыть сущность дела и настаивал бы на том, что он по всем правилам искусства победил на шпагах. Можно себе представить, какая путаница и неясность произошла бы от такого описания происшедшего поединка.
Фехтовальщик, требовавший борьбы по правилам искусства, были французы; его противник, бросивший шпагу и поднявший дубину, были русские; люди, старающиеся объяснить все по правилам фехтования, – историки, которые писали об этом событии.
Со времени пожара Смоленска началась война, не подходящая ни под какие прежние предания войн. Сожжение городов и деревень, отступление после сражений, удар Бородина и опять отступление, оставление и пожар Москвы, ловля мародеров, переимка транспортов, партизанская война – все это были отступления от правил.
Наполеон чувствовал это, и с самого того времени, когда он в правильной позе фехтовальщика остановился в Москве и вместо шпаги противника увидал поднятую над собой дубину, он не переставал жаловаться Кутузову и императору Александру на то, что война велась противно всем правилам (как будто существовали какие то правила для того, чтобы убивать людей). Несмотря на жалобы французов о неисполнении правил, несмотря на то, что русским, высшим по положению людям казалось почему то стыдным драться дубиной, а хотелось по всем правилам стать в позицию en quarte или en tierce [четвертую, третью], сделать искусное выпадение в prime [первую] и т. д., – дубина народной войны поднялась со всей своей грозной и величественной силой и, не спрашивая ничьих вкусов и правил, с глупой простотой, но с целесообразностью, не разбирая ничего, поднималась, опускалась и гвоздила французов до тех пор, пока не погибло все нашествие.
И благо тому народу, который не как французы в 1813 году, отсалютовав по всем правилам искусства и перевернув шпагу эфесом, грациозно и учтиво передает ее великодушному победителю, а благо тому народу, который в минуту испытания, не спрашивая о том, как по правилам поступали другие в подобных случаях, с простотою и легкостью поднимает первую попавшуюся дубину и гвоздит ею до тех пор, пока в душе его чувство оскорбления и мести не заменяется презрением и жалостью.


Одним из самых осязательных и выгодных отступлений от так называемых правил войны есть действие разрозненных людей против людей, жмущихся в кучу. Такого рода действия всегда проявляются в войне, принимающей народный характер. Действия эти состоят в том, что, вместо того чтобы становиться толпой против толпы, люди расходятся врозь, нападают поодиночке и тотчас же бегут, когда на них нападают большими силами, а потом опять нападают, когда представляется случай. Это делали гверильясы в Испании; это делали горцы на Кавказе; это делали русские в 1812 м году.
Войну такого рода назвали партизанскою и полагали, что, назвав ее так, объяснили ее значение. Между тем такого рода война не только не подходит ни под какие правила, но прямо противоположна известному и признанному за непогрешимое тактическому правилу. Правило это говорит, что атакующий должен сосредоточивать свои войска с тем, чтобы в момент боя быть сильнее противника.
Партизанская война (всегда успешная, как показывает история) прямо противуположна этому правилу.
Противоречие это происходит оттого, что военная наука принимает силу войск тождественною с их числительностию. Военная наука говорит, что чем больше войска, тем больше силы. Les gros bataillons ont toujours raison. [Право всегда на стороне больших армий.]
Говоря это, военная наука подобна той механике, которая, основываясь на рассмотрении сил только по отношению к их массам, сказала бы, что силы равны или не равны между собою, потому что равны или не равны их массы.
Сила (количество движения) есть произведение из массы на скорость.
В военном деле сила войска есть также произведение из массы на что то такое, на какое то неизвестное х.
Военная наука, видя в истории бесчисленное количество примеров того, что масса войск не совпадает с силой, что малые отряды побеждают большие, смутно признает существование этого неизвестного множителя и старается отыскать его то в геометрическом построении, то в вооружении, то – самое обыкновенное – в гениальности полководцев. Но подстановление всех этих значений множителя не доставляет результатов, согласных с историческими фактами.
А между тем стоит только отрешиться от установившегося, в угоду героям, ложного взгляда на действительность распоряжений высших властей во время войны для того, чтобы отыскать этот неизвестный х.
Х этот есть дух войска, то есть большее или меньшее желание драться и подвергать себя опасностям всех людей, составляющих войско, совершенно независимо от того, дерутся ли люди под командой гениев или не гениев, в трех или двух линиях, дубинами или ружьями, стреляющими тридцать раз в минуту. Люди, имеющие наибольшее желание драться, всегда поставят себя и в наивыгоднейшие условия для драки.
Дух войска – есть множитель на массу, дающий произведение силы. Определить и выразить значение духа войска, этого неизвестного множителя, есть задача науки.
Задача эта возможна только тогда, когда мы перестанем произвольно подставлять вместо значения всего неизвестного Х те условия, при которых проявляется сила, как то: распоряжения полководца, вооружение и т. д., принимая их за значение множителя, а признаем это неизвестное во всей его цельности, то есть как большее или меньшее желание драться и подвергать себя опасности. Тогда только, выражая уравнениями известные исторические факты, из сравнения относительного значения этого неизвестного можно надеяться на определение самого неизвестного.
Десять человек, батальонов или дивизий, сражаясь с пятнадцатью человеками, батальонами или дивизиями, победили пятнадцать, то есть убили и забрали в плен всех без остатка и сами потеряли четыре; стало быть, уничтожились с одной стороны четыре, с другой стороны пятнадцать. Следовательно, четыре были равны пятнадцати, и, следовательно, 4а:=15у. Следовательно, ж: г/==15:4. Уравнение это не дает значения неизвестного, но оно дает отношение между двумя неизвестными. И из подведения под таковые уравнения исторических различно взятых единиц (сражений, кампаний, периодов войн) получатся ряды чисел, в которых должны существовать и могут быть открыты законы.
Тактическое правило о том, что надо действовать массами при наступлении и разрозненно при отступлении, бессознательно подтверждает только ту истину, что сила войска зависит от его духа. Для того чтобы вести людей под ядра, нужно больше дисциплины, достигаемой только движением в массах, чем для того, чтобы отбиваться от нападающих. Но правило это, при котором упускается из вида дух войска, беспрестанно оказывается неверным и в особенности поразительно противоречит действительности там, где является сильный подъем или упадок духа войска, – во всех народных войнах.
Французы, отступая в 1812 м году, хотя и должны бы защищаться отдельно, по тактике, жмутся в кучу, потому что дух войска упал так, что только масса сдерживает войско вместе. Русские, напротив, по тактике должны бы были нападать массой, на деле же раздробляются, потому что дух поднят так, что отдельные лица бьют без приказания французов и не нуждаются в принуждении для того, чтобы подвергать себя трудам и опасностям.


Так называемая партизанская война началась со вступления неприятеля в Смоленск.
Прежде чем партизанская война была официально принята нашим правительством, уже тысячи людей неприятельской армии – отсталые мародеры, фуражиры – были истреблены казаками и мужиками, побивавшими этих людей так же бессознательно, как бессознательно собаки загрызают забеглую бешеную собаку. Денис Давыдов своим русским чутьем первый понял значение той страшной дубины, которая, не спрашивая правил военного искусства, уничтожала французов, и ему принадлежит слава первого шага для узаконения этого приема войны.
24 го августа был учрежден первый партизанский отряд Давыдова, и вслед за его отрядом стали учреждаться другие. Чем дальше подвигалась кампания, тем более увеличивалось число этих отрядов.
Партизаны уничтожали Великую армию по частям. Они подбирали те отпадавшие листья, которые сами собою сыпались с иссохшего дерева – французского войска, и иногда трясли это дерево. В октябре, в то время как французы бежали к Смоленску, этих партий различных величин и характеров были сотни. Были партии, перенимавшие все приемы армии, с пехотой, артиллерией, штабами, с удобствами жизни; были одни казачьи, кавалерийские; были мелкие, сборные, пешие и конные, были мужицкие и помещичьи, никому не известные. Был дьячок начальником партии, взявший в месяц несколько сот пленных. Была старостиха Василиса, побившая сотни французов.
Последние числа октября было время самого разгара партизанской войны. Тот первый период этой войны, во время которого партизаны, сами удивляясь своей дерзости, боялись всякую минуту быть пойманными и окруженными французами и, не расседлывая и почти не слезая с лошадей, прятались по лесам, ожидая всякую минуту погони, – уже прошел. Теперь уже война эта определилась, всем стало ясно, что можно было предпринять с французами и чего нельзя было предпринимать. Теперь уже только те начальники отрядов, которые с штабами, по правилам ходили вдали от французов, считали еще многое невозможным. Мелкие же партизаны, давно уже начавшие свое дело и близко высматривавшие французов, считали возможным то, о чем не смели и думать начальники больших отрядов. Казаки же и мужики, лазившие между французами, считали, что теперь уже все было возможно.
22 го октября Денисов, бывший одним из партизанов, находился с своей партией в самом разгаре партизанской страсти. С утра он с своей партией был на ходу. Он целый день по лесам, примыкавшим к большой дороге, следил за большим французским транспортом кавалерийских вещей и русских пленных, отделившимся от других войск и под сильным прикрытием, как это было известно от лазутчиков и пленных, направлявшимся к Смоленску. Про этот транспорт было известно не только Денисову и Долохову (тоже партизану с небольшой партией), ходившему близко от Денисова, но и начальникам больших отрядов с штабами: все знали про этот транспорт и, как говорил Денисов, точили на него зубы. Двое из этих больших отрядных начальников – один поляк, другой немец – почти в одно и то же время прислали Денисову приглашение присоединиться каждый к своему отряду, с тем чтобы напасть на транспорт.
– Нет, бг'ат, я сам с усам, – сказал Денисов, прочтя эти бумаги, и написал немцу, что, несмотря на душевное желание, которое он имел служить под начальством столь доблестного и знаменитого генерала, он должен лишить себя этого счастья, потому что уже поступил под начальство генерала поляка. Генералу же поляку он написал то же самое, уведомляя его, что он уже поступил под начальство немца.
Распорядившись таким образом, Денисов намеревался, без донесения о том высшим начальникам, вместе с Долоховым атаковать и взять этот транспорт своими небольшими силами. Транспорт шел 22 октября от деревни Микулиной к деревне Шамшевой. С левой стороны дороги от Микулина к Шамшеву шли большие леса, местами подходившие к самой дороге, местами отдалявшиеся от дороги на версту и больше. По этим то лесам целый день, то углубляясь в середину их, то выезжая на опушку, ехал с партией Денисов, не выпуская из виду двигавшихся французов. С утра, недалеко от Микулина, там, где лес близко подходил к дороге, казаки из партии Денисова захватили две ставшие в грязи французские фуры с кавалерийскими седлами и увезли их в лес. С тех пор и до самого вечера партия, не нападая, следила за движением французов. Надо было, не испугав их, дать спокойно дойти до Шамшева и тогда, соединившись с Долоховым, который должен был к вечеру приехать на совещание к караулке в лесу (в версте от Шамшева), на рассвете пасть с двух сторон как снег на голову и побить и забрать всех разом.
Позади, в двух верстах от Микулина, там, где лес подходил к самой дороге, было оставлено шесть казаков, которые должны были донести сейчас же, как только покажутся новые колонны французов.
Впереди Шамшева точно так же Долохов должен был исследовать дорогу, чтобы знать, на каком расстоянии есть еще другие французские войска. При транспорте предполагалось тысяча пятьсот человек. У Денисова было двести человек, у Долохова могло быть столько же. Но превосходство числа не останавливало Денисова. Одно только, что еще нужно было знать ему, это то, какие именно были эти войска; и для этой цели Денисову нужно было взять языка (то есть человека из неприятельской колонны). В утреннее нападение на фуры дело сделалось с такою поспешностью, что бывших при фурах французов всех перебили и захватили живым только мальчишку барабанщика, который был отсталый и ничего не мог сказать положительно о том, какие были войска в колонне.
Нападать другой раз Денисов считал опасным, чтобы не встревожить всю колонну, и потому он послал вперед в Шамшево бывшего при его партии мужика Тихона Щербатого – захватить, ежели можно, хоть одного из бывших там французских передовых квартиргеров.


Был осенний, теплый, дождливый день. Небо и горизонт были одного и того же цвета мутной воды. То падал как будто туман, то вдруг припускал косой, крупный дождь.
На породистой, худой, с подтянутыми боками лошади, в бурке и папахе, с которых струилась вода, ехал Денисов. Он, так же как и его лошадь, косившая голову и поджимавшая уши, морщился от косого дождя и озабоченно присматривался вперед. Исхудавшее и обросшее густой, короткой, черной бородой лицо его казалось сердито.