BugTraq.Ru: Общая схема вероятностной поточной шифрсистемы

Общая схема вероятностной поточной шифрсистемы
Д.Н. Колегов
Опубликовано: dl, 29.05.06 04:25

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

Ключевые слова: шифрсистема, поточная шифрсистема, вероятностная шифрсистема, стойкость

Введение

Все шифрсистемы можно разделить на два класса - вероятностные и детерминированные. В первых результат шифрования зависит не только от ключа шифрования и открытого текста, как во вторых, но и от некоторого случайного элемента - рандомизатора. Среди современных шифрсистем большинство являются детерминированными и только единицы вероятностными. Вместе с тем известно, что внесение элемента случайности в процесс шифрования позволяет получить следующие важнейшие свойства шифрсистемы [1, 2, 3]:

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

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

В настоящее время на практике в качестве вероятностных поточных шифрсистем широко используются поточные режимы блочных шифров [1], в которых рандомизация шифртекста достигается за счет случайного выбора векторов инициализации, называемых также синхропосылками, и передачи их, как правило, в открытом виде вместе с криптограммой открытого текста. Другим методом рандомизации шифртекста в блочных алгоритмах является добавление в открытый текст наборов случайных букв с последующим шифрованием преобразованного текста [1,2].

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

Под шифром всюду далее понимается любой набор из пяти объектов = (X, K, Y, E, D), где X, K, Y - множества соответственно сообщений (открытых текстов), ключей, криптограмм (шифртекстов), E и D - функции, E: K × X Y, D: K × Y X, связанные соотношением обратимости E(k, x) = y D(k, y) = x для всех x X и y Y и называемые функциями шифрования и расшифрования соответственно. Предполагается, что сообщения, ключи, криптограммы и рандомизаторы являются словами в некоторых алфавитах. Алфавит слов в некотором множестве V обозначается A_V. Предполагается также, что всякий ключ k в K представляется парой взаимозависимых ключей k₁, k₂ так, что k = (k₁, k₂), где k₁ является ключом шифрования: y = E(k, x) = E(k₁, x), а k₂ - ключом расшифрования: D(k, y) = D(k₂, y) = x. В случае, если k₂ вычисляется по k₁ трудно (с экспоненциальной сложностью), то называется шифром с открытым ключом, в противном случае - шифром с закрытым ключом.

Определение вероятностной поточной шифрсистемы PSC

Схематически вероятностная поточная шифрсистема (PSC) изображена на рис. 1.

Рис. 1. Схема вероятностной поточной шифрсистемы PSC

Она состоит из ключевой системы K и блоков рандомизации Ra и шифрования En. Состав ключевой системы здесь не раскрывается, ее функция заключается в выработке тройки ключей k_i K_i, k_w K_w и k_g K_g, называемых ключами соответственно инициализации, свидетельства и генератора. Блок рандомизации состоит из источника (множества) рандомизаторов R и узлов свидетельства W и инициализации h. Формально узел свидетельства является некоторым шифром W = (R, K_w, S, e', d'). Он предназначен для создания свидетельства s = e'(r, k_w) S рандомизатора r R в зависимости от ключа свидетельства k_w. Формально узел инициализации является некоторой функцией h: R × K_i A_X × A_Z × Q. Он создает для блока шифрования вектор инициализации v = (x₀, z₀, q₀) = h(r, k_i). Блок шифрования состоит из генератора ключевых потоков G, представляющего собой множество конечных автоматов M_k = (A_X × A_Z, Q, Г, _k, _k), k Kg, с входным алфавитом A_X × A_Z, выходным алфавитом Г, множеством состояний Q и функциями переходов и выходов соответственно _k: (A_X × A_Z) × Q Q и _k: (A_X × A_Z) × Q Г, и шифра C = (A_X, A_Z, Г, e, d).

При фиксированных ключах k_i, k_w и k = k_g шифрсистема PSC на стороне отправителя открытый текст x = x₁ ... x_l X преобразует в шифртекст z = z₁ ... z_l Z следующим образом: выбирается случайно рандомизатор r R, вычисляются его свидетельство s = e'(r, k_w), вектор инициализации (x₀, z₀, q₀) = h(r, k_i), ключевой поток = ₁ ... _l, где для любого t = 1, ..., l

_t = _k((x_t-1, z_t-1), q_t), q_t = _k((x_t-1, z_t-1), q_t-1) и z_t = e(_t, x_t).

Пара (s, z) передается в канал связи. На стороне получателя шифрсистема PSC восстанавливает открытый текст, вычисляя последовательно r = d'(s, k_w), (x₀, z₀, q₀) = h(r, k_i) и для t = 1, ..., l

_t = _k((x_t-1, z_t-1), q_t), q_t = _k((x_t-1, z_t-1), q_t-1) и x_t = d(_t, z_t).

Классификация шифрсистем PSC

PSC называется шифрсистемой с открытым рандомизатором, если e'(r, k_t) = r для всех k_w K_w. Она называется шифрсистемой с закрытым рандомизатором, если при неизвестном ключе k_w значение рандомизатора r трудно вычислимо по его свидетельству s = e'(r, k_w). PSC называется шифрсистемой с открытым или закрытым ключом, если соответственно таковым является шифр W в ней. Она называется синхронной, если все автоматы M_k в G автономные: их функции

_k((x, z), q) и

_k((x, z), q) зависят от (x, z) фиктивно, т.е. являются по существу функциями только от q. В этом случае, естественно, считается, что значения функции h лежат в Q, т.е. h: R × K_i Q. PSC называется шифрсистемой с закрытым вектором инициализации, если при неизвестном ключе k_i значение h(r, k_i) трудно вычислимо по рандомизатору r. Она называется шифрсистемой с тождественной инициализацией, если h(r, k_i) = r для всех k_i K_i.

Примеры шифрсистем PSC

Многочисленные примеры шифрсистемы PSC различных типов можно получить, выбирая в ней различными способами компоненты W, G, C, h, K, R. Например, при подходящих h, K, R в качестве (W, G, C) в PSC могут выступать комбинации: (AES, RC4, + mod 256), (RSA, BBS, ), (RSA, RSA,

), (

, LFSR+filter,

) и другие [4]. Примером шифрсистемы PSC с закрытым вектором инициализации может служить PSC, в которой ключом k_i служит многочлен f(x) над конечным полем, обновляемый после зашифрования не более n-1 открытых текстов, где n - степень f, и h(r, k_i) = f(r). В других PSC с закрытым вектором инициализации в роли h могут использоваться различные ключевые хэш-функции. Примерами шифрсистем с тождественной инициализацией являются блочные шифры в режиме поточного шифрования, а также синхронные поточные шифры, построенные на основе генераторов ключевого потока с функциональными блоками в качестве закрытого ключа.

Стойкие шифрсистемы PSC с нестойкими компонентами

Понимая под стойкостью вычислительную стойкость к атакам с известным открытым текстом с целью определения неизвестного ключа, рассмотрим шифрсистему PSC в предположении, что требованию стойкости удовлетворяет лишь некоторые из ее компонент. Так, если стоек генератор в G, то криптоаналитик, зная x, s, z и, следовательно, ключевой поток на выходе генератора, не сможет вычислить вектор инициализации. В отсутствие последнего он не может знать рандомизатора и, следовательно, не может провести ни атаку на R (с целью предсказания следующего рандомизатора), ни атаку с известным открытым текстом на W. Если же стойкими являются шифр W и источник рандомизаторов R, то можно допустить нестойкий генератор G. То же самое возможно в случае односторонней функции h.

Литература

Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. - М.: Издательство ТРИУМФ, 2003.
Асосков А.В., Иванов М.А., Мирский А.А., Рузин А.В., Сланин А.В., Тютвин А.Н. Поточные шифры. - М.: КУДИЦ-ОБРАЗ, 2003. - 336 с.
Молдовян. Скоростные блочные шифры. - СПб.: Издательство БХВ-Петербург, 2002.
Агибалов Г.П. Вероятностные схемы симметричного поточного шифрования над конечным полем // Вестник Томского государственного университета. Приложение. - 2005. - N 14 - С. 39 - 42.

обсудить \| все отзывы (0)
	[26549; 34; 6.44]