1.7 Композиционные шифры

1.7.1 Алгебра секретных систем

Впервые Клод Шеннон в своей работе “Математическая теория криптографии” построил алгебраическую модель секретной системы, введя понятия суммы и произведения секретных систем, и именно благодаря его трудам криптология перешла в научно-техническую сферу исследования.

Взвешенная сумма

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

S = pT + qR p + q = 1

p и q, соответственно, вероятности использования системы T и R. Ключ системы S должен содержать информацию о используемой системе. Любая система T может быть записана в виде:

T = p₁T₁ + p₂T₂ + … + p_nT_n ∑ p_i = 1

T_i и p_i соответственно операция шифрования с помощью i-ого ключа и соответствующая вероятность использования i-ого ключа. Таким образом, можно образовать сумму нескольких систем:

T = p₁T₁ + p₂R₂ + … + p_nU_n ∑ p_i = 1

Рисунок 1.1 взвешенная сумма секретных систем

Произведение

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

S = TR

Ключ производной системы S объединяет ключи T и R систем.

Системы, у которых пространства P и C можно отождествить, называются эндоморфными.

Рисунок 1.2 произведение секретных систем

Свойства алгебры секретных систем

• произведение не всегда коммутативно, т.е.

TR ≠ RT

• произведение ассоциативно, т.е.

R(ST) = (RS)T = RST

• выполняется взвешенный ассоциативный закон сложения:

p(p’T + q’R) + qS = pp’T + pq’R + qS

• выполняется дистрибутивные законы:

S(pT + qR) = pST + qSR

(pT + qR)S = pTS + qRS

В листинге 1.1 представлены прототипы двух различных секретных систем (шифрующие функции T и R) и их сумма и произведение. При суммировании, мы используем одну из представленных систем в зависимости от третьего бита ключа, а при произведении – обе системы.

bit8 *T(bit8 *text, bit32 length, bit32 k)

{…}

bit8 *R(bit8 *text, bit32 length, bit32 k)

{…}

// Сложение

bit8 *add _T_R(bit8 *text, int length, bit32 k)

{

if ((k>>3) & 0x01 != 0)

{

return T(text, length, k);

}

else

{

return R(text, length, k);

}

}

// Умножение

bit8 *mul_T_R(bit8 *text, bit32 length, bit32 k)

{

T(text, length, k);

R(text, length, k);

return text;

}

Листинг 1.1 алгебра секретных систем

1.7.2 Теория композиционных шифров

Таким образом, мы можем строить сложные композиции, такие как сумма произведений и произведение сумм. Именно такие композиции создавал и исследовал Клод Шеннон. Главная идея композиционных шифров состоит в создании криптографически стойкой системы из относительно простых криптографических преобразований путем их многократного применения. Для своих исследований в качестве “относительно простых криптографических преобразований” Шеннон использовал шифры перестановки и замены, которые, по его словам, успешно решали две поставленные им задачи:

• Рассеивание: Шеннон под рассеиванием понимал некое абстрактное преобразование, при котором изменение одного бита входа влечет за собой изменение каждого бита выхода с вероятностью 50%, т.е. может повлечь за собой изменение значений почти всех битов выхода. Такое свойство шифра называется лавинным эффектом (avalanche).

Следствия:

• Качество лавинного эффекта определяется используемыми методами рассеивания (diffusion).

• Рассеивание сильно затрудняет поиск зависимостей между входом и выходом.

• Идеальное рассеивание выступает в роли функции, распределяющей ключи равномерно по ключевому пространству, что значительно затрудняет поиск эквивалентных ключей.

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

• Возникает проблема: необходимо обеспечить детерминированность всех операций шифра для возможности обратного преобразования, что негативно отражается на свойстве лавинного эффекта.

• Полнота: Задача полноты заключается в организации нетривиальной зависимости каждого бита выхода шифра от всех без исключения битов входа. Если говорить строго, то для каждого бита выхода j и любого бита входа i необходимо потребовать наличие двух идентичных входов, отличающихся лишь битом i.

Следствия:

• Полнота шифра по большей степени зависит от его перемешивающих свойств (confusion).

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

• Несоблюдение свойства полноты может привести к возможности выделения групп входа и выхода, не зависящих друг от друга.

Рисунок 1.3 Задачи преобразований

а – полнота

б – рассеивание

Совокупность этих двух свойств, полноты и рассеивания, обеспечивает шифру глобальную зависимость от ключа и открытого текста. Если ключ взаимодействует со входом до криптографического преобразования, то полнота для ключа может и не обеспечиваться, как в случае ГОСТ 28147-89. Иначе, если построение простейших криптографических функций зависит от ключа, необходимо чтобы они удовлетворяли свойству полноты для всех (почти всех) значений ключа.

Ограничение, которое накладывается на композиционные шифры, предложенные Шенноном, заключается в необходимости потребовать обратимость всех простейших криптографических функций. В противном случае процесс расшифрования не представляется возможным, даже если известен секретный ключ. Также это ограничение негативно сказавается на програмной и, тем более, аппаратной реализации шифров, построеных по данному принципу (Листинг 1.2).

// простейшая криптографическая функция T

// обратная криптографическая функция к T эквивалентна T

uint8 *T(uint8 *text, int length, uint32 k)

{

for(int i = 0; i < length; i++)

{

text[i] ^= i;

}

return text;

}

// простейшая криптографическая функция R

uint8 *R(uint8 *text, int length, uint32 k)

{

for(int i = 0; i < length; i++)

{

text[i] = (text[i] + i) % 0xFF;

}

return text;

}

// криптографическая функция, обратная R

uint8 *R_reverce(uint8 *text, int length, uint32 k)

{

for(int i = 0; i < length; i++)

{

text[i] = (text[i] - i) % 0xFF;

}

return text;

}

Листинг 1.2 обратимость простейших криптографических функций