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

Размещено на http://www.allbest.ru/

Введение

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

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

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

1.1 Да, это надо

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2.1)

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

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

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

При соответствующем выборе коэффициентов i, на основании характеристического полинома (x)=11x12x23x3…m-1xm-1mxm, который должен быть примитивным, последовательность бит {ak} имеет максимальную длину, равную 2m-1. Такая последовательность называется M-последовательностью.

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

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

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

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

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

(2.2)

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

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

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

(x) = q(x)(x) S(x),(2.3)

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

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

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

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

криптосистема гаммирование шифрование сигнатура

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

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

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

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

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

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

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

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

(3.1)

prev = 0;

для i от 1 до k

{

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

ai = f(prev, ai);

prev = next;

}

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

(3.2)

prev = 0;

для i от 1 до k

{

ai = f -1(prev, ai);

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

}

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

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

(3.3)

prev = 0;

для i от k до 1

{

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

ai = f(prev, ai);

prev = next;

}

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

(3.4)

prev = 0;

для i от k до 1

{

ai = f -1(prev, ai);

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

}

Преобразования (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, ai);

ai = f(prev, ai);

prev = next;

}

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

prev = 0;

для i от k до 1

{

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

ai = f(prev, ai);

prev = next;

}

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

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

prev = 0;

для i от 1 до k

{

ai = f(prev, ai);

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

}

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

prev = 0;

для i от k до 1

{

ai = f(prev, ai);

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

}

Расшифровка

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

prev = 0;

для i от k до 1

{

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

ai = f -1(prev, ai);

prev = next;

}

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

prev = 0;

для i от 1 до k

{

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

ai = f -1(prev, ai);

prev = next;

}

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

prev = 0;

для i от k до 1

{

ai = f -1(prev, ai);

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

}

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

prev = 0;

для i от 1 до k

{

ai = f -1(prev, ai);

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

}

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

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

Как можно было заметить, преобразование осуществляется без какого-либо привлечения ключа, и имеет место однозначное соответствие исходной и преобразованной последовательности. Изменив вид функции на f(сигнатураi, i, ai), где - псевдослучайная последовательность, сгенерированная на основе ключа (или сам ключ, но это снизит криптостойкость), получим зависимость преобразованной последовательности от ключа. Для каждого из преобразований можно использовать различные участки гаммы. Причём из вышеописанного следует то, что малейшее изменение ключа приведёт к глобальному изменению всей преобразованной последовательности.

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

Такое преобразование уже не назовёшь гаммированием с обратной связью, как это описано в [1], это уже скорее свёртка.

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

Данный алгоритм можно применить для потокового шифрования данных. Поскольку конечная часть последовательности в реальном времени недоступна, преобразования (3.6) и (3.8) следует исключить, а преобразования (3.5) и (3.7) объединить. С одной стороны это повлияет на криптостойкость, поскольку нет влияния последующих битов на предыдущие, но с другой стороны конечная часть последовательности также недоступна для криптоанализа. Если процесс передачи данных допускает буферизацию хотя бы нескольких бит, то преобразования (3.6) и (3.8) можно модифицировать таким образом, чтобы они осуществлялись в пределах буфера. Следует предусмотреть процесс восстановления сигнатур в случае утери или искажения части сообщения, но это уже выходит за рамки статьи. Простейший способ - установка сигнатур в начальные (константные или определяемые по некоторому закону) значения после прохождения определённых объёмов данных и вставка синхронизирующей метки в последовательность. Выглядеть всё это будет приблизительно так:

// зашифровка

prev = prev2 = 0;

пока (не конец последовательности)

{

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

ai = f(prev, i, ai);

prev = next;

ai = f(prev2, 'i, ai);

prev2 = сигнатура(prev2, ai);

}

// расшифровка

prev = prev2 = 0;

пока(не конец последовательности)

{

next2 = сигнатура(prev2, ai);

ai = f -1(prev2, 'i, ai);

prev2 = next2;

ai = f -1(prev, i, ai);

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

}

4. Программная реализация (язык С)

Примечание: предполагается что типы int и unsigned имеют размер 4 байта.

Пример функции, генерирующей побитно псевдослучайную последовательность:

// примитивный неприводимый полином для формирования

// М-последовательности с периодом (2-11)-1

// fi(x) = 1(+)x^2(+)x^11

unsigned NextMValue(unsigned prev)

{

register unsigned c = 0;

if(prev & (1<<1))

c++;

if(prev & (1<<10))

c++;

return (prev<<1)|(c&1);

}

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

Пример функции, побитно сжимающей двоичную последовательность в сигнатуру:

// примитивный неприводимый полином

// для вычисления 32-битной сигнатуры

// fi(x) = 1(+)x^1(+)x^27(+)x^28(+)x^32

unsigned NextSignature32

(unsigned prev, unsigned newbit)

{

if(prev&(1<<0))

newbit++;

if(prev&(1<<26))

newbit++;

if(prev&(1<<27))

newbit++;

if(prev&(1<<31))

newbit++;

return (prev<<1)|(newbit&1);

}

Для генерации гаммы на основании ключа будем применять следующую функцию:

unsigned char * generate_gamma(unsigned char *pw, unsigned pwlen, unsigned gamma_len, unsigned char * gamma = NULL)

{

const

gb_len = 256;

static int

polynomial[] = { 1, 5, 23, 171, 243, 1057, 2047, -1 };

//polynomial[] = { 1, 18, 20, 39, -1 };// период 2^40 - 1

static unsigned char

buf[gb_len+1];

memset(buf, 0, sizeof(buf));

if(pwlen)

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

buf[i+1] = pw[i%pwlen];

else

buf[1] = 1;

if(!gamma)

gamma = new unsigned char [gamma_len];

for(int i = 0; i < gamma_len; i++) {

buf[0] = 0;

for(int j = 0; j < 8; j++) {

register unsigned char newbit = 0;

for(int k = 0; polynomial[k] >= 0; k++) {

register unsigned bit = (polynomial[k]+8-j);

if(buf[bit>>3]&(1<<(bit&7)))

newbit++;

}

buf[0] |= (newbit&1)<<(7-j);

}

memmove(buf+1, buf, gb_len);

gamma[i] = buf[0];

}

return gamma;

}

Эта функция может оперировать любым полиномом. Приведён полином степени 2048, или 256 байт. Задавать пароль длиннее 256 байт не имеет смысла, поскольку это никак не отразится на генерируемой гамме. Конечно можно предварительно подвергнуть пароль свёртке, но ведь тогда для вскрытия можно будет перебирать только 256 байт из свёртки, которые и используются для генерации гаммы. Полином взят «с потолка», поэтому для надёжной генерации гаммы следует использовать примитивный неприводимый полином. В комментариях указан примитивный полином степени 40, для которого вручную была проверена правильность работы процедуры. Правда максимальная длина ключа для него всего лишь пять байт.

В [1] указывались недостатки в применении М-последовательностей для генерации гаммы, и предлагалось использовать последовательности Голда, образующиеся суммированием нескольких М-последовательностей.

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

Для сжатия последовательности в сигнатуру используем известную и оптимизированную функцию crc32 (прилагается с исходными текстами):

unsigned crc32tab[] = {

0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,

0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,

0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,

0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,

0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,

0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,

0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,

0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,

0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,

0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,

0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,

0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,

0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,

0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,

0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,

0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,

0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,

0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,

0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,

0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,

0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,

0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,

0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,

0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,

0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,

0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,

0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,

0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,

0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,

0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,

0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,

0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,

0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,

0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,

0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,

0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,

0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,

0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,

0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,

0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,

0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,

0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,

0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,

0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,

0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,

0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,

0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,

0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,

0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,

0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,

0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,

0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,

0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,

0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,

0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,

0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,

0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,

0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,

0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,

0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,

0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,

0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,

0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,

0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d

};

// polynomial is

// X^32+ X^26+X^23+X^22+X^16+X ^12+X^11+X^10 +X^8 +X^7+ X^5+X^4+ X^2+X^1+X^0

unsigned crc32(unsigned crc, unsigned char *buf, unsigned buflen)

{

for(unsigned i = 0; i < buflen; i++)

crc = crc32tab[(unsigned char)(crc ^ unsigned(buf[i]))] ^ ((crc >> 8) & 0x00ffffff);

return crc;

}

Функции зашифровки/расшифровки:

void encrypt(unsigned char * buf, unsigned buflen, unsigned char * gamma)

{

unsigned prev, next;

unsigned char * pgamma;

// фаза 1

// защита от изменений в исходном тексте

// свёртка 1 - прямой ход

prev = 0xffffffff;

pgamma = gamma;

for(int i = 0; i < buflen; i++) {

next = crc32(prev, buf+i, 1);

next = crc32(next, pgamma+i, 1);// гаммирование

buf[i] += prev;

prev = next;

}

// свёртка 2 - обратный ход

prev = 0xffffffff;

pgamma = gamma+buflen;

for(int i = buflen-1; i >= 0; i--) {

next = crc32(prev, buf+i, 1);

next = crc32(next, pgamma+i, 1);// гаммирование

buf[i] += prev;

prev = next;

}

// фаза 2

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

// свёртка 3 - прямой ход

prev = 0xffffffff;

pgamma = gamma+(buflen<<1);

for(int i = 0; i < buflen; i++) {

buf[i] += prev;

prev = crc32(prev, buf+i, 1);

prev = crc32(prev, pgamma+i, 1);// гаммирование

}

// свёртка 4 - обратный ход

prev = 0xffffffff;

pgamma = gamma+(buflen<<1)+buflen;

for(int i = buflen-1; i >= 0; i--) {

buf[i] += prev;

prev = crc32(prev, buf+i, 1);

prev = crc32(prev, pgamma+i, 1);// гаммирование

}

}

void decrypt(unsigned char * buf, unsigned buflen, unsigned char * gamma)

{

unsigned prev, next;

unsigned char * pgamma;

// развёртка 4 - обратный ход

prev = 0xffffffff;

pgamma = gamma+(buflen<<1)+buflen;

for(int i = buflen-1; i >= 0; i--) {

next = crc32(prev, buf+i, 1);

next = crc32(next, pgamma+i, 1);// гаммирование

buf[i] -= prev;

prev = next;

}

// развёртка 3 - прямой ход

prev = 0xffffffff;

pgamma = gamma+(buflen<<1);

for(int i = 0; i < buflen; i++) {

next = crc32(prev, buf+i, 1);

next = crc32(next, pgamma+i, 1);// гаммирование

buf[i] -= prev;

prev = next;

}

// развёртка 2 - обратный ход

prev = 0xffffffff;

pgamma = gamma+buflen;

for(int i = buflen-1; i >= 0; i--) {

buf[i] -= prev;

prev = crc32(prev, buf+i, 1);

prev = crc32(prev, pgamma+i, 1);// гаммирование

}

// развёртка 1 - прямой ход

prev = 0xffffffff;

pgamma = gamma;

for(int i = 0; i < buflen; i++) {

buf[i] -= prev;

prev = crc32(prev, buf+i, 1);

prev = crc32(prev, pgamma+i, 1);// гаммирование

}

}

Функция шифрования файла:

int cryptfile(int encrypt, char *fn, unsigned char *pw, unsigned pwlen)

{

FILE * f = fopen(fn, "r+b");

unsigned char * buf, * gamma;

unsigned buflen;

if(!f)

return -1;

buflen = filelength(f->fd);

buf = new char[buflen];

gamma = generate_gamma(pw, pwlen, buflen<<2);

fread(buf, buflen, 1, f);

if(encrypt)

encrypt(buf, buflen, gamma);

else

decrypt(buf, buflen, gamma);

rewind(f);

fwrite(buf, buflen, 1, f);

memset(buf, 0xff, buflen);

memset(buf, 0, buflen);

memset(gamma, 0xff, buflen<<2);

memset(gamma, 0, buflen<<2);

delete buf;

delete gamma;

fclose(f);

return 0;

}

Проводился небольшой анализ на совпадение байт в преобразованных таким образом файлах. Для четырёх файлов, исходного, с изменённым одним битом в начале, конце и середине файла, совпадение байт (попарно, каждый с каждым) составило менее 0.5%. После сжатия архиватором RAR всех четырёх файлов в один solid-архив размер каждого файла увеличился (вот так;). В прилагаемой программе можно самостоятельно поэкспериментировать с шифровкой различных файлов. Имеется команда сравнения двух файлов. При преобразовании двух файлов они автоматически сравниваются. Попробуйте изменить несколько бит, посмотрите что будет. Кому мало, может усовершенствовать исходные тексты и экспериментировать дальше.

Заключение

Описанный алгоритм достигает поставленные цели.

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

Сама программа и исходные тексты прилагаются.

Литература

1. Баpичев Сеpгей Kpиптогpафия без секpетов (где искать не знаю, у самого только электронный вариант).

2. Ярмолик В.Н. Контроль и диагностика цифровых узлов ЭВМ - Минск: Наука и техника, 1988. - 240 с.

3. Ярмолик В.Н., Демиденко С.Н. Генерирование и применение псевдослучайных сигналов в системах испытаний и контроля - Минск: Наука и техника, 1986. - 200 с.

Размещено на Allbest.ru