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

РСЛОС и фильтрующая функция ${\displaystyle F}$

Примитивный многочлен, ассоциированный с РСЛОС, имеет вид:

${\displaystyle P(X)=X^{192}+X^{189}+X^{188}+X^{169}+X^{156}+X^{155}+X^{132}+X^{131}+X^{94}+X^{77}+X^{46}+X^{17}+X^{16}+X^{5}+1}$

Обозначим через ${\displaystyle s=(s_{t})|_{t\geqslant 0}}$ ^[2] последовательность битов, полученных с выхода РСЛОС, тогда правило вычисления бита на выходе РСЛОС имеет вид:

${\displaystyle s_{192+n}=s_{187+n}\oplus s_{176+n}\oplus s_{175+n}\oplus s_{146+n}\oplus s_{115+n}\oplus s_{98+n}\oplus s_{61+n}\oplus s_{60+n}\oplus s_{37+n}\oplus s_{36+n}\oplus s_{23+n}\oplus s_{4+n}\oplus s_{3+n}\oplus s_{n}}$

Для усложнений зависимостей между битами ${\displaystyle s_{t}}$ РСЛОС и битами ${\displaystyle z_{t}}$ используется нелинейная фильтрующая функция от семи переменных ${\displaystyle F(x_{1},...x_{7})}$ . В каждый такт ${\displaystyle F}$ применяется дважды — к битам, стоящим на разных позициях в РСЛОС. Обозначим ${\displaystyle F1(x_{i_{1}},...,x_{i_{7}})}$ и ${\displaystyle F2(x_{i_{8}},...x_{i_{14}})}$ функции такие, что

${\displaystyle F1(x_{i_{1}},...,x_{i_{7}})=F(x_{i_{1}},...,x_{i_{7}})}$

и

${\displaystyle F2(x_{i_{8}},...,x_{i_{14}})=F(x_{i_{8}},...,x_{i_{14}})}$ , где

${\displaystyle F(x_{i_{1}},...,x_{i_{7}})=\sum _{1\leqslant j<k\leqslant 7}{x_{i_{j}}x_{i_{k}}}}$

Пусть

${\displaystyle y1=(y1_{t})|_{t\geqslant 0}=F(s_{i_{1}+t},...,s_{i_{7}+t})}$

${\displaystyle y2=(y2_{t})|_{t\geqslant 0}=F(s_{i_{8}+t},...,s_{i_{14}+t})}$

${\displaystyle \mathbf {y} =y1_{0},y2_{0},y1_{1},y2_{1},...}$ .

Позиции битов РСЛОС, которые являются аргументами ${\displaystyle F1}$ и ${\displaystyle F2}$ :

• для ${\displaystyle F1}$ : 1, 32, 40, 101, 164, 178, 187;
• для ${\displaystyle F2}$ : 6, 8, 60, 116, 145, 181, 191.

Тогда

${\displaystyle \mathbf {y} 1_{t}=F(s_{t+1},s_{t+32},s_{t+40},s_{t+101},s_{t+164},s_{t+178},s_{t+187})}$

${\displaystyle \mathbf {y} 2_{t}=F(s_{t+6},s_{t+8},s_{t+60},s_{t+116},s_{t+145},s_{t+181},s_{t+191})}$ .

Механизм выборки ABSG

Механизм выборки ABSG используется для предотвращения алгебраических атак и некоторых видов быстрых корреляционных атак с помощью десинхронизации фильтрованных битов РСЛОС ${\displaystyle y_{0},y_{1},y_{2},...}$ и битов гамма ${\displaystyle z_{0},z_{1},z_{2},...}$ . Работа механизма выборки ABSG заключается в разбивке последовательности ${\displaystyle \mathbf {y} =y1_{0},y2_{0},y1_{1},y2_{1},...}$ на подпоследовательности вида ${\displaystyle (b,b^{i},{\bar {b}})}$ , где ${\displaystyle b\in {(0,1)}}$ , и выдачи ${\displaystyle b}$ , если ${\displaystyle i=0}$ , и ${\displaystyle {\bar {b}}}$ в другом случае.

Алгоритм работы ABSG

Input: (${\displaystyle y_{0},y_{1},y_{2},\dots }$ )

Set: ${\displaystyle i=0}$ , ${\displaystyle j=0}$

Repeat the following steps:

1. ${\displaystyle e=y_{i}}$ , ${\displaystyle z_{j}=y_{i+1}}$ ;
2. ${\displaystyle i=i+1}$ ;
3. while (${\displaystyle y_{i}}$ ==${\displaystyle {\bar {e}}}$ ) ${\displaystyle i=i+1}$ ;
4. ${\displaystyle i=i+1}$ ;
5. output ${\displaystyle z_{j}}$ ;
6. ${\displaystyle j=j+1}$ ;

Пример:

пусть ${\displaystyle y=(0101001110100100011101)}$ , тогда, соответствующая последовательность на выходе ABSG имеет вид ${\displaystyle z=(10111010)}$ .

В среднем, ${\displaystyle 3n}$ бит, поступившем на вход ABSG, соответствует ${\displaystyle n}$ бит на выходе, что и видно из примера.

Инициализация начального состояния РСЛОС

Сектретный ключ ${\displaystyle K}$ имеет длину 80 бит, открытый ключ ${\displaystyle IV}$ (Initialization Vector) имеет длину 64 бита, но дополняется нулями до 80 бит. Пусть ${\displaystyle x_{0},...,x_{191}}$ биты РСЛОС. Тогда начальное состояние РСЛОС вычисляется следующим образом:

${\displaystyle x_{i}={\begin{cases}K_{i}\lor IV_{i}~for~0\leqslant i\leqslant 56\\K_{i-56}\lor {\bar {IV_{i-56}}}~for~56\leqslant i\leqslant 111\\K_{i-112}\oplus IV_{i-112}~for~112\leqslant i\leqslant 191\\\end{cases}}}$

Видно, что число всевозможных начальных состояний РСЛОС это ${\displaystyle 2^{56+56+24}}$ .

РСЛОС

Для предотвращения атак компромисс «время-память» длина РСЛОС должна быть не меньше 160 бит. Также РСЛОС должен быть прост в аппаратной реализации. Исходя из этих факторов, размер РСЛОС был выбран равным 192 битам.

Вес Хэмминга примитивного многочлена ${\displaystyle P(x)}$ должен быть достаточно большим, чтобы предотвратить быструю корреляционную атаку, но с дургой стороны вес Хэмминга примитивного многочлена ${\displaystyle P(x)}$ не должен быть слишком большим, чтобы не увеличивать время работы шифра в аппаратной реализации.

Фильтрующая функция ${\displaystyle F}$

Фильтрующая функция ${\displaystyle F}$ должна быть равновесной^[3] и для предотвращения дифференциального криптоанализа должна удовлетворять propagation criterion: функция ${\displaystyle D_{u}F(x)=F(x)+F(x+u)}$ должна быть равновесной. Также, для упрощения аппаратной реализации, желательно, чтобы функция ${\displaystyle F}$ была симметричной, то есть, чтобы значение функции ${\displaystyle F}$ зависело только от веса Хэмминга её аргумента (набора x_1,…x_7). Всем этим требованием удовлетворяет квадратичная функция вида:

${\displaystyle F(x_{i_{1}},...,x_{i_{7}})=\sum _{1\leqslant j<k\leqslant 7}{x_{i_{j}}x_{i_{k}}}}$ ,

которая и используется, как фильтрующая функция шифра Decim.