WikiSort.ru - Не сортированное

Шифрование

Введём обозначения. Пусть ${\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

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

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

Расписание операции #

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

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

В качестве примера рассмотрим вторую атаку на шифр с длиной блока 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}}$ зависят не от всех битов входного и выходного блоков. Соответственно, среди выборки блоков открытого и зашифрованных текстов должны быть блоки с отличающимися соответствующими битами. Работа алгоритма с меньшим числом известных текстов возможна, но тогда с меньшей вероятностью найденное «максимальное» число на втором этапе будет действительно соответствовать настоящему ключу в виду непревышения корня из дисперсии числа событий «уравнение выполняется» над мат. ожиданием разницы чисел этого события и ему противоположного (можно рассмотреть схему Бернулли, где вероятность «успеха» равна вероятности выполнения соотношения).

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

Хеш-функция

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

• Добавить к тексту единичный бит
• Добавить столько нулей, чтобы получился текст с длиной, кратной 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. Есть два варианта этого шифра.

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

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

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