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

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

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

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

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

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

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

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

prev = prev2 = 0;

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

{

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

a_i = f(prev, g_i, a_i);

prev = next;

a_i = f(prev2, g’_i, a_i);

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

}

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

prev = prev2 = 0;

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

{

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

a_i = f ^-1(prev2, g’_i, a_i);

prev2 = next2;

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

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

}

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, для которого вручную была проверена правильность работы процедуры. Правда максимальная длина ключа для него всего лишь пять байт L.

В [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 с.

P.S.

На данный момент в программе-примере  доступной на моей страничке используется примитивный полином 1Åx⁵⁰²Åx⁶⁰⁷, так же исходный код по сравнению с приводимым здесь улучшен и оптимизирован, и работает на порядок быстрее.

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

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