Подход к созданию трудноанализируемых шифров

Подход к созданию трудноанализируемых шифров

Введение

 

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

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

1. Зачем это надо?

1.1 Да, это надо

 

А зачем надо шифроваться  вообще? Есть ли что скрывать обычному законопослушному гражданину от "всесильных" спецслужб (или разных тёмных личностей)? Представляет ли ценность для кого-нибудь банальная личная жизнь обычных  людей?

Думаю лишний раз трогать хакеров и кракеров не надо, это наверно всем порядком поднадоело, а вот вспомнить недавний скандал в Европарламенте, связанный с системой тотального электронного шпионажа «Эшелон», стоит (статья в одном из номеров журнала «Эхо Планеты» за этот год). В Европарламенте обсуждался вопрос, о том, что же всё-таки делать дальше, ведь никто не собирался выкидывать «Эшелон» на свалку только из-за того, что Европарламенту это не понравилось! И одним из выходов было признание необходимости тотального использования криптосистем.

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

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

Да, ещё. Про существование всяких средств перехвата излучения  мониторов и т.п. читал много, а вот про реальное их использование для отлова преступников не слышал. Всё сводилось к банальному взводу ОМОНА (или что у них там) и «Руки от клавы !» с выносом сервера. Да и то, насколько помню, проваливались такие преступники из-за своей жадности, а не из-за того что кто-то что-то у них подслушал. Вполне может быть что такие случаи не афишируются, и поэтому информации минимум.

1.2 Основная  идея

 

Некоторыми из требований, предъявляемых к криптосистемам, являются [1]:

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

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

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

 

2. Немного теории

 

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

Гаммирование – наложение  гаммы (обычно псевдослучайной последовательности) на текст обратимым образом.

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

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

Наша задача состоит в том, чтобы  обеспечить такое гаммирование с  обратной связью, которое бы приводило  к полному изменению текста на выходе даже при несущественном изменении  входного. Рассмотрим немного теории (излагается сокращенно по [2]).

2.1 М-последовательности

 

Одним из наиболее широко применяемых  способов формирования псевдослучайных  последовательностей является способ, основанный на использовании соотношения:

(2.1)

 

где k - номер такта; a_kÎ{0, 1}-символы последовательности;

a_iÎ{0, 1}-постоянные коэффициенты;

- операция  суммирования по модулю два  m логических переменных.

 

При соответствующем  выборе коэффициентов a_i, на основании характеристического полинома j(x)=1Åa₁x¹Åa₂x²a₃x³…a_m-1x^m-1a_mx^m, который должен быть примитивным, последовательность бит {a_k} имеет максимальную длину, равную 2^m-1. Такая последовательность называется M-последовательностью.

Главное преимущество метода формирования псевдослучайных последовательностей по соотношению (2.1) - простота его реализации, как программной, так и аппаратурной.

Некоторыми из наиболее важных для нас свойств М-последовательностей  являются:

• максимальная близость М-последовательности по характеристикам к случайной;
• период последовательности, формируемой по выражению (2.1), определяется старшей степенью порождающего полинома j(x) и равен L = 2^m-1;
• для заданного полинома j(х) существует L различных  
  M-последовательностей, отличающихся фазовым сдвигом.

2.2 Сжатие двоичной  последовательности в сигнатуру

 

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

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

 

                                                       (2.2)

 

где y(k) Î {0,1} – k-й символ сжимаемой последовательности {y(k)}, k = 1..l; a_iÎ{0,1} – коэффициенты порождающего полинома j(x); a_i(k-1)Î{0,1} – содержимое i-го элемента памяти в k-1-й такт. Процедура сдвига информации описывается соотношением

a_j(k) = a_j-1(k-1), j = 2..m.

Для описания процедуры сжатия информации, основанной на применении примитивных полиномов, используются различные математические модели и алгоритмы. Одной из наиболее часто применяемых является модель, реализующая идею представления процедуры сжатия информации как операцию деления полиномов над полем GF(2). При этом в качестве делимого используется поток сжимаемых данных, описываемых полиномом c(x) степени l-1, где l-количество бит в последовательности. Так, например, последовательность 10011 имеет вид полинома c(х) = x⁴ÅxÅ1. Делителем служит примитивный полином y(х), в результате деления на который получается частное q(х) и остаток S(х), связанные классическим соотношением вида

c(x) = q(x)y(x) Å S(x),        (2.3)

где остаток S(х), представляющий собой полином степени, меньшей, чем  
m = deg y(x), называется сигнатурой.

Результат сжатия C(x) (m-разрядное число, содержащееся в a₁..a_m), получающийся по выражению (2.2), не совпадает с S(x), C(x)¹S(x), но линейно с ним связан.

Каковы же вероятности  того, что сигнатуры различаются  для двух различных последовательностей? Сигнатуры различаются для двух последовательностей любой длины l, отличающихся на один бит, и для всех последовательностей длиной l£2^m-1, отличающихся на два любых бита [2]. Для n-кратных изменений (l=2^m-2), при достаточно большом m, сигнатуры различаются с вероятностью » 1-1/2^m, что при m>7 практически равно единице. Единственный параметр, влияющий на значения вероятности - старшая степень m полинома j(х). Дальнейшие упоминания о таких вероятностях будут менее точны, поэтому когда надо будет уточнить, обращайтесь к этому абзацу.

3. Общий вид алгоритма

 

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

Для простоты понимания рассмотрим алгоритм, с функцией, преобразующий  один бит, и шагом в один бит.

k – длина последовательности, бит;

m – старшая степень полинома  для расчёта сигнатуры, а также  количество бит в элементах памяти (prev и next), хранящих сигнатуру;

сигнатура(предыдущая сигнатура, новый  бит) – функция, осуществляющая сжатие последовательности в сигнатуру;

f(x, a_i) – функция, осуществляющая преобразование бита a_i некоторым числом x;

a_i – i-ый бит последовательности.

Базовое преобразование (прямой ход) будет выглядеть так:

(3.1)

prev = 0;

для i от 1 до k

{

next = сигнатура(prev, a_i);

a_i = f(prev, a_i);

prev = next;

}

 

Обратное преобразование (прямой ход) будет выглядеть так:

(3.2)

prev = 0;

для i от 1 до k

{

a_i = f ^-1(prev, a_i);

prev = сигнатура(prev, a_i);

}

 

Как видим, изменение  бита a_i воздействует на все последующие биты, и вероятность того, что изменение этого бита отразиться на последующих, очень близка к единице. А что же делать с битами, предшествующими a_i, ведь изменение их не затронет? Поступим просто – совершим такое же преобразование повторно, но в обратном направлении.

 

Базовое преобразование, обратный ход:

(3.3)

prev = 0;

для i от k до 1

{

next = сигнатура(prev, a_i);

a_i = f(prev, a_i);

prev = next;

}

 

Обратное преобразование, обратный ход:

(3.4)

prev = 0;

для i от k до 1

{

a_i = f ^-1(prev, a_i);

prev = сигнатура(prev, a_i);

}

 

Преобразования (3.1) и (3.3) разносят изменения в любой точке  последовательности на всю последовательность целиком таким образом, что каждый бит становится связанным со всеми остальными, и его изменение повлечёт изменение остальных битов с вероятностью, очень близкой к единице. Для восстановления исходного текста надо применить последовательно преобразования (3.2) и (3.4).

Но вышеописанное обеспечивает полноценное воздействие изменений  только при преобразовании исходного  текста в зашифрованный, при обратном преобразовании воздействие изменений  в зашифрованном тексте на восстанавливаемый  исходный будет слабо. Решается это просто – вводим дополнительно после (3.1) и (3.3) преобразования, аналогичные (3.2) и (3.4), только используем не f ^–1(x, y), а f(x, y).

Выглядеть это будет  так:

Зашифровка

 

фаза 1 – защита от изменений  в исходном тексте

 

// прямой ход          (3.5)

prev = 0;

для i от 1 до k

{

next = сигнатура(prev, a_i);

a_i = f(prev, a_i);

prev = next;

}

// обратный ход          (3.6)

prev = 0;

для i от k до 1

{

next = сигнатура(prev, a_i);

a_i = f(prev, a_i);

prev = next;

}

 

фаза 2 – защита от изменений в зашифрованном тексте

 

// прямой ход          (3.7)

prev = 0;

для i от 1 до k

{

a_i = f(prev, a_i);

prev = сигнатура(prev, a_i);

}

// обратный ход          (3.8)

prev = 0;

для i от k до 1

{

a_i = f(prev, a_i);

prev = сигнатура(prev, a_i);

}

Расшифровка

 

// обратный ход          (3.8)^-1

prev = 0;

для i от k до 1

{

next = сигнатура(prev, a_i);

a_i = f ^-1(prev, a_i);

prev = next;

}

// прямой ход          (3.7)^-1

prev = 0;

для i от 1 до k

{

next = сигнатура(prev, a_i);

a_i = f ^-1(prev, a_i);

prev = next;

}

// обратный ход          (3.6)^-1

prev = 0;

для i от k до 1

{

a_i = f ^-1(prev, a_i);

prev = сигнатура(prev, a_i);

}

// прямой ход          (3.5)^-1

prev = 0;

для i от 1 до k

{

a_i = f ^-1(prev, a_i);

prev = сигнатура(prev, a_i);

}

 

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